JumpThreading.cpp revision ce665bd2e2b581ab0858d1afe359192bac96b868
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com//===- JumpThreading.cpp - Thread control through conditional blocks ------===// 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// The LLVM Compiler Infrastructure 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// This file is distributed under the University of Illinois Open Source 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// License. See LICENSE.TXT for details. 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//===----------------------------------------------------------------------===// 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// This file implements the Jump Threading pass. 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com//===----------------------------------------------------------------------===// 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define DEBUG_TYPE "jump-threading" 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Transforms/Scalar.h" 165c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com#include "llvm/IntrinsicInst.h" 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/LLVMContext.h" 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Pass.h" 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Analysis/InstructionSimplify.h" 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Analysis/LazyValueInfo.h" 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Analysis/Loads.h" 22845fdaca174f4675e9acc164b510e3a5ffa9053creed@android.com#include "llvm/Transforms/Utils/BasicBlockUtils.h" 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Transforms/Utils/Local.h" 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Transforms/Utils/SSAUpdater.h" 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Target/TargetData.h" 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/ADT/DenseMap.h" 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/ADT/DenseSet.h" 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/ADT/Statistic.h" 2997af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com#include "llvm/ADT/STLExtras.h" 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/ADT/SmallPtrSet.h" 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/ADT/SmallSet.h" 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Support/CommandLine.h" 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Support/Debug.h" 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Support/ValueHandle.h" 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "llvm/Support/raw_ostream.h" 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comusing namespace llvm; 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSTATISTIC(NumThreads, "Number of jumps threaded"); 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSTATISTIC(NumFolds, "Number of terminators folded"); 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSTATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi"); 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic cl::opt<unsigned> 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comThreshold("jump-threading-threshold", 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com cl::desc("Max block size to duplicate for jump threading"), 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com cl::init(6), cl::Hidden); 467ffb1b21abcc7bbed5a0fc711f6dd7b9dbb4f577ctguil@chromium.org 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comnamespace { 4815e9d3e66e161ce23df30bc13f8a0c87d196b463robertphillips@google.com /// This pass performs 'jump threading', which looks at blocks that have 4915e9d3e66e161ce23df30bc13f8a0c87d196b463robertphillips@google.com /// multiple predecessors and multiple successors. If one or more of the 50cde92111d50a96b6d0f3e166fbac7c9bc6eca349reed@google.com /// predecessors of the block can be proven to always jump to one of the 518d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org /// successors, we forward the edge from the predecessor to the successor by 526dc745506e6d6cc0936fed4de24443dc1ecb5a34reed@google.com /// duplicating the contents of this block. 53e97f0856a8044866b12527819d14cdfbcdfd96f2bsalomon@google.com /// 548d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org /// An example of when this can occur is code like this: 558d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org /// 568d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org /// if () { ... 578d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org /// X = 4; 588d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org /// } 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// if (X < 3) { 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// In this case, the unconditional branch at the end of the first if can be 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// revectored to the false side of the second if. 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com class JumpThreading : public FunctionPass { 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com TargetData *TD; 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LazyValueInfo *LVI; 67210ce003a5ec039dda80de0569fb47ca4efc4dc7reed@google.com#ifdef NDEBUG 68bf6c1e4aff4d233f6502157fb73459cf69d0ab37junov@chromium.org SmallPtrSet<BasicBlock*, 16> LoopHeaders; 69bf6c1e4aff4d233f6502157fb73459cf69d0ab37junov@chromium.org#else 70bf6c1e4aff4d233f6502157fb73459cf69d0ab37junov@chromium.org SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders; 71bf6c1e4aff4d233f6502157fb73459cf69d0ab37junov@chromium.org#endif 72bf6c1e4aff4d233f6502157fb73459cf69d0ab37junov@chromium.org DenseSet<std::pair<Value*, BasicBlock*> > RecursionSet; 73210ce003a5ec039dda80de0569fb47ca4efc4dc7reed@google.com 74210ce003a5ec039dda80de0569fb47ca4efc4dc7reed@google.com // RAII helper for updating the recursion stack. 75210ce003a5ec039dda80de0569fb47ca4efc4dc7reed@google.com struct RecursionSetRemover { 76210ce003a5ec039dda80de0569fb47ca4efc4dc7reed@google.com DenseSet<std::pair<Value*, BasicBlock*> > &TheSet; 77210ce003a5ec039dda80de0569fb47ca4efc4dc7reed@google.com std::pair<Value*, BasicBlock*> ThePair; 78210ce003a5ec039dda80de0569fb47ca4efc4dc7reed@google.com 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com RecursionSetRemover(DenseSet<std::pair<Value*, BasicBlock*> > &S, 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com std::pair<Value*, BasicBlock*> P) 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com : TheSet(S), ThePair(P) { } 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ~RecursionSetRemover() { 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com TheSet.erase(ThePair); 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com public: 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static char ID; // Pass identification 894370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.com JumpThreading() : FunctionPass(ID) {} 908d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org 919266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com bool runOnFunction(Function &F); 929266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com 939266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com virtual void getAnalysisUsage(AnalysisUsage &AU) const { 949266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com AU.addRequired<LazyValueInfo>(); 959266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com AU.addPreserved<LazyValueInfo>(); 969266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com } 970b53d59a24f667350b4282f88470713902409030reed@google.com 980b53d59a24f667350b4282f88470713902409030reed@google.com void FindLoopHeaders(Function &F); 990b53d59a24f667350b4282f88470713902409030reed@google.com bool ProcessBlock(BasicBlock *BB); 1000b53d59a24f667350b4282f88470713902409030reed@google.com bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock*> &PredBBs, 1010b53d59a24f667350b4282f88470713902409030reed@google.com BasicBlock *SuccBB); 1020b53d59a24f667350b4282f88470713902409030reed@google.com bool DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, 1039266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com const SmallVectorImpl<BasicBlock *> &PredBBs); 1040b53d59a24f667350b4282f88470713902409030reed@google.com 1059266fed56a46a4edc710a52c7be8d46fd7c2bc7areed@google.com typedef SmallVectorImpl<std::pair<ConstantInt*, 106f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com BasicBlock*> > PredValueInfo; 107f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com 108f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, 109f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com PredValueInfo &Result); 110af951c9bc4cbb6e60b430194fe5127ebe99c53fbreed@google.com bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB); 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11251df9e3fe3c1aec370854b2718df16fc02faa1b2reed@google.com 113cde92111d50a96b6d0f3e166fbac7c9bc6eca349reed@google.com bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB); 114cde92111d50a96b6d0f3e166fbac7c9bc6eca349reed@google.com bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB); 115e97f0856a8044866b12527819d14cdfbcdfd96f2bsalomon@google.com 11674b461961607fa57a150a9282c410ef0cab38764vandebo@chromium.org bool ProcessBranchOnPHI(PHINode *PN); 117e97f0856a8044866b12527819d14cdfbcdfd96f2bsalomon@google.com bool ProcessBranchOnXOR(BinaryOperator *BO); 118e97f0856a8044866b12527819d14cdfbcdfd96f2bsalomon@google.com 119e97f0856a8044866b12527819d14cdfbcdfd96f2bsalomon@google.com bool SimplifyPartiallyRedundantLoad(LoadInst *LI); 1204b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com }; 1214b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com} 122daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com 123d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.comchar JumpThreading::ID = 0; 124d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.comINITIALIZE_PASS(JumpThreading, "jump-threading", 125d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com "Jump Threading", false, false) 126d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com 127d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com// Public interface to the Jump Threading pass 128d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.comFunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); } 129d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com 130d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com/// runOnFunction - Top level algorithm. 131d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com/// 132d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.combool JumpThreading::runOnFunction(Function &F) { 1336850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n"); 1346850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com TD = getAnalysisIfAvailable<TargetData>(); 1356850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com LVI = &getAnalysis<LazyValueInfo>(); 1366850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com 1376850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com FindLoopHeaders(F); 1386850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com 1396850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com bool Changed, EverChanged = false; 1406850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com do { 1416850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com Changed = false; 1426850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com for (Function::iterator I = F.begin(), E = F.end(); I != E;) { 1436850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com BasicBlock *BB = I; 1446850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // Thread all of the branches we can over this block. 1456850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com while (ProcessBlock(BB)) 1466850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com Changed = true; 1476850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com 1486850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com ++I; 1496850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com 1506850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // If the block is trivially dead, zap it. This eliminates the successor 1516850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // edges which simplifies the CFG. 1526850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com if (pred_begin(BB) == pred_end(BB) && 1536850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com BB != &BB->getParent()->getEntryBlock()) { 1541f90287df3129cb267422e482c52ebeca6a8990ftomhudson@google.com DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName() 1556850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com << "' with terminator: " << *BB->getTerminator() << '\n'); 1566850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com LoopHeaders.erase(BB); 1576850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com LVI->eraseBlock(BB); 158daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com DeleteDeadBlock(BB); 159daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com Changed = true; 160daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 161daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com // Can't thread an unconditional jump, but if the block is "almost 1626850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // empty", we can replace uses of it with uses of the successor and make 1636850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // this dead. 1646850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com if (BI->isUnconditional() && 1656850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com BB != &BB->getParent()->getEntryBlock()) { 1666850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com BasicBlock::iterator BBI = BB->getFirstNonPHI(); 167daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com // Ignore dbg intrinsics. 168daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com while (isa<DbgInfoIntrinsic>(BBI)) 16974b461961607fa57a150a9282c410ef0cab38764vandebo@chromium.org ++BBI; 170daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com // If the terminator is the only non-phi instruction, try to nuke it. 171daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com if (BBI->isTerminator()) { 172daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com // Since TryToSimplifyUncondBranchFromEmptyBlock may delete the 173daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com // block, we have to make sure it isn't in the LoopHeaders set. We 174daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com // reinsert afterward if needed. 175daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com bool ErasedFromLoopHeaders = LoopHeaders.erase(BB); 176daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com BasicBlock *Succ = BI->getSuccessor(0); 177daba14b7d4fc96b915c45d82713b22729c0d0f37bsalomon@google.com 1786850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // FIXME: It is always conservatively correct to drop the info 1796850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // for a block even if it doesn't get erased. This isn't totally 1806850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // awesome, but it allows us to use AssertingVH to prevent nasty 1816850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // dangling pointer issues within LazyValueInfo. 1826850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com LVI->eraseBlock(BB); 1836850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) { 1846850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com Changed = true; 1856850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // If we deleted BB and BB was the header of a loop, then the 1866850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com // successor is now the header of the loop. 1876850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com BB = Succ; 1886850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com } 1896850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com 1906850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com if (ErasedFromLoopHeaders) 1916850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com LoopHeaders.insert(BB); 192c69809745e6496564639e42ef998ad39adf7dfb8bsalomon@google.com } 1936850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com } 1946850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com } 1956850eab42ba4c2a7033a99824b02a2846ce0ef2absalomon@google.com } 196c69809745e6496564639e42ef998ad39adf7dfb8bsalomon@google.com EverChanged |= Changed; 1974b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com } while (Changed); 198c69809745e6496564639e42ef998ad39adf7dfb8bsalomon@google.com 199c69809745e6496564639e42ef998ad39adf7dfb8bsalomon@google.com LoopHeaders.clear(); 200c69809745e6496564639e42ef998ad39adf7dfb8bsalomon@google.com return EverChanged; 201c69809745e6496564639e42ef998ad39adf7dfb8bsalomon@google.com} 20251df9e3fe3c1aec370854b2718df16fc02faa1b2reed@google.com 20351df9e3fe3c1aec370854b2718df16fc02faa1b2reed@google.com/// getJumpThreadDuplicationCost - Return the cost of duplicating this block to 20451df9e3fe3c1aec370854b2718df16fc02faa1b2reed@google.com/// thread across it. 20551df9e3fe3c1aec370854b2718df16fc02faa1b2reed@google.comstatic unsigned getJumpThreadDuplicationCost(const BasicBlock *BB) { 20651df9e3fe3c1aec370854b2718df16fc02faa1b2reed@google.com /// Ignore PHI nodes, these will be flattened when duplication happens. 207d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com BasicBlock::const_iterator I = BB->getFirstNonPHI(); 208d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com 209d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com // FIXME: THREADING will delete values that are just used to compute the 210d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com // branch, so they shouldn't count against the duplication cost. 211d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com 212d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com 213d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com // Sum up the cost of each instruction until we get to the terminator. Don't 214d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com // include the terminator because the copy won't include it. 215d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com unsigned Size = 0; 2164f1151ab27485aff393d16559086c4c461f137a4epoger@google.com for (; !isa<TerminatorInst>(I); ++I) { 2174f1151ab27485aff393d16559086c4c461f137a4epoger@google.com // Debugger intrinsics don't incur code size. 2184f1151ab27485aff393d16559086c4c461f137a4epoger@google.com if (isa<DbgInfoIntrinsic>(I)) continue; 21951df9e3fe3c1aec370854b2718df16fc02faa1b2reed@google.com 220d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com // If this is a pointer->pointer bitcast, it is free. 221d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com if (isa<BitCastInst>(I) && I->getType()->isPointerTy()) 222d58a1cd00b969a7755c375f55cf80f4d49d3047bbsalomon@google.com continue; 2234b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // All other instructions count for at least one unit. 2258d84fac294682647694b0d2d8a87ac2bd19b6aabvandebo@chromium.org ++Size; 2268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Calls are more expensive. If they are non-intrinsic calls, we model them 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // as having cost of 4. If they are a non-vector intrinsic, we model them 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // as having cost of 2 total, and if they are a vector intrinsic, we model 2308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // them as having cost 1. 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (const CallInst *CI = dyn_cast<CallInst>(I)) { 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!isa<IntrinsicInst>(CI)) 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Size += 3; 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (!CI->getType()->isVectorTy()) 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Size += 1; 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Threading through a switch statement is particularly profitable. If this 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // block ends in a switch, decrease its cost to make it more likely to happen. 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isa<SwitchInst>(I)) 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Size = Size > 6 ? Size-6 : 0; 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 244dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com return Size; 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 246dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com 247dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com/// FindLoopHeaders - We do not want jump threading to turn proper loop 248dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com/// structures into irreducible loops. Doing this breaks up the loop nesting 249dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com/// hierarchy and pessimizes later transformations. To prevent this from 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// happening, we first have to find the loop headers. Here we approximate this 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// by finding targets of backedges in the CFG. 2528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// Note that there definitely are cases when we want to allow threading of 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// edges across a loop header. For example, threading a jump from outside the 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// loop (the preheader) to an exit block of the loop is definitely profitable. 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// It is also almost always profitable to thread backedges from within the loop 257dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com/// to exit blocks, and is often profitable to thread backedges to other blocks 258ad164b2025cba65131ca68221a6ea7640d7b1de8reed@android.com/// within the loop (forming a nested loop). This simple analysis is not rich 259ad164b2025cba65131ca68221a6ea7640d7b1de8reed@android.com/// enough to track all of these properties and keep it up-to-date as the CFG 260ad164b2025cba65131ca68221a6ea7640d7b1de8reed@android.com/// mutates, so we don't allow any of these transformations. 261ad164b2025cba65131ca68221a6ea7640d7b1de8reed@android.com/// 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid JumpThreading::FindLoopHeaders(Function &F) { 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com FindFunctionBackedges(F, Edges); 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 0, e = Edges.size(); i != e; ++i) 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LoopHeaders.insert(const_cast<BasicBlock*>(Edges[i].second)); 2688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Helper method for ComputeValueKnownInPredecessors. If Value is a 2718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// ConstantInt, push it. If it's an undef, push 0. Otherwise, do nothing. 2728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void PushConstantIntOrUndef(SmallVectorImpl<std::pair<ConstantInt*, 273dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com BasicBlock*> > &Result, 27440408614655c4057d93842c9b0f09aa6dfff9e02reed@android.com Constant *Value, BasicBlock* BB){ 27540408614655c4057d93842c9b0f09aa6dfff9e02reed@android.com if (ConstantInt *FoldedCInt = dyn_cast<ConstantInt>(Value)) 27640408614655c4057d93842c9b0f09aa6dfff9e02reed@android.com Result.push_back(std::make_pair(FoldedCInt, BB)); 27740408614655c4057d93842c9b0f09aa6dfff9e02reed@android.com else if (isa<UndefValue>(Value)) 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.push_back(std::make_pair((ConstantInt*)0, BB)); 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// if we can infer that the value is a known ConstantInt in any of our 2838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// predecessors. If so, return the known list of value and pred BB in the 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// result vector. If a value is known to be undef, it is returned as null. 2858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// 286dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com/// This returns true if there were any known values. 287dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com/// 288dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.combool JumpThreading:: 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ 2908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // This method walks up use-def chains recursively. Because of this, we could 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // get into an infinite loop going around loops in the use-def chain. To 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // prevent this, keep track of what (value, block) pairs we've already visited 2938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // and terminate the search if we loop back to them 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!RecursionSet.insert(std::make_pair(V, BB)).second) 295a907ac3e3e3458fbb5d673c3feafb31fd7647b38junov@chromium.org return false; 2968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // An RAII help to remove this pair from the recursion set once the recursion 2988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // stack pops back out again. 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB)); 3008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If V is a constantint, then it is known in all predecessors. 3028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isa<ConstantInt>(V) || isa<UndefValue>(V)) { 3038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ConstantInt *CI = dyn_cast<ConstantInt>(V); 3047c2029367cea5479fa3b74fb0ca2b0297b42b709reed@google.com 3057c2029367cea5479fa3b74fb0ca2b0297b42b709reed@google.com for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 3067c2029367cea5479fa3b74fb0ca2b0297b42b709reed@google.com Result.push_back(std::make_pair(CI, *PI)); 3078f9ecbd3466d4330886b4c23b06e75b468c795adjunov@chromium.org 3087c2029367cea5479fa3b74fb0ca2b0297b42b709reed@google.com return true; 3098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If V is a non-instruction value, or an instruction in a different block, 3128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // then it can't be derived from a PHI. 3138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Instruction *I = dyn_cast<Instruction>(V); 3148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (I == 0 || I->getParent() != BB) { 3158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Okay, if this is a live-in value, see if it has a known value at the end 3178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // of any of our predecessors. 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // FIXME: This should be an edge property, not a block end property. 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// TODO: Per PR2563, we could infer value range information about a 3218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// predecessor based on its terminator. 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // "I" is a non-local compare-with-a-constant instruction. This would be 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // able to handle value inequalities better, for example if the compare is 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // "X < 4" and "X < 3" is known true but "X < 4" itself is not available. 3278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Perhaps getConstantOnEdge should be smart enough to do this? 3288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 3308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *P = *PI; 3318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If the value is known by LazyValueInfo to be a constant in a 3328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // predecessor, use that information to try to thread this block. 3338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *PredCst = LVI->getConstantOnEdge(V, P, BB); 3348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PredCst == 0 || 3358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (!isa<ConstantInt>(PredCst) && !isa<UndefValue>(PredCst))) 3368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com continue; 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.push_back(std::make_pair(dyn_cast<ConstantInt>(PredCst), P)); 3398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3414b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com return !Result.empty(); 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com /// If I is a PHI node, then we know the incoming values for any constants. 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PHINode *PN = dyn_cast<PHINode>(I)) { 3464b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *InVal = PN->getIncomingValue(i); 3488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isa<ConstantInt>(InVal) || isa<UndefValue>(InVal)) { 3498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ConstantInt *CI = dyn_cast<ConstantInt>(InVal); 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.push_back(std::make_pair(CI, PN->getIncomingBlock(i))); 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *CI = LVI->getConstantOnEdge(InVal, 3538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PN->getIncomingBlock(i), BB); 3548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // LVI returns null is no value could be determined. 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!CI) continue; 3568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PushConstantIntOrUndef(Result, CI, PN->getIncomingBlock(i)); 357071eef918d70b6ca8334bc1241d1ea6923e828d5reed@google.com } 358071eef918d70b6ca8334bc1241d1ea6923e828d5reed@google.com } 3598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return !Result.empty(); 3618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> LHSVals, RHSVals; 3648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Handle some boolean conditions. 366071eef918d70b6ca8334bc1241d1ea6923e828d5reed@google.com if (I->getType()->getPrimitiveSizeInBits() == 1) { 367071eef918d70b6ca8334bc1241d1ea6923e828d5reed@google.com // X | true -> true 3688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // X & false -> false 3698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (I->getOpcode() == Instruction::Or || 3708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com I->getOpcode() == Instruction::And) { 3718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals); 3728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals); 3738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (LHSVals.empty() && RHSVals.empty()) 3758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 3768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ConstantInt *InterestingVal; 3788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (I->getOpcode() == Instruction::Or) 3798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com InterestingVal = ConstantInt::getTrue(I->getContext()); 3808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 3818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com InterestingVal = ConstantInt::getFalse(I->getContext()); 3828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SmallPtrSet<BasicBlock*, 4> LHSKnownBBs; 3848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Scan for the sentinel. If we find an undef, force it to the 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // interesting value: x|undef -> true and x&undef -> false. 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (LHSVals[i].first == InterestingVal || LHSVals[i].first == 0) { 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.push_back(LHSVals[i]); 3908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.back().first = InterestingVal; 3918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LHSKnownBBs.insert(LHSVals[i].second); 3928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 0, e = RHSVals.size(); i != e; ++i) 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (RHSVals[i].first == InterestingVal || RHSVals[i].first == 0) { 3958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If we already inferred a value for this block on the LHS, don't 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // re-add it. 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!LHSKnownBBs.count(RHSVals[i].second)) { 3983b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com Result.push_back(RHSVals[i]); 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.back().first = InterestingVal; 4008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return !Result.empty(); 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Handle the NOT form of XOR. 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (I->getOpcode() == Instruction::Xor && 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com isa<ConstantInt>(I->getOperand(1)) && 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com cast<ConstantInt>(I->getOperand(1))->isOne()) { 4103b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result); 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (Result.empty()) 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 4138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Invert the known values. 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 0, e = Result.size(); i != e; ++i) 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (Result[i].first) 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result[i].first = 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com cast<ConstantInt>(ConstantExpr::getNot(Result[i].first)); 4198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4223b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com 42392d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com // Try to simplify some other binary operator values. 4243b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) { 42592d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) { 42692d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> LHSVals; 42792d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals); 42892d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com 42992d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com // Try to use constant folding to simplify the binary operator. 43092d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { 43192d2a299d2738e4369508ea1296981a2f1f8aadbdjsollen@google.com Constant *V = LHSVals[i].first; 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (V == 0) V = UndefValue::get(BO->getType()); 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *Folded = ConstantExpr::get(BO->getOpcode(), V, CI); 4348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PushConstantIntOrUndef(Result, Folded, LHSVals[i].second); 4368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4383b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com 4398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return !Result.empty(); 440bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com } 441bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com 442bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com // Handle compare with phi operand, where the PHI is defined in this block. 443bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) { 444bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com PHINode *PN = dyn_cast<PHINode>(Cmp->getOperand(0)); 44574b461961607fa57a150a9282c410ef0cab38764vandebo@chromium.org if (PN && PN->getParent() == BB) { 446bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com // We can do this simplification if any comparisons fold to true or false. 4478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // See if any do. 448845fdaca174f4675e9acc164b510e3a5ffa9053creed@android.com for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 4498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *PredBB = PN->getIncomingBlock(i); 4508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *LHS = PN->getIncomingValue(i); 4518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *RHS = Cmp->getOperand(1)->DoPHITranslation(BB, PredBB); 4528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *Res = SimplifyCmpInst(Cmp->getPredicate(), LHS, RHS, TD); 4548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (Res == 0) { 4558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!isa<Constant>(RHS)) 456845fdaca174f4675e9acc164b510e3a5ffa9053creed@android.com continue; 4578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LazyValueInfo::Tristate 459845fdaca174f4675e9acc164b510e3a5ffa9053creed@android.com ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS, 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com cast<Constant>(RHS), PredBB, BB); 4618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (ResT == LazyValueInfo::Unknown) 4628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com continue; 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT); 464845fdaca174f4675e9acc164b510e3a5ffa9053creed@android.com } 4658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4662a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com if (Constant *ConstRes = dyn_cast<Constant>(Res)) 4672a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com PushConstantIntOrUndef(Result, ConstRes, PredBB); 4682a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com } 4692a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com 4702a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com return !Result.empty(); 4712a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com } 4722a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com 4732a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com 4742a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com // If comparing a live-in value against a constant, see if we know the 4752a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com // live-in value on any predecessors. 4762a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com if (isa<Constant>(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) { 4772a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com if (!isa<Instruction>(Cmp->getOperand(0)) || 4782a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com cast<Instruction>(Cmp->getOperand(0))->getParent() != BB) { 4792a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com Constant *RHSCst = cast<Constant>(Cmp->getOperand(1)); 4802a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com 4812a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com for (pred_iterator PI = pred_begin(BB), E = pred_end(BB);PI != E; ++PI){ 4822a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com BasicBlock *P = *PI; 4832a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com // If the value is known by LazyValueInfo to be a constant in a 4842a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com // predecessor, use that information to try to thread this block. 4852a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com LazyValueInfo::Tristate Res = 4862a98181f048c11f21f52fbd99f803f5fd6118261reed@google.com LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0), 4878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com RHSCst, P, BB); 4888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (Res == LazyValueInfo::Unknown) 4898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com continue; 4908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *ResC = ConstantInt::get(Cmp->getType(), Res); 4928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.push_back(std::make_pair(cast<ConstantInt>(ResC), P)); 4938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return !Result.empty(); 4968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Try to find a constant value for the LHS of a comparison, 4998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // and evaluate it statically if we can. 5008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (Constant *CmpConst = dyn_cast<Constant>(Cmp->getOperand(1))) { 5018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> LHSVals; 5028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals); 5038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { 5058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *V = LHSVals[i].first; 5068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (V == 0) V = UndefValue::get(CmpConst->getType()); 5078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *Folded = ConstantExpr::getCompare(Cmp->getPredicate(), 5088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com V, CmpConst); 5098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PushConstantIntOrUndef(Result, Folded, LHSVals[i].second); 5108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return !Result.empty(); 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If all else fails, see if LVI can figure out a constant value for us. 5188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *CI = LVI->getConstant(V, BB); 5198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ConstantInt *CInt = dyn_cast_or_null<ConstantInt>(CI); 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (CInt) { 5218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 5228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Result.push_back(std::make_pair(CInt, *PI)); 5238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return !Result.empty(); 5264b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com} 5278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// GetBestDestForBranchOnUndef - If we determine that the specified block ends 5318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// in an undefined jump, decide which block is best to revector to. 5328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// 5338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// Since we can pick an arbitrary destination, we pick the successor with the 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// fewest predecessors. This should reduce the in-degree of the others. 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// 5368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic unsigned GetBestDestForJumpOnUndef(BasicBlock *BB) { 5378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com TerminatorInst *BBTerm = BB->getTerminator(); 5388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned MinSucc = 0; 5398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc); 5408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Compute the successor with the minimum number of predecessors. 5418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 5428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) { 5438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com TestBB = BBTerm->getSuccessor(i); 5448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 5458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (NumPreds < MinNumPreds) 5468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com MinSucc = i; 5478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return MinSucc; 5508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 5518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// ProcessBlock - If there are any predecessors whose control can be threaded 5538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// through to a successor, transform them now. 5548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool JumpThreading::ProcessBlock(BasicBlock *BB) { 5558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If the block is trivially dead, just return and let the caller nuke it. 5568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // This simplifies other transformations. 5578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (pred_begin(BB) == pred_end(BB) && 5588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BB != &BB->getParent()->getEntryBlock()) 5598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 5608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If this block has a single predecessor, and if that pred has a single 5628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // successor, merge the blocks. This encourages recursive jump threading 5638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // because now the condition in this block can be threaded through 5644b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com // predecessors of our predecessor block. 5658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (BasicBlock *SinglePred = BB->getSinglePredecessor()) { 5668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SinglePred->getTerminator()->getNumSuccessors() == 1 && 5678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SinglePred != BB) { 5688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If SinglePred was a loop header, BB becomes one. 5698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (LoopHeaders.erase(SinglePred)) 5708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LoopHeaders.insert(BB); 5718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Remember if SinglePred was the entry block of the function. If so, we 5738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // will need to move BB back to the entry position. 5748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 5758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LVI->eraseBlock(SinglePred); 5768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com MergeBasicBlockIntoOnlyPred(BB); 5778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isEntry && BB != &BB->getParent()->getEntryBlock()) 5798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BB->moveBefore(&BB->getParent()->getEntryBlock()); 5808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Look to see if the terminator is a branch of switch, if not we can't thread 5858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // it. 5868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *Condition; 5878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 5888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Can't thread an unconditional jump. 5898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (BI->isUnconditional()) return false; 5908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Condition = BI->getCondition(); 5918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) 5928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Condition = SI->getCondition(); 5938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 5948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; // Must be an invoke. 5958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If the terminator of this block is branching on a constant, simplify the 5978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // terminator to an unconditional branch. This can occur due to threading in 5988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // other blocks. 5998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isa<ConstantInt>(Condition)) { 6008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com DEBUG(dbgs() << " In block '" << BB->getName() 6018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com << "' folding terminator: " << *BB->getTerminator() << '\n'); 6028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ++NumFolds; 6038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ConstantFoldTerminator(BB); 6048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 6058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If the terminator is branching on an undef, we can pick any of the 6088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // successors to branch to. Let GetBestDestForJumpOnUndef decide. 6098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isa<UndefValue>(Condition)) { 6108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned BestSucc = GetBestDestForJumpOnUndef(BB); 6118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Fold the branch/switch. 6138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com TerminatorInst *BBTerm = BB->getTerminator(); 6148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) { 6158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (i == BestSucc) continue; 6168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BBTerm->getSuccessor(i)->removePredecessor(BB, true); 6178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com DEBUG(dbgs() << " In block '" << BB->getName() 6208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com << "' folding undef terminator: " << *BBTerm << '\n'); 6218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm); 6228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BBTerm->eraseFromParent(); 6238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 6248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Instruction *CondInst = dyn_cast<Instruction>(Condition); 6278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // All the rest of our checks depend on the condition being an instruction. 6298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (CondInst == 0) { 6308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // FIXME: Unify this with code below. 6318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (ProcessThreadableEdges(Condition, BB)) 6328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 6338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 6348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) { 6388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // For a comparison where the LHS is outside this block, it's possible 6398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // that we've branched on it before. Used LVI to see if we can simplify 6408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // the branch based on that. 6418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); 6428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1)); 6438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 6448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (CondBr && CondConst && CondBr->isConditional() && PI != PE && 6458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (!isa<Instruction>(CondCmp->getOperand(0)) || 6468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com cast<Instruction>(CondCmp->getOperand(0))->getParent() != BB)) { 6478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // For predecessor edge, determine if the comparison is true or false 6488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // on that edge. If they're all true or all false, we can simplify the 6498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // branch. 6508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // FIXME: We could handle mixed true/false by duplicating code. 6518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LazyValueInfo::Tristate Baseline = 6524b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com LVI->getPredicateOnEdge(CondCmp->getPredicate(), CondCmp->getOperand(0), 653f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com CondConst, *PI, BB); 654f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com if (Baseline != LazyValueInfo::Unknown) { 655f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com // Check that all remaining incoming values match the first one. 656f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com while (++PI != PE) { 657f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com LazyValueInfo::Tristate Ret = 658f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com LVI->getPredicateOnEdge(CondCmp->getPredicate(), 659f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com CondCmp->getOperand(0), CondConst, *PI, BB); 660f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com if (Ret != Baseline) break; 661f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com } 662f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com 663f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com // If we terminated early, then one of the values didn't match. 664f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com if (PI == PE) { 665f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com unsigned ToRemove = Baseline == LazyValueInfo::True ? 1 : 0; 666f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com unsigned ToKeep = Baseline == LazyValueInfo::True ? 0 : 1; 667f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true); 668f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr); 669f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com CondBr->eraseFromParent(); 6708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 6718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 6758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Check for some cases that are worth simplifying. Right now we want to look 6778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // for loads that are used by a switch or by the condition for the branch. If 6788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we see one, check to see if it's partially redundant. If so, insert a PHI 6798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // which can then be used to thread the values. 6808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // 6818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *SimplifyValue = CondInst; 6828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue)) 6838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isa<Constant>(CondCmp->getOperand(1))) 6848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SimplifyValue = CondCmp->getOperand(0); 6858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // TODO: There are other places where load PRE would be profitable, such as 6878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // more complex comparisons. 6888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue)) 6898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (SimplifyPartiallyRedundantLoad(LI)) 6908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 6918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 6938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Handle a variety of cases where we are branching on something derived from 6948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // a PHI node in the current block. If we can prove that any predecessors 6958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // compute a predictable value based on a PHI node, thread those predecessors. 6964b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com // 6978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (ProcessThreadableEdges(CondInst, BB)) 6988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 6998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If this is an otherwise-unfoldable branch on a phi node in the current 7018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // block, see if we can simplify. 7028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PHINode *PN = dyn_cast<PHINode>(CondInst)) 7038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator())) 7044b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com return ProcessBranchOnPHI(PN); 7058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7074b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify. 7088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (CondInst->getOpcode() == Instruction::Xor && 7098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator())) 7108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst)); 7118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // TODO: If we have: "br (X > 0)" and we have a predecessor where we know 7148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // "(X == 4)", thread through this block. 7158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 7174b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com} 7188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// ProcessBranchOnDuplicateCond - We found a block and a predecessor of that 7208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// block that jump on exactly the same condition. This means that we almost 7218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// always know the direction of the edge in the DESTBB: 7228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// PREDBB: 7238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// br COND, DESTBB, BBY 7248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// DESTBB: 7258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// br COND, BBZ, BBW 7268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// 7278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// If DESTBB has multiple predecessors, we can't just constant fold the branch 7288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// in DESTBB, we have to thread over it. 7298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool JumpThreading::ProcessBranchOnDuplicateCond(BasicBlock *PredBB, 7308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *BB) { 7318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BranchInst *PredBI = cast<BranchInst>(PredBB->getTerminator()); 7328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If both successors of PredBB go to DESTBB, we don't know anything. We can 7348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // fold the branch to an unconditional one, which allows other recursive 7358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // simplifications. 7368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool BranchDir; 7378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PredBI->getSuccessor(1) != BB) 7388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BranchDir = true; 7398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (PredBI->getSuccessor(0) != BB) 7408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BranchDir = false; 7418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else { 7428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com DEBUG(dbgs() << " In block '" << PredBB->getName() 7438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com << "' folding terminator: " << *PredBB->getTerminator() << '\n'); 7448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ++NumFolds; 7458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ConstantFoldTerminator(PredBB); 7468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 7478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 74856c69773aea56c6c6bd47bc7e7970dd081205184djsollen@google.com 749cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com BranchInst *DestBI = cast<BranchInst>(BB->getTerminator()); 750cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com 751cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com // If the dest block has one predecessor, just fix the branch condition to a 752cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com // constant and fold it. 753cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com if (BB->getSinglePredecessor()) { 754cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com DEBUG(dbgs() << " In block '" << BB->getName() 755cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com << "' folding condition to '" << BranchDir << "': " 756cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com << *BB->getTerminator() << '\n'); 757cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com ++NumFolds; 758cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com Value *OldCond = DestBI->getCondition(); 759cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com DestBI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 760cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com BranchDir)); 761cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com // Delete dead instructions before we fold the branch. Folding the branch 762cd9d69b9ce7eb301a9fd8d91b9f95fd99b07bae5djsollen@google.com // can eliminate edges from the CFG which can end up deleting OldCond. 7638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com RecursivelyDeleteTriviallyDeadInstructions(OldCond); 7648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ConstantFoldTerminator(BB); 7658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 7668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 7678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Next, figure out which successor we are threading to. 7708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir); 7718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SmallVector<BasicBlock*, 2> Preds; 7734b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com Preds.push_back(PredBB); 7748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Ok, try to thread it! 7768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return ThreadEdge(BB, Preds, SuccBB); 7778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 7788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7794b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com/// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that 7808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// block that switch on exactly the same condition. This means that we almost 7818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// always know the direction of the edge in the DESTBB: 7828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// PREDBB: 7838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// switch COND [... DESTBB, BBY ... ] 7848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// DESTBB: 7858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// switch COND [... BBZ, BBW ] 7868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// 7878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// Optimizing switches like this is very important, because simplifycfg builds 7888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// switches out of repeated 'if' conditions. 7898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool JumpThreading::ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, 7908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *DestBB) { 7918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Can't thread edge to self. 792845fdaca174f4675e9acc164b510e3a5ffa9053creed@android.com if (PredBB == DestBB) 7938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 7948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SwitchInst *PredSI = cast<SwitchInst>(PredBB->getTerminator()); 7964b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com SwitchInst *DestSI = cast<SwitchInst>(DestBB->getTerminator()); 7978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 7988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // There are a variety of optimizations that we can potentially do on these 7998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // blocks: we order them from most to least preferable. 8008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If DESTBB *just* contains the switch, then we can forward edges from PREDBB 8028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // directly to their destination. This does not introduce *any* code size 8038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // growth. Skip debug info first. 804cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com BasicBlock::iterator BBI = DestBB->begin(); 805cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com while (isa<DbgInfoIntrinsic>(BBI)) 806cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com BBI++; 807cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com 808cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com // FIXME: Thread if it just contains a PHI. 809cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com if (isa<SwitchInst>(BBI)) { 810cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com bool MadeChange = false; 811cb60844b34766aad4151df5e87c144d4a57e9abereed@android.com // Ignore the default edge for now. 8128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 1, e = DestSI->getNumSuccessors(); i != e; ++i) { 8134b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com ConstantInt *DestVal = DestSI->getCaseValue(i); 8148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *DestSucc = DestSI->getSuccessor(i); 8158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Okay, DestSI has a case for 'DestVal' that goes to 'DestSucc'. See if 8178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // PredSI has an explicit case for it. If so, forward. If it is covered 8188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // by the default case, we can't update PredSI. 8198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned PredCase = PredSI->findCaseValue(DestVal); 8208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PredCase == 0) continue; 8218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If PredSI doesn't go to DestBB on this value, then it won't reach the 8238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // case on this condition. 8248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PredSI->getSuccessor(PredCase) != DestBB && 8258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com DestSI->getSuccessor(i) != DestBB) 8268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com continue; 8278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Do not forward this if it already goes to this destination, this would 8294b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com // be an infinite loop. 8308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (PredSI->getSuccessor(PredCase) == DestSucc) 831dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com continue; 8328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Otherwise, we're safe to make the change. Make sure that the edge from 8348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // DestSI to DestSucc is not critical and has no PHI nodes. 8354b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com DEBUG(dbgs() << "FORWARDING EDGE " << *DestVal << " FROM: " << *PredSI); 8368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com DEBUG(dbgs() << "THROUGH: " << *DestSI); 8378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If the destination has PHI nodes, just split the edge for updating 839dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com // simplicity. 840dc3381fc8194a6192af39539c6ac9787b20209d3reed@android.com if (isa<PHINode>(DestSucc->begin()) && !DestSucc->getSinglePredecessor()){ 8418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SplitCriticalEdge(DestSI, i, this); 8428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com DestSucc = DestSI->getSuccessor(i); 8438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com FoldSingleEntryPHINodes(DestSucc); 8458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PredSI->setSuccessor(PredCase, DestSucc); 8468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com MadeChange = true; 8478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 8488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 8498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (MadeChange) 8508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 8518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 852a907ac3e3e3458fbb5d673c3feafb31fd7647b38junov@chromium.org 8538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 854bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com} 855bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com 856bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com 857bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com/// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant 858bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com/// load instruction, eliminate it by replacing it with a PHI node. This is an 859bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com/// important optimization that encourages jump threading, and needs to be run 860bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com/// interlaced with other jump threading tasks. 861bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.combool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { 862bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com // Don't hack volatile loads. 863bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com if (LI->isVolatile()) return false; 864bcb671c82a7341253864cda3a5c46d396402d7fbtomhudson@google.com 8658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If the load is defined in a block with exactly one predecessor, it can't be 866a707f6087455834fab5525a0c656cc5b6df2ff29reed@google.com // partially redundant. 867a707f6087455834fab5525a0c656cc5b6df2ff29reed@google.com BasicBlock *LoadBB = LI->getParent(); 8685e2457ef2eba0c3f2e4c8fc89be7f36659e4f3b1reed@google.com if (LoadBB->getSinglePredecessor()) 869a707f6087455834fab5525a0c656cc5b6df2ff29reed@google.com return false; 8705e2457ef2eba0c3f2e4c8fc89be7f36659e4f3b1reed@google.com 871a707f6087455834fab5525a0c656cc5b6df2ff29reed@google.com Value *LoadedPtr = LI->getOperand(0); 8725e2457ef2eba0c3f2e4c8fc89be7f36659e4f3b1reed@google.com 87340a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com // If the loaded operand is defined in the LoadBB, it can't be available. 87440a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com // TODO: Could do simple PHI translation, that would be fun :) 87540a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr)) 87640a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com if (PtrOp->getParent() == LoadBB) 87740a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com return false; 87840a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com 87940a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com // Scan a few instructions up from the load, to see if it is obviously live at 88040a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com // the entry to its block. 88140a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com BasicBlock::iterator BBIt = LI; 88290c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com 88390c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com if (Value *AvailableVal = 88490c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com FindAvailableLoadedValue(LoadedPtr, LoadBB, BBIt, 6)) { 88590c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com // If the value if the load is locally available within the block, just use 88620a550c6ea947f0ab239da1d4ecba209d76a98fdjustinlin@google.com // it. This frequently occurs for reg2mem'd allocas. 88790c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n"; 88890c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com 88990c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com // If the returned value is the load itself, replace with an undef. This can 89090c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com // only happen in dead loops. 8915e2457ef2eba0c3f2e4c8fc89be7f36659e4f3b1reed@google.com if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType()); 89290c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com LI->replaceAllUsesWith(AvailableVal); 89390c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com LI->eraseFromParent(); 89490c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com return true; 8957d7ca79c3e6e6be7b7849b0d9a7fe26effb89c38reed@google.com } 89690c07ea1d0aa6b7f20252c43fe23ee5ddc1d23cbreed@google.com 8978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Otherwise, if we scanned the whole block and got to the top of the block, 8988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // we know the block is locally transparent to the load. If not, something 8998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // might clobber its value. 9008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (BBIt != LoadBB->begin()) 9018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 9028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SmallPtrSet<BasicBlock*, 8> PredsScanned; 9058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy; 9067ffb1b21abcc7bbed5a0fc711f6dd7b9dbb4f577ctguil@chromium.org AvailablePredsTy AvailablePreds; 9078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *OneUnavailablePred = 0; 9088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If we got here, the loaded value is transparent through to the start of the 9108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // block. Check to see if it is available in any of the predecessor blocks. 9114b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB); 9128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PI != PE; ++PI) { 9138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BasicBlock *PredBB = *PI; 9148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If we already scanned this predecessor, skip it. 9164b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com if (!PredsScanned.insert(PredBB)) 9178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com continue; 9188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Scan the predecessor to see if the value is available in the pred. 9208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com BBIt = PredBB->end(); 9218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6); 9228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!PredAvailable) { 9238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com OneUnavailablePred = PredBB; 9248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com continue; 9254b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com } 9268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If so, this load is partially redundant. Remember this info so that we 9288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // can create a PHI node. 9298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable)); 9308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 9318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 932f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com // If the loaded value isn't available in any predecessor, it isn't partially 9338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // redundant. 9348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (AvailablePreds.empty()) return false; 9358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Okay, the loaded value is available in at least one (and maybe all!) 9378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // predecessors. If the value is unavailable in more than one unique 9388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // predecessor, we want to insert a merge block for those common predecessors. 93974b461961607fa57a150a9282c410ef0cab38764vandebo@chromium.org // This ensures that we only have to insert one reload, thus not increasing 9404370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.com // code size. 9414370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.com BasicBlock *UnavailablePred = 0; 9424370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.com 9434370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.com // If there is exactly one predecessor where the value is unavailable, the 9444370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.com // already computed 'OneUnavailablePred' block is it. If it ends in an 9458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // unconditional branch, we know that it isn't a critical edge. 94649794c0cbd934545854a7b4091af5af7dfb46570reed@google.com if (PredsScanned.size() == AvailablePreds.size()+1 && 94749794c0cbd934545854a7b4091af5af7dfb46570reed@google.com OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) { 9484b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com UnavailablePred = OneUnavailablePred; 949a907ac3e3e3458fbb5d673c3feafb31fd7647b38junov@chromium.org } else if (PredsScanned.size() != AvailablePreds.size()) { 950a907ac3e3e3458fbb5d673c3feafb31fd7647b38junov@chromium.org // Otherwise, we had multiple unavailable predecessors or we had a critical 951a907ac3e3e3458fbb5d673c3feafb31fd7647b38junov@chromium.org // edge from the one. 95249794c0cbd934545854a7b4091af5af7dfb46570reed@google.com SmallVector<BasicBlock*, 8> PredsToSplit; 953a907ac3e3e3458fbb5d673c3feafb31fd7647b38junov@chromium.org SmallPtrSet<BasicBlock*, 8> AvailablePredSet; 95497af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com 95597af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com for (unsigned i = 0, e = AvailablePreds.size(); i != e; ++i) 95697af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com AvailablePredSet.insert(AvailablePreds[i].first); 95797af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com 9588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Add all the unavailable predecessors to the PredsToSplit list. 9598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB); 9608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PI != PE; ++PI) { 9615c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com BasicBlock *P = *PI; 9628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If the predecessor is an indirect goto, we can't split the edge. 9638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (isa<IndirectBrInst>(P->getTerminator())) 9648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 9658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!AvailablePredSet.count(P)) 9678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com PredsToSplit.push_back(P); 9688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 969199f108f14a5f60a9c2205ffa79b26102a206ad0reed@android.com 970b0a7ace7cb2a7559bbc254a7c93698bc71bbd245junov@chromium.org // Split them out to their own block. 9718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com UnavailablePred = 97297af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com SplitBlockPredecessors(LoadBB, &PredsToSplit[0], PredsToSplit.size(), 97397af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com "thread-pre-split", this); 97497af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com } 97597af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com 97697af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com // If the value isn't available in all predecessors, then there will be 97797af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com // exactly one where it isn't available. Insert a load on that edge and add 97897af1a64ae6bdddd346d8babfd9f188279dd6644reed@google.com // it to the AvailablePreds list. 97940a1ae4df28810aa5aa5cf2627d8387b2dfb867arobertphillips@google.com if (UnavailablePred) { 9804b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 && 9818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com "Can't handle critical edge here!"); 9828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr", false, 9838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LI->getAlignment(), 9848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com UnavailablePred->getTerminator()); 9858926b169f6a0dfa4c2129a98ec2aee205f0c8527reed@google.com AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal)); 9868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 98774b461961607fa57a150a9282c410ef0cab38764vandebo@chromium.org 988e97f0856a8044866b12527819d14cdfbcdfd96f2bsalomon@google.com // Now we know that each predecessor of this block has a value in 989e97f0856a8044866b12527819d14cdfbcdfd96f2bsalomon@google.com // AvailablePreds, sort them for efficient access as we're walking the preds. 9908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array_pod_sort(AvailablePreds.begin(), AvailablePreds.end()); 991f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com 992f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com // Create a PHI node at the start of the block for the PRE'd load value. 993f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com PHINode *PN = PHINode::Create(LI->getType(), "", LoadBB->begin()); 994f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com PN->takeName(LI); 9958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 996f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com // Insert new entries into the PHI for each predecessor. A single block may 997f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com // have multiple entries here. 998f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); PI != E; 999f0b5e1190af9807a027c0adba2f1380663c8e910reed@google.com ++PI) { 1000fa6ac938e64fe11b442d05fe8a90ddac2d1951f9bsalomon@google.com BasicBlock *P = *PI; 10018926b169f6a0dfa4c2129a98ec2aee205f0c8527reed@google.com AvailablePredsTy::iterator I = 10028926b169f6a0dfa4c2129a98ec2aee205f0c8527reed@google.com std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(), 10038926b169f6a0dfa4c2129a98ec2aee205f0c8527reed@google.com std::make_pair(P, (Value*)0)); 1004fa6ac938e64fe11b442d05fe8a90ddac2d1951f9bsalomon@google.com 10058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com assert(I != AvailablePreds.end() && I->first == P && 10068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com "Didn't find entry for predecessor!"); 10078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 100852c748b1691f02f90b27c35bc05074fcef709e66bungeman@google.com PN->addIncoming(I->second, I->first); 100952c748b1691f02f90b27c35bc05074fcef709e66bungeman@google.com } 101052c748b1691f02f90b27c35bc05074fcef709e66bungeman@google.com 101152c748b1691f02f90b27c35bc05074fcef709e66bungeman@google.com //cerr << "PRE: " << *LI << *PN << "\n"; 101252c748b1691f02f90b27c35bc05074fcef709e66bungeman@google.com 10134b226023832011bc3bcdd1e5092ff0645ad0bdeereed@google.com LI->replaceAllUsesWith(PN); 10148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LI->eraseFromParent(); 10158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 10178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 10188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// FindMostPopularDest - The specified list contains multiple possible 10208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/// threadable destinations. Pick the one that occurs the most frequently in 10213b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com/// the list. 10223b3e895df6f8ee0f33010367c215944cd16a8334reed@google.comstatic BasicBlock * 10233b3e895df6f8ee0f33010367c215944cd16a8334reed@google.comFindMostPopularDest(BasicBlock *BB, 10248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SmallVectorImpl<std::pair<BasicBlock*, 10253b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com BasicBlock*> > &PredToDestList) { 10268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com assert(!PredToDestList.empty()); 10273b3e895df6f8ee0f33010367c215944cd16a8334reed@google.com 1028f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com // Determine popularity. If there are multiple possible destinations, we 1029f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com // explicitly choose to ignore 'undef' destinations. We prefer to thread 1030f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com // blocks with known and real destinations to threading undef. We'll handle 10315c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com // them later if interesting. 10325c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com DenseMap<BasicBlock*, unsigned> DestPopularity; 10335c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com for (unsigned i = 0, e = PredToDestList.size(); i != e; ++i) 10345c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com if (PredToDestList[i].second) 10355c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com DestPopularity[PredToDestList[i].second]++; 10365c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com 10375c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com // Find the most popular dest. 10385c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com DenseMap<BasicBlock*, unsigned>::iterator DPI = DestPopularity.begin(); 10395c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com BasicBlock *MostPopularDest = DPI->first; 10405c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com unsigned Popularity = DPI->second; 10415c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com SmallVector<BasicBlock*, 4> SamePopularity; 10425c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com 10435c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com for (++DPI; DPI != DestPopularity.end(); ++DPI) { 10445c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com // If the popularity of this entry isn't higher than the popularity we've 10455c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com // seen so far, ignore it. 10465c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com if (DPI->second < Popularity) 10475c3d1471e4908706cd053a5e2ea9ded3a6c2eaebreed@google.com ; // ignore. 104815e9d3e66e161ce23df30bc13f8a0c87d196b463robertphillips@google.com else if (DPI->second == Popularity) { 104915e9d3e66e161ce23df30bc13f8a0c87d196b463robertphillips@google.com // If it is the same as what we've seen so far, keep track of it. 10508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SamePopularity.push_back(DPI->first); 10518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 10528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // If it is more popular, remember it. 10538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SamePopularity.clear(); 10548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com MostPopularDest = DPI->first; 10558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Popularity = DPI->second; 10568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 10588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // Okay, now we know the most popular destination. If there is more than 10608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // destination, we need to determine one. This is arbitrary, but we need 10618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // to make a deterministic decision. Pick the first one that appears in the 10628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // successor list. 10638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!SamePopularity.empty()) { 10648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SamePopularity.push_back(MostPopularDest); 10658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com TerminatorInst *TI = BB->getTerminator(); 10668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (unsigned i = 0; ; ++i) { 10678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com assert(i != TI->getNumSuccessors() && "Didn't find any successor!"); 10688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (std::find(SamePopularity.begin(), SamePopularity.end(), 10708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com TI->getSuccessor(i)) == SamePopularity.end()) 10718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com continue; 10728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com MostPopularDest = TI->getSuccessor(i); 10748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 1075 } 1076 } 1077 1078 // Okay, we have finally picked the most popular destination. 1079 return MostPopularDest; 1080} 1081 1082bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB) { 1083 // If threading this would thread across a loop header, don't even try to 1084 // thread the edge. 1085 if (LoopHeaders.count(BB)) 1086 return false; 1087 1088 SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> PredValues; 1089 if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues)) 1090 return false; 1091 1092 assert(!PredValues.empty() && 1093 "ComputeValueKnownInPredecessors returned true with no values"); 1094 1095 DEBUG(dbgs() << "IN BB: " << *BB; 1096 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) { 1097 dbgs() << " BB '" << BB->getName() << "': FOUND condition = "; 1098 if (PredValues[i].first) 1099 dbgs() << *PredValues[i].first; 1100 else 1101 dbgs() << "UNDEF"; 1102 dbgs() << " for pred '" << PredValues[i].second->getName() 1103 << "'.\n"; 1104 }); 1105 1106 // Decide what we want to thread through. Convert our list of known values to 1107 // a list of known destinations for each pred. This also discards duplicate 1108 // predecessors and keeps track of the undefined inputs (which are represented 1109 // as a null dest in the PredToDestList). 1110 SmallPtrSet<BasicBlock*, 16> SeenPreds; 1111 SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList; 1112 1113 BasicBlock *OnlyDest = 0; 1114 BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL; 1115 1116 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) { 1117 BasicBlock *Pred = PredValues[i].second; 1118 if (!SeenPreds.insert(Pred)) 1119 continue; // Duplicate predecessor entry. 1120 1121 // If the predecessor ends with an indirect goto, we can't change its 1122 // destination. 1123 if (isa<IndirectBrInst>(Pred->getTerminator())) 1124 continue; 1125 1126 ConstantInt *Val = PredValues[i].first; 1127 1128 BasicBlock *DestBB; 1129 if (Val == 0) // Undef. 1130 DestBB = 0; 1131 else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) 1132 DestBB = BI->getSuccessor(Val->isZero()); 1133 else { 1134 SwitchInst *SI = cast<SwitchInst>(BB->getTerminator()); 1135 DestBB = SI->getSuccessor(SI->findCaseValue(Val)); 1136 } 1137 1138 // If we have exactly one destination, remember it for efficiency below. 1139 if (i == 0) 1140 OnlyDest = DestBB; 1141 else if (OnlyDest != DestBB) 1142 OnlyDest = MultipleDestSentinel; 1143 1144 PredToDestList.push_back(std::make_pair(Pred, DestBB)); 1145 } 1146 1147 // If all edges were unthreadable, we fail. 1148 if (PredToDestList.empty()) 1149 return false; 1150 1151 // Determine which is the most common successor. If we have many inputs and 1152 // this block is a switch, we want to start by threading the batch that goes 1153 // to the most popular destination first. If we only know about one 1154 // threadable destination (the common case) we can avoid this. 1155 BasicBlock *MostPopularDest = OnlyDest; 1156 1157 if (MostPopularDest == MultipleDestSentinel) 1158 MostPopularDest = FindMostPopularDest(BB, PredToDestList); 1159 1160 // Now that we know what the most popular destination is, factor all 1161 // predecessors that will jump to it into a single predecessor. 1162 SmallVector<BasicBlock*, 16> PredsToFactor; 1163 for (unsigned i = 0, e = PredToDestList.size(); i != e; ++i) 1164 if (PredToDestList[i].second == MostPopularDest) { 1165 BasicBlock *Pred = PredToDestList[i].first; 1166 1167 // This predecessor may be a switch or something else that has multiple 1168 // edges to the block. Factor each of these edges by listing them 1169 // according to # occurrences in PredsToFactor. 1170 TerminatorInst *PredTI = Pred->getTerminator(); 1171 for (unsigned i = 0, e = PredTI->getNumSuccessors(); i != e; ++i) 1172 if (PredTI->getSuccessor(i) == BB) 1173 PredsToFactor.push_back(Pred); 1174 } 1175 1176 // If the threadable edges are branching on an undefined value, we get to pick 1177 // the destination that these predecessors should get to. 1178 if (MostPopularDest == 0) 1179 MostPopularDest = BB->getTerminator()-> 1180 getSuccessor(GetBestDestForJumpOnUndef(BB)); 1181 1182 // Ok, try to thread it! 1183 return ThreadEdge(BB, PredsToFactor, MostPopularDest); 1184} 1185 1186/// ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on 1187/// a PHI node in the current block. See if there are any simplifications we 1188/// can do based on inputs to the phi node. 1189/// 1190bool JumpThreading::ProcessBranchOnPHI(PHINode *PN) { 1191 BasicBlock *BB = PN->getParent(); 1192 1193 // TODO: We could make use of this to do it once for blocks with common PHI 1194 // values. 1195 SmallVector<BasicBlock*, 1> PredBBs; 1196 PredBBs.resize(1); 1197 1198 // If any of the predecessor blocks end in an unconditional branch, we can 1199 // *duplicate* the conditional branch into that block in order to further 1200 // encourage jump threading and to eliminate cases where we have branch on a 1201 // phi of an icmp (branch on icmp is much better). 1202 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1203 BasicBlock *PredBB = PN->getIncomingBlock(i); 1204 if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator())) 1205 if (PredBr->isUnconditional()) { 1206 PredBBs[0] = PredBB; 1207 // Try to duplicate BB into PredBB. 1208 if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs)) 1209 return true; 1210 } 1211 } 1212 1213 return false; 1214} 1215 1216/// ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on 1217/// a xor instruction in the current block. See if there are any 1218/// simplifications we can do based on inputs to the xor. 1219/// 1220bool JumpThreading::ProcessBranchOnXOR(BinaryOperator *BO) { 1221 BasicBlock *BB = BO->getParent(); 1222 1223 // If either the LHS or RHS of the xor is a constant, don't do this 1224 // optimization. 1225 if (isa<ConstantInt>(BO->getOperand(0)) || 1226 isa<ConstantInt>(BO->getOperand(1))) 1227 return false; 1228 1229 // If the first instruction in BB isn't a phi, we won't be able to infer 1230 // anything special about any particular predecessor. 1231 if (!isa<PHINode>(BB->front())) 1232 return false; 1233 1234 // If we have a xor as the branch input to this block, and we know that the 1235 // LHS or RHS of the xor in any predecessor is true/false, then we can clone 1236 // the condition into the predecessor and fix that value to true, saving some 1237 // logical ops on that path and encouraging other paths to simplify. 1238 // 1239 // This copies something like this: 1240 // 1241 // BB: 1242 // %X = phi i1 [1], [%X'] 1243 // %Y = icmp eq i32 %A, %B 1244 // %Z = xor i1 %X, %Y 1245 // br i1 %Z, ... 1246 // 1247 // Into: 1248 // BB': 1249 // %Y = icmp ne i32 %A, %B 1250 // br i1 %Z, ... 1251 1252 SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> XorOpValues; 1253 bool isLHS = true; 1254 if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues)) { 1255 assert(XorOpValues.empty()); 1256 if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues)) 1257 return false; 1258 isLHS = false; 1259 } 1260 1261 assert(!XorOpValues.empty() && 1262 "ComputeValueKnownInPredecessors returned true with no values"); 1263 1264 // Scan the information to see which is most popular: true or false. The 1265 // predecessors can be of the set true, false, or undef. 1266 unsigned NumTrue = 0, NumFalse = 0; 1267 for (unsigned i = 0, e = XorOpValues.size(); i != e; ++i) { 1268 if (!XorOpValues[i].first) continue; // Ignore undefs for the count. 1269 if (XorOpValues[i].first->isZero()) 1270 ++NumFalse; 1271 else 1272 ++NumTrue; 1273 } 1274 1275 // Determine which value to split on, true, false, or undef if neither. 1276 ConstantInt *SplitVal = 0; 1277 if (NumTrue > NumFalse) 1278 SplitVal = ConstantInt::getTrue(BB->getContext()); 1279 else if (NumTrue != 0 || NumFalse != 0) 1280 SplitVal = ConstantInt::getFalse(BB->getContext()); 1281 1282 // Collect all of the blocks that this can be folded into so that we can 1283 // factor this once and clone it once. 1284 SmallVector<BasicBlock*, 8> BlocksToFoldInto; 1285 for (unsigned i = 0, e = XorOpValues.size(); i != e; ++i) { 1286 if (XorOpValues[i].first != SplitVal && XorOpValues[i].first != 0) continue; 1287 1288 BlocksToFoldInto.push_back(XorOpValues[i].second); 1289 } 1290 1291 // If we inferred a value for all of the predecessors, then duplication won't 1292 // help us. However, we can just replace the LHS or RHS with the constant. 1293 if (BlocksToFoldInto.size() == 1294 cast<PHINode>(BB->front()).getNumIncomingValues()) { 1295 if (SplitVal == 0) { 1296 // If all preds provide undef, just nuke the xor, because it is undef too. 1297 BO->replaceAllUsesWith(UndefValue::get(BO->getType())); 1298 BO->eraseFromParent(); 1299 } else if (SplitVal->isZero()) { 1300 // If all preds provide 0, replace the xor with the other input. 1301 BO->replaceAllUsesWith(BO->getOperand(isLHS)); 1302 BO->eraseFromParent(); 1303 } else { 1304 // If all preds provide 1, set the computed value to 1. 1305 BO->setOperand(!isLHS, SplitVal); 1306 } 1307 1308 return true; 1309 } 1310 1311 // Try to duplicate BB into PredBB. 1312 return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto); 1313} 1314 1315 1316/// AddPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new 1317/// predecessor to the PHIBB block. If it has PHI nodes, add entries for 1318/// NewPred using the entries from OldPred (suitably mapped). 1319static void AddPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, 1320 BasicBlock *OldPred, 1321 BasicBlock *NewPred, 1322 DenseMap<Instruction*, Value*> &ValueMap) { 1323 for (BasicBlock::iterator PNI = PHIBB->begin(); 1324 PHINode *PN = dyn_cast<PHINode>(PNI); ++PNI) { 1325 // Ok, we have a PHI node. Figure out what the incoming value was for the 1326 // DestBlock. 1327 Value *IV = PN->getIncomingValueForBlock(OldPred); 1328 1329 // Remap the value if necessary. 1330 if (Instruction *Inst = dyn_cast<Instruction>(IV)) { 1331 DenseMap<Instruction*, Value*>::iterator I = ValueMap.find(Inst); 1332 if (I != ValueMap.end()) 1333 IV = I->second; 1334 } 1335 1336 PN->addIncoming(IV, NewPred); 1337 } 1338} 1339 1340/// ThreadEdge - We have decided that it is safe and profitable to factor the 1341/// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB 1342/// across BB. Transform the IR to reflect this change. 1343bool JumpThreading::ThreadEdge(BasicBlock *BB, 1344 const SmallVectorImpl<BasicBlock*> &PredBBs, 1345 BasicBlock *SuccBB) { 1346 // If threading to the same block as we come from, we would infinite loop. 1347 if (SuccBB == BB) { 1348 DEBUG(dbgs() << " Not threading across BB '" << BB->getName() 1349 << "' - would thread to self!\n"); 1350 return false; 1351 } 1352 1353 // If threading this would thread across a loop header, don't thread the edge. 1354 // See the comments above FindLoopHeaders for justifications and caveats. 1355 if (LoopHeaders.count(BB)) { 1356 DEBUG(dbgs() << " Not threading across loop header BB '" << BB->getName() 1357 << "' to dest BB '" << SuccBB->getName() 1358 << "' - it might create an irreducible loop!\n"); 1359 return false; 1360 } 1361 1362 unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB); 1363 if (JumpThreadCost > Threshold) { 1364 DEBUG(dbgs() << " Not threading BB '" << BB->getName() 1365 << "' - Cost is too high: " << JumpThreadCost << "\n"); 1366 return false; 1367 } 1368 1369 // And finally, do it! Start by factoring the predecessors is needed. 1370 BasicBlock *PredBB; 1371 if (PredBBs.size() == 1) 1372 PredBB = PredBBs[0]; 1373 else { 1374 DEBUG(dbgs() << " Factoring out " << PredBBs.size() 1375 << " common predecessors.\n"); 1376 PredBB = SplitBlockPredecessors(BB, &PredBBs[0], PredBBs.size(), 1377 ".thr_comm", this); 1378 } 1379 1380 // And finally, do it! 1381 DEBUG(dbgs() << " Threading edge from '" << PredBB->getName() << "' to '" 1382 << SuccBB->getName() << "' with cost: " << JumpThreadCost 1383 << ", across block:\n " 1384 << *BB << "\n"); 1385 1386 LVI->threadEdge(PredBB, BB, SuccBB); 1387 1388 // We are going to have to map operands from the original BB block to the new 1389 // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to 1390 // account for entry from PredBB. 1391 DenseMap<Instruction*, Value*> ValueMapping; 1392 1393 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), 1394 BB->getName()+".thread", 1395 BB->getParent(), BB); 1396 NewBB->moveAfter(PredBB); 1397 1398 BasicBlock::iterator BI = BB->begin(); 1399 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 1400 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); 1401 1402 // Clone the non-phi instructions of BB into NewBB, keeping track of the 1403 // mapping and using it to remap operands in the cloned instructions. 1404 for (; !isa<TerminatorInst>(BI); ++BI) { 1405 Instruction *New = BI->clone(); 1406 New->setName(BI->getName()); 1407 NewBB->getInstList().push_back(New); 1408 ValueMapping[BI] = New; 1409 1410 // Remap operands to patch up intra-block references. 1411 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) 1412 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { 1413 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 1414 if (I != ValueMapping.end()) 1415 New->setOperand(i, I->second); 1416 } 1417 } 1418 1419 // We didn't copy the terminator from BB over to NewBB, because there is now 1420 // an unconditional jump to SuccBB. Insert the unconditional jump. 1421 BranchInst::Create(SuccBB, NewBB); 1422 1423 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the 1424 // PHI nodes for NewBB now. 1425 AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping); 1426 1427 // If there were values defined in BB that are used outside the block, then we 1428 // now have to update all uses of the value to use either the original value, 1429 // the cloned value, or some PHI derived value. This can require arbitrary 1430 // PHI insertion, of which we are prepared to do, clean these up now. 1431 SSAUpdater SSAUpdate; 1432 SmallVector<Use*, 16> UsesToRename; 1433 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 1434 // Scan all uses of this instruction to see if it is used outside of its 1435 // block, and if so, record them in UsesToRename. 1436 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 1437 ++UI) { 1438 Instruction *User = cast<Instruction>(*UI); 1439 if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 1440 if (UserPN->getIncomingBlock(UI) == BB) 1441 continue; 1442 } else if (User->getParent() == BB) 1443 continue; 1444 1445 UsesToRename.push_back(&UI.getUse()); 1446 } 1447 1448 // If there are no uses outside the block, we're done with this instruction. 1449 if (UsesToRename.empty()) 1450 continue; 1451 1452 DEBUG(dbgs() << "JT: Renaming non-local uses of: " << *I << "\n"); 1453 1454 // We found a use of I outside of BB. Rename all uses of I that are outside 1455 // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks 1456 // with the two values we know. 1457 SSAUpdate.Initialize(I->getType(), I->getName()); 1458 SSAUpdate.AddAvailableValue(BB, I); 1459 SSAUpdate.AddAvailableValue(NewBB, ValueMapping[I]); 1460 1461 while (!UsesToRename.empty()) 1462 SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); 1463 DEBUG(dbgs() << "\n"); 1464 } 1465 1466 1467 // Ok, NewBB is good to go. Update the terminator of PredBB to jump to 1468 // NewBB instead of BB. This eliminates predecessors from BB, which requires 1469 // us to simplify any PHI nodes in BB. 1470 TerminatorInst *PredTerm = PredBB->getTerminator(); 1471 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) 1472 if (PredTerm->getSuccessor(i) == BB) { 1473 BB->removePredecessor(PredBB, true); 1474 PredTerm->setSuccessor(i, NewBB); 1475 } 1476 1477 // At this point, the IR is fully up to date and consistent. Do a quick scan 1478 // over the new instructions and zap any that are constants or dead. This 1479 // frequently happens because of phi translation. 1480 SimplifyInstructionsInBlock(NewBB, TD); 1481 1482 // Threaded an edge! 1483 ++NumThreads; 1484 return true; 1485} 1486 1487/// DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch 1488/// to BB which contains an i1 PHI node and a conditional branch on that PHI. 1489/// If we can duplicate the contents of BB up into PredBB do so now, this 1490/// improves the odds that the branch will be on an analyzable instruction like 1491/// a compare. 1492bool JumpThreading::DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, 1493 const SmallVectorImpl<BasicBlock *> &PredBBs) { 1494 assert(!PredBBs.empty() && "Can't handle an empty set"); 1495 1496 // If BB is a loop header, then duplicating this block outside the loop would 1497 // cause us to transform this into an irreducible loop, don't do this. 1498 // See the comments above FindLoopHeaders for justifications and caveats. 1499 if (LoopHeaders.count(BB)) { 1500 DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName() 1501 << "' into predecessor block '" << PredBBs[0]->getName() 1502 << "' - it might create an irreducible loop!\n"); 1503 return false; 1504 } 1505 1506 unsigned DuplicationCost = getJumpThreadDuplicationCost(BB); 1507 if (DuplicationCost > Threshold) { 1508 DEBUG(dbgs() << " Not duplicating BB '" << BB->getName() 1509 << "' - Cost is too high: " << DuplicationCost << "\n"); 1510 return false; 1511 } 1512 1513 // And finally, do it! Start by factoring the predecessors is needed. 1514 BasicBlock *PredBB; 1515 if (PredBBs.size() == 1) 1516 PredBB = PredBBs[0]; 1517 else { 1518 DEBUG(dbgs() << " Factoring out " << PredBBs.size() 1519 << " common predecessors.\n"); 1520 PredBB = SplitBlockPredecessors(BB, &PredBBs[0], PredBBs.size(), 1521 ".thr_comm", this); 1522 } 1523 1524 // Okay, we decided to do this! Clone all the instructions in BB onto the end 1525 // of PredBB. 1526 DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '" 1527 << PredBB->getName() << "' to eliminate branch on phi. Cost: " 1528 << DuplicationCost << " block is:" << *BB << "\n"); 1529 1530 // Unless PredBB ends with an unconditional branch, split the edge so that we 1531 // can just clone the bits from BB into the end of the new PredBB. 1532 BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator()); 1533 1534 if (OldPredBranch == 0 || !OldPredBranch->isUnconditional()) { 1535 PredBB = SplitEdge(PredBB, BB, this); 1536 OldPredBranch = cast<BranchInst>(PredBB->getTerminator()); 1537 } 1538 1539 // We are going to have to map operands from the original BB block into the 1540 // PredBB block. Evaluate PHI nodes in BB. 1541 DenseMap<Instruction*, Value*> ValueMapping; 1542 1543 BasicBlock::iterator BI = BB->begin(); 1544 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 1545 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); 1546 1547 // Clone the non-phi instructions of BB into PredBB, keeping track of the 1548 // mapping and using it to remap operands in the cloned instructions. 1549 for (; BI != BB->end(); ++BI) { 1550 Instruction *New = BI->clone(); 1551 1552 // Remap operands to patch up intra-block references. 1553 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) 1554 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { 1555 DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 1556 if (I != ValueMapping.end()) 1557 New->setOperand(i, I->second); 1558 } 1559 1560 // If this instruction can be simplified after the operands are updated, 1561 // just use the simplified value instead. This frequently happens due to 1562 // phi translation. 1563 if (Value *IV = SimplifyInstruction(New, TD)) { 1564 delete New; 1565 ValueMapping[BI] = IV; 1566 } else { 1567 // Otherwise, insert the new instruction into the block. 1568 New->setName(BI->getName()); 1569 PredBB->getInstList().insert(OldPredBranch, New); 1570 ValueMapping[BI] = New; 1571 } 1572 } 1573 1574 // Check to see if the targets of the branch had PHI nodes. If so, we need to 1575 // add entries to the PHI nodes for branch from PredBB now. 1576 BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator()); 1577 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB, 1578 ValueMapping); 1579 AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB, 1580 ValueMapping); 1581 1582 // If there were values defined in BB that are used outside the block, then we 1583 // now have to update all uses of the value to use either the original value, 1584 // the cloned value, or some PHI derived value. This can require arbitrary 1585 // PHI insertion, of which we are prepared to do, clean these up now. 1586 SSAUpdater SSAUpdate; 1587 SmallVector<Use*, 16> UsesToRename; 1588 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 1589 // Scan all uses of this instruction to see if it is used outside of its 1590 // block, and if so, record them in UsesToRename. 1591 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 1592 ++UI) { 1593 Instruction *User = cast<Instruction>(*UI); 1594 if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 1595 if (UserPN->getIncomingBlock(UI) == BB) 1596 continue; 1597 } else if (User->getParent() == BB) 1598 continue; 1599 1600 UsesToRename.push_back(&UI.getUse()); 1601 } 1602 1603 // If there are no uses outside the block, we're done with this instruction. 1604 if (UsesToRename.empty()) 1605 continue; 1606 1607 DEBUG(dbgs() << "JT: Renaming non-local uses of: " << *I << "\n"); 1608 1609 // We found a use of I outside of BB. Rename all uses of I that are outside 1610 // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks 1611 // with the two values we know. 1612 SSAUpdate.Initialize(I->getType(), I->getName()); 1613 SSAUpdate.AddAvailableValue(BB, I); 1614 SSAUpdate.AddAvailableValue(PredBB, ValueMapping[I]); 1615 1616 while (!UsesToRename.empty()) 1617 SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); 1618 DEBUG(dbgs() << "\n"); 1619 } 1620 1621 // PredBB no longer jumps to BB, remove entries in the PHI node for the edge 1622 // that we nuked. 1623 BB->removePredecessor(PredBB, true); 1624 1625 // Remove the unconditional branch at the end of the PredBB block. 1626 OldPredBranch->eraseFromParent(); 1627 1628 ++NumDupes; 1629 return true; 1630} 1631 1632 1633