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 if (J->getOpcode() == PPC::B) { 83 if (J->getOperand(0).getMBB() == &ReturnMBB) { 84 // This is an unconditional branch to the return. Replace the 85 // branch with a blr. 86 BuildMI(**PI, J, J->getDebugLoc(), TII->get(I->getOpcode())) 87 .copyImplicitOps(I); 88 MachineBasicBlock::iterator K = J--; 89 K->eraseFromParent(); 90 BlockChanged = true; 91 ++NumBLR; 92 continue; 93 } 94 } else if (J->getOpcode() == PPC::BCC) { 95 if (J->getOperand(2).getMBB() == &ReturnMBB) { 96 // This is a conditional branch to the return. Replace the branch 97 // with a bclr. 98 BuildMI(**PI, J, J->getDebugLoc(), TII->get(PPC::BCCLR)) 99 .addImm(J->getOperand(0).getImm()) 100 .addReg(J->getOperand(1).getReg()) 101 .copyImplicitOps(I); 102 MachineBasicBlock::iterator K = J--; 103 K->eraseFromParent(); 104 BlockChanged = true; 105 ++NumBCLR; 106 continue; 107 } 108 } else if (J->getOpcode() == PPC::BC || J->getOpcode() == PPC::BCn) { 109 if (J->getOperand(1).getMBB() == &ReturnMBB) { 110 // This is a conditional branch to the return. Replace the branch 111 // with a bclr. 112 BuildMI( 113 **PI, J, J->getDebugLoc(), 114 TII->get(J->getOpcode() == PPC::BC ? PPC::BCLR : PPC::BCLRn)) 115 .addReg(J->getOperand(0).getReg()) 116 .copyImplicitOps(I); 117 MachineBasicBlock::iterator K = J--; 118 K->eraseFromParent(); 119 BlockChanged = true; 120 ++NumBCLR; 121 continue; 122 } 123 } else if (J->isBranch()) { 124 if (J->isIndirectBranch()) { 125 if (ReturnMBB.hasAddressTaken()) 126 OtherReference = true; 127 } else 128 for (unsigned i = 0; i < J->getNumOperands(); ++i) 129 if (J->getOperand(i).isMBB() && 130 J->getOperand(i).getMBB() == &ReturnMBB) 131 OtherReference = true; 132 } else if (!J->isTerminator() && !J->isDebugValue()) 133 break; 134 135 if (J == (*PI)->begin()) 136 break; 137 138 --J; 139 } 140 141 if ((*PI)->canFallThrough() && (*PI)->isLayoutSuccessor(&ReturnMBB)) 142 OtherReference = true; 143 144 // Predecessors are stored in a vector and can't be removed here. 145 if (!OtherReference && BlockChanged) { 146 PredToRemove.push_back(*PI); 147 } 148 149 if (BlockChanged) 150 Changed = true; 151 } 152 153 for (unsigned i = 0, ie = PredToRemove.size(); i != ie; ++i) 154 PredToRemove[i]->removeSuccessor(&ReturnMBB, true); 155 156 if (Changed && !ReturnMBB.hasAddressTaken()) { 157 // We now might be able to merge this blr-only block into its 158 // by-layout predecessor. 159 if (ReturnMBB.pred_size() == 1) { 160 MachineBasicBlock &PrevMBB = **ReturnMBB.pred_begin(); 161 if (PrevMBB.isLayoutSuccessor(&ReturnMBB) && PrevMBB.canFallThrough()) { 162 // Move the blr into the preceding block. 163 PrevMBB.splice(PrevMBB.end(), &ReturnMBB, I); 164 PrevMBB.removeSuccessor(&ReturnMBB, true); 165 } 166 } 167 168 if (ReturnMBB.pred_empty()) 169 ReturnMBB.eraseFromParent(); 170 } 171 172 return Changed; 173 } 174 175 public: 176 bool runOnMachineFunction(MachineFunction &MF) override { 177 TII = MF.getSubtarget().getInstrInfo(); 178 179 bool Changed = false; 180 181 // If the function does not have at least two blocks, then there is 182 // nothing to do. 183 if (MF.size() < 2) 184 return Changed; 185 186 for (MachineFunction::iterator I = MF.begin(); I != MF.end();) { 187 MachineBasicBlock &B = *I++; 188 if (processBlock(B)) 189 Changed = true; 190 } 191 192 return Changed; 193 } 194 195 void getAnalysisUsage(AnalysisUsage &AU) const override { 196 MachineFunctionPass::getAnalysisUsage(AU); 197 } 198 }; 199 } 200 201 INITIALIZE_PASS(PPCEarlyReturn, DEBUG_TYPE, 202 "PowerPC Early-Return Creation", false, false) 203 204 char PPCEarlyReturn::ID = 0; 205 FunctionPass* 206 llvm::createPPCEarlyReturnPass() { return new PPCEarlyReturn(); } 207 208