← Back to branch summary

~ubuntu-branches/ubuntu/trusty/llvm-toolchain-snapshot/trusty-201310232150

« back to all changes in this revision

Viewing changes to lib/Transforms/Utils/SimplifyCFG.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-27 15:01:57 UTC
  • mfrom: (0.10.1) (0.9.1) (0.8.1) (0.7.1) (0.6.1) (0.5.2)
  • Revision ID: package-import@ubuntu.com-20130527150157-tdkrsjpuvht7v0qx
Tags: 1:3.4~svn182733-1~exp1
http://bugs.debian.org/708677
* New snapshot release (3.4 release)
* Add a symlink of libLLVM-3.4.so.1 to usr/lib/llvm-3.4/lib/libLLVM-3.4.so
    to fix make the llvm-config-3.4 --libdir work (Closes: #708677)
  * Various packages rename to allow co installations:
    * libclang1 => libclang1-3.4
    * libclang1-dbg => libclang1-3.4-dbg
    * libclang-dev => libclang-3.4-dev
    * libclang-common-dev => libclang-common-3.4-dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/Transforms/Utils/SimplifyCFG.cpp
59
59
SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
60
60
       cl::desc("Sink common instructions down to the end block"));
61
61
 
 
62
static cl::opt<bool>
 
63
HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
 
64
       cl::desc("Hoist conditional stores if an unconditional store preceeds"));
 
65
 
62
66
STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
63
67
STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
64
68
STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
1332
1336
  return Changed;
1333
1337
}
1334
1338
 
 
1339
/// \brief Determine if we can hoist sink a sole store instruction out of a
 
1340
/// conditional block.
 
1341
///
 
1342
/// We are looking for code like the following:
 
1343
///   BrBB:
 
1344
///     store i32 %add, i32* %arrayidx2
 
1345
///     ... // No other stores or function calls (we could be calling a memory
 
1346
///     ... // function).
 
1347
///     %cmp = icmp ult %x, %y
 
1348
///     br i1 %cmp, label %EndBB, label %ThenBB
 
1349
///   ThenBB:
 
1350
///     store i32 %add5, i32* %arrayidx2
 
1351
///     br label EndBB
 
1352
///   EndBB:
 
1353
///     ...
 
1354
///   We are going to transform this into:
 
1355
///   BrBB:
 
1356
///     store i32 %add, i32* %arrayidx2
 
1357
///     ... //
 
1358
///     %cmp = icmp ult %x, %y
 
1359
///     %add.add5 = select i1 %cmp, i32 %add, %add5
 
1360
///     store i32 %add.add5, i32* %arrayidx2
 
1361
///     ...
 
1362
///
 
1363
/// \return The pointer to the value of the previous store if the store can be
 
1364
///         hoisted into the predecessor block. 0 otherwise.
 
1365
static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB,
 
1366
                                     BasicBlock *StoreBB, BasicBlock *EndBB) {
 
1367
  StoreInst *StoreToHoist = dyn_cast<StoreInst>(I);
 
1368
  if (!StoreToHoist)
 
1369
    return 0;
 
1370
 
 
1371
  // Volatile or atomic.
 
1372
  if (!StoreToHoist->isSimple())
 
1373
    return 0;
 
1374
 
 
1375
  Value *StorePtr = StoreToHoist->getPointerOperand();
 
1376
 
 
1377
  // Look for a store to the same pointer in BrBB.
 
1378
  unsigned MaxNumInstToLookAt = 10;
 
1379
  for (BasicBlock::reverse_iterator RI = BrBB->rbegin(),
 
1380
       RE = BrBB->rend(); RI != RE && (--MaxNumInstToLookAt); ++RI) {
 
1381
    Instruction *CurI = &*RI;
 
1382
 
 
1383
    // Could be calling an instruction that effects memory like free().
 
1384
    if (CurI->mayHaveSideEffects() && !isa<StoreInst>(CurI))
 
1385
      return 0;
 
1386
 
 
1387
    StoreInst *SI = dyn_cast<StoreInst>(CurI);
 
1388
    // Found the previous store make sure it stores to the same location.
 
1389
    if (SI && SI->getPointerOperand() == StorePtr)
 
1390
      // Found the previous store, return its value operand.
 
1391
      return SI->getValueOperand();
 
1392
    else if (SI)
 
1393
      return 0; // Unknown store.
 
1394
  }
 
1395
 
 
1396
  return 0;
 
1397
}
 
1398
 
1335
1399
/// \brief Speculate a conditional basic block flattening the CFG.
1336
1400
///
1337
1401
/// Note that this is a very risky transform currently. Speculating
1395
1459
  SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts;
1396
1460
 
1397
1461
  unsigned SpeculationCost = 0;
 
1462
  Value *SpeculatedStoreValue = 0;
 
1463
  StoreInst *SpeculatedStore = 0;
1398
1464
  for (BasicBlock::iterator BBI = ThenBB->begin(),
1399
1465
                            BBE = llvm::prior(ThenBB->end());
1400
1466
       BBI != BBE; ++BBI) {
1410
1476
      return false;
1411
1477
 
1412
1478
    // Don't hoist the instruction if it's unsafe or expensive.
1413
 
    if (!isSafeToSpeculativelyExecute(I))
1414
 
      return false;
1415
 
    if (ComputeSpeculationCost(I) > PHINodeFoldingThreshold)
1416
 
      return false;
 
1479
    if (!isSafeToSpeculativelyExecute(I) &&
 
1480
        !(HoistCondStores &&
 
1481
          (SpeculatedStoreValue = isSafeToSpeculateStore(I, BB, ThenBB,
 
1482
                                                         EndBB))))
 
1483
      return false;
 
1484
    if (!SpeculatedStoreValue &&
 
1485
        ComputeSpeculationCost(I) > PHINodeFoldingThreshold)
 
1486
      return false;
 
1487
 
 
1488
    // Store the store speculation candidate.
 
1489
    if (SpeculatedStoreValue)
 
1490
      SpeculatedStore = cast<StoreInst>(I);
1417
1491
 
1418
1492
    // Do not hoist the instruction if any of its operands are defined but not
1419
 
    // used in this BB. The transformation will prevent the operand from
 
1493
    // used in BB. The transformation will prevent the operand from
1420
1494
    // being sunk into the use block.
1421
1495
    for (User::op_iterator i = I->op_begin(), e = I->op_end();
1422
1496
         i != e; ++i) {
1473
1547
 
1474
1548
  // If there are no PHIs to process, bail early. This helps ensure idempotence
1475
1549
  // as well.
1476
 
  if (!HaveRewritablePHIs)
 
1550
  if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue))
1477
1551
    return false;
1478
1552
 
1479
1553
  // If we get here, we can hoist the instruction and if-convert.
1480
1554
  DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";);
1481
1555
 
 
1556
  // Insert a select of the value of the speculated store.
 
1557
  if (SpeculatedStoreValue) {
 
1558
    IRBuilder<true, NoFolder> Builder(BI);
 
1559
    Value *TrueV = SpeculatedStore->getValueOperand();
 
1560
    Value *FalseV = SpeculatedStoreValue;
 
1561
    if (Invert)
 
1562
      std::swap(TrueV, FalseV);
 
1563
    Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() +
 
1564
                                    "." + FalseV->getName());
 
1565
    SpeculatedStore->setOperand(0, S);
 
1566
  }
 
1567
 
1482
1568
  // Hoist the instructions.
1483
1569
  BB->getInstList().splice(BI, ThenBB->getInstList(), ThenBB->begin(),
1484
1570
                           llvm::prior(ThenBB->end()));