Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/LCSSA.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
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 transforms loops by placing phi nodes at the end of the loops for
10
// all values that are live across the loop boundary.  For example, it turns
11
// the left into the right code:
12
//
13
// for (...)                for (...)
14
//   if (c)                   if (c)
15
//     X1 = ...                 X1 = ...
16
//   else                     else
17
//     X2 = ...                 X2 = ...
18
//   X3 = phi(X1, X2)         X3 = phi(X1, X2)
19
// ... = X3 + 4             X4 = phi(X3)
20
//                          ... = X4 + 4
21
//
22
// This is still valid LLVM; the extra phi nodes are purely redundant, and will
23
// be trivially eliminated by InstCombine.  The major benefit of this
24
// transformation is that it makes many other loop optimizations, such as
25
// LoopUnswitching, simpler.
26
//
27
//===----------------------------------------------------------------------===//
28
29
#include "llvm/Transforms/Utils/LCSSA.h"
30
#include "llvm/ADT/STLExtras.h"
31
#include "llvm/ADT/Statistic.h"
32
#include "llvm/Analysis/AliasAnalysis.h"
33
#include "llvm/Analysis/BasicAliasAnalysis.h"
34
#include "llvm/Analysis/BranchProbabilityInfo.h"
35
#include "llvm/Analysis/GlobalsModRef.h"
36
#include "llvm/Analysis/LoopPass.h"
37
#include "llvm/Analysis/MemorySSA.h"
38
#include "llvm/Analysis/ScalarEvolution.h"
39
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
40
#include "llvm/IR/Constants.h"
41
#include "llvm/IR/Dominators.h"
42
#include "llvm/IR/Function.h"
43
#include "llvm/IR/Instructions.h"
44
#include "llvm/IR/IntrinsicInst.h"
45
#include "llvm/IR/PredIteratorCache.h"
46
#include "llvm/Pass.h"
47
#include "llvm/Transforms/Utils.h"
48
#include "llvm/Transforms/Utils/Local.h"
49
#include "llvm/Transforms/Utils/LoopUtils.h"
50
#include "llvm/Transforms/Utils/SSAUpdater.h"
51
using namespace llvm;
52
53
#define DEBUG_TYPE "lcssa"
54
55
STATISTIC(NumLCSSA, "Number of live out of a loop variables");
56
57
#ifdef EXPENSIVE_CHECKS
58
static bool VerifyLoopLCSSA = true;
59
#else
60
static bool VerifyLoopLCSSA = false;
61
#endif
62
static cl::opt<bool, true>
63
    VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA),
64
                        cl::Hidden,
65
                        cl::desc("Verify loop lcssa form (time consuming)"));
66
67
/// Return true if the specified block is in the list.
68
static bool isExitBlock(BasicBlock *BB,
69
705k
                        const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
70
705k
  return is_contained(ExitBlocks, BB);
71
705k
}
72
73
/// For every instruction from the worklist, check to see if it has any uses
74
/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
75
/// rewrite the uses.
76
bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
77
1.52M
                                    DominatorTree &DT, LoopInfo &LI) {
78
1.52M
  SmallVector<Use *, 16> UsesToRewrite;
79
1.52M
  SmallSetVector<PHINode *, 16> PHIsToRemove;
80
1.52M
  PredIteratorCache PredCache;
81
1.52M
  bool Changed = false;
82
1.52M
83
1.52M
  // Cache the Loop ExitBlocks across this loop.  We expect to get a lot of
84
1.52M
  // instructions within the same loops, computing the exit blocks is
85
1.52M
  // expensive, and we're not mutating the loop structure.
86
1.52M
  SmallDenseMap<Loop*, SmallVector<BasicBlock *,1>> LoopExitBlocks;
87
1.52M
88
6.93M
  while (!Worklist.empty()) {
89
5.41M
    UsesToRewrite.clear();
90
5.41M
91
5.41M
    Instruction *I = Worklist.pop_back_val();
92
5.41M
    assert(!I->getType()->isTokenTy() && "Tokens shouldn't be in the worklist");
93
5.41M
    BasicBlock *InstBB = I->getParent();
94
5.41M
    Loop *L = LI.getLoopFor(InstBB);
95
5.41M
    assert(L && "Instruction belongs to a BB that's not part of a loop");
96
5.41M
    if (!LoopExitBlocks.count(L))
97
1.64M
      L->getExitBlocks(LoopExitBlocks[L]);
98
5.41M
    assert(LoopExitBlocks.count(L));
99
5.41M
    const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[L];
100
5.41M
101
5.41M
    if (ExitBlocks.empty())
102
36
      continue;
103
5.41M
104
14.6M
    
for (Use &U : I->uses())5.41M
{
105
14.6M
      Instruction *User = cast<Instruction>(U.getUser());
106
14.6M
      BasicBlock *UserBB = User->getParent();
107
14.6M
      if (auto *PN = dyn_cast<PHINode>(User))
108
3.48M
        UserBB = PN->getIncomingBlock(U);
109
14.6M
110
14.6M
      if (InstBB != UserBB && 
!L->contains(UserBB)5.74M
)
111
1.05M
        UsesToRewrite.push_back(&U);
112
14.6M
    }
113
5.41M
114
5.41M
    // If there are no uses outside the loop, exit with no change.
115
5.41M
    if (UsesToRewrite.empty())
116
4.75M
      continue;
117
659k
118
659k
    ++NumLCSSA; // We are applying the transformation
119
659k
120
659k
    // Invoke instructions are special in that their result value is not
121
659k
    // available along their unwind edge. The code below tests to see whether
122
659k
    // DomBB dominates the value, so adjust DomBB to the normal destination
123
659k
    // block, which is effectively where the value is first usable.
124
659k
    BasicBlock *DomBB = InstBB;
125
659k
    if (auto *Inv = dyn_cast<InvokeInst>(I))
126
1.21k
      DomBB = Inv->getNormalDest();
127
659k
128
659k
    DomTreeNode *DomNode = DT.getNode(DomBB);
129
659k
130
659k
    SmallVector<PHINode *, 16> AddedPHIs;
131
659k
    SmallVector<PHINode *, 8> PostProcessPHIs;
132
659k
133
659k
    SmallVector<PHINode *, 4> InsertedPHIs;
134
659k
    SSAUpdater SSAUpdate(&InsertedPHIs);
135
659k
    SSAUpdate.Initialize(I->getType(), I->getName());
136
659k
137
659k
    // Insert the LCSSA phi's into all of the exit blocks dominated by the
138
659k
    // value, and add them to the Phi's map.
139
1.29M
    for (BasicBlock *ExitBB : ExitBlocks) {
140
1.29M
      if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
141
327k
        continue;
142
968k
143
968k
      // If we already inserted something for this BB, don't reprocess it.
144
968k
      if (SSAUpdate.HasValueForBlock(ExitBB))
145
71.7k
        continue;
146
896k
147
896k
      PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
148
896k
                                    I->getName() + ".lcssa", &ExitBB->front());
149
896k
      // Get the debug location from the original instruction.
150
896k
      PN->setDebugLoc(I->getDebugLoc());
151
896k
      // Add inputs from inside the loop for this PHI.
152
968k
      for (BasicBlock *Pred : PredCache.get(ExitBB)) {
153
968k
        PN->addIncoming(I, Pred);
154
968k
155
968k
        // If the exit block has a predecessor not within the loop, arrange for
156
968k
        // the incoming value use corresponding to that predecessor to be
157
968k
        // rewritten in terms of a different LCSSA PHI.
158
968k
        if (!L->contains(Pred))
159
36
          UsesToRewrite.push_back(
160
36
              &PN->getOperandUse(PN->getOperandNumForIncomingValue(
161
36
                  PN->getNumIncomingValues() - 1)));
162
968k
      }
163
896k
164
896k
      AddedPHIs.push_back(PN);
165
896k
166
896k
      // Remember that this phi makes the value alive in this block.
167
896k
      SSAUpdate.AddAvailableValue(ExitBB, PN);
168
896k
169
896k
      // LoopSimplify might fail to simplify some loops (e.g. when indirect
170
896k
      // branches are involved). In such situations, it might happen that an
171
896k
      // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
172
896k
      // create PHIs in such an exit block, we are also inserting PHIs into L2's
173
896k
      // header. This could break LCSSA form for L2 because these inserted PHIs
174
896k
      // can also have uses outside of L2. Remember all PHIs in such situation
175
896k
      // as to revisit than later on. FIXME: Remove this if indirectbr support
176
896k
      // into LoopSimplify gets improved.
177
896k
      if (auto *OtherLoop = LI.getLoopFor(ExitBB))
178
265k
        if (!L->contains(OtherLoop))
179
265k
          PostProcessPHIs.push_back(PN);
180
896k
    }
181
659k
182
659k
    // Rewrite all uses outside the loop in terms of the new PHIs we just
183
659k
    // inserted.
184
1.05M
    for (Use *UseToRewrite : UsesToRewrite) {
185
1.05M
      // If this use is in an exit block, rewrite to use the newly inserted PHI.
186
1.05M
      // This is required for correctness because SSAUpdate doesn't handle uses
187
1.05M
      // in the same block.  It assumes the PHI we inserted is at the end of the
188
1.05M
      // block.
189
1.05M
      Instruction *User = cast<Instruction>(UseToRewrite->getUser());
190
1.05M
      BasicBlock *UserBB = User->getParent();
191
1.05M
      if (auto *PN = dyn_cast<PHINode>(User))
192
416k
        UserBB = PN->getIncomingBlock(*UseToRewrite);
193
1.05M
194
1.05M
      if (isa<PHINode>(UserBB->begin()) && 
isExitBlock(UserBB, ExitBlocks)705k
) {
195
679k
        // Tell the VHs that the uses changed. This updates SCEV's caches.
196
679k
        if (UseToRewrite->get()->hasValueHandle())
197
76.5k
          ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front());
198
679k
        UseToRewrite->set(&UserBB->front());
199
679k
        continue;
200
679k
      }
201
371k
202
371k
      // If we added a single PHI, it must dominate all uses and we can directly
203
371k
      // rename it.
204
371k
      if (AddedPHIs.size() == 1) {
205
242k
        // Tell the VHs that the uses changed. This updates SCEV's caches.
206
242k
        // We might call ValueIsRAUWd multiple times for the same value.
207
242k
        if (UseToRewrite->get()->hasValueHandle())
208
1.41k
          ValueHandleBase::ValueIsRAUWd(*UseToRewrite, AddedPHIs[0]);
209
242k
        UseToRewrite->set(AddedPHIs[0]);
210
242k
        continue;
211
242k
      }
212
128k
213
128k
      // Otherwise, do full PHI insertion.
214
128k
      SSAUpdate.RewriteUse(*UseToRewrite);
215
128k
    }
216
659k
217
659k
    SmallVector<DbgValueInst *, 4> DbgValues;
218
659k
    llvm::findDbgValues(DbgValues, I);
219
659k
220
659k
    // Update pre-existing debug value uses that reside outside the loop.
221
659k
    auto &Ctx = I->getContext();
222
659k
    for (auto DVI : DbgValues) {
223
31
      BasicBlock *UserBB = DVI->getParent();
224
31
      if (InstBB == UserBB || 
L->contains(UserBB)11
)
225
22
        continue;
226
9
      // We currently only handle debug values residing in blocks that were
227
9
      // traversed while rewriting the uses. If we inserted just a single PHI,
228
9
      // we will handle all relevant debug values.
229
9
      Value *V = AddedPHIs.size() == 1 ? 
AddedPHIs[0]6
230
9
                                       : 
SSAUpdate.FindValueForBlock(UserBB)3
;
231
9
      if (V)
232
8
        DVI->setOperand(0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(V)));
233
9
    }
234
659k
235
659k
    // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
236
659k
    // to post-process them to keep LCSSA form.
237
659k
    for (PHINode *InsertedPN : InsertedPHIs) {
238
13.2k
      if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
239
3.21k
        if (!L->contains(OtherLoop))
240
3.21k
          PostProcessPHIs.push_back(InsertedPN);
241
13.2k
    }
242
659k
243
659k
    // Post process PHI instructions that were inserted into another disjoint
244
659k
    // loop and update their exits properly.
245
659k
    for (auto *PostProcessPN : PostProcessPHIs)
246
268k
      if (!PostProcessPN->use_empty())
247
246k
        Worklist.push_back(PostProcessPN);
248
659k
249
659k
    // Keep track of PHI nodes that we want to remove because they did not have
250
659k
    // any uses rewritten. If the new PHI is used, store it so that we can
251
659k
    // try to propagate dbg.value intrinsics to it.
252
659k
    SmallVector<PHINode *, 2> NeedDbgValues;
253
659k
    for (PHINode *PN : AddedPHIs)
254
896k
      if (PN->use_empty())
255
189k
        PHIsToRemove.insert(PN);
256
706k
      else
257
706k
        NeedDbgValues.push_back(PN);
258
659k
    insertDebugValuesForPHIs(InstBB, NeedDbgValues);
259
659k
    Changed = true;
260
659k
  }
261
1.52M
  // Remove PHI nodes that did not have any uses rewritten. We need to redo the
262
1.52M
  // use_empty() check here, because even if the PHI node wasn't used when added
263
1.52M
  // to PHIsToRemove, later added PHI nodes can be using it.  This cleanup is
264
1.52M
  // not guaranteed to handle trees/cycles of PHI nodes that only are used by
265
1.52M
  // each other. Such situations has only been noticed when the input IR
266
1.52M
  // contains unreachable code, and leaving some extra redundant PHI nodes in
267
1.52M
  // such situations is considered a minor problem.
268
1.52M
  for (PHINode *PN : PHIsToRemove)
269
189k
    if (PN->use_empty())
270
189k
      PN->eraseFromParent();
271
1.52M
  return Changed;
272
1.52M
}
273
274
// Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
275
static void computeBlocksDominatingExits(
276
    Loop &L, DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
277
1.52M
    SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
278
1.52M
  SmallVector<BasicBlock *, 8> BBWorklist;
279
1.52M
280
1.52M
  // We start from the exit blocks, as every block trivially dominates itself
281
1.52M
  // (not strictly).
282
1.52M
  for (BasicBlock *BB : ExitBlocks)
283
2.10M
    BBWorklist.push_back(BB);
284
1.52M
285
6.64M
  while (!BBWorklist.empty()) {
286
5.12M
    BasicBlock *BB = BBWorklist.pop_back_val();
287
5.12M
288
5.12M
    // Check if this is a loop header. If this is the case, we're done.
289
5.12M
    if (L.getHeader() == BB)
290
1.52M
      continue;
291
3.59M
292
3.59M
    // Otherwise, add its immediate predecessor in the dominator tree to the
293
3.59M
    // worklist, unless we visited it already.
294
3.59M
    BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
295
3.59M
296
3.59M
    // Exit blocks can have an immediate dominator not beloinging to the
297
3.59M
    // loop. For an exit block to be immediately dominated by another block
298
3.59M
    // outside the loop, it implies not all paths from that dominator, to the
299
3.59M
    // exit block, go through the loop.
300
3.59M
    // Example:
301
3.59M
    //
302
3.59M
    // |---- A
303
3.59M
    // |     |
304
3.59M
    // |     B<--
305
3.59M
    // |     |  |
306
3.59M
    // |---> C --
307
3.59M
    //       |
308
3.59M
    //       D
309
3.59M
    //
310
3.59M
    // C is the exit block of the loop and it's immediately dominated by A,
311
3.59M
    // which doesn't belong to the loop.
312
3.59M
    if (!L.contains(IDomBB))
313
825
      continue;
314
3.59M
315
3.59M
    if (BlocksDominatingExits.insert(IDomBB))
316
3.02M
      BBWorklist.push_back(IDomBB);
317
3.59M
  }
318
1.52M
}
319
320
bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
321
1.52M
                     ScalarEvolution *SE) {
322
1.52M
  bool Changed = false;
323
1.52M
324
#ifdef EXPENSIVE_CHECKS
325
  // Verify all sub-loops are in LCSSA form already.
326
  for (Loop *SubLoop: L)
327
    assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
328
#endif
329
330
1.52M
  SmallVector<BasicBlock *, 8> ExitBlocks;
331
1.52M
  L.getExitBlocks(ExitBlocks);
332
1.52M
  if (ExitBlocks.empty())
333
811
    return false;
334
1.52M
335
1.52M
  SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;
336
1.52M
337
1.52M
  // We want to avoid use-scanning leveraging dominance informations.
338
1.52M
  // If a block doesn't dominate any of the loop exits, the none of the values
339
1.52M
  // defined in the loop can be used outside.
340
1.52M
  // We compute the set of blocks fullfilling the conditions in advance
341
1.52M
  // walking the dominator tree upwards until we hit a loop header.
342
1.52M
  computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);
343
1.52M
344
1.52M
  SmallVector<Instruction *, 8> Worklist;
345
1.52M
346
1.52M
  // Look at all the instructions in the loop, checking to see if they have uses
347
1.52M
  // outside the loop.  If so, put them into the worklist to rewrite those uses.
348
3.02M
  for (BasicBlock *BB : BlocksDominatingExits) {
349
3.02M
    // Skip blocks that are part of any sub-loops, they must be in LCSSA
350
3.02M
    // already.
351
3.02M
    if (LI->getLoopFor(BB) != &L)
352
362k
      continue;
353
20.4M
    
for (Instruction &I : *BB)2.65M
{
354
20.4M
      // Reject two common cases fast: instructions with no uses (like stores)
355
20.4M
      // and instructions with one use that is in the same block as this.
356
20.4M
      if (I.use_empty() ||
357
20.4M
          
(16.1M
I.hasOneUse()16.1M
&&
I.user_back()->getParent() == BB11.5M
&&
358
16.1M
           
!isa<PHINode>(I.user_back())11.1M
))
359
15.2M
        continue;
360
5.16M
361
5.16M
      // Tokens cannot be used in PHI nodes, so we skip over them.
362
5.16M
      // We can run into tokens which are live out of a loop with catchswitch
363
5.16M
      // instructions in Windows EH if the catchswitch has one catchpad which
364
5.16M
      // is inside the loop and another which is not.
365
5.16M
      if (I.getType()->isTokenTy())
366
5
        continue;
367
5.16M
368
5.16M
      Worklist.push_back(&I);
369
5.16M
    }
370
2.65M
  }
371
1.52M
  Changed = formLCSSAForInstructions(Worklist, DT, *LI);
372
1.52M
373
1.52M
  // If we modified the code, remove any caches about the loop from SCEV to
374
1.52M
  // avoid dangling entries.
375
1.52M
  // FIXME: This is a big hammer, can we clear the cache more selectively?
376
1.52M
  if (SE && 
Changed154k
)
377
569
    SE->forgetLoop(&L);
378
1.52M
379
1.52M
  assert(L.isLCSSAForm(DT));
380
1.52M
381
1.52M
  return Changed;
382
1.52M
}
383
384
/// Process a loop nest depth first.
385
bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
386
1.52M
                                ScalarEvolution *SE) {
387
1.52M
  bool Changed = false;
388
1.52M
389
1.52M
  // Recurse depth-first through inner loops.
390
1.52M
  for (Loop *SubLoop : L.getSubLoops())
391
375k
    Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);
392
1.52M
393
1.52M
  Changed |= formLCSSA(L, DT, LI, SE);
394
1.52M
  return Changed;
395
1.52M
}
396
397
/// Process all loops in the function, inner-most out.
398
static bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT,
399
2.58M
                                ScalarEvolution *SE) {
400
2.58M
  bool Changed = false;
401
2.58M
  for (auto &L : *LI)
402
1.00M
    Changed |= formLCSSARecursively(*L, DT, LI, SE);
403
2.58M
  return Changed;
404
2.58M
}
405
406
namespace {
407
struct LCSSAWrapperPass : public FunctionPass {
408
  static char ID; // Pass identification, replacement for typeid
409
99.4k
  LCSSAWrapperPass() : FunctionPass(ID) {
410
99.4k
    initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry());
411
99.4k
  }
412
413
  // Cached analysis information for the current function.
414
  DominatorTree *DT;
415
  LoopInfo *LI;
416
  ScalarEvolution *SE;
417
418
  bool runOnFunction(Function &F) override;
419
0
  void verifyAnalysis() const override {
420
0
    // This check is very expensive. On the loop intensive compiles it may cause
421
0
    // up to 10x slowdown. Currently it's disabled by default. LPPassManager
422
0
    // always does limited form of the LCSSA verification. Similar reasoning
423
0
    // was used for the LoopInfo verifier.
424
0
    if (VerifyLoopLCSSA) {
425
0
      assert(all_of(*LI,
426
0
                    [&](Loop *L) {
427
0
                      return L->isRecursivelyLCSSAForm(*DT, *LI);
428
0
                    }) &&
429
0
             "LCSSA form is broken!");
430
0
    }
431
0
  };
432
433
  /// This transformation requires natural loop information & requires that
434
  /// loop preheaders be inserted into the CFG.  It maintains both of these,
435
  /// as well as the CFG.  It also requires dominator information.
436
99.4k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
437
99.4k
    AU.setPreservesCFG();
438
99.4k
439
99.4k
    AU.addRequired<DominatorTreeWrapperPass>();
440
99.4k
    AU.addRequired<LoopInfoWrapperPass>();
441
99.4k
    AU.addPreservedID(LoopSimplifyID);
442
99.4k
    AU.addPreserved<AAResultsWrapperPass>();
443
99.4k
    AU.addPreserved<BasicAAWrapperPass>();
444
99.4k
    AU.addPreserved<GlobalsAAWrapperPass>();
445
99.4k
    AU.addPreserved<ScalarEvolutionWrapperPass>();
446
99.4k
    AU.addPreserved<SCEVAAWrapperPass>();
447
99.4k
    AU.addPreserved<BranchProbabilityInfoWrapperPass>();
448
99.4k
    AU.addPreserved<MemorySSAWrapperPass>();
449
99.4k
450
99.4k
    // This is needed to perform LCSSA verification inside LPPassManager
451
99.4k
    AU.addRequired<LCSSAVerificationPass>();
452
99.4k
    AU.addPreserved<LCSSAVerificationPass>();
453
99.4k
  }
454
};
455
}
456
457
char LCSSAWrapperPass::ID = 0;
458
101k
INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
459
101k
                      false, false)
460
101k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
461
101k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
462
101k
INITIALIZE_PASS_DEPENDENCY(LCSSAVerificationPass)
463
101k
INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
464
                    false, false)
465
466
2.44k
Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
467
char &llvm::LCSSAID = LCSSAWrapperPass::ID;
468
469
/// Transform \p F into loop-closed SSA form.
470
2.57M
bool LCSSAWrapperPass::runOnFunction(Function &F) {
471
2.57M
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
472
2.57M
  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
473
2.57M
  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
474
2.57M
  SE = SEWP ? 
&SEWP->getSE()100
:
nullptr2.57M
;
475
2.57M
476
2.57M
  return formLCSSAOnAllLoops(LI, *DT, SE);
477
2.57M
}
478
479
6.21k
PreservedAnalyses LCSSAPass::run(Function &F, FunctionAnalysisManager &AM) {
480
6.21k
  auto &LI = AM.getResult<LoopAnalysis>(F);
481
6.21k
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
482
6.21k
  auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
483
6.21k
  if (!formLCSSAOnAllLoops(&LI, DT, SE))
484
5.97k
    return PreservedAnalyses::all();
485
236
486
236
  PreservedAnalyses PA;
487
236
  PA.preserveSet<CFGAnalyses>();
488
236
  PA.preserve<BasicAA>();
489
236
  PA.preserve<GlobalsAA>();
490
236
  PA.preserve<SCEVAA>();
491
236
  PA.preserve<ScalarEvolutionAnalysis>();
492
236
  // BPI maps terminators to probabilities, since we don't modify the CFG, no
493
236
  // updates are needed to preserve it.
494
236
  PA.preserve<BranchProbabilityAnalysis>();
495
236
  PA.preserve<MemorySSAAnalysis>();
496
236
  return PA;
497
236
}