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