LLVM  6.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  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  }
120 }
121 
122 /// relaxBranches - For Hexagon, if the jump target/loop label is too far from
123 /// the jump/loop instruction then, we need to make sure that we have constant
124 /// extenders set for jumps and loops.
125 
126 /// There are six iterations in this phase. It's self explanatory below.
127 bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
128  // Compute the offset of each basic block
129  // offset of the current instruction from the start.
130  // map for each instruction to the beginning of the function
131  DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
132  computeOffset(MF, BlockToInstOffset);
133 
134  return reGenerateBranch(MF, BlockToInstOffset);
135 }
136 
137 /// Check if a given instruction is:
138 /// - a jump to a distant target
139 /// - that exceeds its immediate range
140 /// If both conditions are true, it requires constant extension.
141 bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
142  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
143  MachineBasicBlock &B = *MI.getParent();
144  auto FirstTerm = B.getFirstInstrTerminator();
145  if (FirstTerm == B.instr_end())
146  return false;
147 
148  unsigned InstOffset = BlockToInstOffset[&B];
149  unsigned Distance = 0;
150 
151  // To save time, estimate exact position of a branch instruction
152  // as one at the end of the MBB.
153  // Number of instructions times typical instruction size.
154  InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
155 
156  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
158 
159  // Try to analyze this branch.
160  if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
161  // Could not analyze it. See if this is something we can recognize.
162  // If it is a NVJ, it should always have its target in
163  // a fixed location.
164  if (HII->isNewValueJump(*FirstTerm))
165  TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
166  }
167  if (TBB && &MI == &*FirstTerm) {
168  Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
170  return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
171  }
172  if (FBB) {
173  // Look for second terminator.
174  auto SecondTerm = std::next(FirstTerm);
175  assert(SecondTerm != B.instr_end() &&
176  (SecondTerm->isBranch() || SecondTerm->isCall()) &&
177  "Bad second terminator");
178  if (&MI != &*SecondTerm)
179  return false;
180  // Analyze the second branch in the BB.
181  Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
183  return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
184  }
185  return false;
186 }
187 
188 bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
189  DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
190  bool Changed = false;
191 
192  for (auto &B : MF) {
193  for (auto &MI : B) {
194  if (!MI.isBranch() || !isJumpOutOfRange(MI, BlockToInstOffset))
195  continue;
196  DEBUG(dbgs() << "Long distance jump. isExtendable("
197  << HII->isExtendable(MI) << ") isConstExtended("
198  << HII->isConstExtended(MI) << ") " << MI);
199 
200  // Since we have not merged HW loops relaxation into
201  // this code (yet), soften our approach for the moment.
202  if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
203  DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
204  } else {
205  // Find which operand is expandable.
206  int ExtOpNum = HII->getCExtOpNum(MI);
207  MachineOperand &MO = MI.getOperand(ExtOpNum);
208  // This need to be something we understand. So far we assume all
209  // branches have only MBB address as expandable field.
210  // If it changes, this will need to be expanded.
211  assert(MO.isMBB() && "Branch with unknown expandable field type");
212  // Mark given operand as extended.
214  Changed = true;
215  }
216  }
217  }
218  return Changed;
219 }
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.
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:482
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
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:864
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
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:139
Representation of each machine instruction.
Definition: MachineInstr.h:59
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())
#define HEXAGON_INSTR_SIZE
Definition: Hexagon.h:30
const HexagonInstrInfo * getInstrInfo() const override
#define DEBUG(X)
Definition: Debug.h:118
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.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295