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 {
41
42 struct HexagonBranchRelaxation : public MachineFunctionPass {
43 public:
44 static char ID;
45
46 HexagonBranchRelaxation() : MachineFunctionPass(ID) {}
47
48 bool runOnMachineFunction(MachineFunction &MF) override;
49
50 StringRef getPassName() const override {
51 return "Hexagon Branch Relaxation";
52 }
53
54 void getAnalysisUsage(AnalysisUsage &AU) const override {
55 AU.setPreservesCFG();
56 MachineFunctionPass::getAnalysisUsage(AU);
57 }
58
59 private:
60 const HexagonInstrInfo *HII;
61 const HexagonRegisterInfo *HRI;
62
63 bool relaxBranches(MachineFunction &MF);
64 void computeOffset(MachineFunction &MF,
65 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
66 bool reGenerateBranch(MachineFunction &MF,
67 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
68 bool isJumpOutOfRange(MachineInstr &MI,
69 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
70 };
71
72 char HexagonBranchRelaxation::ID = 0;
73
74} // end anonymous namespace
75
76INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax",
77 "Hexagon Branch Relaxation", false, false)
78
79FunctionPass *llvm::createHexagonBranchRelaxation() {
80 return new HexagonBranchRelaxation();
81}
82
83bool HexagonBranchRelaxation::runOnMachineFunction(MachineFunction &MF) {
84 LLVM_DEBUG(dbgs() << "****** Hexagon Branch Relaxation ******\n");
85
86 auto &HST = MF.getSubtarget<HexagonSubtarget>();
87 HII = HST.getInstrInfo();
88 HRI = HST.getRegisterInfo();
89
90 bool Changed = false;
91 Changed = relaxBranches(MF);
92 return Changed;
93}
94
95void HexagonBranchRelaxation::computeOffset(MachineFunction &MF,
96 DenseMap<MachineBasicBlock*, unsigned> &OffsetMap) {
97 // offset of the current instruction from the start.
98 unsigned InstOffset = 0;
99 for (auto &B : MF) {
100 if (B.getAlignment() != Align(1)) {
101 // Although we don't know the exact layout of the final code, we need
102 // to account for alignment padding somehow. This heuristic pads each
103 // aligned basic block according to the alignment value.
104 InstOffset = alignTo(Size: InstOffset, A: B.getAlignment());
105 }
106 OffsetMap[&B] = InstOffset;
107 for (auto &MI : B.instrs()) {
108 InstOffset += HII->getSize(MI);
109 // Assume that all extendable branches will be extended.
110 if (MI.isBranch() && HII->isExtendable(MI))
111 InstOffset += HEXAGON_INSTR_SIZE;
112 }
113 }
114}
115
116/// relaxBranches - For Hexagon, if the jump target/loop label is too far from
117/// the jump/loop instruction then, we need to make sure that we have constant
118/// extenders set for jumps and loops.
119
120/// There are six iterations in this phase. It's self explanatory below.
121bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
122 // Compute the offset of each basic block
123 // offset of the current instruction from the start.
124 // map for each instruction to the beginning of the function
125 DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
126 computeOffset(MF, OffsetMap&: BlockToInstOffset);
127
128 return reGenerateBranch(MF, BlockToInstOffset);
129}
130
131/// Check if a given instruction is:
132/// - a jump to a distant target
133/// - that exceeds its immediate range
134/// If both conditions are true, it requires constant extension.
135bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
136 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
137 MachineBasicBlock &B = *MI.getParent();
138 auto FirstTerm = B.getFirstInstrTerminator();
139 if (FirstTerm == B.instr_end())
140 return false;
141
142 if (HII->isExtended(MI))
143 return false;
144
145 unsigned InstOffset = BlockToInstOffset[&B];
146 unsigned Distance = 0;
147
148 // To save time, estimate exact position of a branch instruction
149 // as one at the end of the MBB.
150 // Number of instructions times typical instruction size.
151 InstOffset += HII->nonDbgBBSize(BB: &B) * HEXAGON_INSTR_SIZE;
152
153 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
154 SmallVector<MachineOperand, 4> Cond;
155
156 // Try to analyze this branch.
157 if (HII->analyzeBranch(MBB&: B, TBB, FBB, Cond, AllowModify: false)) {
158 // Could not analyze it. See if this is something we can recognize.
159 // If it is a NVJ, it should always have its target in
160 // a fixed location.
161 if (HII->isNewValueJump(MI: *FirstTerm))
162 TBB = FirstTerm->getOperand(i: HII->getCExtOpNum(MI: *FirstTerm)).getMBB();
163 }
164 if (TBB && &MI == &*FirstTerm) {
165 Distance = std::abs(x: (long long)InstOffset - BlockToInstOffset[TBB])
166 + BranchRelaxSafetyBuffer;
167 return !HII->isJumpWithinBranchRange(MI: *FirstTerm, offset: Distance);
168 }
169 if (FBB) {
170 // Look for second terminator.
171 auto SecondTerm = std::next(x: FirstTerm);
172 assert(SecondTerm != B.instr_end() &&
173 (SecondTerm->isBranch() || SecondTerm->isCall()) &&
174 "Bad second terminator");
175 if (&MI != &*SecondTerm)
176 return false;
177 // Analyze the second branch in the BB.
178 Distance = std::abs(x: (long long)InstOffset - BlockToInstOffset[FBB])
179 + BranchRelaxSafetyBuffer;
180 return !HII->isJumpWithinBranchRange(MI: *SecondTerm, offset: Distance);
181 }
182 return false;
183}
184
185bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
186 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
187 bool Changed = false;
188
189 for (auto &B : MF) {
190 for (auto &MI : B) {
191 if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
192 continue;
193 LLVM_DEBUG(dbgs() << "Long distance jump. isExtendable("
194 << HII->isExtendable(MI) << ") isConstExtended("
195 << HII->isConstExtended(MI) << ") " << MI);
196
197 // Since we have not merged HW loops relaxation into
198 // this code (yet), soften our approach for the moment.
199 if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
200 LLVM_DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
201 } else {
202 // Find which operand is expandable.
203 int ExtOpNum = HII->getCExtOpNum(MI);
204 MachineOperand &MO = MI.getOperand(i: ExtOpNum);
205 // This need to be something we understand. So far we assume all
206 // branches have only MBB address as expandable field.
207 // If it changes, this will need to be expanded.
208 assert(MO.isMBB() && "Branch with unknown expandable field type");
209 // Mark given operand as extended.
210 MO.addTargetFlag(F: HexagonII::HMOTF_ConstExtended);
211 Changed = true;
212 }
213 }
214 }
215 return Changed;
216}
217