lib/Target/Hexagon/HexagonBranchRelaxation.cpp

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