LLVM  13.0.0git
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"
20 #include "llvm/Analysis/CFG.h"
22 #include "llvm/IR/DataLayout.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/GlobalVariable.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/LLVMContext.h"
28 #include "llvm/IR/Metadata.h"
29 #include "llvm/IR/Module.h"
30 #include "llvm/IR/PatternMatch.h"
31 #include "llvm/InitializePasses.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 
43  "PredicateInfo Printer", false, false)
48 static cl::opt<bool> VerifyPredicateInfo(
49  "verify-predicateinfo", cl::init(false), cl::Hidden,
50  cl::desc("Verify PredicateInfo in legacy printer pass."));
51 DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
52  "Controls which variables are renamed with predicateinfo");
53 
54 // Maximum number of conditions considered for renaming for each branch/assume.
55 // This limits renaming of deep and/or chains.
56 static const unsigned MaxCondsPerBranch = 8;
57 
58 namespace {
59 // Given a predicate info that is a type of branching terminator, get the
60 // branching block.
61 const BasicBlock *getBranchBlock(const PredicateBase *PB) {
62  assert(isa<PredicateWithEdge>(PB) &&
63  "Only branches and switches should have PHIOnly defs that "
64  "require branch blocks.");
65  return cast<PredicateWithEdge>(PB)->From;
66 }
67 
68 // Given a predicate info that is a type of branching terminator, get the
69 // branching terminator.
70 static Instruction *getBranchTerminator(const PredicateBase *PB) {
71  assert(isa<PredicateWithEdge>(PB) &&
72  "Not a predicate info type we know how to get a terminator from.");
73  return cast<PredicateWithEdge>(PB)->From->getTerminator();
74 }
75 
76 // Given a predicate info that is a type of branching terminator, get the
77 // edge this predicate info represents
78 std::pair<BasicBlock *, BasicBlock *> getBlockEdge(const PredicateBase *PB) {
79  assert(isa<PredicateWithEdge>(PB) &&
80  "Not a predicate info type we know how to get an edge from.");
81  const auto *PEdge = cast<PredicateWithEdge>(PB);
82  return std::make_pair(PEdge->From, PEdge->To);
83 }
84 }
85 
86 namespace llvm {
87 enum LocalNum {
88  // Operations that must appear first in the block.
90  // Operations that are somewhere in the middle of the block, and are sorted on
91  // demand.
93  // Operations that must appear last in a block, like successor phi node uses.
95 };
96 
97 // Associate global and local DFS info with defs and uses, so we can sort them
98 // into a global domination ordering.
99 struct ValueDFS {
100  int DFSIn = 0;
101  int DFSOut = 0;
102  unsigned int LocalNum = LN_Middle;
103  // Only one of Def or Use will be set.
104  Value *Def = nullptr;
105  Use *U = nullptr;
106  // Neither PInfo nor EdgeOnly participate in the ordering
107  PredicateBase *PInfo = nullptr;
108  bool EdgeOnly = false;
109 };
110 
111 // Perform a strict weak ordering on instructions and arguments.
112 static bool valueComesBefore(const Value *A, 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 cast<Instruction>(A)->comesBefore(cast<Instruction>(B));
122 }
123 
124 // This compares ValueDFS structures. Doing so allows us to walk the minimum
125 // number of instructions necessary to compute our def/use ordering.
129 
130  bool operator()(const ValueDFS &A, const ValueDFS &B) const {
131  if (&A == &B)
132  return false;
133  // The only case we can't directly compare them is when they in the same
134  // block, and both have localnum == middle. In that case, we have to use
135  // comesbefore to see what the real ordering is, because they are in the
136  // same basic block.
137 
138  assert((A.DFSIn != B.DFSIn || A.DFSOut == B.DFSOut) &&
139  "Equal DFS-in numbers imply equal out numbers");
140  bool SameBlock = A.DFSIn == B.DFSIn;
141 
142  // We want to put the def that will get used for a given set of phi uses,
143  // before those phi uses.
144  // So we sort by edge, then by def.
145  // Note that only phi nodes uses and defs can come last.
146  if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
147  return comparePHIRelated(A, B);
148 
149  bool isADef = A.Def;
150  bool isBDef = B.Def;
151  if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
152  return std::tie(A.DFSIn, A.LocalNum, isADef) <
153  std::tie(B.DFSIn, B.LocalNum, isBDef);
154  return localComesBefore(A, B);
155  }
156 
157  // For a phi use, or a non-materialized def, return the edge it represents.
158  std::pair<BasicBlock *, BasicBlock *> getBlockEdge(const ValueDFS &VD) const {
159  if (!VD.Def && VD.U) {
160  auto *PHI = cast<PHINode>(VD.U->getUser());
161  return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
162  }
163  // This is really a non-materialized def.
164  return ::getBlockEdge(VD.PInfo);
165  }
166 
167  // For two phi related values, return the ordering.
168  bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
169  BasicBlock *ASrc, *ADest, *BSrc, *BDest;
170  std::tie(ASrc, ADest) = getBlockEdge(A);
171  std::tie(BSrc, BDest) = getBlockEdge(B);
172 
173 #ifndef NDEBUG
174  // This function should only be used for values in the same BB, check that.
175  DomTreeNode *DomASrc = DT.getNode(ASrc);
176  DomTreeNode *DomBSrc = DT.getNode(BSrc);
177  assert(DomASrc->getDFSNumIn() == (unsigned)A.DFSIn &&
178  "DFS numbers for A should match the ones of the source block");
179  assert(DomBSrc->getDFSNumIn() == (unsigned)B.DFSIn &&
180  "DFS numbers for B should match the ones of the source block");
181  assert(A.DFSIn == B.DFSIn && "Values must be in the same block");
182 #endif
183  (void)ASrc;
184  (void)BSrc;
185 
186  // Use DFS numbers to compare destination blocks, to guarantee a
187  // deterministic order.
188  DomTreeNode *DomADest = DT.getNode(ADest);
189  DomTreeNode *DomBDest = DT.getNode(BDest);
190  unsigned AIn = DomADest->getDFSNumIn();
191  unsigned BIn = DomBDest->getDFSNumIn();
192  bool isADef = A.Def;
193  bool isBDef = B.Def;
194  assert((!A.Def || !A.U) && (!B.Def || !B.U) &&
195  "Def and U cannot be set at the same time");
196  // Now sort by edge destination and then defs before uses.
197  return std::tie(AIn, isADef) < std::tie(BIn, isBDef);
198  }
199 
200  // Get the definition of an instruction that occurs in the middle of a block.
201  Value *getMiddleDef(const ValueDFS &VD) const {
202  if (VD.Def)
203  return VD.Def;
204  // It's possible for the defs and uses to be null. For branches, the local
205  // numbering will say the placed predicaeinfos should go first (IE
206  // LN_beginning), so we won't be in this function. For assumes, we will end
207  // up here, beause we need to order the def we will place relative to the
208  // assume. So for the purpose of ordering, we pretend the def is right
209  // after the assume, because that is where we will insert the info.
210  if (!VD.U) {
211  assert(VD.PInfo &&
212  "No def, no use, and no predicateinfo should not occur");
213  assert(isa<PredicateAssume>(VD.PInfo) &&
214  "Middle of block should only occur for assumes");
215  return cast<PredicateAssume>(VD.PInfo)->AssumeInst->getNextNode();
216  }
217  return nullptr;
218  }
219 
220  // Return either the Def, if it's not null, or the user of the Use, if the def
221  // is null.
222  const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
223  if (Def)
224  return cast<Instruction>(Def);
225  return cast<Instruction>(U->getUser());
226  }
227 
228  // This performs the necessary local basic block ordering checks to tell
229  // whether A comes before B, where both are in the same basic block.
230  bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
231  auto *ADef = getMiddleDef(A);
232  auto *BDef = getMiddleDef(B);
233 
234  // See if we have real values or uses. If we have real values, we are
235  // guaranteed they are instructions or arguments. No matter what, we are
236  // guaranteed they are in the same block if they are instructions.
237  auto *ArgA = dyn_cast_or_null<Argument>(ADef);
238  auto *ArgB = dyn_cast_or_null<Argument>(BDef);
239 
240  if (ArgA || ArgB)
241  return valueComesBefore(ArgA, ArgB);
242 
243  auto *AInst = getDefOrUser(ADef, A.U);
244  auto *BInst = getDefOrUser(BDef, B.U);
245  return valueComesBefore(AInst, BInst);
246  }
247 };
248 
250  // Used to store information about each value we might rename.
251  struct ValueInfo {
253  };
254 
255  PredicateInfo &PI;
256  Function &F;
257  DominatorTree &DT;
258  AssumptionCache &AC;
259 
260  // This stores info about each operand or comparison result we make copies
261  // of. The real ValueInfos start at index 1, index 0 is unused so that we
262  // can more easily detect invalid indexing.
263  SmallVector<ValueInfo, 32> ValueInfos;
264 
265  // This gives the index into the ValueInfos array for a given Value. Because
266  // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell
267  // whether it returned a valid result.
268  DenseMap<Value *, unsigned int> ValueInfoNums;
269 
270  // The set of edges along which we can only handle phi uses, due to critical
271  // edges.
273 
274  ValueInfo &getOrCreateValueInfo(Value *);
275  const ValueInfo &getValueInfo(Value *) const;
276 
277  void processAssume(IntrinsicInst *, BasicBlock *,
278  SmallVectorImpl<Value *> &OpsToRename);
279  void processBranch(BranchInst *, BasicBlock *,
280  SmallVectorImpl<Value *> &OpsToRename);
282  SmallVectorImpl<Value *> &OpsToRename);
283  void renameUses(SmallVectorImpl<Value *> &OpsToRename);
284  void addInfoFor(SmallVectorImpl<Value *> &OpsToRename, Value *Op,
285  PredicateBase *PB);
286 
288  void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
289  Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);
290  bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;
291  void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);
292 
293 public:
295  AssumptionCache &AC)
296  : PI(PI), F(F), DT(DT), AC(AC) {
297  // Push an empty operand info so that we can detect 0 as not finding one
298  ValueInfos.resize(1);
299  }
300 
301  void buildPredicateInfo();
302 };
303 
304 bool PredicateInfoBuilder::stackIsInScope(const ValueDFSStack &Stack,
305  const ValueDFS &VDUse) const {
306  if (Stack.empty())
307  return false;
308  // If it's a phi only use, make sure it's for this phi node edge, and that the
309  // use is in a phi node. If it's anything else, and the top of the stack is
310  // EdgeOnly, we need to pop the stack. We deliberately sort phi uses next to
311  // the defs they must go with so that we can know it's time to pop the stack
312  // when we hit the end of the phi uses for a given def.
313  if (Stack.back().EdgeOnly) {
314  if (!VDUse.U)
315  return false;
316  auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
317  if (!PHI)
318  return false;
319  // Check edge
320  BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
321  if (EdgePred != getBranchBlock(Stack.back().PInfo))
322  return false;
323 
324  // Use dominates, which knows how to handle edge dominance.
325  return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
326  }
327 
328  return (VDUse.DFSIn >= Stack.back().DFSIn &&
329  VDUse.DFSOut <= Stack.back().DFSOut);
330 }
331 
332 void PredicateInfoBuilder::popStackUntilDFSScope(ValueDFSStack &Stack,
333  const ValueDFS &VD) {
334  while (!Stack.empty() && !stackIsInScope(Stack, VD))
335  Stack.pop_back();
336 }
337 
338 // Convert the uses of Op into a vector of uses, associating global and local
339 // DFS info with each one.
340 void PredicateInfoBuilder::convertUsesToDFSOrdered(
341  Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
342  for (auto &U : Op->uses()) {
343  if (auto *I = dyn_cast<Instruction>(U.getUser())) {
344  ValueDFS VD;
345  // Put the phi node uses in the incoming block.
346  BasicBlock *IBlock;
347  if (auto *PN = dyn_cast<PHINode>(I)) {
348  IBlock = PN->getIncomingBlock(U);
349  // Make phi node users appear last in the incoming block
350  // they are from.
351  VD.LocalNum = LN_Last;
352  } else {
353  // If it's not a phi node use, it is somewhere in the middle of the
354  // block.
355  IBlock = I->getParent();
356  VD.LocalNum = LN_Middle;
357  }
358  DomTreeNode *DomNode = DT.getNode(IBlock);
359  // It's possible our use is in an unreachable block. Skip it if so.
360  if (!DomNode)
361  continue;
362  VD.DFSIn = DomNode->getDFSNumIn();
363  VD.DFSOut = DomNode->getDFSNumOut();
364  VD.U = &U;
365  DFSOrderedSet.push_back(VD);
366  }
367  }
368 }
369 
370 bool shouldRename(Value *V) {
371  // Only want real values, not constants. Additionally, operands with one use
372  // are only being used in the comparison, which means they will not be useful
373  // for us to consider for predicateinfo.
374  return (isa<Instruction>(V) || isa<Argument>(V)) && !V->hasOneUse();
375 }
376 
377 // Collect relevant operations from Comparison that we may want to insert copies
378 // for.
379 void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
380  auto *Op0 = Comparison->getOperand(0);
381  auto *Op1 = Comparison->getOperand(1);
382  if (Op0 == Op1)
383  return;
384 
385  CmpOperands.push_back(Op0);
386  CmpOperands.push_back(Op1);
387 }
388 
389 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
390 void PredicateInfoBuilder::addInfoFor(SmallVectorImpl<Value *> &OpsToRename,
391  Value *Op, PredicateBase *PB) {
392  auto &OperandInfo = getOrCreateValueInfo(Op);
393  if (OperandInfo.Infos.empty())
394  OpsToRename.push_back(Op);
395  PI.AllInfos.push_back(PB);
396  OperandInfo.Infos.push_back(PB);
397 }
398 
399 // Process an assume instruction and place relevant operations we want to rename
400 // into OpsToRename.
401 void PredicateInfoBuilder::processAssume(
402  IntrinsicInst *II, BasicBlock *AssumeBB,
403  SmallVectorImpl<Value *> &OpsToRename) {
404  SmallVector<Value *, 4> Worklist;
405  SmallPtrSet<Value *, 4> Visited;
406  Worklist.push_back(II->getOperand(0));
407  while (!Worklist.empty()) {
408  Value *Cond = Worklist.pop_back_val();
409  if (!Visited.insert(Cond).second)
410  continue;
411  if (Visited.size() > MaxCondsPerBranch)
412  break;
413 
414  Value *Op0, *Op1;
415  if (match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
416  Worklist.push_back(Op1);
417  Worklist.push_back(Op0);
418  }
419 
421  Values.push_back(Cond);
422  if (auto *Cmp = dyn_cast<CmpInst>(Cond))
423  collectCmpOps(Cmp, Values);
424 
425  for (Value *V : Values) {
426  if (shouldRename(V)) {
427  auto *PA = new PredicateAssume(V, II, Cond);
428  addInfoFor(OpsToRename, V, PA);
429  }
430  }
431  }
432 }
433 
434 // Process a block terminating branch, and place relevant operations to be
435 // renamed into OpsToRename.
436 void PredicateInfoBuilder::processBranch(
437  BranchInst *BI, BasicBlock *BranchBB,
438  SmallVectorImpl<Value *> &OpsToRename) {
439  BasicBlock *FirstBB = BI->getSuccessor(0);
440  BasicBlock *SecondBB = BI->getSuccessor(1);
441 
442  for (BasicBlock *Succ : {FirstBB, SecondBB}) {
443  bool TakenEdge = Succ == FirstBB;
444  // Don't try to insert on a self-edge. This is mainly because we will
445  // eliminate during renaming anyway.
446  if (Succ == BranchBB)
447  continue;
448 
449  SmallVector<Value *, 4> Worklist;
450  SmallPtrSet<Value *, 4> Visited;
451  Worklist.push_back(BI->getCondition());
452  while (!Worklist.empty()) {
453  Value *Cond = Worklist.pop_back_val();
454  if (!Visited.insert(Cond).second)
455  continue;
456  if (Visited.size() > MaxCondsPerBranch)
457  break;
458 
459  Value *Op0, *Op1;
460  if (TakenEdge ? match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))
461  : match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
462  Worklist.push_back(Op1);
463  Worklist.push_back(Op0);
464  }
465 
467  Values.push_back(Cond);
468  if (auto *Cmp = dyn_cast<CmpInst>(Cond))
469  collectCmpOps(Cmp, Values);
470 
471  for (Value *V : Values) {
472  if (shouldRename(V)) {
473  PredicateBase *PB =
474  new PredicateBranch(V, BranchBB, Succ, Cond, TakenEdge);
475  addInfoFor(OpsToRename, V, PB);
476  if (!Succ->getSinglePredecessor())
477  EdgeUsesOnly.insert({BranchBB, Succ});
478  }
479  }
480  }
481  }
482 }
483 // Process a block terminating switch, and place relevant operations to be
484 // renamed into OpsToRename.
485 void PredicateInfoBuilder::processSwitch(
486  SwitchInst *SI, BasicBlock *BranchBB,
487  SmallVectorImpl<Value *> &OpsToRename) {
488  Value *Op = SI->getCondition();
489  if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
490  return;
491 
492  // Remember how many outgoing edges there are to every successor.
494  for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
495  BasicBlock *TargetBlock = SI->getSuccessor(i);
496  ++SwitchEdges[TargetBlock];
497  }
498 
499  // Now propagate info for each case value
500  for (auto C : SI->cases()) {
501  BasicBlock *TargetBlock = C.getCaseSuccessor();
502  if (SwitchEdges.lookup(TargetBlock) == 1) {
504  Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
505  addInfoFor(OpsToRename, Op, PS);
506  if (!TargetBlock->getSinglePredecessor())
507  EdgeUsesOnly.insert({BranchBB, TargetBlock});
508  }
509  }
510 }
511 
512 // Build predicate info for our function
514  DT.updateDFSNumbers();
515  // Collect operands to rename from all conditional branch terminators, as well
516  // as assume statements.
517  SmallVector<Value *, 8> OpsToRename;
518  for (auto DTN : depth_first(DT.getRootNode())) {
519  BasicBlock *BranchBB = DTN->getBlock();
520  if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
521  if (!BI->isConditional())
522  continue;
523  // Can't insert conditional information if they all go to the same place.
524  if (BI->getSuccessor(0) == BI->getSuccessor(1))
525  continue;
526  processBranch(BI, BranchBB, OpsToRename);
527  } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
528  processSwitch(SI, BranchBB, OpsToRename);
529  }
530  }
531  for (auto &Assume : AC.assumptions()) {
532  if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
533  if (DT.isReachableFromEntry(II->getParent()))
534  processAssume(II, II->getParent(), OpsToRename);
535  }
536  // Now rename all our operations.
537  renameUses(OpsToRename);
538 }
539 
540 // Given the renaming stack, make all the operands currently on the stack real
541 // by inserting them into the IR. Return the last operation's value.
542 Value *PredicateInfoBuilder::materializeStack(unsigned int &Counter,
543  ValueDFSStack &RenameStack,
544  Value *OrigOp) {
545  // Find the first thing we have to materialize
546  auto RevIter = RenameStack.rbegin();
547  for (; RevIter != RenameStack.rend(); ++RevIter)
548  if (RevIter->Def)
549  break;
550 
551  size_t Start = RevIter - RenameStack.rbegin();
552  // The maximum number of things we should be trying to materialize at once
553  // right now is 4, depending on if we had an assume, a branch, and both used
554  // and of conditions.
555  for (auto RenameIter = RenameStack.end() - Start;
556  RenameIter != RenameStack.end(); ++RenameIter) {
557  auto *Op =
558  RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
559  ValueDFS &Result = *RenameIter;
560  auto *ValInfo = Result.PInfo;
561  ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
562  ? OrigOp
563  : (RenameStack.end() - Start - 1)->Def;
564  // For edge predicates, we can just place the operand in the block before
565  // the terminator. For assume, we have to place it right before the assume
566  // to ensure we dominate all of our uses. Always insert right before the
567  // relevant instruction (terminator, assume), so that we insert in proper
568  // order in the case of multiple predicateinfo in the same block.
569  if (isa<PredicateWithEdge>(ValInfo)) {
570  IRBuilder<> B(getBranchTerminator(ValInfo));
572  F.getParent(), Intrinsic::ssa_copy, Op->getType());
573  CallInst *PIC =
574  B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
575  PI.PredicateMap.insert({PIC, ValInfo});
576  Result.Def = PIC;
577  } else {
578  auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
579  assert(PAssume &&
580  "Should not have gotten here without it being an assume");
581  // Insert the predicate directly after the assume. While it also holds
582  // directly before it, assume(i1 true) is not a useful fact.
583  IRBuilder<> B(PAssume->AssumeInst->getNextNode());
585  F.getParent(), Intrinsic::ssa_copy, Op->getType());
586  CallInst *PIC = B.CreateCall(IF, Op);
587  PI.PredicateMap.insert({PIC, ValInfo});
588  Result.Def = PIC;
589  }
590  }
591  return RenameStack.back().Def;
592 }
593 
594 // Instead of the standard SSA renaming algorithm, which is O(Number of
595 // instructions), and walks the entire dominator tree, we walk only the defs +
596 // uses. The standard SSA renaming algorithm does not really rely on the
597 // dominator tree except to order the stack push/pops of the renaming stacks, so
598 // that defs end up getting pushed before hitting the correct uses. This does
599 // not require the dominator tree, only the *order* of the dominator tree. The
600 // complete and correct ordering of the defs and uses, in dominator tree is
601 // contained in the DFS numbering of the dominator tree. So we sort the defs and
602 // uses into the DFS ordering, and then just use the renaming stack as per
603 // normal, pushing when we hit a def (which is a predicateinfo instruction),
604 // popping when we are out of the dfs scope for that def, and replacing any uses
605 // with top of stack if it exists. In order to handle liveness without
606 // propagating liveness info, we don't actually insert the predicateinfo
607 // instruction def until we see a use that it would dominate. Once we see such
608 // a use, we materialize the predicateinfo instruction in the right place and
609 // use it.
610 //
611 // TODO: Use this algorithm to perform fast single-variable renaming in
612 // promotememtoreg and memoryssa.
613 void PredicateInfoBuilder::renameUses(SmallVectorImpl<Value *> &OpsToRename) {
615  // Compute liveness, and rename in O(uses) per Op.
616  for (auto *Op : OpsToRename) {
617  LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
618  unsigned Counter = 0;
619  SmallVector<ValueDFS, 16> OrderedUses;
620  const auto &ValueInfo = getValueInfo(Op);
621  // Insert the possible copies into the def/use list.
622  // They will become real copies if we find a real use for them, and never
623  // created otherwise.
624  for (auto &PossibleCopy : ValueInfo.Infos) {
625  ValueDFS VD;
626  // Determine where we are going to place the copy by the copy type.
627  // The predicate info for branches always come first, they will get
628  // materialized in the split block at the top of the block.
629  // The predicate info for assumes will be somewhere in the middle,
630  // it will get materialized in front of the assume.
631  if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
632  VD.LocalNum = LN_Middle;
633  DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
634  if (!DomNode)
635  continue;
636  VD.DFSIn = DomNode->getDFSNumIn();
637  VD.DFSOut = DomNode->getDFSNumOut();
638  VD.PInfo = PossibleCopy;
639  OrderedUses.push_back(VD);
640  } else if (isa<PredicateWithEdge>(PossibleCopy)) {
641  // If we can only do phi uses, we treat it like it's in the branch
642  // block, and handle it specially. We know that it goes last, and only
643  // dominate phi uses.
644  auto BlockEdge = getBlockEdge(PossibleCopy);
645  if (EdgeUsesOnly.count(BlockEdge)) {
646  VD.LocalNum = LN_Last;
647  auto *DomNode = DT.getNode(BlockEdge.first);
648  if (DomNode) {
649  VD.DFSIn = DomNode->getDFSNumIn();
650  VD.DFSOut = DomNode->getDFSNumOut();
651  VD.PInfo = PossibleCopy;
652  VD.EdgeOnly = true;
653  OrderedUses.push_back(VD);
654  }
655  } else {
656  // Otherwise, we are in the split block (even though we perform
657  // insertion in the branch block).
658  // Insert a possible copy at the split block and before the branch.
659  VD.LocalNum = LN_First;
660  auto *DomNode = DT.getNode(BlockEdge.second);
661  if (DomNode) {
662  VD.DFSIn = DomNode->getDFSNumIn();
663  VD.DFSOut = DomNode->getDFSNumOut();
664  VD.PInfo = PossibleCopy;
665  OrderedUses.push_back(VD);
666  }
667  }
668  }
669  }
670 
671  convertUsesToDFSOrdered(Op, OrderedUses);
672  // Here we require a stable sort because we do not bother to try to
673  // assign an order to the operands the uses represent. Thus, two
674  // uses in the same instruction do not have a strict sort order
675  // currently and will be considered equal. We could get rid of the
676  // stable sort by creating one if we wanted.
677  llvm::stable_sort(OrderedUses, Compare);
678  SmallVector<ValueDFS, 8> RenameStack;
679  // For each use, sorted into dfs order, push values and replaces uses with
680  // top of stack, which will represent the reaching def.
681  for (auto &VD : OrderedUses) {
682  // We currently do not materialize copy over copy, but we should decide if
683  // we want to.
684  bool PossibleCopy = VD.PInfo != nullptr;
685  if (RenameStack.empty()) {
686  LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
687  } else {
688  LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
689  << RenameStack.back().DFSIn << ","
690  << RenameStack.back().DFSOut << ")\n");
691  }
692 
693  LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
694  << VD.DFSOut << ")\n");
695 
696  bool ShouldPush = (VD.Def || PossibleCopy);
697  bool OutOfScope = !stackIsInScope(RenameStack, VD);
698  if (OutOfScope || ShouldPush) {
699  // Sync to our current scope.
700  popStackUntilDFSScope(RenameStack, VD);
701  if (ShouldPush) {
702  RenameStack.push_back(VD);
703  }
704  }
705  // If we get to this point, and the stack is empty we must have a use
706  // with no renaming needed, just skip it.
707  if (RenameStack.empty())
708  continue;
709  // Skip values, only want to rename the uses
710  if (VD.Def || PossibleCopy)
711  continue;
712  if (!DebugCounter::shouldExecute(RenameCounter)) {
713  LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
714  continue;
715  }
716  ValueDFS &Result = RenameStack.back();
717 
718  // If the possible copy dominates something, materialize our stack up to
719  // this point. This ensures every comparison that affects our operation
720  // ends up with predicateinfo.
721  if (!Result.Def)
722  Result.Def = materializeStack(Counter, RenameStack, Op);
723 
724  LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
725  << *VD.U->get() << " in " << *(VD.U->getUser())
726  << "\n");
727  assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
728  "Predicateinfo def should have dominated this use");
729  VD.U->set(Result.Def);
730  }
731  }
732 }
733 
734 PredicateInfoBuilder::ValueInfo &
735 PredicateInfoBuilder::getOrCreateValueInfo(Value *Operand) {
736  auto OIN = ValueInfoNums.find(Operand);
737  if (OIN == ValueInfoNums.end()) {
738  // This will grow it
739  ValueInfos.resize(ValueInfos.size() + 1);
740  // This will use the new size and give us a 0 based number of the info
741  auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
742  assert(InsertResult.second && "Value info number already existed?");
743  return ValueInfos[InsertResult.first->second];
744  }
745  return ValueInfos[OIN->second];
746 }
747 
748 const PredicateInfoBuilder::ValueInfo &
749 PredicateInfoBuilder::getValueInfo(Value *Operand) const {
750  auto OINI = ValueInfoNums.lookup(Operand);
751  assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
752  assert(OINI < ValueInfos.size() &&
753  "Value Info Number greater than size of Value Info Table");
754  return ValueInfos[OINI];
755 }
756 
758  AssumptionCache &AC)
759  : F(F) {
760  PredicateInfoBuilder Builder(*this, F, DT, AC);
761  Builder.buildPredicateInfo();
762 }
763 
765  switch (Type) {
766  case PT_Assume:
767  case PT_Branch: {
768  bool TrueEdge = true;
769  if (auto *PBranch = dyn_cast<PredicateBranch>(this))
770  TrueEdge = PBranch->TrueEdge;
771 
772  if (Condition == RenamedOp) {
773  return {{CmpInst::ICMP_EQ,
774  TrueEdge ? ConstantInt::getTrue(Condition->getType())
776  }
777 
778  CmpInst *Cmp = dyn_cast<CmpInst>(Condition);
779  if (!Cmp) {
780  // TODO: Make this an assertion once RenamedOp is fully accurate.
781  return None;
782  }
783 
784  CmpInst::Predicate Pred;
785  Value *OtherOp;
786  if (Cmp->getOperand(0) == RenamedOp) {
787  Pred = Cmp->getPredicate();
788  OtherOp = Cmp->getOperand(1);
789  } else if (Cmp->getOperand(1) == RenamedOp) {
790  Pred = Cmp->getSwappedPredicate();
791  OtherOp = Cmp->getOperand(0);
792  } else {
793  // TODO: Make this an assertion once RenamedOp is fully accurate.
794  return None;
795  }
796 
797  // Invert predicate along false edge.
798  if (!TrueEdge)
799  Pred = CmpInst::getInversePredicate(Pred);
800 
801  return {{Pred, OtherOp}};
802  }
803  case PT_Switch:
804  if (Condition != RenamedOp) {
805  // TODO: Make this an assertion once RenamedOp is fully accurate.
806  return None;
807  }
808 
809  return {{CmpInst::ICMP_EQ, cast<PredicateSwitch>(this)->CaseValue}};
810  }
811  llvm_unreachable("Unknown predicate type");
812 }
813 
815 
817 
819  : FunctionPass(ID) {
822 }
823 
825  AU.setPreservesAll();
828 }
829 
831  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
832  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
833  auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
834  PredInfo->print(dbgs());
836  PredInfo->verifyPredicateInfo();
837  return false;
838 }
839 
842  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
843  auto &AC = AM.getResult<AssumptionAnalysis>(F);
844  OS << "PredicateInfo for function: " << F.getName() << "\n";
845  auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
846  PredInfo->print(OS);
847 
848  return PreservedAnalyses::all();
849 }
850 
851 /// An assembly annotator class to print PredicateInfo information in
852 /// comments.
854  friend class PredicateInfo;
855  const PredicateInfo *PredInfo;
856 
857 public:
859 
861  formatted_raw_ostream &OS) override {}
862 
864  formatted_raw_ostream &OS) override {
865  if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
866  OS << "; Has predicate info\n";
867  if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
868  OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
869  << " Comparison:" << *PB->Condition << " Edge: [";
870  PB->From->printAsOperand(OS);
871  OS << ",";
872  PB->To->printAsOperand(OS);
873  OS << "]";
874  } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
875  OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
876  << " Switch:" << *PS->Switch << " Edge: [";
877  PS->From->printAsOperand(OS);
878  OS << ",";
879  PS->To->printAsOperand(OS);
880  OS << "]";
881  } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
882  OS << "; assume predicate info {"
883  << " Comparison:" << *PA->Condition;
884  }
885  OS << ", RenamedOp: ";
886  PI->RenamedOp->printAsOperand(OS, false);
887  OS << " }\n";
888  }
889  }
890 };
891 
893  PredicateInfoAnnotatedWriter Writer(this);
894  F.print(OS, &Writer);
895 }
896 
897 void PredicateInfo::dump() const {
898  PredicateInfoAnnotatedWriter Writer(this);
899  F.print(dbgs(), &Writer);
900 }
901 
904  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
905  auto &AC = AM.getResult<AssumptionAnalysis>(F);
906  std::make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
907 
908  return PreservedAnalyses::all();
909 }
910 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::valueComesBefore
static bool valueComesBefore(const Value *A, const Value *B)
Definition: PredicateInfo.cpp:112
AssumptionCache.h
llvm::ValueDFS::LocalNum
unsigned int LocalNum
Definition: PredicateInfo.cpp:102
llvm
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::PredicateInfoBuilder::PredicateInfoBuilder
PredicateInfoBuilder(PredicateInfo &PI, Function &F, DominatorTree &DT, AssumptionCache &AC)
Definition: PredicateInfo.cpp:294
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
llvm::ValueDFS_Compare::DT
DominatorTree & DT
Definition: PredicateInfo.cpp:127
llvm::PredicateInfoPrinterLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: PredicateInfo.cpp:824
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:447
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1295
Metadata.h
PredicateInfo.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::LN_First
@ LN_First
Definition: PredicateInfo.cpp:89
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
llvm::Function
Definition: Function.h:61
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
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:197
llvm::LocalNum
LocalNum
Definition: PredicateInfo.cpp:87
Printer
print PredicateInfo Printer
Definition: PredicateInfo.cpp:47
llvm::PredicateInfoAnnotatedWriter::PredicateInfoAnnotatedWriter
PredicateInfoAnnotatedWriter(const PredicateInfo *M)
Definition: PredicateInfo.cpp:858
llvm::PT_Branch
@ PT_Branch
Definition: PredicateInfo.h:69
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
VerifyPredicateInfo
print PredicateInfo static false cl::opt< bool > VerifyPredicateInfo("verify-predicateinfo", cl::init(false), cl::Hidden, cl::desc("Verify PredicateInfo in legacy printer pass."))
llvm::PT_Assume
@ PT_Assume
Definition: PredicateInfo.h:69
llvm::AMDGPUISD::IF
@ IF
Definition: AMDGPUISelLowering.h:348
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:823
llvm::ValueDFS::DFSIn
int DFSIn
Definition: PredicateInfo.cpp:100
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::LN_Last
@ LN_Last
Definition: PredicateInfo.cpp:94
llvm::shouldRename
bool shouldRename(Value *V)
Definition: PredicateInfo.cpp:370
llvm::PredicateInfo::verifyPredicateInfo
void verifyPredicateInfo() const
Definition: PredicateInfo.cpp:814
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DenseMap.h
Module.h
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::PredicateBranch
Definition: PredicateInfo.h:144
llvm::Optional
Definition: APInt.h:34
llvm::SmallPtrSet< Value *, 4 >
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::PredicateInfoBuilder
Definition: PredicateInfo.cpp:249
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::DomTreeNodeBase::getDFSNumIn
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
Definition: GenericDomTree.h:143
llvm::DomTreeNodeBase::getDFSNumOut
unsigned getDFSNumOut() const
Definition: GenericDomTree.h:144
llvm::ValueDFS::U
Use * U
Definition: PredicateInfo.cpp:105
CommandLine.h
FormattedStream.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::PredicateInfoPrinterLegacyPass::runOnFunction
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: PredicateInfo.cpp:830
false
Definition: StackSlotColoring.cpp:142
llvm::ValueDFS_Compare::getMiddleDef
Value * getMiddleDef(const ValueDFS &VD) const
Definition: PredicateInfo.cpp:201
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
opt
arm prera ldst opt
Definition: ARMLoadStoreOptimizer.cpp:2191
pass
modulo schedule Modulo Schedule test pass
Definition: ModuloSchedule.cpp:2126
llvm::PredicateInfoPrinterLegacyPass
Definition: PredicateInfo.h:211
llvm::Instruction
Definition: Instruction.h:45
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
MaxCondsPerBranch
static const unsigned MaxCondsPerBranch
Definition: PredicateInfo.cpp:56
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
SmallPtrSet.h
PatternMatch.h
llvm::PredicateSwitch
Definition: PredicateInfo.h:158
Utils.h
llvm::ValueDFS::PInfo
PredicateBase * PInfo
Definition: PredicateInfo.cpp:107
llvm::None
const NoneType None
Definition: None.h:23
DEBUG_COUNTER
DEBUG_COUNTER(RenameCounter, "predicateinfo-rename", "Controls which variables are renamed with predicateinfo")
llvm::PredicateInfo
Encapsulates PredicateInfo, including all data associated with memory accesses.
Definition: PredicateInfo.h:176
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:166
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3086
llvm::PredicateInfoBuilder::buildPredicateInfo
void buildPredicateInfo()
Definition: PredicateInfo.cpp:513
llvm::PredicateInfo::dump
void dump() const
Definition: PredicateInfo.cpp:897
llvm::PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass
PredicateInfoPrinterLegacyPass()
Definition: PredicateInfo.cpp:818
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
AssemblyAnnotationWriter.h
llvm::PredicateInfoPrinterLegacyPass::ID
static char ID
Definition: PredicateInfo.h:215
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::PT_Switch
@ PT_Switch
Definition: PredicateInfo.h:69
llvm::PredicateBase
Definition: PredicateInfo.h:80
llvm::ValueDFS_Compare::getDefOrUser
const Instruction * getDefOrUser(const Value *Def, const Use *U) const
Definition: PredicateInfo.cpp:222
llvm::ValueDFS
Definition: PredicateInfo.cpp:99
llvm::PredicateInfoAnnotatedWriter::emitInstructionAnnot
void emitInstructionAnnot(const Instruction *I, formatted_raw_ostream &OS) override
emitInstructionAnnot - This may be implemented to emit a string right before an instruction is emitte...
Definition: PredicateInfo.cpp:863
Verify
ppc ctr loops PowerPC CTR Loops Verify
Definition: PPCCTRLoops.cpp:77
processSwitch
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, DominatorTree *DT)
Simplify a switch instruction by removing cases which can never fire.
Definition: CorrelatedValuePropagation.cpp:328
llvm::PatternMatch::m_LogicalOr
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Definition: PatternMatch.h:2457
llvm::ValueDFS_Compare::operator()
bool operator()(const ValueDFS &A, const ValueDFS &B) const
Definition: PredicateInfo.cpp:130
llvm::ValueDFS_Compare::localComesBefore
bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const
Definition: PredicateInfo.cpp:230
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::PredicateBase::RenamedOp
Value * RenamedOp
Definition: PredicateInfo.h:90
llvm::DenseMap
Definition: DenseMap.h:714
llvm::PredicateInfoVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PredicateInfo.cpp:902
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LN_Middle
@ LN_Middle
Definition: PredicateInfo.cpp:92
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::pdb::PDB_MemoryType::Stack
@ Stack
llvm::formatted_raw_ostream
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
Definition: FormattedStream.h:30
IRBuilder.h
llvm::PredicateBase::Condition
Value * Condition
Definition: PredicateInfo.h:92
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PredicateInfo::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(const Value *V) const
Definition: PredicateInfo.h:186
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:649
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
Compare
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
Definition: README_P9.txt:309
CFG.h
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::PredicateInfoAnnotatedWriter
An assembly annotator class to print PredicateInfo information in comments.
Definition: PredicateInfo.cpp:853
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::initializePredicateInfoPrinterLegacyPassPass
void initializePredicateInfoPrinterLegacyPassPass(PassRegistry &)
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
cl
http eax xorl edx cl sete al setne dl sall cl
Definition: README.txt:25
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
verify
ppc ctr loops verify
Definition: PPCCTRLoops.cpp:76
llvm::collectCmpOps
void collectCmpOps(CmpInst *Comparison, SmallVectorImpl< Value * > &CmpOperands)
Definition: PredicateInfo.cpp:379
llvm::DomTreeNodeBase< BasicBlock >
llvm::BasicBlock::getTerminator
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:148
llvm::ValueDFS::Def
Value * Def
Definition: PredicateInfo.cpp:104
llvm::PredicateInfoPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: PredicateInfo.cpp:840
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo", "PredicateInfo Printer", false, false) INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
llvm::ValueDFS_Compare::comparePHIRelated
bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const
Definition: PredicateInfo.cpp:168
llvm::ValueDFS_Compare
Definition: PredicateInfo.cpp:126
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1640
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
llvm::ValueDFS_Compare::getBlockEdge
std::pair< BasicBlock *, BasicBlock * > getBlockEdge(const ValueDFS &VD) const
Definition: PredicateInfo.cpp:158
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::AssemblyAnnotationWriter
Definition: AssemblyAnnotationWriter.h:27
GlobalVariable.h
DebugCounter.h
llvm::PredicateInfo::print
void print(raw_ostream &) const
Definition: PredicateInfo.cpp:892
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::ValueDFS_Compare::ValueDFS_Compare
ValueDFS_Compare(DominatorTree &DT)
Definition: PredicateInfo.cpp:128
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::ValueDFS::DFSOut
int DFSOut
Definition: PredicateInfo.cpp:101
Dominators.h
rename
static void rename(GlobalValue *GV)
Definition: AutoUpgrade.cpp:38
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::SmallVectorImpl< Value * >
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3149
llvm::ValueDFS::EdgeOnly
bool EdgeOnly
Definition: PredicateInfo.cpp:108
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3005
InitializePasses.h
predicateinfo
print predicateinfo
Definition: PredicateInfo.cpp:46
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::PredicateInfoAnnotatedWriter::emitBasicBlockStartAnnot
void emitBasicBlockStartAnnot(const BasicBlock *BB, formatted_raw_ostream &OS) override
emitBasicBlockStartAnnot - This may be implemented to emit a string right after the basic block label...
Definition: PredicateInfo.cpp:860
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3084
llvm::PredicateBase::getConstraint
Optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
Definition: PredicateInfo.cpp:764
llvm::PatternMatch::m_LogicalAnd
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
Definition: PatternMatch.h:2446
llvm::PredicateInfo::PredicateInfo
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
Definition: PredicateInfo.cpp:757
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3098
llvm::PredicateAssume
Definition: PredicateInfo.h:114
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38