contrib/llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp

   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 "MCTargetDesc/PPCPredicates.h"
  16 #include "PPC.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.SkipPHIsLabelsAndDebug(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->isDebugInstr())
 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::NoVRegs);
 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(); }