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