contrib/llvm/lib/Target/Hexagon/HexagonBranchRelaxation.cpp

   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 "llvm/ADT/DenseMap.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/ADT/StringRef.h"
  18 #include "llvm/CodeGen/MachineBasicBlock.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineOperand.h"
  23 #include "llvm/CodeGen/Passes.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <cassert>
  29 #include <cstdint>
  30 #include <cstdlib>
  31 #include <iterator>
  32
  33 using namespace llvm;
  34
  35 // Since we have no exact knowledge of code layout, allow some safety buffer
  36 // for jump target. This is measured in bytes.
  37 static cl::opt<uint32_t> BranchRelaxSafetyBuffer("branch-relax-safety-buffer",
  38   cl::init(200), cl::Hidden, cl::ZeroOrMore, 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()) {
 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       int ByteAlign = (1u << B.getAlignment()) - 1;
 114       InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
 115     }
 116     OffsetMap[&B] = InstOffset;
 117     for (auto &MI : B.instrs()) {
 118       InstOffset += HII->getSize(MI);
 119       // Assume that all extendable branches will be extended.
 120       if (MI.isBranch() && HII->isExtendable(MI))
 121         InstOffset += HEXAGON_INSTR_SIZE;
 122     }
 123   }
 124 }
 125
 126 /// relaxBranches - For Hexagon, if the jump target/loop label is too far from
 127 /// the jump/loop instruction then, we need to make sure that we have constant
 128 /// extenders set for jumps and loops.
 129
 130 /// There are six iterations in this phase. It's self explanatory below.
 131 bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
 132   // Compute the offset of each basic block
 133   // offset of the current instruction from the start.
 134   // map for each instruction to the beginning of the function
 135   DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
 136   computeOffset(MF, BlockToInstOffset);
 137
 138   return reGenerateBranch(MF, BlockToInstOffset);
 139 }
 140
 141 /// Check if a given instruction is:
 142 /// - a jump to a distant target
 143 /// - that exceeds its immediate range
 144 /// If both conditions are true, it requires constant extension.
 145 bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
 146       DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
 147   MachineBasicBlock &B = *MI.getParent();
 148   auto FirstTerm = B.getFirstInstrTerminator();
 149   if (FirstTerm == B.instr_end())
 150     return false;
 151
 152   if (HII->isExtended(MI))
 153     return false;
 154
 155   unsigned InstOffset = BlockToInstOffset[&B];
 156   unsigned Distance = 0;
 157
 158   // To save time, estimate exact position of a branch instruction
 159   // as one at the end of the MBB.
 160   // Number of instructions times typical instruction size.
 161   InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
 162
 163   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 164   SmallVector<MachineOperand, 4> Cond;
 165
 166   // Try to analyze this branch.
 167   if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
 168     // Could not analyze it. See if this is something we can recognize.
 169     // If it is a NVJ, it should always have its target in
 170     // a fixed location.
 171     if (HII->isNewValueJump(*FirstTerm))
 172       TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
 173   }
 174   if (TBB && &MI == &*FirstTerm) {
 175     Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
 176                 + BranchRelaxSafetyBuffer;
 177     return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
 178   }
 179   if (FBB) {
 180     // Look for second terminator.
 181     auto SecondTerm = std::next(FirstTerm);
 182     assert(SecondTerm != B.instr_end() &&
 183           (SecondTerm->isBranch() || SecondTerm->isCall()) &&
 184           "Bad second terminator");
 185     if (&MI != &*SecondTerm)
 186       return false;
 187     // Analyze the second branch in the BB.
 188     Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
 189                 + BranchRelaxSafetyBuffer;
 190     return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
 191   }
 192   return false;
 193 }
 194
 195 bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
 196       DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
 197   bool Changed = false;
 198
 199   for (auto &B : MF) {
 200     for (auto &MI : B) {
 201       if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
 202         continue;
 203       LLVM_DEBUG(dbgs() << "Long distance jump. isExtendable("
 204                         << HII->isExtendable(MI) << ") isConstExtended("
 205                         << HII->isConstExtended(MI) << ") " << MI);
 206
 207       // Since we have not merged HW loops relaxation into
 208       // this code (yet), soften our approach for the moment.
 209       if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
 210         LLVM_DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
 211       } else {
 212         // Find which operand is expandable.
 213         int ExtOpNum = HII->getCExtOpNum(MI);
 214         MachineOperand &MO = MI.getOperand(ExtOpNum);
 215         // This need to be something we understand. So far we assume all
 216         // branches have only MBB address as expandable field.
 217         // If it changes, this will need to be expanded.
 218         assert(MO.isMBB() && "Branch with unknown expandable field type");
 219         // Mark given operand as extended.
 220         MO.addTargetFlag(HexagonII::HMOTF_ConstExtended);
 221         Changed = true;
 222       }
 223     }
 224   }
 225   return Changed;
 226 }