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