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() != Align::None()) {
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  InstOffset = alignTo(InstOffset, B.getAlignment());
113  }
114  OffsetMap[&B] = InstOffset;
115  for (auto &MI : B.instrs()) {
116  InstOffset += HII->getSize(MI);
117  // Assume that all extendable branches will be extended.
118  if (MI.isBranch() && HII->isExtendable(MI))
119  InstOffset += HEXAGON_INSTR_SIZE;
120  }
121  }
122 }
123 
124 /// relaxBranches - For Hexagon, if the jump target/loop label is too far from
125 /// the jump/loop instruction then, we need to make sure that we have constant
126 /// extenders set for jumps and loops.
127 
128 /// There are six iterations in this phase. It's self explanatory below.
129 bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
130  // Compute the offset of each basic block
131  // offset of the current instruction from the start.
132  // map for each instruction to the beginning of the function
133  DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
134  computeOffset(MF, BlockToInstOffset);
135 
136  return reGenerateBranch(MF, BlockToInstOffset);
137 }
138 
139 /// Check if a given instruction is:
140 /// - a jump to a distant target
141 /// - that exceeds its immediate range
142 /// If both conditions are true, it requires constant extension.
143 bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
144  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
145  MachineBasicBlock &B = *MI.getParent();
146  auto FirstTerm = B.getFirstInstrTerminator();
147  if (FirstTerm == B.instr_end())
148  return false;
149 
150  if (HII->isExtended(MI))
151  return false;
152 
153  unsigned InstOffset = BlockToInstOffset[&B];
154  unsigned Distance = 0;
155 
156  // To save time, estimate exact position of a branch instruction
157  // as one at the end of the MBB.
158  // Number of instructions times typical instruction size.
159  InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
160 
161  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
163 
164  // Try to analyze this branch.
165  if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
166  // Could not analyze it. See if this is something we can recognize.
167  // If it is a NVJ, it should always have its target in
168  // a fixed location.
169  if (HII->isNewValueJump(*FirstTerm))
170  TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
171  }
172  if (TBB && &MI == &*FirstTerm) {
173  Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
175  return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
176  }
177  if (FBB) {
178  // Look for second terminator.
179  auto SecondTerm = std::next(FirstTerm);
180  assert(SecondTerm != B.instr_end() &&
181  (SecondTerm->isBranch() || SecondTerm->isCall()) &&
182  "Bad second terminator");
183  if (&MI != &*SecondTerm)
184  return false;
185  // Analyze the second branch in the BB.
186  Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
188  return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
189  }
190  return false;
191 }
192 
193 bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
194  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
195  bool Changed = false;
196 
197  for (auto &B : MF) {
198  for (auto &MI : B) {
199  if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
200  continue;
201  LLVM_DEBUG(dbgs() << "Long distance jump. isExtendable("
202  << HII->isExtendable(MI) << ") isConstExtended("
203  << HII->isConstExtended(MI) << ") " << MI);
204 
205  // Since we have not merged HW loops relaxation into
206  // this code (yet), soften our approach for the moment.
207  if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
208  LLVM_DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
209  } else {
210  // Find which operand is expandable.
211  int ExtOpNum = HII->getCExtOpNum(MI);
212  MachineOperand &MO = MI.getOperand(ExtOpNum);
213  // This need to be something we understand. So far we assume all
214  // branches have only MBB address as expandable field.
215  // If it changes, this will need to be expanded.
216  assert(MO.isMBB() && "Branch with unknown expandable field type");
217  // Mark given operand as extended.
219  Changed = true;
220  }
221  }
222  }
223  return Changed;
224 }
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:680
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
static constexpr const Align None()
Returns a default constructed Align which corresponds to no alignment.
Definition: Alignment.h:93
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:255
Representation of each machine instruction.
Definition: MachineInstr.h:63
void addTargetFlag(unsigned F)
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:163
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1228
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:415