Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/MustExecute.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
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
#include "llvm/Analysis/MustExecute.h"
10
#include "llvm/Analysis/InstructionSimplify.h"
11
#include "llvm/Analysis/LoopInfo.h"
12
#include "llvm/Analysis/Passes.h"
13
#include "llvm/Analysis/ValueTracking.h"
14
#include "llvm/IR/AssemblyAnnotationWriter.h"
15
#include "llvm/IR/DataLayout.h"
16
#include "llvm/IR/InstIterator.h"
17
#include "llvm/IR/LLVMContext.h"
18
#include "llvm/IR/Module.h"
19
#include "llvm/Support/ErrorHandling.h"
20
#include "llvm/Support/FormattedStream.h"
21
#include "llvm/Support/raw_ostream.h"
22
using namespace llvm;
23
24
const DenseMap<BasicBlock *, ColorVector> &
25
13.2M
LoopSafetyInfo::getBlockColors() const {
26
13.2M
  return BlockColors;
27
13.2M
}
28
29
6
void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
30
6
  ColorVector &ColorsForNewBlock = BlockColors[New];
31
6
  ColorVector &ColorsForOldBlock = BlockColors[Old];
32
6
  ColorsForNewBlock = ColorsForOldBlock;
33
6
}
34
35
81
bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
36
81
  (void)BB;
37
81
  return anyBlockMayThrow();
38
81
}
39
40
78.1k
bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
41
78.1k
  return MayThrow;
42
78.1k
}
43
44
78.1k
void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
45
78.1k
  assert(CurLoop != nullptr && "CurLoop can't be null");
46
78.1k
  BasicBlock *Header = CurLoop->getHeader();
47
78.1k
  // Iterate over header and compute safety info.
48
78.1k
  HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
49
78.1k
  MayThrow = HeaderMayThrow;
50
78.1k
  // Iterate over loop instructions and compute safety info.
51
78.1k
  // Skip header as it has been computed and stored in HeaderMayThrow.
52
78.1k
  // The first block in loopinfo.Blocks is guaranteed to be the header.
53
78.1k
  assert(Header == *CurLoop->getBlocks().begin() &&
54
78.1k
         "First block must be header");
55
78.1k
  for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
56
78.1k
                            BBE = CurLoop->block_end();
57
136k
       (BB != BBE) && 
!MayThrow63.7k
;
++BB58.8k
)
58
58.8k
    MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
59
78.1k
60
78.1k
  computeBlockColors(CurLoop);
61
78.1k
}
62
63
64.6k
bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
64
64.6k
  return ICF.hasICF(BB);
65
64.6k
}
66
67
8.37k
bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
68
8.37k
  return MayThrow;
69
8.37k
}
70
71
608k
void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
72
608k
  assert(CurLoop != nullptr && "CurLoop can't be null");
73
608k
  ICF.clear();
74
608k
  MW.clear();
75
608k
  MayThrow = false;
76
608k
  // Figure out the fact that at least one block may throw.
77
608k
  for (auto &BB : CurLoop->blocks())
78
1.37M
    if (ICF.hasICF(&*BB)) {
79
272k
      MayThrow = true;
80
272k
      break;
81
272k
    }
82
608k
  computeBlockColors(CurLoop);
83
608k
}
84
85
void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
86
188k
                                            const BasicBlock *BB) {
87
188k
  ICF.insertInstructionTo(Inst, BB);
88
188k
  MW.insertInstructionTo(Inst, BB);
89
188k
}
90
91
221k
void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
92
221k
  ICF.removeInstruction(Inst);
93
221k
  MW.removeInstruction(Inst);
94
221k
}
95
96
686k
void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
97
686k
  // Compute funclet colors if we might sink/hoist in a function with a funclet
98
686k
  // personality routine.
99
686k
  Function *Fn = CurLoop->getHeader()->getParent();
100
686k
  if (Fn->hasPersonalityFn())
101
44.0k
    if (Constant *PersonalityFn = Fn->getPersonalityFn())
102
44.0k
      if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
103
16
        BlockColors = colorEHFunclets(*Fn);
104
686k
}
105
106
/// Return true if we can prove that the given ExitBlock is not reached on the
107
/// first iteration of the given loop.  That is, the backedge of the loop must
108
/// be executed before the ExitBlock is executed in any dynamic execution trace.
109
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
110
                                           const DominatorTree *DT,
111
3.43k
                                           const Loop *CurLoop) {
112
3.43k
  auto *CondExitBlock = ExitBlock->getSinglePredecessor();
113
3.43k
  if (!CondExitBlock)
114
1.12k
    // expect unique exits
115
1.12k
    return false;
116
2.30k
  assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
117
2.30k
  auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
118
2.30k
  if (!BI || 
!BI->isConditional()2.27k
)
119
33
    return false;
120
2.27k
  // If condition is constant and false leads to ExitBlock then we always
121
2.27k
  // execute the true branch.
122
2.27k
  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
123
151
    return BI->getSuccessor(Cond->getZExtValue() ? 
1114
:
037
) == ExitBlock;
124
2.12k
  auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
125
2.12k
  if (!Cond)
126
102
    return false;
127
2.02k
  // todo: this would be a lot more powerful if we used scev, but all the
128
2.02k
  // plumbing is currently missing to pass a pointer in from the pass
129
2.02k
  // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
130
2.02k
  auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
131
2.02k
  auto *RHS = Cond->getOperand(1);
132
2.02k
  if (!LHS || 
LHS->getParent() != CurLoop->getHeader()329
)
133
1.82k
    return false;
134
201
  auto DL = ExitBlock->getModule()->getDataLayout();
135
201
  auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
136
201
  auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
137
201
                                          IVStart, RHS,
138
201
                                          {DL, /*TLI*/ nullptr,
139
201
                                              DT, /*AC*/ nullptr, BI});
140
201
  auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
141
201
  if (!SimpleCst)
142
195
    return false;
143
6
  if (ExitBlock == BI->getSuccessor(0))
144
1
    return SimpleCst->isZeroValue();
145
5
  assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
146
5
  return SimpleCst->isAllOnesValue();
147
5
}
148
149
/// Collect all blocks from \p CurLoop which lie on all possible paths from
150
/// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
151
/// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
152
static void collectTransitivePredecessors(
153
    const Loop *CurLoop, const BasicBlock *BB,
154
23.7k
    SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
155
23.7k
  assert(Predecessors.empty() && "Garbage in predecessors set?");
156
23.7k
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
157
23.7k
  if (BB == CurLoop->getHeader())
158
0
    return;
159
23.7k
  SmallVector<const BasicBlock *, 4> WorkList;
160
29.7k
  for (auto *Pred : predecessors(BB)) {
161
29.7k
    Predecessors.insert(Pred);
162
29.7k
    WorkList.push_back(Pred);
163
29.7k
  }
164
145k
  while (!WorkList.empty()) {
165
121k
    auto *Pred = WorkList.pop_back_val();
166
121k
    assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
167
121k
    // We are not interested in backedges and we don't want to leave loop.
168
121k
    if (Pred == CurLoop->getHeader())
169
23.7k
      continue;
170
98.0k
    // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
171
98.0k
    // blocks of this inner loop, even those that are always executed AFTER the
172
98.0k
    // BB. It may make our analysis more conservative than it could be, see test
173
98.0k
    // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
174
98.0k
    // We can ignore backedge of all loops containing BB to get a sligtly more
175
98.0k
    // optimistic result.
176
98.0k
    for (auto *PredPred : predecessors(Pred))
177
142k
      if (Predecessors.insert(PredPred).second)
178
92.1k
        WorkList.push_back(PredPred);
179
98.0k
  }
180
23.7k
}
181
182
bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
183
                                             const BasicBlock *BB,
184
47.6k
                                             const DominatorTree *DT) const {
185
47.6k
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
186
47.6k
187
47.6k
  // Fast path: header is always reached once the loop is entered.
188
47.6k
  if (BB == CurLoop->getHeader())
189
23.9k
    return true;
190
23.7k
191
23.7k
  // Collect all transitive predecessors of BB in the same loop. This set will
192
23.7k
  // be a subset of the blocks within the loop.
193
23.7k
  SmallPtrSet<const BasicBlock *, 4> Predecessors;
194
23.7k
  collectTransitivePredecessors(CurLoop, BB, Predecessors);
195
23.7k
196
23.7k
  // Make sure that all successors of, all predecessors of BB which are not
197
23.7k
  // dominated by BB, are either:
198
23.7k
  // 1) BB,
199
23.7k
  // 2) Also predecessors of BB,
200
23.7k
  // 3) Exit blocks which are not taken on 1st iteration.
201
23.7k
  // Memoize blocks we've already checked.
202
23.7k
  SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
203
64.6k
  for (auto *Pred : Predecessors) {
204
64.6k
    // Predecessor block may throw, so it has a side exit.
205
64.6k
    if (blockMayThrow(Pred))
206
1.34k
      return false;
207
63.3k
208
63.3k
    // BB dominates Pred, so if Pred runs, BB must run.
209
63.3k
    // This is true when Pred is a loop latch.
210
63.3k
    if (DT->dominates(BB, Pred))
211
1.54k
      continue;
212
61.7k
213
61.7k
    for (auto *Succ : successors(Pred))
214
92.2k
      if (CheckedSuccessors.insert(Succ).second &&
215
92.2k
          
Succ != BB73.5k
&&
!Predecessors.count(Succ)59.6k
)
216
17.0k
        // By discharging conditions that are not executed on the 1st iteration,
217
17.0k
        // we guarantee that *at least* on the first iteration all paths from
218
17.0k
        // header that *may* execute will lead us to the block of interest. So
219
17.0k
        // that if we had virtually peeled one iteration away, in this peeled
220
17.0k
        // iteration the set of predecessors would contain only paths from
221
17.0k
        // header to BB without any exiting edges that may execute.
222
17.0k
        //
223
17.0k
        // TODO: We only do it for exiting edges currently. We could use the
224
17.0k
        // same function to skip some of the edges within the loop if we know
225
17.0k
        // that they will not be taken on the 1st iteration.
226
17.0k
        //
227
17.0k
        // TODO: If we somehow know the number of iterations in loop, the same
228
17.0k
        // check may be done for any arbitrary N-th iteration as long as N is
229
17.0k
        // not greater than minimum number of iterations in this loop.
230
17.0k
        if (CurLoop->contains(Succ) ||
231
17.0k
            
!CanProveNotTakenFirstIteration(Succ, DT, CurLoop)3.43k
)
232
17.0k
          return false;
233
61.7k
  }
234
23.7k
235
23.7k
  // All predecessors can only lead us to BB.
236
23.7k
  
return true5.40k
;
237
23.7k
}
238
239
/// Returns true if the instruction in a loop is guaranteed to execute at least
240
/// once.
241
bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
242
                                                 const DominatorTree *DT,
243
105
                                                 const Loop *CurLoop) const {
244
105
  // If the instruction is in the header block for the loop (which is very
245
105
  // common), it is always guaranteed to dominate the exit blocks.  Since this
246
105
  // is a common case, and can save some work, check it now.
247
105
  if (Inst.getParent() == CurLoop->getHeader())
248
39
    // If there's a throw in the header block, we can't guarantee we'll reach
249
39
    // Inst unless we can prove that Inst comes before the potential implicit
250
39
    // exit.  At the moment, we use a (cheap) hack for the common case where
251
39
    // the instruction of interest is the first one in the block.
252
39
    return !HeaderMayThrow ||
253
39
           
Inst.getParent()->getFirstNonPHIOrDbg() == &Inst10
;
254
66
255
66
  // If there is a path from header to exit or latch that doesn't lead to our
256
66
  // instruction's block, return false.
257
66
  return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
258
66
}
259
260
bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
261
                                              const DominatorTree *DT,
262
49.4k
                                              const Loop *CurLoop) const {
263
49.4k
  return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
264
49.4k
         
allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT)47.6k
;
265
49.4k
}
266
267
bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
268
12
                                                 const Loop *CurLoop) const {
269
12
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
270
12
271
12
  // Fast path: there are no instructions before header.
272
12
  if (BB == CurLoop->getHeader())
273
12
    return true;
274
0
275
0
  // Collect all transitive predecessors of BB in the same loop. This set will
276
0
  // be a subset of the blocks within the loop.
277
0
  SmallPtrSet<const BasicBlock *, 4> Predecessors;
278
0
  collectTransitivePredecessors(CurLoop, BB, Predecessors);
279
0
  // Find if there any instruction in either predecessor that could write
280
0
  // to memory.
281
0
  for (auto *Pred : Predecessors)
282
0
    if (MW.mayWriteToMemory(Pred))
283
0
      return false;
284
0
  return true;
285
0
}
286
287
bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
288
19
                                                 const Loop *CurLoop) const {
289
19
  auto *BB = I.getParent();
290
19
  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
291
19
  return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
292
19
         
doesNotWriteMemoryBefore(BB, CurLoop)12
;
293
19
}
294
295
namespace {
296
  struct MustExecutePrinter : public FunctionPass {
297
298
    static char ID; // Pass identification, replacement for typeid
299
3
    MustExecutePrinter() : FunctionPass(ID) {
300
3
      initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
301
3
    }
302
3
    void getAnalysisUsage(AnalysisUsage &AU) const override {
303
3
      AU.setPreservesAll();
304
3
      AU.addRequired<DominatorTreeWrapperPass>();
305
3
      AU.addRequired<LoopInfoWrapperPass>();
306
3
    }
307
    bool runOnFunction(Function &F) override;
308
  };
309
}
310
311
char MustExecutePrinter::ID = 0;
312
11.0k
INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
313
11.0k
                      "Instructions which execute on loop entry", false, true)
314
11.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
315
11.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
316
11.0k
INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
317
                    "Instructions which execute on loop entry", false, true)
318
319
0
FunctionPass *llvm::createMustExecutePrinter() {
320
0
  return new MustExecutePrinter();
321
0
}
322
323
67
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
324
67
  // TODO: merge these two routines.  For the moment, we display the best
325
67
  // result obtained by *either* implementation.  This is a bit unfair since no
326
67
  // caller actually gets the full power at the moment.
327
67
  SimpleLoopSafetyInfo LSI;
328
67
  LSI.computeLoopSafetyInfo(L);
329
67
  return LSI.isGuaranteedToExecute(I, DT, L) ||
330
67
    
isGuaranteedToExecuteForEveryIteration(&I, L)23
;
331
67
}
332
333
namespace {
334
/// An assembly annotator class to print must execute information in
335
/// comments.
336
class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
337
  DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
338
339
public:
340
  MustExecuteAnnotatedWriter(const Function &F,
341
9
                             DominatorTree &DT, LoopInfo &LI) {
342
80
    for (auto &I: instructions(F)) {
343
80
      Loop *L = LI.getLoopFor(I.getParent());
344
147
      while (L) {
345
67
        if (isMustExecuteIn(I, L, &DT)) {
346
46
          MustExec[&I].push_back(L);
347
46
        }
348
67
        L = L->getParentLoop();
349
67
      };
350
80
    }
351
9
  }
352
  MustExecuteAnnotatedWriter(const Module &M,
353
0
                             DominatorTree &DT, LoopInfo &LI) {
354
0
    for (auto &F : M)
355
0
    for (auto &I: instructions(F)) {
356
0
      Loop *L = LI.getLoopFor(I.getParent());
357
0
      while (L) {
358
0
        if (isMustExecuteIn(I, L, &DT)) {
359
0
          MustExec[&I].push_back(L);
360
0
        }
361
0
        L = L->getParentLoop();
362
0
      };
363
0
    }
364
0
  }
365
366
367
80
  void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
368
80
    if (!MustExec.count(&V))
369
37
      return;
370
43
371
43
    const auto &Loops = MustExec.lookup(&V);
372
43
    const auto NumLoops = Loops.size();
373
43
    if (NumLoops > 1)
374
3
      OS << " ; (mustexec in " << NumLoops << " loops: ";
375
40
    else
376
40
      OS << " ; (mustexec in: ";
377
43
378
43
    bool first = true;
379
46
    for (const Loop *L : Loops) {
380
46
      if (!first)
381
3
        OS << ", ";
382
46
      first = false;
383
46
      OS << L->getHeader()->getName();
384
46
    }
385
43
    OS << ")";
386
43
  }
387
};
388
} // namespace
389
390
9
bool MustExecutePrinter::runOnFunction(Function &F) {
391
9
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
392
9
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
393
9
394
9
  MustExecuteAnnotatedWriter Writer(F, DT, LI);
395
9
  F.print(dbgs(), &Writer);
396
9
397
9
  return false;
398
9
}