LLVM  8.0.1
HexagonCFGOptimizer.cpp
Go to the documentation of this file.
1 //===- HexagonCFGOptimizer.cpp - CFG optimizations ------------------------===//
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 #include "Hexagon.h"
19 #include "llvm/Pass.h"
21 #include <cassert>
22 #include <vector>
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "hexagon_cfg"
27 
28 namespace llvm {
29 
32 
33 } // end namespace llvm
34 
35 namespace {
36 
37 class HexagonCFGOptimizer : public MachineFunctionPass {
38 private:
39  void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);
40  bool isOnFallThroughPath(MachineBasicBlock *MBB);
41 
42 public:
43  static char ID;
44 
45  HexagonCFGOptimizer() : MachineFunctionPass(ID) {
47  }
48 
49  StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }
50  bool runOnMachineFunction(MachineFunction &Fn) override;
51 
52  MachineFunctionProperties getRequiredProperties() const override {
55  }
56 };
57 
58 } // end anonymous namespace
59 
61 
62 static bool IsConditionalBranch(int Opc) {
63  switch (Opc) {
64  case Hexagon::J2_jumpt:
65  case Hexagon::J2_jumptpt:
66  case Hexagon::J2_jumpf:
67  case Hexagon::J2_jumpfpt:
68  case Hexagon::J2_jumptnew:
69  case Hexagon::J2_jumpfnew:
70  case Hexagon::J2_jumptnewpt:
71  case Hexagon::J2_jumpfnewpt:
72  return true;
73  }
74  return false;
75 }
76 
77 static bool IsUnconditionalJump(int Opc) {
78  return (Opc == Hexagon::J2_jump);
79 }
80 
81 void HexagonCFGOptimizer::InvertAndChangeJumpTarget(
82  MachineInstr &MI, MachineBasicBlock *NewTarget) {
83  const TargetInstrInfo *TII =
85  int NewOpcode = 0;
86  switch (MI.getOpcode()) {
87  case Hexagon::J2_jumpt:
88  NewOpcode = Hexagon::J2_jumpf;
89  break;
90  case Hexagon::J2_jumpf:
91  NewOpcode = Hexagon::J2_jumpt;
92  break;
93  case Hexagon::J2_jumptnewpt:
94  NewOpcode = Hexagon::J2_jumpfnewpt;
95  break;
96  case Hexagon::J2_jumpfnewpt:
97  NewOpcode = Hexagon::J2_jumptnewpt;
98  break;
99  default:
100  llvm_unreachable("Cannot handle this case");
101  }
102 
103  MI.setDesc(TII->get(NewOpcode));
104  MI.getOperand(1).setMBB(NewTarget);
105 }
106 
107 bool HexagonCFGOptimizer::isOnFallThroughPath(MachineBasicBlock *MBB) {
108  if (MBB->canFallThrough())
109  return true;
110  for (MachineBasicBlock *PB : MBB->predecessors())
111  if (PB->isLayoutSuccessor(MBB) && PB->canFallThrough())
112  return true;
113  return false;
114 }
115 
116 bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
117  if (skipFunction(Fn.getFunction()))
118  return false;
119 
120  // Loop over all of the basic blocks.
121  for (MachineFunction::iterator MBBb = Fn.begin(), MBBe = Fn.end();
122  MBBb != MBBe; ++MBBb) {
123  MachineBasicBlock *MBB = &*MBBb;
124 
125  // Traverse the basic block.
127  if (MII != MBB->end()) {
128  MachineInstr &MI = *MII;
129  int Opc = MI.getOpcode();
130  if (IsConditionalBranch(Opc)) {
131  // (Case 1) Transform the code if the following condition occurs:
132  // BB1: if (p0) jump BB3
133  // ...falls-through to BB2 ...
134  // BB2: jump BB4
135  // ...next block in layout is BB3...
136  // BB3: ...
137  //
138  // Transform this to:
139  // BB1: if (!p0) jump BB4
140  // Remove BB2
141  // BB3: ...
142  //
143  // (Case 2) A variation occurs when BB3 contains a JMP to BB4:
144  // BB1: if (p0) jump BB3
145  // ...falls-through to BB2 ...
146  // BB2: jump BB4
147  // ...other basic blocks ...
148  // BB4:
149  // ...not a fall-thru
150  // BB3: ...
151  // jump BB4
152  //
153  // Transform this to:
154  // BB1: if (!p0) jump BB4
155  // Remove BB2
156  // BB3: ...
157  // BB4: ...
158  unsigned NumSuccs = MBB->succ_size();
160  MachineBasicBlock* FirstSucc = *SI;
161  MachineBasicBlock* SecondSucc = *(++SI);
162  MachineBasicBlock* LayoutSucc = nullptr;
163  MachineBasicBlock* JumpAroundTarget = nullptr;
164 
165  if (MBB->isLayoutSuccessor(FirstSucc)) {
166  LayoutSucc = FirstSucc;
167  JumpAroundTarget = SecondSucc;
168  } else if (MBB->isLayoutSuccessor(SecondSucc)) {
169  LayoutSucc = SecondSucc;
170  JumpAroundTarget = FirstSucc;
171  } else {
172  // Odd case...cannot handle.
173  }
174 
175  // The target of the unconditional branch must be JumpAroundTarget.
176  // TODO: If not, we should not invert the unconditional branch.
177  MachineBasicBlock* CondBranchTarget = nullptr;
178  if (MI.getOpcode() == Hexagon::J2_jumpt ||
179  MI.getOpcode() == Hexagon::J2_jumpf) {
180  CondBranchTarget = MI.getOperand(1).getMBB();
181  }
182 
183  if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) {
184  continue;
185  }
186 
187  if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) {
188  // Ensure that BB2 has one instruction -- an unconditional jump.
189  if ((LayoutSucc->size() == 1) &&
190  IsUnconditionalJump(LayoutSucc->front().getOpcode())) {
191  assert(JumpAroundTarget && "jump target is needed to process second basic block");
192  MachineBasicBlock* UncondTarget =
193  LayoutSucc->front().getOperand(0).getMBB();
194  // Check if the layout successor of BB2 is BB3.
195  bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget);
196  bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) &&
197  !JumpAroundTarget->empty() &&
198  IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) &&
199  JumpAroundTarget->pred_size() == 1 &&
200  JumpAroundTarget->succ_size() == 1;
201 
202  if (case1 || case2) {
203  InvertAndChangeJumpTarget(MI, UncondTarget);
204  MBB->replaceSuccessor(JumpAroundTarget, UncondTarget);
205 
206  // Remove the unconditional branch in LayoutSucc.
207  LayoutSucc->erase(LayoutSucc->begin());
208  LayoutSucc->replaceSuccessor(UncondTarget, JumpAroundTarget);
209 
210  // This code performs the conversion for case 2, which moves
211  // the block to the fall-thru case (BB3 in the code above).
212  if (case2 && !case1) {
213  JumpAroundTarget->moveAfter(LayoutSucc);
214  // only move a block if it doesn't have a fall-thru. otherwise
215  // the CFG will be incorrect.
216  if (!isOnFallThroughPath(UncondTarget))
217  UncondTarget->moveAfter(JumpAroundTarget);
218  }
219 
220  // Correct live-in information. Is used by post-RA scheduler
221  // The live-in to LayoutSucc is now all values live-in to
222  // JumpAroundTarget.
223  std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(
224  LayoutSucc->livein_begin(), LayoutSucc->livein_end());
225  std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(
226  JumpAroundTarget->livein_begin(),
227  JumpAroundTarget->livein_end());
228  for (const auto &OrigLI : OrigLiveIn)
229  LayoutSucc->removeLiveIn(OrigLI.PhysReg);
230  for (const auto &NewLI : NewLiveIn)
231  LayoutSucc->addLiveIn(NewLI);
232  }
233  }
234  }
235  }
236  }
237  }
238  return true;
239 }
240 
241 //===----------------------------------------------------------------------===//
242 // Public Constructor Functions
243 //===----------------------------------------------------------------------===//
244 
245 INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",
246  false, false)
247 
249  return new HexagonCFGOptimizer();
250 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:24
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
static bool IsUnconditionalJump(int Opc)
void moveAfter(MachineBasicBlock *NewBefore)
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
static bool IsConditionalBranch(int Opc)
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
virtual const TargetInstrInfo * getInstrInfo() const
TargetInstrInfo - Interface to description of machine instruction set.
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
livein_iterator livein_end() const
void setMBB(MachineBasicBlock *MBB)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
iterator_range< pred_iterator > predecessors()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
unsigned pred_size() const
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
unsigned succ_size() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer", false, false) FunctionPass *llvm
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeHexagonCFGOptimizerPass(PassRegistry &)
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
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
std::vector< MachineBasicBlock * >::iterator succ_iterator
livein_iterator livein_begin() const
Properties which a MachineFunction may have at a given point in time.
FunctionPass * createHexagonCFGOptimizer()