Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==//
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 family of functions perform manipulations on basic blocks, and
10
// instructions contained within basic blocks.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
15
#include "llvm/ADT/ArrayRef.h"
16
#include "llvm/ADT/SmallPtrSet.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Twine.h"
19
#include "llvm/Analysis/CFG.h"
20
#include "llvm/Analysis/DomTreeUpdater.h"
21
#include "llvm/Analysis/LoopInfo.h"
22
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
23
#include "llvm/Analysis/MemorySSAUpdater.h"
24
#include "llvm/Analysis/PostDominators.h"
25
#include "llvm/IR/BasicBlock.h"
26
#include "llvm/IR/CFG.h"
27
#include "llvm/IR/Constants.h"
28
#include "llvm/IR/DebugInfoMetadata.h"
29
#include "llvm/IR/Dominators.h"
30
#include "llvm/IR/Function.h"
31
#include "llvm/IR/InstrTypes.h"
32
#include "llvm/IR/Instruction.h"
33
#include "llvm/IR/Instructions.h"
34
#include "llvm/IR/IntrinsicInst.h"
35
#include "llvm/IR/LLVMContext.h"
36
#include "llvm/IR/Type.h"
37
#include "llvm/IR/User.h"
38
#include "llvm/IR/Value.h"
39
#include "llvm/IR/ValueHandle.h"
40
#include "llvm/Support/Casting.h"
41
#include "llvm/Support/Debug.h"
42
#include "llvm/Support/raw_ostream.h"
43
#include "llvm/Transforms/Utils/Local.h"
44
#include <cassert>
45
#include <cstdint>
46
#include <string>
47
#include <utility>
48
#include <vector>
49
50
using namespace llvm;
51
52
#define DEBUG_TYPE "basicblock-utils"
53
54
void llvm::DetatchDeadBlocks(
55
    ArrayRef<BasicBlock *> BBs,
56
    SmallVectorImpl<DominatorTree::UpdateType> *Updates,
57
641k
    bool KeepOneInputPHIs) {
58
641k
  for (auto *BB : BBs) {
59
104k
    // Loop through all of our successors and make sure they know that one
60
104k
    // of their predecessors is going away.
61
104k
    SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
62
137k
    for (BasicBlock *Succ : successors(BB)) {
63
137k
      Succ->removePredecessor(BB, KeepOneInputPHIs);
64
137k
      if (Updates && 
UniqueSuccessors.insert(Succ).second27.0k
)
65
27.0k
        Updates->push_back({DominatorTree::Delete, BB, Succ});
66
137k
    }
67
104k
68
104k
    // Zap all the instructions in the block.
69
283k
    while (!BB->empty()) {
70
179k
      Instruction &I = BB->back();
71
179k
      // If this instruction is used, replace uses with an arbitrary value.
72
179k
      // Because control flow can't get here, we don't care what we replace the
73
179k
      // value with.  Note that since this block is unreachable, and all values
74
179k
      // contained within it must dominate their uses, that all uses will
75
179k
      // eventually be removed (they are themselves dead).
76
179k
      if (!I.use_empty())
77
903
        I.replaceAllUsesWith(UndefValue::get(I.getType()));
78
179k
      BB->getInstList().pop_back();
79
179k
    }
80
104k
    new UnreachableInst(BB->getContext(), BB);
81
104k
    assert(BB->getInstList().size() == 1 &&
82
104k
           isa<UnreachableInst>(BB->getTerminator()) &&
83
104k
           "The successor list of BB isn't empty before "
84
104k
           "applying corresponding DTU updates.");
85
104k
  }
86
641k
}
87
88
void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU,
89
103k
                           bool KeepOneInputPHIs) {
90
103k
  DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);
91
103k
}
92
93
void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU,
94
641k
                            bool KeepOneInputPHIs) {
95
#ifndef NDEBUG
96
  // Make sure that all predecessors of each dead block is also dead.
97
  SmallPtrSet<BasicBlock *, 4> Dead(BBs.begin(), BBs.end());
98
  assert(Dead.size() == BBs.size() && "Duplicating blocks?");
99
  for (auto *BB : Dead)
100
    for (BasicBlock *Pred : predecessors(BB))
101
      assert(Dead.count(Pred) && "All predecessors must be dead!");
102
#endif
103
104
641k
  SmallVector<DominatorTree::UpdateType, 4> Updates;
105
641k
  DetatchDeadBlocks(BBs, DTU ? 
&Updates25.2k
:
nullptr616k
, KeepOneInputPHIs);
106
641k
107
641k
  if (DTU)
108
25.2k
    DTU->applyUpdatesPermissive(Updates);
109
641k
110
641k
  for (BasicBlock *BB : BBs)
111
104k
    if (DTU)
112
25.2k
      DTU->deleteBB(BB);
113
78.8k
    else
114
78.8k
      BB->eraseFromParent();
115
641k
}
116
117
bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
118
537k
                                      bool KeepOneInputPHIs) {
119
537k
  df_iterator_default_set<BasicBlock*> Reachable;
120
537k
121
537k
  // Mark all reachable blocks.
122
537k
  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
123
2.74M
    (void)BB/* Mark all reachable blocks */;
124
537k
125
537k
  // Collect all dead blocks.
126
537k
  std::vector<BasicBlock*> DeadBlocks;
127
3.28M
  for (Function::iterator I = F.begin(), E = F.end(); I != E; 
++I2.74M
)
128
2.74M
    if (!Reachable.count(&*I)) {
129
157
      BasicBlock *BB = &*I;
130
157
      DeadBlocks.push_back(BB);
131
157
    }
132
537k
133
537k
  // Delete the dead blocks.
134
537k
  DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
135
537k
136
537k
  return !DeadBlocks.empty();
137
537k
}
138
139
void llvm::FoldSingleEntryPHINodes(BasicBlock *BB,
140
96.7k
                                   MemoryDependenceResults *MemDep) {
141
96.7k
  if (!isa<PHINode>(BB->begin())) 
return40.3k
;
142
56.3k
143
138k
  
while (PHINode *56.3k
PN = dyn_cast<PHINode>(BB->begin())) {
144
82.0k
    if (PN->getIncomingValue(0) != PN)
145
82.0k
      PN->replaceAllUsesWith(PN->getIncomingValue(0));
146
0
    else
147
0
      PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
148
82.0k
149
82.0k
    if (MemDep)
150
27
      MemDep->removeInstruction(PN);  // Memdep updates AA itself.
151
82.0k
152
82.0k
    PN->eraseFromParent();
153
82.0k
  }
154
56.3k
}
155
156
429k
bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) {
157
429k
  // Recursively deleting a PHI may cause multiple PHIs to be deleted
158
429k
  // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
159
429k
  SmallVector<WeakTrackingVH, 8> PHIs;
160
429k
  for (PHINode &PN : BB->phis())
161
703k
    PHIs.push_back(&PN);
162
429k
163
429k
  bool Changed = false;
164
1.13M
  for (unsigned i = 0, e = PHIs.size(); i != e; 
++i703k
)
165
703k
    if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
166
703k
      Changed |= RecursivelyDeleteDeadPHINode(PN, TLI);
167
429k
168
429k
  return Changed;
169
429k
}
170
171
bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
172
                                     LoopInfo *LI, MemorySSAUpdater *MSSAU,
173
36.1M
                                     MemoryDependenceResults *MemDep) {
174
36.1M
  if (BB->hasAddressTaken())
175
824
    return false;
176
36.1M
177
36.1M
  // Can't merge if there are multiple predecessors, or no predecessors.
178
36.1M
  BasicBlock *PredBB = BB->getUniquePredecessor();
179
36.1M
  if (!PredBB) 
return false15.6M
;
180
20.5M
181
20.5M
  // Don't break self-loops.
182
20.5M
  if (PredBB == BB) 
return false15
;
183
20.5M
  // Don't break unwinding instructions.
184
20.5M
  if (PredBB->getTerminator()->isExceptionalTerminator())
185
657k
    return false;
186
19.8M
187
19.8M
  // Can't merge if there are multiple distinct successors.
188
19.8M
  if (PredBB->getUniqueSuccessor() != BB)
189
19.4M
    return false;
190
476k
191
476k
  // Can't merge if there is PHI loop.
192
476k
  for (PHINode &PN : BB->phis())
193
66.9k
    for (Value *IncValue : PN.incoming_values())
194
73.9k
      if (IncValue == &PN)
195
2
        return false;
196
476k
197
476k
  
LLVM_DEBUG476k
(dbgs() << "Merging: " << BB->getName() << " into "
198
476k
                    << PredBB->getName() << "\n");
199
476k
200
476k
  // Begin by getting rid of unneeded PHIs.
201
476k
  SmallVector<AssertingVH<Value>, 4> IncomingValues;
202
476k
  if (isa<PHINode>(BB->front())) {
203
44.7k
    for (PHINode &PN : BB->phis())
204
66.9k
      if (!isa<PHINode>(PN.getIncomingValue(0)) ||
205
66.9k
          
cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB12.6k
)
206
66.9k
        IncomingValues.push_back(PN.getIncomingValue(0));
207
44.7k
    FoldSingleEntryPHINodes(BB, MemDep);
208
44.7k
  }
209
476k
210
476k
  // DTU update: Collect all the edges that exit BB.
211
476k
  // These dominator edges will be redirected from Pred.
212
476k
  std::vector<DominatorTree::UpdateType> Updates;
213
476k
  if (DTU) {
214
273k
    Updates.reserve(1 + (2 * succ_size(BB)));
215
273k
    // Add insert edges first. Experimentally, for the particular case of two
216
273k
    // blocks that can be merged, with a single successor and single predecessor
217
273k
    // respectively, it is beneficial to have all insert updates first. Deleting
218
273k
    // edges first may lead to unreachable blocks, followed by inserting edges
219
273k
    // making the blocks reachable again. Such DT updates lead to high compile
220
273k
    // times. We add inserts before deletes here to reduce compile time.
221
651k
    for (auto I = succ_begin(BB), E = succ_end(BB); I != E; 
++I377k
)
222
377k
      // This successor of BB may already have PredBB as a predecessor.
223
377k
      if (llvm::find(successors(PredBB), *I) == succ_end(PredBB))
224
377k
        Updates.push_back({DominatorTree::Insert, PredBB, *I});
225
651k
    for (auto I = succ_begin(BB), E = succ_end(BB); I != E; 
++I377k
)
226
377k
      Updates.push_back({DominatorTree::Delete, BB, *I});
227
273k
    Updates.push_back({DominatorTree::Delete, PredBB, BB});
228
273k
  }
229
476k
230
476k
  if (MSSAU)
231
44
    MSSAU->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin()));
232
476k
233
476k
  // Delete the unconditional branch from the predecessor...
234
476k
  PredBB->getInstList().pop_back();
235
476k
236
476k
  // Make all PHI nodes that referred to BB now refer to Pred as their
237
476k
  // source...
238
476k
  BB->replaceAllUsesWith(PredBB);
239
476k
240
476k
  // Move all definitions in the successor to the predecessor...
241
476k
  PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
242
476k
  new UnreachableInst(BB->getContext(), BB);
243
476k
244
476k
  // Eliminate duplicate dbg.values describing the entry PHI node post-splice.
245
476k
  for (auto Incoming : IncomingValues) {
246
66.9k
    if (isa<Instruction>(*Incoming)) {
247
66.6k
      SmallVector<DbgValueInst *, 2> DbgValues;
248
66.6k
      SmallDenseSet<std::pair<DILocalVariable *, DIExpression *>, 2>
249
66.6k
          DbgValueSet;
250
66.6k
      llvm::findDbgValues(DbgValues, Incoming);
251
66.6k
      for (auto &DVI : DbgValues) {
252
24
        auto R = DbgValueSet.insert({DVI->getVariable(), DVI->getExpression()});
253
24
        if (!R.second)
254
6
          DVI->eraseFromParent();
255
24
      }
256
66.6k
    }
257
66.9k
  }
258
476k
259
476k
  // Inherit predecessors name if it exists.
260
476k
  if (!PredBB->hasName())
261
368k
    PredBB->takeName(BB);
262
476k
263
476k
  if (LI)
264
291k
    LI->removeBlock(BB);
265
476k
266
476k
  if (MemDep)
267
23.7k
    MemDep->invalidateCachedPredecessors();
268
476k
269
476k
  // Finally, erase the old block and update dominator info.
270
476k
  if (DTU) {
271
273k
    assert(BB->getInstList().size() == 1 &&
272
273k
           isa<UnreachableInst>(BB->getTerminator()) &&
273
273k
           "The successor list of BB isn't empty before "
274
273k
           "applying corresponding DTU updates.");
275
273k
    DTU->applyUpdatesPermissive(Updates);
276
273k
    DTU->deleteBB(BB);
277
273k
  }
278
202k
279
202k
  else {
280
202k
    BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
281
202k
  }
282
476k
  return true;
283
476k
}
284
285
void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
286
42.0k
                                BasicBlock::iterator &BI, Value *V) {
287
42.0k
  Instruction &I = *BI;
288
42.0k
  // Replaces all of the uses of the instruction with uses of the value
289
42.0k
  I.replaceAllUsesWith(V);
290
42.0k
291
42.0k
  // Make sure to propagate a name if there is one already.
292
42.0k
  if (I.hasName() && 
!V->hasName()0
)
293
0
    V->takeName(&I);
294
42.0k
295
42.0k
  // Delete the unnecessary instruction now...
296
42.0k
  BI = BIL.erase(BI);
297
42.0k
}
298
299
void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
300
42.0k
                               BasicBlock::iterator &BI, Instruction *I) {
301
42.0k
  assert(I->getParent() == nullptr &&
302
42.0k
         "ReplaceInstWithInst: Instruction already inserted into basic block!");
303
42.0k
304
42.0k
  // Copy debug location to newly added instruction, if it wasn't already set
305
42.0k
  // by the caller.
306
42.0k
  if (!I->getDebugLoc())
307
41.0k
    I->setDebugLoc(BI->getDebugLoc());
308
42.0k
309
42.0k
  // Insert the new instruction into the basic block...
310
42.0k
  BasicBlock::iterator New = BIL.insert(BI, I);
311
42.0k
312
42.0k
  // Replace all uses of the old instruction, and delete it.
313
42.0k
  ReplaceInstWithValue(BIL, BI, I);
314
42.0k
315
42.0k
  // Move BI back to point to the newly inserted instruction
316
42.0k
  BI = New;
317
42.0k
}
318
319
42.0k
void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
320
42.0k
  BasicBlock::iterator BI(From);
321
42.0k
  ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
322
42.0k
}
323
324
BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
325
6.14k
                            LoopInfo *LI, MemorySSAUpdater *MSSAU) {
326
6.14k
  unsigned SuccNum = GetSuccessorNumber(BB, Succ);
327
6.14k
328
6.14k
  // If this is a critical edge, let SplitCriticalEdge do it.
329
6.14k
  Instruction *LatchTerm = BB->getTerminator();
330
6.14k
  if (SplitCriticalEdge(
331
6.14k
          LatchTerm, SuccNum,
332
6.14k
          CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA()))
333
341
    return LatchTerm->getSuccessor(SuccNum);
334
5.80k
335
5.80k
  // If the edge isn't critical, then BB has a single successor or Succ has a
336
5.80k
  // single pred.  Split the block.
337
5.80k
  if (BasicBlock *SP = Succ->getSinglePredecessor()) {
338
85
    // If the successor only has a single pred, split the top of the successor
339
85
    // block.
340
85
    assert(SP == BB && "CFG broken");
341
85
    SP = nullptr;
342
85
    return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU);
343
85
  }
344
5.71k
345
5.71k
  // Otherwise, if BB has a single successor, split it at the bottom of the
346
5.71k
  // block.
347
5.71k
  assert(BB->getTerminator()->getNumSuccessors() == 1 &&
348
5.71k
         "Should have a single succ!");
349
5.71k
  return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU);
350
5.71k
}
351
352
unsigned
353
llvm::SplitAllCriticalEdges(Function &F,
354
65
                            const CriticalEdgeSplittingOptions &Options) {
355
65
  unsigned NumBroken = 0;
356
1.53k
  for (BasicBlock &BB : F) {
357
1.53k
    Instruction *TI = BB.getTerminator();
358
1.53k
    if (TI->getNumSuccessors() > 1 && 
!isa<IndirectBrInst>(TI)517
)
359
1.64k
      
for (unsigned i = 0, e = TI->getNumSuccessors(); 516
i != e;
++i1.13k
)
360
1.13k
        if (SplitCriticalEdge(TI, i, Options))
361
492
          ++NumBroken;
362
1.53k
  }
363
65
  return NumBroken;
364
65
}
365
366
BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt,
367
                             DominatorTree *DT, LoopInfo *LI,
368
12.2k
                             MemorySSAUpdater *MSSAU) {
369
12.2k
  BasicBlock::iterator SplitIt = SplitPt->getIterator();
370
12.3k
  while (isa<PHINode>(SplitIt) || 
SplitIt->isEHPad()12.2k
)
371
118
    ++SplitIt;
372
12.2k
  BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
373
12.2k
374
12.2k
  // The new block lives in whichever loop the old one did. This preserves
375
12.2k
  // LCSSA as well, because we force the split point to be after any PHI nodes.
376
12.2k
  if (LI)
377
11.5k
    if (Loop *L = LI->getLoopFor(Old))
378
3.88k
      L->addBasicBlockToLoop(New, *LI);
379
12.2k
380
12.2k
  if (DT)
381
11.6k
    // Old dominates New. New node dominates all other nodes dominated by Old.
382
11.6k
    if (DomTreeNode *OldNode = DT->getNode(Old)) {
383
11.6k
      std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
384
11.6k
385
11.6k
      DomTreeNode *NewNode = DT->addNewBlock(New, Old);
386
11.6k
      for (DomTreeNode *I : Children)
387
10.6k
        DT->changeImmediateDominator(I, NewNode);
388
11.6k
    }
389
12.2k
390
12.2k
  // Move MemoryAccesses still tracked in Old, but part of New now.
391
12.2k
  // Update accesses in successor blocks accordingly.
392
12.2k
  if (MSSAU)
393
335
    MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
394
12.2k
395
12.2k
  return New;
396
12.2k
}
397
398
/// Update DominatorTree, LoopInfo, and LCCSA analysis information.
399
static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
400
                                      ArrayRef<BasicBlock *> Preds,
401
                                      DominatorTree *DT, LoopInfo *LI,
402
                                      MemorySSAUpdater *MSSAU,
403
1.30M
                                      bool PreserveLCSSA, bool &HasLoopExit) {
404
1.30M
  // Update dominator tree if available.
405
1.30M
  if (DT) {
406
1.27M
    if (OldBB == DT->getRootNode()->getBlock()) {
407
1
      assert(NewBB == &NewBB->getParent()->getEntryBlock());
408
1
      DT->setNewRoot(NewBB);
409
1.27M
    } else {
410
1.27M
      // Split block expects NewBB to have a non-empty set of predecessors.
411
1.27M
      DT->splitBlock(NewBB);
412
1.27M
    }
413
1.27M
  }
414
1.30M
415
1.30M
  // Update MemoryPhis after split if MemorySSA is available
416
1.30M
  if (MSSAU)
417
211
    MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
418
1.30M
419
1.30M
  // The rest of the logic is only relevant for updating the loop structures.
420
1.30M
  if (!LI)
421
24.1k
    return;
422
1.27M
423
1.27M
  assert(DT && "DT should be available to update LoopInfo!");
424
1.27M
  Loop *L = LI->getLoopFor(OldBB);
425
1.27M
426
1.27M
  // If we need to preserve loop analyses, collect some information about how
427
1.27M
  // this split will affect loops.
428
1.27M
  bool IsLoopEntry = !!L;
429
1.27M
  bool SplitMakesNewLoopHeader = false;
430
1.37M
  for (BasicBlock *Pred : Preds) {
431
1.37M
    // Preds that are not reachable from entry should not be used to identify if
432
1.37M
    // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
433
1.37M
    // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
434
1.37M
    // as true and make the NewBB the header of some loop. This breaks LI.
435
1.37M
    if (!DT->isReachableFromEntry(Pred))
436
5
      continue;
437
1.37M
    // If we need to preserve LCSSA, determine if any of the preds is a loop
438
1.37M
    // exit.
439
1.37M
    if (PreserveLCSSA)
440
12.6k
      if (Loop *PL = LI->getLoopFor(Pred))
441
12.1k
        if (!PL->contains(OldBB))
442
12.0k
          HasLoopExit = true;
443
1.37M
444
1.37M
    // If we need to preserve LoopInfo, note whether any of the preds crosses
445
1.37M
    // an interesting loop boundary.
446
1.37M
    if (!L)
447
686k
      continue;
448
693k
    if (L->contains(Pred))
449
170k
      IsLoopEntry = false;
450
523k
    else
451
523k
      SplitMakesNewLoopHeader = true;
452
693k
  }
453
1.27M
454
1.27M
  // Unless we have a loop for OldBB, nothing else to do here.
455
1.27M
  if (!L)
456
624k
    return;
457
652k
458
652k
  if (IsLoopEntry) {
459
490k
    // Add the new block to the nearest enclosing loop (and not an adjacent
460
490k
    // loop). To find this, examine each of the predecessors and determine which
461
490k
    // loops enclose them, and select the most-nested loop which contains the
462
490k
    // loop containing the block being split.
463
490k
    Loop *InnermostPredLoop = nullptr;
464
522k
    for (BasicBlock *Pred : Preds) {
465
522k
      if (Loop *PredLoop = LI->getLoopFor(Pred)) {
466
190k
        // Seek a loop which actually contains the block being split (to avoid
467
190k
        // adjacent loops).
468
237k
        while (PredLoop && 
!PredLoop->contains(OldBB)193k
)
469
46.2k
          PredLoop = PredLoop->getParentLoop();
470
190k
471
190k
        // Select the most-nested of these loops which contains the block.
472
190k
        if (PredLoop && 
PredLoop->contains(OldBB)147k
&&
473
190k
            
(147k
!InnermostPredLoop147k
||
474
147k
             
InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()6.29k
))
475
140k
          InnermostPredLoop = PredLoop;
476
190k
      }
477
522k
    }
478
490k
479
490k
    if (InnermostPredLoop)
480
140k
      InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
481
490k
  } else {
482
162k
    L->addBasicBlockToLoop(NewBB, *LI);
483
162k
    if (SplitMakesNewLoopHeader)
484
343
      L->moveToHeader(NewBB);
485
162k
  }
486
652k
}
487
488
/// Update the PHI nodes in OrigBB to include the values coming from NewBB.
489
/// This also updates AliasAnalysis, if available.
490
static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
491
                           ArrayRef<BasicBlock *> Preds, BranchInst *BI,
492
1.30M
                           bool HasLoopExit) {
493
1.30M
  // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
494
1.30M
  SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
495
2.36M
  for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
496
1.06M
    PHINode *PN = cast<PHINode>(I++);
497
1.06M
498
1.06M
    // Check to see if all of the values coming in are the same.  If so, we
499
1.06M
    // don't need to create a new PHI node, unless it's needed for LCSSA.
500
1.06M
    Value *InVal = nullptr;
501
1.06M
    if (!HasLoopExit) {
502
1.05M
      InVal = PN->getIncomingValueForBlock(Preds[0]);
503
4.31M
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; 
++i3.25M
) {
504
3.32M
        if (!PredSet.count(PN->getIncomingBlock(i)))
505
2.17M
          continue;
506
1.15M
        if (!InVal)
507
0
          InVal = PN->getIncomingValue(i);
508
1.15M
        else if (InVal != PN->getIncomingValue(i)) {
509
73.1k
          InVal = nullptr;
510
73.1k
          break;
511
73.1k
        }
512
1.15M
      }
513
1.05M
    }
514
1.06M
515
1.06M
    if (InVal) {
516
985k
      // If all incoming values for the new PHI would be the same, just don't
517
985k
      // make a new PHI.  Instead, just remove the incoming values from the old
518
985k
      // PHI.
519
985k
520
985k
      // NOTE! This loop walks backwards for a reason! First off, this minimizes
521
985k
      // the cost of removal if we end up removing a large number of values, and
522
985k
      // second off, this ensures that the indices for the incoming values
523
985k
      // aren't invalidated when we remove one.
524
4.11M
      for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; 
--i3.12M
)
525
3.12M
        if (PredSet.count(PN->getIncomingBlock(i)))
526
1.03M
          PN->removeIncomingValue(i, false);
527
985k
528
985k
      // Add an incoming value to the PHI node in the loop for the preheader
529
985k
      // edge.
530
985k
      PN->addIncoming(InVal, NewBB);
531
985k
      continue;
532
985k
    }
533
82.0k
534
82.0k
    // If the values coming into the block are not the same, we need a new
535
82.0k
    // PHI.
536
82.0k
    // Create the new PHI node, insert it into NewBB at the end of the block
537
82.0k
    PHINode *NewPHI =
538
82.0k
        PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
539
82.0k
540
82.0k
    // NOTE! This loop walks backwards for a reason! First off, this minimizes
541
82.0k
    // the cost of removal if we end up removing a large number of values, and
542
82.0k
    // second off, this ensures that the indices for the incoming values aren't
543
82.0k
    // invalidated when we remove one.
544
427k
    for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; 
--i345k
) {
545
345k
      BasicBlock *IncomingBB = PN->getIncomingBlock(i);
546
345k
      if (PredSet.count(IncomingBB)) {
547
229k
        Value *V = PN->removeIncomingValue(i, false);
548
229k
        NewPHI->addIncoming(V, IncomingBB);
549
229k
      }
550
345k
    }
551
82.0k
552
82.0k
    PN->addIncoming(NewPHI, NewBB);
553
82.0k
  }
554
1.30M
}
555
556
BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
557
                                         ArrayRef<BasicBlock *> Preds,
558
                                         const char *Suffix, DominatorTree *DT,
559
                                         LoopInfo *LI, MemorySSAUpdater *MSSAU,
560
1.30M
                                         bool PreserveLCSSA) {
561
1.30M
  // Do not attempt to split that which cannot be split.
562
1.30M
  if (!BB->canSplitPredecessors())
563
2
    return nullptr;
564
1.30M
565
1.30M
  // For the landingpads we need to act a bit differently.
566
1.30M
  // Delegate this work to the SplitLandingPadPredecessors.
567
1.30M
  if (BB->isLandingPad()) {
568
662
    SmallVector<BasicBlock*, 2> NewBBs;
569
662
    std::string NewName = std::string(Suffix) + ".split-lp";
570
662
571
662
    SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
572
662
                                LI, MSSAU, PreserveLCSSA);
573
662
    return NewBBs[0];
574
662
  }
575
1.29M
576
1.29M
  // Create new basic block, insert right before the original block.
577
1.29M
  BasicBlock *NewBB = BasicBlock::Create(
578
1.29M
      BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
579
1.29M
580
1.29M
  // The new block unconditionally branches to the old block.
581
1.29M
  BranchInst *BI = BranchInst::Create(BB, NewBB);
582
1.29M
  // Splitting the predecessors of a loop header creates a preheader block.
583
1.29M
  if (LI && 
LI->isLoopHeader(BB)1.27M
)
584
491k
    // Using the loop start line number prevents debuggers stepping into the
585
491k
    // loop body for this instruction.
586
491k
    BI->setDebugLoc(LI->getLoopFor(BB)->getStartLoc());
587
808k
  else
588
808k
    BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
589
1.29M
590
1.29M
  // Move the edges from Preds to point to NewBB instead of BB.
591
2.77M
  for (unsigned i = 0, e = Preds.size(); i != e; 
++i1.47M
) {
592
1.47M
    // This is slightly more strict than necessary; the minimum requirement
593
1.47M
    // is that there be no more than one indirectbr branching to BB. And
594
1.47M
    // all BlockAddress uses would need to be updated.
595
1.47M
    assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
596
1.47M
           "Cannot split an edge from an IndirectBrInst");
597
1.47M
    assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
598
1.47M
           "Cannot split an edge from a CallBrInst");
599
1.47M
    Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
600
1.47M
  }
601
1.29M
602
1.29M
  // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
603
1.29M
  // node becomes an incoming value for BB's phi node.  However, if the Preds
604
1.29M
  // list is empty, we need to insert dummy entries into the PHI nodes in BB to
605
1.29M
  // account for the newly created predecessor.
606
1.29M
  if (Preds.empty()) {
607
1
    // Insert dummy values as the incoming value.
608
1
    for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); 
++I0
)
609
0
      cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
610
1
  }
611
1.29M
612
1.29M
  // Update DominatorTree, LoopInfo, and LCCSA analysis information.
613
1.29M
  bool HasLoopExit = false;
614
1.29M
  UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSAU, PreserveLCSSA,
615
1.29M
                            HasLoopExit);
616
1.29M
617
1.29M
  if (!Preds.empty()) {
618
1.29M
    // Update the PHI nodes in BB with the values coming from NewBB.
619
1.29M
    UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
620
1.29M
  }
621
1.29M
622
1.29M
  return NewBB;
623
1.29M
}
624
625
void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
626
                                       ArrayRef<BasicBlock *> Preds,
627
                                       const char *Suffix1, const char *Suffix2,
628
                                       SmallVectorImpl<BasicBlock *> &NewBBs,
629
                                       DominatorTree *DT, LoopInfo *LI,
630
                                       MemorySSAUpdater *MSSAU,
631
690
                                       bool PreserveLCSSA) {
632
690
  assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
633
690
634
690
  // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
635
690
  // it right before the original block.
636
690
  BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
637
690
                                          OrigBB->getName() + Suffix1,
638
690
                                          OrigBB->getParent(), OrigBB);
639
690
  NewBBs.push_back(NewBB1);
640
690
641
690
  // The new block unconditionally branches to the old block.
642
690
  BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
643
690
  BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
644
690
645
690
  // Move the edges from Preds to point to NewBB1 instead of OrigBB.
646
1.73k
  for (unsigned i = 0, e = Preds.size(); i != e; 
++i1.04k
) {
647
1.04k
    // This is slightly more strict than necessary; the minimum requirement
648
1.04k
    // is that there be no more than one indirectbr branching to BB. And
649
1.04k
    // all BlockAddress uses would need to be updated.
650
1.04k
    assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
651
1.04k
           "Cannot split an edge from an IndirectBrInst");
652
1.04k
    Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
653
1.04k
  }
654
690
655
690
  bool HasLoopExit = false;
656
690
  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSAU, PreserveLCSSA,
657
690
                            HasLoopExit);
658
690
659
690
  // Update the PHI nodes in OrigBB with the values coming from NewBB1.
660
690
  UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
661
690
662
690
  // Move the remaining edges from OrigBB to point to NewBB2.
663
690
  SmallVector<BasicBlock*, 8> NewBB2Preds;
664
690
  for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
665
4.54k
       i != e; ) {
666
3.85k
    BasicBlock *Pred = *i++;
667
3.85k
    if (Pred == NewBB1) 
continue690
;
668
3.16k
    assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
669
3.16k
           "Cannot split an edge from an IndirectBrInst");
670
3.16k
    NewBB2Preds.push_back(Pred);
671
3.16k
    e = pred_end(OrigBB);
672
3.16k
  }
673
690
674
690
  BasicBlock *NewBB2 = nullptr;
675
690
  if (!NewBB2Preds.empty()) {
676
564
    // Create another basic block for the rest of OrigBB's predecessors.
677
564
    NewBB2 = BasicBlock::Create(OrigBB->getContext(),
678
564
                                OrigBB->getName() + Suffix2,
679
564
                                OrigBB->getParent(), OrigBB);
680
564
    NewBBs.push_back(NewBB2);
681
564
682
564
    // The new block unconditionally branches to the old block.
683
564
    BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
684
564
    BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
685
564
686
564
    // Move the remaining edges from OrigBB to point to NewBB2.
687
564
    for (BasicBlock *NewBB2Pred : NewBB2Preds)
688
3.16k
      NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
689
564
690
564
    // Update DominatorTree, LoopInfo, and LCCSA analysis information.
691
564
    HasLoopExit = false;
692
564
    UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSAU,
693
564
                              PreserveLCSSA, HasLoopExit);
694
564
695
564
    // Update the PHI nodes in OrigBB with the values coming from NewBB2.
696
564
    UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
697
564
  }
698
690
699
690
  LandingPadInst *LPad = OrigBB->getLandingPadInst();
700
690
  Instruction *Clone1 = LPad->clone();
701
690
  Clone1->setName(Twine("lpad") + Suffix1);
702
690
  NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
703
690
704
690
  if (NewBB2) {
705
564
    Instruction *Clone2 = LPad->clone();
706
564
    Clone2->setName(Twine("lpad") + Suffix2);
707
564
    NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
708
564
709
564
    // Create a PHI node for the two cloned landingpad instructions only
710
564
    // if the original landingpad instruction has some uses.
711
564
    if (!LPad->use_empty()) {
712
545
      assert(!LPad->getType()->isTokenTy() &&
713
545
             "Split cannot be applied if LPad is token type. Otherwise an "
714
545
             "invalid PHINode of token type would be created.");
715
545
      PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
716
545
      PN->addIncoming(Clone1, NewBB1);
717
545
      PN->addIncoming(Clone2, NewBB2);
718
545
      LPad->replaceAllUsesWith(PN);
719
545
    }
720
564
    LPad->eraseFromParent();
721
564
  } else {
722
126
    // There is no second clone. Just replace the landing pad with the first
723
126
    // clone.
724
126
    LPad->replaceAllUsesWith(Clone1);
725
126
    LPad->eraseFromParent();
726
126
  }
727
690
}
728
729
ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
730
                                             BasicBlock *Pred,
731
117k
                                             DomTreeUpdater *DTU) {
732
117k
  Instruction *UncondBranch = Pred->getTerminator();
733
117k
  // Clone the return and add it to the end of the predecessor.
734
117k
  Instruction *NewRet = RI->clone();
735
117k
  Pred->getInstList().push_back(NewRet);
736
117k
737
117k
  // If the return instruction returns a value, and if the value was a
738
117k
  // PHI node in "BB", propagate the right value into the return.
739
117k
  for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
740
221k
       i != e; 
++i103k
) {
741
103k
    Value *V = *i;
742
103k
    Instruction *NewBC = nullptr;
743
103k
    if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
744
12
      // Return value might be bitcasted. Clone and insert it before the
745
12
      // return instruction.
746
12
      V = BCI->getOperand(0);
747
12
      NewBC = BCI->clone();
748
12
      Pred->getInstList().insert(NewRet->getIterator(), NewBC);
749
12
      *i = NewBC;
750
12
    }
751
103k
    if (PHINode *PN = dyn_cast<PHINode>(V)) {
752
99.3k
      if (PN->getParent() == BB) {
753
99.3k
        if (NewBC)
754
11
          NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
755
99.3k
        else
756
99.3k
          *i = PN->getIncomingValueForBlock(Pred);
757
99.3k
      }
758
99.3k
    }
759
103k
  }
760
117k
761
117k
  // Update any PHI nodes in the returning block to realize that we no
762
117k
  // longer branch to them.
763
117k
  BB->removePredecessor(Pred);
764
117k
  UncondBranch->eraseFromParent();
765
117k
766
117k
  if (DTU)
767
418
    DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
768
117k
769
117k
  return cast<ReturnInst>(NewRet);
770
117k
}
771
772
Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
773
                                             Instruction *SplitBefore,
774
                                             bool Unreachable,
775
                                             MDNode *BranchWeights,
776
                                             DominatorTree *DT, LoopInfo *LI,
777
3.47k
                                             BasicBlock *ThenBlock) {
778
3.47k
  BasicBlock *Head = SplitBefore->getParent();
779
3.47k
  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
780
3.47k
  Instruction *HeadOldTerm = Head->getTerminator();
781
3.47k
  LLVMContext &C = Head->getContext();
782
3.47k
  Instruction *CheckTerm;
783
3.47k
  bool CreateThenBlock = (ThenBlock == nullptr);
784
3.47k
  if (CreateThenBlock) {
785
3.30k
    ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
786
3.30k
    if (Unreachable)
787
274
      CheckTerm = new UnreachableInst(C, ThenBlock);
788
3.03k
    else
789
3.03k
      CheckTerm = BranchInst::Create(Tail, ThenBlock);
790
3.30k
    CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
791
3.30k
  } else
792
172
    CheckTerm = ThenBlock->getTerminator();
793
3.47k
  BranchInst *HeadNewTerm =
794
3.47k
    BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
795
3.47k
  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
796
3.47k
  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
797
3.47k
798
3.47k
  if (DT) {
799
175
    if (DomTreeNode *OldNode = DT->getNode(Head)) {
800
175
      std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
801
175
802
175
      DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
803
175
      for (DomTreeNode *Child : Children)
804
14
        DT->changeImmediateDominator(Child, NewNode);
805
175
806
175
      // Head dominates ThenBlock.
807
175
      if (CreateThenBlock)
808
175
        DT->addNewBlock(ThenBlock, Head);
809
0
      else
810
0
        DT->changeImmediateDominator(ThenBlock, Head);
811
175
    }
812
175
  }
813
3.47k
814
3.47k
  if (LI) {
815
9
    if (Loop *L = LI->getLoopFor(Head)) {
816
9
      L->addBasicBlockToLoop(ThenBlock, *LI);
817
9
      L->addBasicBlockToLoop(Tail, *LI);
818
9
    }
819
9
  }
820
3.47k
821
3.47k
  return CheckTerm;
822
3.47k
}
823
824
void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
825
                                         Instruction **ThenTerm,
826
                                         Instruction **ElseTerm,
827
132
                                         MDNode *BranchWeights) {
828
132
  BasicBlock *Head = SplitBefore->getParent();
829
132
  BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
830
132
  Instruction *HeadOldTerm = Head->getTerminator();
831
132
  LLVMContext &C = Head->getContext();
832
132
  BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
833
132
  BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
834
132
  *ThenTerm = BranchInst::Create(Tail, ThenBlock);
835
132
  (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
836
132
  *ElseTerm = BranchInst::Create(Tail, ElseBlock);
837
132
  (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
838
132
  BranchInst *HeadNewTerm =
839
132
    BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
840
132
  HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
841
132
  ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
842
132
}
843
844
Value *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
845
4.69M
                             BasicBlock *&IfFalse) {
846
4.69M
  PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
847
4.69M
  BasicBlock *Pred1 = nullptr;
848
4.69M
  BasicBlock *Pred2 = nullptr;
849
4.69M
850
4.69M
  if (SomePHI) {
851
4.66M
    if (SomePHI->getNumIncomingValues() != 2)
852
19
      return nullptr;
853
4.66M
    Pred1 = SomePHI->getIncomingBlock(0);
854
4.66M
    Pred2 = SomePHI->getIncomingBlock(1);
855
4.66M
  } else {
856
30.3k
    pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
857
30.3k
    if (PI == PE) // No predecessor
858
28.1k
      return nullptr;
859
2.22k
    Pred1 = *PI++;
860
2.22k
    if (PI == PE) // Only one predecessor
861
1.71k
      return nullptr;
862
505
    Pred2 = *PI++;
863
505
    if (PI != PE) // More than two predecessors
864
38
      return nullptr;
865
4.66M
  }
866
4.66M
867
4.66M
  // We can only handle branches.  Other control flow will be lowered to
868
4.66M
  // branches if possible anyway.
869
4.66M
  BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
870
4.66M
  BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
871
4.66M
  if (!Pred1Br || 
!Pred2Br4.65M
)
872
35.4k
    return nullptr;
873
4.62M
874
4.62M
  // Eliminate code duplication by ensuring that Pred1Br is conditional if
875
4.62M
  // either are.
876
4.62M
  if (Pred2Br->isConditional()) {
877
3.36M
    // If both branches are conditional, we don't have an "if statement".  In
878
3.36M
    // reality, we could transform this case, but since the condition will be
879
3.36M
    // required anyway, we stand no chance of eliminating it, so the xform is
880
3.36M
    // probably not profitable.
881
3.36M
    if (Pred1Br->isConditional())
882
1.66M
      return nullptr;
883
1.70M
884
1.70M
    std::swap(Pred1, Pred2);
885
1.70M
    std::swap(Pred1Br, Pred2Br);
886
1.70M
  }
887
4.62M
888
4.62M
  
if (2.96M
Pred1Br->isConditional()2.96M
) {
889
2.38M
    // The only thing we have to watch out for here is to make sure that Pred2
890
2.38M
    // doesn't have incoming edges from other blocks.  If it does, the condition
891
2.38M
    // doesn't dominate BB.
892
2.38M
    if (!Pred2->getSinglePredecessor())
893
661k
      return nullptr;
894
1.72M
895
1.72M
    // If we found a conditional branch predecessor, make sure that it branches
896
1.72M
    // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
897
1.72M
    if (Pred1Br->getSuccessor(0) == BB &&
898
1.72M
        
Pred1Br->getSuccessor(1) == Pred2869k
) {
899
433k
      IfTrue = Pred1;
900
433k
      IfFalse = Pred2;
901
1.28M
    } else if (Pred1Br->getSuccessor(0) == Pred2 &&
902
1.28M
               
Pred1Br->getSuccessor(1) == BB242k
) {
903
242k
      IfTrue = Pred2;
904
242k
      IfFalse = Pred1;
905
1.04M
    } else {
906
1.04M
      // We know that one arm of the conditional goes to BB, so the other must
907
1.04M
      // go somewhere unrelated, and this must not be an "if statement".
908
1.04M
      return nullptr;
909
1.04M
    }
910
676k
911
676k
    return Pred1Br->getCondition();
912
676k
  }
913
584k
914
584k
  // Ok, if we got here, both predecessors end with an unconditional branch to
915
584k
  // BB.  Don't panic!  If both blocks only have a single (identical)
916
584k
  // predecessor, and THAT is a conditional branch, then we're all ok!
917
584k
  BasicBlock *CommonPred = Pred1->getSinglePredecessor();
918
584k
  if (CommonPred == nullptr || 
CommonPred != Pred2->getSinglePredecessor()361k
)
919
372k
    return nullptr;
920
211k
921
211k
  // Otherwise, if this is a conditional branch, then we can use it!
922
211k
  BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
923
211k
  if (!BI) 
return nullptr1.26k
;
924
210k
925
210k
  assert(BI->isConditional() && "Two successors but not conditional?");
926
210k
  if (BI->getSuccessor(0) == Pred1) {
927
101k
    IfTrue = Pred1;
928
101k
    IfFalse = Pred2;
929
108k
  } else {
930
108k
    IfTrue = Pred2;
931
108k
    IfFalse = Pred1;
932
108k
  }
933
210k
  return BI->getCondition();
934
210k
}