1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- BranchFolding.h - Fold machine code branch instructions --*- C++ -*===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_CODEGEN_BRANCHFOLDING_HPP 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_CODEGEN_BRANCHFOLDING_HPP 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/SmallPtrSet.h" 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineBasicBlock.h" 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <vector> 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class MachineFunction; 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class MachineModuleInfo; 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class RegScavenger; 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class TargetInstrInfo; 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class TargetRegisterInfo; 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class BranchFolder { 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist); 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OptimizeFunction(MachineFunction &MF, 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetInstrInfo *tii, 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterInfo *tri, 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineModuleInfo *mmi); 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class MergePotentialsElt { 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Hash; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *Block; 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MergePotentialsElt(unsigned h, MachineBasicBlock *b) 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Hash(h), Block(b) {} 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getHash() const { return Hash; } 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *getBlock() const { return Block; } 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setBlock(MachineBasicBlock *MBB) { 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Block = MBB; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator<(const MergePotentialsElt &) const; 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<MergePotentialsElt>::iterator MPIterator; 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<MergePotentialsElt> MergePotentials; 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging; 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class SameTailElt { 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MPIterator MPIter; 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator TailStartPos; 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp) 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : MPIter(mp), TailStartPos(tsp) {} 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MPIterator getMPIter() const { 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MPIter; 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MergePotentialsElt &getMergePotentialsElt() const { 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *getMPIter(); 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator getTailStartPos() const { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return TailStartPos; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getHash() const { 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getMergePotentialsElt().getHash(); 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *getBlock() const { 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getMergePotentialsElt().getBlock(); 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool tailIsWholeBlock() const { 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return TailStartPos == getBlock()->begin(); 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setBlock(MachineBasicBlock *MBB) { 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman getMergePotentialsElt().setBlock(MBB); 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setTailStartPos(MachineBasicBlock::iterator Pos) { 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TailStartPos = Pos; 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<SameTailElt> SameTails; 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool EnableTailMerge; 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool EnableHoistCommonCode; 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetInstrInfo *TII; 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterInfo *TRI; 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineModuleInfo *MMI; 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegScavenger *RS; 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool TailMergeBlocks(MachineFunction &MF); 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool TryTailMergeBlocks(MachineBasicBlock* SuccBB, 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock* PredBB); 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void MaintainLiveIns(MachineBasicBlock *CurMBB, 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *NewMBB); 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *NewDest); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator BBI1); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength, 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *SuccBB, 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *PredBB); 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock* PredBB); 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned maxCommonTailLength, 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned &commonTailIndex); 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OptimizeBranches(MachineFunction &MF); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OptimizeBlock(MachineBasicBlock *MBB); 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RemoveDeadBlock(MachineBasicBlock *MBB); 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OptimizeImpDefsBlock(MachineBasicBlock *MBB); 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool HoistCommonCode(MachineFunction &MF); 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB); 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */ 124