LLVM  10.0.0svn
PredicateInfo.cpp
Go to the documentation of this file.
1 //===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//
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 file implements the PredicateInfo class.
10 //
11 //===----------------------------------------------------------------===//
12 
14 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/CFG.h"
23 #include "llvm/IR/DataLayout.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/GlobalVariable.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/InstIterator.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/Support/Debug.h"
36 #include "llvm/Transforms/Utils.h"
37 #include <algorithm>
38 #define DEBUG_TYPE "predicateinfo"
39 using namespace llvm;
40 using namespace PatternMatch;
41 using namespace llvm::PredicateInfoClasses;
42 
44  "PredicateInfo Printer", false, false)
48  "PredicateInfo Printer", false, false)
49 static cl::opt<bool> VerifyPredicateInfo(
50  "verify-predicateinfo", cl::init(false), cl::Hidden,
51  cl::desc("Verify PredicateInfo in legacy printer pass."));
52 DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
53  "Controls which variables are renamed with predicateinfo");
54 
55 namespace {
56 // Given a predicate info that is a type of branching terminator, get the
57 // branching block.
58 const BasicBlock *getBranchBlock(const PredicateBase *PB) {
59  assert(isa<PredicateWithEdge>(PB) &&
60  "Only branches and switches should have PHIOnly defs that "
61  "require branch blocks.");
62  return cast<PredicateWithEdge>(PB)->From;
63 }
64 
65 // Given a predicate info that is a type of branching terminator, get the
66 // branching terminator.
67 static Instruction *getBranchTerminator(const PredicateBase *PB) {
68  assert(isa<PredicateWithEdge>(PB) &&
69  "Not a predicate info type we know how to get a terminator from.");
70  return cast<PredicateWithEdge>(PB)->From->getTerminator();
71 }
72 
73 // Given a predicate info that is a type of branching terminator, get the
74 // edge this predicate info represents
75 const std::pair<BasicBlock *, BasicBlock *>
76 getBlockEdge(const PredicateBase *PB) {
77  assert(isa<PredicateWithEdge>(PB) &&
78  "Not a predicate info type we know how to get an edge from.");
79  const auto *PEdge = cast<PredicateWithEdge>(PB);
80  return std::make_pair(PEdge->From, PEdge->To);
81 }
82 }
83 
84 namespace llvm {
85 namespace PredicateInfoClasses {
86 enum LocalNum {
87  // Operations that must appear first in the block.
89  // Operations that are somewhere in the middle of the block, and are sorted on
90  // demand.
92  // Operations that must appear last in a block, like successor phi node uses.
94 };
95 
96 // Associate global and local DFS info with defs and uses, so we can sort them
97 // into a global domination ordering.
98 struct ValueDFS {
99  int DFSIn = 0;
100  int DFSOut = 0;
101  unsigned int LocalNum = LN_Middle;
102  // Only one of Def or Use will be set.
103  Value *Def = nullptr;
104  Use *U = nullptr;
105  // Neither PInfo nor EdgeOnly participate in the ordering
106  PredicateBase *PInfo = nullptr;
107  bool EdgeOnly = false;
108 };
109 
110 // Perform a strict weak ordering on instructions and arguments.
111 static bool valueComesBefore(OrderedInstructions &OI, const Value *A,
112  const Value *B) {
113  auto *ArgA = dyn_cast_or_null<Argument>(A);
114  auto *ArgB = dyn_cast_or_null<Argument>(B);
115  if (ArgA && !ArgB)
116  return true;
117  if (ArgB && !ArgA)
118  return false;
119  if (ArgA && ArgB)
120  return ArgA->getArgNo() < ArgB->getArgNo();
121  return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B));
122 }
123 
124 // This compares ValueDFS structures, creating OrderedBasicBlocks where
125 // necessary to compare uses/defs in the same block. Doing so allows us to walk
126 // the minimum number of instructions necessary to compute our def/use ordering.
131  : DT(DT), OI(OI) {}
132 
133  bool operator()(const ValueDFS &A, const ValueDFS &B) const {
134  if (&A == &B)
135  return false;
136  // The only case we can't directly compare them is when they in the same
137  // block, and both have localnum == middle. In that case, we have to use
138  // comesbefore to see what the real ordering is, because they are in the
139  // same basic block.
140 
141  assert((A.DFSIn != B.DFSIn || A.DFSOut == B.DFSOut) &&
142  "Equal DFS-in numbers imply equal out numbers");
143  bool SameBlock = A.DFSIn == B.DFSIn;
144 
145  // We want to put the def that will get used for a given set of phi uses,
146  // before those phi uses.
147  // So we sort by edge, then by def.
148  // Note that only phi nodes uses and defs can come last.
149  if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
150  return comparePHIRelated(A, B);
151 
152  bool isADef = A.Def;
153  bool isBDef = B.Def;
154  if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
155  return std::tie(A.DFSIn, A.LocalNum, isADef) <
156  std::tie(B.DFSIn, B.LocalNum, isBDef);
157  return localComesBefore(A, B);
158  }
159 
160  // For a phi use, or a non-materialized def, return the edge it represents.
161  const std::pair<BasicBlock *, BasicBlock *>
162  getBlockEdge(const ValueDFS &VD) const {
163  if (!VD.Def && VD.U) {
164  auto *PHI = cast<PHINode>(VD.U->getUser());
165  return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
166  }
167  // This is really a non-materialized def.
168  return ::getBlockEdge(VD.PInfo);
169  }
170 
171  // For two phi related values, return the ordering.
172  bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
173  BasicBlock *ASrc, *ADest, *BSrc, *BDest;
174  std::tie(ASrc, ADest) = getBlockEdge(A);
175  std::tie(BSrc, BDest) = getBlockEdge(B);
176 
177 #ifndef NDEBUG
178  // This function should only be used for values in the same BB, check that.
179  DomTreeNode *DomASrc = DT.getNode(ASrc);
180  DomTreeNode *DomBSrc = DT.getNode(BSrc);
181  assert(DomASrc->getDFSNumIn() == (unsigned)A.DFSIn &&
182  "DFS numbers for A should match the ones of the source block");
183  assert(DomBSrc->getDFSNumIn() == (unsigned)B.DFSIn &&
184  "DFS numbers for B should match the ones of the source block");
185  assert(A.DFSIn == B.DFSIn && "Values must be in the same block");
186 #endif
187  (void)ASrc;
188  (void)BSrc;
189 
190  // Use DFS numbers to compare destination blocks, to guarantee a
191  // deterministic order.
192  DomTreeNode *DomADest = DT.getNode(ADest);
193  DomTreeNode *DomBDest = DT.getNode(BDest);
194  unsigned AIn = DomADest->getDFSNumIn();
195  unsigned BIn = DomBDest->getDFSNumIn();
196  bool isADef = A.Def;
197  bool isBDef = B.Def;
198  assert((!A.Def || !A.U) && (!B.Def || !B.U) &&
199  "Def and U cannot be set at the same time");
200  // Now sort by edge destination and then defs before uses.
201  return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
202  }
203 
204  // Get the definition of an instruction that occurs in the middle of a block.
205  Value *getMiddleDef(const ValueDFS &VD) const {
206  if (VD.Def)
207  return VD.Def;
208  // It's possible for the defs and uses to be null. For branches, the local
209  // numbering will say the placed predicaeinfos should go first (IE
210  // LN_beginning), so we won't be in this function. For assumes, we will end
211  // up here, beause we need to order the def we will place relative to the
212  // assume. So for the purpose of ordering, we pretend the def is the assume
213  // because that is where we will insert the info.
214  if (!VD.U) {
215  assert(VD.PInfo &&
216  "No def, no use, and no predicateinfo should not occur");
217  assert(isa<PredicateAssume>(VD.PInfo) &&
218  "Middle of block should only occur for assumes");
219  return cast<PredicateAssume>(VD.PInfo)->AssumeInst;
220  }
221  return nullptr;
222  }
223 
224  // Return either the Def, if it's not null, or the user of the Use, if the def
225  // is null.
226  const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
227  if (Def)
228  return cast<Instruction>(Def);
229  return cast<Instruction>(U->getUser());
230  }
231 
232  // This performs the necessary local basic block ordering checks to tell
233  // whether A comes before B, where both are in the same basic block.
234  bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
235  auto *ADef = getMiddleDef(A);
236  auto *BDef = getMiddleDef(B);
237 
238  // See if we have real values or uses. If we have real values, we are
239  // guaranteed they are instructions or arguments. No matter what, we are
240  // guaranteed they are in the same block if they are instructions.
241  auto *ArgA = dyn_cast_or_null<Argument>(ADef);
242  auto *ArgB = dyn_cast_or_null<Argument>(BDef);
243 
244  if (ArgA || ArgB)
245  return valueComesBefore(OI, ArgA, ArgB);
246 
247  auto *AInst = getDefOrUser(ADef, A.U);
248  auto *BInst = getDefOrUser(BDef, B.U);
249  return valueComesBefore(OI, AInst, BInst);
250  }
251 };
252 
253 } // namespace PredicateInfoClasses
254 
255 bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack,
256  const ValueDFS &VDUse) const {
257  if (Stack.empty())
258  return false;
259  // If it's a phi only use, make sure it's for this phi node edge, and that the
260  // use is in a phi node. If it's anything else, and the top of the stack is
261  // EdgeOnly, we need to pop the stack. We deliberately sort phi uses next to
262  // the defs they must go with so that we can know it's time to pop the stack
263  // when we hit the end of the phi uses for a given def.
264  if (Stack.back().EdgeOnly) {
265  if (!VDUse.U)
266  return false;
267  auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
268  if (!PHI)
269  return false;
270  // Check edge
271  BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
272  if (EdgePred != getBranchBlock(Stack.back().PInfo))
273  return false;
274 
275  // Use dominates, which knows how to handle edge dominance.
276  return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
277  }
278 
279  return (VDUse.DFSIn >= Stack.back().DFSIn &&
280  VDUse.DFSOut <= Stack.back().DFSOut);
281 }
282 
283 void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack,
284  const ValueDFS &VD) {
285  while (!Stack.empty() && !stackIsInScope(Stack, VD))
286  Stack.pop_back();
287 }
288 
289 // Convert the uses of Op into a vector of uses, associating global and local
290 // DFS info with each one.
291 void PredicateInfo::convertUsesToDFSOrdered(
292  Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
293  for (auto &U : Op->uses()) {
294  if (auto *I = dyn_cast<Instruction>(U.getUser())) {
295  ValueDFS VD;
296  // Put the phi node uses in the incoming block.
297  BasicBlock *IBlock;
298  if (auto *PN = dyn_cast<PHINode>(I)) {
299  IBlock = PN->getIncomingBlock(U);
300  // Make phi node users appear last in the incoming block
301  // they are from.
302  VD.LocalNum = LN_Last;
303  } else {
304  // If it's not a phi node use, it is somewhere in the middle of the
305  // block.
306  IBlock = I->getParent();
307  VD.LocalNum = LN_Middle;
308  }
309  DomTreeNode *DomNode = DT.getNode(IBlock);
310  // It's possible our use is in an unreachable block. Skip it if so.
311  if (!DomNode)
312  continue;
313  VD.DFSIn = DomNode->getDFSNumIn();
314  VD.DFSOut = DomNode->getDFSNumOut();
315  VD.U = &U;
316  DFSOrderedSet.push_back(VD);
317  }
318  }
319 }
320 
321 // Collect relevant operations from Comparison that we may want to insert copies
322 // for.
323 void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
324  auto *Op0 = Comparison->getOperand(0);
325  auto *Op1 = Comparison->getOperand(1);
326  if (Op0 == Op1)
327  return;
328  CmpOperands.push_back(Comparison);
329  // Only want real values, not constants. Additionally, operands with one use
330  // are only being used in the comparison, which means they will not be useful
331  // for us to consider for predicateinfo.
332  //
333  if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse())
334  CmpOperands.push_back(Op0);
335  if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse())
336  CmpOperands.push_back(Op1);
337 }
338 
339 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
340 void PredicateInfo::addInfoFor(SmallVectorImpl<Value *> &OpsToRename, Value *Op,
341  PredicateBase *PB) {
342  auto &OperandInfo = getOrCreateValueInfo(Op);
343  if (OperandInfo.Infos.empty())
344  OpsToRename.push_back(Op);
345  AllInfos.push_back(PB);
346  OperandInfo.Infos.push_back(PB);
347 }
348 
349 // Process an assume instruction and place relevant operations we want to rename
350 // into OpsToRename.
351 void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
352  SmallVectorImpl<Value *> &OpsToRename) {
353  // See if we have a comparison we support
354  SmallVector<Value *, 8> CmpOperands;
355  SmallVector<Value *, 2> ConditionsToProcess;
356  CmpInst::Predicate Pred;
357  Value *Operand = II->getOperand(0);
358  if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
359  m_Cmp(Pred, m_Value(), m_Value()))
360  .match(II->getOperand(0))) {
361  ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0));
362  ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1));
363  ConditionsToProcess.push_back(Operand);
364  } else if (isa<CmpInst>(Operand)) {
365 
366  ConditionsToProcess.push_back(Operand);
367  }
368  for (auto Cond : ConditionsToProcess) {
369  if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
370  collectCmpOps(Cmp, CmpOperands);
371  // Now add our copy infos for our operands
372  for (auto *Op : CmpOperands) {
373  auto *PA = new PredicateAssume(Op, II, Cmp);
374  addInfoFor(OpsToRename, Op, PA);
375  }
376  CmpOperands.clear();
377  } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
378  // Otherwise, it should be an AND.
379  assert(BinOp->getOpcode() == Instruction::And &&
380  "Should have been an AND");
381  auto *PA = new PredicateAssume(BinOp, II, BinOp);
382  addInfoFor(OpsToRename, BinOp, PA);
383  } else {
384  llvm_unreachable("Unknown type of condition");
385  }
386  }
387 }
388 
389 // Process a block terminating branch, and place relevant operations to be
390 // renamed into OpsToRename.
391 void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
392  SmallVectorImpl<Value *> &OpsToRename) {
393  BasicBlock *FirstBB = BI->getSuccessor(0);
394  BasicBlock *SecondBB = BI->getSuccessor(1);
395  SmallVector<BasicBlock *, 2> SuccsToProcess;
396  SuccsToProcess.push_back(FirstBB);
397  SuccsToProcess.push_back(SecondBB);
398  SmallVector<Value *, 2> ConditionsToProcess;
399 
400  auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) {
401  for (auto *Succ : SuccsToProcess) {
402  // Don't try to insert on a self-edge. This is mainly because we will
403  // eliminate during renaming anyway.
404  if (Succ == BranchBB)
405  continue;
406  bool TakenEdge = (Succ == FirstBB);
407  // For and, only insert on the true edge
408  // For or, only insert on the false edge
409  if ((isAnd && !TakenEdge) || (isOr && TakenEdge))
410  continue;
411  PredicateBase *PB =
412  new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge);
413  addInfoFor(OpsToRename, Op, PB);
414  if (!Succ->getSinglePredecessor())
415  EdgeUsesOnly.insert({BranchBB, Succ});
416  }
417  };
418 
419  // Match combinations of conditions.
420  CmpInst::Predicate Pred;
421  bool isAnd = false;
422  bool isOr = false;
423  SmallVector<Value *, 8> CmpOperands;
424  if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
425  m_Cmp(Pred, m_Value(), m_Value()))) ||
426  match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
427  m_Cmp(Pred, m_Value(), m_Value())))) {
428  auto *BinOp = cast<BinaryOperator>(BI->getCondition());
429  if (BinOp->getOpcode() == Instruction::And)
430  isAnd = true;
431  else if (BinOp->getOpcode() == Instruction::Or)
432  isOr = true;
433  ConditionsToProcess.push_back(BinOp->getOperand(0));
434  ConditionsToProcess.push_back(BinOp->getOperand(1));
435  ConditionsToProcess.push_back(BI->getCondition());
436  } else if (isa<CmpInst>(BI->getCondition())) {
437  ConditionsToProcess.push_back(BI->getCondition());
438  }
439  for (auto Cond : ConditionsToProcess) {
440  if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
441  collectCmpOps(Cmp, CmpOperands);
442  // Now add our copy infos for our operands
443  for (auto *Op : CmpOperands)
444  InsertHelper(Op, isAnd, isOr, Cmp);
445  } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
446  // This must be an AND or an OR.
447  assert((BinOp->getOpcode() == Instruction::And ||
448  BinOp->getOpcode() == Instruction::Or) &&
449  "Should have been an AND or an OR");
450  // The actual value of the binop is not subject to the same restrictions
451  // as the comparison. It's either true or false on the true/false branch.
452  InsertHelper(BinOp, false, false, BinOp);
453  } else {
454  llvm_unreachable("Unknown type of condition");
455  }
456  CmpOperands.clear();
457  }
458 }
459 // Process a block terminating switch, and place relevant operations to be
460 // renamed into OpsToRename.
461 void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB,
462  SmallVectorImpl<Value *> &OpsToRename) {
463  Value *Op = SI->getCondition();
464  if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
465  return;
466 
467  // Remember how many outgoing edges there are to every successor.
469  for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
470  BasicBlock *TargetBlock = SI->getSuccessor(i);
471  ++SwitchEdges[TargetBlock];
472  }
473 
474  // Now propagate info for each case value
475  for (auto C : SI->cases()) {
476  BasicBlock *TargetBlock = C.getCaseSuccessor();
477  if (SwitchEdges.lookup(TargetBlock) == 1) {
479  Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
480  addInfoFor(OpsToRename, Op, PS);
481  if (!TargetBlock->getSinglePredecessor())
482  EdgeUsesOnly.insert({BranchBB, TargetBlock});
483  }
484  }
485 }
486 
487 // Build predicate info for our function
488 void PredicateInfo::buildPredicateInfo() {
489  DT.updateDFSNumbers();
490  // Collect operands to rename from all conditional branch terminators, as well
491  // as assume statements.
492  SmallVector<Value *, 8> OpsToRename;
493  for (auto DTN : depth_first(DT.getRootNode())) {
494  BasicBlock *BranchBB = DTN->getBlock();
495  if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
496  if (!BI->isConditional())
497  continue;
498  // Can't insert conditional information if they all go to the same place.
499  if (BI->getSuccessor(0) == BI->getSuccessor(1))
500  continue;
501  processBranch(BI, BranchBB, OpsToRename);
502  } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
503  processSwitch(SI, BranchBB, OpsToRename);
504  }
505  }
506  for (auto &Assume : AC.assumptions()) {
507  if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
508  if (DT.isReachableFromEntry(II->getParent()))
509  processAssume(II, II->getParent(), OpsToRename);
510  }
511  // Now rename all our operations.
512  renameUses(OpsToRename);
513 }
514 
515 // Create a ssa_copy declaration with custom mangling, because
516 // Intrinsic::getDeclaration does not handle overloaded unnamed types properly:
517 // all unnamed types get mangled to the same string. We use the pointer
518 // to the type as name here, as it guarantees unique names for different
519 // types and we remove the declarations when destroying PredicateInfo.
520 // It is a workaround for PR38117, because solving it in a fully general way is
521 // tricky (FIXME).
523  std::string Name = "llvm.ssa.copy." + utostr((uintptr_t) Ty);
524  return cast<Function>(
525  M->getOrInsertFunction(Name,
526  getType(M->getContext(), Intrinsic::ssa_copy, Ty))
527  .getCallee());
528 }
529 
530 // Given the renaming stack, make all the operands currently on the stack real
531 // by inserting them into the IR. Return the last operation's value.
532 Value *PredicateInfo::materializeStack(unsigned int &Counter,
533  ValueDFSStack &RenameStack,
534  Value *OrigOp) {
535  // Find the first thing we have to materialize
536  auto RevIter = RenameStack.rbegin();
537  for (; RevIter != RenameStack.rend(); ++RevIter)
538  if (RevIter->Def)
539  break;
540 
541  size_t Start = RevIter - RenameStack.rbegin();
542  // The maximum number of things we should be trying to materialize at once
543  // right now is 4, depending on if we had an assume, a branch, and both used
544  // and of conditions.
545  for (auto RenameIter = RenameStack.end() - Start;
546  RenameIter != RenameStack.end(); ++RenameIter) {
547  auto *Op =
548  RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
549  ValueDFS &Result = *RenameIter;
550  auto *ValInfo = Result.PInfo;
551  // For edge predicates, we can just place the operand in the block before
552  // the terminator. For assume, we have to place it right before the assume
553  // to ensure we dominate all of our uses. Always insert right before the
554  // relevant instruction (terminator, assume), so that we insert in proper
555  // order in the case of multiple predicateinfo in the same block.
556  if (isa<PredicateWithEdge>(ValInfo)) {
557  IRBuilder<> B(getBranchTerminator(ValInfo));
558  Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
559  if (empty(IF->users()))
560  CreatedDeclarations.insert(IF);
561  CallInst *PIC =
562  B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
563  PredicateMap.insert({PIC, ValInfo});
564  Result.Def = PIC;
565  } else {
566  auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
567  assert(PAssume &&
568  "Should not have gotten here without it being an assume");
569  IRBuilder<> B(PAssume->AssumeInst);
570  Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
571  if (empty(IF->users()))
572  CreatedDeclarations.insert(IF);
573  CallInst *PIC = B.CreateCall(IF, Op);
574  PredicateMap.insert({PIC, ValInfo});
575  Result.Def = PIC;
576  }
577  }
578  return RenameStack.back().Def;
579 }
580 
581 // Instead of the standard SSA renaming algorithm, which is O(Number of
582 // instructions), and walks the entire dominator tree, we walk only the defs +
583 // uses. The standard SSA renaming algorithm does not really rely on the
584 // dominator tree except to order the stack push/pops of the renaming stacks, so
585 // that defs end up getting pushed before hitting the correct uses. This does
586 // not require the dominator tree, only the *order* of the dominator tree. The
587 // complete and correct ordering of the defs and uses, in dominator tree is
588 // contained in the DFS numbering of the dominator tree. So we sort the defs and
589 // uses into the DFS ordering, and then just use the renaming stack as per
590 // normal, pushing when we hit a def (which is a predicateinfo instruction),
591 // popping when we are out of the dfs scope for that def, and replacing any uses
592 // with top of stack if it exists. In order to handle liveness without
593 // propagating liveness info, we don't actually insert the predicateinfo
594 // instruction def until we see a use that it would dominate. Once we see such
595 // a use, we materialize the predicateinfo instruction in the right place and
596 // use it.
597 //
598 // TODO: Use this algorithm to perform fast single-variable renaming in
599 // promotememtoreg and memoryssa.
600 void PredicateInfo::renameUses(SmallVectorImpl<Value *> &OpsToRename) {
601  ValueDFS_Compare Compare(DT, OI);
602  // Compute liveness, and rename in O(uses) per Op.
603  for (auto *Op : OpsToRename) {
604  LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
605  unsigned Counter = 0;
606  SmallVector<ValueDFS, 16> OrderedUses;
607  const auto &ValueInfo = getValueInfo(Op);
608  // Insert the possible copies into the def/use list.
609  // They will become real copies if we find a real use for them, and never
610  // created otherwise.
611  for (auto &PossibleCopy : ValueInfo.Infos) {
612  ValueDFS VD;
613  // Determine where we are going to place the copy by the copy type.
614  // The predicate info for branches always come first, they will get
615  // materialized in the split block at the top of the block.
616  // The predicate info for assumes will be somewhere in the middle,
617  // it will get materialized in front of the assume.
618  if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
619  VD.LocalNum = LN_Middle;
620  DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
621  if (!DomNode)
622  continue;
623  VD.DFSIn = DomNode->getDFSNumIn();
624  VD.DFSOut = DomNode->getDFSNumOut();
625  VD.PInfo = PossibleCopy;
626  OrderedUses.push_back(VD);
627  } else if (isa<PredicateWithEdge>(PossibleCopy)) {
628  // If we can only do phi uses, we treat it like it's in the branch
629  // block, and handle it specially. We know that it goes last, and only
630  // dominate phi uses.
631  auto BlockEdge = getBlockEdge(PossibleCopy);
632  if (EdgeUsesOnly.count(BlockEdge)) {
633  VD.LocalNum = LN_Last;
634  auto *DomNode = DT.getNode(BlockEdge.first);
635  if (DomNode) {
636  VD.DFSIn = DomNode->getDFSNumIn();
637  VD.DFSOut = DomNode->getDFSNumOut();
638  VD.PInfo = PossibleCopy;
639  VD.EdgeOnly = true;
640  OrderedUses.push_back(VD);
641  }
642  } else {
643  // Otherwise, we are in the split block (even though we perform
644  // insertion in the branch block).
645  // Insert a possible copy at the split block and before the branch.
646  VD.LocalNum = LN_First;
647  auto *DomNode = DT.getNode(BlockEdge.second);
648  if (DomNode) {
649  VD.DFSIn = DomNode->getDFSNumIn();
650  VD.DFSOut = DomNode->getDFSNumOut();
651  VD.PInfo = PossibleCopy;
652  OrderedUses.push_back(VD);
653  }
654  }
655  }
656  }
657 
658  convertUsesToDFSOrdered(Op, OrderedUses);
659  // Here we require a stable sort because we do not bother to try to
660  // assign an order to the operands the uses represent. Thus, two
661  // uses in the same instruction do not have a strict sort order
662  // currently and will be considered equal. We could get rid of the
663  // stable sort by creating one if we wanted.
664  llvm::stable_sort(OrderedUses, Compare);
665  SmallVector<ValueDFS, 8> RenameStack;
666  // For each use, sorted into dfs order, push values and replaces uses with
667  // top of stack, which will represent the reaching def.
668  for (auto &VD : OrderedUses) {
669  // We currently do not materialize copy over copy, but we should decide if
670  // we want to.
671  bool PossibleCopy = VD.PInfo != nullptr;
672  if (RenameStack.empty()) {
673  LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
674  } else {
675  LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
676  << RenameStack.back().DFSIn << ","
677  << RenameStack.back().DFSOut << ")\n");
678  }
679 
680  LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
681  << VD.DFSOut << ")\n");
682 
683  bool ShouldPush = (VD.Def || PossibleCopy);
684  bool OutOfScope = !stackIsInScope(RenameStack, VD);
685  if (OutOfScope || ShouldPush) {
686  // Sync to our current scope.
687  popStackUntilDFSScope(RenameStack, VD);
688  if (ShouldPush) {
689  RenameStack.push_back(VD);
690  }
691  }
692  // If we get to this point, and the stack is empty we must have a use
693  // with no renaming needed, just skip it.
694  if (RenameStack.empty())
695  continue;
696  // Skip values, only want to rename the uses
697  if (VD.Def || PossibleCopy)
698  continue;
699  if (!DebugCounter::shouldExecute(RenameCounter)) {
700  LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
701  continue;
702  }
703  ValueDFS &Result = RenameStack.back();
704 
705  // If the possible copy dominates something, materialize our stack up to
706  // this point. This ensures every comparison that affects our operation
707  // ends up with predicateinfo.
708  if (!Result.Def)
709  Result.Def = materializeStack(Counter, RenameStack, Op);
710 
711  LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
712  << *VD.U->get() << " in " << *(VD.U->getUser())
713  << "\n");
714  assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
715  "Predicateinfo def should have dominated this use");
716  VD.U->set(Result.Def);
717  }
718  }
719 }
720 
721 PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
722  auto OIN = ValueInfoNums.find(Operand);
723  if (OIN == ValueInfoNums.end()) {
724  // This will grow it
725  ValueInfos.resize(ValueInfos.size() + 1);
726  // This will use the new size and give us a 0 based number of the info
727  auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
728  assert(InsertResult.second && "Value info number already existed?");
729  return ValueInfos[InsertResult.first->second];
730  }
731  return ValueInfos[OIN->second];
732 }
733 
734 const PredicateInfo::ValueInfo &
735 PredicateInfo::getValueInfo(Value *Operand) const {
736  auto OINI = ValueInfoNums.lookup(Operand);
737  assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
738  assert(OINI < ValueInfos.size() &&
739  "Value Info Number greater than size of Value Info Table");
740  return ValueInfos[OINI];
741 }
742 
744  AssumptionCache &AC)
745  : F(F), DT(DT), AC(AC), OI(&DT) {
746  // Push an empty operand info so that we can detect 0 as not finding one
747  ValueInfos.resize(1);
748  buildPredicateInfo();
749 }
750 
751 // Remove all declarations we created . The PredicateInfo consumers are
752 // responsible for remove the ssa_copy calls created.
754  // Collect function pointers in set first, as SmallSet uses a SmallVector
755  // internally and we have to remove the asserting value handles first.
756  SmallPtrSet<Function *, 20> FunctionPtrs;
757  for (auto &F : CreatedDeclarations)
758  FunctionPtrs.insert(&*F);
759  CreatedDeclarations.clear();
760 
761  for (Function *F : FunctionPtrs) {
762  assert(F->user_begin() == F->user_end() &&
763  "PredicateInfo consumer did not remove all SSA copies.");
764  F->eraseFromParent();
765  }
766 }
767 
769 
771 
773  : FunctionPass(ID) {
776 }
777 
779  AU.setPreservesAll();
782 }
783 
784 // Replace ssa_copy calls created by PredicateInfo with their operand.
785 static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
786  for (auto I = inst_begin(F), E = inst_end(F); I != E;) {
787  Instruction *Inst = &*I++;
788  const auto *PI = PredInfo.getPredicateInfoFor(Inst);
789  auto *II = dyn_cast<IntrinsicInst>(Inst);
790  if (!PI || !II || II->getIntrinsicID() != Intrinsic::ssa_copy)
791  continue;
792 
793  Inst->replaceAllUsesWith(II->getOperand(0));
794  Inst->eraseFromParent();
795  }
796 }
797 
799  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
800  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
801  auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
802  PredInfo->print(dbgs());
804  PredInfo->verifyPredicateInfo();
805 
806  replaceCreatedSSACopys(*PredInfo, F);
807  return false;
808 }
809 
812  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
813  auto &AC = AM.getResult<AssumptionAnalysis>(F);
814  OS << "PredicateInfo for function: " << F.getName() << "\n";
815  auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
816  PredInfo->print(OS);
817 
818  replaceCreatedSSACopys(*PredInfo, F);
819  return PreservedAnalyses::all();
820 }
821 
822 /// An assembly annotator class to print PredicateInfo information in
823 /// comments.
825  friend class PredicateInfo;
826  const PredicateInfo *PredInfo;
827 
828 public:
829  PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
830 
831  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
832  formatted_raw_ostream &OS) {}
833 
834  virtual void emitInstructionAnnot(const Instruction *I,
835  formatted_raw_ostream &OS) {
836  if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
837  OS << "; Has predicate info\n";
838  if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
839  OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
840  << " Comparison:" << *PB->Condition << " Edge: [";
841  PB->From->printAsOperand(OS);
842  OS << ",";
843  PB->To->printAsOperand(OS);
844  OS << "] }\n";
845  } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
846  OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
847  << " Switch:" << *PS->Switch << " Edge: [";
848  PS->From->printAsOperand(OS);
849  OS << ",";
850  PS->To->printAsOperand(OS);
851  OS << "] }\n";
852  } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
853  OS << "; assume predicate info {"
854  << " Comparison:" << *PA->Condition << " }\n";
855  }
856  }
857  }
858 };
859 
861  PredicateInfoAnnotatedWriter Writer(this);
862  F.print(OS, &Writer);
863 }
864 
865 void PredicateInfo::dump() const {
866  PredicateInfoAnnotatedWriter Writer(this);
867  F.print(dbgs(), &Writer);
868 }
869 
872  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
873  auto &AC = AM.getResult<AssumptionAnalysis>(F);
874  std::make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
875 
876  return PreservedAnalyses::all();
877 }
878 }
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:831
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
iterator_range< use_iterator > uses()
Definition: Value.h:374
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:78
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
bool operator()(const ValueDFS &A, const ValueDFS &B) const
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static Function * getCopyDeclaration(Module *M, Type *Ty)
void verifyPredicateInfo() const
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
Value * getCondition() const
void collectCmpOps(CmpInst *Comparison, SmallVectorImpl< Value *> &CmpOperands)
A cache of @llvm.assume calls within a function.
const std::pair< BasicBlock *, BasicBlock * > getBlockEdge(const ValueDFS &VD) const
BasicBlock * getSuccessor(unsigned i) const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
virtual void emitBasicBlockStartAnnot(const BasicBlock *BB, formatted_raw_ostream &OS)
emitBasicBlockStartAnnot - This may be implemented to emit a string right after the basic block label...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static bool valueComesBefore(OrderedInstructions &OI, const Value *A, const Value *B)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
ValueDFS_Compare(DominatorTree &DT, OrderedInstructions &OI)
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:131
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
This file provides an implementation of debug counters.
PredicateInfoAnnotatedWriter(const PredicateInfo *M)
void initializePredicateInfoPrinterLegacyPassPass(PassRegistry &)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
ppc ctr loops PowerPC CTR Loops Verify
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
print PredicateInfo static false cl::opt< bool > VerifyPredicateInfo("verify-predicateinfo", cl::init(false), cl::Hidden, cl::desc("Verify PredicateInfo in legacy printer pass."))
unsigned getNumSuccessors() const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
BasicBlock * getSuccessor(unsigned idx) const
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const
bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
print predicateinfo
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:837
Conditional or Unconditional Branch instruction.
INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo", "PredicateInfo Printer", false, false) INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Represent the analysis usage information of a pass.
bool dfsBefore(const Instruction *, const Instruction *) const
Return true if the first instruction comes before the second in the dominator tree DFS traversal if t...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
unsigned getDFSNumOut() const
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:73
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
static wasm::ValType getType(const TargetRegisterClass *RC)
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
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.
Struct that holds a reference to a particular GUID in a global value summary.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:50
A function analysis which provides an AssumptionCache.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
Module.h This file contains the declarations for the Module class.
modulo schedule Modulo Schedule test pass
bool isConditional() const
FunctionCallee getOrInsertFunction(StringRef Name, FunctionType *T, AttributeList AttributeList)
Look up the specified function in the module symbol table.
Definition: Module.cpp:143
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:223
static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Encapsulates PredicateInfo, including all data associated with memory accesses.
const PredicateBase * getPredicateInfoFor(const Value *V) const
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:419
print PredicateInfo Printer
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
static void rename(GlobalValue *GV)
Definition: AutoUpgrade.cpp:33
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2237
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Function.cpp:226
An assembly annotator class to print PredicateInfo information in comments.
AnalysisUsage & addRequiredTransitive()
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:185
iterator_range< df_iterator< T > > depth_first(const T &G)
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:395
void stable_sort(R &&Range)
Definition: STLExtras.h:1289
LLVM Value Representation.
Definition: Value.h:73
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:432
hexagon cext opt
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:132
A container for analyses that lazily runs them and caches their results.
void print(raw_ostream &) const
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DEBUG_COUNTER(RenameCounter, "predicateinfo-rename", "Controls which variables are renamed with predicateinfo")
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Value * getMiddleDef(const ValueDFS &VD) const
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66
const Instruction * getDefOrUser(const Value *Def, const Use *U) const
virtual void emitInstructionAnnot(const Instruction *I, formatted_raw_ostream &OS)
emitInstructionAnnot - This may be implemented to emit a string right before an instruction is emitte...
void resize(size_type N)
Definition: SmallVector.h:344
user_iterator user_end()
Definition: Value.h:403