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 "PPC.h" 16 #include "MCTargetDesc/PPCPredicates.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" 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/Debug.h" 30 #include "llvm/Support/ErrorHandling.h" 31 #include "llvm/Support/TargetRegistry.h" 32 #include "llvm/Support/raw_ostream.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 { 41 void initializePPCEarlyReturnPass(PassRegistry&); 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) { 51 initializePPCEarlyReturnPass(*PassRegistry::getPassRegistry()); 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.SkipPHIsAndLabels(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 69 SmallVector<MachineBasicBlock*, 8> PredToRemove; 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); 87 MachineBasicBlock::iterator K = J--; 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); 101 MachineBasicBlock::iterator K = J--; 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); 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->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 { 198 return MachineFunctionProperties().set( 199 MachineFunctionProperties::Property::AllVRegsAllocated); 200 } 201 202 void getAnalysisUsage(AnalysisUsage &AU) const override { 203 MachineFunctionPass::getAnalysisUsage(AU); 204 } 205 }; 206 } 207 208 INITIALIZE_PASS(PPCEarlyReturn, DEBUG_TYPE, 209 "PowerPC Early-Return Creation", false, false) 210 211 char PPCEarlyReturn::ID = 0; 212 FunctionPass* 213 llvm::createPPCEarlyReturnPass() { return new PPCEarlyReturn(); } 214