LLVM  8.0.0svn
HexagonBranchRelaxation.cpp
Go to the documentation of this file.
1 //===--- HexagonBranchRelaxation.cpp - Identify and relax long jumps ------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #define DEBUG_TYPE "hexagon-brelax"
11 
12 #include "Hexagon.h"
13 #include "HexagonInstrInfo.h"
14 #include "HexagonSubtarget.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/StringRef.h"
23 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/Pass.h"
26 #include "llvm/Support/Debug.h"
28 #include <cassert>
29 #include <cstdint>
30 #include <cstdlib>
31 #include <iterator>
32 
33 using namespace llvm;
34 
35 // Since we have no exact knowledge of code layout, allow some safety buffer
36 // for jump target. This is measured in bytes.
37 static cl::opt<uint32_t> BranchRelaxSafetyBuffer("branch-relax-safety-buffer",
38  cl::init(200), cl::Hidden, cl::ZeroOrMore, cl::desc("safety buffer size"));
39 
40 namespace llvm {
41 
44 
45 } // end namespace llvm
46 
47 namespace {
48 
49  struct HexagonBranchRelaxation : public MachineFunctionPass {
50  public:
51  static char ID;
52 
53  HexagonBranchRelaxation() : MachineFunctionPass(ID) {
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();
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 
82 
83 } // end anonymous namespace
84 
85 INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax",
86  "Hexagon Branch Relaxation", false, false)
87 
89  return new HexagonBranchRelaxation();
90 }
91 
92 bool 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 
104 void HexagonBranchRelaxation::computeOffset(MachineFunction &MF,
106  // offset of the current instruction from the start.
107  unsigned InstOffset = 0;
108  for (auto &B : MF) {
109  if (B.getAlignment()) {
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  int ByteAlign = (1u << B.getAlignment()) - 1;
114  InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
115  }
116  OffsetMap[&B] = InstOffset;
117  for (auto &MI : B.instrs()) {
118  InstOffset += HII->getSize(MI);
119  // Assume that all extendable branches will be extended.
120  if (MI.isBranch() && HII->isExtendable(MI))
121  InstOffset += HEXAGON_INSTR_SIZE;
122  }
123  }
124 }
125 
126 /// relaxBranches - For Hexagon, if the jump target/loop label is too far from
127 /// the jump/loop instruction then, we need to make sure that we have constant
128 /// extenders set for jumps and loops.
129 
130 /// There are six iterations in this phase. It's self explanatory below.
131 bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
132  // Compute the offset of each basic block
133  // offset of the current instruction from the start.
134  // map for each instruction to the beginning of the function
135  DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
136  computeOffset(MF, BlockToInstOffset);
137 
138  return reGenerateBranch(MF, BlockToInstOffset);
139 }
140 
141 /// Check if a given instruction is:
142 /// - a jump to a distant target
143 /// - that exceeds its immediate range
144 /// If both conditions are true, it requires constant extension.
145 bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
146  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
147  MachineBasicBlock &B = *MI.getParent();
148  auto FirstTerm = B.getFirstInstrTerminator();
149  if (FirstTerm == B.instr_end())
150  return false;
151 
152  if (HII->isExtended(MI))
153  return false;
154 
155  unsigned InstOffset = BlockToInstOffset[&B];
156  unsigned Distance = 0;
157 
158  // To save time, estimate exact position of a branch instruction
159  // as one at the end of the MBB.
160  // Number of instructions times typical instruction size.
161  InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
162 
163  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
165 
166  // Try to analyze this branch.
167  if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
168  // Could not analyze it. See if this is something we can recognize.
169  // If it is a NVJ, it should always have its target in
170  // a fixed location.
171  if (HII->isNewValueJump(*FirstTerm))
172  TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
173  }
174  if (TBB && &MI == &*FirstTerm) {
175  Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
177  return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
178  }
179  if (FBB) {
180  // Look for second terminator.
181  auto SecondTerm = std::next(FirstTerm);
182  assert(SecondTerm != B.instr_end() &&
183  (SecondTerm->isBranch() || SecondTerm->isCall()) &&
184  "Bad second terminator");
185  if (&MI != &*SecondTerm)
186  return false;
187  // Analyze the second branch in the BB.
188  Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
190  return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
191  }
192  return false;
193 }
194 
195 bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
196  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
197  bool Changed = false;
198 
199  for (auto &B : MF) {
200  for (auto &MI : B) {
201  if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
202  continue;
203  LLVM_DEBUG(dbgs() << "Long distance jump. isExtendable("
204  << HII->isExtendable(MI) << ") isConstExtended("
205  << HII->isConstExtended(MI) << ") " << MI);
206 
207  // Since we have not merged HW loops relaxation into
208  // this code (yet), soften our approach for the moment.
209  if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
210  LLVM_DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
211  } else {
212  // Find which operand is expandable.
213  int ExtOpNum = HII->getCExtOpNum(MI);
214  MachineOperand &MO = MI.getOperand(ExtOpNum);
215  // This need to be something we understand. So far we assume all
216  // branches have only MBB address as expandable field.
217  // If it changes, this will need to be expanded.
218  assert(MO.isMBB() && "Branch with unknown expandable field type");
219  // Mark given operand as extended.
221  Changed = true;
222  }
223  }
224  }
225  return Changed;
226 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_end()
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:657
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
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:285
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:847
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
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:1213
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:49
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414