Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/LoopSimplify.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopSimplify.cpp - Loop Canonicalization 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 several transformations to transform natural loops into a
10
// simpler form, which makes subsequent analyses and transformations simpler and
11
// more effective.
12
//
13
// Loop pre-header insertion guarantees that there is a single, non-critical
14
// entry edge from outside of the loop to the loop header.  This simplifies a
15
// number of analyses and transformations, such as LICM.
16
//
17
// Loop exit-block insertion guarantees that all exit blocks from the loop
18
// (blocks which are outside of the loop that have predecessors inside of the
19
// loop) only have predecessors from inside of the loop (and are thus dominated
20
// by the loop header).  This simplifies transformations such as store-sinking
21
// that are built into LICM.
22
//
23
// This pass also guarantees that loops will have exactly one backedge.
24
//
25
// Indirectbr instructions introduce several complications. If the loop
26
// contains or is entered by an indirectbr instruction, it may not be possible
27
// to transform the loop and make these guarantees. Client code should check
28
// that these conditions are true before relying on them.
29
//
30
// Similar complications arise from callbr instructions, particularly in
31
// asm-goto where blockaddress expressions are used.
32
//
33
// Note that the simplifycfg pass will clean up blocks which are split out but
34
// end up being unnecessary, so usage of this pass should not pessimize
35
// generated code.
36
//
37
// This pass obviously modifies the CFG, but updates loop information and
38
// dominator information.
39
//
40
//===----------------------------------------------------------------------===//
41
42
#include "llvm/Transforms/Utils/LoopSimplify.h"
43
#include "llvm/ADT/DepthFirstIterator.h"
44
#include "llvm/ADT/SetOperations.h"
45
#include "llvm/ADT/SetVector.h"
46
#include "llvm/ADT/SmallVector.h"
47
#include "llvm/ADT/Statistic.h"
48
#include "llvm/Analysis/AliasAnalysis.h"
49
#include "llvm/Analysis/AssumptionCache.h"
50
#include "llvm/Analysis/BasicAliasAnalysis.h"
51
#include "llvm/Analysis/BranchProbabilityInfo.h"
52
#include "llvm/Analysis/DependenceAnalysis.h"
53
#include "llvm/Analysis/GlobalsModRef.h"
54
#include "llvm/Analysis/InstructionSimplify.h"
55
#include "llvm/Analysis/LoopInfo.h"
56
#include "llvm/Analysis/MemorySSA.h"
57
#include "llvm/Analysis/MemorySSAUpdater.h"
58
#include "llvm/Analysis/ScalarEvolution.h"
59
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
60
#include "llvm/IR/CFG.h"
61
#include "llvm/IR/Constants.h"
62
#include "llvm/IR/DataLayout.h"
63
#include "llvm/IR/Dominators.h"
64
#include "llvm/IR/Function.h"
65
#include "llvm/IR/Instructions.h"
66
#include "llvm/IR/IntrinsicInst.h"
67
#include "llvm/IR/LLVMContext.h"
68
#include "llvm/IR/Module.h"
69
#include "llvm/IR/Type.h"
70
#include "llvm/Support/Debug.h"
71
#include "llvm/Support/raw_ostream.h"
72
#include "llvm/Transforms/Utils.h"
73
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
74
#include "llvm/Transforms/Utils/Local.h"
75
#include "llvm/Transforms/Utils/LoopUtils.h"
76
using namespace llvm;
77
78
#define DEBUG_TYPE "loop-simplify"
79
80
STATISTIC(NumNested  , "Number of nested loops split out");
81
82
// If the block isn't already, move the new block to right after some 'outside
83
// block' block.  This prevents the preheader from being placed inside the loop
84
// body, e.g. when the loop hasn't been rotated.
85
static void placeSplitBlockCarefully(BasicBlock *NewBB,
86
                                     SmallVectorImpl<BasicBlock *> &SplitPreds,
87
490k
                                     Loop *L) {
88
490k
  // Check to see if NewBB is already well placed.
89
490k
  Function::iterator BBI = --NewBB->getIterator();
90
728k
  for (unsigned i = 0, e = SplitPreds.size(); i != e; 
++i237k
) {
91
521k
    if (&*BBI == SplitPreds[i])
92
283k
      return;
93
521k
  }
94
490k
95
490k
  // If it isn't already after an outside block, move it after one.  This is
96
490k
  // always good as it makes the uncond branch from the outside block into a
97
490k
  // fall-through.
98
490k
99
490k
  // Figure out *which* outside block to put this after.  Prefer an outside
100
490k
  // block that neighbors a BB actually in the loop.
101
490k
  BasicBlock *FoundBB = nullptr;
102
427k
  for (unsigned i = 0, e = SplitPreds.size(); i != e; 
++i221k
) {
103
225k
    Function::iterator BBI = SplitPreds[i]->getIterator();
104
225k
    if (++BBI != NewBB->getParent()->end() && 
L->contains(&*BBI)225k
) {
105
4.67k
      FoundBB = SplitPreds[i];
106
4.67k
      break;
107
4.67k
    }
108
225k
  }
109
206k
110
206k
  // If our heuristic for a *good* bb to place this after doesn't find
111
206k
  // anything, just pick something.  It's likely better than leaving it within
112
206k
  // the loop.
113
206k
  if (!FoundBB)
114
201k
    FoundBB = SplitPreds[0];
115
206k
  NewBB->moveAfter(FoundBB);
116
206k
}
117
118
/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
119
/// preheader, this method is called to insert one.  This method has two phases:
120
/// preheader insertion and analysis updating.
121
///
122
BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
123
                                         LoopInfo *LI, MemorySSAUpdater *MSSAU,
124
489k
                                         bool PreserveLCSSA) {
125
489k
  BasicBlock *Header = L->getHeader();
126
489k
127
489k
  // Compute the set of predecessors of the loop that are not in the loop.
128
489k
  SmallVector<BasicBlock*, 8> OutsideBlocks;
129
489k
  for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
130
1.51M
       PI != PE; 
++PI1.02M
) {
131
1.02M
    BasicBlock *P = *PI;
132
1.02M
    if (!L->contains(P)) {         // Coming in from outside the loop?
133
522k
      // If the loop is branched to from an indirect terminator, we won't
134
522k
      // be able to fully transform the loop, because it prohibits
135
522k
      // edge splitting.
136
522k
      if (P->getTerminator()->isIndirectTerminator())
137
46
        return nullptr;
138
522k
139
522k
      // Keep track of it.
140
522k
      OutsideBlocks.push_back(P);
141
522k
    }
142
1.02M
  }
143
489k
144
489k
  // Split out the loop pre-header.
145
489k
  BasicBlock *PreheaderBB;
146
489k
  PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
147
489k
                                       LI, MSSAU, PreserveLCSSA);
148
489k
  if (!PreheaderBB)
149
0
    return nullptr;
150
489k
151
489k
  LLVM_DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
152
489k
                    << PreheaderBB->getName() << "\n");
153
489k
154
489k
  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
155
489k
  // code layout too horribly.
156
489k
  placeSplitBlockCarefully(PreheaderBB, OutsideBlocks, L);
157
489k
158
489k
  return PreheaderBB;
159
489k
}
160
161
/// Add the specified block, and all of its predecessors, to the specified set,
162
/// if it's not already in there.  Stop predecessor traversal when we reach
163
/// StopBlock.
164
static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
165
469
                                  std::set<BasicBlock*> &Blocks) {
166
469
  SmallVector<BasicBlock *, 8> Worklist;
167
469
  Worklist.push_back(InputBB);
168
8.38k
  do {
169
8.38k
    BasicBlock *BB = Worklist.pop_back_val();
170
8.38k
    if (Blocks.insert(BB).second && 
BB != StopBlock5.83k
)
171
5.49k
      // If BB is not already processed and it is not a stop block then
172
5.49k
      // insert its predecessor in the work list
173
13.4k
      
for (pred_iterator I = pred_begin(BB), E = pred_end(BB); 5.49k
I != E;
++I7.91k
) {
174
7.91k
        BasicBlock *WBB = *I;
175
7.91k
        Worklist.push_back(WBB);
176
7.91k
      }
177
8.38k
  } while (!Worklist.empty());
178
469
}
179
180
/// The first part of loop-nestification is to find a PHI node that tells
181
/// us how to partition the loops.
182
static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,
183
4.60k
                                        AssumptionCache *AC) {
184
4.60k
  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
185
6.91k
  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
186
2.64k
    PHINode *PN = cast<PHINode>(I);
187
2.64k
    ++I;
188
2.64k
    if (Value *V = SimplifyInstruction(PN, {DL, nullptr, DT, AC})) {
189
177
      // This is a degenerate PHI already, don't modify it!
190
177
      PN->replaceAllUsesWith(V);
191
177
      PN->eraseFromParent();
192
177
      continue;
193
177
    }
194
2.46k
195
2.46k
    // Scan this PHI node looking for a use of the PHI node by itself.
196
10.0k
    
for (unsigned i = 0, e = PN->getNumIncomingValues(); 2.46k
i != e;
++i7.58k
)
197
7.92k
      if (PN->getIncomingValue(i) == PN &&
198
7.92k
          
L->contains(PN->getIncomingBlock(i))339
)
199
339
        // We found something tasty to remove.
200
339
        return PN;
201
2.46k
  }
202
4.60k
  
return nullptr4.26k
;
203
4.60k
}
204
205
/// If this loop has multiple backedges, try to pull one of them out into
206
/// a nested loop.
207
///
208
/// This is important for code that looks like
209
/// this:
210
///
211
///  Loop:
212
///     ...
213
///     br cond, Loop, Next
214
///     ...
215
///     br cond2, Loop, Out
216
///
217
/// To identify this common case, we look at the PHI nodes in the header of the
218
/// loop.  PHI nodes with unchanging values on one backedge correspond to values
219
/// that change in the "outer" loop, but not in the "inner" loop.
220
///
221
/// If we are able to separate out a loop, return the new outer loop that was
222
/// created.
223
///
224
static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
225
                                DominatorTree *DT, LoopInfo *LI,
226
                                ScalarEvolution *SE, bool PreserveLCSSA,
227
4.61k
                                AssumptionCache *AC, MemorySSAUpdater *MSSAU) {
228
4.61k
  // Don't try to separate loops without a preheader.
229
4.61k
  if (!Preheader)
230
2
    return nullptr;
231
4.60k
232
4.60k
  // The header is not a landing pad; preheader insertion should ensure this.
233
4.60k
  BasicBlock *Header = L->getHeader();
234
4.60k
  assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
235
4.60k
236
4.60k
  PHINode *PN = findPHIToPartitionLoops(L, DT, AC);
237
4.60k
  if (!PN) 
return nullptr4.26k
; // No known way to partition.
238
339
239
339
  // Pull out all predecessors that have varying values in the loop.  This
240
339
  // handles the case when a PHI node has multiple instances of itself as
241
339
  // arguments.
242
339
  SmallVector<BasicBlock*, 8> OuterLoopPreds;
243
1.60k
  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; 
++i1.26k
) {
244
1.26k
    if (PN->getIncomingValue(i) != PN ||
245
1.26k
        
!L->contains(PN->getIncomingBlock(i))469
) {
246
795
      // We can't split indirect control flow edges.
247
795
      if (PN->getIncomingBlock(i)->getTerminator()->isIndirectTerminator())
248
1
        return nullptr;
249
794
      OuterLoopPreds.push_back(PN->getIncomingBlock(i));
250
794
    }
251
1.26k
  }
252
339
  
LLVM_DEBUG338
(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
253
338
254
338
  // If ScalarEvolution is around and knows anything about values in
255
338
  // this loop, tell it to forget them, because we're about to
256
338
  // substantially change it.
257
338
  if (SE)
258
2
    SE->forgetLoop(L);
259
338
260
338
  BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
261
338
                                             DT, LI, MSSAU, PreserveLCSSA);
262
338
263
338
  // Make sure that NewBB is put someplace intelligent, which doesn't mess up
264
338
  // code layout too horribly.
265
338
  placeSplitBlockCarefully(NewBB, OuterLoopPreds, L);
266
338
267
338
  // Create the new outer loop.
268
338
  Loop *NewOuter = LI->AllocateLoop();
269
338
270
338
  // Change the parent loop to use the outer loop as its child now.
271
338
  if (Loop *Parent = L->getParentLoop())
272
59
    Parent->replaceChildLoopWith(L, NewOuter);
273
279
  else
274
279
    LI->changeTopLevelLoop(L, NewOuter);
275
338
276
338
  // L is now a subloop of our outer loop.
277
338
  NewOuter->addChildLoop(L);
278
338
279
338
  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
280
12.8k
       I != E; 
++I12.5k
)
281
12.5k
    NewOuter->addBlockEntry(*I);
282
338
283
338
  // Now reset the header in L, which had been moved by
284
338
  // SplitBlockPredecessors for the outer loop.
285
338
  L->moveToHeader(Header);
286
338
287
338
  // Determine which blocks should stay in L and which should be moved out to
288
338
  // the Outer loop now.
289
338
  std::set<BasicBlock*> BlocksInL;
290
1.14k
  for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; 
++PI807
) {
291
807
    BasicBlock *P = *PI;
292
807
    if (DT->dominates(Header, P))
293
469
      addBlockAndPredsToSet(P, Header, BlocksInL);
294
807
  }
295
338
296
338
  // Scan all of the loop children of L, moving them to OuterLoop if they are
297
338
  // not part of the inner loop.
298
338
  const std::vector<Loop*> &SubLoops = L->getSubLoops();
299
852
  for (size_t I = 0; I != SubLoops.size(); )
300
514
    if (BlocksInL.count(SubLoops[I]->getHeader()))
301
209
      ++I;   // Loop remains in L
302
305
    else
303
305
      NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
304
338
305
338
  SmallVector<BasicBlock *, 8> OuterLoopBlocks;
306
338
  OuterLoopBlocks.push_back(NewBB);
307
338
  // Now that we know which blocks are in L and which need to be moved to
308
338
  // OuterLoop, move any blocks that need it.
309
12.8k
  for (unsigned i = 0; i != L->getBlocks().size(); 
++i12.5k
) {
310
12.5k
    BasicBlock *BB = L->getBlocks()[i];
311
12.5k
    if (!BlocksInL.count(BB)) {
312
6.69k
      // Move this block to the parent, updating the exit blocks sets
313
6.69k
      L->removeBlockFromLoop(BB);
314
6.69k
      if ((*LI)[BB] == L) {
315
4.63k
        LI->changeLoopFor(BB, NewOuter);
316
4.63k
        OuterLoopBlocks.push_back(BB);
317
4.63k
      }
318
6.69k
      --i;
319
6.69k
    }
320
12.5k
  }
321
338
322
338
  // Split edges to exit blocks from the inner loop, if they emerged in the
323
338
  // process of separating the outer one.
324
338
  formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA);
325
338
326
338
  if (PreserveLCSSA) {
327
4
    // Fix LCSSA form for L. Some values, which previously were only used inside
328
4
    // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
329
4
    // in corresponding exit blocks.
330
4
    // We don't need to form LCSSA recursively, because there cannot be uses
331
4
    // inside a newly created loop of defs from inner loops as those would
332
4
    // already be a use of an LCSSA phi node.
333
4
    formLCSSA(*L, *DT, LI, SE);
334
4
335
4
    assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
336
4
           "LCSSA is broken after separating nested loops!");
337
4
  }
338
338
339
338
  return NewOuter;
340
339
}
341
342
/// This method is called when the specified loop has more than one
343
/// backedge in it.
344
///
345
/// If this occurs, revector all of these backedges to target a new basic block
346
/// and have that block branch to the loop header.  This ensures that loops
347
/// have exactly one backedge.
348
static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
349
                                             DominatorTree *DT, LoopInfo *LI,
350
4.34k
                                             MemorySSAUpdater *MSSAU) {
351
4.34k
  assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
352
4.34k
353
4.34k
  // Get information about the loop
354
4.34k
  BasicBlock *Header = L->getHeader();
355
4.34k
  Function *F = Header->getParent();
356
4.34k
357
4.34k
  // Unique backedge insertion currently depends on having a preheader.
358
4.34k
  if (!Preheader)
359
2
    return nullptr;
360
4.34k
361
4.34k
  // The header is not an EH pad; preheader insertion should ensure this.
362
4.34k
  assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
363
4.34k
364
4.34k
  // Figure out which basic blocks contain back-edges to the loop header.
365
4.34k
  std::vector<BasicBlock*> BackedgeBlocks;
366
24.6k
  for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; 
++I20.3k
){
367
20.3k
    BasicBlock *P = *I;
368
20.3k
369
20.3k
    // Indirect edges cannot be split, so we must fail if we find one.
370
20.3k
    if (P->getTerminator()->isIndirectTerminator())
371
8
      return nullptr;
372
20.3k
373
20.3k
    if (P != Preheader) 
BackedgeBlocks.push_back(P)15.9k
;
374
20.3k
  }
375
4.34k
376
4.34k
  // Create and insert the new backedge block...
377
4.34k
  BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(),
378
4.33k
                                           Header->getName() + ".backedge", F);
379
4.33k
  BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
380
4.33k
  BETerminator->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc());
381
4.33k
382
4.33k
  LLVM_DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block "
383
4.33k
                    << BEBlock->getName() << "\n");
384
4.33k
385
4.33k
  // Move the new backedge block to right after the last backedge block.
386
4.33k
  Function::iterator InsertPos = ++BackedgeBlocks.back()->getIterator();
387
4.33k
  F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
388
4.33k
389
4.33k
  // Now that the block has been inserted into the function, create PHI nodes in
390
4.33k
  // the backedge block which correspond to any PHI nodes in the header block.
391
6.38k
  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); 
++I2.05k
) {
392
2.05k
    PHINode *PN = cast<PHINode>(I);
393
2.05k
    PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(),
394
2.05k
                                     PN->getName()+".be", BETerminator);
395
2.05k
396
2.05k
    // Loop over the PHI node, moving all entries except the one for the
397
2.05k
    // preheader over to the new PHI node.
398
2.05k
    unsigned PreheaderIdx = ~0U;
399
2.05k
    bool HasUniqueIncomingValue = true;
400
2.05k
    Value *UniqueValue = nullptr;
401
10.9k
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; 
++i8.93k
) {
402
8.93k
      BasicBlock *IBB = PN->getIncomingBlock(i);
403
8.93k
      Value *IV = PN->getIncomingValue(i);
404
8.93k
      if (IBB == Preheader) {
405
2.05k
        PreheaderIdx = i;
406
6.87k
      } else {
407
6.87k
        NewPN->addIncoming(IV, IBB);
408
6.87k
        if (HasUniqueIncomingValue) {
409
4.72k
          if (!UniqueValue)
410
2.05k
            UniqueValue = IV;
411
2.67k
          else if (UniqueValue != IV)
412
1.24k
            HasUniqueIncomingValue = false;
413
4.72k
        }
414
6.87k
      }
415
8.93k
    }
416
2.05k
417
2.05k
    // Delete all of the incoming values from the old PN except the preheader's
418
2.05k
    assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
419
2.05k
    if (PreheaderIdx != 0) {
420
793
      PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
421
793
      PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
422
793
    }
423
2.05k
    // Nuke all entries except the zero'th.
424
8.93k
    for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; 
++i6.87k
)
425
6.87k
      PN->removeIncomingValue(e-i, false);
426
2.05k
427
2.05k
    // Finally, add the newly constructed PHI node as the entry for the BEBlock.
428
2.05k
    PN->addIncoming(NewPN, BEBlock);
429
2.05k
430
2.05k
    // As an optimization, if all incoming values in the new PhiNode (which is a
431
2.05k
    // subset of the incoming values of the old PHI node) have the same value,
432
2.05k
    // eliminate the PHI Node.
433
2.05k
    if (HasUniqueIncomingValue) {
434
811
      NewPN->replaceAllUsesWith(UniqueValue);
435
811
      BEBlock->getInstList().erase(NewPN);
436
811
    }
437
2.05k
  }
438
4.33k
439
4.33k
  // Now that all of the PHI nodes have been inserted and adjusted, modify the
440
4.33k
  // backedge blocks to jump to the BEBlock instead of the header.
441
4.33k
  // If one of the backedges has llvm.loop metadata attached, we remove
442
4.33k
  // it from the backedge and add it to BEBlock.
443
4.33k
  unsigned LoopMDKind = BEBlock->getContext().getMDKindID("llvm.loop");
444
4.33k
  MDNode *LoopMD = nullptr;
445
20.3k
  for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; 
++i15.9k
) {
446
15.9k
    Instruction *TI = BackedgeBlocks[i]->getTerminator();
447
15.9k
    if (!LoopMD)
448
15.7k
      LoopMD = TI->getMetadata(LoopMDKind);
449
15.9k
    TI->setMetadata(LoopMDKind, nullptr);
450
15.9k
    TI->replaceSuccessorWith(Header, BEBlock);
451
15.9k
  }
452
4.33k
  BEBlock->getTerminator()->setMetadata(LoopMDKind, LoopMD);
453
4.33k
454
4.33k
  //===--- Update all analyses which we must preserve now -----------------===//
455
4.33k
456
4.33k
  // Update Loop Information - we know that this block is now in the current
457
4.33k
  // loop and all parent loops.
458
4.33k
  L->addBasicBlockToLoop(BEBlock, *LI);
459
4.33k
460
4.33k
  // Update dominator information
461
4.33k
  DT->splitBlock(BEBlock);
462
4.33k
463
4.33k
  if (MSSAU)
464
11
    MSSAU->updatePhisWhenInsertingUniqueBackedgeBlock(Header, Preheader,
465
11
                                                      BEBlock);
466
4.33k
467
4.33k
  return BEBlock;
468
4.34k
}
469
470
/// Simplify one loop and queue further loops for simplification.
471
static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
472
                            DominatorTree *DT, LoopInfo *LI,
473
                            ScalarEvolution *SE, AssumptionCache *AC,
474
1.97M
                            MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
475
1.97M
  bool Changed = false;
476
1.97M
  if (MSSAU && 
VerifyMemorySSA347
)
477
323
    MSSAU->getMemorySSA()->verifyMemorySSA();
478
1.97M
479
1.97M
ReprocessLoop:
480
1.97M
481
1.97M
  // Check to see that no blocks (other than the header) in this loop have
482
1.97M
  // predecessors that are not in the loop.  This is not valid for natural
483
1.97M
  // loops, but can occur if the blocks are unreachable.  Since they are
484
1.97M
  // unreachable we can just shamelessly delete those CFG edges!
485
1.97M
  for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
486
10.9M
       BB != E; 
++BB9.00M
) {
487
9.00M
    if (*BB == L->getHeader()) 
continue1.97M
;
488
7.03M
489
7.03M
    SmallPtrSet<BasicBlock*, 4> BadPreds;
490
7.03M
    for (pred_iterator PI = pred_begin(*BB),
491
17.6M
         PE = pred_end(*BB); PI != PE; 
++PI10.5M
) {
492
10.5M
      BasicBlock *P = *PI;
493
10.5M
      if (!L->contains(P))
494
36
        BadPreds.insert(P);
495
10.5M
    }
496
7.03M
497
7.03M
    // Delete each unique out-of-loop (and thus dead) predecessor.
498
7.03M
    for (BasicBlock *P : BadPreds) {
499
36
500
36
      LLVM_DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
501
36
                        << P->getName() << "\n");
502
36
503
36
      // Zap the dead pred's terminator and replace it with unreachable.
504
36
      Instruction *TI = P->getTerminator();
505
36
      changeToUnreachable(TI, /*UseLLVMTrap=*/false, PreserveLCSSA,
506
36
                          /*DTU=*/nullptr, MSSAU);
507
36
      Changed = true;
508
36
    }
509
7.03M
  }
510
1.97M
511
1.97M
  if (MSSAU && 
VerifyMemorySSA347
)
512
323
    MSSAU->getMemorySSA()->verifyMemorySSA();
513
1.97M
514
1.97M
  // If there are exiting blocks with branches on undef, resolve the undef in
515
1.97M
  // the direction which will exit the loop. This will help simplify loop
516
1.97M
  // trip count computations.
517
1.97M
  SmallVector<BasicBlock*, 8> ExitingBlocks;
518
1.97M
  L->getExitingBlocks(ExitingBlocks);
519
1.97M
  for (BasicBlock *ExitingBlock : ExitingBlocks)
520
2.69M
    if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
521
2.57M
      if (BI->isConditional()) {
522
2.57M
        if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
523
734
524
734
          LLVM_DEBUG(dbgs()
525
734
                     << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
526
734
                     << ExitingBlock->getName() << "\n");
527
734
528
734
          BI->setCondition(ConstantInt::get(Cond->getType(),
529
734
                                            !L->contains(BI->getSuccessor(0))));
530
734
531
734
          Changed = true;
532
734
        }
533
2.57M
      }
534
1.97M
535
1.97M
  // Does the loop already have a preheader?  If so, don't insert one.
536
1.97M
  BasicBlock *Preheader = L->getLoopPreheader();
537
1.97M
  if (!Preheader) {
538
489k
    Preheader = InsertPreheaderForLoop(L, DT, LI, MSSAU, PreserveLCSSA);
539
489k
    if (Preheader)
540
489k
      Changed = true;
541
489k
  }
542
1.97M
543
1.97M
  // Next, check to make sure that all exit nodes of the loop only have
544
1.97M
  // predecessors that are inside of the loop.  This check guarantees that the
545
1.97M
  // loop preheader/header will dominate the exit blocks.  If the exit block has
546
1.97M
  // predecessors from outside of the loop, split the edge now.
547
1.97M
  if (formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA))
548
717k
    Changed = true;
549
1.97M
550
1.97M
  if (MSSAU && 
VerifyMemorySSA347
)
551
323
    MSSAU->getMemorySSA()->verifyMemorySSA();
552
1.97M
553
1.97M
  // If the header has more than two predecessors at this point (from the
554
1.97M
  // preheader and from multiple backedges), we must adjust the loop.
555
1.97M
  BasicBlock *LoopLatch = L->getLoopLatch();
556
1.97M
  if (!LoopLatch) {
557
4.68k
    // If this is really a nested loop, rip it out into a child loop.  Don't do
558
4.68k
    // this for loops with a giant number of backedges, just factor them into a
559
4.68k
    // common backedge instead.
560
4.68k
    if (L->getNumBackEdges() < 8) {
561
4.61k
      if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE,
562
338
                                            PreserveLCSSA, AC, MSSAU)) {
563
338
        ++NumNested;
564
338
        // Enqueue the outer loop as it should be processed next in our
565
338
        // depth-first nest walk.
566
338
        Worklist.push_back(OuterL);
567
338
568
338
        // This is a big restructuring change, reprocess the whole loop.
569
338
        Changed = true;
570
338
        // GCC doesn't tail recursion eliminate this.
571
338
        // FIXME: It isn't clear we can't rely on LLVM to TRE this.
572
338
        goto ReprocessLoop;
573
338
      }
574
4.34k
    }
575
4.34k
576
4.34k
    // If we either couldn't, or didn't want to, identify nesting of the loops,
577
4.34k
    // insert a new block that all backedges target, then make it jump to the
578
4.34k
    // loop header.
579
4.34k
    LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI, MSSAU);
580
4.34k
    if (LoopLatch)
581
4.33k
      Changed = true;
582
4.34k
  }
583
1.97M
584
1.97M
  
if (1.97M
MSSAU1.97M
&&
VerifyMemorySSA347
)
585
323
    MSSAU->getMemorySSA()->verifyMemorySSA();
586
1.97M
587
1.97M
  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
588
1.97M
589
1.97M
  // Scan over the PHI nodes in the loop header.  Since they now have only two
590
1.97M
  // incoming values (the loop is canonicalized), we may have simplified the PHI
591
1.97M
  // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
592
1.97M
  PHINode *PN;
593
1.97M
  for (BasicBlock::iterator I = L->getHeader()->begin();
594
4.71M
       (PN = dyn_cast<PHINode>(I++)); )
595
2.73M
    if (Value *V = SimplifyInstruction(PN, {DL, nullptr, DT, AC})) {
596
791
      if (SE) 
SE->forgetValue(PN)130
;
597
791
      if (!PreserveLCSSA || 
LI->replacementPreservesLCSSAForm(PN, V)131
) {
598
790
        PN->replaceAllUsesWith(V);
599
790
        PN->eraseFromParent();
600
790
      }
601
791
    }
602
1.97M
603
1.97M
  // If this loop has multiple exits and the exits all go to the same
604
1.97M
  // block, attempt to merge the exits. This helps several passes, such
605
1.97M
  // as LoopRotation, which do not support loops with multiple exits.
606
1.97M
  // SimplifyCFG also does this (and this code uses the same utility
607
1.97M
  // function), however this code is loop-aware, where SimplifyCFG is
608
1.97M
  // not. That gives it the advantage of being able to hoist
609
1.97M
  // loop-invariant instructions out of the way to open up more
610
1.97M
  // opportunities, and the disadvantage of having the responsibility
611
1.97M
  // to preserve dominator information.
612
1.97M
  auto HasUniqueExitBlock = [&]() {
613
1.97M
    BasicBlock *UniqueExit = nullptr;
614
1.97M
    for (auto *ExitingBB : ExitingBlocks)
615
4.79M
      
for (auto *SuccBB : successors(ExitingBB))2.50M
{
616
4.79M
        if (L->contains(SuccBB))
617
2.28M
          continue;
618
2.51M
619
2.51M
        if (!UniqueExit)
620
1.97M
          UniqueExit = SuccBB;
621
538k
        else if (UniqueExit != SuccBB)
622
393k
          return false;
623
2.51M
      }
624
1.97M
625
1.97M
    
return true1.58M
;
626
1.97M
  };
627
1.97M
  if (HasUniqueExitBlock()) {
628
3.28M
    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; 
++i1.69M
) {
629
1.69M
      BasicBlock *ExitingBlock = ExitingBlocks[i];
630
1.69M
      if (!ExitingBlock->getSinglePredecessor()) 
continue1.49M
;
631
205k
      BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
632
205k
      if (!BI || 
!BI->isConditional()205k
)
continue570
;
633
205k
      CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
634
205k
      if (!CI || 
CI->getParent() != ExitingBlock201k
)
continue4.10k
;
635
200k
636
200k
      // Attempt to hoist out all instructions except for the
637
200k
      // comparison and the branch.
638
200k
      bool AllInvariant = true;
639
200k
      bool AnyInvariant = false;
640
211k
      for (auto I = ExitingBlock->instructionsWithoutDebug().begin(); &*I != BI; ) {
641
202k
        Instruction *Inst = &*I++;
642
202k
        if (Inst == CI)
643
10.0k
          continue;
644
192k
        if (!L->makeLoopInvariant(
645
192k
                Inst, AnyInvariant,
646
192k
                Preheader ? Preheader->getTerminator() : 
nullptr0
, MSSAU)) {
647
191k
          AllInvariant = false;
648
191k
          break;
649
191k
        }
650
192k
      }
651
200k
      if (AnyInvariant) {
652
771
        Changed = true;
653
771
        // The loop disposition of all SCEV expressions that depend on any
654
771
        // hoisted values have also changed.
655
771
        if (SE)
656
99
          SE->forgetLoopDispositions(L);
657
771
      }
658
200k
      if (!AllInvariant) 
continue191k
;
659
9.87k
660
9.87k
      // The block has now been cleared of all instructions except for
661
9.87k
      // a comparison and a conditional branch. SimplifyCFG may be able
662
9.87k
      // to fold it now.
663
9.87k
      if (!FoldBranchToCommonDest(BI, MSSAU))
664
9.80k
        continue;
665
78
666
78
      // Success. The block is now dead, so remove it from the loop,
667
78
      // update the dominator tree and delete it.
668
78
      LLVM_DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
669
78
                        << ExitingBlock->getName() << "\n");
670
78
671
78
      assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
672
78
      Changed = true;
673
78
      LI->removeBlock(ExitingBlock);
674
78
675
78
      DomTreeNode *Node = DT->getNode(ExitingBlock);
676
78
      const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
677
78
        Node->getChildren();
678
88
      while (!Children.empty()) {
679
10
        DomTreeNode *Child = Children.front();
680
10
        DT->changeImmediateDominator(Child, Node->getIDom());
681
10
      }
682
78
      DT->eraseNode(ExitingBlock);
683
78
      if (MSSAU) {
684
0
        SmallSetVector<BasicBlock *, 8> ExitBlockSet;
685
0
        ExitBlockSet.insert(ExitingBlock);
686
0
        MSSAU->removeBlocks(ExitBlockSet);
687
0
      }
688
78
689
78
      BI->getSuccessor(0)->removePredecessor(
690
78
          ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
691
78
      BI->getSuccessor(1)->removePredecessor(
692
78
          ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
693
78
      ExitingBlock->eraseFromParent();
694
78
    }
695
1.58M
  }
696
1.97M
697
1.97M
  // Changing exit conditions for blocks may affect exit counts of this loop and
698
1.97M
  // any of its paretns, so we must invalidate the entire subtree if we've made
699
1.97M
  // any changes.
700
1.97M
  if (Changed && 
SE861k
)
701
134k
    SE->forgetTopmostLoop(L);
702
1.97M
703
1.97M
  if (MSSAU && 
VerifyMemorySSA347
)
704
323
    MSSAU->getMemorySSA()->verifyMemorySSA();
705
1.97M
706
1.97M
  return Changed;
707
1.97M
}
708
709
bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
710
                        ScalarEvolution *SE, AssumptionCache *AC,
711
1.42M
                        MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
712
1.42M
  bool Changed = false;
713
1.42M
714
#ifndef NDEBUG
715
  // If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA
716
  // form.
717
  if (PreserveLCSSA) {
718
    assert(DT && "DT not available.");
719
    assert(LI && "LI not available.");
720
    assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
721
           "Requested to preserve LCSSA, but it's already broken.");
722
  }
723
#endif
724
725
1.42M
  // Worklist maintains our depth-first queue of loops in this nest to process.
726
1.42M
  SmallVector<Loop *, 4> Worklist;
727
1.42M
  Worklist.push_back(L);
728
1.42M
729
1.42M
  // Walk the worklist from front to back, pushing newly found sub loops onto
730
1.42M
  // the back. This will let us process loops from back to front in depth-first
731
1.42M
  // order. We can use this simple process because loops form a tree.
732
3.40M
  for (unsigned Idx = 0; Idx != Worklist.size(); 
++Idx1.97M
) {
733
1.97M
    Loop *L2 = Worklist[Idx];
734
1.97M
    Worklist.append(L2->begin(), L2->end());
735
1.97M
  }
736
1.42M
737
3.40M
  while (!Worklist.empty())
738
1.97M
    Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
739
1.97M
                               AC, MSSAU, PreserveLCSSA);
740
1.42M
741
1.42M
  return Changed;
742
1.42M
}
743
744
namespace {
745
  struct LoopSimplify : public FunctionPass {
746
    static char ID; // Pass identification, replacement for typeid
747
142k
    LoopSimplify() : FunctionPass(ID) {
748
142k
      initializeLoopSimplifyPass(*PassRegistry::getPassRegistry());
749
142k
    }
750
751
    bool runOnFunction(Function &F) override;
752
753
142k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
754
142k
      AU.addRequired<AssumptionCacheTracker>();
755
142k
756
142k
      // We need loop information to identify the loops...
757
142k
      AU.addRequired<DominatorTreeWrapperPass>();
758
142k
      AU.addPreserved<DominatorTreeWrapperPass>();
759
142k
760
142k
      AU.addRequired<LoopInfoWrapperPass>();
761
142k
      AU.addPreserved<LoopInfoWrapperPass>();
762
142k
763
142k
      AU.addPreserved<BasicAAWrapperPass>();
764
142k
      AU.addPreserved<AAResultsWrapperPass>();
765
142k
      AU.addPreserved<GlobalsAAWrapperPass>();
766
142k
      AU.addPreserved<ScalarEvolutionWrapperPass>();
767
142k
      AU.addPreserved<SCEVAAWrapperPass>();
768
142k
      AU.addPreservedID(LCSSAID);
769
142k
      AU.addPreserved<DependenceAnalysisWrapperPass>();
770
142k
      AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
771
142k
      AU.addPreserved<BranchProbabilityInfoWrapperPass>();
772
142k
      if (EnableMSSALoopDependency)
773
91
        AU.addPreserved<MemorySSAWrapperPass>();
774
142k
    }
775
776
    /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
777
    void verifyAnalysis() const override;
778
  };
779
}
780
781
char LoopSimplify::ID = 0;
782
102k
INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
783
102k
                "Canonicalize natural loops", false, false)
784
102k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
785
102k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
786
102k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
787
102k
INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
788
                "Canonicalize natural loops", false, false)
789
790
// Publicly exposed interface to pass...
791
char &llvm::LoopSimplifyID = LoopSimplify::ID;
792
0
Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
793
794
/// runOnFunction - Run down all loops in the CFG (recursively, but we could do
795
/// it in any convenient order) inserting preheaders...
796
///
797
3.30M
bool LoopSimplify::runOnFunction(Function &F) {
798
3.30M
  bool Changed = false;
799
3.30M
  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
800
3.30M
  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
801
3.30M
  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
802
3.30M
  ScalarEvolution *SE = SEWP ? 
&SEWP->getSE()265k
:
nullptr3.04M
;
803
3.30M
  AssumptionCache *AC =
804
3.30M
      &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
805
3.30M
  MemorySSA *MSSA = nullptr;
806
3.30M
  std::unique_ptr<MemorySSAUpdater> MSSAU;
807
3.30M
  if (EnableMSSALoopDependency) {
808
273
    auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
809
273
    if (MSSAAnalysis) {
810
270
      MSSA = &MSSAAnalysis->getMSSA();
811
270
      MSSAU = make_unique<MemorySSAUpdater>(MSSA);
812
270
    }
813
273
  }
814
3.30M
815
3.30M
  bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
816
3.30M
817
3.30M
  // Simplify each loop nest in the function.
818
4.59M
  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; 
++I1.29M
)
819
1.29M
    Changed |= simplifyLoop(*I, DT, LI, SE, AC, MSSAU.get(), PreserveLCSSA);
820
3.30M
821
#ifndef NDEBUG
822
  if (PreserveLCSSA) {
823
    bool InLCSSA = all_of(
824
        *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
825
    assert(InLCSSA && "LCSSA is broken after loop-simplify.");
826
  }
827
#endif
828
  return Changed;
829
3.30M
}
830
831
PreservedAnalyses LoopSimplifyPass::run(Function &F,
832
6.21k
                                        FunctionAnalysisManager &AM) {
833
6.21k
  bool Changed = false;
834
6.21k
  LoopInfo *LI = &AM.getResult<LoopAnalysis>(F);
835
6.21k
  DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
836
6.21k
  ScalarEvolution *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
837
6.21k
  AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
838
6.21k
839
6.21k
  // Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA
840
6.21k
  // after simplifying the loops. MemorySSA is not preserved either.
841
7.52k
  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; 
++I1.31k
)
842
1.31k
    Changed |=
843
1.31k
        simplifyLoop(*I, DT, LI, SE, AC, nullptr, /*PreserveLCSSA*/ false);
844
6.21k
845
6.21k
  if (!Changed)
846
5.89k
    return PreservedAnalyses::all();
847
321
848
321
  PreservedAnalyses PA;
849
321
  PA.preserve<DominatorTreeAnalysis>();
850
321
  PA.preserve<LoopAnalysis>();
851
321
  PA.preserve<BasicAA>();
852
321
  PA.preserve<GlobalsAA>();
853
321
  PA.preserve<SCEVAA>();
854
321
  PA.preserve<ScalarEvolutionAnalysis>();
855
321
  PA.preserve<DependenceAnalysis>();
856
321
  // BPI maps conditional terminators to probabilities, LoopSimplify can insert
857
321
  // blocks, but it does so only by splitting existing blocks and edges. This
858
321
  // results in the interesting property that all new terminators inserted are
859
321
  // unconditional branches which do not appear in BPI. All deletions are
860
321
  // handled via ValueHandle callbacks w/in BPI.
861
321
  PA.preserve<BranchProbabilityAnalysis>();
862
321
  return PA;
863
321
}
864
865
// FIXME: Restore this code when we re-enable verification in verifyAnalysis
866
// below.
867
#if 0
868
static void verifyLoop(Loop *L) {
869
  // Verify subloops.
870
  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
871
    verifyLoop(*I);
872
873
  // It used to be possible to just assert L->isLoopSimplifyForm(), however
874
  // with the introduction of indirectbr, there are now cases where it's
875
  // not possible to transform a loop as necessary. We can at least check
876
  // that there is an indirectbr near any time there's trouble.
877
878
  // Indirectbr can interfere with preheader and unique backedge insertion.
879
  if (!L->getLoopPreheader() || !L->getLoopLatch()) {
880
    bool HasIndBrPred = false;
881
    for (pred_iterator PI = pred_begin(L->getHeader()),
882
         PE = pred_end(L->getHeader()); PI != PE; ++PI)
883
      if (isa<IndirectBrInst>((*PI)->getTerminator())) {
884
        HasIndBrPred = true;
885
        break;
886
      }
887
    assert(HasIndBrPred &&
888
           "LoopSimplify has no excuse for missing loop header info!");
889
    (void)HasIndBrPred;
890
  }
891
892
  // Indirectbr can interfere with exit block canonicalization.
893
  if (!L->hasDedicatedExits()) {
894
    bool HasIndBrExiting = false;
895
    SmallVector<BasicBlock*, 8> ExitingBlocks;
896
    L->getExitingBlocks(ExitingBlocks);
897
    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
898
      if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) {
899
        HasIndBrExiting = true;
900
        break;
901
      }
902
    }
903
904
    assert(HasIndBrExiting &&
905
           "LoopSimplify has no excuse for missing exit block info!");
906
    (void)HasIndBrExiting;
907
  }
908
}
909
#endif
910
911
0
void LoopSimplify::verifyAnalysis() const {
912
0
  // FIXME: This routine is being called mid-way through the loop pass manager
913
0
  // as loop passes destroy this analysis. That's actually fine, but we have no
914
0
  // way of expressing that here. Once all of the passes that destroy this are
915
0
  // hoisted out of the loop pass manager we can add back verification here.
916
#if 0
917
  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
918
    verifyLoop(*I);
919
#endif
920
}