llvm/lib/Target/PowerPC/PPCCTRLoops.cpp

   1 //===-- PPCCTRLoops.cpp - Verify 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 verifies that all bdnz/bdz instructions are dominated by a loop
  10 // mtctr before any other instructions that might clobber the ctr register.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 // CTR loops are produced by the HardwareLoops pass and this pass is simply a
  15 // verification that no invalid CTR loops are produced. As such, it isn't
  16 // something that needs to be run (or even defined) for Release builds so the
  17 // entire file is guarded by NDEBUG.
  18 #ifndef NDEBUG
  19 #include <vector>
  20
  21 #include "MCTargetDesc/PPCMCTargetDesc.h"
  22 #include "PPC.h"
  23 #include "llvm/ADT/SmallSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/StringRef.h"
  26 #include "llvm/ADT/ilist_iterator.h"
  27 #include "llvm/CodeGen/MachineBasicBlock.h"
  28 #include "llvm/CodeGen/MachineDominators.h"
  29 #include "llvm/CodeGen/MachineFunction.h"
  30 #include "llvm/CodeGen/MachineFunctionPass.h"
  31 #include "llvm/CodeGen/MachineInstr.h"
  32 #include "llvm/CodeGen/MachineInstrBundleIterator.h"
  33 #include "llvm/CodeGen/MachineOperand.h"
  34 #include "llvm/CodeGen/Register.h"
  35 #include "llvm/InitializePasses.h"
  36 #include "llvm/Pass.h"
  37 #include "llvm/PassRegistry.h"
  38 #include "llvm/Support/CodeGen.h"
  39 #include "llvm/Support/Debug.h"
  40 #include "llvm/Support/ErrorHandling.h"
  41 #include "llvm/Support/GenericDomTreeConstruction.h"
  42 #include "llvm/Support/Printable.h"
  43 #include "llvm/Support/raw_ostream.h"
  44
  45 using namespace llvm;
  46
  47 #define DEBUG_TYPE "ppc-ctrloops-verify"
  48
  49 namespace {
  50
  51   struct PPCCTRLoopsVerify : public MachineFunctionPass {
  52   public:
  53     static char ID;
  54
  55     PPCCTRLoopsVerify() : MachineFunctionPass(ID) {
  56       initializePPCCTRLoopsVerifyPass(*PassRegistry::getPassRegistry());
  57     }
  58
  59     void getAnalysisUsage(AnalysisUsage &AU) const override {
  60       AU.addRequired<MachineDominatorTree>();
  61       MachineFunctionPass::getAnalysisUsage(AU);
  62     }
  63
  64     bool runOnMachineFunction(MachineFunction &MF) override;
  65
  66   private:
  67     MachineDominatorTree *MDT;
  68   };
  69
  70   char PPCCTRLoopsVerify::ID = 0;
  71 } // end anonymous namespace
  72
  73 INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
  74                       "PowerPC CTR Loops Verify", false, false)
  75 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  76 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
  77                     "PowerPC CTR Loops Verify", false, false)
  78
  79 FunctionPass *llvm::createPPCCTRLoopsVerify() {
  80   return new PPCCTRLoopsVerify();
  81 }
  82
  83 static bool clobbersCTR(const MachineInstr &MI) {
  84   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
  85     const MachineOperand &MO = MI.getOperand(i);
  86     if (MO.isReg()) {
  87       if (MO.isDef() && (MO.getReg() == PPC::CTR || MO.getReg() == PPC::CTR8))
  88         return true;
  89     } else if (MO.isRegMask()) {
  90       if (MO.clobbersPhysReg(PPC::CTR) || MO.clobbersPhysReg(PPC::CTR8))
  91         return true;
  92     }
  93   }
  94
  95   return false;
  96 }
  97
  98 static bool verifyCTRBranch(MachineBasicBlock *MBB,
  99                             MachineBasicBlock::iterator I) {
 100   MachineBasicBlock::iterator BI = I;
 101   SmallSet<MachineBasicBlock *, 16>   Visited;
 102   SmallVector<MachineBasicBlock *, 8> Preds;
 103   bool CheckPreds;
 104
 105   if (I == MBB->begin()) {
 106     Visited.insert(MBB);
 107     goto queue_preds;
 108   } else
 109     --I;
 110
 111 check_block:
 112   Visited.insert(MBB);
 113   if (I == MBB->end())
 114     goto queue_preds;
 115
 116   CheckPreds = true;
 117   for (MachineBasicBlock::iterator IE = MBB->begin();; --I) {
 118     unsigned Opc = I->getOpcode();
 119     if (Opc == PPC::MTCTRloop || Opc == PPC::MTCTR8loop) {
 120       CheckPreds = false;
 121       break;
 122     }
 123
 124     if (I != BI && clobbersCTR(*I)) {
 125       LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " (" << MBB->getFullName()
 126                         << ") instruction " << *I
 127                         << " clobbers CTR, invalidating "
 128                         << printMBBReference(*BI->getParent()) << " ("
 129                         << BI->getParent()->getFullName() << ") instruction "
 130                         << *BI << "\n");
 131       return false;
 132     }
 133
 134     if (I == IE)
 135       break;
 136   }
 137
 138   if (!CheckPreds && Preds.empty())
 139     return true;
 140
 141   if (CheckPreds) {
 142 queue_preds:
 143     if (MachineFunction::iterator(MBB) == MBB->getParent()->begin()) {
 144       LLVM_DEBUG(dbgs() << "Unable to find a MTCTR instruction for "
 145                         << printMBBReference(*BI->getParent()) << " ("
 146                         << BI->getParent()->getFullName() << ") instruction "
 147                         << *BI << "\n");
 148       return false;
 149     }
 150
 151     append_range(Preds, MBB->predecessors());
 152   }
 153
 154   do {
 155     MBB = Preds.pop_back_val();
 156     if (!Visited.count(MBB)) {
 157       I = MBB->getLastNonDebugInstr();
 158       goto check_block;
 159     }
 160   } while (!Preds.empty());
 161
 162   return true;
 163 }
 164
 165 bool PPCCTRLoopsVerify::runOnMachineFunction(MachineFunction &MF) {
 166   MDT = &getAnalysis<MachineDominatorTree>();
 167
 168   // Verify that all bdnz/bdz instructions are dominated by a loop mtctr before
 169   // any other instructions that might clobber the ctr register.
 170   for (MachineFunction::iterator I = MF.begin(), IE = MF.end();
 171        I != IE; ++I) {
 172     MachineBasicBlock *MBB = &*I;
 173     if (!MDT->isReachableFromEntry(MBB))
 174       continue;
 175
 176     for (MachineBasicBlock::iterator MII = MBB->getFirstTerminator(),
 177       MIIE = MBB->end(); MII != MIIE; ++MII) {
 178       unsigned Opc = MII->getOpcode();
 179       if (Opc == PPC::BDNZ8 || Opc == PPC::BDNZ ||
 180           Opc == PPC::BDZ8  || Opc == PPC::BDZ)
 181         if (!verifyCTRBranch(MBB, MII))
 182           llvm_unreachable("Invalid PPC CTR loop!");
 183     }
 184   }
 185
 186   return false;
 187 }
 188 #endif // NDEBUG