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   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   }
 120 }
 121
 122 /// relaxBranches - For Hexagon, if the jump target/loop label is too far from
 123 /// the jump/loop instruction then, we need to make sure that we have constant
 124 /// extenders set for jumps and loops.
 125
 126 /// There are six iterations in this phase. It's self explanatory below.
 127 bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
 128   // Compute the offset of each basic block
 129   // offset of the current instruction from the start.
 130   // map for each instruction to the beginning of the function
 131   DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
 132   computeOffset(MF, BlockToInstOffset);
 133
 134   return reGenerateBranch(MF, BlockToInstOffset);
 135 }
 136
 137 /// Check if a given instruction is:
 138 /// - a jump to a distant target
 139 /// - that exceeds its immediate range
 140 /// If both conditions are true, it requires constant extension.
 141 bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
 142       DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
 143   MachineBasicBlock &B = *MI.getParent();
 144   auto FirstTerm = B.getFirstInstrTerminator();
 145   if (FirstTerm == B.instr_end())
 146     return false;
 147
 148   unsigned InstOffset = BlockToInstOffset[&B];
 149   unsigned Distance = 0;
 150
 151   // To save time, estimate exact position of a branch instruction
 152   // as one at the end of the MBB.
 153   // Number of instructions times typical instruction size.
 154   InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
 155
 156   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 157   SmallVector<MachineOperand, 4> Cond;
 158
 159   // Try to analyze this branch.
 160   if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
 161     // Could not analyze it. See if this is something we can recognize.
 162     // If it is a NVJ, it should always have its target in
 163     // a fixed location.
 164     if (HII->isNewValueJump(*FirstTerm))
 165       TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
 166   }
 167   if (TBB && &MI == &*FirstTerm) {
 168     Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
 169                 + BranchRelaxSafetyBuffer;
 170     return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
 171   }
 172   if (FBB) {
 173     // Look for second terminator.
 174     auto SecondTerm = std::next(FirstTerm);
 175     assert(SecondTerm != B.instr_end() &&
 176           (SecondTerm->isBranch() || SecondTerm->isCall()) &&
 177           "Bad second terminator");
 178     if (&MI != &*SecondTerm)
 179       return false;
 180     // Analyze the second branch in the BB.
 181     Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
 182                 + BranchRelaxSafetyBuffer;
 183     return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
 184   }
 185   return false;
 186 }
 187
 188 bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
 189       DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
 190   bool Changed = false;
 191
 192   for (auto &B : MF) {
 193     for (auto &MI : B) {
 194       if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
 195         continue;
 196       DEBUG(dbgs() << "Long distance jump. isExtendable("
 197                    << HII->isExtendable(MI) << ") isConstExtended("
 198                    << HII->isConstExtended(MI) << ") " << MI);
 199
 200       // Since we have not merged HW loops relaxation into
 201       // this code (yet), soften our approach for the moment.
 202       if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
 203         DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
 204       } else {
 205         // Find which operand is expandable.
 206         int ExtOpNum = HII->getCExtOpNum(MI);
 207         MachineOperand &MO = MI.getOperand(ExtOpNum);
 208         // This need to be something we understand. So far we assume all
 209         // branches have only MBB address as expandable field.
 210         // If it changes, this will need to be expanded.
 211         assert(MO.isMBB() && "Branch with unknown expandable field type");
 212         // Mark given operand as extended.
 213         MO.addTargetFlag(HexagonII::HMOTF_ConstExtended);
 214         Changed = true;
 215       }
 216     }
 217   }
 218   return Changed;
 219 }