Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/PredicateInfo.cpp
Line
Count
Source (jump to first uncovered line)
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
13
#include "llvm/Transforms/Utils/PredicateInfo.h"
14
#include "llvm/ADT/DenseMap.h"
15
#include "llvm/ADT/DepthFirstIterator.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"
20
#include "llvm/Analysis/AssumptionCache.h"
21
#include "llvm/Analysis/CFG.h"
22
#include "llvm/IR/AssemblyAnnotationWriter.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/Support/Debug.h"
34
#include "llvm/Support/DebugCounter.h"
35
#include "llvm/Support/FormattedStream.h"
36
#include "llvm/Transforms/Utils.h"
37
#include <algorithm>
38
#define DEBUG_TYPE "predicateinfo"
39
using namespace llvm;
40
using namespace PatternMatch;
41
using namespace llvm::PredicateInfoClasses;
42
43
11.0k
INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
44
11.0k
                      "PredicateInfo Printer", false, false)
45
11.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
46
11.0k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
47
11.0k
INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
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
147k
const BasicBlock *getBranchBlock(const PredicateBase *PB) {
59
147k
  assert(isa<PredicateWithEdge>(PB) &&
60
147k
         "Only branches and switches should have PHIOnly defs that "
61
147k
         "require branch blocks.");
62
147k
  return cast<PredicateWithEdge>(PB)->From;
63
147k
}
64
65
// Given a predicate info that is a type of branching terminator, get the
66
// branching terminator.
67
515k
static Instruction *getBranchTerminator(const PredicateBase *PB) {
68
515k
  assert(isa<PredicateWithEdge>(PB) &&
69
515k
         "Not a predicate info type we know how to get a terminator from.");
70
515k
  return cast<PredicateWithEdge>(PB)->From->getTerminator();
71
515k
}
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
3.94M
getBlockEdge(const PredicateBase *PB) {
77
3.94M
  assert(isa<PredicateWithEdge>(PB) &&
78
3.94M
         "Not a predicate info type we know how to get an edge from.");
79
3.94M
  const auto *PEdge = cast<PredicateWithEdge>(PB);
80
3.94M
  return std::make_pair(PEdge->From, PEdge->To);
81
3.94M
}
82
}
83
84
namespace llvm {
85
namespace PredicateInfoClasses {
86
enum LocalNum {
87
  // Operations that must appear first in the block.
88
  LN_First,
89
  // Operations that are somewhere in the middle of the block, and are sorted on
90
  // demand.
91
  LN_Middle,
92
  // Operations that must appear last in a block, like successor phi node uses.
93
  LN_Last
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
16.4M
                             const Value *B) {
113
16.4M
  auto *ArgA = dyn_cast_or_null<Argument>(A);
114
16.4M
  auto *ArgB = dyn_cast_or_null<Argument>(B);
115
16.4M
  if (ArgA && 
!ArgB859k
)
116
643k
    return true;
117
15.7M
  if (ArgB && 
!ArgA278k
)
118
62.2k
    return false;
119
15.7M
  if (ArgA && 
ArgB215k
)
120
215k
    return ArgA->getArgNo() < ArgB->getArgNo();
121
15.5M
  return OI.dfsBefore(cast<Instruction>(A), cast<Instruction>(B));
122
15.5M
}
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.
127
struct ValueDFS_Compare {
128
  OrderedInstructions &OI;
129
591k
  ValueDFS_Compare(OrderedInstructions &OI) : OI(OI) {}
130
131
22.1M
  bool operator()(const ValueDFS &A, const ValueDFS &B) const {
132
22.1M
    if (&A == &B)
133
0
      return false;
134
22.1M
    // The only case we can't directly compare them is when they in the same
135
22.1M
    // block, and both have localnum == middle.  In that case, we have to use
136
22.1M
    // comesbefore to see what the real ordering is, because they are in the
137
22.1M
    // same basic block.
138
22.1M
139
22.1M
    bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut);
140
22.1M
141
22.1M
    // We want to put the def that will get used for a given set of phi uses,
142
22.1M
    // before those phi uses.
143
22.1M
    // So we sort by edge, then by def.
144
22.1M
    // Note that only phi nodes uses and defs can come last.
145
22.1M
    if (SameBlock && 
A.LocalNum == LN_Last12.0M
&&
B.LocalNum == LN_Last505k
)
146
415k
      return comparePHIRelated(A, B);
147
21.7M
148
21.7M
    if (!SameBlock || 
A.LocalNum != LN_Middle11.6M
||
B.LocalNum != LN_Middle11.5M
)
149
12.9M
      return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.U) <
150
12.9M
             std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.U);
151
8.79M
    return localComesBefore(A, B);
152
8.79M
  }
153
154
  // For a phi use, or a non-materialized def, return the edge it represents.
155
  const std::pair<BasicBlock *, BasicBlock *>
156
831k
  getBlockEdge(const ValueDFS &VD) const {
157
831k
    if (!VD.Def && VD.U) {
158
175k
      auto *PHI = cast<PHINode>(VD.U->getUser());
159
175k
      return std::make_pair(PHI->getIncomingBlock(*VD.U), PHI->getParent());
160
175k
    }
161
655k
    // This is really a non-materialized def.
162
655k
    return ::getBlockEdge(VD.PInfo);
163
655k
  }
164
165
  // For two phi related values, return the ordering.
166
415k
  bool comparePHIRelated(const ValueDFS &A, const ValueDFS &B) const {
167
415k
    auto &ABlockEdge = getBlockEdge(A);
168
415k
    auto &BBlockEdge = getBlockEdge(B);
169
415k
    // Now sort by block edge and then defs before uses.
170
415k
    return std::tie(ABlockEdge, A.Def, A.U) < std::tie(BBlockEdge, B.Def, B.U);
171
415k
  }
172
173
  // Get the definition of an instruction that occurs in the middle of a block.
174
17.5M
  Value *getMiddleDef(const ValueDFS &VD) const {
175
17.5M
    if (VD.Def)
176
0
      return VD.Def;
177
17.5M
    // It's possible for the defs and uses to be null.  For branches, the local
178
17.5M
    // numbering will say the placed predicaeinfos should go first (IE
179
17.5M
    // LN_beginning), so we won't be in this function. For assumes, we will end
180
17.5M
    // up here, beause we need to order the def we will place relative to the
181
17.5M
    // assume.  So for the purpose of ordering, we pretend the def is the assume
182
17.5M
    // because that is where we will insert the info.
183
17.5M
    if (!VD.U) {
184
58
      assert(VD.PInfo &&
185
58
             "No def, no use, and no predicateinfo should not occur");
186
58
      assert(isa<PredicateAssume>(VD.PInfo) &&
187
58
             "Middle of block should only occur for assumes");
188
58
      return cast<PredicateAssume>(VD.PInfo)->AssumeInst;
189
58
    }
190
17.5M
    return nullptr;
191
17.5M
  }
192
193
  // Return either the Def, if it's not null, or the user of the Use, if the def
194
  // is null.
195
17.5M
  const Instruction *getDefOrUser(const Value *Def, const Use *U) const {
196
17.5M
    if (Def)
197
58
      return cast<Instruction>(Def);
198
17.5M
    return cast<Instruction>(U->getUser());
199
17.5M
  }
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
8.79M
  bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
204
8.79M
    auto *ADef = getMiddleDef(A);
205
8.79M
    auto *BDef = getMiddleDef(B);
206
8.79M
207
8.79M
    // See if we have real values or uses. If we have real values, we are
208
8.79M
    // guaranteed they are instructions or arguments. No matter what, we are
209
8.79M
    // guaranteed they are in the same block if they are instructions.
210
8.79M
    auto *ArgA = dyn_cast_or_null<Argument>(ADef);
211
8.79M
    auto *ArgB = dyn_cast_or_null<Argument>(BDef);
212
8.79M
213
8.79M
    if (ArgA || ArgB)
214
0
      return valueComesBefore(OI, ArgA, ArgB);
215
8.79M
216
8.79M
    auto *AInst = getDefOrUser(ADef, A.U);
217
8.79M
    auto *BInst = getDefOrUser(BDef, B.U);
218
8.79M
    return valueComesBefore(OI, AInst, BInst);
219
8.79M
  }
220
};
221
222
} // namespace PredicateInfoClasses
223
224
bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack,
225
8.75M
                                   const ValueDFS &VDUse) const {
226
8.75M
  if (Stack.empty())
227
3.43M
    return false;
228
5.32M
  // If it's a phi only use, make sure it's for this phi node edge, and that the
229
5.32M
  // use is in a phi node.  If it's anything else, and the top of the stack is
230
5.32M
  // EdgeOnly, we need to pop the stack.  We deliberately sort phi uses next to
231
5.32M
  // the defs they must go with so that we can know it's time to pop the stack
232
5.32M
  // when we hit the end of the phi uses for a given def.
233
5.32M
  if (Stack.back().EdgeOnly) {
234
2.15M
    if (!VDUse.U)
235
1.86M
      return false;
236
281k
    auto *PHI = dyn_cast<PHINode>(VDUse.U->getUser());
237
281k
    if (!PHI)
238
133k
      return false;
239
147k
    // Check edge
240
147k
    BasicBlock *EdgePred = PHI->getIncomingBlock(*VDUse.U);
241
147k
    if (EdgePred != getBranchBlock(Stack.back().PInfo))
242
1.06k
      return false;
243
146k
244
146k
    // Use dominates, which knows how to handle edge dominance.
245
146k
    return DT.dominates(getBlockEdge(Stack.back().PInfo), *VDUse.U);
246
146k
  }
247
3.16M
248
3.16M
  return (VDUse.DFSIn >= Stack.back().DFSIn &&
249
3.16M
          VDUse.DFSOut <= Stack.back().DFSOut);
250
3.16M
}
251
252
void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack,
253
5.16M
                                          const ValueDFS &VD) {
254
6.81M
  while (!Stack.empty() && 
!stackIsInScope(Stack, VD)1.84M
)
255
1.65M
    Stack.pop_back();
256
5.16M
}
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
1.51M
    Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
262
3.75M
  for (auto &U : Op->uses()) {
263
3.75M
    if (auto *I = dyn_cast<Instruction>(U.getUser())) {
264
3.75M
      ValueDFS VD;
265
3.75M
      // Put the phi node uses in the incoming block.
266
3.75M
      BasicBlock *IBlock;
267
3.75M
      if (auto *PN = dyn_cast<PHINode>(I)) {
268
221k
        IBlock = PN->getIncomingBlock(U);
269
221k
        // Make phi node users appear last in the incoming block
270
221k
        // they are from.
271
221k
        VD.LocalNum = LN_Last;
272
3.53M
      } else {
273
3.53M
        // If it's not a phi node use, it is somewhere in the middle of the
274
3.53M
        // block.
275
3.53M
        IBlock = I->getParent();
276
3.53M
        VD.LocalNum = LN_Middle;
277
3.53M
      }
278
3.75M
      DomTreeNode *DomNode = DT.getNode(IBlock);
279
3.75M
      // It's possible our use is in an unreachable block. Skip it if so.
280
3.75M
      if (!DomNode)
281
2
        continue;
282
3.75M
      VD.DFSIn = DomNode->getDFSNumIn();
283
3.75M
      VD.DFSOut = DomNode->getDFSNumOut();
284
3.75M
      VD.U = &U;
285
3.75M
      DFSOrderedSet.push_back(VD);
286
3.75M
    }
287
3.75M
  }
288
1.51M
}
289
290
// Collect relevant operations from Comparison that we may want to insert copies
291
// for.
292
917k
void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
293
917k
  auto *Op0 = Comparison->getOperand(0);
294
917k
  auto *Op1 = Comparison->getOperand(1);
295
917k
  if (Op0 == Op1)
296
3.27k
    return;
297
914k
  CmpOperands.push_back(Comparison);
298
914k
  // Only want real values, not constants.  Additionally, operands with one use
299
914k
  // are only being used in the comparison, which means they will not be useful
300
914k
  // for us to consider for predicateinfo.
301
914k
  //
302
914k
  if ((isa<Instruction>(Op0) || 
isa<Argument>(Op0)153k
) &&
!Op0->hasOneUse()902k
)
303
595k
    CmpOperands.push_back(Op0);
304
914k
  if ((isa<Instruction>(Op1) || 
isa<Argument>(Op1)711k
) &&
!Op1->hasOneUse()257k
)
305
163k
    CmpOperands.push_back(Op1);
306
914k
}
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
3.14M
                               PredicateBase *PB) {
311
3.14M
  OpsToRename.insert(Op);
312
3.14M
  auto &OperandInfo = getOrCreateValueInfo(Op);
313
3.14M
  AllInfos.push_back(PB);
314
3.14M
  OperandInfo.Infos.push_back(PB);
315
3.14M
}
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
42
                                  SmallPtrSetImpl<Value *> &OpsToRename) {
321
42
  // See if we have a comparison we support
322
42
  SmallVector<Value *, 8> CmpOperands;
323
42
  SmallVector<Value *, 2> ConditionsToProcess;
324
42
  CmpInst::Predicate Pred;
325
42
  Value *Operand = II->getOperand(0);
326
42
  if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
327
42
              m_Cmp(Pred, m_Value(), m_Value()))
328
42
          .match(II->getOperand(0))) {
329
1
    ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0));
330
1
    ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1));
331
1
    ConditionsToProcess.push_back(Operand);
332
41
  } else if (isa<CmpInst>(Operand)) {
333
30
334
30
    ConditionsToProcess.push_back(Operand);
335
30
  }
336
42
  for (auto Cond : ConditionsToProcess) {
337
33
    if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
338
32
      collectCmpOps(Cmp, CmpOperands);
339
32
      // Now add our copy infos for our operands
340
48
      for (auto *Op : CmpOperands) {
341
48
        auto *PA = new PredicateAssume(Op, II, Cmp);
342
48
        addInfoFor(OpsToRename, Op, PA);
343
48
      }
344
32
      CmpOperands.clear();
345
32
    } else 
if (auto *1
BinOp1
= dyn_cast<BinaryOperator>(Cond)) {
346
1
      // Otherwise, it should be an AND.
347
1
      assert(BinOp->getOpcode() == Instruction::And &&
348
1
             "Should have been an AND");
349
1
      auto *PA = new PredicateAssume(BinOp, II, BinOp);
350
1
      addInfoFor(OpsToRename, BinOp, PA);
351
1
    } else {
352
0
      llvm_unreachable("Unknown type of condition");
353
0
    }
354
33
  }
355
42
}
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
975k
                                  SmallPtrSetImpl<Value *> &OpsToRename) {
361
975k
  BasicBlock *FirstBB = BI->getSuccessor(0);
362
975k
  BasicBlock *SecondBB = BI->getSuccessor(1);
363
975k
  SmallVector<BasicBlock *, 2> SuccsToProcess;
364
975k
  SuccsToProcess.push_back(FirstBB);
365
975k
  SuccsToProcess.push_back(SecondBB);
366
975k
  SmallVector<Value *, 2> ConditionsToProcess;
367
975k
368
1.71M
  auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) {
369
3.42M
    for (auto *Succ : SuccsToProcess) {
370
3.42M
      // Don't try to insert on a self-edge. This is mainly because we will
371
3.42M
      // eliminate during renaming anyway.
372
3.42M
      if (Succ == BranchBB)
373
135k
        continue;
374
3.29M
      bool TakenEdge = (Succ == FirstBB);
375
3.29M
      // For and, only insert on the true edge
376
3.29M
      // For or, only insert on the false edge
377
3.29M
      if ((isAnd && 
!TakenEdge203k
) ||
(3.18M
isOr3.18M
&&
TakenEdge109k
))
378
156k
        continue;
379
3.13M
      PredicateBase *PB =
380
3.13M
          new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge);
381
3.13M
      addInfoFor(OpsToRename, Op, PB);
382
3.13M
      if (!Succ->getSinglePredecessor())
383
1.30M
        EdgeUsesOnly.insert({BranchBB, Succ});
384
3.13M
    }
385
1.71M
  };
386
975k
387
975k
  // Match combinations of conditions.
388
975k
  CmpInst::Predicate Pred;
389
975k
  bool isAnd = false;
390
975k
  bool isOr = false;
391
975k
  SmallVector<Value *, 8> CmpOperands;
392
975k
  if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
393
975k
                                      m_Cmp(Pred, m_Value(), m_Value()))) ||
394
975k
      match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
395
947k
                                     m_Cmp(Pred, m_Value(), m_Value())))) {
396
41.1k
    auto *BinOp = cast<BinaryOperator>(BI->getCondition());
397
41.1k
    if (BinOp->getOpcode() == Instruction::And)
398
28.1k
      isAnd = true;
399
13.0k
    else if (BinOp->getOpcode() == Instruction::Or)
400
13.0k
      isOr = true;
401
41.1k
    ConditionsToProcess.push_back(BinOp->getOperand(0));
402
41.1k
    ConditionsToProcess.push_back(BinOp->getOperand(1));
403
41.1k
    ConditionsToProcess.push_back(BI->getCondition());
404
934k
  } else if (isa<CmpInst>(BI->getCondition())) {
405
835k
    ConditionsToProcess.push_back(BI->getCondition());
406
835k
  }
407
975k
  for (auto Cond : ConditionsToProcess) {
408
958k
    if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
409
917k
      collectCmpOps(Cmp, CmpOperands);
410
917k
      // Now add our copy infos for our operands
411
917k
      for (auto *Op : CmpOperands)
412
1.67M
        InsertHelper(Op, isAnd, isOr, Cmp);
413
917k
    } else 
if (auto *41.1k
BinOp41.1k
= dyn_cast<BinaryOperator>(Cond)) {
414
41.1k
      // This must be an AND or an OR.
415
41.1k
      assert((BinOp->getOpcode() == Instruction::And ||
416
41.1k
              BinOp->getOpcode() == Instruction::Or) &&
417
41.1k
             "Should have been an AND or an OR");
418
41.1k
      // The actual value of the binop is not subject to the same restrictions
419
41.1k
      // as the comparison. It's either true or false on the true/false branch.
420
41.1k
      InsertHelper(BinOp, false, false, BinOp);
421
41.1k
    } else {
422
0
      llvm_unreachable("Unknown type of condition");
423
0
    }
424
958k
    CmpOperands.clear();
425
958k
  }
426
975k
}
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
13.4k
                                  SmallPtrSetImpl<Value *> &OpsToRename) {
431
13.4k
  Value *Op = SI->getCondition();
432
13.4k
  if ((!isa<Instruction>(Op) && 
!isa<Argument>(Op)1.04k
) ||
Op->hasOneUse()13.3k
)
433
9.76k
    return;
434
3.64k
435
3.64k
  // Remember how many outgoing edges there are to every successor.
436
3.64k
  SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
437
20.2k
  for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; 
++i16.6k
) {
438
16.6k
    BasicBlock *TargetBlock = SI->getSuccessor(i);
439
16.6k
    ++SwitchEdges[TargetBlock];
440
16.6k
  }
441
3.64k
442
3.64k
  // Now propagate info for each case value
443
12.9k
  for (auto C : SI->cases()) {
444
12.9k
    BasicBlock *TargetBlock = C.getCaseSuccessor();
445
12.9k
    if (SwitchEdges.lookup(TargetBlock) == 1) {
446
10.8k
      PredicateSwitch *PS = new PredicateSwitch(
447
10.8k
          Op, SI->getParent(), TargetBlock, C.getCaseValue(), SI);
448
10.8k
      addInfoFor(OpsToRename, Op, PS);
449
10.8k
      if (!TargetBlock->getSinglePredecessor())
450
285
        EdgeUsesOnly.insert({BranchBB, TargetBlock});
451
10.8k
    }
452
12.9k
  }
453
3.64k
}
454
455
// Build predicate info for our function
456
591k
void PredicateInfo::buildPredicateInfo() {
457
591k
  DT.updateDFSNumbers();
458
591k
  // Collect operands to rename from all conditional branch terminators, as well
459
591k
  // as assume statements.
460
591k
  SmallPtrSet<Value *, 8> OpsToRename;
461
2.42M
  for (auto DTN : depth_first(DT.getRootNode())) {
462
2.42M
    BasicBlock *BranchBB = DTN->getBlock();
463
2.42M
    if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
464
1.75M
      if (!BI->isConditional())
465
780k
        continue;
466
975k
      // Can't insert conditional information if they all go to the same place.
467
975k
      if (BI->getSuccessor(0) == BI->getSuccessor(1))
468
16
        continue;
469
975k
      processBranch(BI, BranchBB, OpsToRename);
470
975k
    } else 
if (auto *667k
SI667k
= dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
471
13.4k
      processSwitch(SI, BranchBB, OpsToRename);
472
13.4k
    }
473
2.42M
  }
474
591k
  for (auto &Assume : AC.assumptions()) {
475
44
    if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
476
44
      if (DT.isReachableFromEntry(II->getParent()))
477
42
        processAssume(II, II->getParent(), OpsToRename);
478
44
  }
479
591k
  // Now rename all our operations.
480
591k
  renameUses(OpsToRename);
481
591k
}
482
483
// Create a ssa_copy declaration with custom mangling, because
484
// Intrinsic::getDeclaration does not handle overloaded unnamed types properly:
485
// all unnamed types get mangled to the same string. We use the pointer
486
// to the type as name here, as it guarantees unique names for different
487
// types and we remove the declarations when destroying PredicateInfo.
488
// It is a workaround for PR38117, because solving it in a fully general way is
489
// tricky (FIXME).
490
515k
static Function *getCopyDeclaration(Module *M, Type *Ty) {
491
515k
  std::string Name = "llvm.ssa.copy." + utostr((uintptr_t) Ty);
492
515k
  return cast<Function>(
493
515k
      M->getOrInsertFunction(Name,
494
515k
                             getType(M->getContext(), Intrinsic::ssa_copy, Ty))
495
515k
          .getCallee());
496
515k
}
497
498
// Given the renaming stack, make all the operands currently on the stack real
499
// by inserting them into the IR.  Return the last operation's value.
500
Value *PredicateInfo::materializeStack(unsigned int &Counter,
501
                                       ValueDFSStack &RenameStack,
502
509k
                                       Value *OrigOp) {
503
509k
  // Find the first thing we have to materialize
504
509k
  auto RevIter = RenameStack.rbegin();
505
1.02M
  for (; RevIter != RenameStack.rend(); 
++RevIter515k
)
506
548k
    if (RevIter->Def)
507
32.8k
      break;
508
509k
509
509k
  size_t Start = RevIter - RenameStack.rbegin();
510
509k
  // The maximum number of things we should be trying to materialize at once
511
509k
  // right now is 4, depending on if we had an assume, a branch, and both used
512
509k
  // and of conditions.
513
509k
  for (auto RenameIter = RenameStack.end() - Start;
514
1.02M
       RenameIter != RenameStack.end(); 
++RenameIter515k
) {
515
515k
    auto *Op =
516
515k
        RenameIter == RenameStack.begin() ? 
OrigOp477k
:
(RenameIter - 1)->Def38.9k
;
517
515k
    ValueDFS &Result = *RenameIter;
518
515k
    auto *ValInfo = Result.PInfo;
519
515k
    // For edge predicates, we can just place the operand in the block before
520
515k
    // the terminator.  For assume, we have to place it right before the assume
521
515k
    // to ensure we dominate all of our uses.  Always insert right before the
522
515k
    // relevant instruction (terminator, assume), so that we insert in proper
523
515k
    // order in the case of multiple predicateinfo in the same block.
524
515k
    if (isa<PredicateWithEdge>(ValInfo)) {
525
515k
      IRBuilder<> B(getBranchTerminator(ValInfo));
526
515k
      Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
527
515k
      if (empty(IF->users()))
528
40.2k
        CreatedDeclarations.insert(IF);
529
515k
      CallInst *PIC =
530
515k
          B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
531
515k
      PredicateMap.insert({PIC, ValInfo});
532
515k
      Result.Def = PIC;
533
515k
    } else {
534
45
      auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
535
45
      assert(PAssume &&
536
45
             "Should not have gotten here without it being an assume");
537
45
      IRBuilder<> B(PAssume->AssumeInst);
538
45
      Function *IF = getCopyDeclaration(F.getParent(), Op->getType());
539
45
      if (empty(IF->users()))
540
40
        CreatedDeclarations.insert(IF);
541
45
      CallInst *PIC = B.CreateCall(IF, Op);
542
45
      PredicateMap.insert({PIC, ValInfo});
543
45
      Result.Def = PIC;
544
45
    }
545
515k
  }
546
509k
  return RenameStack.back().Def;
547
509k
}
548
549
// Instead of the standard SSA renaming algorithm, which is O(Number of
550
// instructions), and walks the entire dominator tree, we walk only the defs +
551
// uses.  The standard SSA renaming algorithm does not really rely on the
552
// dominator tree except to order the stack push/pops of the renaming stacks, so
553
// that defs end up getting pushed before hitting the correct uses.  This does
554
// not require the dominator tree, only the *order* of the dominator tree. The
555
// complete and correct ordering of the defs and uses, in dominator tree is
556
// contained in the DFS numbering of the dominator tree. So we sort the defs and
557
// uses into the DFS ordering, and then just use the renaming stack as per
558
// normal, pushing when we hit a def (which is a predicateinfo instruction),
559
// popping when we are out of the dfs scope for that def, and replacing any uses
560
// with top of stack if it exists.  In order to handle liveness without
561
// propagating liveness info, we don't actually insert the predicateinfo
562
// instruction def until we see a use that it would dominate.  Once we see such
563
// a use, we materialize the predicateinfo instruction in the right place and
564
// use it.
565
//
566
// TODO: Use this algorithm to perform fast single-variable renaming in
567
// promotememtoreg and memoryssa.
568
591k
void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpSet) {
569
591k
  // Sort OpsToRename since we are going to iterate it.
570
591k
  SmallVector<Value *, 8> OpsToRename(OpSet.begin(), OpSet.end());
571
7.63M
  auto Comparator = [&](const Value *A, const Value *B) {
572
7.63M
    return valueComesBefore(OI, A, B);
573
7.63M
  };
574
591k
  llvm::sort(OpsToRename, Comparator);
575
591k
  ValueDFS_Compare Compare(OI);
576
591k
  // Compute liveness, and rename in O(uses) per Op.
577
1.51M
  for (auto *Op : OpsToRename) {
578
1.51M
    LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n");
579
1.51M
    unsigned Counter = 0;
580
1.51M
    SmallVector<ValueDFS, 16> OrderedUses;
581
1.51M
    const auto &ValueInfo = getValueInfo(Op);
582
1.51M
    // Insert the possible copies into the def/use list.
583
1.51M
    // They will become real copies if we find a real use for them, and never
584
1.51M
    // created otherwise.
585
3.14M
    for (auto &PossibleCopy : ValueInfo.Infos) {
586
3.14M
      ValueDFS VD;
587
3.14M
      // Determine where we are going to place the copy by the copy type.
588
3.14M
      // The predicate info for branches always come first, they will get
589
3.14M
      // materialized in the split block at the top of the block.
590
3.14M
      // The predicate info for assumes will be somewhere in the middle,
591
3.14M
      // it will get materialized in front of the assume.
592
3.14M
      if (const auto *PAssume = dyn_cast<PredicateAssume>(PossibleCopy)) {
593
49
        VD.LocalNum = LN_Middle;
594
49
        DomTreeNode *DomNode = DT.getNode(PAssume->AssumeInst->getParent());
595
49
        if (!DomNode)
596
0
          continue;
597
49
        VD.DFSIn = DomNode->getDFSNumIn();
598
49
        VD.DFSOut = DomNode->getDFSNumOut();
599
49
        VD.PInfo = PossibleCopy;
600
49
        OrderedUses.push_back(VD);
601
3.14M
      } else if (isa<PredicateWithEdge>(PossibleCopy)) {
602
3.14M
        // If we can only do phi uses, we treat it like it's in the branch
603
3.14M
        // block, and handle it specially. We know that it goes last, and only
604
3.14M
        // dominate phi uses.
605
3.14M
        auto BlockEdge = getBlockEdge(PossibleCopy);
606
3.14M
        if (EdgeUsesOnly.count(BlockEdge)) {
607
1.30M
          VD.LocalNum = LN_Last;
608
1.30M
          auto *DomNode = DT.getNode(BlockEdge.first);
609
1.30M
          if (DomNode) {
610
1.30M
            VD.DFSIn = DomNode->getDFSNumIn();
611
1.30M
            VD.DFSOut = DomNode->getDFSNumOut();
612
1.30M
            VD.PInfo = PossibleCopy;
613
1.30M
            VD.EdgeOnly = true;
614
1.30M
            OrderedUses.push_back(VD);
615
1.30M
          }
616
1.84M
        } else {
617
1.84M
          // Otherwise, we are in the split block (even though we perform
618
1.84M
          // insertion in the branch block).
619
1.84M
          // Insert a possible copy at the split block and before the branch.
620
1.84M
          VD.LocalNum = LN_First;
621
1.84M
          auto *DomNode = DT.getNode(BlockEdge.second);
622
1.84M
          if (DomNode) {
623
1.84M
            VD.DFSIn = DomNode->getDFSNumIn();
624
1.84M
            VD.DFSOut = DomNode->getDFSNumOut();
625
1.84M
            VD.PInfo = PossibleCopy;
626
1.84M
            OrderedUses.push_back(VD);
627
1.84M
          }
628
1.84M
        }
629
3.14M
      }
630
3.14M
    }
631
1.51M
632
1.51M
    convertUsesToDFSOrdered(Op, OrderedUses);
633
1.51M
    // Here we require a stable sort because we do not bother to try to
634
1.51M
    // assign an order to the operands the uses represent. Thus, two
635
1.51M
    // uses in the same instruction do not have a strict sort order
636
1.51M
    // currently and will be considered equal. We could get rid of the
637
1.51M
    // stable sort by creating one if we wanted.
638
1.51M
    llvm::stable_sort(OrderedUses, Compare);
639
1.51M
    SmallVector<ValueDFS, 8> RenameStack;
640
1.51M
    // For each use, sorted into dfs order, push values and replaces uses with
641
1.51M
    // top of stack, which will represent the reaching def.
642
6.90M
    for (auto &VD : OrderedUses) {
643
6.90M
      // We currently do not materialize copy over copy, but we should decide if
644
6.90M
      // we want to.
645
6.90M
      bool PossibleCopy = VD.PInfo != nullptr;
646
6.90M
      if (RenameStack.empty()) {
647
3.43M
        LLVM_DEBUG(dbgs() << "Rename Stack is empty\n");
648
3.47M
      } else {
649
3.47M
        LLVM_DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
650
3.47M
                          << RenameStack.back().DFSIn << ","
651
3.47M
                          << RenameStack.back().DFSOut << ")\n");
652
3.47M
      }
653
6.90M
654
6.90M
      LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
655
6.90M
                        << VD.DFSOut << ")\n");
656
6.90M
657
6.90M
      bool ShouldPush = (VD.Def || PossibleCopy);
658
6.90M
      bool OutOfScope = !stackIsInScope(RenameStack, VD);
659
6.90M
      if (OutOfScope || 
ShouldPush1.83M
) {
660
5.16M
        // Sync to our current scope.
661
5.16M
        popStackUntilDFSScope(RenameStack, VD);
662
5.16M
        if (ShouldPush) {
663
3.14M
          RenameStack.push_back(VD);
664
3.14M
        }
665
5.16M
      }
666
6.90M
      // If we get to this point, and the stack is empty we must have a use
667
6.90M
      // with no renaming needed, just skip it.
668
6.90M
      if (RenameStack.empty())
669
2.00M
        continue;
670
4.90M
      // Skip values, only want to rename the uses
671
4.90M
      if (VD.Def || PossibleCopy)
672
3.14M
        continue;
673
1.75M
      if (!DebugCounter::shouldExecute(RenameCounter)) {
674
0
        LLVM_DEBUG(dbgs() << "Skipping execution due to debug counter\n");
675
0
        continue;
676
0
      }
677
1.75M
      ValueDFS &Result = RenameStack.back();
678
1.75M
679
1.75M
      // If the possible copy dominates something, materialize our stack up to
680
1.75M
      // this point. This ensures every comparison that affects our operation
681
1.75M
      // ends up with predicateinfo.
682
1.75M
      if (!Result.Def)
683
509k
        Result.Def = materializeStack(Counter, RenameStack, Op);
684
1.75M
685
1.75M
      LLVM_DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
686
1.75M
                        << *VD.U->get() << " in " << *(VD.U->getUser())
687
1.75M
                        << "\n");
688
1.75M
      assert(DT.dominates(cast<Instruction>(Result.Def), *VD.U) &&
689
1.75M
             "Predicateinfo def should have dominated this use");
690
1.75M
      VD.U->set(Result.Def);
691
1.75M
    }
692
1.51M
  }
693
591k
}
694
695
3.14M
PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
696
3.14M
  auto OIN = ValueInfoNums.find(Operand);
697
3.14M
  if (OIN == ValueInfoNums.end()) {
698
1.51M
    // This will grow it
699
1.51M
    ValueInfos.resize(ValueInfos.size() + 1);
700
1.51M
    // This will use the new size and give us a 0 based number of the info
701
1.51M
    auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
702
1.51M
    assert(InsertResult.second && "Value info number already existed?");
703
1.51M
    return ValueInfos[InsertResult.first->second];
704
1.51M
  }
705
1.63M
  return ValueInfos[OIN->second];
706
1.63M
}
707
708
const PredicateInfo::ValueInfo &
709
1.51M
PredicateInfo::getValueInfo(Value *Operand) const {
710
1.51M
  auto OINI = ValueInfoNums.lookup(Operand);
711
1.51M
  assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
712
1.51M
  assert(OINI < ValueInfos.size() &&
713
1.51M
         "Value Info Number greater than size of Value Info Table");
714
1.51M
  return ValueInfos[OINI];
715
1.51M
}
716
717
PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
718
                             AssumptionCache &AC)
719
591k
    : F(F), DT(DT), AC(AC), OI(&DT) {
720
591k
  // Push an empty operand info so that we can detect 0 as not finding one
721
591k
  ValueInfos.resize(1);
722
591k
  buildPredicateInfo();
723
591k
}
724
725
// Remove all declarations we created . The PredicateInfo consumers are
726
// responsible for remove the ssa_copy calls created.
727
591k
PredicateInfo::~PredicateInfo() {
728
591k
  // Collect function pointers in set first, as SmallSet uses a SmallVector
729
591k
  // internally and we have to remove the asserting value handles first.
730
591k
  SmallPtrSet<Function *, 20> FunctionPtrs;
731
591k
  for (auto &F : CreatedDeclarations)
732
40.3k
    FunctionPtrs.insert(&*F);
733
591k
  CreatedDeclarations.clear();
734
591k
735
591k
  for (Function *F : FunctionPtrs) {
736
40.3k
    assert(F->user_begin() == F->user_end() &&
737
40.3k
           "PredicateInfo consumer did not remove all SSA copies.");
738
40.3k
    F->eraseFromParent();
739
40.3k
  }
740
591k
}
741
742
0
void PredicateInfo::verifyPredicateInfo() const {}
743
744
char PredicateInfoPrinterLegacyPass::ID = 0;
745
746
PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass()
747
8
    : FunctionPass(ID) {
748
8
  initializePredicateInfoPrinterLegacyPassPass(
749
8
      *PassRegistry::getPassRegistry());
750
8
}
751
752
8
void PredicateInfoPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
753
8
  AU.setPreservesAll();
754
8
  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
755
8
  AU.addRequired<AssumptionCacheTracker>();
756
8
}
757
758
// Replace ssa_copy calls created by PredicateInfo with their operand.
759
34
static void replaceCreatedSSACopys(PredicateInfo &PredInfo, Function &F) {
760
420
  for (auto I = inst_begin(F), E = inst_end(F); I != E;) {
761
386
    Instruction *Inst = &*I++;
762
386
    const auto *PI = PredInfo.getPredicateInfoFor(Inst);
763
386
    auto *II = dyn_cast<IntrinsicInst>(Inst);
764
386
    if (!PI || 
!II68
||
II->getIntrinsicID() != Intrinsic::ssa_copy68
)
765
318
      continue;
766
68
767
68
    Inst->replaceAllUsesWith(II->getOperand(0));
768
68
    Inst->eraseFromParent();
769
68
  }
770
34
}
771
772
34
bool PredicateInfoPrinterLegacyPass::runOnFunction(Function &F) {
773
34
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
774
34
  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
775
34
  auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
776
34
  PredInfo->print(dbgs());
777
34
  if (VerifyPredicateInfo)
778
0
    PredInfo->verifyPredicateInfo();
779
34
780
34
  replaceCreatedSSACopys(*PredInfo, F);
781
34
  return false;
782
34
}
783
784
PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
785
0
                                                FunctionAnalysisManager &AM) {
786
0
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
787
0
  auto &AC = AM.getResult<AssumptionAnalysis>(F);
788
0
  OS << "PredicateInfo for function: " << F.getName() << "\n";
789
0
  auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
790
0
  PredInfo->print(OS);
791
0
792
0
  replaceCreatedSSACopys(*PredInfo, F);
793
0
  return PreservedAnalyses::all();
794
0
}
795
796
/// An assembly annotator class to print PredicateInfo information in
797
/// comments.
798
class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
799
  friend class PredicateInfo;
800
  const PredicateInfo *PredInfo;
801
802
public:
803
34
  PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
804
805
  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
806
131
                                        formatted_raw_ostream &OS) {}
807
808
  virtual void emitInstructionAnnot(const Instruction *I,
809
386
                                    formatted_raw_ostream &OS) {
810
386
    if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
811
68
      OS << "; Has predicate info\n";
812
68
      if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
813
61
        OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
814
61
           << " Comparison:" << *PB->Condition << " Edge: [";
815
61
        PB->From->printAsOperand(OS);
816
61
        OS << ",";
817
61
        PB->To->printAsOperand(OS);
818
61
        OS << "] }\n";
819
61
      } else 
if (const auto *7
PS7
= dyn_cast<PredicateSwitch>(PI)) {
820
2
        OS << "; switch predicate info { CaseValue: " << *PS->CaseValue
821
2
           << " Switch:" << *PS->Switch << " Edge: [";
822
2
        PS->From->printAsOperand(OS);
823
2
        OS << ",";
824
2
        PS->To->printAsOperand(OS);
825
2
        OS << "] }\n";
826
5
      } else if (const auto *PA = dyn_cast<PredicateAssume>(PI)) {
827
5
        OS << "; assume predicate info {"
828
5
           << " Comparison:" << *PA->Condition << " }\n";
829
5
      }
830
68
    }
831
386
  }
832
};
833
834
34
void PredicateInfo::print(raw_ostream &OS) const {
835
34
  PredicateInfoAnnotatedWriter Writer(this);
836
34
  F.print(OS, &Writer);
837
34
}
838
839
0
void PredicateInfo::dump() const {
840
0
  PredicateInfoAnnotatedWriter Writer(this);
841
0
  F.print(dbgs(), &Writer);
842
0
}
843
844
PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
845
0
                                                 FunctionAnalysisManager &AM) {
846
0
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
847
0
  auto &AC = AM.getResult<AssumptionAnalysis>(F);
848
0
  make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
849
0
850
0
  return PreservedAnalyses::all();
851
0
}
852
}