LLVM  6.0.0svn
PPCEarlyReturn.cpp
Go to the documentation of this file.
1 //===------------- PPCEarlyReturn.cpp - Form Early Returns ----------------===//
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 // A pass that form early (predicated) returns. If-conversion handles some of
11 // this, but this pass picks up some remaining cases.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "PPC.h"
17 #include "PPCInstrBuilder.h"
18 #include "PPCInstrInfo.h"
19 #include "PPCMachineFunctionInfo.h"
20 #include "PPCTargetMachine.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/Statistic.h"
28 #include "llvm/MC/MCAsmInfo.h"
29 #include "llvm/Support/Debug.h"
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "ppc-early-ret"
37 STATISTIC(NumBCLR, "Number of early conditional returns");
38 STATISTIC(NumBLR, "Number of early returns");
39 
40 namespace llvm {
42 }
43 
44 namespace {
45  // PPCEarlyReturn pass - For simple functions without epilogue code, move
46  // returns up, and create conditional returns, to avoid unnecessary
47  // branch-to-blr sequences.
48  struct PPCEarlyReturn : public MachineFunctionPass {
49  static char ID;
50  PPCEarlyReturn() : MachineFunctionPass(ID) {
52  }
53 
54  const TargetInstrInfo *TII;
55 
56 protected:
57  bool processBlock(MachineBasicBlock &ReturnMBB) {
58  bool Changed = false;
59 
60  MachineBasicBlock::iterator I = ReturnMBB.begin();
61  I = ReturnMBB.SkipPHIsLabelsAndDebug(I);
62 
63  // The block must be essentially empty except for the blr.
64  if (I == ReturnMBB.end() ||
65  (I->getOpcode() != PPC::BLR && I->getOpcode() != PPC::BLR8) ||
66  I != ReturnMBB.getLastNonDebugInstr())
67  return Changed;
68 
70  for (MachineBasicBlock::pred_iterator PI = ReturnMBB.pred_begin(),
71  PIE = ReturnMBB.pred_end(); PI != PIE; ++PI) {
72  bool OtherReference = false, BlockChanged = false;
73 
74  if ((*PI)->empty())
75  continue;
76 
77  for (MachineBasicBlock::iterator J = (*PI)->getLastNonDebugInstr();;) {
78  if (J == (*PI)->end())
79  break;
80 
81  if (J->getOpcode() == PPC::B) {
82  if (J->getOperand(0).getMBB() == &ReturnMBB) {
83  // This is an unconditional branch to the return. Replace the
84  // branch with a blr.
85  BuildMI(**PI, J, J->getDebugLoc(), TII->get(I->getOpcode()))
86  .copyImplicitOps(*I);
88  K->eraseFromParent();
89  BlockChanged = true;
90  ++NumBLR;
91  continue;
92  }
93  } else if (J->getOpcode() == PPC::BCC) {
94  if (J->getOperand(2).getMBB() == &ReturnMBB) {
95  // This is a conditional branch to the return. Replace the branch
96  // with a bclr.
97  BuildMI(**PI, J, J->getDebugLoc(), TII->get(PPC::BCCLR))
98  .addImm(J->getOperand(0).getImm())
99  .addReg(J->getOperand(1).getReg())
100  .copyImplicitOps(*I);
102  K->eraseFromParent();
103  BlockChanged = true;
104  ++NumBCLR;
105  continue;
106  }
107  } else if (J->getOpcode() == PPC::BC || J->getOpcode() == PPC::BCn) {
108  if (J->getOperand(1).getMBB() == &ReturnMBB) {
109  // This is a conditional branch to the return. Replace the branch
110  // with a bclr.
111  BuildMI(
112  **PI, J, J->getDebugLoc(),
113  TII->get(J->getOpcode() == PPC::BC ? PPC::BCLR : PPC::BCLRn))
114  .addReg(J->getOperand(0).getReg())
115  .copyImplicitOps(*I);
117  K->eraseFromParent();
118  BlockChanged = true;
119  ++NumBCLR;
120  continue;
121  }
122  } else if (J->isBranch()) {
123  if (J->isIndirectBranch()) {
124  if (ReturnMBB.hasAddressTaken())
125  OtherReference = true;
126  } else
127  for (unsigned i = 0; i < J->getNumOperands(); ++i)
128  if (J->getOperand(i).isMBB() &&
129  J->getOperand(i).getMBB() == &ReturnMBB)
130  OtherReference = true;
131  } else if (!J->isTerminator() && !J->isDebugValue())
132  break;
133 
134  if (J == (*PI)->begin())
135  break;
136 
137  --J;
138  }
139 
140  if ((*PI)->canFallThrough() && (*PI)->isLayoutSuccessor(&ReturnMBB))
141  OtherReference = true;
142 
143  // Predecessors are stored in a vector and can't be removed here.
144  if (!OtherReference && BlockChanged) {
145  PredToRemove.push_back(*PI);
146  }
147 
148  if (BlockChanged)
149  Changed = true;
150  }
151 
152  for (unsigned i = 0, ie = PredToRemove.size(); i != ie; ++i)
153  PredToRemove[i]->removeSuccessor(&ReturnMBB, true);
154 
155  if (Changed && !ReturnMBB.hasAddressTaken()) {
156  // We now might be able to merge this blr-only block into its
157  // by-layout predecessor.
158  if (ReturnMBB.pred_size() == 1) {
159  MachineBasicBlock &PrevMBB = **ReturnMBB.pred_begin();
160  if (PrevMBB.isLayoutSuccessor(&ReturnMBB) && PrevMBB.canFallThrough()) {
161  // Move the blr into the preceding block.
162  PrevMBB.splice(PrevMBB.end(), &ReturnMBB, I);
163  PrevMBB.removeSuccessor(&ReturnMBB, true);
164  }
165  }
166 
167  if (ReturnMBB.pred_empty())
168  ReturnMBB.eraseFromParent();
169  }
170 
171  return Changed;
172  }
173 
174 public:
175  bool runOnMachineFunction(MachineFunction &MF) override {
176  if (skipFunction(*MF.getFunction()))
177  return false;
178 
179  TII = MF.getSubtarget().getInstrInfo();
180 
181  bool Changed = false;
182 
183  // If the function does not have at least two blocks, then there is
184  // nothing to do.
185  if (MF.size() < 2)
186  return Changed;
187 
188  for (MachineFunction::iterator I = MF.begin(); I != MF.end();) {
189  MachineBasicBlock &B = *I++;
190  if (processBlock(B))
191  Changed = true;
192  }
193 
194  return Changed;
195  }
196 
197  MachineFunctionProperties getRequiredProperties() const override {
200  }
201 
202  void getAnalysisUsage(AnalysisUsage &AU) const override {
204  }
205  };
206 }
207 
208 INITIALIZE_PASS(PPCEarlyReturn, DEBUG_TYPE,
209  "PowerPC Early-Return Creation", false, false)
210 
211 char PPCEarlyReturn::ID = 0;
213 llvm::createPPCEarlyReturnPass() { return new PPCEarlyReturn(); }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
#define DEBUG_TYPE
unsigned size() const
STATISTIC(NumFunctions, "Total number of functions")
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing function and deletes it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
iterator getLastNonDebugInstr()
Returns an iterator to the last non-debug instruction in the basic block, or end().
virtual const TargetInstrInfo * getInstrInfo() const
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
FunctionPass * createPPCEarlyReturnPass()
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.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
std::vector< MachineBasicBlock * >::iterator pred_iterator
bool hasAddressTaken() const
Test whether this block is potentially the target of an indirect branch.
void initializePPCEarlyReturnPass(PassRegistry &)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:34
Iterator for intrusive lists based on ilist_node.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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 MachineInstrBuilder & copyImplicitOps(const MachineInstr &OtherMI) const
Copy all the implicit operands from OtherMI onto this one.
MachineFunctionProperties & set(Property P)
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
#define I(x, y, z)
Definition: MD5.cpp:58
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
iterator SkipPHIsLabelsAndDebug(iterator I)
Return the first instruction in MBB after I that is not a PHI, label or debug.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
Properties which a MachineFunction may have at a given point in time.