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