1030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng//===-- BranchFolding.h - Fold machine code branch instructions --*- C++ -*===// 2030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng// 3030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng// The LLVM Compiler Infrastructure 4030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng// 5030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng// This file is distributed under the University of Illinois Open Source 6030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng// License. See LICENSE.TXT for details. 7030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng// 8030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng//===----------------------------------------------------------------------===// 9030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 10030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng#ifndef LLVM_CODEGEN_BRANCHFOLDING_HPP 11030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng#define LLVM_CODEGEN_BRANCHFOLDING_HPP 12030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 13f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola#include "llvm/ADT/SmallPtrSet.h" 14030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng#include "llvm/CodeGen/MachineBasicBlock.h" 15030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng#include <vector> 16030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 17030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Chengnamespace llvm { 18030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng class MachineFunction; 19030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng class MachineModuleInfo; 20030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng class RegScavenger; 21030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng class TargetInstrInfo; 22030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng class TargetRegisterInfo; 23030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 24030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng class BranchFolder { 25030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng public: 26cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist); 27030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 28030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool OptimizeFunction(MachineFunction &MF, 29030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetInstrInfo *tii, 30030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetRegisterInfo *tri, 31030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineModuleInfo *mmi); 32030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng private: 33ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman class MergePotentialsElt { 34ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned Hash; 35ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *Block; 36ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman public: 37ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MergePotentialsElt(unsigned h, MachineBasicBlock *b) 38ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman : Hash(h), Block(b) {} 39ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman 40ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned getHash() const { return Hash; } 41ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *getBlock() const { return Block; } 42ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman 43ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman void setBlock(MachineBasicBlock *MBB) { 44ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman Block = MBB; 45ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 46ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman 47ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman bool operator<(const MergePotentialsElt &) const; 48ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman }; 49030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng typedef std::vector<MergePotentialsElt>::iterator MPIterator; 50030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng std::vector<MergePotentialsElt> MergePotentials; 51f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4Rafael Espindola SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging; 52030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 53ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman class SameTailElt { 54ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MPIterator MPIter; 55ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock::iterator TailStartPos; 56ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman public: 57ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp) 58ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman : MPIter(mp), TailStartPos(tsp) {} 59ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman 60ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MPIterator getMPIter() const { 61ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return MPIter; 62ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 63ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MergePotentialsElt &getMergePotentialsElt() const { 64ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return *getMPIter(); 65ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 66ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock::iterator getTailStartPos() const { 67ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return TailStartPos; 68ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 69ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman unsigned getHash() const { 70ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return getMergePotentialsElt().getHash(); 71ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 72ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman MachineBasicBlock *getBlock() const { 73ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return getMergePotentialsElt().getBlock(); 74ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 75ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman bool tailIsWholeBlock() const { 76ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman return TailStartPos == getBlock()->begin(); 77ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 78ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman 79ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman void setBlock(MachineBasicBlock *MBB) { 80ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman getMergePotentialsElt().setBlock(MBB); 81ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 82ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman void setTailStartPos(MachineBasicBlock::iterator Pos) { 83ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman TailStartPos = Pos; 84ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman } 85ffe644ebf4dcc50b314261ddd2d08c841f629349Dan Gohman }; 86030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng std::vector<SameTailElt> SameTails; 87030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 88030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool EnableTailMerge; 89cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool EnableHoistCommonCode; 90030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetInstrInfo *TII; 91030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng const TargetRegisterInfo *TRI; 92030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineModuleInfo *MMI; 93030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng RegScavenger *RS; 94030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 95030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool TailMergeBlocks(MachineFunction &MF); 96412a3b90d1f4f1ad42c6c0e7e4e596f7ab688cb7Dan Gohman bool TryTailMergeBlocks(MachineBasicBlock* SuccBB, 97412a3b90d1f4f1ad42c6c0e7e4e596f7ab688cb7Dan Gohman MachineBasicBlock* PredBB); 98a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman void MaintainLiveIns(MachineBasicBlock *CurMBB, 99a38cfb2fceb266bd78164021c08284dc59a1e8a3Eli Friedman MachineBasicBlock *NewMBB); 100030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, 101030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineBasicBlock *NewDest); 102030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB, 103030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineBasicBlock::iterator BBI1); 104412a3b90d1f4f1ad42c6c0e7e4e596f7ab688cb7Dan Gohman unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength, 105412a3b90d1f4f1ad42c6c0e7e4e596f7ab688cb7Dan Gohman MachineBasicBlock *SuccBB, 106412a3b90d1f4f1ad42c6c0e7e4e596f7ab688cb7Dan Gohman MachineBasicBlock *PredBB); 107030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB, 108030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng MachineBasicBlock* PredBB); 1094d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB, 1104d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng unsigned maxCommonTailLength, 1114d54e5b2dd4a3d3bed38ff9c7aa57fc66adb5855Evan Cheng unsigned &commonTailIndex); 112030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 113030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool OptimizeBranches(MachineFunction &MF); 114030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool OptimizeBlock(MachineBasicBlock *MBB); 115030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng void RemoveDeadBlock(MachineBasicBlock *MBB); 116030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng bool OptimizeImpDefsBlock(MachineBasicBlock *MBB); 117cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng 118cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool HoistCommonCode(MachineFunction &MF); 119cbc988be22bc9411d95215c8b7251b5f85710674Evan Cheng bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB); 120030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng }; 121030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng} 122030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng 123030a0a0cdb38924e55773a8e0b5fe7347aa664aaEvan Cheng#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */ 124