LLVM  13.0.0git
PredicateInfo.cpp
Go to the documentation of this file.
1 //===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------===//
8 //
9 // This file implements the PredicateInfo class.
10 //
11 //===----------------------------------------------------------------===//
12 
14 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
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 // Create a ssa_copy declaration with custom mangling, because
543 // Intrinsic::getDeclaration does not handle overloaded unnamed types properly:
544 // all unnamed types get mangled to the same string. We use the pointer
545 // to the type as name here, as it guarantees unique names for different
546 // types and we remove the declarations when destroying PredicateInfo.
547 // It is a workaround for PR38117, because solving it in a fully general way is
548 // tricky (FIXME).
550  std::string Name = "llvm.ssa.copy." + utostr((uintptr_t) Ty);
551  return cast<Function>(
552  M->getOrInsertFunction(Name,
553  getType(M->getContext(), Intrinsic::ssa_copy, Ty))
554  .getCallee());
555 }
556 
557 // Given the renaming stack, make all the operands currently on the stack real
558 // by inserting them into the IR. Return the last operation's value.
559 Value *PredicateInfoBuilder::materializeStack(unsigned int &Counter,
560  ValueDFSStack &RenameStack,
561  Value *OrigOp) {
562  // Find the first thing we have to materialize
563  auto RevIter = RenameStack.rbegin();
564  for (; RevIter != RenameStack.rend(); ++RevIter)
565  if (RevIter->Def)
566  break;
567 
568  size_t Start = RevIter - RenameStack.rbegin();
569  // The maximum number of things we should be trying to materialize at once
570  // right now is 4, depending on if we had an assume, a branch, and both used
571  // and of conditions.
572  for (auto RenameIter = RenameStack.end() - Start;
573  RenameIter != RenameStack.end(); ++RenameIter) {
574  auto *Op =
575  RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
576  ValueDFS &Result = *RenameIter;
577  auto *ValInfo = Result.PInfo;
578  ValInfo->RenamedOp = (RenameStack.end() - Start) == RenameStack.begin()
579  ? OrigOp
580  : (RenameStack.end() - Start - 1)->Def;
581  // For edge predicates, we can just place the operand in the block before
582  // the terminator. For assume, we have to place it right before the assume
583  // to ensure we dominate all of our uses. Always insert right before the
584  // relevant instruction (terminator, assume), so that we insert in proper
585  // order in the case of multiple predicateinfo in the same block.
586  if (isa<PredicateWithEdge>(ValInfo)) {
587  IRBuilder<> B(getBranchTerminator(ValInfo));
588  Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
589  if (IF->users().empty())
590  PI.CreatedDeclarations.insert(IF);
591  CallInst *PIC =
592  B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
593  PI.PredicateMap.insert({PIC, ValInfo});
594  Result.Def = PIC;
595  } else {
596  auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
597  assert(PAssume &&
598  "Should not have gotten here without it being an assume");
599  // Insert the predicate directly after the assume. While it also holds
600  // directly before it, assume(i1 true) is not a useful fact.
601  IRBuilder<> B(PAssume->AssumeInst->getNextNode());
602  Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
603  if (IF->users().empty())
604  PI.CreatedDeclarations.insert(IF);
605  CallInst *PIC = B.CreateCall(IF, Op);
606  PI.PredicateMap.insert({PIC, ValInfo});
607  Result.Def = PIC;
608  }
609  }
610  return RenameStack.back().Def;
611 }
612 
613 // Instead of the standard SSA renaming algorithm, which is O(Number of
614 // instructions), and walks the entire dominator tree, we walk only the defs +
615 // uses. The standard SSA renaming algorithm does not really rely on the
616 // dominator tree except to order the stack push/pops of the renaming stacks, so
617 // that defs end up getting pushed before hitting the correct uses. This does
618 // not require the dominator tree, only the *order* of the dominator tree. The
619 // complete and correct ordering of the defs and uses, in dominator tree is
620 // contained in the DFS numbering of the dominator tree. So we sort the defs and
621 // uses into the DFS ordering, and then just use the renaming stack as per
622 // normal, pushing when we hit a def (which is a predicateinfo instruction),
623 // popping when we are out of the dfs scope for that def, and replacing any uses
624 // with top of stack if it exists. In order to handle liveness without
625 // propagating liveness info, we don't actually insert the predicateinfo
626 // instruction def until we see a use that it would dominate. Once we see such
627 // a use, we materialize the predicateinfo instruction in the right place and
628 // use it.
629 //
630 // TODO: Use this algorithm to perform fast single-variable renaming in
631 // promotememtoreg and memoryssa.
632 void PredicateInfoBuilder::renameUses(SmallVectorImpl<Value *> &OpsToRename) {
634  // Compute liveness, and rename in O(uses) per Op.
635  for (auto *Op : OpsToRename) {
636  LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
637  unsigned Counter = 0;
638  SmallVector<ValueDFS, 16> OrderedUses;
639  const auto &ValueInfo = getValueInfo(Op);
640  // Insert the possible copies into the def/use list.
641  // They will become real copies if we find a real use for them, and never
642  // created otherwise.
643  for (auto &PossibleCopy : ValueInfo.Infos) {
644  ValueDFS VD;
645  // Determine where we are going to place the copy by the copy type.
646  // The predicate info for branches always come first, they will get
647  // materialized in the split block at the top of the block.
648  // The predicate info for assumes will be somewhere in the middle,
649  // it will get materialized in front of the assume.
650  if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
651  VD.LocalNum = LN_Middle;
652  DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
653  if (!DomNode)
654  continue;
655  VD.DFSIn = DomNode->getDFSNumIn();
656  VD.DFSOut = DomNode->getDFSNumOut();
657  VD.PInfo = PossibleCopy;
658  OrderedUses.push_back(VD);
659  } else if (isa<PredicateWithEdge>(PossibleCopy)) {
660  // If we can only do phi uses, we treat it like it's in the branch
661  // block, and handle it specially. We know that it goes last, and only
662  // dominate phi uses.
663  auto BlockEdge = getBlockEdge(PossibleCopy);
664  if (EdgeUsesOnly.count(BlockEdge)) {
665  VD.LocalNum = LN_Last;
666  auto *DomNode = DT.getNode(BlockEdge.first);
667  if (DomNode) {
668  VD.DFSIn = DomNode->getDFSNumIn();
669  VD.DFSOut = DomNode->getDFSNumOut();
670  VD.PInfo = PossibleCopy;
671  VD.EdgeOnly = true;
672  OrderedUses.push_back(VD);
673  }
674  } else {
675  // Otherwise, we are in the split block (even though we perform
676  // insertion in the branch block).
677  // Insert a possible copy at the split block and before the branch.
678  VD.LocalNum = LN_First;
679  auto *DomNode = DT.getNode(BlockEdge.second);
680  if (DomNode) {
681  VD.DFSIn = DomNode->getDFSNumIn();
682  VD.DFSOut = DomNode->getDFSNumOut();
683  VD.PInfo = PossibleCopy;
684  OrderedUses.push_back(VD);
685  }
686  }
687  }
688  }
689 
690  convertUsesToDFSOrdered(Op, OrderedUses);
691  // Here we require a stable sort because we do not bother to try to
692  // assign an order to the operands the uses represent. Thus, two
693  // uses in the same instruction do not have a strict sort order
694  // currently and will be considered equal. We could get rid of the
695  // stable sort by creating one if we wanted.
696  llvm::stable_sort(OrderedUses, Compare);
697  SmallVector<ValueDFS, 8> RenameStack;
698  // For each use, sorted into dfs order, push values and replaces uses with
699  // top of stack, which will represent the reaching def.
700  for (auto &VD : OrderedUses) {
701  // We currently do not materialize copy over copy, but we should decide if
702  // we want to.
703  bool PossibleCopy = VD.PInfo != nullptr;
704  if (RenameStack.empty()) {
705  LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
706  } else {
707  LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
708  << RenameStack.back().DFSIn << ","
709  << RenameStack.back().DFSOut << ")\n");
710  }
711 
712  LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
713  << VD.DFSOut << ")\n");
714 
715  bool ShouldPush = (VD.Def || PossibleCopy);
716  bool OutOfScope = !stackIsInScope(RenameStack, VD);
717  if (OutOfScope || ShouldPush) {
718  // Sync to our current scope.
719  popStackUntilDFSScope(RenameStack, VD);
720  if (ShouldPush) {
721  RenameStack.push_back(VD);
722  }
723  }
724  // If we get to this point, and the stack is empty we must have a use
725  // with no renaming needed, just skip it.
726  if (RenameStack.empty())
727  continue;
728  // Skip values, only want to rename the uses
729  if (VD.Def || PossibleCopy)
730  continue;
731  if (!DebugCounter::shouldExecute(RenameCounter)) {
732  LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
733  continue;
734  }
735  ValueDFS &Result = RenameStack.back();
736 
737  // If the possible copy dominates something, materialize our stack up to
738  // this point. This ensures every comparison that affects our operation
739  // ends up with predicateinfo.
740  if (!Result.Def)
741  Result.Def = materializeStack(Counter, RenameStack, Op);
742 
743  LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
744  << *VD.U->get() << " in " << *(VD.U->getUser())
745  << "\n");
746  assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
747  "Predicateinfo def should have dominated this use");
748  VD.U->set(Result.Def);
749  }
750  }
751 }
752 
753 PredicateInfoBuilder::ValueInfo &
754 PredicateInfoBuilder::getOrCreateValueInfo(Value *Operand) {
755  auto OIN = ValueInfoNums.find(Operand);
756  if (OIN == ValueInfoNums.end()) {
757  // This will grow it
758  ValueInfos.resize(ValueInfos.size() + 1);
759  // This will use the new size and give us a 0 based number of the info
760  auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
761  assert(InsertResult.second && "Value info number already existed?");
762  return ValueInfos[InsertResult.first->second];
763  }
764  return ValueInfos[OIN->second];
765 }
766 
767 const PredicateInfoBuilder::ValueInfo &
768 PredicateInfoBuilder::getValueInfo(Value *Operand) const {
769  auto OINI = ValueInfoNums.lookup(Operand);
770  assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
771  assert(OINI < ValueInfos.size() &&
772  "Value Info Number greater than size of Value Info Table");
773  return ValueInfos[OINI];
774 }
775 
777  AssumptionCache &AC)
778  : F(F) {
779  PredicateInfoBuilder Builder(*this, F, DT, AC);
780  Builder.buildPredicateInfo();
781 }
782 
783 // Remove all declarations we created . The PredicateInfo consumers are
784 // responsible for remove the ssa_copy calls created.
786  // Collect function pointers in set first, as SmallSet uses a SmallVector
787  // internally and we have to remove the asserting value handles first.
788  SmallPtrSet<Function *, 20> FunctionPtrs;
789  for (auto &F : CreatedDeclarations)
790  FunctionPtrs.insert(&*F);
791  CreatedDeclarations.clear();
792 
793  for (Function *F : FunctionPtrs) {
794  assert(F->user_begin() == F->user_end() &&
795  "PredicateInfo consumer did not remove all SSA copies.");
796  F->eraseFromParent();
797  }
798 }
799 
801  switch (Type) {
802  case PT_Assume:
803  case PT_Branch: {
804  bool TrueEdge = true;
805  if (auto *PBranch = dyn_cast<PredicateBranch>(this))
806  TrueEdge = PBranch->TrueEdge;
807 
808  if (Condition == RenamedOp) {
809  return {{CmpInst::ICMP_EQ,
810  TrueEdge ? ConstantInt::getTrue(Condition->getType())
812  }
813 
814  CmpInst *Cmp = dyn_cast<CmpInst>(Condition);
815  if (!Cmp) {
816  // TODO: Make this an assertion once RenamedOp is fully accurate.
817  return None;
818  }
819 
820  CmpInst::Predicate Pred;
821  Value *OtherOp;
822  if (Cmp->getOperand(0) == RenamedOp) {
823  Pred = Cmp->getPredicate();
824  OtherOp = Cmp->getOperand(1);
825  } else if (Cmp->getOperand(1) == RenamedOp) {
826  Pred = Cmp->getSwappedPredicate();
827  OtherOp = Cmp->getOperand(0);
828  } else {
829  // TODO: Make this an assertion once RenamedOp is fully accurate.
830  return None;
831  }
832 
833  // Invert predicate along false edge.
834  if (!TrueEdge)
835  Pred = CmpInst::getInversePredicate(Pred);
836 
837  return {{Pred, OtherOp}};
838  }
839  case PT_Switch:
840  if (Condition != RenamedOp) {
841  // TODO: Make this an assertion once RenamedOp is fully accurate.
842  return None;
843  }
844 
845  return {{CmpInst::ICMP_EQ, cast<PredicateSwitch>(this)->CaseValue}};
846  }
847  llvm_unreachable("Unknown predicate type");
848 }
849 
851 
853 
855  : FunctionPass(ID) {
858 }
859 
861  AU.setPreservesAll();
864 }
865 
866 // Replace ssa_copy calls created by PredicateInfo with their operand.
867 static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
869  const auto *PI = PredInfo.getPredicateInfoFor(&Inst);
870  auto *II = dyn_cast<IntrinsicInst>(&Inst);
871  if (!PI || !II || II->getIntrinsicID() != Intrinsic::ssa_copy)
872  continue;
873 
874  Inst.replaceAllUsesWith(II->getOperand(0));
875  Inst.eraseFromParent();
876  }
877 }
878 
880  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
881  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
882  auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
883  PredInfo->print(dbgs());
885  PredInfo->verifyPredicateInfo();
886 
887  replaceCreatedSSACopys(*PredInfo, F);
888  return false;
889 }
890 
893  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
894  auto &AC = AM.getResult<AssumptionAnalysis>(F);
895  OS << "PredicateInfo for function: " << F.getName() << "\n";
896  auto PredInfo = std::make_unique<PredicateInfo>(F, DT, AC);
897  PredInfo->print(OS);
898 
899  replaceCreatedSSACopys(*PredInfo, F);
900  return PreservedAnalyses::all();
901 }
902 
903 /// An assembly annotator class to print PredicateInfo information in
904 /// comments.
906  friend class PredicateInfo;
907  const PredicateInfo *PredInfo;
908 
909 public:
911 
913  formatted_raw_ostream &OS) override {}
914 
916  formatted_raw_ostream &OS) override {
917  if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
918  OS << "; Has predicate info\n";
919  if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
920  OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
921  << " Comparison:" << *PB->Condition << " Edge: [";
922  PB->From->printAsOperand(OS);
923  OS << ",";
924  PB->To->printAsOperand(OS);
925  OS << "]";
926  } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
927  OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
928  << " Switch:" << *PS->Switch << " Edge: [";
929  PS->From->printAsOperand(OS);
930  OS << ",";
931  PS->To->printAsOperand(OS);
932  OS << "]";
933  } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
934  OS << "; assume predicate info {"
935  << " Comparison:" << *PA->Condition;
936  }
937  OS << ", RenamedOp: ";
938  PI->RenamedOp->printAsOperand(OS, false);
939  OS << " }\n";
940  }
941  }
942 };
943 
945  PredicateInfoAnnotatedWriter Writer(this);
946  F.print(OS, &Writer);
947 }
948 
949 void PredicateInfo::dump() const {
950  PredicateInfoAnnotatedWriter Writer(this);
951  F.print(dbgs(), &Writer);
952 }
953 
956  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
957  auto &AC = AM.getResult<AssumptionAnalysis>(F);
958  std::make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
959 
960  return PreservedAnalyses::all();
961 }
962 }
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
This class represents lattice values for constants.
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:743
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:860
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:437
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
Metadata.h
PredicateInfo.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::LN_First
@ LN_First
Definition: PredicateInfo.cpp: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:785
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:51
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:910
llvm::Function::eraseFromParent
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Function.cpp:321
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:348
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:823
llvm::ValueDFS::DFSIn
int DFSIn
Definition: PredicateInfo.cpp: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:850
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DenseMap.h
Module.h
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::PredicateBranch
Definition: PredicateInfo.h:146
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet< Value *, 4 >
llvm::Value::user_begin
user_iterator user_begin()
Definition: Value.h:400
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
getType
static wasm::ValType getType(const TargetRegisterClass *RC)
Definition: WebAssemblyMCInstLower.cpp:190
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::PredicateInfoBuilder
Definition: PredicateInfo.cpp: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:132
llvm::DomTreeNodeBase::getDFSNumIn
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
Definition: GenericDomTree.h:143
llvm::DomTreeNodeBase::getDFSNumOut
unsigned getDFSNumOut() const
Definition: GenericDomTree.h:144
llvm::ValueDFS::U
Use * U
Definition: PredicateInfo.cpp: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
SI
@ SI
Definition: SIInstrInfo.cpp:7382
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:879
llvm::replaceCreatedSSACopys
static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F)
Definition: PredicateInfo.cpp:867
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
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:278
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
MaxCondsPerBranch
static const unsigned MaxCondsPerBranch
Definition: PredicateInfo.cpp: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:166
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3086
llvm::PredicateInfoBuilder::buildPredicateInfo
void buildPredicateInfo()
Definition: PredicateInfo.cpp:515
llvm::PredicateInfo::dump
void dump() const
Definition: PredicateInfo.cpp:949
llvm::PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass
PredicateInfoPrinterLegacyPass()
Definition: PredicateInfo.cpp:854
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
AssemblyAnnotationWriter.h
llvm::Value::user_end
user_iterator user_end()
Definition: Value.h:408
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:915
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:327
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:2456
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:58
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:954
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:440
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:581
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())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::PredicateInfo::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(const Value *V) const
Definition: PredicateInfo.h:188
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:643
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:905
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::initializePredicateInfoPrinterLegacyPassPass
void initializePredicateInfoPrinterLegacyPassPass(PassRegistry &)
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
cl
http eax xorl edx cl sete al setne dl sall cl
Definition: README.txt:25
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
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:891
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:831
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:227
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:80
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1633
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:824
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
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:302
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:944
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
llvm::ValueDFS_Compare::ValueDFS_Compare
ValueDFS_Compare(DominatorTree &DT)
Definition: PredicateInfo.cpp:130
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
llvm::ValueDFS::DFSOut
int DFSOut
Definition: PredicateInfo.cpp:103
llvm::PredicateInfo::~PredicateInfo
~PredicateInfo()
Definition: PredicateInfo.cpp:785
Dominators.h
rename
static void rename(GlobalValue *GV)
Definition: AutoUpgrade.cpp:39
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::SmallVectorImpl< Value * >
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3149
llvm::ValueDFS::EdgeOnly
bool EdgeOnly
Definition: PredicateInfo.cpp:110
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3005
llvm::getCopyDeclaration
static Function * getCopyDeclaration(Module *M, Type *Ty)
Definition: PredicateInfo.cpp:549
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:912
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3084
llvm::PredicateBase::getConstraint
Optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
Definition: PredicateInfo.cpp:800
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:2445
llvm::PredicateInfo::PredicateInfo
PredicateInfo(Function &, DominatorTree &, AssumptionCache &)
Definition: PredicateInfo.cpp:776
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3098
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:37