contrib/llvm/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()) {
 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       int ByteAlign = (1u << B.getAlignment()) - 1;
 113       InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
 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 }