Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BreakCriticalEdges.cpp - Critical Edge Elimination 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
// BreakCriticalEdges pass - Break all of the critical edges in the CFG by
10
// inserting a dummy basic block.  This pass may be "required" by passes that
11
// cannot deal with critical edges.  For this usage, the structure type is
12
// forward declared.  This pass obviously invalidates the CFG, but can update
13
// dominator trees.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#include "llvm/Transforms/Utils/BreakCriticalEdges.h"
18
#include "llvm/ADT/SetVector.h"
19
#include "llvm/ADT/SmallVector.h"
20
#include "llvm/ADT/Statistic.h"
21
#include "llvm/Analysis/BlockFrequencyInfo.h"
22
#include "llvm/Analysis/BranchProbabilityInfo.h"
23
#include "llvm/Analysis/CFG.h"
24
#include "llvm/Analysis/LoopInfo.h"
25
#include "llvm/Analysis/MemorySSAUpdater.h"
26
#include "llvm/Analysis/PostDominators.h"
27
#include "llvm/IR/CFG.h"
28
#include "llvm/IR/Dominators.h"
29
#include "llvm/IR/Instructions.h"
30
#include "llvm/IR/Type.h"
31
#include "llvm/Support/ErrorHandling.h"
32
#include "llvm/Transforms/Utils.h"
33
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
34
#include "llvm/Transforms/Utils/Cloning.h"
35
#include "llvm/Transforms/Utils/ValueMapper.h"
36
using namespace llvm;
37
38
#define DEBUG_TYPE "break-crit-edges"
39
40
STATISTIC(NumBroken, "Number of blocks inserted");
41
42
namespace {
43
  struct BreakCriticalEdges : public FunctionPass {
44
    static char ID; // Pass identification, replacement for typeid
45
15
    BreakCriticalEdges() : FunctionPass(ID) {
46
15
      initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
47
15
    }
48
49
24
    bool runOnFunction(Function &F) override {
50
24
      auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
51
24
      auto *DT = DTWP ? 
&DTWP->getDomTree()4
:
nullptr20
;
52
24
53
24
      auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
54
24
      auto *PDT = PDTWP ? 
&PDTWP->getPostDomTree()0
: nullptr;
55
24
56
24
      auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
57
24
      auto *LI = LIWP ? 
&LIWP->getLoopInfo()3
:
nullptr21
;
58
24
      unsigned N =
59
24
          SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT));
60
24
      NumBroken += N;
61
24
      return N > 0;
62
24
    }
63
64
15
    void getAnalysisUsage(AnalysisUsage &AU) const override {
65
15
      AU.addPreserved<DominatorTreeWrapperPass>();
66
15
      AU.addPreserved<LoopInfoWrapperPass>();
67
15
68
15
      // No loop canonicalization guarantees are broken by this pass.
69
15
      AU.addPreservedID(LoopSimplifyID);
70
15
    }
71
  };
72
}
73
74
char BreakCriticalEdges::ID = 0;
75
INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
76
                "Break critical edges in CFG", false, false)
77
78
// Publicly exposed interface to pass...
79
char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
80
0
FunctionPass *llvm::createBreakCriticalEdgesPass() {
81
0
  return new BreakCriticalEdges();
82
0
}
83
84
PreservedAnalyses BreakCriticalEdgesPass::run(Function &F,
85
2
                                              FunctionAnalysisManager &AM) {
86
2
  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
87
2
  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
88
2
  unsigned N = SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI));
89
2
  NumBroken += N;
90
2
  if (N == 0)
91
0
    return PreservedAnalyses::all();
92
2
  PreservedAnalyses PA;
93
2
  PA.preserve<DominatorTreeAnalysis>();
94
2
  PA.preserve<LoopAnalysis>();
95
2
  return PA;
96
2
}
97
98
//===----------------------------------------------------------------------===//
99
//    Implementation of the external critical edge manipulation functions
100
//===----------------------------------------------------------------------===//
101
102
/// When a loop exit edge is split, LCSSA form may require new PHIs in the new
103
/// exit block. This function inserts the new PHIs, as needed. Preds is a list
104
/// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is
105
/// the old loop exit, now the successor of SplitBB.
106
static void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
107
                                       BasicBlock *SplitBB,
108
35.1k
                                       BasicBlock *DestBB) {
109
35.1k
  // SplitBB shouldn't have anything non-trivial in it yet.
110
35.1k
  assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
111
35.1k
          SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!");
112
35.1k
113
35.1k
  // For each PHI in the destination block.
114
35.1k
  for (PHINode &PN : DestBB->phis()) {
115
22.0k
    unsigned Idx = PN.getBasicBlockIndex(SplitBB);
116
22.0k
    Value *V = PN.getIncomingValue(Idx);
117
22.0k
118
22.0k
    // If the input is a PHI which already satisfies LCSSA, don't create
119
22.0k
    // a new one.
120
22.0k
    if (const PHINode *VP = dyn_cast<PHINode>(V))
121
15.6k
      if (VP->getParent() == SplitBB)
122
2
        continue;
123
22.0k
124
22.0k
    // Otherwise a new PHI is needed. Create one and populate it.
125
22.0k
    PHINode *NewPN = PHINode::Create(
126
22.0k
        PN.getType(), Preds.size(), "split",
127
22.0k
        SplitBB->isLandingPad() ? 
&SplitBB->front()0
: SplitBB->getTerminator());
128
44.0k
    for (unsigned i = 0, e = Preds.size(); i != e; 
++i22.0k
)
129
22.0k
      NewPN->addIncoming(V, Preds[i]);
130
22.0k
131
22.0k
    // Update the original PHI.
132
22.0k
    PN.setIncomingValue(Idx, NewPN);
133
22.0k
  }
134
35.1k
}
135
136
BasicBlock *
137
llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
138
106k
                        const CriticalEdgeSplittingOptions &Options) {
139
106k
  if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
140
13.4k
    return nullptr;
141
93.4k
142
93.4k
  assert(!isa<IndirectBrInst>(TI) &&
143
93.4k
         "Cannot split critical edge from IndirectBrInst");
144
93.4k
145
93.4k
  BasicBlock *TIBB = TI->getParent();
146
93.4k
  BasicBlock *DestBB = TI->getSuccessor(SuccNum);
147
93.4k
148
93.4k
  // Splitting the critical edge to a pad block is non-trivial. Don't do
149
93.4k
  // it in this generic function.
150
93.4k
  if (DestBB->isEHPad()) 
return nullptr69
;
151
93.3k
152
93.3k
  // Don't split the non-fallthrough edge from a callbr.
153
93.3k
  if (isa<CallBrInst>(TI) && 
SuccNum > 00
)
154
0
    return nullptr;
155
93.3k
156
93.3k
  if (Options.IgnoreUnreachableDests &&
157
93.3k
      
isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime())12
)
158
2
    return nullptr;
159
93.3k
160
93.3k
  // Create a new basic block, linking it into the CFG.
161
93.3k
  BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
162
93.3k
                      TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
163
93.3k
  // Create our unconditional branch.
164
93.3k
  BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
165
93.3k
  NewBI->setDebugLoc(TI->getDebugLoc());
166
93.3k
167
93.3k
  // Branch to the new block, breaking the edge.
168
93.3k
  TI->setSuccessor(SuccNum, NewBB);
169
93.3k
170
93.3k
  // Insert the block into the function... right after the block TI lives in.
171
93.3k
  Function &F = *TIBB->getParent();
172
93.3k
  Function::iterator FBBI = TIBB->getIterator();
173
93.3k
  F.getBasicBlockList().insert(++FBBI, NewBB);
174
93.3k
175
93.3k
  // If there are any PHI nodes in DestBB, we need to update them so that they
176
93.3k
  // merge incoming values from NewBB instead of from TIBB.
177
93.3k
  {
178
93.3k
    unsigned BBIdx = 0;
179
184k
    for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); 
++I90.8k
) {
180
90.8k
      // We no longer enter through TIBB, now we come in through NewBB.
181
90.8k
      // Revector exactly one entry in the PHI node that used to come from
182
90.8k
      // TIBB to come from NewBB.
183
90.8k
      PHINode *PN = cast<PHINode>(I);
184
90.8k
185
90.8k
      // Reuse the previous value of BBIdx if it lines up.  In cases where we
186
90.8k
      // have multiple phi nodes with *lots* of predecessors, this is a speed
187
90.8k
      // win because we don't have to scan the PHI looking for TIBB.  This
188
90.8k
      // happens because the BB list of PHI nodes are usually in the same
189
90.8k
      // order.
190
90.8k
      if (PN->getIncomingBlock(BBIdx) != TIBB)
191
11.5k
        BBIdx = PN->getBasicBlockIndex(TIBB);
192
90.8k
      PN->setIncomingBlock(BBIdx, NewBB);
193
90.8k
    }
194
93.3k
  }
195
93.3k
196
93.3k
  // If there are any other edges from TIBB to DestBB, update those to go
197
93.3k
  // through the split block, making those edges non-critical as well (and
198
93.3k
  // reducing the number of phi entries in the DestBB if relevant).
199
93.3k
  if (Options.MergeIdenticalEdges) {
200
8.71k
    for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; 
++i3.25k
) {
201
3.25k
      if (TI->getSuccessor(i) != DestBB) 
continue3.22k
;
202
26
203
26
      // Remove an entry for TIBB from DestBB phi nodes.
204
26
      DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
205
26
206
26
      // We found another edge to DestBB, go to NewBB instead.
207
26
      TI->setSuccessor(i, NewBB);
208
26
    }
209
5.46k
  }
210
93.3k
211
93.3k
  // If we have nothing to update, just return.
212
93.3k
  auto *DT = Options.DT;
213
93.3k
  auto *PDT = Options.PDT;
214
93.3k
  auto *LI = Options.LI;
215
93.3k
  auto *MSSAU = Options.MSSAU;
216
93.3k
  if (MSSAU)
217
197
    MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
218
197
        DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
219
93.3k
220
93.3k
  if (!DT && 
!PDT783
&&
!LI783
)
221
783
    return NewBB;
222
92.6k
223
92.6k
  if (DT || 
PDT0
) {
224
92.6k
    // Update the DominatorTree.
225
92.6k
    //       ---> NewBB -----\
226
92.6k
    //      /                 V
227
92.6k
    //  TIBB -------\\------> DestBB
228
92.6k
    //
229
92.6k
    // First, inform the DT about the new path from TIBB to DestBB via NewBB,
230
92.6k
    // then delete the old edge from TIBB to DestBB. By doing this in that order
231
92.6k
    // DestBB stays reachable in the DT the whole time and its subtree doesn't
232
92.6k
    // get disconnected.
233
92.6k
    SmallVector<DominatorTree::UpdateType, 3> Updates;
234
92.6k
    Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
235
92.6k
    Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
236
92.6k
    if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB))
237
92.5k
      Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
238
92.6k
239
92.6k
    if (DT)
240
92.6k
      DT->applyUpdates(Updates);
241
92.6k
    if (PDT)
242
1
      PDT->applyUpdates(Updates);
243
92.6k
  }
244
92.6k
245
92.6k
  // Update LoopInfo if it is around.
246
92.6k
  if (LI) {
247
75.4k
    if (Loop *TIL = LI->getLoopFor(TIBB)) {
248
47.4k
      // If one or the other blocks were not in a loop, the new block is not
249
47.4k
      // either, and thus LI doesn't need to be updated.
250
47.4k
      if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
251
20.5k
        if (TIL == DestLoop) {
252
3.17k
          // Both in the same loop, the NewBB joins loop.
253
3.17k
          DestLoop->addBasicBlockToLoop(NewBB, *LI);
254
17.3k
        } else if (TIL->contains(DestLoop)) {
255
8.21k
          // Edge from an outer loop to an inner loop.  Add to the outer loop.
256
8.21k
          TIL->addBasicBlockToLoop(NewBB, *LI);
257
9.16k
        } else if (DestLoop->contains(TIL)) {
258
9.16k
          // Edge from an inner loop to an outer loop.  Add to the outer loop.
259
9.16k
          DestLoop->addBasicBlockToLoop(NewBB, *LI);
260
9.16k
        } else {
261
0
          // Edge from two loops with no containment relation.  Because these
262
0
          // are natural loops, we know that the destination block must be the
263
0
          // header of its loop (adding a branch into a loop elsewhere would
264
0
          // create an irreducible loop).
265
0
          assert(DestLoop->getHeader() == DestBB &&
266
0
                 "Should not create irreducible loops!");
267
0
          if (Loop *P = DestLoop->getParentLoop())
268
0
            P->addBasicBlockToLoop(NewBB, *LI);
269
0
        }
270
20.5k
      }
271
47.4k
272
47.4k
      // If TIBB is in a loop and DestBB is outside of that loop, we may need
273
47.4k
      // to update LoopSimplify form and LCSSA form.
274
47.4k
      if (!TIL->contains(DestBB)) {
275
36.0k
        assert(!TIL->contains(NewBB) &&
276
36.0k
               "Split point for loop exit is contained in loop!");
277
36.0k
278
36.0k
        // Update LCSSA form in the newly created exit block.
279
36.0k
        if (Options.PreserveLCSSA) {
280
35.1k
          createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
281
35.1k
        }
282
36.0k
283
36.0k
        // The only that we can break LoopSimplify form by splitting a critical
284
36.0k
        // edge is if after the split there exists some edge from TIL to DestBB
285
36.0k
        // *and* the only edge into DestBB from outside of TIL is that of
286
36.0k
        // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
287
36.0k
        // is the new exit block and it has no non-loop predecessors. If the
288
36.0k
        // second isn't true, then DestBB was not in LoopSimplify form prior to
289
36.0k
        // the split as it had a non-loop predecessor. In both of these cases,
290
36.0k
        // the predecessor must be directly in TIL, not in a subloop, or again
291
36.0k
        // LoopSimplify doesn't hold.
292
36.0k
        SmallVector<BasicBlock *, 4> LoopPreds;
293
73.1k
        for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E;
294
72.2k
             
++I37.0k
) {
295
72.2k
          BasicBlock *P = *I;
296
72.2k
          if (P == NewBB)
297
36.0k
            continue; // The new block is known.
298
36.1k
          if (LI->getLoopFor(P) != TIL) {
299
35.1k
            // No need to re-simplify, it wasn't to start with.
300
35.1k
            LoopPreds.clear();
301
35.1k
            break;
302
35.1k
          }
303
1.04k
          LoopPreds.push_back(P);
304
1.04k
        }
305
36.0k
        if (!LoopPreds.empty()) {
306
898
          assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
307
898
          BasicBlock *NewExitBB = SplitBlockPredecessors(
308
898
              DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
309
898
          if (Options.PreserveLCSSA)
310
2
            createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
311
898
        }
312
36.0k
      }
313
47.4k
    }
314
75.4k
  }
315
92.6k
316
92.6k
  return NewBB;
317
92.6k
}
318
319
// Return the unique indirectbr predecessor of a block. This may return null
320
// even if such a predecessor exists, if it's not useful for splitting.
321
// If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
322
// predecessors of BB.
323
static BasicBlock *
324
314
findIBRPredecessor(BasicBlock *BB, SmallVectorImpl<BasicBlock *> &OtherPreds) {
325
314
  // If the block doesn't have any PHIs, we don't care about it, since there's
326
314
  // no point in splitting it.
327
314
  PHINode *PN = dyn_cast<PHINode>(BB->begin());
328
314
  if (!PN)
329
209
    return nullptr;
330
105
331
105
  // Verify we have exactly one IBR predecessor.
332
105
  // Conservatively bail out if one of the other predecessors is not a "regular"
333
105
  // terminator (that is, not a switch or a br).
334
105
  BasicBlock *IBB = nullptr;
335
357
  for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; 
++Pred252
) {
336
254
    BasicBlock *PredBB = PN->getIncomingBlock(Pred);
337
254
    Instruction *PredTerm = PredBB->getTerminator();
338
254
    switch (PredTerm->getOpcode()) {
339
254
    case Instruction::IndirectBr:
340
107
      if (IBB)
341
2
        return nullptr;
342
105
      IBB = PredBB;
343
105
      break;
344
147
    case Instruction::Br:
345
147
    case Instruction::Switch:
346
147
      OtherPreds.push_back(PredBB);
347
147
      continue;
348
147
    default:
349
0
      return nullptr;
350
254
    }
351
254
  }
352
105
353
105
  
return IBB103
;
354
105
}
355
356
bool llvm::SplitIndirectBrCriticalEdges(Function &F,
357
                                        BranchProbabilityInfo *BPI,
358
490k
                                        BlockFrequencyInfo *BFI) {
359
490k
  // Check whether the function has any indirectbrs, and collect which blocks
360
490k
  // they may jump to. Since most functions don't have indirect branches,
361
490k
  // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
362
490k
  SmallSetVector<BasicBlock *, 16> Targets;
363
2.56M
  for (auto &BB : F) {
364
2.56M
    auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
365
2.56M
    if (!IBI)
366
2.56M
      continue;
367
112
368
450
    
for (unsigned Succ = 0, E = IBI->getNumSuccessors(); 112
Succ != E;
++Succ338
)
369
338
      Targets.insert(IBI->getSuccessor(Succ));
370
112
  }
371
490k
372
490k
  if (Targets.empty())
373
490k
    return false;
374
97
375
97
  bool ShouldUpdateAnalysis = BPI && 
BFI6
;
376
97
  bool Changed = false;
377
314
  for (BasicBlock *Target : Targets) {
378
314
    SmallVector<BasicBlock *, 16> OtherPreds;
379
314
    BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
380
314
    // If we did not found an indirectbr, or the indirectbr is the only
381
314
    // incoming edge, this isn't the kind of edge we're looking for.
382
314
    if (!IBRPred || 
OtherPreds.empty()103
)
383
213
      continue;
384
101
385
101
    // Don't even think about ehpads/landingpads.
386
101
    Instruction *FirstNonPHI = Target->getFirstNonPHI();
387
101
    if (FirstNonPHI->isEHPad() || Target->isLandingPad())
388
0
      continue;
389
101
390
101
    BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
391
101
    if (ShouldUpdateAnalysis) {
392
5
      // Copy the BFI/BPI from Target to BodyBlock.
393
5
      for (unsigned I = 0, E = BodyBlock->getTerminator()->getNumSuccessors();
394
9
           I < E; 
++I4
)
395
4
        BPI->setEdgeProbability(BodyBlock, I,
396
4
                                BPI->getEdgeProbability(Target, I));
397
5
      BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
398
5
    }
399
101
    // It's possible Target was its own successor through an indirectbr.
400
101
    // In this case, the indirectbr now comes from BodyBlock.
401
101
    if (IBRPred == Target)
402
10
      IBRPred = BodyBlock;
403
101
404
101
    // At this point Target only has PHIs, and BodyBlock has the rest of the
405
101
    // block's body. Create a copy of Target that will be used by the "direct"
406
101
    // preds.
407
101
    ValueToValueMapTy VMap;
408
101
    BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
409
101
410
101
    BlockFrequency BlockFreqForDirectSucc;
411
145
    for (BasicBlock *Pred : OtherPreds) {
412
145
      // If the target is a loop to itself, then the terminator of the split
413
145
      // block (BodyBlock) needs to be updated.
414
145
      BasicBlock *Src = Pred != Target ? 
Pred143
:
BodyBlock2
;
415
145
      Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
416
145
      if (ShouldUpdateAnalysis)
417
12
        BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
418
12
            BPI->getEdgeProbability(Src, DirectSucc);
419
145
    }
420
101
    if (ShouldUpdateAnalysis) {
421
5
      BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency());
422
5
      BlockFrequency NewBlockFreqForTarget =
423
5
          BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
424
5
      BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency());
425
5
      BPI->eraseBlock(Target);
426
5
    }
427
101
428
101
    // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
429
101
    // they are clones, so the number of PHIs are the same.
430
101
    // (a) Remove the edge coming from IBRPred from the "Direct" PHI
431
101
    // (b) Leave that as the only edge in the "Indirect" PHI.
432
101
    // (c) Merge the two in the body block.
433
101
    BasicBlock::iterator Indirect = Target->begin(),
434
101
                         End = Target->getFirstNonPHI()->getIterator();
435
101
    BasicBlock::iterator Direct = DirectSucc->begin();
436
101
    BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
437
101
438
101
    assert(&*End == Target->getTerminator() &&
439
101
           "Block was expected to only contain PHIs");
440
101
441
237
    while (Indirect != End) {
442
136
      PHINode *DirPHI = cast<PHINode>(Direct);
443
136
      PHINode *IndPHI = cast<PHINode>(Indirect);
444
136
445
136
      // Now, clean up - the direct block shouldn't get the indirect value,
446
136
      // and vice versa.
447
136
      DirPHI->removeIncomingValue(IBRPred);
448
136
      Direct++;
449
136
450
136
      // Advance the pointer here, to avoid invalidation issues when the old
451
136
      // PHI is erased.
452
136
      Indirect++;
453
136
454
136
      PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
455
136
      NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
456
136
                             IBRPred);
457
136
458
136
      // Create a PHI in the body block, to merge the direct and indirect
459
136
      // predecessors.
460
136
      PHINode *MergePHI =
461
136
          PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
462
136
      MergePHI->addIncoming(NewIndPHI, Target);
463
136
      MergePHI->addIncoming(DirPHI, DirectSucc);
464
136
465
136
      IndPHI->replaceAllUsesWith(MergePHI);
466
136
      IndPHI->eraseFromParent();
467
136
    }
468
101
469
101
    Changed = true;
470
101
  }
471
97
472
97
  return Changed;
473
97
}