205 lines · c
1//===- BranchFolding.h - Fold machine code branch instructions --*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H10#define LLVM_LIB_CODEGEN_BRANCHFOLDING_H11 12#include "llvm/ADT/DenseMap.h"13#include "llvm/ADT/SmallPtrSet.h"14#include "llvm/CodeGen/LivePhysRegs.h"15#include "llvm/CodeGen/MachineBasicBlock.h"16#include "llvm/Support/Compiler.h"17#include <vector>18 19namespace llvm {20 21class BasicBlock;22class MachineBranchProbabilityInfo;23class MachineFunction;24class MachineLoopInfo;25class MachineRegisterInfo;26class MBFIWrapper;27class ProfileSummaryInfo;28class TargetInstrInfo;29class TargetRegisterInfo;30 31 class LLVM_LIBRARY_VISIBILITY BranchFolder {32 public:33 explicit BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,34 MBFIWrapper &FreqInfo,35 const MachineBranchProbabilityInfo &ProbInfo,36 ProfileSummaryInfo *PSI,37 // Min tail length to merge. Defaults to commandline38 // flag. Ignored for optsize.39 unsigned MinTailLength = 0);40 41 /// Perhaps branch folding, tail merging and other CFG optimizations on the42 /// given function. Block placement changes the layout and may create new43 /// tail merging opportunities.44 bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,45 const TargetRegisterInfo *tri,46 MachineLoopInfo *mli = nullptr,47 bool AfterPlacement = false);48 49 private:50 class MergePotentialsElt {51 unsigned Hash;52 MachineBasicBlock *Block;53 DebugLoc BranchDebugLoc;54 55 public:56 MergePotentialsElt(unsigned h, MachineBasicBlock *b, DebugLoc bdl)57 : Hash(h), Block(b), BranchDebugLoc(std::move(bdl)) {}58 59 unsigned getHash() const { return Hash; }60 MachineBasicBlock *getBlock() const { return Block; }61 62 void setBlock(MachineBasicBlock *MBB) {63 Block = MBB;64 }65 66 const DebugLoc &getBranchDebugLoc() { return BranchDebugLoc; }67 68 bool operator<(const MergePotentialsElt &) const;69 };70 71 using MPIterator = std::vector<MergePotentialsElt>::iterator;72 73 std::vector<MergePotentialsElt> MergePotentials;74 SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;75 DenseMap<const MachineBasicBlock *, int> EHScopeMembership;76 77 class SameTailElt {78 MPIterator MPIter;79 MachineBasicBlock::iterator TailStartPos;80 81 public:82 SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)83 : MPIter(mp), TailStartPos(tsp) {}84 85 MPIterator getMPIter() const {86 return MPIter;87 }88 89 MergePotentialsElt &getMergePotentialsElt() const {90 return *getMPIter();91 }92 93 MachineBasicBlock::iterator getTailStartPos() const {94 return TailStartPos;95 }96 97 unsigned getHash() const {98 return getMergePotentialsElt().getHash();99 }100 101 MachineBasicBlock *getBlock() const {102 return getMergePotentialsElt().getBlock();103 }104 105 bool tailIsWholeBlock() const {106 return TailStartPos == getBlock()->begin();107 }108 109 void setBlock(MachineBasicBlock *MBB) {110 getMergePotentialsElt().setBlock(MBB);111 }112 113 void setTailStartPos(MachineBasicBlock::iterator Pos) {114 TailStartPos = Pos;115 }116 };117 std::vector<SameTailElt> SameTails;118 119 bool AfterBlockPlacement = false;120 bool EnableTailMerge = false;121 bool EnableHoistCommonCode = false;122 bool UpdateLiveIns = false;123 unsigned MinCommonTailLength;124 const TargetInstrInfo *TII = nullptr;125 const MachineRegisterInfo *MRI = nullptr;126 const TargetRegisterInfo *TRI = nullptr;127 MachineLoopInfo *MLI = nullptr;128 LivePhysRegs LiveRegs;129 130 private:131 MBFIWrapper &MBBFreqInfo;132 const MachineBranchProbabilityInfo &MBPI;133 ProfileSummaryInfo *PSI;134 135 bool TailMergeBlocks(MachineFunction &MF);136 bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,137 MachineBasicBlock* PredBB,138 unsigned MinCommonTailLength);139 void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);140 141 /// Delete the instruction OldInst and everything after it, replacing it142 /// with an unconditional branch to NewDest.143 void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,144 MachineBasicBlock &NewDest);145 146 /// Given a machine basic block and an iterator into it, split the MBB so147 /// that the part before the iterator falls into the part starting at the148 /// iterator. This returns the new MBB.149 MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,150 MachineBasicBlock::iterator BBI1,151 const BasicBlock *BB);152 153 /// Look through all the blocks in MergePotentials that have hash CurHash154 /// (guaranteed to match the last element). Build the vector SameTails of155 /// all those that have the (same) largest number of instructions in common156 /// of any pair of these blocks. SameTails entries contain an iterator into157 /// MergePotentials (from which the MachineBasicBlock can be found) and a158 /// MachineBasicBlock::iterator into that MBB indicating the instruction159 /// where the matching code sequence begins. Order of elements in SameTails160 /// is the reverse of the order in which those blocks appear in161 /// MergePotentials (where they are not necessarily consecutive).162 unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,163 MachineBasicBlock *SuccBB,164 MachineBasicBlock *PredBB);165 166 /// Remove all blocks with hash CurHash from MergePotentials, restoring167 /// branches at ends of blocks as appropriate.168 void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock *SuccBB,169 MachineBasicBlock *PredBB,170 const DebugLoc &BranchDL);171 172 /// None of the blocks to be tail-merged consist only of the common tail.173 /// Create a block that does by splitting one.174 bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,175 MachineBasicBlock *SuccBB,176 unsigned maxCommonTailLength,177 unsigned &commonTailIndex);178 179 /// Create merged DebugLocs of identical instructions across SameTails and180 /// assign it to the instruction in common tail; merge MMOs and undef flags.181 void mergeCommonTails(unsigned commonTailIndex);182 183 bool OptimizeBranches(MachineFunction &MF);184 185 /// Analyze and optimize control flow related to the specified block. This186 /// is never called on the entry block.187 bool OptimizeBlock(MachineBasicBlock *MBB);188 189 /// Remove the specified dead machine basic block from the function,190 /// updating the CFG.191 void RemoveDeadBlock(MachineBasicBlock *MBB);192 193 /// Hoist common instruction sequences at the start of basic blocks to their194 /// common predecessor.195 bool HoistCommonCode(MachineFunction &MF);196 197 /// If the successors of MBB has common instruction sequence at the start of198 /// the function, move the instructions before MBB terminator if it's legal.199 bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);200 };201 202} // end namespace llvm203 204#endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H205