Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopInstSimplify.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopInstSimplify.cpp - Loop Instruction Simplification 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 pass performs lightweight instruction simplification on loop bodies.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Transforms/Scalar/LoopInstSimplify.h"
14
#include "llvm/ADT/PointerIntPair.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/ADT/SmallPtrSet.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/Analysis/AssumptionCache.h"
20
#include "llvm/Analysis/InstructionSimplify.h"
21
#include "llvm/Analysis/LoopInfo.h"
22
#include "llvm/Analysis/LoopIterator.h"
23
#include "llvm/Analysis/LoopPass.h"
24
#include "llvm/Analysis/MemorySSA.h"
25
#include "llvm/Analysis/MemorySSAUpdater.h"
26
#include "llvm/Analysis/TargetLibraryInfo.h"
27
#include "llvm/IR/BasicBlock.h"
28
#include "llvm/IR/CFG.h"
29
#include "llvm/IR/DataLayout.h"
30
#include "llvm/IR/Dominators.h"
31
#include "llvm/IR/Instruction.h"
32
#include "llvm/IR/Instructions.h"
33
#include "llvm/IR/Module.h"
34
#include "llvm/IR/PassManager.h"
35
#include "llvm/IR/User.h"
36
#include "llvm/Pass.h"
37
#include "llvm/Support/Casting.h"
38
#include "llvm/Transforms/Scalar.h"
39
#include "llvm/Transforms/Utils/Local.h"
40
#include "llvm/Transforms/Utils/LoopUtils.h"
41
#include <algorithm>
42
#include <utility>
43
44
using namespace llvm;
45
46
#define DEBUG_TYPE "loop-instsimplify"
47
48
STATISTIC(NumSimplified, "Number of redundant instructions simplified");
49
50
static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
51
                             AssumptionCache &AC, const TargetLibraryInfo &TLI,
52
100
                             MemorySSAUpdater *MSSAU) {
53
100
  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
54
100
  SimplifyQuery SQ(DL, &TLI, &DT, &AC);
55
100
56
100
  // On the first pass over the loop body we try to simplify every instruction.
57
100
  // On subsequent passes, we can restrict this to only simplifying instructions
58
100
  // where the inputs have been updated. We end up needing two sets: one
59
100
  // containing the instructions we are simplifying in *this* pass, and one for
60
100
  // the instructions we will want to simplify in the *next* pass. We use
61
100
  // pointers so we can swap between two stably allocated sets.
62
100
  SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
63
100
64
100
  // Track the PHI nodes that have already been visited during each iteration so
65
100
  // that we can identify when it is necessary to iterate.
66
100
  SmallPtrSet<PHINode *, 4> VisitedPHIs;
67
100
68
100
  // While simplifying we may discover dead code or cause code to become dead.
69
100
  // Keep track of all such instructions and we will delete them at the end.
70
100
  SmallVector<Instruction *, 8> DeadInsts;
71
100
72
100
  // First we want to create an RPO traversal of the loop body. By processing in
73
100
  // RPO we can ensure that definitions are processed prior to uses (for non PHI
74
100
  // uses) in all cases. This ensures we maximize the simplifications in each
75
100
  // iteration over the loop and minimizes the possible causes for continuing to
76
100
  // iterate.
77
100
  LoopBlocksRPO RPOT(&L);
78
100
  RPOT.perform(&LI);
79
100
  MemorySSA *MSSA = MSSAU ? 
MSSAU->getMemorySSA()13
:
nullptr87
;
80
100
81
100
  bool Changed = false;
82
117
  for (;;) {
83
117
    if (MSSAU && 
VerifyMemorySSA21
)
84
21
      MSSA->verifyMemorySSA();
85
243
    for (BasicBlock *BB : RPOT) {
86
879
      for (Instruction &I : *BB) {
87
879
        if (auto *PI = dyn_cast<PHINode>(&I))
88
151
          VisitedPHIs.insert(PI);
89
879
90
879
        if (I.use_empty()) {
91
332
          if (isInstructionTriviallyDead(&I, &TLI))
92
2
            DeadInsts.push_back(&I);
93
332
          continue;
94
332
        }
95
547
96
547
        // We special case the first iteration which we can detect due to the
97
547
        // empty `ToSimplify` set.
98
547
        bool IsFirstIteration = ToSimplify->empty();
99
547
100
547
        if (!IsFirstIteration && 
!ToSimplify->count(&I)75
)
101
66
          continue;
102
481
103
481
        Value *V = SimplifyInstruction(&I, SQ.getWithInstruction(&I));
104
481
        if (!V || 
!LI.replacementPreservesLCSSAForm(&I, V)47
)
105
434
          continue;
106
47
107
47
        for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
108
104
             UI != UE;) {
109
57
          Use &U = *UI++;
110
57
          auto *UserI = cast<Instruction>(U.getUser());
111
57
          U.set(V);
112
57
113
57
          // If the instruction is used by a PHI node we have already processed
114
57
          // we'll need to iterate on the loop body to converge, so add it to
115
57
          // the next set.
116
57
          if (auto *UserPI = dyn_cast<PHINode>(UserI))
117
41
            if (VisitedPHIs.count(UserPI)) {
118
17
              Next->insert(UserPI);
119
17
              continue;
120
17
            }
121
40
122
40
          // If we are only simplifying targeted instructions and the user is an
123
40
          // instruction in the loop body, add it to our set of targeted
124
40
          // instructions. Because we process defs before uses (outside of PHIs)
125
40
          // we won't have visited it yet.
126
40
          //
127
40
          // We also skip any uses outside of the loop being simplified. Those
128
40
          // should always be PHI nodes due to LCSSA form, and we don't want to
129
40
          // try to simplify those away.
130
40
          assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
131
40
                 "Uses outside the loop should be PHI nodes due to LCSSA!");
132
40
          if (!IsFirstIteration && 
L.contains(UserI)8
)
133
0
            ToSimplify->insert(UserI);
134
40
        }
135
47
136
47
        if (MSSAU)
137
23
          if (Instruction *SimpleI = dyn_cast_or_null<Instruction>(V))
138
13
            if (MemoryAccess *MA = MSSA->getMemoryAccess(&I))
139
0
              if (MemoryAccess *ReplacementMA = MSSA->getMemoryAccess(SimpleI))
140
0
                MA->replaceAllUsesWith(ReplacementMA);
141
47
142
47
        assert(I.use_empty() && "Should always have replaced all uses!");
143
47
        if (isInstructionTriviallyDead(&I, &TLI))
144
47
          DeadInsts.push_back(&I);
145
47
        ++NumSimplified;
146
47
        Changed = true;
147
47
      }
148
243
    }
149
117
150
117
    // Delete any dead instructions found thus far now that we've finished an
151
117
    // iteration over all instructions in all the loop blocks.
152
117
    if (!DeadInsts.empty()) {
153
29
      Changed = true;
154
29
      RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
155
29
    }
156
117
157
117
    if (MSSAU && 
VerifyMemorySSA21
)
158
21
      MSSA->verifyMemorySSA();
159
117
160
117
    // If we never found a PHI that needs to be simplified in the next
161
117
    // iteration, we're done.
162
117
    if (Next->empty())
163
100
      break;
164
17
165
17
    // Otherwise, put the next set in place for the next iteration and reset it
166
17
    // and the visited PHIs for that iteration.
167
17
    std::swap(Next, ToSimplify);
168
17
    Next->clear();
169
17
    VisitedPHIs.clear();
170
17
    DeadInsts.clear();
171
17
  }
172
100
173
100
  return Changed;
174
100
}
175
176
namespace {
177
178
class LoopInstSimplifyLegacyPass : public LoopPass {
179
public:
180
  static char ID; // Pass ID, replacement for typeid
181
182
1
  LoopInstSimplifyLegacyPass() : LoopPass(ID) {
183
1
    initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
184
1
  }
185
186
1
  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
187
1
    if (skipLoop(L))
188
0
      return false;
189
1
    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
190
1
    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
191
1
    AssumptionCache &AC =
192
1
        getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
193
1
            *L->getHeader()->getParent());
194
1
    const TargetLibraryInfo &TLI =
195
1
        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
196
1
    MemorySSA *MSSA = nullptr;
197
1
    Optional<MemorySSAUpdater> MSSAU;
198
1
    if (EnableMSSALoopDependency) {
199
0
      MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
200
0
      MSSAU = MemorySSAUpdater(MSSA);
201
0
    }
202
1
203
1
    return simplifyLoopInst(*L, DT, LI, AC, TLI,
204
1
                            MSSAU.hasValue() ? 
MSSAU.getPointer()0
: nullptr);
205
1
  }
206
207
1
  void getAnalysisUsage(AnalysisUsage &AU) const override {
208
1
    AU.addRequired<AssumptionCacheTracker>();
209
1
    AU.addRequired<DominatorTreeWrapperPass>();
210
1
    AU.addRequired<TargetLibraryInfoWrapperPass>();
211
1
    AU.setPreservesCFG();
212
1
    if (EnableMSSALoopDependency) {
213
0
      AU.addRequired<MemorySSAWrapperPass>();
214
0
      AU.addPreserved<MemorySSAWrapperPass>();
215
0
    }
216
1
    getLoopAnalysisUsage(AU);
217
1
  }
218
};
219
220
} // end anonymous namespace
221
222
PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
223
                                            LoopStandardAnalysisResults &AR,
224
99
                                            LPMUpdater &) {
225
99
  Optional<MemorySSAUpdater> MSSAU;
226
99
  if (AR.MSSA) {
227
13
    MSSAU = MemorySSAUpdater(AR.MSSA);
228
13
    AR.MSSA->verifyMemorySSA();
229
13
  }
230
99
  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI,
231
99
                        MSSAU.hasValue() ? 
MSSAU.getPointer()13
:
nullptr86
))
232
79
    return PreservedAnalyses::all();
233
20
234
20
  auto PA = getLoopPassPreservedAnalyses();
235
20
  PA.preserveSet<CFGAnalyses>();
236
20
  if (EnableMSSALoopDependency)
237
10
    PA.preserve<MemorySSAAnalysis>();
238
20
  return PA;
239
20
}
240
241
char LoopInstSimplifyLegacyPass::ID = 0;
242
243
36.0k
INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
244
36.0k
                      "Simplify instructions in loops", false, false)
245
36.0k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
246
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopPass)
247
36.0k
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
248
36.0k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
249
36.0k
INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
250
                    "Simplify instructions in loops", false, false)
251
252
0
Pass *llvm::createLoopInstSimplifyPass() {
253
0
  return new LoopInstSimplifyLegacyPass();
254
0
}