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/MC/TargetRegistry.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/ErrorHandling.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 {
40   // PPCEarlyReturn pass - For simple functions without epilogue code, move
41   // returns up, and create conditional returns, to avoid unnecessary
42   // branch-to-blr sequences.
43   struct PPCEarlyReturn : public MachineFunctionPass {
44     static char ID;
45     PPCEarlyReturn() : MachineFunctionPass(ID) {
46       initializePPCEarlyReturnPass(*PassRegistry::getPassRegistry());
47     }
48 
49     const TargetInstrInfo *TII;
50 
51 protected:
52     bool processBlock(MachineBasicBlock &ReturnMBB) {
53       bool Changed = false;
54 
55       MachineBasicBlock::iterator I = ReturnMBB.begin();
56       I = ReturnMBB.SkipPHIsLabelsAndDebug(I);
57 
58       // The block must be essentially empty except for the blr.
59       if (I == ReturnMBB.end() ||
60           (I->getOpcode() != PPC::BLR && I->getOpcode() != PPC::BLR8) ||
61           I != ReturnMBB.getLastNonDebugInstr())
62         return Changed;
63 
64       SmallVector<MachineBasicBlock*, 8> PredToRemove;
65       for (MachineBasicBlock *Pred : ReturnMBB.predecessors()) {
66         bool OtherReference = false, BlockChanged = false;
67 
68         if (Pred->empty())
69           continue;
70 
71         for (MachineBasicBlock::iterator J = Pred->getLastNonDebugInstr();;) {
72           if (J == Pred->end())
73             break;
74 
75           if (J->getOpcode() == PPC::B) {
76             if (J->getOperand(0).getMBB() == &ReturnMBB) {
77               // This is an unconditional branch to the return. Replace the
78               // branch with a blr.
79               MachineInstr *MI = ReturnMBB.getParent()->CloneMachineInstr(&*I);
80               Pred->insert(J, MI);
81 
82               MachineBasicBlock::iterator K = J--;
83               K->eraseFromParent();
84               BlockChanged = true;
85               ++NumBLR;
86               continue;
87             }
88           } else if (J->getOpcode() == PPC::BCC) {
89             if (J->getOperand(2).getMBB() == &ReturnMBB) {
90               // This is a conditional branch to the return. Replace the branch
91               // with a bclr.
92               MachineInstr *MI = ReturnMBB.getParent()->CloneMachineInstr(&*I);
93               MI->setDesc(TII->get(PPC::BCCLR));
94               MachineInstrBuilder(*ReturnMBB.getParent(), MI)
95                   .add(J->getOperand(0))
96                   .add(J->getOperand(1));
97               Pred->insert(J, MI);
98 
99               MachineBasicBlock::iterator K = J--;
100               K->eraseFromParent();
101               BlockChanged = true;
102               ++NumBCLR;
103               continue;
104             }
105           } else if (J->getOpcode() == PPC::BC || J->getOpcode() == PPC::BCn) {
106             if (J->getOperand(1).getMBB() == &ReturnMBB) {
107               // This is a conditional branch to the return. Replace the branch
108               // with a bclr.
109               MachineInstr *MI = ReturnMBB.getParent()->CloneMachineInstr(&*I);
110               MI->setDesc(
111                   TII->get(J->getOpcode() == PPC::BC ? PPC::BCLR : PPC::BCLRn));
112               MachineInstrBuilder(*ReturnMBB.getParent(), MI)
113                   .add(J->getOperand(0));
114               Pred->insert(J, MI);
115 
116               MachineBasicBlock::iterator K = J--;
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->isDebugInstr())
132             break;
133 
134           if (J == Pred->begin())
135             break;
136 
137           --J;
138         }
139 
140         if (Pred->canFallThrough() && Pred->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(Pred);
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 (MachineBasicBlock &B : llvm::make_early_inc_range(MF))
189         Changed |= processBlock(B);
190 
191       return Changed;
192     }
193 
194     MachineFunctionProperties getRequiredProperties() const override {
195       return MachineFunctionProperties().set(
196           MachineFunctionProperties::Property::NoVRegs);
197     }
198 
199     void getAnalysisUsage(AnalysisUsage &AU) const override {
200       MachineFunctionPass::getAnalysisUsage(AU);
201     }
202   };
203 }
204 
205 INITIALIZE_PASS(PPCEarlyReturn, DEBUG_TYPE,
206                 "PowerPC Early-Return Creation", false, false)
207 
208 char PPCEarlyReturn::ID = 0;
209 FunctionPass*
210 llvm::createPPCEarlyReturnPass() { return new PPCEarlyReturn(); }
211