LLVM  10.0.0svn
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 #define DEBUG_TYPE "hexagon-brelax"
10 
11 #include "Hexagon.h"
12 #include "HexagonInstrInfo.h"
13 #include "HexagonSubtarget.h"
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/StringRef.h"
22 #include "llvm/CodeGen/Passes.h"
23 #include "llvm/Pass.h"
25 #include "llvm/Support/Debug.h"
27 #include <cassert>
28 #include <cstdint>
29 #include <cstdlib>
30 #include <iterator>
31 
32 using 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.
36 static cl::opt<uint32_t> BranchRelaxSafetyBuffer("branch-relax-safety-buffer",
37  cl::init(200), cl::Hidden, cl::ZeroOrMore, cl::desc("safety buffer size"));
38 
39 namespace llvm {
40 
43 
44 } // end namespace llvm
45 
46 namespace {
47 
48  struct HexagonBranchRelaxation : public MachineFunctionPass {
49  public:
50  static char ID;
51 
52  HexagonBranchRelaxation() : MachineFunctionPass(ID) {
54  }
55 
56  bool runOnMachineFunction(MachineFunction &MF) override;
57 
58  StringRef getPassName() const override {
59  return "Hexagon Branch Relaxation";
60  }
61 
62  void getAnalysisUsage(AnalysisUsage &AU) const override {
63  AU.setPreservesCFG();
65  }
66 
67  private:
68  const HexagonInstrInfo *HII;
69  const HexagonRegisterInfo *HRI;
70 
71  bool relaxBranches(MachineFunction &MF);
72  void computeOffset(MachineFunction &MF,
73  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
74  bool reGenerateBranch(MachineFunction &MF,
75  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
76  bool isJumpOutOfRange(MachineInstr &MI,
77  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
78  };
79 
81 
82 } // end anonymous namespace
83 
84 INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax",
85  "Hexagon Branch Relaxation", false, false)
86 
88  return new HexagonBranchRelaxation();
89 }
90 
91 bool HexagonBranchRelaxation::runOnMachineFunction(MachineFunction &MF) {
92  LLVM_DEBUG(dbgs() << "****** Hexagon Branch Relaxation ******\n");
93 
94  auto &HST = MF.getSubtarget<HexagonSubtarget>();
95  HII = HST.getInstrInfo();
96  HRI = HST.getRegisterInfo();
97 
98  bool Changed = false;
99  Changed = relaxBranches(MF);
100  return Changed;
101 }
102 
103 void HexagonBranchRelaxation::computeOffset(MachineFunction &MF,
105  // offset of the current instruction from the start.
106  unsigned InstOffset = 0;
107  for (auto &B : MF) {
108  if (B.getAlignment()) {
109  // Although we don't know the exact layout of the final code, we need
110  // to account for alignment padding somehow. This heuristic pads each
111  // aligned basic block according to the alignment value.
112  int ByteAlign = (1u << B.getAlignment()) - 1;
113  InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
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.
130 bool 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, 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.
144 bool 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(&B) * HEXAGON_INSTR_SIZE;
161 
162  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
164 
165  // Try to analyze this branch.
166  if (HII->analyzeBranch(B, TBB, FBB, Cond, 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(*FirstTerm))
171  TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
172  }
173  if (TBB && &MI == &*FirstTerm) {
174  Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
176  return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
177  }
178  if (FBB) {
179  // Look for second terminator.
180  auto SecondTerm = std::next(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((long long)InstOffset - BlockToInstOffset[FBB])
189  return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
190  }
191  return false;
192 }
193 
194 bool 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(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.
220  Changed = true;
221  }
222  }
223  }
224  return Changed;
225 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_end()
This class represents lattice values for constants.
Definition: AllocatorList.h:23
instr_iterator getFirstInstrTerminator()
Same getFirstTerminator but it ignores bundles and return an instr_iterator instead.
#define HEXAGON_INSTR_SIZE
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:659
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void initializeHexagonBranchRelaxationPass(PassRegistry &)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Represent the analysis usage information of a pass.
static cl::opt< uint32_t > BranchRelaxSafetyBuffer("branch-relax-safety-buffer", cl::init(200), cl::Hidden, cl::ZeroOrMore, cl::desc("safety buffer size"))
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax", "Hexagon Branch Relaxation", false, false) FunctionPass *llvm
FunctionPass * createHexagonBranchRelaxation()
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
Representation of each machine instruction.
Definition: MachineInstr.h:64
void addTargetFlag(unsigned F)
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1223
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const HexagonInstrInfo * getInstrInfo() const override
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416