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 
15 #include "PPCInstrInfo.h"
16 #include "MCTargetDesc/PPCPredicates.h"
17 #include "PPC.h"
18 #include "PPCInstrBuilder.h"
19 #include "PPCMachineFunctionInfo.h"
20 #include "PPCTargetMachine.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/CodeGen/MachineFrameInfo.h"
24 #include "llvm/CodeGen/MachineFunctionPass.h"
25 #include "llvm/CodeGen/MachineInstrBuilder.h"
26 #include "llvm/CodeGen/MachineMemOperand.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/MC/MCAsmInfo.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/ErrorHandling.h"
32 #include "llvm/Support/TargetRegistry.h"
33 #include "llvm/Support/raw_ostream.h"
34 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "ppc-early-ret"
38 STATISTIC(NumBCLR, "Number of early conditional returns");
39 STATISTIC(NumBLR,  "Number of early returns");
40 
41 namespace llvm {
42   void initializePPCEarlyReturnPass(PassRegistry&);
43 }
44 
45 namespace {
46   // PPCEarlyReturn pass - For simple functions without epilogue code, move
47   // returns up, and create conditional returns, to avoid unnecessary
48   // branch-to-blr sequences.
49   struct PPCEarlyReturn : public MachineFunctionPass {
50     static char ID;
51     PPCEarlyReturn() : MachineFunctionPass(ID) {
52       initializePPCEarlyReturnPass(*PassRegistry::getPassRegistry());
53     }
54 
55     const TargetInstrInfo *TII;
56 
57 protected:
58     bool processBlock(MachineBasicBlock &ReturnMBB) {
59       bool Changed = false;
60 
61       MachineBasicBlock::iterator I = ReturnMBB.begin();
62       I = ReturnMBB.SkipPHIsAndLabels(I);
63 
64       // The block must be essentially empty except for the blr.
65       if (I == ReturnMBB.end() ||
66           (I->getOpcode() != PPC::BLR && I->getOpcode() != PPC::BLR8) ||
67           I != ReturnMBB.getLastNonDebugInstr())
68         return Changed;
69 
70       SmallVector<MachineBasicBlock*, 8> PredToRemove;
71       for (MachineBasicBlock::pred_iterator PI = ReturnMBB.pred_begin(),
72            PIE = ReturnMBB.pred_end(); PI != PIE; ++PI) {
73         bool OtherReference = false, BlockChanged = false;
74 
75         if ((*PI)->empty())
76           continue;
77 
78         for (MachineBasicBlock::iterator J = (*PI)->getLastNonDebugInstr();;) {
79           if (J == (*PI)->end())
80             break;
81 
82           MachineInstrBuilder MIB;
83           if (J->getOpcode() == PPC::B) {
84             if (J->getOperand(0).getMBB() == &ReturnMBB) {
85               // This is an unconditional branch to the return. Replace the
86               // branch with a blr.
87               MIB =
88                 BuildMI(**PI, J, J->getDebugLoc(), TII->get(I->getOpcode()));
89               MIB.copyImplicitOps(I);
90               MachineBasicBlock::iterator K = J--;
91               K->eraseFromParent();
92               BlockChanged = true;
93               ++NumBLR;
94               continue;
95             }
96           } else if (J->getOpcode() == PPC::BCC) {
97             if (J->getOperand(2).getMBB() == &ReturnMBB) {
98               // This is a conditional branch to the return. Replace the branch
99               // with a bclr.
100               MIB = BuildMI(**PI, J, J->getDebugLoc(), TII->get(PPC::BCCLR))
101                       .addImm(J->getOperand(0).getImm())
102                       .addReg(J->getOperand(1).getReg());
103               MIB.copyImplicitOps(I);
104               MachineBasicBlock::iterator K = J--;
105               K->eraseFromParent();
106               BlockChanged = true;
107               ++NumBCLR;
108               continue;
109             }
110           } else if (J->getOpcode() == PPC::BC || J->getOpcode() == PPC::BCn) {
111             if (J->getOperand(1).getMBB() == &ReturnMBB) {
112               // This is a conditional branch to the return. Replace the branch
113               // with a bclr.
114               MIB = BuildMI(**PI, J, J->getDebugLoc(),
115                             TII->get(J->getOpcode() == PPC::BC ?
116                                      PPC::BCLR : PPC::BCLRn))
117                       .addReg(J->getOperand(0).getReg());
118               MIB.copyImplicitOps(I);
119               MachineBasicBlock::iterator K = J--;
120               K->eraseFromParent();
121               BlockChanged = true;
122               ++NumBCLR;
123               continue;
124             }
125           } else if (J->isBranch()) {
126             if (J->isIndirectBranch()) {
127               if (ReturnMBB.hasAddressTaken())
128                 OtherReference = true;
129             } else
130               for (unsigned i = 0; i < J->getNumOperands(); ++i)
131                 if (J->getOperand(i).isMBB() &&
132                     J->getOperand(i).getMBB() == &ReturnMBB)
133                   OtherReference = true;
134           } else if (!J->isTerminator() && !J->isDebugValue())
135             break;
136 
137           if (J == (*PI)->begin())
138             break;
139 
140           --J;
141         }
142 
143         if ((*PI)->canFallThrough() && (*PI)->isLayoutSuccessor(&ReturnMBB))
144           OtherReference = true;
145 
146         // Predecessors are stored in a vector and can't be removed here.
147         if (!OtherReference && BlockChanged) {
148           PredToRemove.push_back(*PI);
149         }
150 
151         if (BlockChanged)
152           Changed = true;
153       }
154 
155       for (unsigned i = 0, ie = PredToRemove.size(); i != ie; ++i)
156         PredToRemove[i]->removeSuccessor(&ReturnMBB);
157 
158       if (Changed && !ReturnMBB.hasAddressTaken()) {
159         // We now might be able to merge this blr-only block into its
160         // by-layout predecessor.
161         if (ReturnMBB.pred_size() == 1) {
162           MachineBasicBlock &PrevMBB = **ReturnMBB.pred_begin();
163           if (PrevMBB.isLayoutSuccessor(&ReturnMBB) && PrevMBB.canFallThrough()) {
164             // Move the blr into the preceding block.
165             PrevMBB.splice(PrevMBB.end(), &ReturnMBB, I);
166             PrevMBB.removeSuccessor(&ReturnMBB);
167           }
168         }
169 
170         if (ReturnMBB.pred_empty())
171           ReturnMBB.eraseFromParent();
172       }
173 
174       return Changed;
175     }
176 
177 public:
178     bool runOnMachineFunction(MachineFunction &MF) override {
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     void getAnalysisUsage(AnalysisUsage &AU) const override {
198       MachineFunctionPass::getAnalysisUsage(AU);
199     }
200   };
201 }
202 
203 INITIALIZE_PASS(PPCEarlyReturn, DEBUG_TYPE,
204                 "PowerPC Early-Return Creation", false, false)
205 
206 char PPCEarlyReturn::ID = 0;
207 FunctionPass*
208 llvm::createPPCEarlyReturnPass() { return new PPCEarlyReturn(); }
209 
210