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