blob: aacbd59ca493ea44afa5b7b09506be27dc00f5b1 [file] [log] [blame]
Daniel Berlin439042b2017-02-07 21:10:46 +00001//===-- 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
14#include "llvm/Transforms/Utils/PredicateInfo.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DepthFirstIterator.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/Analysis/AssumptionCache.h"
21#include "llvm/Analysis/CFG.h"
22#include "llvm/Analysis/OrderedBasicBlock.h"
23#include "llvm/IR/AssemblyAnnotationWriter.h"
24#include "llvm/IR/DataLayout.h"
25#include "llvm/IR/Dominators.h"
26#include "llvm/IR/GlobalVariable.h"
27#include "llvm/IR/IRBuilder.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/Support/Debug.h"
Daniel Berlina4b5c012017-02-19 04:29:01 +000034#include "llvm/Support/DebugCounter.h"
Daniel Berlin439042b2017-02-07 21:10:46 +000035#include "llvm/Support/FormattedStream.h"
36#include "llvm/Transforms/Scalar.h"
37#include <algorithm>
38#define DEBUG_TYPE "predicateinfo"
39using namespace llvm;
40using namespace PatternMatch;
41using namespace llvm::PredicateInfoClasses;
42
43INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
44 "PredicateInfo Printer", false, false)
45INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
46INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
47INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
48 "PredicateInfo Printer", false, false)
49static cl::opt<bool> VerifyPredicateInfo(
50 "verify-predicateinfo", cl::init(false), cl::Hidden,
51 cl::desc("Verify PredicateInfo in legacy printer pass."));
Daniel Berlinfccbda92017-02-22 22:20:58 +000052namespace {
Daniel Berlina4b5c012017-02-19 04:29:01 +000053DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
Simon Pilgrim57981802017-02-19 12:32:44 +000054 "Controls which variables are renamed with predicateinfo")
Daniel Berlinfccbda92017-02-22 22:20:58 +000055// Given a predicate info that is a type of branching terminator, get the
56// branching block.
57const BasicBlock *getBranchBlock(const PredicateBase *PB) {
58 assert(isa<PredicateWithEdge>(PB) &&
59 "Only branches and switches should have PHIOnly defs that "
60 "require branch blocks.");
61 return cast<PredicateWithEdge>(PB)->From;
62}
63
64// Given a predicate info that is a type of branching terminator, get the
65// branching terminator.
66static Instruction *getBranchTerminator(const PredicateBase *PB) {
67 assert(isa<PredicateWithEdge>(PB) &&
68 "Not a predicate info type we know how to get a terminator from.");
69 return cast<PredicateWithEdge>(PB)->From->getTerminator();
70}
71
72// Given a predicate info that is a type of branching terminator, get the
73// edge this predicate info represents
74const std::pair<BasicBlock *, BasicBlock *>
75getBlockEdge(const PredicateBase *PB) {
76 assert(isa<PredicateWithEdge>(PB) &&
77 "Not a predicate info type we know how to get an edge from.");
78 const auto *PEdge = cast<PredicateWithEdge>(PB);
79 return std::make_pair(PEdge->From, PEdge->To);
80}
81}
Daniel Berlina4b5c012017-02-19 04:29:01 +000082
Daniel Berlin439042b2017-02-07 21:10:46 +000083namespace llvm {
84namespace PredicateInfoClasses {
85enum LocalNum {
86 // Operations that must appear first in the block.
87 LN_First,
88 // Operations that are somewhere in the middle of the block, and are sorted on
89 // demand.
90 LN_Middle,
91 // Operations that must appear last in a block, like successor phi node uses.
92 LN_Last
93};
94
95// Associate global and local DFS info with defs and uses, so we can sort them
96// into a global domination ordering.
97struct ValueDFS {
98 int DFSIn = 0;
99 int DFSOut = 0;
100 unsigned int LocalNum = LN_Middle;
Daniel Berlin439042b2017-02-07 21:10:46 +0000101 // Only one of Def or Use will be set.
102 Value *Def = nullptr;
Daniel Berlinc763fd12017-02-07 22:11:43 +0000103 Use *U = nullptr;
Daniel Berlin588e0be2017-02-18 23:06:38 +0000104 // Neither PInfo nor EdgeOnly participate in the ordering
Daniel Berlindbe82642017-02-12 22:12:20 +0000105 PredicateBase *PInfo = nullptr;
Daniel Berlin588e0be2017-02-18 23:06:38 +0000106 bool EdgeOnly = false;
Daniel Berlin439042b2017-02-07 21:10:46 +0000107};
108
109// This compares ValueDFS structures, creating OrderedBasicBlocks where
110// necessary to compare uses/defs in the same block. Doing so allows us to walk
111// the minimum number of instructions necessary to compute our def/use ordering.
112struct ValueDFS_Compare {
113 DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &OBBMap;
114 ValueDFS_Compare(
115 DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &OBBMap)
116 : OBBMap(OBBMap) {}
117 bool operator()(const ValueDFS &A, const ValueDFS &B) const {
118 if (&A == &B)
119 return false;
120 // The only case we can't directly compare them is when they in the same
121 // block, and both have localnum == middle. In that case, we have to use
122 // comesbefore to see what the real ordering is, because they are in the
123 // same basic block.
124
125 bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut);
126
Daniel Berlindbe82642017-02-12 22:12:20 +0000127 // We want to put the def that will get used for a given set of phi uses,
128 // before those phi uses.
129 // So we sort by edge, then by def.
130 // Note that only phi nodes uses and defs can come last.
131 if (SameBlock && A.LocalNum == LN_Last && B.LocalNum == LN_Last)
132 return comparePHIRelated(A, B);
133
Daniel Berlin439042b2017-02-07 21:10:46 +0000134 if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
Daniel Berlinc763fd12017-02-07 22:11:43 +0000135 return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.U) <
136 std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.U);
Daniel Berlin439042b2017-02-07 21:10:46 +0000137 return localComesBefore(A, B);
138 }
139
Daniel Berlindbe82642017-02-12 22:12:20 +0000140 // For a phi use, or a non-materialized def, return the edge it represents.
Daniel Berlinfccbda92017-02-22 22:20:58 +0000141 const std::pair<BasicBlock *, BasicBlock *>
Daniel Berlindbe82642017-02-12 22:12:20 +0000142 getBlockEdge(const ValueDFS &VD) const {
143 if (!VD.Def && VD.U) {
144 auto *PHI = cast<PHINode>(VD.U->getUser());
145 return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
146 }
147 // This is really a non-materialized def.
Daniel Berlinfccbda92017-02-22 22:20:58 +0000148 return ::getBlockEdge(VD.PInfo);
Daniel Berlindbe82642017-02-12 22:12:20 +0000149 }
150
151 // For two phi related values, return the ordering.
152 bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
153 auto &ABlockEdge = getBlockEdge(A);
154 auto &BBlockEdge = getBlockEdge(B);
155 // Now sort by block edge and then defs before uses.
156 return std::tie(ABlockEdge, A.Def, A.U) < std::tie(BBlockEdge, B.Def, B.U);
157 }
158
Daniel Berlin439042b2017-02-07 21:10:46 +0000159 // Get the definition of an instruction that occurs in the middle of a block.
160 Value *getMiddleDef(const ValueDFS &VD) const {
161 if (VD.Def)
162 return VD.Def;
163 // It's possible for the defs and uses to be null. For branches, the local
164 // numbering will say the placed predicaeinfos should go first (IE
165 // LN_beginning), so we won't be in this function. For assumes, we will end
166 // up here, beause we need to order the def we will place relative to the
167 // assume. So for the purpose of ordering, we pretend the def is the assume
168 // because that is where we will insert the info.
Daniel Berlinc763fd12017-02-07 22:11:43 +0000169 if (!VD.U) {
Daniel Berlin439042b2017-02-07 21:10:46 +0000170 assert(VD.PInfo &&
171 "No def, no use, and no predicateinfo should not occur");
172 assert(isa<PredicateAssume>(VD.PInfo) &&
173 "Middle of block should only occur for assumes");
174 return cast<PredicateAssume>(VD.PInfo)->AssumeInst;
175 }
176 return nullptr;
177 }
178
179 // Return either the Def, if it's not null, or the user of the Use, if the def
180 // is null.
Daniel Berlinc763fd12017-02-07 22:11:43 +0000181 const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
Daniel Berlin439042b2017-02-07 21:10:46 +0000182 if (Def)
183 return cast<Instruction>(Def);
Daniel Berlinc763fd12017-02-07 22:11:43 +0000184 return cast<Instruction>(U->getUser());
Daniel Berlin439042b2017-02-07 21:10:46 +0000185 }
186
187 // This performs the necessary local basic block ordering checks to tell
188 // whether A comes before B, where both are in the same basic block.
189 bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
190 auto *ADef = getMiddleDef(A);
191 auto *BDef = getMiddleDef(B);
192
193 // See if we have real values or uses. If we have real values, we are
194 // guaranteed they are instructions or arguments. No matter what, we are
195 // guaranteed they are in the same block if they are instructions.
196 auto *ArgA = dyn_cast_or_null<Argument>(ADef);
197 auto *ArgB = dyn_cast_or_null<Argument>(BDef);
198
199 if (ArgA && !ArgB)
200 return true;
201 if (ArgB && !ArgA)
202 return false;
203 if (ArgA && ArgB)
204 return ArgA->getArgNo() < ArgB->getArgNo();
205
Daniel Berlinc763fd12017-02-07 22:11:43 +0000206 auto *AInst = getDefOrUser(ADef, A.U);
207 auto *BInst = getDefOrUser(BDef, B.U);
Daniel Berlin439042b2017-02-07 21:10:46 +0000208
209 auto *BB = AInst->getParent();
210 auto LookupResult = OBBMap.find(BB);
211 if (LookupResult != OBBMap.end())
212 return LookupResult->second->dominates(AInst, BInst);
213 else {
214 auto Result = OBBMap.insert({BB, make_unique<OrderedBasicBlock>(BB)});
215 return Result.first->second->dominates(AInst, BInst);
216 }
Daniel Berlinc763fd12017-02-07 22:11:43 +0000217 return std::tie(ADef, A.U) < std::tie(BDef, B.U);
Daniel Berlin439042b2017-02-07 21:10:46 +0000218 }
219};
220
221} // namespace PredicateInfoClasses
222
Daniel Berlindbe82642017-02-12 22:12:20 +0000223bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack,
224 const ValueDFS &VDUse) const {
Daniel Berlin439042b2017-02-07 21:10:46 +0000225 if (Stack.empty())
226 return false;
Daniel Berlindbe82642017-02-12 22:12:20 +0000227 // If it's a phi only use, make sure it's for this phi node edge, and that the
228 // use is in a phi node. If it's anything else, and the top of the stack is
Daniel Berlin588e0be2017-02-18 23:06:38 +0000229 // EdgeOnly, we need to pop the stack. We deliberately sort phi uses next to
Daniel Berlindbe82642017-02-12 22:12:20 +0000230 // the defs they must go with so that we can know it's time to pop the stack
231 // when we hit the end of the phi uses for a given def.
Daniel Berlin588e0be2017-02-18 23:06:38 +0000232 if (Stack.back().EdgeOnly) {
Daniel Berlindbe82642017-02-12 22:12:20 +0000233 if (!VDUse.U)
234 return false;
235 auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
236 if (!PHI)
237 return false;
Daniel Berlinfccbda92017-02-22 22:20:58 +0000238 // Check edge
Daniel Berlindbe82642017-02-12 22:12:20 +0000239 BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
Daniel Berlinfccbda92017-02-22 22:20:58 +0000240 if (EdgePred != getBranchBlock(Stack.back().PInfo))
Daniel Berlindbe82642017-02-12 22:12:20 +0000241 return false;
Daniel Berlin588e0be2017-02-18 23:06:38 +0000242
243 // Use dominates, which knows how to handle edge dominance.
Daniel Berlinfccbda92017-02-22 22:20:58 +0000244 return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
Daniel Berlindbe82642017-02-12 22:12:20 +0000245 }
246
247 return (VDUse.DFSIn >= Stack.back().DFSIn &&
248 VDUse.DFSOut <= Stack.back().DFSOut);
Daniel Berlin439042b2017-02-07 21:10:46 +0000249}
250
Daniel Berlindbe82642017-02-12 22:12:20 +0000251void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack,
252 const ValueDFS &VD) {
253 while (!Stack.empty() && !stackIsInScope(Stack, VD))
Daniel Berlin439042b2017-02-07 21:10:46 +0000254 Stack.pop_back();
255}
256
257// Convert the uses of Op into a vector of uses, associating global and local
258// DFS info with each one.
259void PredicateInfo::convertUsesToDFSOrdered(
260 Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
261 for (auto &U : Op->uses()) {
262 if (auto *I = dyn_cast<Instruction>(U.getUser())) {
263 ValueDFS VD;
264 // Put the phi node uses in the incoming block.
265 BasicBlock *IBlock;
266 if (auto *PN = dyn_cast<PHINode>(I)) {
267 IBlock = PN->getIncomingBlock(U);
268 // Make phi node users appear last in the incoming block
269 // they are from.
270 VD.LocalNum = LN_Last;
271 } else {
272 // If it's not a phi node use, it is somewhere in the middle of the
273 // block.
274 IBlock = I->getParent();
275 VD.LocalNum = LN_Middle;
276 }
277 DomTreeNode *DomNode = DT.getNode(IBlock);
278 // It's possible our use is in an unreachable block. Skip it if so.
279 if (!DomNode)
280 continue;
281 VD.DFSIn = DomNode->getDFSNumIn();
282 VD.DFSOut = DomNode->getDFSNumOut();
Daniel Berlinc763fd12017-02-07 22:11:43 +0000283 VD.U = &U;
Daniel Berlin439042b2017-02-07 21:10:46 +0000284 DFSOrderedSet.push_back(VD);
285 }
286 }
287}
288
289// Collect relevant operations from Comparison that we may want to insert copies
290// for.
291void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
292 auto *Op0 = Comparison->getOperand(0);
293 auto *Op1 = Comparison->getOperand(1);
294 if (Op0 == Op1)
295 return;
296 CmpOperands.push_back(Comparison);
297 // Only want real values, not constants. Additionally, operands with one use
298 // are only being used in the comparison, which means they will not be useful
299 // for us to consider for predicateinfo.
300 //
Daniel Berlin588e0be2017-02-18 23:06:38 +0000301 if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse())
Daniel Berlin439042b2017-02-07 21:10:46 +0000302 CmpOperands.push_back(Op0);
Daniel Berlin588e0be2017-02-18 23:06:38 +0000303 if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse())
Daniel Berlin439042b2017-02-07 21:10:46 +0000304 CmpOperands.push_back(Op1);
305}
306
Daniel Berlin588e0be2017-02-18 23:06:38 +0000307// Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
308void PredicateInfo::addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op,
309 PredicateBase *PB) {
310 OpsToRename.insert(Op);
311 auto &OperandInfo = getOrCreateValueInfo(Op);
312 AllInfos.push_back(PB);
313 OperandInfo.Infos.push_back(PB);
314}
315
Daniel Berlin439042b2017-02-07 21:10:46 +0000316// Process an assume instruction and place relevant operations we want to rename
317// into OpsToRename.
318void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
319 SmallPtrSetImpl<Value *> &OpsToRename) {
Daniel Berlin588e0be2017-02-18 23:06:38 +0000320 // See if we have a comparison we support
Daniel Berlin439042b2017-02-07 21:10:46 +0000321 SmallVector<Value *, 8> CmpOperands;
Daniel Berlin588e0be2017-02-18 23:06:38 +0000322 SmallVector<Value *, 2> ConditionsToProcess;
Daniel Berlin439042b2017-02-07 21:10:46 +0000323 CmpInst::Predicate Pred;
324 Value *Operand = II->getOperand(0);
325 if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
326 m_Cmp(Pred, m_Value(), m_Value()))
327 .match(II->getOperand(0))) {
Daniel Berlin588e0be2017-02-18 23:06:38 +0000328 ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0));
329 ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1));
330 ConditionsToProcess.push_back(Operand);
331 } else if (isa<CmpInst>(Operand)) {
332
333 ConditionsToProcess.push_back(Operand);
Daniel Berlin439042b2017-02-07 21:10:46 +0000334 }
Daniel Berlin588e0be2017-02-18 23:06:38 +0000335 for (auto Cond : ConditionsToProcess) {
336 if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
Daniel Berlin439042b2017-02-07 21:10:46 +0000337 collectCmpOps(Cmp, CmpOperands);
338 // Now add our copy infos for our operands
339 for (auto *Op : CmpOperands) {
Daniel Berlin588e0be2017-02-18 23:06:38 +0000340 auto *PA = new PredicateAssume(Op, II, Cmp);
341 addInfoFor(OpsToRename, Op, PA);
Daniel Berlin439042b2017-02-07 21:10:46 +0000342 }
343 CmpOperands.clear();
Daniel Berlin588e0be2017-02-18 23:06:38 +0000344 } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
345 // Otherwise, it should be an AND.
346 assert(BinOp->getOpcode() == Instruction::And &&
Simon Pilgrimdba90112017-02-19 00:33:37 +0000347 "Should have been an AND");
348 auto *PA = new PredicateAssume(BinOp, II, BinOp);
349 addInfoFor(OpsToRename, BinOp, PA);
Daniel Berlin588e0be2017-02-18 23:06:38 +0000350 } else {
351 llvm_unreachable("Unknown type of condition");
Daniel Berlin439042b2017-02-07 21:10:46 +0000352 }
353 }
354}
355
356// Process a block terminating branch, and place relevant operations to be
357// renamed into OpsToRename.
358void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
359 SmallPtrSetImpl<Value *> &OpsToRename) {
Daniel Berlin439042b2017-02-07 21:10:46 +0000360 BasicBlock *FirstBB = BI->getSuccessor(0);
361 BasicBlock *SecondBB = BI->getSuccessor(1);
Daniel Berlin439042b2017-02-07 21:10:46 +0000362 SmallVector<BasicBlock *, 2> SuccsToProcess;
Daniel Berlindbe82642017-02-12 22:12:20 +0000363 SuccsToProcess.push_back(FirstBB);
364 SuccsToProcess.push_back(SecondBB);
Daniel Berlin588e0be2017-02-18 23:06:38 +0000365 SmallVector<Value *, 2> ConditionsToProcess;
366
367 auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) {
368 for (auto *Succ : SuccsToProcess) {
369 // Don't try to insert on a self-edge. This is mainly because we will
370 // eliminate during renaming anyway.
371 if (Succ == BranchBB)
372 continue;
373 bool TakenEdge = (Succ == FirstBB);
374 // For and, only insert on the true edge
375 // For or, only insert on the false edge
376 if ((isAnd && !TakenEdge) || (isOr && TakenEdge))
377 continue;
378 PredicateBase *PB =
379 new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge);
380 addInfoFor(OpsToRename, Op, PB);
381 if (!Succ->getSinglePredecessor())
382 EdgeUsesOnly.insert({BranchBB, Succ});
383 }
384 };
Daniel Berlin439042b2017-02-07 21:10:46 +0000385
386 // Match combinations of conditions.
Daniel Berlin588e0be2017-02-18 23:06:38 +0000387 CmpInst::Predicate Pred;
388 bool isAnd = false;
389 bool isOr = false;
390 SmallVector<Value *, 8> CmpOperands;
Daniel Berlin439042b2017-02-07 21:10:46 +0000391 if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
392 m_Cmp(Pred, m_Value(), m_Value()))) ||
393 match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
394 m_Cmp(Pred, m_Value(), m_Value())))) {
395 auto *BinOp = cast<BinaryOperator>(BI->getCondition());
396 if (BinOp->getOpcode() == Instruction::And)
397 isAnd = true;
398 else if (BinOp->getOpcode() == Instruction::Or)
399 isOr = true;
Daniel Berlin588e0be2017-02-18 23:06:38 +0000400 ConditionsToProcess.push_back(BinOp->getOperand(0));
401 ConditionsToProcess.push_back(BinOp->getOperand(1));
402 ConditionsToProcess.push_back(BI->getCondition());
403 } else if (isa<CmpInst>(BI->getCondition())) {
404 ConditionsToProcess.push_back(BI->getCondition());
Daniel Berlin439042b2017-02-07 21:10:46 +0000405 }
Daniel Berlin588e0be2017-02-18 23:06:38 +0000406 for (auto Cond : ConditionsToProcess) {
407 if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
Daniel Berlin439042b2017-02-07 21:10:46 +0000408 collectCmpOps(Cmp, CmpOperands);
409 // Now add our copy infos for our operands
Daniel Berlin588e0be2017-02-18 23:06:38 +0000410 for (auto *Op : CmpOperands)
411 InsertHelper(Op, isAnd, isOr, Cmp);
412 } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
413 // This must be an AND or an OR.
414 assert((BinOp->getOpcode() == Instruction::And ||
415 BinOp->getOpcode() == Instruction::Or) &&
416 "Should have been an AND or an OR");
417 // The actual value of the binop is not subject to the same restrictions
418 // as the comparison. It's either true or false on the true/false branch.
Simon Pilgrimdba90112017-02-19 00:33:37 +0000419 InsertHelper(BinOp, false, false, BinOp);
Daniel Berlin588e0be2017-02-18 23:06:38 +0000420 } else {
421 llvm_unreachable("Unknown type of condition");
Daniel Berlin439042b2017-02-07 21:10:46 +0000422 }
Daniel Berlin588e0be2017-02-18 23:06:38 +0000423 CmpOperands.clear();
Daniel Berlin439042b2017-02-07 21:10:46 +0000424 }
425}
Daniel Berlinfccbda92017-02-22 22:20:58 +0000426// Process a block terminating switch, and place relevant operations to be
427// renamed into OpsToRename.
428void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB,
429 SmallPtrSetImpl<Value *> &OpsToRename) {
430 Value *Op = SI->getCondition();
431 if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
432 return;
433
434 // Remember how many outgoing edges there are to every successor.
435 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
436 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
437 BasicBlock *TargetBlock = SI->getSuccessor(i);
438 ++SwitchEdges[TargetBlock];
439 }
440
441 // Now propagate info for each case value
442 for (auto C : SI->cases()) {
443 BasicBlock *TargetBlock = C.getCaseSuccessor();
444 if (SwitchEdges.lookup(TargetBlock) == 1) {
445 PredicateSwitch *PS = new PredicateSwitch(
446 Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
447 addInfoFor(OpsToRename, Op, PS);
448 if (!TargetBlock->getSinglePredecessor())
449 EdgeUsesOnly.insert({BranchBB, TargetBlock});
450 }
451 }
452}
Daniel Berlin439042b2017-02-07 21:10:46 +0000453
454// Build predicate info for our function
455void PredicateInfo::buildPredicateInfo() {
456 DT.updateDFSNumbers();
457 // Collect operands to rename from all conditional branch terminators, as well
458 // as assume statements.
459 SmallPtrSet<Value *, 8> OpsToRename;
460 for (auto DTN : depth_first(DT.getRootNode())) {
461 BasicBlock *BranchBB = DTN->getBlock();
462 if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
463 if (!BI->isConditional())
464 continue;
465 processBranch(BI, BranchBB, OpsToRename);
Daniel Berlinfccbda92017-02-22 22:20:58 +0000466 } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
467 processSwitch(SI, BranchBB, OpsToRename);
Daniel Berlin439042b2017-02-07 21:10:46 +0000468 }
469 }
470 for (auto &Assume : AC.assumptions()) {
471 if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
472 processAssume(II, II->getParent(), OpsToRename);
473 }
474 // Now rename all our operations.
475 renameUses(OpsToRename);
476}
Daniel Berlinfccbda92017-02-22 22:20:58 +0000477
478// Given the renaming stack, make all the operands currently on the stack real
479// by inserting them into the IR. Return the last operation's value.
Daniel Berlin439042b2017-02-07 21:10:46 +0000480Value *PredicateInfo::materializeStack(unsigned int &Counter,
481 ValueDFSStack &RenameStack,
482 Value *OrigOp) {
483 // Find the first thing we have to materialize
484 auto RevIter = RenameStack.rbegin();
485 for (; RevIter != RenameStack.rend(); ++RevIter)
486 if (RevIter->Def)
487 break;
488
489 size_t Start = RevIter - RenameStack.rbegin();
490 // The maximum number of things we should be trying to materialize at once
491 // right now is 4, depending on if we had an assume, a branch, and both used
492 // and of conditions.
493 for (auto RenameIter = RenameStack.end() - Start;
494 RenameIter != RenameStack.end(); ++RenameIter) {
495 auto *Op =
496 RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
497 ValueDFS &Result = *RenameIter;
498 auto *ValInfo = Result.PInfo;
Daniel Berlinfccbda92017-02-22 22:20:58 +0000499 // For edge predicates, we can just place the operand in the block before
Daniel Berlindbe82642017-02-12 22:12:20 +0000500 // the terminator. For assume, we have to place it right before the assume
501 // to ensure we dominate all of our uses. Always insert right before the
502 // relevant instruction (terminator, assume), so that we insert in proper
503 // order in the case of multiple predicateinfo in the same block.
Daniel Berlinfccbda92017-02-22 22:20:58 +0000504 if (isa<PredicateWithEdge>(ValInfo)) {
505 IRBuilder<> B(getBranchTerminator(ValInfo));
Daniel Berlin439042b2017-02-07 21:10:46 +0000506 Function *IF = Intrinsic::getDeclaration(
507 F.getParent(), Intrinsic::ssa_copy, Op->getType());
Daniel Berlin588e0be2017-02-18 23:06:38 +0000508 CallInst *PIC =
509 B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
Daniel Berlin439042b2017-02-07 21:10:46 +0000510 PredicateMap.insert({PIC, ValInfo});
511 Result.Def = PIC;
512 } else {
513 auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
514 assert(PAssume &&
515 "Should not have gotten here without it being an assume");
Daniel Berlindbe82642017-02-12 22:12:20 +0000516 IRBuilder<> B(PAssume->AssumeInst);
Daniel Berlin439042b2017-02-07 21:10:46 +0000517 Function *IF = Intrinsic::getDeclaration(
518 F.getParent(), Intrinsic::ssa_copy, Op->getType());
Daniel Berlin588e0be2017-02-18 23:06:38 +0000519 CallInst *PIC = B.CreateCall(IF, Op);
Daniel Berlin439042b2017-02-07 21:10:46 +0000520 PredicateMap.insert({PIC, ValInfo});
521 Result.Def = PIC;
522 }
523 }
524 return RenameStack.back().Def;
525}
526
527// Instead of the standard SSA renaming algorithm, which is O(Number of
528// instructions), and walks the entire dominator tree, we walk only the defs +
529// uses. The standard SSA renaming algorithm does not really rely on the
530// dominator tree except to order the stack push/pops of the renaming stacks, so
531// that defs end up getting pushed before hitting the correct uses. This does
532// not require the dominator tree, only the *order* of the dominator tree. The
533// complete and correct ordering of the defs and uses, in dominator tree is
534// contained in the DFS numbering of the dominator tree. So we sort the defs and
535// uses into the DFS ordering, and then just use the renaming stack as per
536// normal, pushing when we hit a def (which is a predicateinfo instruction),
537// popping when we are out of the dfs scope for that def, and replacing any uses
538// with top of stack if it exists. In order to handle liveness without
539// propagating liveness info, we don't actually insert the predicateinfo
540// instruction def until we see a use that it would dominate. Once we see such
541// a use, we materialize the predicateinfo instruction in the right place and
542// use it.
543//
544// TODO: Use this algorithm to perform fast single-variable renaming in
545// promotememtoreg and memoryssa.
546void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpsToRename) {
547 ValueDFS_Compare Compare(OBBMap);
548 // Compute liveness, and rename in O(uses) per Op.
549 for (auto *Op : OpsToRename) {
550 unsigned Counter = 0;
551 SmallVector<ValueDFS, 16> OrderedUses;
552 const auto &ValueInfo = getValueInfo(Op);
553 // Insert the possible copies into the def/use list.
554 // They will become real copies if we find a real use for them, and never
555 // created otherwise.
556 for (auto &PossibleCopy : ValueInfo.Infos) {
557 ValueDFS VD;
Daniel Berlin439042b2017-02-07 21:10:46 +0000558 // Determine where we are going to place the copy by the copy type.
559 // The predicate info for branches always come first, they will get
560 // materialized in the split block at the top of the block.
561 // The predicate info for assumes will be somewhere in the middle,
562 // it will get materialized in front of the assume.
Daniel Berlindbe82642017-02-12 22:12:20 +0000563 if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
Daniel Berlin439042b2017-02-07 21:10:46 +0000564 VD.LocalNum = LN_Middle;
Daniel Berlindbe82642017-02-12 22:12:20 +0000565 DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
566 if (!DomNode)
567 continue;
568 VD.DFSIn = DomNode->getDFSNumIn();
569 VD.DFSOut = DomNode->getDFSNumOut();
570 VD.PInfo = PossibleCopy;
571 OrderedUses.push_back(VD);
Daniel Berlinfccbda92017-02-22 22:20:58 +0000572 } else if (isa<PredicateWithEdge>(PossibleCopy)) {
Daniel Berlindbe82642017-02-12 22:12:20 +0000573 // If we can only do phi uses, we treat it like it's in the branch
574 // block, and handle it specially. We know that it goes last, and only
575 // dominate phi uses.
Daniel Berlinfccbda92017-02-22 22:20:58 +0000576 auto BlockEdge = getBlockEdge(PossibleCopy);
577 if (EdgeUsesOnly.count(BlockEdge)) {
Daniel Berlindbe82642017-02-12 22:12:20 +0000578 VD.LocalNum = LN_Last;
Daniel Berlinfccbda92017-02-22 22:20:58 +0000579 auto *DomNode = DT.getNode(BlockEdge.first);
Daniel Berlindbe82642017-02-12 22:12:20 +0000580 if (DomNode) {
581 VD.DFSIn = DomNode->getDFSNumIn();
582 VD.DFSOut = DomNode->getDFSNumOut();
583 VD.PInfo = PossibleCopy;
Daniel Berlin588e0be2017-02-18 23:06:38 +0000584 VD.EdgeOnly = true;
Daniel Berlindbe82642017-02-12 22:12:20 +0000585 OrderedUses.push_back(VD);
586 }
587 } else {
588 // Otherwise, we are in the split block (even though we perform
589 // insertion in the branch block).
590 // Insert a possible copy at the split block and before the branch.
591 VD.LocalNum = LN_First;
Daniel Berlinfccbda92017-02-22 22:20:58 +0000592 auto *DomNode = DT.getNode(BlockEdge.second);
Daniel Berlindbe82642017-02-12 22:12:20 +0000593 if (DomNode) {
594 VD.DFSIn = DomNode->getDFSNumIn();
595 VD.DFSOut = DomNode->getDFSNumOut();
596 VD.PInfo = PossibleCopy;
597 OrderedUses.push_back(VD);
598 }
599 }
600 }
Daniel Berlin439042b2017-02-07 21:10:46 +0000601 }
602
603 convertUsesToDFSOrdered(Op, OrderedUses);
604 std::sort(OrderedUses.begin(), OrderedUses.end(), Compare);
605 SmallVector<ValueDFS, 8> RenameStack;
606 // For each use, sorted into dfs order, push values and replaces uses with
607 // top of stack, which will represent the reaching def.
608 for (auto &VD : OrderedUses) {
609 // We currently do not materialize copy over copy, but we should decide if
610 // we want to.
611 bool PossibleCopy = VD.PInfo != nullptr;
612 if (RenameStack.empty()) {
613 DEBUG(dbgs() << "Rename Stack is empty\n");
614 } else {
615 DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
616 << RenameStack.back().DFSIn << ","
617 << RenameStack.back().DFSOut << ")\n");
618 }
619
620 DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
621 << VD.DFSOut << ")\n");
622
623 bool ShouldPush = (VD.Def || PossibleCopy);
Daniel Berlindbe82642017-02-12 22:12:20 +0000624 bool OutOfScope = !stackIsInScope(RenameStack, VD);
Daniel Berlin439042b2017-02-07 21:10:46 +0000625 if (OutOfScope || ShouldPush) {
626 // Sync to our current scope.
Daniel Berlindbe82642017-02-12 22:12:20 +0000627 popStackUntilDFSScope(RenameStack, VD);
Daniel Berlin439042b2017-02-07 21:10:46 +0000628 if (ShouldPush) {
629 RenameStack.push_back(VD);
630 }
631 }
632 // If we get to this point, and the stack is empty we must have a use
633 // with no renaming needed, just skip it.
634 if (RenameStack.empty())
635 continue;
636 // Skip values, only want to rename the uses
637 if (VD.Def || PossibleCopy)
638 continue;
Daniel Berlina4b5c012017-02-19 04:29:01 +0000639 if (!DebugCounter::shouldExecute(RenameCounter)) {
640 DEBUG(dbgs() << "Skipping execution due to debug counter\n");
641 continue;
642 }
Daniel Berlin439042b2017-02-07 21:10:46 +0000643 ValueDFS &Result = RenameStack.back();
644
645 // If the possible copy dominates something, materialize our stack up to
646 // this point. This ensures every comparison that affects our operation
647 // ends up with predicateinfo.
648 if (!Result.Def)
649 Result.Def = materializeStack(Counter, RenameStack, Op);
650
651 DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
Daniel Berlinc763fd12017-02-07 22:11:43 +0000652 << *VD.U->get() << " in " << *(VD.U->getUser()) << "\n");
653 assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
Daniel Berlin439042b2017-02-07 21:10:46 +0000654 "Predicateinfo def should have dominated this use");
Daniel Berlinc763fd12017-02-07 22:11:43 +0000655 VD.U->set(Result.Def);
Daniel Berlin439042b2017-02-07 21:10:46 +0000656 }
657 }
658}
659
660PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
661 auto OIN = ValueInfoNums.find(Operand);
662 if (OIN == ValueInfoNums.end()) {
663 // This will grow it
664 ValueInfos.resize(ValueInfos.size() + 1);
665 // This will use the new size and give us a 0 based number of the info
666 auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
667 assert(InsertResult.second && "Value info number already existed?");
668 return ValueInfos[InsertResult.first->second];
669 }
670 return ValueInfos[OIN->second];
671}
672
673const PredicateInfo::ValueInfo &
674PredicateInfo::getValueInfo(Value *Operand) const {
675 auto OINI = ValueInfoNums.lookup(Operand);
676 assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
677 assert(OINI < ValueInfos.size() &&
678 "Value Info Number greater than size of Value Info Table");
679 return ValueInfos[OINI];
680}
681
682PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
683 AssumptionCache &AC)
684 : F(F), DT(DT), AC(AC) {
685 // Push an empty operand info so that we can detect 0 as not finding one
686 ValueInfos.resize(1);
687 buildPredicateInfo();
688}
689
690PredicateInfo::~PredicateInfo() {}
691
692void PredicateInfo::verifyPredicateInfo() const {}
693
694char PredicateInfoPrinterLegacyPass::ID = 0;
695
696PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass()
697 : FunctionPass(ID) {
698 initializePredicateInfoPrinterLegacyPassPass(
699 *PassRegistry::getPassRegistry());
700}
701
702void PredicateInfoPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
703 AU.setPreservesAll();
704 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
705 AU.addRequired<AssumptionCacheTracker>();
706}
707
708bool PredicateInfoPrinterLegacyPass::runOnFunction(Function &F) {
709 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
710 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
711 auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
712 PredInfo->print(dbgs());
713 if (VerifyPredicateInfo)
714 PredInfo->verifyPredicateInfo();
715 return false;
716}
717
718PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
719 FunctionAnalysisManager &AM) {
720 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
721 auto &AC = AM.getResult<AssumptionAnalysis>(F);
722 OS << "PredicateInfo for function: " << F.getName() << "\n";
723 make_unique<PredicateInfo>(F, DT, AC)->print(OS);
724
725 return PreservedAnalyses::all();
726}
727
728/// \brief An assembly annotator class to print PredicateInfo information in
729/// comments.
730class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
731 friend class PredicateInfo;
732 const PredicateInfo *PredInfo;
733
734public:
735 PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
736
737 virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
738 formatted_raw_ostream &OS) {}
739
740 virtual void emitInstructionAnnot(const Instruction *I,
741 formatted_raw_ostream &OS) {
742 if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
743 OS << "; Has predicate info\n";
Daniel Berlinfccbda92017-02-22 22:20:58 +0000744 if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
Daniel Berlin439042b2017-02-07 21:10:46 +0000745 OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
Daniel Berlinfccbda92017-02-22 22:20:58 +0000746 << " Comparison:" << *PB->Condition << " Edge: [";
747 PB->From->printAsOperand(OS);
748 OS << ",";
749 PB->To->printAsOperand(OS);
750 OS << "] }\n";
751 } else if (const auto *PS = dyn_cast<PredicateSwitch>(PI)) {
752 OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
753 << " Switch:" << *PS->Switch << " Edge: [";
754 PS->From->printAsOperand(OS);
755 OS << ",";
756 PS->To->printAsOperand(OS);
757 OS << "] }\n";
758 } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
Daniel Berlin439042b2017-02-07 21:10:46 +0000759 OS << "; assume predicate info {"
Daniel Berlin588e0be2017-02-18 23:06:38 +0000760 << " Comparison:" << *PA->Condition << " }\n";
Daniel Berlinfccbda92017-02-22 22:20:58 +0000761 }
Daniel Berlin439042b2017-02-07 21:10:46 +0000762 }
763 }
764};
765
766void PredicateInfo::print(raw_ostream &OS) const {
767 PredicateInfoAnnotatedWriter Writer(this);
768 F.print(OS, &Writer);
769}
770
771void PredicateInfo::dump() const {
772 PredicateInfoAnnotatedWriter Writer(this);
773 F.print(dbgs(), &Writer);
774}
775
776PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
777 FunctionAnalysisManager &AM) {
778 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
779 auto &AC = AM.getResult<AssumptionAnalysis>(F);
780 make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
781
782 return PreservedAnalyses::all();
783}
784}