1 //===--- HexagonBranchRelaxation.cpp - Identify and relax long jumps ------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #define DEBUG_TYPE "hexagon-brelax" 11 12 #include "Hexagon.h" 13 #include "HexagonInstrInfo.h" 14 #include "HexagonSubtarget.h" 15 #include "HexagonTargetMachine.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/CodeGen/MachineFunction.h" 18 #include "llvm/CodeGen/MachineFunctionPass.h" 19 #include "llvm/CodeGen/Passes.h" 20 #include "llvm/PassSupport.h" 21 #include "llvm/Support/CommandLine.h" 22 #include "llvm/Support/Debug.h" 23 #include "llvm/Support/raw_ostream.h" 24 25 using namespace llvm; 26 27 // Since we have no exact knowledge of code layout, allow some safety buffer 28 // for jump target. This is measured in bytes. 29 static cl::opt<uint32_t> BranchRelaxSafetyBuffer("branch-relax-safety-buffer", 30 cl::init(200), cl::Hidden, cl::ZeroOrMore, cl::desc("safety buffer size")); 31 32 namespace llvm { 33 FunctionPass *createHexagonBranchRelaxation(); 34 void initializeHexagonBranchRelaxationPass(PassRegistry&); 35 } 36 37 namespace { 38 struct HexagonBranchRelaxation : public MachineFunctionPass { 39 public: 40 static char ID; 41 HexagonBranchRelaxation() : MachineFunctionPass(ID) { 42 initializeHexagonBranchRelaxationPass(*PassRegistry::getPassRegistry()); 43 } 44 45 bool runOnMachineFunction(MachineFunction &MF) override; 46 47 const char *getPassName() const override { 48 return "Hexagon Branch Relaxation"; 49 } 50 51 void getAnalysisUsage(AnalysisUsage &AU) const override { 52 AU.setPreservesCFG(); 53 MachineFunctionPass::getAnalysisUsage(AU); 54 } 55 56 private: 57 const HexagonInstrInfo *HII; 58 const HexagonRegisterInfo *HRI; 59 60 bool relaxBranches(MachineFunction &MF); 61 void computeOffset(MachineFunction &MF, 62 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset); 63 bool reGenerateBranch(MachineFunction &MF, 64 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset); 65 bool isJumpOutOfRange(MachineInstr &MI, 66 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset); 67 }; 68 69 char HexagonBranchRelaxation::ID = 0; 70 } // end anonymous namespace 71 72 INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax", 73 "Hexagon Branch Relaxation", false, false) 74 75 FunctionPass *llvm::createHexagonBranchRelaxation() { 76 return new HexagonBranchRelaxation(); 77 } 78 79 80 bool HexagonBranchRelaxation::runOnMachineFunction(MachineFunction &MF) { 81 DEBUG(dbgs() << "****** Hexagon Branch Relaxation ******\n"); 82 83 auto &HST = MF.getSubtarget<HexagonSubtarget>(); 84 HII = HST.getInstrInfo(); 85 HRI = HST.getRegisterInfo(); 86 87 bool Changed = false; 88 Changed = relaxBranches(MF); 89 return Changed; 90 } 91 92 93 void HexagonBranchRelaxation::computeOffset(MachineFunction &MF, 94 DenseMap<MachineBasicBlock*, unsigned> &OffsetMap) { 95 // offset of the current instruction from the start. 96 unsigned InstOffset = 0; 97 for (auto &B : MF) { 98 if (B.getAlignment()) { 99 // Although we don't know the exact layout of the final code, we need 100 // to account for alignment padding somehow. This heuristic pads each 101 // aligned basic block according to the alignment value. 102 int ByteAlign = (1u << B.getAlignment()) - 1; 103 InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign); 104 } 105 OffsetMap[&B] = InstOffset; 106 for (auto &MI : B.instrs()) 107 InstOffset += HII->getSize(&MI); 108 } 109 } 110 111 112 /// relaxBranches - For Hexagon, if the jump target/loop label is too far from 113 /// the jump/loop instruction then, we need to make sure that we have constant 114 /// extenders set for jumps and loops. 115 116 /// There are six iterations in this phase. It's self explanatory below. 117 bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) { 118 // Compute the offset of each basic block 119 // offset of the current instruction from the start. 120 // map for each instruction to the beginning of the function 121 DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset; 122 computeOffset(MF, BlockToInstOffset); 123 124 return reGenerateBranch(MF, BlockToInstOffset); 125 } 126 127 128 /// Check if a given instruction is: 129 /// - a jump to a distant target 130 /// - that exceeds its immediate range 131 /// If both conditions are true, it requires constant extension. 132 bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI, 133 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) { 134 MachineBasicBlock &B = *MI.getParent(); 135 auto FirstTerm = B.getFirstInstrTerminator(); 136 if (FirstTerm == B.instr_end()) 137 return false; 138 139 unsigned InstOffset = BlockToInstOffset[&B]; 140 unsigned Distance = 0; 141 142 // To save time, estimate exact position of a branch instruction 143 // as one at the end of the MBB. 144 // Number of instructions times typical instruction size. 145 InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE; 146 147 MachineBasicBlock *TBB = NULL, *FBB = NULL; 148 SmallVector<MachineOperand, 4> Cond; 149 150 // Try to analyze this branch. 151 if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) { 152 // Could not analyze it. See if this is something we can recognize. 153 // If it is a NVJ, it should always have its target in 154 // a fixed location. 155 if (HII->isNewValueJump(&*FirstTerm)) 156 TBB = FirstTerm->getOperand(HII->getCExtOpNum(&*FirstTerm)).getMBB(); 157 } 158 if (TBB && &MI == &*FirstTerm) { 159 Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB]) 160 + BranchRelaxSafetyBuffer; 161 return !HII->isJumpWithinBranchRange(&*FirstTerm, Distance); 162 } 163 if (FBB) { 164 // Look for second terminator. 165 auto SecondTerm = std::next(FirstTerm); 166 assert(SecondTerm != B.instr_end() && 167 (SecondTerm->isBranch() || SecondTerm->isCall()) && 168 "Bad second terminator"); 169 if (&MI != &*SecondTerm) 170 return false; 171 // Analyze the second branch in the BB. 172 Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB]) 173 + BranchRelaxSafetyBuffer; 174 return !HII->isJumpWithinBranchRange(&*SecondTerm, Distance); 175 } 176 return false; 177 } 178 179 180 bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF, 181 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) { 182 bool Changed = false; 183 184 for (auto &B : MF) { 185 for (auto &MI : B) { 186 if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset)) 187 continue; 188 DEBUG(dbgs() << "Long distance jump. isExtendable(" 189 << HII->isExtendable(&MI) << ") isConstExtended(" 190 << HII->isConstExtended(&MI) << ") " << MI); 191 192 // Since we have not merged HW loops relaxation into 193 // this code (yet), soften our approach for the moment. 194 if (!HII->isExtendable(&MI) && !HII->isExtended(&MI)) { 195 DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n"); 196 } else { 197 // Find which operand is expandable. 198 int ExtOpNum = HII->getCExtOpNum(&MI); 199 MachineOperand &MO = MI.getOperand(ExtOpNum); 200 // This need to be something we understand. So far we assume all 201 // branches have only MBB address as expandable field. 202 // If it changes, this will need to be expanded. 203 assert(MO.isMBB() && "Branch with unknown expandable field type"); 204 // Mark given operand as extended. 205 MO.addTargetFlag(HexagonII::HMOTF_ConstExtended); 206 Changed = true; 207 } 208 } 209 } 210 return Changed; 211 } 212