lib/Target/PowerPC/PPCCTRLoops.cpp

   1 //===-- PPCCTRLoops.cpp - Identify and generate CTR loops -----------------===//
   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 // This pass identifies loops where we can generate the PPC branch instructions
  10 // that decrement and test the count register (CTR) (bdnz and friends).
  11 //
  12 // The pattern that defines the induction variable can changed depending on
  13 // prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
  14 // normalizes induction variables, and the Loop Strength Reduction pass
  15 // run by 'llc' may also make changes to the induction variable.
  16 //
  17 // Criteria for CTR loops:
  18 //  - Countable loops (w/ ind. var for a trip count)
  19 //  - Try inner-most loops first
  20 //  - No nested CTR loops.
  21 //  - No function calls in loops.
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "PPC.h"
  26 #include "PPCSubtarget.h"
  27 #include "PPCTargetMachine.h"
  28 #include "PPCTargetTransformInfo.h"
  29 #include "llvm/ADT/STLExtras.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/Analysis/AssumptionCache.h"
  32 #include "llvm/Analysis/CFG.h"
  33 #include "llvm/Analysis/CodeMetrics.h"
  34 #include "llvm/Analysis/LoopInfo.h"
  35 #include "llvm/Analysis/LoopIterator.h"
  36 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  37 #include "llvm/Analysis/TargetLibraryInfo.h"
  38 #include "llvm/Analysis/TargetTransformInfo.h"
  39 #include "llvm/Transforms/Utils/Local.h"
  40 #include "llvm/CodeGen/TargetPassConfig.h"
  41 #include "llvm/CodeGen/TargetSchedule.h"
  42 #include "llvm/IR/Constants.h"
  43 #include "llvm/IR/DerivedTypes.h"
  44 #include "llvm/IR/Dominators.h"
  45 #include "llvm/IR/InlineAsm.h"
  46 #include "llvm/IR/Instructions.h"
  47 #include "llvm/IR/IntrinsicInst.h"
  48 #include "llvm/IR/Module.h"
  49 #include "llvm/IR/ValueHandle.h"
  50 #include "llvm/PassSupport.h"
  51 #include "llvm/Support/CommandLine.h"
  52 #include "llvm/Support/Debug.h"
  53 #include "llvm/Support/raw_ostream.h"
  54 #include "llvm/Transforms/Scalar.h"
  55 #include "llvm/Transforms/Utils.h"
  56 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  57 #include "llvm/Transforms/Utils/LoopUtils.h"
  58
  59 #ifndef NDEBUG
  60 #include "llvm/CodeGen/MachineDominators.h"
  61 #include "llvm/CodeGen/MachineFunction.h"
  62 #include "llvm/CodeGen/MachineFunctionPass.h"
  63 #include "llvm/CodeGen/MachineRegisterInfo.h"
  64 #endif
  65
  66 using namespace llvm;
  67
  68 #define DEBUG_TYPE "ctrloops"
  69
  70 #ifndef NDEBUG
  71 static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1));
  72 #endif
  73
  74 namespace {
  75
  76 #ifndef NDEBUG
  77   struct PPCCTRLoopsVerify : public MachineFunctionPass {
  78   public:
  79     static char ID;
  80
  81     PPCCTRLoopsVerify() : MachineFunctionPass(ID) {
  82       initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry());
  83     }
  84
  85     void getAnalysisUsage(AnalysisUsage &AU) const override {
  86       AU.addRequired<MachineDominatorTree>();
  87       MachineFunctionPass::getAnalysisUsage(AU);
  88     }
  89
  90     bool runOnMachineFunction(MachineFunction &MF) override;
  91
  92   private:
  93     MachineDominatorTree *MDT;
  94   };
  95
  96   char PPCCTRLoopsVerify::ID = 0;
  97 #endif // NDEBUG
  98 } // end anonymous namespace
  99
 100 #ifndef NDEBUG
 101 INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
 102                       "PowerPC CTR Loops Verify", false, false)
 103 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 104 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
 105                     "PowerPC CTR Loops Verify", false, false)
 106
 107 FunctionPass *llvm::createPPCCTRLoopsVerify() {
 108   return new PPCCTRLoopsVerify();
 109 }
 110 #endif // NDEBUG
 111
 112 #ifndef NDEBUG
 113 static bool clobbersCTR(const MachineInstr &MI) {
 114   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 115     const MachineOperand &MO = MI.getOperand(i);
 116     if (MO.isReg()) {
 117       if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8))
 118         return true;
 119     } else if (MO.isRegMask()) {
 120       if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8))
 121         return true;
 122     }
 123   }
 124
 125   return false;
 126 }
 127
 128 static bool verifyCTRBranch(MachineBasicBlock *MBB,
 129                             MachineBasicBlock::iterator I) {
 130   MachineBasicBlock::iterator BI = I;
 131   SmallSet<MachineBasicBlock *, 16>   Visited;
 132   SmallVector<MachineBasicBlock *, 8> Preds;
 133   bool CheckPreds;
 134
 135   if (I == MBB->begin()) {
 136     Visited.insert(MBB);
 137     goto queue_preds;
 138   } else
 139     --I;
 140
 141 check_block:
 142   Visited.insert(MBB);
 143   if (I == MBB->end())
 144     goto queue_preds;
 145
 146   CheckPreds = true;
 147   for (MachineBasicBlock::iterator IE = MBB->begin();; --I) {
 148     unsigned Opc = I->getOpcode();
 149     if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) {
 150       CheckPreds = false;
 151       break;
 152     }
 153
 154     if (I != BI && clobbersCTR(*I)) {
 155       LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " (" << MBB->getFullName()
 156                         << ") instruction " << *I
 157                         << " clobbers CTR, invalidating "
 158                         << printMBBReference(*BI->getParent()) << " ("
 159                         << BI->getParent()->getFullName() << ") instruction "
 160                         << *BI << "\n");
 161       return false;
 162     }
 163
 164     if (I == IE)
 165       break;
 166   }
 167
 168   if (!CheckPreds && Preds.empty())
 169     return true;
 170
 171   if (CheckPreds) {
 172 queue_preds:
 173     if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) {
 174       LLVM_DEBUG(dbgs() << "Unable to find a MTCTR instruction for "
 175                         << printMBBReference(*BI->getParent()) << " ("
 176                         << BI->getParent()->getFullName() << ") instruction "
 177                         << *BI << "\n");
 178       return false;
 179     }
 180
 181     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 182          PIE = MBB->pred_end(); PI != PIE; ++PI)
 183       Preds.push_back(*PI);
 184   }
 185
 186   do {
 187     MBB = Preds.pop_back_val();
 188     if (!Visited.count(MBB)) {
 189       I = MBB->getLastNonDebugInstr();
 190       goto check_block;
 191     }
 192   } while (!Preds.empty());
 193
 194   return true;
 195 }
 196
 197 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) {
 198   MDT = &getAnalysis<MachineDominatorTree>();
 199
 200   // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before
 201   // any other instructions that might clobber the ctr register.
 202   for (MachineFunction::iterator I = MF.begin(), IE = MF.end();
 203        I != IE; ++I) {
 204     MachineBasicBlock *MBB = &*I;
 205     if (!MDT->isReachableFromEntry(MBB))
 206       continue;
 207
 208     for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(),
 209       MIIE = MBB->end(); MII != MIIE; ++MII) {
 210       unsigned Opc = MII->getOpcode();
 211       if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ ||
 212           Opc == PPC::BDZ8  || Opc == PPC::BDZ)
 213         if (!verifyCTRBranch(MBB, MII))
 214           llvm_unreachable("Invalid PPC CTR loop!");
 215     }
 216   }
 217
 218   return false;
 219 }
 220 #endif // NDEBUG