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#include "Hexagon.h"
10#include "HexagonInstrInfo.h"
11#include "HexagonSubtarget.h"
12#include "llvm/ADT/DenseMap.h"
13#include "llvm/ADT/SmallVector.h"
14#include "llvm/ADT/StringRef.h"
15#include "llvm/CodeGen/MachineBasicBlock.h"
16#include "llvm/CodeGen/MachineFunction.h"
17#include "llvm/CodeGen/MachineFunctionPass.h"
18#include "llvm/CodeGen/MachineInstr.h"
19#include "llvm/CodeGen/MachineOperand.h"
20#include "llvm/CodeGen/Passes.h"
21#include "llvm/Pass.h"
22#include "llvm/Support/CommandLine.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/raw_ostream.h"
25#include <cassert>
26#include <cstdint>
27#include <cstdlib>
28#include <iterator>
29
30#define DEBUG_TYPE "hexagon-brelax"
31
32using 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.
36static cl::opt<uint32_t>
37 BranchRelaxSafetyBuffer("branch-relax-safety-buffer", cl::init(Val: 200),
38 cl::Hidden, cl::desc("safety buffer size"));
39
40namespace llvm {
41
42 FunctionPass *createHexagonBranchRelaxation();
43 void initializeHexagonBranchRelaxationPass(PassRegistry&);
44
45} // end namespace llvm
46
47namespace {
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
85INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax",
86 "Hexagon Branch Relaxation", false, false)
87
88FunctionPass *llvm::createHexagonBranchRelaxation() {
89 return new HexagonBranchRelaxation();
90}
91
92bool 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
104void 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() != Align(1)) {
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 InstOffset = alignTo(Size: InstOffset, A: B.getAlignment());
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.
130bool 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, OffsetMap&: 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.
144bool 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(BB: &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(MBB&: B, TBB, FBB, Cond, AllowModify: 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(MI: *FirstTerm))
171 TBB = FirstTerm->getOperand(i: HII->getCExtOpNum(MI: *FirstTerm)).getMBB();
172 }
173 if (TBB && &MI == &*FirstTerm) {
174 Distance = std::abs(x: (long long)InstOffset - BlockToInstOffset[TBB])
175 + BranchRelaxSafetyBuffer;
176 return !HII->isJumpWithinBranchRange(MI: *FirstTerm, offset: Distance);
177 }
178 if (FBB) {
179 // Look for second terminator.
180 auto SecondTerm = std::next(x: 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(x: (long long)InstOffset - BlockToInstOffset[FBB])
188 + BranchRelaxSafetyBuffer;
189 return !HII->isJumpWithinBranchRange(MI: *SecondTerm, offset: Distance);
190 }
191 return false;
192}
193
194bool 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(i: 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(F: HexagonII::HMOTF_ConstExtended);
220 Changed = true;
221 }
222 }
223 }
224 return Changed;
225}
226