LLVM  9.0.0svn
PPCCTRLoops.cpp
Go to the documentation of this file.
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"
32 #include "llvm/Analysis/CFG.h"
34 #include "llvm/Analysis/LoopInfo.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"
52 #include "llvm/Support/Debug.h"
54 #include "llvm/Transforms/Scalar.h"
55 #include "llvm/Transforms/Utils.h"
58 
59 #ifndef NDEBUG
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) {
83  }
84 
85  void getAnalysisUsage(AnalysisUsage &AU) const override {
88  }
89 
90  bool runOnMachineFunction(MachineFunction &MF) override;
91 
92  private:
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)
104 INITIALIZE_PASS_END(PPCCTRLoopsVerify, "ppc-ctr-loops-verify",
105  "PowerPC CTR Loops Verify", false, false)
106 
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 
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 
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 
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
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void initializePPCCTRLoopsVerifyPass(PassRegistry &)
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Hexagon Hardware Loops
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
This file a TargetTransformInfo::Concept conforming object specific to the PPC target machine...
static cl::opt< int > CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1))
ppc ctr loops PowerPC CTR Loops Verify
CHAIN = BDNZ CHAIN, DESTBB - These are used to create counter-based loops.
FunctionPass * createPPCCTRLoopsVerify()
iterator getLastNonDebugInstr()
Returns an iterator to the last non-debug instruction in the basic block, or end().
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
std::vector< MachineBasicBlock * >::iterator pred_iterator
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
Iterator for intrusive lists based on ilist_node.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
INITIALIZE_PASS_BEGIN(PPCCTRLoopsVerify, "ppc-ctr-loops-verify", "PowerPC CTR Loops Verify", false, false) INITIALIZE_PASS_END(PPCCTRLoopsVerify
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
bool isReg() const
isReg - Tests if this is a MO_Register operand.
static bool clobbersCTR(const MachineInstr &MI)
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
IRTranslator LLVM IR MI
This pass exposes codegen information to IR-level passes.
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
static bool verifyCTRBranch(MachineBasicBlock *MBB, MachineBasicBlock::iterator I)
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
loops
Definition: LoopInfo.cpp:1016
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164