LLVM 24.0.0git
HexagonBranchRelaxation.cpp
Go to the documentation of this file.
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"
14#include "llvm/ADT/StringRef.h"
20#include "llvm/CodeGen/Passes.h"
21#include "llvm/Pass.h"
23#include "llvm/Support/Debug.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.
37 BranchRelaxSafetyBuffer("branch-relax-safety-buffer", cl::init(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();
57 }
58
59 private:
60 const HexagonInstrInfo *HII;
61
62 bool relaxBranches(MachineFunction &MF);
63 void computeOffset(MachineFunction &MF,
64 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
65 bool reGenerateBranch(MachineFunction &MF,
66 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
67 bool isJumpOutOfRange(MachineInstr &MI,
68 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
69 };
70
71 char HexagonBranchRelaxation::ID = 0;
72
73} // end anonymous namespace
74
75INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax",
76 "Hexagon Branch Relaxation", false, false)
77
79 return new HexagonBranchRelaxation();
80}
81
82bool HexagonBranchRelaxation::runOnMachineFunction(MachineFunction &MF) {
83 LLVM_DEBUG(dbgs() << "****** Hexagon Branch Relaxation ******\n");
84
85 auto &HST = MF.getSubtarget<HexagonSubtarget>();
86 HII = HST.getInstrInfo();
87
88 bool Changed = false;
89 Changed = relaxBranches(MF);
90 return Changed;
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() != Align(1)) {
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 InstOffset = alignTo(InstOffset, B.getAlignment());
103 }
104 OffsetMap[&B] = InstOffset;
105 for (auto &MI : B.instrs()) {
106 InstOffset += HII->getSize(MI);
107 // Assume that all extendable branches will be extended.
108 if (MI.isBranch() && HII->isExtendable(MI))
109 InstOffset += HEXAGON_INSTR_SIZE;
110 }
111 }
112}
113
114/// relaxBranches - For Hexagon, if the jump target/loop label is too far from
115/// the jump/loop instruction then, we need to make sure that we have constant
116/// extenders set for jumps and loops.
117
118/// There are six iterations in this phase. It's self explanatory below.
119bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
120 // Compute the offset of each basic block
121 // offset of the current instruction from the start.
122 // map for each instruction to the beginning of the function
123 DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
124 computeOffset(MF, BlockToInstOffset);
125
126 return reGenerateBranch(MF, BlockToInstOffset);
127}
128
129/// Check if a given instruction is:
130/// - a jump to a distant target
131/// - that exceeds its immediate range
132/// If both conditions are true, it requires constant extension.
133bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
134 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
135 MachineBasicBlock &B = *MI.getParent();
136 auto FirstTerm = B.getFirstInstrTerminator();
137 if (FirstTerm == B.instr_end())
138 return false;
139
140 if (HII->isExtended(MI))
141 return false;
142
143 unsigned InstOffset = BlockToInstOffset[&B];
144 unsigned Distance = 0;
145
146 // To save time, estimate exact position of a branch instruction
147 // as one at the end of the MBB.
148 // Number of instructions times typical instruction size.
149 InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
150
151 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
152 SmallVector<MachineOperand, 4> Cond;
153
154 // Try to analyze this branch.
155 if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
156 // Could not analyze it. See if this is something we can recognize.
157 // If it is a NVJ, it should always have its target in
158 // a fixed location.
159 if (HII->isNewValueJump(*FirstTerm))
160 TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
161 }
162 if (TBB && &MI == &*FirstTerm) {
163 Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
165 return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
166 }
167 if (FBB) {
168 // Look for second terminator.
169 auto SecondTerm = std::next(FirstTerm);
170 assert(SecondTerm != B.instr_end() &&
171 (SecondTerm->isBranch() || SecondTerm->isCall()) &&
172 "Bad second terminator");
173 if (&MI != &*SecondTerm)
174 return false;
175 // Analyze the second branch in the BB.
176 Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
178 return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
179 }
180 return false;
181}
182
183bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
184 DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
185 bool Changed = false;
186
187 for (auto &B : MF) {
188 for (auto &MI : B) {
189 if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
190 continue;
191 LLVM_DEBUG(dbgs() << "Long distance jump. isExtendable("
192 << HII->isExtendable(MI) << ") isConstExtended("
193 << HII->isConstExtended(MI) << ") " << MI);
194
195 // Since we have not merged HW loops relaxation into
196 // this code (yet), soften our approach for the moment.
197 if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
198 LLVM_DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
199 } else {
200 // Find which operand is expandable.
201 int ExtOpNum = HII->getCExtOpNum(MI);
202 MachineOperand &MO = MI.getOperand(ExtOpNum);
203 // This need to be something we understand. So far we assume all
204 // branches have only MBB address as expandable field.
205 // If it changes, this will need to be expanded.
206 assert(MO.isMBB() && "Branch with unknown expandable field type");
207 // Mark given operand as extended.
209 Changed = true;
210 }
211 }
212 }
213 return Changed;
214}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseMap class.
static cl::opt< uint32_t > BranchRelaxSafetyBuffer("branch-relax-safety-buffer", cl::init(200), cl::Hidden, cl::desc("safety buffer size"))
#define HEXAGON_INSTR_SIZE
IRTranslator LLVM IR MI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition PassSupport.h:56
SmallVector< MachineOperand, 4 > Cond
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
This file defines the SmallVector class.
#define LLVM_DEBUG(...)
Definition Debug.h:119
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition Pass.cpp:280
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void addTargetFlag(unsigned F)
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
FunctionPass * createHexagonBranchRelaxation()
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
constexpr uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition Alignment.h:149