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 25using 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. 29static cl::opt<uint32_t> BranchRelaxSafetyBuffer("branch-relax-safety-buffer", 30 cl::init(200), cl::Hidden, cl::ZeroOrMore, cl::desc("safety buffer size")); 31 32namespace llvm { 33 FunctionPass *createHexagonBranchRelaxation(); 34 void initializeHexagonBranchRelaxationPass(PassRegistry&); 35} 36 37namespace { 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 72INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax", 73 "Hexagon Branch Relaxation", false, false) 74 75FunctionPass *llvm::createHexagonBranchRelaxation() { 76 return new HexagonBranchRelaxation(); 77} 78 79 80bool 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 93void 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. 117bool 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. 132bool 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 180bool 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