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