1198090Srdivacky//===-- BranchFolding.h - Fold machine code branch instructions --*- C++ -*===// 2198090Srdivacky// 3198090Srdivacky// The LLVM Compiler Infrastructure 4198090Srdivacky// 5198090Srdivacky// This file is distributed under the University of Illinois Open Source 6198090Srdivacky// License. See LICENSE.TXT for details. 7198090Srdivacky// 8198090Srdivacky//===----------------------------------------------------------------------===// 9198090Srdivacky 10198090Srdivacky#ifndef LLVM_CODEGEN_BRANCHFOLDING_HPP 11198090Srdivacky#define LLVM_CODEGEN_BRANCHFOLDING_HPP 12198090Srdivacky 13224145Sdim#include "llvm/ADT/SmallPtrSet.h" 14198090Srdivacky#include "llvm/CodeGen/MachineBasicBlock.h" 15198090Srdivacky#include <vector> 16198090Srdivacky 17198090Srdivackynamespace llvm { 18198090Srdivacky class MachineFunction; 19198090Srdivacky class MachineModuleInfo; 20198090Srdivacky class RegScavenger; 21198090Srdivacky class TargetInstrInfo; 22198090Srdivacky class TargetRegisterInfo; 23198090Srdivacky 24198090Srdivacky class BranchFolder { 25198090Srdivacky public: 26223017Sdim explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist); 27198090Srdivacky 28198090Srdivacky bool OptimizeFunction(MachineFunction &MF, 29198090Srdivacky const TargetInstrInfo *tii, 30198090Srdivacky const TargetRegisterInfo *tri, 31198090Srdivacky MachineModuleInfo *mmi); 32198090Srdivacky private: 33199481Srdivacky class MergePotentialsElt { 34199481Srdivacky unsigned Hash; 35199481Srdivacky MachineBasicBlock *Block; 36199481Srdivacky public: 37199481Srdivacky MergePotentialsElt(unsigned h, MachineBasicBlock *b) 38199481Srdivacky : Hash(h), Block(b) {} 39199481Srdivacky 40199481Srdivacky unsigned getHash() const { return Hash; } 41199481Srdivacky MachineBasicBlock *getBlock() const { return Block; } 42199481Srdivacky 43199481Srdivacky void setBlock(MachineBasicBlock *MBB) { 44199481Srdivacky Block = MBB; 45199481Srdivacky } 46199481Srdivacky 47199481Srdivacky bool operator<(const MergePotentialsElt &) const; 48199481Srdivacky }; 49198090Srdivacky typedef std::vector<MergePotentialsElt>::iterator MPIterator; 50198090Srdivacky std::vector<MergePotentialsElt> MergePotentials; 51224145Sdim SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging; 52198090Srdivacky 53199481Srdivacky class SameTailElt { 54199481Srdivacky MPIterator MPIter; 55199481Srdivacky MachineBasicBlock::iterator TailStartPos; 56199481Srdivacky public: 57199481Srdivacky SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp) 58199481Srdivacky : MPIter(mp), TailStartPos(tsp) {} 59199481Srdivacky 60199481Srdivacky MPIterator getMPIter() const { 61199481Srdivacky return MPIter; 62199481Srdivacky } 63199481Srdivacky MergePotentialsElt &getMergePotentialsElt() const { 64199481Srdivacky return *getMPIter(); 65199481Srdivacky } 66199481Srdivacky MachineBasicBlock::iterator getTailStartPos() const { 67199481Srdivacky return TailStartPos; 68199481Srdivacky } 69199481Srdivacky unsigned getHash() const { 70199481Srdivacky return getMergePotentialsElt().getHash(); 71199481Srdivacky } 72199481Srdivacky MachineBasicBlock *getBlock() const { 73199481Srdivacky return getMergePotentialsElt().getBlock(); 74199481Srdivacky } 75199481Srdivacky bool tailIsWholeBlock() const { 76199481Srdivacky return TailStartPos == getBlock()->begin(); 77199481Srdivacky } 78199481Srdivacky 79199481Srdivacky void setBlock(MachineBasicBlock *MBB) { 80199481Srdivacky getMergePotentialsElt().setBlock(MBB); 81199481Srdivacky } 82199481Srdivacky void setTailStartPos(MachineBasicBlock::iterator Pos) { 83199481Srdivacky TailStartPos = Pos; 84199481Srdivacky } 85199481Srdivacky }; 86198090Srdivacky std::vector<SameTailElt> SameTails; 87198090Srdivacky 88198090Srdivacky bool EnableTailMerge; 89223017Sdim bool EnableHoistCommonCode; 90198090Srdivacky const TargetInstrInfo *TII; 91198090Srdivacky const TargetRegisterInfo *TRI; 92198090Srdivacky MachineModuleInfo *MMI; 93198090Srdivacky RegScavenger *RS; 94198090Srdivacky 95198090Srdivacky bool TailMergeBlocks(MachineFunction &MF); 96199481Srdivacky bool TryTailMergeBlocks(MachineBasicBlock* SuccBB, 97199481Srdivacky MachineBasicBlock* PredBB); 98224145Sdim void MaintainLiveIns(MachineBasicBlock *CurMBB, 99224145Sdim MachineBasicBlock *NewMBB); 100198090Srdivacky void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 101198090Srdivacky MachineBasicBlock *NewDest); 102198090Srdivacky MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 103198090Srdivacky MachineBasicBlock::iterator BBI1); 104199481Srdivacky unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength, 105199481Srdivacky MachineBasicBlock *SuccBB, 106199481Srdivacky MachineBasicBlock *PredBB); 107198090Srdivacky void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, 108198090Srdivacky MachineBasicBlock* PredBB); 109210299Sed bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 110210299Sed unsigned maxCommonTailLength, 111210299Sed unsigned &commonTailIndex); 112198090Srdivacky 113198090Srdivacky bool OptimizeBranches(MachineFunction &MF); 114198090Srdivacky bool OptimizeBlock(MachineBasicBlock *MBB); 115198090Srdivacky void RemoveDeadBlock(MachineBasicBlock *MBB); 116198090Srdivacky bool OptimizeImpDefsBlock(MachineBasicBlock *MBB); 117223017Sdim 118223017Sdim bool HoistCommonCode(MachineFunction &MF); 119223017Sdim bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB); 120198090Srdivacky }; 121198090Srdivacky} 122198090Srdivacky 123198090Srdivacky#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */ 124