LLVM  9.0.0svn
HexagonCFGOptimizer.cpp
Go to the documentation of this file.
1 //===- HexagonCFGOptimizer.cpp - CFG optimizations ------------------------===//
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 #include "Hexagon.h"
18 #include "llvm/Pass.h"
20 #include <cassert>
21 #include <vector>
22 
23 using namespace llvm;
24 
25 #define DEBUG_TYPE "hexagon_cfg"
26 
27 namespace llvm {
28 
31 
32 } // end namespace llvm
33 
34 namespace {
35 
36 class HexagonCFGOptimizer : public MachineFunctionPass {
37 private:
38  void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);
39  bool isOnFallThroughPath(MachineBasicBlock *MBB);
40 
41 public:
42  static char ID;
43 
44  HexagonCFGOptimizer() : MachineFunctionPass(ID) {
46  }
47 
48  StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }
49  bool runOnMachineFunction(MachineFunction &Fn) override;
50 
51  MachineFunctionProperties getRequiredProperties() const override {
54  }
55 };
56 
57 } // end anonymous namespace
58 
60 
61 static bool IsConditionalBranch(int Opc) {
62  switch (Opc) {
63  case Hexagon::J2_jumpt:
64  case Hexagon::J2_jumptpt:
65  case Hexagon::J2_jumpf:
66  case Hexagon::J2_jumpfpt:
67  case Hexagon::J2_jumptnew:
68  case Hexagon::J2_jumpfnew:
69  case Hexagon::J2_jumptnewpt:
70  case Hexagon::J2_jumpfnewpt:
71  return true;
72  }
73  return false;
74 }
75 
76 static bool IsUnconditionalJump(int Opc) {
77  return (Opc == Hexagon::J2_jump);
78 }
79 
80 void HexagonCFGOptimizer::InvertAndChangeJumpTarget(
81  MachineInstr &MI, MachineBasicBlock *NewTarget) {
82  const TargetInstrInfo *TII =
84  int NewOpcode = 0;
85  switch (MI.getOpcode()) {
86  case Hexagon::J2_jumpt:
87  NewOpcode = Hexagon::J2_jumpf;
88  break;
89  case Hexagon::J2_jumpf:
90  NewOpcode = Hexagon::J2_jumpt;
91  break;
92  case Hexagon::J2_jumptnewpt:
93  NewOpcode = Hexagon::J2_jumpfnewpt;
94  break;
95  case Hexagon::J2_jumpfnewpt:
96  NewOpcode = Hexagon::J2_jumptnewpt;
97  break;
98  default:
99  llvm_unreachable("Cannot handle this case");
100  }
101 
102  MI.setDesc(TII->get(NewOpcode));
103  MI.getOperand(1).setMBB(NewTarget);
104 }
105 
106 bool HexagonCFGOptimizer::isOnFallThroughPath(MachineBasicBlock *MBB) {
107  if (MBB->canFallThrough())
108  return true;
109  for (MachineBasicBlock *PB : MBB->predecessors())
110  if (PB->isLayoutSuccessor(MBB) && PB->canFallThrough())
111  return true;
112  return false;
113 }
114 
115 bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
116  if (skipFunction(Fn.getFunction()))
117  return false;
118 
119  // Loop over all of the basic blocks.
120  for (MachineFunction::iterator MBBb = Fn.begin(), MBBe = Fn.end();
121  MBBb != MBBe; ++MBBb) {
122  MachineBasicBlock *MBB = &*MBBb;
123 
124  // Traverse the basic block.
126  if (MII != MBB->end()) {
127  MachineInstr &MI = *MII;
128  int Opc = MI.getOpcode();
129  if (IsConditionalBranch(Opc)) {
130  // (Case 1) Transform the code if the following condition occurs:
131  // BB1: if (p0) jump BB3
132  // ...falls-through to BB2 ...
133  // BB2: jump BB4
134  // ...next block in layout is BB3...
135  // BB3: ...
136  //
137  // Transform this to:
138  // BB1: if (!p0) jump BB4
139  // Remove BB2
140  // BB3: ...
141  //
142  // (Case 2) A variation occurs when BB3 contains a JMP to BB4:
143  // BB1: if (p0) jump BB3
144  // ...falls-through to BB2 ...
145  // BB2: jump BB4
146  // ...other basic blocks ...
147  // BB4:
148  // ...not a fall-thru
149  // BB3: ...
150  // jump BB4
151  //
152  // Transform this to:
153  // BB1: if (!p0) jump BB4
154  // Remove BB2
155  // BB3: ...
156  // BB4: ...
157  unsigned NumSuccs = MBB->succ_size();
159  MachineBasicBlock* FirstSucc = *SI;
160  MachineBasicBlock* SecondSucc = *(++SI);
161  MachineBasicBlock* LayoutSucc = nullptr;
162  MachineBasicBlock* JumpAroundTarget = nullptr;
163 
164  if (MBB->isLayoutSuccessor(FirstSucc)) {
165  LayoutSucc = FirstSucc;
166  JumpAroundTarget = SecondSucc;
167  } else if (MBB->isLayoutSuccessor(SecondSucc)) {
168  LayoutSucc = SecondSucc;
169  JumpAroundTarget = FirstSucc;
170  } else {
171  // Odd case...cannot handle.
172  }
173 
174  // The target of the unconditional branch must be JumpAroundTarget.
175  // TODO: If not, we should not invert the unconditional branch.
176  MachineBasicBlock* CondBranchTarget = nullptr;
177  if (MI.getOpcode() == Hexagon::J2_jumpt ||
178  MI.getOpcode() == Hexagon::J2_jumpf) {
179  CondBranchTarget = MI.getOperand(1).getMBB();
180  }
181 
182  if (!LayoutSucc || (CondBranchTarget != JumpAroundTarget)) {
183  continue;
184  }
185 
186  if ((NumSuccs == 2) && LayoutSucc && (LayoutSucc->pred_size() == 1)) {
187  // Ensure that BB2 has one instruction -- an unconditional jump.
188  if ((LayoutSucc->size() == 1) &&
189  IsUnconditionalJump(LayoutSucc->front().getOpcode())) {
190  assert(JumpAroundTarget && "jump target is needed to process second basic block");
191  MachineBasicBlock* UncondTarget =
192  LayoutSucc->front().getOperand(0).getMBB();
193  // Check if the layout successor of BB2 is BB3.
194  bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget);
195  bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) &&
196  !JumpAroundTarget->empty() &&
197  IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) &&
198  JumpAroundTarget->pred_size() == 1 &&
199  JumpAroundTarget->succ_size() == 1;
200 
201  if (case1 || case2) {
202  InvertAndChangeJumpTarget(MI, UncondTarget);
203  MBB->replaceSuccessor(JumpAroundTarget, UncondTarget);
204 
205  // Remove the unconditional branch in LayoutSucc.
206  LayoutSucc->erase(LayoutSucc->begin());
207  LayoutSucc->replaceSuccessor(UncondTarget, JumpAroundTarget);
208 
209  // This code performs the conversion for case 2, which moves
210  // the block to the fall-thru case (BB3 in the code above).
211  if (case2 && !case1) {
212  JumpAroundTarget->moveAfter(LayoutSucc);
213  // only move a block if it doesn't have a fall-thru. otherwise
214  // the CFG will be incorrect.
215  if (!isOnFallThroughPath(UncondTarget))
216  UncondTarget->moveAfter(JumpAroundTarget);
217  }
218 
219  // Correct live-in information. Is used by post-RA scheduler
220  // The live-in to LayoutSucc is now all values live-in to
221  // JumpAroundTarget.
222  std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(
223  LayoutSucc->livein_begin(), LayoutSucc->livein_end());
224  std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(
225  JumpAroundTarget->livein_begin(),
226  JumpAroundTarget->livein_end());
227  for (const auto &OrigLI : OrigLiveIn)
228  LayoutSucc->removeLiveIn(OrigLI.PhysReg);
229  for (const auto &NewLI : NewLiveIn)
230  LayoutSucc->addLiveIn(NewLI);
231  }
232  }
233  }
234  }
235  }
236  }
237  return true;
238 }
239 
240 //===----------------------------------------------------------------------===//
241 // Public Constructor Functions
242 //===----------------------------------------------------------------------===//
243 
244 INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",
245  false, false)
246 
248  return new HexagonCFGOptimizer();
249 }
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:23
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:408
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:284
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:253
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:63
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:44
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:48
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
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()