18383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner//===- JumpThreading.cpp - Thread control through conditional blocks ------===// 28383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// 38383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// The LLVM Compiler Infrastructure 48383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// 58383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// This file is distributed under the University of Illinois Open Source 68383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// License. See LICENSE.TXT for details. 78383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// 88383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner//===----------------------------------------------------------------------===// 98383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// 10177480b7ede0441135572d641a2497df25a7d95fChris Lattner// This file implements the Jump Threading pass. 118383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// 128383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner//===----------------------------------------------------------------------===// 138383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner 148383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner#include "llvm/Transforms/Scalar.h" 15fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#include "llvm/ADT/DenseMap.h" 16cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson#include "llvm/ADT/DenseSet.h" 17fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#include "llvm/ADT/STLExtras.h" 18fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#include "llvm/ADT/SmallPtrSet.h" 19fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#include "llvm/ADT/SmallSet.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2181e480463d8bb57776d03cebfd083762909023f1Nick Lewycky#include "llvm/Analysis/CFG.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ConstantFolding.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/LazyValueInfo.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Loads.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ValueHandle.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 318383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner#include "llvm/Support/CommandLine.h" 32177480b7ede0441135572d641a2497df25a7d95fChris Lattner#include "llvm/Support/Debug.h" 3393b67e40de356569493c285b86b138a3f11b5035Daniel Dunbar#include "llvm/Support/raw_ostream.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLibraryInfo.h" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/BasicBlockUtils.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 37d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/SSAUpdater.h" 388383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattnerusing namespace llvm; 398383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "jump-threading" 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 42bd3401fa98b578080e227afce940bca80137dea6Chris LattnerSTATISTIC(NumThreads, "Number of jumps threaded"); 43bd3401fa98b578080e227afce940bca80137dea6Chris LattnerSTATISTIC(NumFolds, "Number of terminators folded"); 4478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris LattnerSTATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi"); 458383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner 46177480b7ede0441135572d641a2497df25a7d95fChris Lattnerstatic cl::opt<unsigned> 476f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van BommelThreshold("jump-threading-threshold", 48177480b7ede0441135572d641a2497df25a7d95fChris Lattner cl::desc("Max block size to duplicate for jump threading"), 49177480b7ede0441135572d641a2497df25a7d95fChris Lattner cl::init(6), cl::Hidden); 50177480b7ede0441135572d641a2497df25a7d95fChris Lattner 518383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattnernamespace { 52ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel // These are at global scope so static functions can use them too. 53ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel typedef SmallVectorImpl<std::pair<Constant*, BasicBlock*> > PredValueInfo; 54ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel typedef SmallVector<std::pair<Constant*, BasicBlock*>, 8> PredValueInfoTy; 55ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel 566033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel // This is used to keep track of what kind of constant we're currently hoping 576033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel // to find. 586033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel enum ConstantPreference { 596033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger, 606033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantBlockAddress 616033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel }; 626033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel 6394019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// This pass performs 'jump threading', which looks at blocks that have 6494019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// multiple predecessors and multiple successors. If one or more of the 6594019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// predecessors of the block can be proven to always jump to one of the 6694019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// successors, we forward the edge from the predecessor to the successor by 6794019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// duplicating the contents of this block. 6894019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// 6994019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// An example of when this can occur is code like this: 7094019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// 7194019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// if () { ... 7294019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// X = 4; 7394019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// } 7494019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// if (X < 3) { 7594019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// 7694019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// In this case, the unconditional branch at the end of the first if can be 7794019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// revectored to the false side of the second if. 7894019f8e064bf84085b44c35ab0c1efb76fb94f7Chris Lattner /// 793e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class JumpThreading : public FunctionPass { 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL; 81aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier TargetLibraryInfo *TLI; 82cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner LazyValueInfo *LVI; 83fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#ifdef NDEBUG 84fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallPtrSet<BasicBlock*, 16> LoopHeaders; 85fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#else 86fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders; 87fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#endif 88cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson DenseSet<std::pair<Value*, BasicBlock*> > RecursionSet; 896f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 909ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson // RAII helper for updating the recursion stack. 919ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson struct RecursionSetRemover { 929ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson DenseSet<std::pair<Value*, BasicBlock*> > &TheSet; 939ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson std::pair<Value*, BasicBlock*> ThePair; 946f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 959ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson RecursionSetRemover(DenseSet<std::pair<Value*, BasicBlock*> > &S, 969ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson std::pair<Value*, BasicBlock*> P) 979ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson : TheSet(S), ThePair(P) { } 986f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 999ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson ~RecursionSetRemover() { 1009ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson TheSet.erase(ThePair); 1019ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson } 1029ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson }; 1038383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner public: 1048383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner static char ID; // Pass identification 105081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson JumpThreading() : FunctionPass(ID) { 106081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeJumpThreadingPass(*PassRegistry::getPassRegistry()); 107081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 1088383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 1106f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 112c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson AU.addRequired<LazyValueInfo>(); 113c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson AU.addPreserved<LazyValueInfo>(); 114aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier AU.addRequired<TargetLibraryInfo>(); 115cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner } 1166f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 117cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner void FindLoopHeaders(Function &F); 118c7bcbf6903a741e5252d6003916fb3624be937e5Chris Lattner bool ProcessBlock(BasicBlock *BB); 1195729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock*> &PredBBs, 1205729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *SuccBB); 12178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner bool DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, 1222249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner const SmallVectorImpl<BasicBlock *> &PredBBs); 1236f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1245729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, 1256033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel PredValueInfo &Result, 1266033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ConstantPreference Preference); 1276033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 1286033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ConstantPreference Preference); 1296f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 13077beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner bool ProcessBranchOnPHI(PHINode *PN); 1312249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner bool ProcessBranchOnXOR(BinaryOperator *BO); 1326f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 13369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner bool SimplifyPartiallyRedundantLoad(LoadInst *LI); 134c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB); 1358383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner }; 1368383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner} 1378383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner 138844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar JumpThreading::ID = 0; 1392ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading", 1402ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Jump Threading", false, false) 1412ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LazyValueInfo) 142aab8e28d5e470711d80276bbf717408c3ab966fdChad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 1432ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(JumpThreading, "jump-threading", 144ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Jump Threading", false, false) 145844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1468383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner// Public interface to the Jump Threading pass 1478383a7b7a6acdae478d4b4c2520915153b73f676Chris LattnerFunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); } 1488383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner 1498383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner/// runOnFunction - Top level algorithm. 1508383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner/// 1518383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattnerbool JumpThreading::runOnFunction(Function &F) { 15236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(F)) 15336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 155fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n"); 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DL = DLP ? &DLP->getDataLayout() : nullptr; 158aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier TLI = &getAnalysis<TargetLibraryInfo>(); 159c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson LVI = &getAnalysis<LazyValueInfo>(); 1606f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 161cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Remove unreachable blocks from function as they may result in infinite 162cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // loop. We do threading if we found something profitable. Jump threading a 163cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // branch can create other opportunities. If these opportunities form a cycle 164cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // i.e. if any jump treading is undoing previous threading in the path, then 165cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // we will loop forever. We take care of this issue by not jump threading for 166cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // back edges. This works for normal cases but not for unreachable blocks as 167cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // they may have cycle with no back edge. 168cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines removeUnreachableBlocks(F); 169cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 170fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump FindLoopHeaders(F); 1716f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 17266b581ef4965ca3a6c72450ee9916a5c2ab44461Benjamin Kramer bool Changed, EverChanged = false; 17366b581ef4965ca3a6c72450ee9916a5c2ab44461Benjamin Kramer do { 17466b581ef4965ca3a6c72450ee9916a5c2ab44461Benjamin Kramer Changed = false; 175421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E;) { 176421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner BasicBlock *BB = I; 1776f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel // Thread all of the branches we can over this block. 178421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner while (ProcessBlock(BB)) 179bd3401fa98b578080e227afce940bca80137dea6Chris Lattner Changed = true; 1806f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 181421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner ++I; 1826f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 183421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner // If the block is trivially dead, zap it. This eliminates the successor 184421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner // edges which simplifies the CFG. 185421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner if (pred_begin(BB) == pred_end(BB) && 18620fa76ef6f7c2d3073e0960cf347af8db64708fcChris Lattner BB != &BB->getParent()->getEntryBlock()) { 187fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName() 18878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner << "' with terminator: " << *BB->getTerminator() << '\n'); 189fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump LoopHeaders.erase(BB); 190c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson LVI->eraseBlock(BB); 191421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner DeleteDeadBlock(BB); 192421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner Changed = true; 193e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner continue; 194e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner } 195f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson 196e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 197f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson 198e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // Can't thread an unconditional jump, but if the block is "almost 199e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // empty", we can replace uses of it with uses of the successor and make 200e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // this dead. 201e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner if (BI && BI->isUnconditional() && 202e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner BB != &BB->getParent()->getEntryBlock() && 203f3183f6da6321c6496daa107ea5d6d48b99d9330Chris Lattner // If the terminator is the only non-phi instruction, try to nuke it. 204e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner BB->getFirstNonPHIOrDbg()->isTerminator()) { 205e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // Since TryToSimplifyUncondBranchFromEmptyBlock may delete the 206e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // block, we have to make sure it isn't in the LoopHeaders set. We 207e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // reinsert afterward if needed. 208e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner bool ErasedFromLoopHeaders = LoopHeaders.erase(BB); 209e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner BasicBlock *Succ = BI->getSuccessor(0); 210e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner 211e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // FIXME: It is always conservatively correct to drop the info 212e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // for a block even if it doesn't get erased. This isn't totally 213e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // awesome, but it allows us to use AssertingVH to prevent nasty 214e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // dangling pointer issues within LazyValueInfo. 215e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner LVI->eraseBlock(BB); 216e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) { 217e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner Changed = true; 218e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // If we deleted BB and BB was the header of a loop, then the 219e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner // successor is now the header of the loop. 220e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner BB = Succ; 221f3183f6da6321c6496daa107ea5d6d48b99d9330Chris Lattner } 222e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner 223e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner if (ErasedFromLoopHeaders) 224e991b5fdd5ab583531300097cf35e1087d479ef0Chris Lattner LoopHeaders.insert(BB); 225421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner } 226421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner } 227bd3401fa98b578080e227afce940bca80137dea6Chris Lattner EverChanged |= Changed; 22866b581ef4965ca3a6c72450ee9916a5c2ab44461Benjamin Kramer } while (Changed); 2296f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 230fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump LoopHeaders.clear(); 231bd3401fa98b578080e227afce940bca80137dea6Chris Lattner return EverChanged; 2328383a7b7a6acdae478d4b4c2520915153b73f676Chris Lattner} 233177480b7ede0441135572d641a2497df25a7d95fChris Lattner 23478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// getJumpThreadDuplicationCost - Return the cost of duplicating this block to 235c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem/// thread across it. Stop scanning the block when passing the threshold. 236c69908695af9cf509bf498a492854db5f0556e0fNadav Rotemstatic unsigned getJumpThreadDuplicationCost(const BasicBlock *BB, 237c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem unsigned Threshold) { 23878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner /// Ignore PHI nodes, these will be flattened when duplication happens. 23978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner BasicBlock::const_iterator I = BB->getFirstNonPHI(); 2406f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 241b14b88a40ab12996c2982c4bc10fd35bb9a371d4Chris Lattner // FIXME: THREADING will delete values that are just used to compute the 242b14b88a40ab12996c2982c4bc10fd35bb9a371d4Chris Lattner // branch, so they shouldn't count against the duplication cost. 2436f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 24478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Sum up the cost of each instruction until we get to the terminator. Don't 24578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // include the terminator because the copy won't include it. 24678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner unsigned Size = 0; 24778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner for (; !isa<TerminatorInst>(I); ++I) { 248c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem 249c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem // Stop scanning the block if we've reached the threshold. 250c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem if (Size > Threshold) 251c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem return Size; 252c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem 25378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Debugger intrinsics don't incur code size. 25478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (isa<DbgInfoIntrinsic>(I)) continue; 2556f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 25678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // If this is a pointer->pointer bitcast, it is free. 2571df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (isa<BitCastInst>(I) && I->getType()->isPointerTy()) 25878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner continue; 2596f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 26078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // All other instructions count for at least one unit. 26178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner ++Size; 2626f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 26378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Calls are more expensive. If they are non-intrinsic calls, we model them 26478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // as having cost of 4. If they are a non-vector intrinsic, we model them 26578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // as having cost of 2 total, and if they are a vector intrinsic, we model 26678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // them as having cost 1. 26778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (const CallInst *CI = dyn_cast<CallInst>(I)) { 26836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CI->cannotDuplicate()) 26967ae13575900e8efd056672987249fd0adbf5e73James Molloy // Blocks with NoDuplicate are modelled as having infinite cost, so they 27067ae13575900e8efd056672987249fd0adbf5e73James Molloy // are never duplicated. 27167ae13575900e8efd056672987249fd0adbf5e73James Molloy return ~0U; 27267ae13575900e8efd056672987249fd0adbf5e73James Molloy else if (!isa<IntrinsicInst>(CI)) 27378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner Size += 3; 2741df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands else if (!CI->getType()->isVectorTy()) 27578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner Size += 1; 27678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 27778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 2786f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 27978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Threading through a switch statement is particularly profitable. If this 28078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // block ends in a switch, decrease its cost to make it more likely to happen. 28178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (isa<SwitchInst>(I)) 28278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner Size = Size > 6 ? Size-6 : 0; 2836f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 2846033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel // The same holds for indirect branches, but slightly more so. 2856033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (isa<IndirectBrInst>(I)) 2866033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Size = Size > 8 ? Size-8 : 0; 2876033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel 28878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner return Size; 28978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner} 29078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner 291fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// FindLoopHeaders - We do not want jump threading to turn proper loop 292fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// structures into irreducible loops. Doing this breaks up the loop nesting 293fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// hierarchy and pessimizes later transformations. To prevent this from 294fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// happening, we first have to find the loop headers. Here we approximate this 295fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// by finding targets of backedges in the CFG. 296fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// 297fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// Note that there definitely are cases when we want to allow threading of 298fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// edges across a loop header. For example, threading a jump from outside the 299fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// loop (the preheader) to an exit block of the loop is definitely profitable. 300fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// It is also almost always profitable to thread backedges from within the loop 301fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// to exit blocks, and is often profitable to thread backedges to other blocks 302fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// within the loop (forming a nested loop). This simple analysis is not rich 303fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// enough to track all of these properties and keep it up-to-date as the CFG 304fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// mutates, so we don't allow any of these transformations. 305fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// 306fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stumpvoid JumpThreading::FindLoopHeaders(Function &F) { 307fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 308fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump FindFunctionBackedges(F, Edges); 3096f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 310fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump for (unsigned i = 0, e = Edges.size(); i != e; ++i) 311fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump LoopHeaders.insert(const_cast<BasicBlock*>(Edges[i].second)); 312fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump} 313fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 314ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel/// getKnownConstant - Helper method to determine if we can thread over a 315ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel/// terminator with the given value as its condition, and if so what value to 3166033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel/// use for that. What kind of value this is depends on whether we want an 3176033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel/// integer or a block address, but an undef is always accepted. 318ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel/// Returns null if Val is null or not an appropriate constant. 3196033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommelstatic Constant *getKnownConstant(Value *Val, ConstantPreference Preference) { 320ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (!Val) 321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 322ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel 323ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel // Undef is "known" enough. 324ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (UndefValue *U = dyn_cast<UndefValue>(Val)) 325ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel return U; 326ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel 3276033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Preference == WantBlockAddress) 3286033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel return dyn_cast<BlockAddress>(Val->stripPointerCasts()); 329ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel 3306033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel return dyn_cast<ConstantInt>(Val); 3310eb355ab6be61ebd7adb407e02a3604be032b99eOwen Anderson} 3320eb355ab6be61ebd7adb407e02a3604be032b99eOwen Anderson 3335729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see 3346033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel/// if we can infer that the value is a known ConstantInt/BlockAddress or undef 3356033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel/// in any of our predecessors. If so, return the known list of value and pred 3366033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel/// BB in the result vector. 3375729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// 3385729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// This returns true if there were any known values. 3395729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// 3405729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattnerbool JumpThreading:: 3416033b346e20d6932cc62c754cf23ae51786724d6Frits van BommelComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, 3426033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ConstantPreference Preference) { 3439ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson // This method walks up use-def chains recursively. Because of this, we could 3449ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson // get into an infinite loop going around loops in the use-def chain. To 3459ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson // prevent this, keep track of what (value, block) pairs we've already visited 3469ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson // and terminate the search if we loop back to them 347cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson if (!RecursionSet.insert(std::make_pair(V, BB)).second) 348cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson return false; 3496f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 3509ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson // An RAII help to remove this pair from the recursion set once the recursion 3519ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson // stack pops back out again. 3529ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB)); 3536f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 354ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel // If V is a constant, then it is known in all predecessors. 3556033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(V, Preference)) { 356cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 357ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel Result.push_back(std::make_pair(KC, *PI)); 3586f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 3595729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return true; 3605729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 3616f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 3625729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If V is a non-instruction value, or an instruction in a different block, 3635729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // then it can't be derived from a PHI. 3645729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner Instruction *I = dyn_cast<Instruction>(V); 365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!I || I->getParent() != BB) { 3666f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 367cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner // Okay, if this is a live-in value, see if it has a known value at the end 368cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner // of any of our predecessors. 369cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner // 370cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner // FIXME: This should be an edge property, not a block end property. 371cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner /// TODO: Per PR2563, we could infer value range information about a 372cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner /// predecessor based on its terminator. 373cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner // 374c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if 375c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // "I" is a non-local compare-with-a-constant instruction. This would be 376c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // able to handle value inequalities better, for example if the compare is 377c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // "X < 4" and "X < 3" is known true but "X < 4" itself is not available. 378c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // Perhaps getConstantOnEdge should be smart enough to do this? 3796f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 380c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 381c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson BasicBlock *P = *PI; 382c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // If the value is known by LazyValueInfo to be a constant in a 383c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // predecessor, use that information to try to thread this block. 384c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson Constant *PredCst = LVI->getConstantOnEdge(V, P, BB); 3856033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(PredCst, Preference)) 386ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel Result.push_back(std::make_pair(KC, P)); 387cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner } 3886f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 389c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson return !Result.empty(); 390cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner } 3916f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 3925729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner /// If I is a PHI node, then we know the incoming values for any constants. 3935729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (PHINode *PN = dyn_cast<PHINode>(I)) { 3945729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 3955729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner Value *InVal = PN->getIncomingValue(i); 3966033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(InVal, Preference)) { 397ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); 398c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson } else { 39962efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson Constant *CI = LVI->getConstantOnEdge(InVal, 40062efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson PN->getIncomingBlock(i), BB); 4016033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(CI, Preference)) 4026033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); 4035729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 4045729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 4056f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4065729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return !Result.empty(); 4075729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 4086f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 409ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel PredValueInfoTy LHSVals, RHSVals; 4105729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 4115729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Handle some boolean conditions. 4126f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel if (I->getType()->getPrimitiveSizeInBits() == 1) { 4136033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel assert(Preference == WantInteger && "One-bit non-integer type?"); 4145729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // X | true -> true 4155729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // X & false -> false 4165729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (I->getOpcode() == Instruction::Or || 4175729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner I->getOpcode() == Instruction::And) { 4186033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, 4196033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger); 4206033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals, 4216033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger); 4226f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4239ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson if (LHSVals.empty() && RHSVals.empty()) 4245729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return false; 4256f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4265729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner ConstantInt *InterestingVal; 4275729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (I->getOpcode() == Instruction::Or) 4285729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner InterestingVal = ConstantInt::getTrue(I->getContext()); 4295729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner else 4305729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner InterestingVal = ConstantInt::getFalse(I->getContext()); 4316f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4322fa7b48eb594db245dc6af6060c92bbd2b19546bChris Lattner SmallPtrSet<BasicBlock*, 4> LHSKnownBBs; 4336f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4341e452650c6044735b6aa922d41736bda5721adccChris Lattner // Scan for the sentinel. If we find an undef, force it to the 4351e452650c6044735b6aa922d41736bda5721adccChris Lattner // interesting value: x|undef -> true and x&undef -> false. 4365729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) 437ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (LHSVals[i].first == InterestingVal || 438ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel isa<UndefValue>(LHSVals[i].first)) { 4395729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner Result.push_back(LHSVals[i]); 4401e452650c6044735b6aa922d41736bda5721adccChris Lattner Result.back().first = InterestingVal; 4412fa7b48eb594db245dc6af6060c92bbd2b19546bChris Lattner LHSKnownBBs.insert(LHSVals[i].second); 4421e452650c6044735b6aa922d41736bda5721adccChris Lattner } 4435729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = RHSVals.size(); i != e; ++i) 444ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (RHSVals[i].first == InterestingVal || 445ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel isa<UndefValue>(RHSVals[i].first)) { 4460a96144aac449114330a5264b649eb449dc19a37Chris Lattner // If we already inferred a value for this block on the LHS, don't 4470a96144aac449114330a5264b649eb449dc19a37Chris Lattner // re-add it. 4482fa7b48eb594db245dc6af6060c92bbd2b19546bChris Lattner if (!LHSKnownBBs.count(RHSVals[i].second)) { 4490a96144aac449114330a5264b649eb449dc19a37Chris Lattner Result.push_back(RHSVals[i]); 4500a96144aac449114330a5264b649eb449dc19a37Chris Lattner Result.back().first = InterestingVal; 4510a96144aac449114330a5264b649eb449dc19a37Chris Lattner } 4521e452650c6044735b6aa922d41736bda5721adccChris Lattner } 4536f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4545729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return !Result.empty(); 4555729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 4566f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 457055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner // Handle the NOT form of XOR. 458055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner if (I->getOpcode() == Instruction::Xor && 459055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner isa<ConstantInt>(I->getOperand(1)) && 460055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner cast<ConstantInt>(I->getOperand(1))->isOne()) { 4616033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result, 4626033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger); 4639ba353627a11349b1da7b596fe44e73cd5fe7a48Owen Anderson if (Result.empty()) 464055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner return false; 465055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner 466055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner // Invert the known values. 467055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner for (unsigned i = 0, e = Result.size(); i != e; ++i) 468ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel Result[i].first = ConstantExpr::getNot(Result[i].first); 4696f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 470055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner return true; 471055d046f483af3c66f4d19a32a17fc63ed2c22d5Chris Lattner } 4726f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 47362efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson // Try to simplify some other binary operator values. 47462efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) { 4756033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel assert(Preference != WantBlockAddress 4766033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel && "A binary operator creating a block address?"); 4770eb355ab6be61ebd7adb407e02a3604be032b99eOwen Anderson if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) { 478ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel PredValueInfoTy LHSVals; 4796033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals, 4806033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger); 4816f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 482cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson // Try to use constant folding to simplify the binary operator. 483cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { 484906a675db8af7bacdd78708453fc7f7558e64033Chris Lattner Constant *V = LHSVals[i].first; 4850eb355ab6be61ebd7adb407e02a3604be032b99eOwen Anderson Constant *Folded = ConstantExpr::get(BO->getOpcode(), V, CI); 4866f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4876033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(Folded, WantInteger)) 4886033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Result.push_back(std::make_pair(KC, LHSVals[i].second)); 489cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson } 49062efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson } 4916f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 492cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson return !Result.empty(); 4935729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 4946f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 4955729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Handle compare with phi operand, where the PHI is defined in this block. 4965729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) { 4976033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel assert(Preference == WantInteger && "Compares only produce integers"); 4985729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner PHINode *PN = dyn_cast<PHINode>(Cmp->getOperand(0)); 4995729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (PN && PN->getParent() == BB) { 5005729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // We can do this simplification if any comparisons fold to true or false. 5015729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // See if any do. 5025729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 5035729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *PredBB = PN->getIncomingBlock(i); 5045729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner Value *LHS = PN->getIncomingValue(i); 5055729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner Value *RHS = Cmp->getOperand(1)->DoPHITranslation(BB, PredBB); 5066f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 50736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Res = SimplifyCmpInst(Cmp->getPredicate(), LHS, RHS, DL); 508dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Res) { 509c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson if (!isa<Constant>(RHS)) 51066c04c48debfd4357beaf9310346b2b24046b685Chris Lattner continue; 5116f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 5126f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel LazyValueInfo::Tristate 51366c04c48debfd4357beaf9310346b2b24046b685Chris Lattner ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS, 51466c04c48debfd4357beaf9310346b2b24046b685Chris Lattner cast<Constant>(RHS), PredBB, BB); 51566c04c48debfd4357beaf9310346b2b24046b685Chris Lattner if (ResT == LazyValueInfo::Unknown) 51666c04c48debfd4357beaf9310346b2b24046b685Chris Lattner continue; 51766c04c48debfd4357beaf9310346b2b24046b685Chris Lattner Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT); 51866c04c48debfd4357beaf9310346b2b24046b685Chris Lattner } 5196f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 5206033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(Res, WantInteger)) 5216033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Result.push_back(std::make_pair(KC, PredBB)); 5225729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 5236f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 5245729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return !Result.empty(); 5255729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 5266f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 5276f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 5282ad00bf99d5738c39dbc8cab7e30a0b55e0714adChris Lattner // If comparing a live-in value against a constant, see if we know the 5292ad00bf99d5738c39dbc8cab7e30a0b55e0714adChris Lattner // live-in value on any predecessors. 530c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson if (isa<Constant>(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) { 53162efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson if (!isa<Instruction>(Cmp->getOperand(0)) || 532327ca7bec274e25c05a0a4ae5b51a8a2062012c7Owen Anderson cast<Instruction>(Cmp->getOperand(0))->getParent() != BB) { 53362efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson Constant *RHSCst = cast<Constant>(Cmp->getOperand(1)); 534ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif 53562efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson for (pred_iterator PI = pred_begin(BB), E = pred_end(BB);PI != E; ++PI){ 53662efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson BasicBlock *P = *PI; 53762efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson // If the value is known by LazyValueInfo to be a constant in a 53862efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson // predecessor, use that information to try to thread this block. 53962efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson LazyValueInfo::Tristate Res = 54062efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0), 54162efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson RHSCst, P, BB); 54262efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson if (Res == LazyValueInfo::Unknown) 54362efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson continue; 5440e0ff29271df58e3bc545e40f5432c436e8bd76bChris Lattner 54562efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson Constant *ResC = ConstantInt::get(Cmp->getType(), Res); 546ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel Result.push_back(std::make_pair(ResC, P)); 54762efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson } 548ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif 54962efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson return !Result.empty(); 55062efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson } 5516f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 552cb21190cbd8ae1aece5b833ebe3814ada4260627Owen Anderson // Try to find a constant value for the LHS of a comparison, 55362efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson // and evaluate it statically if we can. 554327ca7bec274e25c05a0a4ae5b51a8a2062012c7Owen Anderson if (Constant *CmpConst = dyn_cast<Constant>(Cmp->getOperand(1))) { 555ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel PredValueInfoTy LHSVals; 5566033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, 5576033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger); 5586f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 55962efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { 560906a675db8af7bacdd78708453fc7f7558e64033Chris Lattner Constant *V = LHSVals[i].first; 5610eb355ab6be61ebd7adb407e02a3604be032b99eOwen Anderson Constant *Folded = ConstantExpr::getCompare(Cmp->getPredicate(), 5620eb355ab6be61ebd7adb407e02a3604be032b99eOwen Anderson V, CmpConst); 5636033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(Folded, WantInteger)) 5646033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Result.push_back(std::make_pair(KC, LHSVals[i].second)); 56562efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson } 5666f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 56762efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson return !Result.empty(); 56862efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson } 5692ad00bf99d5738c39dbc8cab7e30a0b55e0714adChris Lattner } 5705729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 5716f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 57226e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel if (SelectInst *SI = dyn_cast<SelectInst>(I)) { 57326e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // Handle select instructions where at least one operand is a known constant 57426e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // and we can figure out the condition value for any predecessor block. 57526e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference); 57626e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference); 57726e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel PredValueInfoTy Conds; 57826e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel if ((TrueVal || FalseVal) && 57926e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds, 58026e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel WantInteger)) { 58126e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel for (unsigned i = 0, e = Conds.size(); i != e; ++i) { 58226e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel Constant *Cond = Conds[i].first; 58326e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel 58426e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // Figure out what value to use for the condition. 58526e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel bool KnownCond; 58626e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel if (ConstantInt *CI = dyn_cast<ConstantInt>(Cond)) { 58726e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // A known boolean. 58826e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel KnownCond = CI->isOne(); 58926e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel } else { 59026e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel assert(isa<UndefValue>(Cond) && "Unexpected condition value"); 59126e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // Either operand will do, so be sure to pick the one that's a known 59226e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // constant. 59326e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // FIXME: Do this more cleverly if both values are known constants? 594dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines KnownCond = (TrueVal != nullptr); 59526e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel } 59626e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel 59726e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel // See if the select has a known constant value for this predecessor. 59826e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel if (Constant *Val = KnownCond ? TrueVal : FalseVal) 59926e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel Result.push_back(std::make_pair(Val, Conds[i].second)); 60026e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel } 60126e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel 60226e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel return !Result.empty(); 60326e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel } 60426e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel } 60526e097ca4bdb31000655ff9ec39fe7d9b7ea226dFrits van Bommel 606c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson // If all else fails, see if LVI can figure out a constant value for us. 607c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson Constant *CI = LVI->getConstant(V, BB); 6086033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (Constant *KC = getKnownConstant(CI, Preference)) { 609c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 610ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel Result.push_back(std::make_pair(KC, *PI)); 61162efd3b38576536cf06ed5bf2f39535eb7961e99Owen Anderson } 6126f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 613c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson return !Result.empty(); 6145729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner} 6155729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 6165729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 6176bf77500c655520a04ea8640af6dccbcf995a754Chris Lattner 618e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner/// GetBestDestForBranchOnUndef - If we determine that the specified block ends 619e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner/// in an undefined jump, decide which block is best to revector to. 620e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner/// 621e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner/// Since we can pick an arbitrary destination, we pick the successor with the 622e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner/// fewest predecessors. This should reduce the in-degree of the others. 623e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner/// 624e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattnerstatic unsigned GetBestDestForJumpOnUndef(BasicBlock *BB) { 625e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner TerminatorInst *BBTerm = BB->getTerminator(); 626e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner unsigned MinSucc = 0; 627e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc); 628e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner // Compute the successor with the minimum number of predecessors. 629e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 630e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) { 631e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner TestBB = BBTerm->getSuccessor(i); 632e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB)); 633f227b50a8e30598464c244a675d8e857b62a52acJakub Staszak if (NumPreds < MinNumPreds) { 634e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner MinSucc = i; 635f227b50a8e30598464c244a675d8e857b62a52acJakub Staszak MinNumPreds = NumPreds; 636f227b50a8e30598464c244a675d8e857b62a52acJakub Staszak } 637e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner } 6386f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 639e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner return MinSucc; 640e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner} 641e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner 64278f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattnerstatic bool hasAddressTakenAndUsed(BasicBlock *BB) { 64378f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner if (!BB->hasAddressTaken()) return false; 644f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson 64578f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner // If the block has its address taken, it may be a tree of dead constants 64678f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner // hanging off of it. These shouldn't keep the block alive. 64778f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner BlockAddress *BA = BlockAddress::get(BB); 64878f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner BA->removeDeadConstantUsers(); 64978f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner return !BA->use_empty(); 65078f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner} 65178f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner 652c7bcbf6903a741e5252d6003916fb3624be937e5Chris Lattner/// ProcessBlock - If there are any predecessors whose control can be threaded 653177480b7ede0441135572d641a2497df25a7d95fChris Lattner/// through to a successor, transform them now. 654c7bcbf6903a741e5252d6003916fb3624be937e5Chris Lattnerbool JumpThreading::ProcessBlock(BasicBlock *BB) { 6558231fd1e6ca940511843381ea5f0dbfbc740b1e6Chris Lattner // If the block is trivially dead, just return and let the caller nuke it. 6568231fd1e6ca940511843381ea5f0dbfbc740b1e6Chris Lattner // This simplifies other transformations. 6578231fd1e6ca940511843381ea5f0dbfbc740b1e6Chris Lattner if (pred_begin(BB) == pred_end(BB) && 6588231fd1e6ca940511843381ea5f0dbfbc740b1e6Chris Lattner BB != &BB->getParent()->getEntryBlock()) 6598231fd1e6ca940511843381ea5f0dbfbc740b1e6Chris Lattner return false; 6606f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 66169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If this block has a single predecessor, and if that pred has a single 66269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // successor, merge the blocks. This encourages recursive jump threading 66369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // because now the condition in this block can be threaded through 66469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // predecessors of our predecessor block. 6655729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (BasicBlock *SinglePred = BB->getSinglePredecessor()) { 666f5102a0f088e7c96f7028bf7ca1c24975c314fffChris Lattner if (SinglePred->getTerminator()->getNumSuccessors() == 1 && 66778f7a25f9826ba66610b5bca83ebea71793abf59Chris Lattner SinglePred != BB && !hasAddressTakenAndUsed(BB)) { 668fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump // If SinglePred was a loop header, BB becomes one. 669fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump if (LoopHeaders.erase(SinglePred)) 670fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump LoopHeaders.insert(BB); 6716f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 6723d86d242c69a26ba2e6102f32b00b04884c4c9b1Chris Lattner // Remember if SinglePred was the entry block of the function. If so, we 6733d86d242c69a26ba2e6102f32b00b04884c4c9b1Chris Lattner // will need to move BB back to the entry position. 6743d86d242c69a26ba2e6102f32b00b04884c4c9b1Chris Lattner bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 675c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson LVI->eraseBlock(SinglePred); 67669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner MergeBasicBlockIntoOnlyPred(BB); 6776f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 6783d86d242c69a26ba2e6102f32b00b04884c4c9b1Chris Lattner if (isEntry && BB != &BB->getParent()->getEntryBlock()) 6793d86d242c69a26ba2e6102f32b00b04884c4c9b1Chris Lattner BB->moveBefore(&BB->getParent()->getEntryBlock()); 68069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner return true; 68169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } 6825729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 6835729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 6846033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel // What kind of constant we're looking for. 6856033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ConstantPreference Preference = WantInteger; 6866033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel 6876033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel // Look to see if the terminator is a conditional branch, switch or indirect 6886033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel // branch, if not we can't thread it. 689177480b7ede0441135572d641a2497df25a7d95fChris Lattner Value *Condition; 6906033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Instruction *Terminator = BB->getTerminator(); 6916033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) { 692bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // Can't thread an unconditional jump. 693bd3401fa98b578080e227afce940bca80137dea6Chris Lattner if (BI->isUnconditional()) return false; 694177480b7ede0441135572d641a2497df25a7d95fChris Lattner Condition = BI->getCondition(); 6956033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) { 696177480b7ede0441135572d641a2497df25a7d95fChris Lattner Condition = SI->getCondition(); 6976033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel } else if (IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) { 698dd2fb6c10b30e70ab8f910e21e583be3e90bb88cRichard Osborne // Can't thread indirect branch with no successors. 699dd2fb6c10b30e70ab8f910e21e583be3e90bb88cRichard Osborne if (IB->getNumSuccessors() == 0) return false; 7006033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Condition = IB->getAddress()->stripPointerCasts(); 7016033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel Preference = WantBlockAddress; 7026033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel } else { 703177480b7ede0441135572d641a2497df25a7d95fChris Lattner return false; // Must be an invoke. 7046033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel } 7056f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 706f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson // Run constant folding to see if we can reduce the condition to a simple 707f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson // constant. 708f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson if (Instruction *I = dyn_cast<Instruction>(Condition)) { 70936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *SimpleVal = ConstantFoldInstruction(I, DL, TLI); 710f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson if (SimpleVal) { 711f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson I->replaceAllUsesWith(SimpleVal); 712f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson I->eraseFromParent(); 713f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson Condition = SimpleVal; 714f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson } 715f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson } 716f6832bbda08b6975caa264de183bf3ee1d472acaOwen Anderson 717421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner // If the terminator is branching on an undef, we can pick any of the 718e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner // successors to branch to. Let GetBestDestForJumpOnUndef decide. 719421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner if (isa<UndefValue>(Condition)) { 720e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner unsigned BestSucc = GetBestDestForJumpOnUndef(BB); 7216f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 722421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner // Fold the branch/switch. 723e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner TerminatorInst *BBTerm = BB->getTerminator(); 724421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) { 725e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner if (i == BestSucc) continue; 72636c4debc94e7c68c769dfda781851a0c963dd746Owen Anderson BBTerm->getSuccessor(i)->removePredecessor(BB, true); 727421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner } 7286f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 729fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " In block '" << BB->getName() 73078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner << "' folding undef terminator: " << *BBTerm << '\n'); 731e33583b7c2b4d715a24e4d668bf446af9c836e54Chris Lattner BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm); 732421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner BBTerm->eraseFromParent(); 733421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner return true; 734421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner } 7356f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 736ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel // If the terminator of this block is branching on a constant, simplify the 737ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel // terminator to an unconditional branch. This can occur due to threading in 738ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel // other blocks. 7396033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (getKnownConstant(Condition, Preference)) { 740ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel DEBUG(dbgs() << " In block '" << BB->getName() 741ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel << "' folding terminator: " << *BB->getTerminator() << '\n'); 742ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel ++NumFolds; 7435649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel ConstantFoldTerminator(BB, true); 744ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel return true; 745ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel } 746ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel 747421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner Instruction *CondInst = dyn_cast<Instruction>(Condition); 748421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner 749421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner // All the rest of our checks depend on the condition being an instruction. 750dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CondInst) { 75187e9f59c7a823ba86d8aafa4e15ac03e6db244c3Chris Lattner // FIXME: Unify this with code below. 7526033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (ProcessThreadableEdges(Condition, BB, Preference)) 75387e9f59c7a823ba86d8aafa4e15ac03e6db244c3Chris Lattner return true; 754421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner return false; 7556f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel } 7566f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 7576f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 7589683f181746c2312c8828c79b6e25a07fb441d57Nick Lewycky if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) { 759660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson // For a comparison where the LHS is outside this block, it's possible 760fc2fb17fb764470626f3d7ecf2fb68fe73b0d757Owen Anderson // that we've branched on it before. Used LVI to see if we can simplify 761660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson // the branch based on that. 762660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); 763660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1)); 764c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 765c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson if (CondBr && CondConst && CondBr->isConditional() && PI != PE && 766660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson (!isa<Instruction>(CondCmp->getOperand(0)) || 767660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson cast<Instruction>(CondCmp->getOperand(0))->getParent() != BB)) { 768660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson // For predecessor edge, determine if the comparison is true or false 769660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson // on that edge. If they're all true or all false, we can simplify the 770660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson // branch. 771660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson // FIXME: We could handle mixed true/false by duplicating code. 7726f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel LazyValueInfo::Tristate Baseline = 773c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson LVI->getPredicateOnEdge(CondCmp->getPredicate(), CondCmp->getOperand(0), 774c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson CondConst, *PI, BB); 775c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson if (Baseline != LazyValueInfo::Unknown) { 776c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson // Check that all remaining incoming values match the first one. 777c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson while (++PI != PE) { 778bdabacdccae980b82b5d92e10697b8aeb3b94cfaChris Lattner LazyValueInfo::Tristate Ret = 779bdabacdccae980b82b5d92e10697b8aeb3b94cfaChris Lattner LVI->getPredicateOnEdge(CondCmp->getPredicate(), 780bdabacdccae980b82b5d92e10697b8aeb3b94cfaChris Lattner CondCmp->getOperand(0), CondConst, *PI, BB); 781c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson if (Ret != Baseline) break; 782c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson } 7836f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 784c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson // If we terminated early, then one of the values didn't match. 785c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson if (PI == PE) { 786c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson unsigned ToRemove = Baseline == LazyValueInfo::True ? 1 : 0; 787c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson unsigned ToKeep = Baseline == LazyValueInfo::True ? 0 : 1; 78836c4debc94e7c68c769dfda781851a0c963dd746Owen Anderson CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true); 789c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr); 790c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson CondBr->eraseFromParent(); 791c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson return true; 792c1bdac66fff1e65aba02ec853cc0693dcc967f33Owen Anderson } 793660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson } 794c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 795660cab32fe5105bcaa17daa4704c24065ac0a7e6Owen Anderson } 796c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 797c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer if (CondBr && CondConst && TryToUnfoldSelect(CondCmp, BB)) 798c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer return true; 7999683f181746c2312c8828c79b6e25a07fb441d57Nick Lewycky } 80069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 80169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Check for some cases that are worth simplifying. Right now we want to look 80269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // for loads that are used by a switch or by the condition for the branch. If 80369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // we see one, check to see if it's partially redundant. If so, insert a PHI 80469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // which can then be used to thread the values. 80569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // 806421fa9e32e445c972df4a981c60fbec4e21ac187Chris Lattner Value *SimplifyValue = CondInst; 80769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue)) 80869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (isa<Constant>(CondCmp->getOperand(1))) 80969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner SimplifyValue = CondCmp->getOperand(0); 8106f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8114e447ebc5897a466c37bd2e9f5514d3fc5135789Chris Lattner // TODO: There are other places where load PRE would be profitable, such as 8124e447ebc5897a466c37bd2e9f5514d3fc5135789Chris Lattner // more complex comparisons. 81369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue)) 81469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (SimplifyPartiallyRedundantLoad(LI)) 81569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner return true; 8166f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8176f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8185729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Handle a variety of cases where we are branching on something derived from 8195729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // a PHI node in the current block. If we can prove that any predecessors 8205729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // compute a predictable value based on a PHI node, thread those predecessors. 8215729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // 8226033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (ProcessThreadableEdges(CondInst, BB, Preference)) 823cc4d3b25f336eef135cb7125716ecb2c1979e92eChris Lattner return true; 8246f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 82577beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner // If this is an otherwise-unfoldable branch on a phi node in the current 82677beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner // block, see if we can simplify. 82777beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(CondInst)) 82877beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator())) 82977beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner return ProcessBranchOnPHI(PN); 8306f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8316f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8322249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify. 8332249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner if (CondInst->getOpcode() == Instruction::Xor && 8342249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator())) 8352249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst)); 8366f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8376f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 83869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // TODO: If we have: "br (X > 0)" and we have a predecessor where we know 83977beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner // "(X == 4)", thread through this block. 8406f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 841d38c14e6ed0136624a18cf8338c82f1709d804aaChris Lattner return false; 842d38c14e6ed0136624a18cf8338c82f1709d804aaChris Lattner} 843d38c14e6ed0136624a18cf8338c82f1709d804aaChris Lattner 84469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner/// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant 84569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner/// load instruction, eliminate it by replacing it with a PHI node. This is an 84669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner/// important optimization that encourages jump threading, and needs to be run 84769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner/// interlaced with other jump threading tasks. 84869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattnerbool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { 8492bc3d52b9ab422ee9f7e42a1a4e3b818e623a5f7Eli Friedman // Don't hack volatile/atomic loads. 8502bc3d52b9ab422ee9f7e42a1a4e3b818e623a5f7Eli Friedman if (!LI->isSimple()) return false; 8516f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 85269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If the load is defined in a block with exactly one predecessor, it can't be 85369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // partially redundant. 85469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner BasicBlock *LoadBB = LI->getParent(); 85569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (LoadBB->getSinglePredecessor()) 85669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner return false; 8576f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8583e033f29239e48c190f29cdf3a02cdfbaf2fe72bBill Wendling // If the load is defined in a landing pad, it can't be partially redundant, 8593e033f29239e48c190f29cdf3a02cdfbaf2fe72bBill Wendling // because the edges between the invoke and the landing pad cannot have other 8603e033f29239e48c190f29cdf3a02cdfbaf2fe72bBill Wendling // instructions between them. 8613e033f29239e48c190f29cdf3a02cdfbaf2fe72bBill Wendling if (LoadBB->isLandingPad()) 8623e033f29239e48c190f29cdf3a02cdfbaf2fe72bBill Wendling return false; 8633e033f29239e48c190f29cdf3a02cdfbaf2fe72bBill Wendling 86469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner Value *LoadedPtr = LI->getOperand(0); 86569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 86669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If the loaded operand is defined in the LoadBB, it can't be available. 8674e447ebc5897a466c37bd2e9f5514d3fc5135789Chris Lattner // TODO: Could do simple PHI translation, that would be fun :) 86869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr)) 86969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (PtrOp->getParent() == LoadBB) 87069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner return false; 8716f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 87269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Scan a few instructions up from the load, to see if it is obviously live at 87369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // the entry to its block. 87469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner BasicBlock::iterator BBIt = LI; 87569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 8766f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel if (Value *AvailableVal = 8774e447ebc5897a466c37bd2e9f5514d3fc5135789Chris Lattner FindAvailableLoadedValue(LoadedPtr, LoadBB, BBIt, 6)) { 87869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If the value if the load is locally available within the block, just use 87969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // it. This frequently occurs for reg2mem'd allocas. 88069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n"; 8816f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8822a99b482a62e3f1ac3fd716fba430ac32fedade4Chris Lattner // If the returned value is the load itself, replace with an undef. This can 8832a99b482a62e3f1ac3fd716fba430ac32fedade4Chris Lattner // only happen in dead loops. 8849e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType()); 88569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner LI->replaceAllUsesWith(AvailableVal); 88669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner LI->eraseFromParent(); 88769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner return true; 88869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } 88969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 89069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Otherwise, if we scanned the whole block and got to the top of the block, 89169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // we know the block is locally transparent to the load. If not, something 89269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // might clobber its value. 89369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (BBIt != LoadBB->begin()) 89469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner return false; 8956f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 8965161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner // If all of the loads and stores that feed the value have the same TBAA tag, 8975161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner // then we can propagate it onto any newly inserted loads. 898a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem MDNode *TBAATag = LI->getMetadata(LLVMContext::MD_tbaa); 8996f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 90069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner SmallPtrSet<BasicBlock*, 8> PredsScanned; 90169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy; 90269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner AvailablePredsTy AvailablePreds; 903dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *OneUnavailablePred = nullptr; 9046f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 90569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If we got here, the loaded value is transparent through to the start of the 90669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // block. Check to see if it is available in any of the predecessor blocks. 90769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB); 90869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner PI != PE; ++PI) { 90969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner BasicBlock *PredBB = *PI; 91069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 91169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If we already scanned this predecessor, skip it. 91269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (!PredsScanned.insert(PredBB)) 91369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner continue; 91469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 91569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Scan the predecessor to see if the value is available in the pred. 91669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner BBIt = PredBB->end(); 917dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MDNode *ThisTBAATag = nullptr; 9185161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6, 919dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nullptr, &ThisTBAATag); 92069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (!PredAvailable) { 92169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner OneUnavailablePred = PredBB; 92269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner continue; 92369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } 924a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 9255161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner // If tbaa tags disagree or are not present, forget about them. 926dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (TBAATag != ThisTBAATag) TBAATag = nullptr; 9276f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 92869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If so, this load is partially redundant. Remember this info so that we 92969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // can create a PHI node. 93069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable)); 93169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } 9326f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 93369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If the loaded value isn't available in any predecessor, it isn't partially 93469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // redundant. 93569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (AvailablePreds.empty()) return false; 9366f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 93769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Okay, the loaded value is available in at least one (and maybe all!) 93869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // predecessors. If the value is unavailable in more than one unique 93969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // predecessor, we want to insert a merge block for those common predecessors. 94069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // This ensures that we only have to insert one reload, thus not increasing 94169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // code size. 942dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *UnavailablePred = nullptr; 9436f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 94469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If there is exactly one predecessor where the value is unavailable, the 94569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // already computed 'OneUnavailablePred' block is it. If it ends in an 94669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // unconditional branch, we know that it isn't a critical edge. 94769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (PredsScanned.size() == AvailablePreds.size()+1 && 94869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) { 94969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner UnavailablePred = OneUnavailablePred; 95069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } else if (PredsScanned.size() != AvailablePreds.size()) { 95169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Otherwise, we had multiple unavailable predecessors or we had a critical 95269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // edge from the one. 95369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner SmallVector<BasicBlock*, 8> PredsToSplit; 95469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner SmallPtrSet<BasicBlock*, 8> AvailablePredSet; 95569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 95669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner for (unsigned i = 0, e = AvailablePreds.size(); i != e; ++i) 95769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner AvailablePredSet.insert(AvailablePreds[i].first); 95869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 95969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Add all the unavailable predecessors to the PredsToSplit list. 96069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner for (pred_iterator PI = pred_begin(LoadBB), PE = pred_end(LoadBB); 961e58867e55e472d81bbf5b1d26310a5b3918d2fb6Chris Lattner PI != PE; ++PI) { 962ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif BasicBlock *P = *PI; 963e58867e55e472d81bbf5b1d26310a5b3918d2fb6Chris Lattner // If the predecessor is an indirect goto, we can't split the edge. 964ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif if (isa<IndirectBrInst>(P->getTerminator())) 965e58867e55e472d81bbf5b1d26310a5b3918d2fb6Chris Lattner return false; 9666f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 967ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif if (!AvailablePredSet.count(P)) 968ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif PredsToSplit.push_back(P); 969e58867e55e472d81bbf5b1d26310a5b3918d2fb6Chris Lattner } 9706f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 97169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Split them out to their own block. 97269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner UnavailablePred = 9732fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak SplitBlockPredecessors(LoadBB, PredsToSplit, "thread-pre-split", this); 97469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } 9756f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 97669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // If the value isn't available in all predecessors, then there will be 97769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // exactly one where it isn't available. Insert a load on that edge and add 97869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // it to the AvailablePreds list. 97969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner if (UnavailablePred) { 98069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 && 98169e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner "Can't handle critical edge here!"); 98295a7de6b916e49265ebdae04a32f6beda7f89028Devang Patel LoadInst *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr", false, 9834e447ebc5897a466c37bd2e9f5514d3fc5135789Chris Lattner LI->getAlignment(), 98469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner UnavailablePred->getTerminator()); 98595a7de6b916e49265ebdae04a32f6beda7f89028Devang Patel NewVal->setDebugLoc(LI->getDebugLoc()); 9865161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner if (TBAATag) 9875161de6ebbd36b0532bd980483d757f5a3014611Chris Lattner NewVal->setMetadata(LLVMContext::MD_tbaa, TBAATag); 988a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 98969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal)); 99069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } 9916f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 99269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Now we know that each predecessor of this block has a value in 99369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // AvailablePreds, sort them for efficient access as we're walking the preds. 994a3522000ab9c821f48856d0c25ada8297c1c2914Chris Lattner array_pod_sort(AvailablePreds.begin(), AvailablePreds.end()); 9956f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 99669e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Create a PHI node at the start of the block for the PRE'd load value. 997d8b4fb4aab4d6fedb2b14bed1b846451b17bde7cJay Foad pred_iterator PB = pred_begin(LoadBB), PE = pred_end(LoadBB); 9983ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *PN = PHINode::Create(LI->getType(), std::distance(PB, PE), "", 9993ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad LoadBB->begin()); 100069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner PN->takeName(LI); 100195a7de6b916e49265ebdae04a32f6beda7f89028Devang Patel PN->setDebugLoc(LI->getDebugLoc()); 10026f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 100369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // Insert new entries into the PHI for each predecessor. A single block may 100469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner // have multiple entries here. 1005d8b4fb4aab4d6fedb2b14bed1b846451b17bde7cJay Foad for (pred_iterator PI = PB; PI != PE; ++PI) { 1006ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif BasicBlock *P = *PI; 10076f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel AvailablePredsTy::iterator I = 100869e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner std::lower_bound(AvailablePreds.begin(), AvailablePreds.end(), 1009dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::make_pair(P, (Value*)nullptr)); 10106f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1011ee1f44fba3f2ba01657f217d159b4d09f249e46dGabor Greif assert(I != AvailablePreds.end() && I->first == P && 101269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner "Didn't find entry for predecessor!"); 10136f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 101469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner PN->addIncoming(I->second, I->first); 101569e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner } 10166f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 101769e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner //cerr << "PRE: " << *LI << *PN << "\n"; 10186f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 101969e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner LI->replaceAllUsesWith(PN); 102069e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner LI->eraseFromParent(); 10216f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 102269e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner return true; 102369e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner} 102469e067fdd86d34cb81ccdffb82415b4f89144218Chris Lattner 10255729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// FindMostPopularDest - The specified list contains multiple possible 10265729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// threadable destinations. Pick the one that occurs the most frequently in 10275729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// the list. 10285729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattnerstatic BasicBlock * 10295729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris LattnerFindMostPopularDest(BasicBlock *BB, 10305729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner const SmallVectorImpl<std::pair<BasicBlock*, 10315729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock*> > &PredToDestList) { 10325729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner assert(!PredToDestList.empty()); 10336f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 10345729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Determine popularity. If there are multiple possible destinations, we 10355729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // explicitly choose to ignore 'undef' destinations. We prefer to thread 10365729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // blocks with known and real destinations to threading undef. We'll handle 10375729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // them later if interesting. 10385729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner DenseMap<BasicBlock*, unsigned> DestPopularity; 10395729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PredToDestList.size(); i != e; ++i) 10405729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (PredToDestList[i].second) 10415729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner DestPopularity[PredToDestList[i].second]++; 10426f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 10435729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Find the most popular dest. 10445729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner DenseMap<BasicBlock*, unsigned>::iterator DPI = DestPopularity.begin(); 10455729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *MostPopularDest = DPI->first; 10465729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner unsigned Popularity = DPI->second; 10475729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner SmallVector<BasicBlock*, 4> SamePopularity; 10486f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 10495729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (++DPI; DPI != DestPopularity.end(); ++DPI) { 10505729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If the popularity of this entry isn't higher than the popularity we've 10515729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // seen so far, ignore it. 10525729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (DPI->second < Popularity) 10535729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner ; // ignore. 10545729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner else if (DPI->second == Popularity) { 10555729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If it is the same as what we've seen so far, keep track of it. 10565729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner SamePopularity.push_back(DPI->first); 10575729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } else { 10585729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If it is more popular, remember it. 10595729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner SamePopularity.clear(); 10605729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner MostPopularDest = DPI->first; 10615729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner Popularity = DPI->second; 10626f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel } 106378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 10646f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 106501abcf339f8d42921c680fefb2ff988cfeee1198Frits van Bommel // Okay, now we know the most popular destination. If there is more than one 10665729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // destination, we need to determine one. This is arbitrary, but we need 10675729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // to make a deterministic decision. Pick the first one that appears in the 10685729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // successor list. 10695729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (!SamePopularity.empty()) { 10705729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner SamePopularity.push_back(MostPopularDest); 10715729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner TerminatorInst *TI = BB->getTerminator(); 10725729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0; ; ++i) { 10735729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner assert(i != TI->getNumSuccessors() && "Didn't find any successor!"); 10746f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 10755729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (std::find(SamePopularity.begin(), SamePopularity.end(), 10765729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner TI->getSuccessor(i)) == SamePopularity.end()) 10775729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner continue; 10786f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 10795729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner MostPopularDest = TI->getSuccessor(i); 108012d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel break; 108112d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel } 108212d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel } 10836f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 10845729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Okay, we have finally picked the most popular destination. 10855729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return MostPopularDest; 10865729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner} 10875729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 10886033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommelbool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, 10896033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel ConstantPreference Preference) { 10905729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If threading this would thread across a loop header, don't even try to 10915729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // thread the edge. 10925729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (LoopHeaders.count(BB)) 109312d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel return false; 10946f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1095ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel PredValueInfoTy PredValues; 10966033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference)) 109712d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel return false; 10986f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 10995729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner assert(!PredValues.empty() && 11005729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner "ComputeValueKnownInPredecessors returned true with no values"); 11015729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 1102fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << "IN BB: " << *BB; 11035729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PredValues.size(); i != e; ++i) { 1104ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel dbgs() << " BB '" << BB->getName() << "': FOUND condition = " 1105ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel << *PredValues[i].first 1106ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel << " for pred '" << PredValues[i].second->getName() << "'.\n"; 11075729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner }); 11086f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11095729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Decide what we want to thread through. Convert our list of known values to 11105729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // a list of known destinations for each pred. This also discards duplicate 11115729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // predecessors and keeps track of the undefined inputs (which are represented 1112e7e63fe9650fc01043c96e2bf8a1ecc19e49c5b7Chris Lattner // as a null dest in the PredToDestList). 11135729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner SmallPtrSet<BasicBlock*, 16> SeenPreds; 11145729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList; 11156f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *OnlyDest = nullptr; 11175729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL; 11186f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11195729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PredValues.size(); i != e; ++i) { 11205729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *Pred = PredValues[i].second; 11215729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (!SeenPreds.insert(Pred)) 11225729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner continue; // Duplicate predecessor entry. 11236f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11245729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If the predecessor ends with an indirect goto, we can't change its 11255729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // destination. 11265729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (isa<IndirectBrInst>(Pred->getTerminator())) 112712d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel continue; 11286f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1129ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel Constant *Val = PredValues[i].first; 11306f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11315729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *DestBB; 1132ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (isa<UndefValue>(Val)) 1133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DestBB = nullptr; 11345729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) 1135ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero()); 113624473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1137c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy DestBB = SI->findCaseValue(cast<ConstantInt>(Val)).getCaseSuccessor(); 113824473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy } else { 11396033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel assert(isa<IndirectBrInst>(BB->getTerminator()) 11406033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel && "Unexpected terminator"); 11416033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel DestBB = cast<BlockAddress>(Val)->getBasicBlock(); 114212d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel } 11435729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 11445729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If we have exactly one destination, remember it for efficiency below. 114501abcf339f8d42921c680fefb2ff988cfeee1198Frits van Bommel if (PredToDestList.empty()) 11465729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner OnlyDest = DestBB; 11475729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner else if (OnlyDest != DestBB) 11485729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner OnlyDest = MultipleDestSentinel; 11496f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11505729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner PredToDestList.push_back(std::make_pair(Pred, DestBB)); 115112d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel } 11526f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11535729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If all edges were unthreadable, we fail. 11545729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (PredToDestList.empty()) 115512d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel return false; 11566f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11575729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Determine which is the most common successor. If we have many inputs and 11585729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // this block is a switch, we want to start by threading the batch that goes 11595729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // to the most popular destination first. If we only know about one 11605729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // threadable destination (the common case) we can avoid this. 11615729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *MostPopularDest = OnlyDest; 11626f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11635729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (MostPopularDest == MultipleDestSentinel) 11645729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner MostPopularDest = FindMostPopularDest(BB, PredToDestList); 11656f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11665729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // Now that we know what the most popular destination is, factor all 11675729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // predecessors that will jump to it into a single predecessor. 11685729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner SmallVector<BasicBlock*, 16> PredsToFactor; 11695729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PredToDestList.size(); i != e; ++i) 11705729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (PredToDestList[i].second == MostPopularDest) { 11715729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *Pred = PredToDestList[i].first; 11726f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11735729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // This predecessor may be a switch or something else that has multiple 11745729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // edges to the block. Factor each of these edges by listing them 11755729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // according to # occurrences in PredsToFactor. 11765729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner TerminatorInst *PredTI = Pred->getTerminator(); 11775729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PredTI->getNumSuccessors(); i != e; ++i) 11785729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (PredTI->getSuccessor(i) == BB) 11795729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner PredsToFactor.push_back(Pred); 11805729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 11815729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 11825729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If the threadable edges are branching on an undefined value, we get to pick 11835729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // the destination that these predecessors should get to. 1184dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!MostPopularDest) 11855729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner MostPopularDest = BB->getTerminator()-> 11865729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner getSuccessor(GetBestDestForJumpOnUndef(BB)); 11876f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 118812d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel // Ok, try to thread it! 11895729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return ThreadEdge(BB, PredsToFactor, MostPopularDest); 11905729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner} 11915729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 119277beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner/// ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on 119377beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner/// a PHI node in the current block. See if there are any simplifications we 119477beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner/// can do based on inputs to the phi node. 11956f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel/// 119677beb479f556093c5f1b4854fcbb095cda34f202Chris Lattnerbool JumpThreading::ProcessBranchOnPHI(PHINode *PN) { 11975729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *BB = PN->getParent(); 11986f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 11992249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // TODO: We could make use of this to do it once for blocks with common PHI 12002249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // values. 12012249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner SmallVector<BasicBlock*, 1> PredBBs; 12022249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner PredBBs.resize(1); 12036f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 12045729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // If any of the predecessor blocks end in an unconditional branch, we can 120577beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner // *duplicate* the conditional branch into that block in order to further 120677beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner // encourage jump threading and to eliminate cases where we have branch on a 120777beb479f556093c5f1b4854fcbb095cda34f202Chris Lattner // phi of an icmp (branch on icmp is much better). 12085729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 12095729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *PredBB = PN->getIncomingBlock(i); 12105729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator())) 12112249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner if (PredBr->isUnconditional()) { 12122249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner PredBBs[0] = PredBB; 12132249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // Try to duplicate BB into PredBB. 12142249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs)) 12152249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner return true; 12162249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner } 12175729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 12185729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner 12195729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner return false; 122012d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel} 122112d53dba36905d20b02cf7c4cdae057ae4a5a5e1Devang Patel 12222249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner/// ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on 12232249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner/// a xor instruction in the current block. See if there are any 12242249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner/// simplifications we can do based on inputs to the xor. 12256f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel/// 12262249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattnerbool JumpThreading::ProcessBranchOnXOR(BinaryOperator *BO) { 12272249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner BasicBlock *BB = BO->getParent(); 12286f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 12292249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // If either the LHS or RHS of the xor is a constant, don't do this 12302249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // optimization. 12312249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner if (isa<ConstantInt>(BO->getOperand(0)) || 12322249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner isa<ConstantInt>(BO->getOperand(1))) 12332249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner return false; 12346f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 12352dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner // If the first instruction in BB isn't a phi, we won't be able to infer 12362dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner // anything special about any particular predecessor. 12372dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner if (!isa<PHINode>(BB->front())) 12382dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner return false; 12396f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 12402249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // If we have a xor as the branch input to this block, and we know that the 12412249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // LHS or RHS of the xor in any predecessor is true/false, then we can clone 12422249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // the condition into the predecessor and fix that value to true, saving some 12432249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // logical ops on that path and encouraging other paths to simplify. 12442249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // 12452249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // This copies something like this: 12462249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // 12472249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // BB: 12482249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // %X = phi i1 [1], [%X'] 12492249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // %Y = icmp eq i32 %A, %B 12502249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // %Z = xor i1 %X, %Y 12512249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // br i1 %Z, ... 12522249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // 12532249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // Into: 12542249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // BB': 12552249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // %Y = icmp ne i32 %A, %B 12562249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // br i1 %Z, ... 12572249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner 1258ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel PredValueInfoTy XorOpValues; 12592249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner bool isLHS = true; 12606033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues, 12616033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger)) { 12622249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner assert(XorOpValues.empty()); 12636033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues, 12646033b346e20d6932cc62c754cf23ae51786724d6Frits van Bommel WantInteger)) 12652249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner return false; 12662249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner isLHS = false; 12672249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner } 12686f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 12692249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner assert(!XorOpValues.empty() && 12702249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner "ComputeValueKnownInPredecessors returned true with no values"); 12712249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner 12722249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // Scan the information to see which is most popular: true or false. The 12732249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // predecessors can be of the set true, false, or undef. 12742249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner unsigned NumTrue = 0, NumFalse = 0; 12752249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner for (unsigned i = 0, e = XorOpValues.size(); i != e; ++i) { 1276ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (isa<UndefValue>(XorOpValues[i].first)) 1277ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel // Ignore undefs for the count. 1278ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel continue; 1279ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (cast<ConstantInt>(XorOpValues[i].first)->isZero()) 12802249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner ++NumFalse; 12812249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner else 12822249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner ++NumTrue; 12832249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner } 12846f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 12852249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // Determine which value to split on, true, false, or undef if neither. 1286dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ConstantInt *SplitVal = nullptr; 12872249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner if (NumTrue > NumFalse) 12882249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner SplitVal = ConstantInt::getTrue(BB->getContext()); 12892249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner else if (NumTrue != 0 || NumFalse != 0) 12902249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner SplitVal = ConstantInt::getFalse(BB->getContext()); 12916f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 12922249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // Collect all of the blocks that this can be folded into so that we can 12932249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // factor this once and clone it once. 12942249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner SmallVector<BasicBlock*, 8> BlocksToFoldInto; 12952249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner for (unsigned i = 0, e = XorOpValues.size(); i != e; ++i) { 1296ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel if (XorOpValues[i].first != SplitVal && 1297ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel !isa<UndefValue>(XorOpValues[i].first)) 1298ea388f217b8368db13f598e4c547bab5582eb82aFrits van Bommel continue; 12992249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner 13002249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner BlocksToFoldInto.push_back(XorOpValues[i].second); 13012249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner } 13026f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 13032dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner // If we inferred a value for all of the predecessors, then duplication won't 13042dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner // help us. However, we can just replace the LHS or RHS with the constant. 13052dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner if (BlocksToFoldInto.size() == 13062dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner cast<PHINode>(BB->front()).getNumIncomingValues()) { 1307dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!SplitVal) { 13082dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner // If all preds provide undef, just nuke the xor, because it is undef too. 13092dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner BO->replaceAllUsesWith(UndefValue::get(BO->getType())); 13102dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner BO->eraseFromParent(); 13112dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner } else if (SplitVal->isZero()) { 13122dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner // If all preds provide 0, replace the xor with the other input. 13132dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner BO->replaceAllUsesWith(BO->getOperand(isLHS)); 13142dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner BO->eraseFromParent(); 13152dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner } else { 13162dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner // If all preds provide 1, set the computed value to 1. 13172dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner BO->setOperand(!isLHS, SplitVal); 13182dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner } 13196f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 13202dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner return true; 13212dd7657a5b063e6f77c34f418b7e23654b6fe4a0Chris Lattner } 13226f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 13232249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // Try to duplicate BB into PredBB. 1324797c440caf24e92b16b9a87a39ef2f5c4cfb60f0Chris Lattner return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto); 13252249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner} 13262249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner 13272249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner 132878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// AddPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new 132978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// predecessor to the PHIBB block. If it has PHI nodes, add entries for 133078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// NewPred using the entries from OldPred (suitably mapped). 133178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattnerstatic void AddPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, 133278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner BasicBlock *OldPred, 133378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner BasicBlock *NewPred, 133478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner DenseMap<Instruction*, Value*> &ValueMap) { 133578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner for (BasicBlock::iterator PNI = PHIBB->begin(); 133678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner PHINode *PN = dyn_cast<PHINode>(PNI); ++PNI) { 133778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Ok, we have a PHI node. Figure out what the incoming value was for the 133878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // DestBlock. 133978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner Value *IV = PN->getIncomingValueForBlock(OldPred); 13406f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 134178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Remap the value if necessary. 134278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(IV)) { 134378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner DenseMap<Instruction*, Value*>::iterator I = ValueMap.find(Inst); 134478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (I != ValueMap.end()) 134578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner IV = I->second; 1346bdbf1a177de085927c375efa986c52af2057fb7aChris Lattner } 13476f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 134878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner PN->addIncoming(IV, NewPred); 1349bdbf1a177de085927c375efa986c52af2057fb7aChris Lattner } 1350fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump} 1351fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 13525729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// ThreadEdge - We have decided that it is safe and profitable to factor the 13535729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB 13545729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner/// across BB. Transform the IR to reflect this change. 13556f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommelbool JumpThreading::ThreadEdge(BasicBlock *BB, 13566f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel const SmallVectorImpl<BasicBlock*> &PredBBs, 1357bdbf1a177de085927c375efa986c52af2057fb7aChris Lattner BasicBlock *SuccBB) { 1358eede65ce6cb29c8f3a701be8606e95c9a213efffChris Lattner // If threading to the same block as we come from, we would infinite loop. 1359eede65ce6cb29c8f3a701be8606e95c9a213efffChris Lattner if (SuccBB == BB) { 1360fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Not threading across BB '" << BB->getName() 136193b67e40de356569493c285b86b138a3f11b5035Daniel Dunbar << "' - would thread to self!\n"); 1362eede65ce6cb29c8f3a701be8606e95c9a213efffChris Lattner return false; 1363eede65ce6cb29c8f3a701be8606e95c9a213efffChris Lattner } 13646f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1365fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump // If threading this would thread across a loop header, don't thread the edge. 1366fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump // See the comments above FindLoopHeaders for justifications and caveats. 1367fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump if (LoopHeaders.count(BB)) { 1368fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Not threading across loop header BB '" << BB->getName() 136993b67e40de356569493c285b86b138a3f11b5035Daniel Dunbar << "' to dest BB '" << SuccBB->getName() 137093b67e40de356569493c285b86b138a3f11b5035Daniel Dunbar << "' - it might create an irreducible loop!\n"); 1371fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump return false; 1372fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump } 1373fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 1374c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, Threshold); 137578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (JumpThreadCost > Threshold) { 1376fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Not threading BB '" << BB->getName() 137778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner << "' - Cost is too high: " << JumpThreadCost << "\n"); 137878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner return false; 137978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 13806f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 13815729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner // And finally, do it! Start by factoring the predecessors is needed. 13825729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner BasicBlock *PredBB; 13835729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner if (PredBBs.size() == 1) 13845729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner PredBB = PredBBs[0]; 13855729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner else { 1386fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Factoring out " << PredBBs.size() 13875729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner << " common predecessors.\n"); 13882fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak PredBB = SplitBlockPredecessors(BB, PredBBs, ".thr_comm", this); 13895729d38c81bc2e3b21a2bb7a80a8cde384fc7b7bChris Lattner } 13906f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1391a5ddb59a1319ccd23844c74809a64bc4d88f59d1Chris Lattner // And finally, do it! 1392fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Threading edge from '" << PredBB->getName() << "' to '" 1393460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar << SuccBB->getName() << "' with cost: " << JumpThreadCost 139493b67e40de356569493c285b86b138a3f11b5035Daniel Dunbar << ", across block:\n " 139593b67e40de356569493c285b86b138a3f11b5035Daniel Dunbar << *BB << "\n"); 13966f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1397c809d90bca41a5578012959ea2e493f9d949f969Owen Anderson LVI->threadEdge(PredBB, BB, SuccBB); 13986f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1399bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // We are going to have to map operands from the original BB block to the new 1400bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to 1401bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // account for entry from PredBB. 1402bd3401fa98b578080e227afce940bca80137dea6Chris Lattner DenseMap<Instruction*, Value*> ValueMapping; 14036f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 14046f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), 14056f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel BB->getName()+".thread", 14061d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BB->getParent(), BB); 1407bd3401fa98b578080e227afce940bca80137dea6Chris Lattner NewBB->moveAfter(PredBB); 14086f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1409bd3401fa98b578080e227afce940bca80137dea6Chris Lattner BasicBlock::iterator BI = BB->begin(); 1410bd3401fa98b578080e227afce940bca80137dea6Chris Lattner for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 1411bd3401fa98b578080e227afce940bca80137dea6Chris Lattner ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); 14126f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1413bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // Clone the non-phi instructions of BB into NewBB, keeping track of the 1414bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // mapping and using it to remap operands in the cloned instructions. 1415bd3401fa98b578080e227afce940bca80137dea6Chris Lattner for (; !isa<TerminatorInst>(BI); ++BI) { 14166776064d190701c5bae4d5403939eed2e480d1cdNick Lewycky Instruction *New = BI->clone(); 1417460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar New->setName(BI->getName()); 1418bd3401fa98b578080e227afce940bca80137dea6Chris Lattner NewBB->getInstList().push_back(New); 1419bd3401fa98b578080e227afce940bca80137dea6Chris Lattner ValueMapping[BI] = New; 14206f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1421bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // Remap operands to patch up intra-block references. 1422bd3401fa98b578080e227afce940bca80137dea6Chris Lattner for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) 1423f530c92cd55f35f64904e42e38b3a2bc92b347cbDan Gohman if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { 1424f530c92cd55f35f64904e42e38b3a2bc92b347cbDan Gohman DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 1425f530c92cd55f35f64904e42e38b3a2bc92b347cbDan Gohman if (I != ValueMapping.end()) 1426f530c92cd55f35f64904e42e38b3a2bc92b347cbDan Gohman New->setOperand(i, I->second); 1427f530c92cd55f35f64904e42e38b3a2bc92b347cbDan Gohman } 1428bd3401fa98b578080e227afce940bca80137dea6Chris Lattner } 14296f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1430bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // We didn't copy the terminator from BB over to NewBB, because there is now 1431bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // an unconditional jump to SuccBB. Insert the unconditional jump. 143295a7de6b916e49265ebdae04a32f6beda7f89028Devang Patel BranchInst *NewBI =BranchInst::Create(SuccBB, NewBB); 143395a7de6b916e49265ebdae04a32f6beda7f89028Devang Patel NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc()); 14346f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1435bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the 1436bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // PHI nodes for NewBB now. 143778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping); 14386f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1439433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // If there were values defined in BB that are used outside the block, then we 1440433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // now have to update all uses of the value to use either the original value, 1441433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // the cloned value, or some PHI derived value. This can require arbitrary 1442433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // PHI insertion, of which we are prepared to do, clean these up now. 1443433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner SSAUpdater SSAUpdate; 1444433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner SmallVector<Use*, 16> UsesToRename; 1445433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 1446433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // Scan all uses of this instruction to see if it is used outside of its 1447433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // block, and if so, record them in UsesToRename. 144836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Use &U : I->uses()) { 144936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *User = cast<Instruction>(U.getUser()); 1450433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 145136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UserPN->getIncomingBlock(U) == BB) 1452433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner continue; 1453433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner } else if (User->getParent() == BB) 1454433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner continue; 14556f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 145636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UsesToRename.push_back(&U); 1457433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner } 14586f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1459433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // If there are no uses outside the block, we're done with this instruction. 1460433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner if (UsesToRename.empty()) 1461433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner continue; 14626f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1463fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << "JT: Renaming non-local uses of: " << *I << "\n"); 1464433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner 1465433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // We found a use of I outside of BB. Rename all uses of I that are outside 1466433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks 1467433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner // with the two values we know. 1468fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands SSAUpdate.Initialize(I->getType(), I->getName()); 1469433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner SSAUpdate.AddAvailableValue(BB, I); 1470433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner SSAUpdate.AddAvailableValue(NewBB, ValueMapping[I]); 14716f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1472433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner while (!UsesToRename.empty()) 1473433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); 1474fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << "\n"); 1475433a0dbb262b16b42d75715a4dad618a475ba91bChris Lattner } 14766f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 14776f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1478ef0c6744d5050ad724e1ae90e6ac2b932ce01e13Chris Lattner // Ok, NewBB is good to go. Update the terminator of PredBB to jump to 1479bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // NewBB instead of BB. This eliminates predecessors from BB, which requires 1480bd3401fa98b578080e227afce940bca80137dea6Chris Lattner // us to simplify any PHI nodes in BB. 1481bd3401fa98b578080e227afce940bca80137dea6Chris Lattner TerminatorInst *PredTerm = PredBB->getTerminator(); 1482bd3401fa98b578080e227afce940bca80137dea6Chris Lattner for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) 1483bd3401fa98b578080e227afce940bca80137dea6Chris Lattner if (PredTerm->getSuccessor(i) == BB) { 148436c4debc94e7c68c769dfda781851a0c963dd746Owen Anderson BB->removePredecessor(PredBB, true); 1485bd3401fa98b578080e227afce940bca80137dea6Chris Lattner PredTerm->setSuccessor(i, NewBB); 1486bd3401fa98b578080e227afce940bca80137dea6Chris Lattner } 14876f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1488ef0c6744d5050ad724e1ae90e6ac2b932ce01e13Chris Lattner // At this point, the IR is fully up to date and consistent. Do a quick scan 1489ef0c6744d5050ad724e1ae90e6ac2b932ce01e13Chris Lattner // over the new instructions and zap any that are constants or dead. This 1490ef0c6744d5050ad724e1ae90e6ac2b932ce01e13Chris Lattner // frequently happens because of phi translation. 149136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SimplifyInstructionsInBlock(NewBB, DL, TLI); 14926f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1493fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump // Threaded an edge! 1494fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump ++NumThreads; 1495fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump return true; 1496177480b7ede0441135572d641a2497df25a7d95fChris Lattner} 149778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner 149878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch 149978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// to BB which contains an i1 PHI node and a conditional branch on that PHI. 150078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// If we can duplicate the contents of BB up into PredBB do so now, this 150178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// improves the odds that the branch will be on an analyzable instruction like 150278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner/// a compare. 150378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattnerbool JumpThreading::DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, 15042249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner const SmallVectorImpl<BasicBlock *> &PredBBs) { 15052249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner assert(!PredBBs.empty() && "Can't handle an empty set"); 15062249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner 150778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // If BB is a loop header, then duplicating this block outside the loop would 150878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // cause us to transform this into an irreducible loop, don't do this. 150978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // See the comments above FindLoopHeaders for justifications and caveats. 151078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (LoopHeaders.count(BB)) { 1511fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName() 15122249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner << "' into predecessor block '" << PredBBs[0]->getName() 151378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner << "' - it might create an irreducible loop!\n"); 151478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner return false; 151578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 15166f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1517c69908695af9cf509bf498a492854db5f0556e0fNadav Rotem unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, Threshold); 151878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (DuplicationCost > Threshold) { 1519fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Not duplicating BB '" << BB->getName() 152078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner << "' - Cost is too high: " << DuplicationCost << "\n"); 152178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner return false; 152278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 15236f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 15242249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // And finally, do it! Start by factoring the predecessors is needed. 15252249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner BasicBlock *PredBB; 15262249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner if (PredBBs.size() == 1) 15272249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner PredBB = PredBBs[0]; 15282249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner else { 15292249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner DEBUG(dbgs() << " Factoring out " << PredBBs.size() 15302249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner << " common predecessors.\n"); 15312fac1d5d61a83c45dcf44119c41dce15ef10e9dcJakub Staszak PredBB = SplitBlockPredecessors(BB, PredBBs, ".thr_comm", this); 15322249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner } 15336f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 153478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Okay, we decided to do this! Clone all the instructions in BB onto the end 153578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // of PredBB. 1536fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '" 153778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner << PredBB->getName() << "' to eliminate branch on phi. Cost: " 153878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner << DuplicationCost << " block is:" << *BB << "\n"); 15396f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 15402249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // Unless PredBB ends with an unconditional branch, split the edge so that we 15412249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner // can just clone the bits from BB into the end of the new PredBB. 1542d668839cb9b5db6865fd98e5e7dfccd64abf3e95Chris Lattner BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator()); 15436f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1544dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!OldPredBranch || !OldPredBranch->isUnconditional()) { 15452249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner PredBB = SplitEdge(PredBB, BB, this); 15462249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner OldPredBranch = cast<BranchInst>(PredBB->getTerminator()); 15472249a0b1bd0941e61c0b87f2f64a5c8cab45f14cChris Lattner } 15486f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 154978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // We are going to have to map operands from the original BB block into the 155078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // PredBB block. Evaluate PHI nodes in BB. 155178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner DenseMap<Instruction*, Value*> ValueMapping; 15526f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 155378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner BasicBlock::iterator BI = BB->begin(); 155478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 155578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); 15566f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 155778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Clone the non-phi instructions of BB into PredBB, keeping track of the 155878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // mapping and using it to remap operands in the cloned instructions. 155978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner for (; BI != BB->end(); ++BI) { 156078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner Instruction *New = BI->clone(); 15616f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 156278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Remap operands to patch up intra-block references. 156378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i) 156478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) { 156578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner DenseMap<Instruction*, Value*>::iterator I = ValueMapping.find(Inst); 156678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (I != ValueMapping.end()) 156778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner New->setOperand(i, I->second); 156878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 1569972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner 1570972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner // If this instruction can be simplified after the operands are updated, 1571972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner // just use the simplified value instead. This frequently happens due to 1572972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner // phi translation. 157336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *IV = SimplifyInstruction(New, DL)) { 1574972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner delete New; 1575972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner ValueMapping[BI] = IV; 1576972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner } else { 1577972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner // Otherwise, insert the new instruction into the block. 1578972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner New->setName(BI->getName()); 1579972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner PredBB->getInstList().insert(OldPredBranch, New); 1580972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner ValueMapping[BI] = New; 1581972a46c96a06ecb0e8ce73c796c313175abe76bbChris Lattner } 158278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 15836f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 158478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Check to see if the targets of the branch had PHI nodes. If so, we need to 158578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // add entries to the PHI nodes for branch from PredBB now. 158678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator()); 158778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB, 158878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner ValueMapping); 158978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB, 159078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner ValueMapping); 15916f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 159278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // If there were values defined in BB that are used outside the block, then we 159378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // now have to update all uses of the value to use either the original value, 159478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // the cloned value, or some PHI derived value. This can require arbitrary 159578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // PHI insertion, of which we are prepared to do, clean these up now. 159678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner SSAUpdater SSAUpdate; 159778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner SmallVector<Use*, 16> UsesToRename; 159878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 159978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Scan all uses of this instruction to see if it is used outside of its 160078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // block, and if so, record them in UsesToRename. 160136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Use &U : I->uses()) { 160236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *User = cast<Instruction>(U.getUser()); 160378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 160436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UserPN->getIncomingBlock(U) == BB) 160578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner continue; 160678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } else if (User->getParent() == BB) 160778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner continue; 16086f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 160936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UsesToRename.push_back(&U); 161078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 16116f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 161278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // If there are no uses outside the block, we're done with this instruction. 161378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner if (UsesToRename.empty()) 161478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner continue; 16156f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 1616fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << "JT: Renaming non-local uses of: " << *I << "\n"); 16176f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 161878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // We found a use of I outside of BB. Rename all uses of I that are outside 161978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks 162078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // with the two values we know. 1621fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands SSAUpdate.Initialize(I->getType(), I->getName()); 162278c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner SSAUpdate.AddAvailableValue(BB, I); 162378c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner SSAUpdate.AddAvailableValue(PredBB, ValueMapping[I]); 16246f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 162578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner while (!UsesToRename.empty()) 162678c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); 1627fe7fe6603fea2ca121282cd329f5300ea7d9fd51David Greene DEBUG(dbgs() << "\n"); 162878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner } 16296f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 163078c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // PredBB no longer jumps to BB, remove entries in the PHI node for the edge 163178c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // that we nuked. 163236c4debc94e7c68c769dfda781851a0c963dd746Owen Anderson BB->removePredecessor(PredBB, true); 16336f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 163478c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner // Remove the unconditional branch at the end of the PredBB block. 163578c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner OldPredBranch->eraseFromParent(); 16366f9a8307e087110d57b1e63dae154d351f6b0f6bFrits van Bommel 163778c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner ++NumDupes; 163878c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner return true; 163978c552ef309eb8c47d12aac2c0b3af7849c27ce9Chris Lattner} 1640c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 1641c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// TryToUnfoldSelect - Look for blocks of the form 1642c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// bb1: 1643c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// %a = select 1644c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// br bb 1645c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// 1646c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// bb2: 1647c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// %p = phi [%a, %bb] ... 1648c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// %c = icmp %p 1649c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// br i1 %c 1650c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// 1651c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// And expand the select into a branch structure if one of its arms allows %c 1652c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer/// to be folded. This later enables threading from bb1 over bb2. 1653c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramerbool JumpThreading::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { 1654c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator()); 1655c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0)); 1656c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1)); 1657c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 1658c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer if (!CondBr || !CondBr->isConditional() || !CondLHS || 1659c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer CondLHS->getParent() != BB) 1660c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer return false; 1661c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 1662c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) { 1663c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer BasicBlock *Pred = CondLHS->getIncomingBlock(I); 1664c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I)); 1665c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 1666c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // Look if one of the incoming values is a select in the corresponding 1667c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // predecessor. 1668c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer if (!SI || SI->getParent() != Pred || !SI->hasOneUse()) 1669c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer continue; 1670c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 1671c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator()); 1672c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer if (!PredTerm || !PredTerm->isUnconditional()) 1673c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer continue; 1674c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 1675c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // Now check if one of the select values would allow us to constant fold the 1676c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // terminator in BB. We don't do the transform if both sides fold, those 1677c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // cases will be threaded in any case. 1678c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer LazyValueInfo::Tristate LHSFolds = 1679c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1), 1680c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer CondRHS, Pred, BB); 1681c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer LazyValueInfo::Tristate RHSFolds = 1682c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2), 1683c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer CondRHS, Pred, BB); 1684c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer if ((LHSFolds != LazyValueInfo::Unknown || 1685c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer RHSFolds != LazyValueInfo::Unknown) && 1686c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer LHSFolds != RHSFolds) { 1687c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // Expand the select. 1688c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // 1689c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // Pred -- 1690c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // | v 1691c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // | NewBB 1692c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // | | 1693c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // |----- 1694c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // v 1695c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // BB 1696c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold", 1697c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer BB->getParent(), BB); 1698c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // Move the unconditional branch to NewBB. 1699c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer PredTerm->removeFromParent(); 1700c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer NewBB->getInstList().insert(NewBB->end(), PredTerm); 1701c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // Create a conditional branch and update PHI nodes. 1702c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer BranchInst::Create(NewBB, BB, SI->getCondition(), Pred); 1703c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer CondLHS->setIncomingValue(I, SI->getFalseValue()); 1704c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer CondLHS->addIncoming(SI->getTrueValue(), NewBB); 1705c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // The select is now dead. 1706c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer SI->eraseFromParent(); 1707c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer 1708c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer // Update any other PHI nodes in BB. 1709c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer for (BasicBlock::iterator BI = BB->begin(); 1710c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer PHINode *Phi = dyn_cast<PHINode>(BI); ++BI) 1711c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer if (Phi != CondLHS) 1712c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB); 1713c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer return true; 1714c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer } 1715c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer } 1716c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer return false; 1717c11b107f21f8f1baf1021999fc7d01b93e00922bBenjamin Kramer} 1718