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