Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
10
#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
11
#include "llvm/ADT/DenseMap.h"
12
#include "llvm/ADT/STLExtras.h"
13
#include "llvm/ADT/Sequence.h"
14
#include "llvm/ADT/SetVector.h"
15
#include "llvm/ADT/SmallPtrSet.h"
16
#include "llvm/ADT/SmallVector.h"
17
#include "llvm/ADT/Statistic.h"
18
#include "llvm/ADT/Twine.h"
19
#include "llvm/Analysis/AssumptionCache.h"
20
#include "llvm/Analysis/LoopAnalysisManager.h"
21
#include "llvm/Analysis/LoopInfo.h"
22
#include "llvm/Analysis/LoopPass.h"
23
#include "llvm/IR/BasicBlock.h"
24
#include "llvm/IR/Constant.h"
25
#include "llvm/IR/Constants.h"
26
#include "llvm/IR/Dominators.h"
27
#include "llvm/IR/Function.h"
28
#include "llvm/IR/InstrTypes.h"
29
#include "llvm/IR/Instruction.h"
30
#include "llvm/IR/Instructions.h"
31
#include "llvm/IR/Use.h"
32
#include "llvm/IR/Value.h"
33
#include "llvm/Pass.h"
34
#include "llvm/Support/Casting.h"
35
#include "llvm/Support/Debug.h"
36
#include "llvm/Support/ErrorHandling.h"
37
#include "llvm/Support/GenericDomTree.h"
38
#include "llvm/Support/raw_ostream.h"
39
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
40
#include "llvm/Transforms/Utils/LoopUtils.h"
41
#include <algorithm>
42
#include <cassert>
43
#include <iterator>
44
#include <utility>
45
46
#define DEBUG_TYPE "simple-loop-unswitch"
47
48
using namespace llvm;
49
50
STATISTIC(NumBranches, "Number of branches unswitched");
51
STATISTIC(NumSwitches, "Number of switches unswitched");
52
STATISTIC(NumTrivial, "Number of unswitches that are trivial");
53
54
static void replaceLoopUsesWithConstant(Loop &L, Value &LIC,
55
13
                                        Constant &Replacement) {
56
13
  assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
57
13
58
13
  // Replace uses of LIC in the loop with the given constant.
59
26
  for (auto UI = LIC.use_begin(), UE = LIC.use_end(); 
UI != UE26
;) {
60
13
    // Grab the use and walk past it so we can clobber it in the use list.
61
13
    Use *U = &*UI++;
62
13
    Instruction *UserI = dyn_cast<Instruction>(U->getUser());
63
13
    if (
!UserI || 13
!L.contains(UserI)13
)
64
13
      continue;
65
0
66
0
    // Replace this use within the loop body.
67
0
    *U = &Replacement;
68
0
  }
69
13
}
70
71
/// Update the dominator tree after removing one exiting predecessor of a loop
72
/// exit block.
73
static void updateLoopExitIDom(BasicBlock *LoopExitBB, Loop &L,
74
5
                               DominatorTree &DT) {
75
5
  assert(pred_begin(LoopExitBB) != pred_end(LoopExitBB) &&
76
5
         "Cannot have empty predecessors of the loop exit block if we split "
77
5
         "off a block to unswitch!");
78
5
79
5
  BasicBlock *IDom = *pred_begin(LoopExitBB);
80
5
  // Walk all of the other predecessors finding the nearest common dominator
81
5
  // until all predecessors are covered or we reach the loop header. The loop
82
5
  // header necessarily dominates all loop exit blocks in loop simplified form
83
5
  // so we can early-exit the moment we hit that block.
84
5
  for (auto PI = std::next(pred_begin(LoopExitBB)), PE = pred_end(LoopExitBB);
85
5
       
PI != PE && 5
IDom != L.getHeader()0
;
++PI0
)
86
0
    IDom = DT.findNearestCommonDominator(IDom, *PI);
87
5
88
5
  DT.changeImmediateDominator(LoopExitBB, IDom);
89
5
}
90
91
/// Update the dominator tree after unswitching a particular former exit block.
92
///
93
/// This handles the full update of the dominator tree after hoisting a block
94
/// that previously was an exit block (or split off of an exit block) up to be
95
/// reached from the new immediate dominator of the preheader.
96
///
97
/// The common case is simple -- we just move the unswitched block to have an
98
/// immediate dominator of the old preheader. But in complex cases, there may
99
/// be other blocks reachable from the unswitched block that are immediately
100
/// dominated by some node between the unswitched one and the old preheader.
101
/// All of these also need to be hoisted in the dominator tree. We also want to
102
/// minimize queries to the dominator tree because each step of this
103
/// invalidates any DFS numbers that would make queries fast.
104
static void updateDTAfterUnswitch(BasicBlock *UnswitchedBB, BasicBlock *OldPH,
105
69
                                  DominatorTree &DT) {
106
69
  DomTreeNode *OldPHNode = DT[OldPH];
107
69
  DomTreeNode *UnswitchedNode = DT[UnswitchedBB];
108
69
  // If the dominator tree has already been updated for this unswitched node,
109
69
  // we're done. This makes it easier to use this routine if there are multiple
110
69
  // paths to the same unswitched destination.
111
69
  if (UnswitchedNode->getIDom() == OldPHNode)
112
33
    return;
113
36
114
36
  // First collect the domtree nodes that we are hoisting over. These are the
115
36
  // set of nodes which may have children that need to be hoisted as well.
116
36
  SmallPtrSet<DomTreeNode *, 4> DomChain;
117
117
  for (auto *IDom = UnswitchedNode->getIDom(); IDom != OldPHNode;
118
81
       IDom = IDom->getIDom())
119
81
    DomChain.insert(IDom);
120
36
121
36
  // The unswitched block ends up immediately dominated by the old preheader --
122
36
  // regardless of whether it is the loop exit block or split off of the loop
123
36
  // exit block.
124
36
  DT.changeImmediateDominator(UnswitchedNode, OldPHNode);
125
36
126
36
  // For everything that moves up the dominator tree, we need to examine the
127
36
  // dominator frontier to see if it additionally should move up the dominator
128
36
  // tree. This lambda appends the dominator frontier for a node on the
129
36
  // worklist.
130
36
  //
131
36
  // Note that we don't currently use the IDFCalculator here for two reasons:
132
36
  // 1) It computes dominator tree levels for the entire function on each run
133
36
  //    of 'compute'. While this isn't terrible, given that we expect to update
134
36
  //    relatively small subtrees of the domtree, it isn't necessarily the right
135
36
  //    tradeoff.
136
36
  // 2) The interface doesn't fit this usage well. It doesn't operate in
137
36
  //    append-only, and builds several sets that we don't need.
138
36
  //
139
36
  // FIXME: Neither of these issues are a big deal and could be addressed with
140
36
  // some amount of refactoring of IDFCalculator. That would allow us to share
141
36
  // the core logic here (which is solving the same core problem).
142
36
  SmallSetVector<BasicBlock *, 4> Worklist;
143
36
  SmallVector<DomTreeNode *, 4> DomNodes;
144
36
  SmallPtrSet<BasicBlock *, 4> DomSet;
145
43
  auto AppendDomFrontier = [&](DomTreeNode *Node) {
146
43
    assert(DomNodes.empty() && "Must start with no dominator nodes.");
147
43
    assert(DomSet.empty() && "Must start with an empty dominator set.");
148
43
149
43
    // First flatten this subtree into sequence of nodes by doing a pre-order
150
43
    // walk.
151
43
    DomNodes.push_back(Node);
152
43
    // We intentionally re-evaluate the size as each node can add new children.
153
43
    // Because this is a tree walk, this cannot add any duplicates.
154
90
    for (int i = 0; 
i < (int)DomNodes.size()90
;
++i47
)
155
47
      DomNodes.insert(DomNodes.end(), DomNodes[i]->begin(), DomNodes[i]->end());
156
43
157
43
    // Now create a set of the basic blocks so we can quickly test for
158
43
    // dominated successors. We could in theory use the DFS numbers of the
159
43
    // dominator tree for this, but we want this to remain predictably fast
160
43
    // even while we mutate the dominator tree in ways that would invalidate
161
43
    // the DFS numbering.
162
43
    for (DomTreeNode *InnerN : DomNodes)
163
47
      DomSet.insert(InnerN->getBlock());
164
43
165
43
    // Now re-walk the nodes, appending every successor of every node that isn't
166
43
    // in the set. Note that we don't append the node itself, even though if it
167
43
    // is a successor it does not strictly dominate itself and thus it would be
168
43
    // part of the dominance frontier. The reason we don't append it is that
169
43
    // the node passed in came *from* the worklist and so it has already been
170
43
    // processed.
171
43
    for (DomTreeNode *InnerN : DomNodes)
172
47
      for (BasicBlock *SuccBB : successors(InnerN->getBlock()))
173
15
        
if (15
!DomSet.count(SuccBB)15
)
174
11
          Worklist.insert(SuccBB);
175
43
176
43
    DomNodes.clear();
177
43
    DomSet.clear();
178
43
  };
179
36
180
36
  // Append the initial dom frontier nodes.
181
36
  AppendDomFrontier(UnswitchedNode);
182
36
183
36
  // Walk the worklist. We grow the list in the loop and so must recompute size.
184
47
  for (int i = 0; 
i < (int)Worklist.size()47
;
++i11
) {
185
11
    auto *BB = Worklist[i];
186
11
187
11
    DomTreeNode *Node = DT[BB];
188
11
    assert(!DomChain.count(Node) &&
189
11
           "Cannot be dominated by a block you can reach!");
190
11
191
11
    // If this block had an immediate dominator somewhere in the chain
192
11
    // we hoisted over, then its position in the domtree needs to move as it is
193
11
    // reachable from a node hoisted over this chain.
194
11
    if (!DomChain.count(Node->getIDom()))
195
4
      continue;
196
7
197
7
    DT.changeImmediateDominator(Node, OldPHNode);
198
7
199
7
    // Now add this node's dominator frontier to the worklist as well.
200
7
    AppendDomFrontier(Node);
201
7
  }
202
69
}
203
204
/// Check that all the LCSSA PHI nodes in the loop exit block have trivial
205
/// incoming values along this edge.
206
static bool areLoopExitPHIsLoopInvariant(Loop &L, BasicBlock &ExitingBB,
207
72
                                         BasicBlock &ExitBB) {
208
88
  for (Instruction &I : ExitBB) {
209
88
    auto *PN = dyn_cast<PHINode>(&I);
210
88
    if (!PN)
211
88
      // No more PHIs to check.
212
69
      return true;
213
19
214
19
    // If the incoming value for this edge isn't loop invariant the unswitch
215
19
    // won't be trivial.
216
19
    
if (19
!L.isLoopInvariant(PN->getIncomingValueForBlock(&ExitingBB))19
)
217
3
      return false;
218
0
  }
219
0
  
llvm_unreachable0
("Basic blocks should never be empty!");
220
0
}
221
222
/// Rewrite the PHI nodes in an unswitched loop exit basic block.
223
///
224
/// Requires that the loop exit and unswitched basic block are the same, and
225
/// that the exiting block was a unique predecessor of that block. Rewrites the
226
/// PHI nodes in that block such that what were LCSSA PHI nodes become trivial
227
/// PHI nodes from the old preheader that now contains the unswitched
228
/// terminator.
229
static void rewritePHINodesForUnswitchedExitBlock(BasicBlock &UnswitchedBB,
230
                                                  BasicBlock &OldExitingBB,
231
31
                                                  BasicBlock &OldPH) {
232
38
  for (Instruction &I : UnswitchedBB) {
233
38
    auto *PN = dyn_cast<PHINode>(&I);
234
38
    if (!PN)
235
38
      // No more PHIs to check.
236
31
      break;
237
7
238
7
    // When the loop exit is directly unswitched we just need to update the
239
7
    // incoming basic block. We loop to handle weird cases with repeated
240
7
    // incoming blocks, but expect to typically only have one operand here.
241
7
    
for (auto i : seq<int>(0, PN->getNumOperands())) 7
{
242
9
      assert(PN->getIncomingBlock(i) == &OldExitingBB &&
243
9
             "Found incoming block different from unique predecessor!");
244
9
      PN->setIncomingBlock(i, &OldPH);
245
9
    }
246
38
  }
247
31
}
248
249
/// Rewrite the PHI nodes in the loop exit basic block and the split off
250
/// unswitched block.
251
///
252
/// Because the exit block remains an exit from the loop, this rewrites the
253
/// LCSSA PHI nodes in it to remove the unswitched edge and introduces PHI
254
/// nodes into the unswitched basic block to select between the value in the
255
/// old preheader and the loop exit.
256
static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB,
257
                                                      BasicBlock &UnswitchedBB,
258
                                                      BasicBlock &OldExitingBB,
259
5
                                                      BasicBlock &OldPH) {
260
5
  assert(&ExitBB != &UnswitchedBB &&
261
5
         "Must have different loop exit and unswitched blocks!");
262
5
  Instruction *InsertPt = &*UnswitchedBB.begin();
263
10
  for (Instruction &I : ExitBB) {
264
10
    auto *PN = dyn_cast<PHINode>(&I);
265
10
    if (!PN)
266
10
      // No more PHIs to check.
267
5
      break;
268
5
269
5
    auto *NewPN = PHINode::Create(PN->getType(), /*NumReservedValues*/ 2,
270
5
                                  PN->getName() + ".split", InsertPt);
271
5
272
5
    // Walk backwards over the old PHI node's inputs to minimize the cost of
273
5
    // removing each one. We have to do this weird loop manually so that we
274
5
    // create the same number of new incoming edges in the new PHI as we expect
275
5
    // each case-based edge to be included in the unswitched switch in some
276
5
    // cases.
277
5
    // FIXME: This is really, really gross. It would be much cleaner if LLVM
278
5
    // allowed us to create a single entry for a predecessor block without
279
5
    // having separate entries for each "edge" even though these edges are
280
5
    // required to produce identical results.
281
17
    for (int i = PN->getNumIncomingValues() - 1; 
i >= 017
;
--i12
) {
282
12
      if (PN->getIncomingBlock(i) != &OldExitingBB)
283
5
        continue;
284
7
285
7
      Value *Incoming = PN->removeIncomingValue(i);
286
7
      NewPN->addIncoming(Incoming, &OldPH);
287
7
    }
288
10
289
10
    // Now replace the old PHI with the new one and wire the old one in as an
290
10
    // input to the new one.
291
10
    PN->replaceAllUsesWith(NewPN);
292
10
    NewPN->addIncoming(PN, &ExitBB);
293
10
  }
294
5
}
295
296
/// Unswitch a trivial branch if the condition is loop invariant.
297
///
298
/// This routine should only be called when loop code leading to the branch has
299
/// been validated as trivial (no side effects). This routine checks if the
300
/// condition is invariant and one of the successors is a loop exit. This
301
/// allows us to unswitch without duplicating the loop, making it trivial.
302
///
303
/// If this routine fails to unswitch the branch it returns false.
304
///
305
/// If the branch can be unswitched, this routine splits the preheader and
306
/// hoists the branch above that split. Preserves loop simplified form
307
/// (splitting the exit block as necessary). It simplifies the branch within
308
/// the loop to an unconditional branch but doesn't remove it entirely. Further
309
/// cleanup can be done with some simplify-cfg like pass.
310
static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
311
30
                                  LoopInfo &LI) {
312
30
  assert(BI.isConditional() && "Can only unswitch a conditional branch!");
313
30
  DEBUG(dbgs() << "  Trying to unswitch branch: " << BI << "\n");
314
30
315
30
  Value *LoopCond = BI.getCondition();
316
30
317
30
  // Need a trivial loop condition to unswitch.
318
30
  if (!L.isLoopInvariant(LoopCond))
319
11
    return false;
320
19
321
19
  // FIXME: We should compute this once at the start and update it!
322
19
  SmallVector<BasicBlock *, 16> ExitBlocks;
323
19
  L.getExitBlocks(ExitBlocks);
324
19
  SmallPtrSet<BasicBlock *, 16> ExitBlockSet(ExitBlocks.begin(),
325
19
                                             ExitBlocks.end());
326
19
327
19
  // Check to see if a successor of the branch is guaranteed to
328
19
  // exit through a unique exit block without having any
329
19
  // side-effects.  If so, determine the value of Cond that causes
330
19
  // it to do this.
331
19
  ConstantInt *CondVal = ConstantInt::getTrue(BI.getContext());
332
19
  ConstantInt *Replacement = ConstantInt::getFalse(BI.getContext());
333
19
  int LoopExitSuccIdx = 0;
334
19
  auto *LoopExitBB = BI.getSuccessor(0);
335
19
  if (
!ExitBlockSet.count(LoopExitBB)19
) {
336
15
    std::swap(CondVal, Replacement);
337
15
    LoopExitSuccIdx = 1;
338
15
    LoopExitBB = BI.getSuccessor(1);
339
15
    if (!ExitBlockSet.count(LoopExitBB))
340
4
      return false;
341
15
  }
342
15
  auto *ContinueBB = BI.getSuccessor(1 - LoopExitSuccIdx);
343
15
  assert(L.contains(ContinueBB) &&
344
15
         "Cannot have both successors exit and still be in the loop!");
345
15
346
15
  auto *ParentBB = BI.getParent();
347
15
  if (!areLoopExitPHIsLoopInvariant(L, *ParentBB, *LoopExitBB))
348
2
    return false;
349
13
350
13
  
DEBUG13
(dbgs() << " unswitching trivial branch when: " << CondVal
351
13
               << " == " << LoopCond << "\n");
352
13
353
13
  // Split the preheader, so that we know that there is a safe place to insert
354
13
  // the conditional branch. We will change the preheader to have a conditional
355
13
  // branch on LoopCond.
356
13
  BasicBlock *OldPH = L.getLoopPreheader();
357
13
  BasicBlock *NewPH = SplitEdge(OldPH, L.getHeader(), &DT, &LI);
358
13
359
13
  // Now that we have a place to insert the conditional branch, create a place
360
13
  // to branch to: this is the exit block out of the loop that we are
361
13
  // unswitching. We need to split this if there are other loop predecessors.
362
13
  // Because the loop is in simplified form, *any* other predecessor is enough.
363
13
  BasicBlock *UnswitchedBB;
364
13
  if (BasicBlock *
PredBB13
= LoopExitBB->getUniquePredecessor()) {
365
10
    (void)PredBB;
366
10
    assert(PredBB == BI.getParent() &&
367
10
           "A branch's parent isn't a predecessor!");
368
10
    UnswitchedBB = LoopExitBB;
369
13
  } else {
370
3
    UnswitchedBB = SplitBlock(LoopExitBB, &LoopExitBB->front(), &DT, &LI);
371
3
  }
372
13
373
13
  // Now splice the branch to gate reaching the new preheader and re-point its
374
13
  // successors.
375
13
  OldPH->getInstList().splice(std::prev(OldPH->end()),
376
13
                              BI.getParent()->getInstList(), BI);
377
13
  OldPH->getTerminator()->eraseFromParent();
378
13
  BI.setSuccessor(LoopExitSuccIdx, UnswitchedBB);
379
13
  BI.setSuccessor(1 - LoopExitSuccIdx, NewPH);
380
13
381
13
  // Create a new unconditional branch that will continue the loop as a new
382
13
  // terminator.
383
13
  BranchInst::Create(ContinueBB, ParentBB);
384
13
385
13
  // Rewrite the relevant PHI nodes.
386
13
  if (UnswitchedBB == LoopExitBB)
387
10
    rewritePHINodesForUnswitchedExitBlock(*UnswitchedBB, *ParentBB, *OldPH);
388
13
  else
389
3
    rewritePHINodesForExitAndUnswitchedBlocks(*LoopExitBB, *UnswitchedBB,
390
3
                                              *ParentBB, *OldPH);
391
13
392
13
  // Now we need to update the dominator tree.
393
13
  updateDTAfterUnswitch(UnswitchedBB, OldPH, DT);
394
13
  // But if we split something off of the loop exit block then we also removed
395
13
  // one of the predecessors for the loop exit block and may need to update its
396
13
  // idom.
397
13
  if (UnswitchedBB != LoopExitBB)
398
3
    updateLoopExitIDom(LoopExitBB, L, DT);
399
30
400
30
  // Since this is an i1 condition we can also trivially replace uses of it
401
30
  // within the loop with a constant.
402
30
  replaceLoopUsesWithConstant(L, *LoopCond, *Replacement);
403
30
404
30
  ++NumTrivial;
405
30
  ++NumBranches;
406
30
  return true;
407
30
}
408
409
/// Unswitch a trivial switch if the condition is loop invariant.
410
///
411
/// This routine should only be called when loop code leading to the switch has
412
/// been validated as trivial (no side effects). This routine checks if the
413
/// condition is invariant and that at least one of the successors is a loop
414
/// exit. This allows us to unswitch without duplicating the loop, making it
415
/// trivial.
416
///
417
/// If this routine fails to unswitch the switch it returns false.
418
///
419
/// If the switch can be unswitched, this routine splits the preheader and
420
/// copies the switch above that split. If the default case is one of the
421
/// exiting cases, it copies the non-exiting cases and points them at the new
422
/// preheader. If the default case is not exiting, it copies the exiting cases
423
/// and points the default at the preheader. It preserves loop simplified form
424
/// (splitting the exit blocks as necessary). It simplifies the switch within
425
/// the loop by removing now-dead cases. If the default case is one of those
426
/// unswitched, it replaces its destination with a new basic block containing
427
/// only unreachable. Such basic blocks, while technically loop exits, are not
428
/// considered for unswitching so this is a stable transform and the same
429
/// switch will not be revisited. If after unswitching there is only a single
430
/// in-loop successor, the switch is further simplified to an unconditional
431
/// branch. Still more cleanup can be done with some simplify-cfg like pass.
432
static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
433
10
                                  LoopInfo &LI) {
434
10
  DEBUG(dbgs() << "  Trying to unswitch switch: " << SI << "\n");
435
10
  Value *LoopCond = SI.getCondition();
436
10
437
10
  // If this isn't switching on an invariant condition, we can't unswitch it.
438
10
  if (!L.isLoopInvariant(LoopCond))
439
1
    return false;
440
9
441
9
  auto *ParentBB = SI.getParent();
442
9
443
9
  // FIXME: We should compute this once at the start and update it!
444
9
  SmallVector<BasicBlock *, 16> ExitBlocks;
445
9
  L.getExitBlocks(ExitBlocks);
446
9
  SmallPtrSet<BasicBlock *, 16> ExitBlockSet(ExitBlocks.begin(),
447
9
                                             ExitBlocks.end());
448
9
449
9
  SmallVector<int, 4> ExitCaseIndices;
450
61
  for (auto Case : SI.cases()) {
451
61
    auto *SuccBB = Case.getCaseSuccessor();
452
61
    if (ExitBlockSet.count(SuccBB) &&
453
53
        areLoopExitPHIsLoopInvariant(L, *ParentBB, *SuccBB))
454
52
      ExitCaseIndices.push_back(Case.getCaseIndex());
455
61
  }
456
9
  BasicBlock *DefaultExitBB = nullptr;
457
9
  if (ExitBlockSet.count(SI.getDefaultDest()) &&
458
4
      areLoopExitPHIsLoopInvariant(L, *ParentBB, *SI.getDefaultDest()) &&
459
4
      !isa<UnreachableInst>(SI.getDefaultDest()->getTerminator()))
460
4
    DefaultExitBB = SI.getDefaultDest();
461
5
  else 
if (5
ExitCaseIndices.empty()5
)
462
1
    return false;
463
8
464
8
  
DEBUG8
(dbgs() << " unswitching trivial cases...\n");
465
8
466
8
  SmallVector<std::pair<ConstantInt *, BasicBlock *>, 4> ExitCases;
467
8
  ExitCases.reserve(ExitCaseIndices.size());
468
8
  // We walk the case indices backwards so that we remove the last case first
469
8
  // and don't disrupt the earlier indices.
470
52
  for (unsigned Index : reverse(ExitCaseIndices)) {
471
52
    auto CaseI = SI.case_begin() + Index;
472
52
    // Save the value of this case.
473
52
    ExitCases.push_back({CaseI->getCaseValue(), CaseI->getCaseSuccessor()});
474
52
    // Delete the unswitched cases.
475
52
    SI.removeCase(CaseI);
476
52
  }
477
8
478
8
  // Check if after this all of the remaining cases point at the same
479
8
  // successor.
480
8
  BasicBlock *CommonSuccBB = nullptr;
481
8
  if (SI.getNumCases() > 0 &&
482
4
      std::all_of(std::next(SI.case_begin()), SI.case_end(),
483
3
                  [&SI](const SwitchInst::CaseHandle &Case) {
484
3
                    return Case.getCaseSuccessor() ==
485
3
                           SI.case_begin()->getCaseSuccessor();
486
3
                  }))
487
2
    CommonSuccBB = SI.case_begin()->getCaseSuccessor();
488
8
489
8
  if (
DefaultExitBB8
) {
490
4
    // We can't remove the default edge so replace it with an edge to either
491
4
    // the single common remaining successor (if we have one) or an unreachable
492
4
    // block.
493
4
    if (
CommonSuccBB4
) {
494
2
      SI.setDefaultDest(CommonSuccBB);
495
4
    } else {
496
2
      BasicBlock *UnreachableBB = BasicBlock::Create(
497
2
          ParentBB->getContext(),
498
2
          Twine(ParentBB->getName()) + ".unreachable_default",
499
2
          ParentBB->getParent());
500
2
      new UnreachableInst(ParentBB->getContext(), UnreachableBB);
501
2
      SI.setDefaultDest(UnreachableBB);
502
2
      DT.addNewBlock(UnreachableBB, ParentBB);
503
2
    }
504
8
  } else {
505
4
    // If we're not unswitching the default, we need it to match any cases to
506
4
    // have a common successor or if we have no cases it is the common
507
4
    // successor.
508
4
    if (SI.getNumCases() == 0)
509
4
      CommonSuccBB = SI.getDefaultDest();
510
0
    else 
if (0
SI.getDefaultDest() != CommonSuccBB0
)
511
0
      CommonSuccBB = nullptr;
512
4
  }
513
8
514
8
  // Split the preheader, so that we know that there is a safe place to insert
515
8
  // the switch.
516
8
  BasicBlock *OldPH = L.getLoopPreheader();
517
8
  BasicBlock *NewPH = SplitEdge(OldPH, L.getHeader(), &DT, &LI);
518
8
  OldPH->getTerminator()->eraseFromParent();
519
8
520
8
  // Now add the unswitched switch.
521
8
  auto *NewSI = SwitchInst::Create(LoopCond, NewPH, ExitCases.size(), OldPH);
522
8
523
8
  // Rewrite the IR for the unswitched basic blocks. This requires two steps.
524
8
  // First, we split any exit blocks with remaining in-loop predecessors. Then
525
8
  // we update the PHIs in one of two ways depending on if there was a split.
526
8
  // We walk in reverse so that we split in the same order as the cases
527
8
  // appeared. This is purely for convenience of reading the resulting IR, but
528
8
  // it doesn't cost anything really.
529
8
  SmallPtrSet<BasicBlock *, 2> UnswitchedExitBBs;
530
8
  SmallDenseMap<BasicBlock *, BasicBlock *, 2> SplitExitBBMap;
531
8
  // Handle the default exit if necessary.
532
8
  // FIXME: It'd be great if we could merge this with the loop below but LLVM's
533
8
  // ranges aren't quite powerful enough yet.
534
8
  if (
DefaultExitBB8
) {
535
4
    if (
pred_empty(DefaultExitBB)4
) {
536
4
      UnswitchedExitBBs.insert(DefaultExitBB);
537
4
      rewritePHINodesForUnswitchedExitBlock(*DefaultExitBB, *ParentBB, *OldPH);
538
4
    } else {
539
0
      auto *SplitBB =
540
0
          SplitBlock(DefaultExitBB, &DefaultExitBB->front(), &DT, &LI);
541
0
      rewritePHINodesForExitAndUnswitchedBlocks(*DefaultExitBB, *SplitBB,
542
0
                                                *ParentBB, *OldPH);
543
0
      updateLoopExitIDom(DefaultExitBB, L, DT);
544
0
      DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB;
545
0
    }
546
4
  }
547
8
  // Note that we must use a reference in the for loop so that we update the
548
8
  // container.
549
52
  for (auto &CasePair : reverse(ExitCases)) {
550
52
    // Grab a reference to the exit block in the pair so that we can update it.
551
52
    BasicBlock *ExitBB = CasePair.second;
552
52
553
52
    // If this case is the last edge into the exit block, we can simply reuse it
554
52
    // as it will no longer be a loop exit. No mapping necessary.
555
52
    if (
pred_empty(ExitBB)52
) {
556
49
      // Only rewrite once.
557
49
      if (UnswitchedExitBBs.insert(ExitBB).second)
558
17
        rewritePHINodesForUnswitchedExitBlock(*ExitBB, *ParentBB, *OldPH);
559
49
      continue;
560
49
    }
561
3
562
3
    // Otherwise we need to split the exit block so that we retain an exit
563
3
    // block from the loop and a target for the unswitched condition.
564
3
    BasicBlock *&SplitExitBB = SplitExitBBMap[ExitBB];
565
3
    if (
!SplitExitBB3
) {
566
2
      // If this is the first time we see this, do the split and remember it.
567
2
      SplitExitBB = SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI);
568
2
      rewritePHINodesForExitAndUnswitchedBlocks(*ExitBB, *SplitExitBB,
569
2
                                                *ParentBB, *OldPH);
570
2
      updateLoopExitIDom(ExitBB, L, DT);
571
2
    }
572
52
    // Update the case pair to point to the split block.
573
52
    CasePair.second = SplitExitBB;
574
52
  }
575
8
576
8
  // Now add the unswitched cases. We do this in reverse order as we built them
577
8
  // in reverse order.
578
52
  for (auto CasePair : reverse(ExitCases)) {
579
52
    ConstantInt *CaseVal = CasePair.first;
580
52
    BasicBlock *UnswitchedBB = CasePair.second;
581
52
582
52
    NewSI->addCase(CaseVal, UnswitchedBB);
583
52
    updateDTAfterUnswitch(UnswitchedBB, OldPH, DT);
584
52
  }
585
8
586
8
  // If the default was unswitched, re-point it and add explicit cases for
587
8
  // entering the loop.
588
8
  if (
DefaultExitBB8
) {
589
4
    NewSI->setDefaultDest(DefaultExitBB);
590
4
    updateDTAfterUnswitch(DefaultExitBB, OldPH, DT);
591
4
592
4
    // We removed all the exit cases, so we just copy the cases to the
593
4
    // unswitched switch.
594
4
    for (auto Case : SI.cases())
595
8
      NewSI->addCase(Case.getCaseValue(), NewPH);
596
4
  }
597
8
598
8
  // If we ended up with a common successor for every path through the switch
599
8
  // after unswitching, rewrite it to an unconditional branch to make it easy
600
8
  // to recognize. Otherwise we potentially have to recognize the default case
601
8
  // pointing at unreachable and other complexity.
602
8
  if (
CommonSuccBB8
) {
603
6
    BasicBlock *BB = SI.getParent();
604
6
    SI.eraseFromParent();
605
6
    BranchInst::Create(CommonSuccBB, BB);
606
6
  }
607
10
608
10
  DT.verifyDomTree();
609
10
  ++NumTrivial;
610
10
  ++NumSwitches;
611
10
  return true;
612
10
}
613
614
/// This routine scans the loop to find a branch or switch which occurs before
615
/// any side effects occur. These can potentially be unswitched without
616
/// duplicating the loop. If a branch or switch is successfully unswitched the
617
/// scanning continues to see if subsequent branches or switches have become
618
/// trivial. Once all trivial candidates have been unswitched, this routine
619
/// returns.
620
///
621
/// The return value indicates whether anything was unswitched (and therefore
622
/// changed).
623
static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT,
624
90
                                         LoopInfo &LI) {
625
90
  bool Changed = false;
626
90
627
90
  // If loop header has only one reachable successor we should keep looking for
628
90
  // trivial condition candidates in the successor as well. An alternative is
629
90
  // to constant fold conditions and merge successors into loop header (then we
630
90
  // only need to check header's terminator). The reason for not doing this in
631
90
  // LoopUnswitch pass is that it could potentially break LoopPassManager's
632
90
  // invariants. Folding dead branches could either eliminate the current loop
633
90
  // or make other loops unreachable. LCSSA form might also not be preserved
634
90
  // after deleting branches. The following code keeps traversing loop header's
635
90
  // successors until it finds the trivial condition candidate (condition that
636
90
  // is not a constant). Since unswitching generates branches with constant
637
90
  // conditions, this scenario could be very common in practice.
638
90
  BasicBlock *CurrentBB = L.getHeader();
639
90
  SmallPtrSet<BasicBlock *, 8> Visited;
640
90
  Visited.insert(CurrentBB);
641
109
  do {
642
109
    // Check if there are any side-effecting instructions (e.g. stores, calls,
643
109
    // volatile loads) in the part of the loop that the code *would* execute
644
109
    // without unswitching.
645
109
    if (llvm::any_of(*CurrentBB,
646
267
                     [](Instruction &I) { return I.mayHaveSideEffects(); }))
647
43
      return Changed;
648
66
649
66
    TerminatorInst *CurrentTerm = CurrentBB->getTerminator();
650
66
651
66
    if (auto *
SI66
= dyn_cast<SwitchInst>(CurrentTerm)) {
652
11
      // Don't bother trying to unswitch past a switch with a constant
653
11
      // condition. This should be removed prior to running this pass by
654
11
      // simplify-cfg.
655
11
      if (isa<Constant>(SI->getCondition()))
656
1
        return Changed;
657
10
658
10
      
if (10
!unswitchTrivialSwitch(L, *SI, DT, LI)10
)
659
10
        // Coludn't unswitch this one so we're done.
660
2
        return Changed;
661
8
662
8
      // Mark that we managed to unswitch something.
663
8
      Changed = true;
664
8
665
8
      // If unswitching turned the terminator into an unconditional branch then
666
8
      // we can continue. The unswitching logic specifically works to fold any
667
8
      // cases it can into an unconditional branch to make it easier to
668
8
      // recognize here.
669
8
      auto *BI = dyn_cast<BranchInst>(CurrentBB->getTerminator());
670
8
      if (
!BI || 8
BI->isConditional()6
)
671
2
        return Changed;
672
6
673
6
      CurrentBB = BI->getSuccessor(0);
674
6
      continue;
675
6
    }
676
55
677
55
    auto *BI = dyn_cast<BranchInst>(CurrentTerm);
678
55
    if (!BI)
679
55
      // We do not understand other terminator instructions.
680
1
      return Changed;
681
54
682
54
    // Don't bother trying to unswitch past an unconditional branch or a branch
683
54
    // with a constant value. These should be removed by simplify-cfg prior to
684
54
    // running this pass.
685
54
    
if (54
!BI->isConditional() || 54
isa<Constant>(BI->getCondition())43
)
686
24
      return Changed;
687
30
688
30
    // Found a trivial condition candidate: non-foldable conditional branch. If
689
30
    // we fail to unswitch this, we can't do anything else that is trivial.
690
30
    
if (30
!unswitchTrivialBranch(L, *BI, DT, LI)30
)
691
17
      return Changed;
692
13
693
13
    // Mark that we managed to unswitch something.
694
13
    Changed = true;
695
13
696
13
    // We unswitched the branch. This should always leave us with an
697
13
    // unconditional branch that we can follow now.
698
13
    BI = cast<BranchInst>(CurrentBB->getTerminator());
699
13
    assert(!BI->isConditional() &&
700
13
           "Cannot form a conditional branch by unswitching1");
701
13
    CurrentBB = BI->getSuccessor(0);
702
13
703
13
    // When continuing, if we exit the loop or reach a previous visited block,
704
13
    // then we can not reach any trivial condition candidates (unfoldable
705
13
    // branch instructions or switch instructions) and no unswitch can happen.
706
90
  } while (
L.contains(CurrentBB) && 19
Visited.insert(CurrentBB).second19
);
707
90
708
0
  return Changed;
709
90
}
710
711
/// Unswitch control flow predicated on loop invariant conditions.
712
///
713
/// This first hoists all branches or switches which are trivial (IE, do not
714
/// require duplicating any part of the loop) out of the loop body. It then
715
/// looks at other loop invariant control flows and tries to unswitch those as
716
/// well by cloning the loop if the result is small enough.
717
static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI,
718
90
                         AssumptionCache &AC) {
719
90
  assert(L.isLCSSAForm(DT) &&
720
90
         "Loops must be in LCSSA form before unswitching.");
721
90
  bool Changed = false;
722
90
723
90
  // Must be in loop simplified form: we need a preheader and dedicated exits.
724
90
  if (!L.isLoopSimplifyForm())
725
0
    return false;
726
90
727
90
  // Try trivial unswitch first before loop over other basic blocks in the loop.
728
90
  Changed |= unswitchAllTrivialConditions(L, DT, LI);
729
90
730
90
  // FIXME: Add support for non-trivial unswitching by cloning the loop.
731
90
732
90
  return Changed;
733
90
}
734
735
PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
736
                                              LoopStandardAnalysisResults &AR,
737
50
                                              LPMUpdater &U) {
738
50
  Function &F = *L.getHeader()->getParent();
739
50
  (void)F;
740
50
741
50
  DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L << "\n");
742
50
743
50
  if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC))
744
40
    return PreservedAnalyses::all();
745
10
746
#ifndef NDEBUG
747
  // Historically this pass has had issues with the dominator tree so verify it
748
  // in asserts builds.
749
  AR.DT.verifyDomTree();
750
#endif
751
0
  return getLoopPassPreservedAnalyses();
752
10
}
753
754
namespace {
755
756
class SimpleLoopUnswitchLegacyPass : public LoopPass {
757
public:
758
  static char ID; // Pass ID, replacement for typeid
759
760
24
  explicit SimpleLoopUnswitchLegacyPass() : LoopPass(ID) {
761
24
    initializeSimpleLoopUnswitchLegacyPassPass(
762
24
        *PassRegistry::getPassRegistry());
763
24
  }
764
765
  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
766
767
24
  void getAnalysisUsage(AnalysisUsage &AU) const override {
768
24
    AU.addRequired<AssumptionCacheTracker>();
769
24
    getLoopAnalysisUsage(AU);
770
24
  }
771
};
772
773
} // end anonymous namespace
774
775
40
bool SimpleLoopUnswitchLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
776
40
  if (skipLoop(L))
777
0
    return false;
778
40
779
40
  Function &F = *L->getHeader()->getParent();
780
40
781
40
  DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << *L << "\n");
782
40
783
40
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
784
40
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
785
40
  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
786
40
787
40
  bool Changed = unswitchLoop(*L, DT, LI, AC);
788
40
789
#ifndef NDEBUG
790
  // Historically this pass has had issues with the dominator tree so verify it
791
  // in asserts builds.
792
  DT.verifyDomTree();
793
#endif
794
  return Changed;
795
40
}
796
797
char SimpleLoopUnswitchLegacyPass::ID = 0;
798
24.6k
INITIALIZE_PASS_BEGIN24.6k
(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch",
799
24.6k
                      "Simple unswitch loops", false, false)
800
24.6k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
801
24.6k
INITIALIZE_PASS_DEPENDENCY(LoopPass)
802
24.6k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
803
24.6k
INITIALIZE_PASS_END(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch",
804
                    "Simple unswitch loops", false, false)
805
806
0
Pass *llvm::createSimpleLoopUnswitchLegacyPass() {
807
0
  return new SimpleLoopUnswitchLegacyPass();
808
0
}