Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
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 Dead Loop Deletion Pass. This pass is responsible
10
// for eliminating loops with non-infinite computable trip counts that have no
11
// side effects or volatile instructions, and do not contribute to the
12
// computation of the function's return value.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/Transforms/Scalar/LoopDeletion.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/Analysis/GlobalsModRef.h"
20
#include "llvm/Analysis/LoopPass.h"
21
#include "llvm/IR/Dominators.h"
22
#include "llvm/IR/PatternMatch.h"
23
#include "llvm/Transforms/Scalar.h"
24
#include "llvm/Transforms/Scalar/LoopPassManager.h"
25
#include "llvm/Transforms/Utils/LoopUtils.h"
26
using namespace llvm;
27
28
#define DEBUG_TYPE "loop-delete"
29
30
STATISTIC(NumDeleted, "Number of loops deleted");
31
32
enum class LoopDeletionResult {
33
  Unmodified,
34
  Modified,
35
  Deleted,
36
};
37
38
/// Determines if a loop is dead.
39
///
40
/// This assumes that we've already checked for unique exit and exiting blocks,
41
/// and that the code is in LCSSA form.
42
static bool isLoopDead(Loop *L, ScalarEvolution &SE,
43
                       SmallVectorImpl<BasicBlock *> &ExitingBlocks,
44
                       BasicBlock *ExitBlock, bool &Changed,
45
155k
                       BasicBlock *Preheader) {
46
155k
  // Make sure that all PHI entries coming from the loop are loop invariant.
47
155k
  // Because the code is in LCSSA form, any values used outside of the loop
48
155k
  // must pass through a PHI in the exit block, meaning that this check is
49
155k
  // sufficient to guarantee that no loop-variant values are used outside
50
155k
  // of the loop.
51
155k
  bool AllEntriesInvariant = true;
52
155k
  bool AllOutgoingValuesSame = true;
53
155k
  for (PHINode &P : ExitBlock->phis()) {
54
56.2k
    Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
55
56.2k
56
56.2k
    // Make sure all exiting blocks produce the same incoming value for the exit
57
56.2k
    // block.  If there are different incoming values for different exiting
58
56.2k
    // blocks, then it is impossible to statically determine which value should
59
56.2k
    // be used.
60
56.2k
    AllOutgoingValuesSame =
61
56.2k
        all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
62
8.20k
          return incoming == P.getIncomingValueForBlock(BB);
63
8.20k
        });
64
56.2k
65
56.2k
    if (!AllOutgoingValuesSame)
66
7.28k
      break;
67
48.9k
68
48.9k
    if (Instruction *I = dyn_cast<Instruction>(incoming))
69
48.9k
      if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
70
48.9k
        AllEntriesInvariant = false;
71
48.9k
        break;
72
48.9k
      }
73
48.9k
  }
74
155k
75
155k
  if (Changed)
76
3
    SE.forgetLoopDispositions(L);
77
155k
78
155k
  if (!AllEntriesInvariant || 
!AllOutgoingValuesSame106k
)
79
56.1k
    return false;
80
99.0k
81
99.0k
  // Make sure that no instructions in the block have potential side-effects.
82
99.0k
  // This includes instructions that could write to memory, and loads that are
83
99.0k
  // marked volatile.
84
99.0k
  for (auto &I : L->blocks())
85
667k
    
if (122k
any_of(*I, [](Instruction &I) 122k
{ return I.mayHaveSideEffects(); }))
86
83.8k
      return false;
87
99.0k
  
return true15.2k
;
88
99.0k
}
89
90
/// This function returns true if there is no viable path from the
91
/// entry block to the header of \p L. Right now, it only does
92
/// a local search to save compile time.
93
155k
static bool isLoopNeverExecuted(Loop *L) {
94
155k
  using namespace PatternMatch;
95
155k
96
155k
  auto *Preheader = L->getLoopPreheader();
97
155k
  // TODO: We can relax this constraint, since we just need a loop
98
155k
  // predecessor.
99
155k
  assert(Preheader && "Needs preheader!");
100
155k
101
155k
  if (Preheader == &Preheader->getParent()->getEntryBlock())
102
10.3k
    return false;
103
144k
  // All predecessors of the preheader should have a constant conditional
104
144k
  // branch, with the loop's preheader as not-taken.
105
144k
  
for (auto *Pred: predecessors(Preheader))144k
{
106
144k
    BasicBlock *Taken, *NotTaken;
107
144k
    ConstantInt *Cond;
108
144k
    if (!match(Pred->getTerminator(),
109
144k
               m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
110
144k
      return false;
111
199
    if (!Cond->getZExtValue())
112
77
      std::swap(Taken, NotTaken);
113
199
    if (Taken == Preheader)
114
149
      return false;
115
199
  }
116
144k
  assert(!pred_empty(Preheader) &&
117
42
         "Preheader should have predecessors at this point!");
118
42
  // All the predecessors have the loop preheader as not-taken target.
119
42
  return true;
120
144k
}
121
122
/// Remove a loop if it is dead.
123
///
124
/// A loop is considered dead if it does not impact the observable behavior of
125
/// the program other than finite running time. This never removes a loop that
126
/// might be infinite (unless it is never executed), as doing so could change
127
/// the halting/non-halting nature of a program.
128
///
129
/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
130
/// order to make various safety checks work.
131
///
132
/// \returns true if any changes were made. This may mutate the loop even if it
133
/// is unable to delete it due to hoisting trivially loop invariant
134
/// instructions out of the loop.
135
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
136
219k
                                           ScalarEvolution &SE, LoopInfo &LI) {
137
219k
  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
138
219k
139
219k
  // We can only remove the loop if there is a preheader that we can branch from
140
219k
  // after removing it. Also, if LoopSimplify form is not available, stay out
141
219k
  // of trouble.
142
219k
  BasicBlock *Preheader = L->getLoopPreheader();
143
219k
  if (!Preheader || !L->hasDedicatedExits()) {
144
2
    LLVM_DEBUG(
145
2
        dbgs()
146
2
        << "Deletion requires Loop with preheader and dedicated exits.\n");
147
2
    return LoopDeletionResult::Unmodified;
148
2
  }
149
219k
  // We can't remove loops that contain subloops.  If the subloops were dead,
150
219k
  // they would already have been removed in earlier executions of this pass.
151
219k
  if (L->begin() != L->end()) {
152
35.8k
    LLVM_DEBUG(dbgs() << "Loop contains subloops.\n");
153
35.8k
    return LoopDeletionResult::Unmodified;
154
35.8k
  }
155
183k
156
183k
157
183k
  BasicBlock *ExitBlock = L->getUniqueExitBlock();
158
183k
159
183k
  if (ExitBlock && 
isLoopNeverExecuted(L)155k
) {
160
42
    LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
161
42
    // Set incoming value to undef for phi nodes in the exit block.
162
42
    for (PHINode &P : ExitBlock->phis()) {
163
5
      std::fill(P.incoming_values().begin(), P.incoming_values().end(),
164
5
                UndefValue::get(P.getType()));
165
5
    }
166
42
    deleteDeadLoop(L, &DT, &SE, &LI);
167
42
    ++NumDeleted;
168
42
    return LoopDeletionResult::Deleted;
169
42
  }
170
183k
171
183k
  // The remaining checks below are for a loop being dead because all statements
172
183k
  // in the loop are invariant.
173
183k
  SmallVector<BasicBlock *, 4> ExitingBlocks;
174
183k
  L->getExitingBlocks(ExitingBlocks);
175
183k
176
183k
  // We require that the loop only have a single exit block.  Otherwise, we'd
177
183k
  // be in the situation of needing to be able to solve statically which exit
178
183k
  // block will be branched to, or trying to preserve the branching logic in
179
183k
  // a loop invariant manner.
180
183k
  if (!ExitBlock) {
181
28.4k
    LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n");
182
28.4k
    return LoopDeletionResult::Unmodified;
183
28.4k
  }
184
155k
  // Finally, we have to check that the loop really is dead.
185
155k
  bool Changed = false;
186
155k
  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
187
140k
    LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
188
140k
    return Changed ? 
LoopDeletionResult::Modified3
189
140k
                   : 
LoopDeletionResult::Unmodified139k
;
190
140k
  }
191
15.2k
192
15.2k
  // Don't remove loops for which we can't solve the trip count.
193
15.2k
  // They could be infinite, in which case we'd be changing program behavior.
194
15.2k
  const SCEV *S = SE.getMaxBackedgeTakenCount(L);
195
15.2k
  if (isa<SCEVCouldNotCompute>(S)) {
196
243
    LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
197
243
    return Changed ? 
LoopDeletionResult::Modified0
198
243
                   : LoopDeletionResult::Unmodified;
199
243
  }
200
14.9k
201
14.9k
  LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
202
14.9k
  deleteDeadLoop(L, &DT, &SE, &LI);
203
14.9k
  ++NumDeleted;
204
14.9k
205
14.9k
  return LoopDeletionResult::Deleted;
206
14.9k
}
207
208
PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
209
                                        LoopStandardAnalysisResults &AR,
210
85
                                        LPMUpdater &Updater) {
211
85
212
85
  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
213
85
  LLVM_DEBUG(L.dump());
214
85
  std::string LoopName = L.getName();
215
85
  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI);
216
85
  if (Result == LoopDeletionResult::Unmodified)
217
69
    return PreservedAnalyses::all();
218
16
219
16
  if (Result == LoopDeletionResult::Deleted)
220
16
    Updater.markLoopAsDeleted(L, LoopName);
221
16
222
16
  return getLoopPassPreservedAnalyses();
223
16
}
224
225
namespace {
226
class LoopDeletionLegacyPass : public LoopPass {
227
public:
228
  static char ID; // Pass ID, replacement for typeid
229
13.4k
  LoopDeletionLegacyPass() : LoopPass(ID) {
230
13.4k
    initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
231
13.4k
  }
232
233
  // Possibly eliminate loop L if it is dead.
234
  bool runOnLoop(Loop *L, LPPassManager &) override;
235
236
13.4k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
237
13.4k
    getLoopAnalysisUsage(AU);
238
13.4k
  }
239
};
240
}
241
242
char LoopDeletionLegacyPass::ID = 0;
243
48.9k
INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
244
48.9k
                      "Delete dead loops", false, false)
245
48.9k
INITIALIZE_PASS_DEPENDENCY(LoopPass)
246
48.9k
INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
247
                    "Delete dead loops", false, false)
248
249
13.4k
Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
250
251
219k
bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
252
219k
  if (skipLoop(L))
253
16
    return false;
254
219k
  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
255
219k
  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
256
219k
  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
257
219k
258
219k
  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
259
219k
  LLVM_DEBUG(L->dump());
260
219k
261
219k
  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI);
262
219k
263
219k
  if (Result == LoopDeletionResult::Deleted)
264
15.0k
    LPM.markLoopAsDeleted(*L);
265
219k
266
219k
  return Result != LoopDeletionResult::Unmodified;
267
219k
}