14d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===-- Local.cpp - Functions to perform local transformations ------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 94d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 104d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// This family of functions perform various local transformations to the 114d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// program. 124d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 134d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 144d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 154d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner#include "llvm/Transforms/Utils/Local.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 173333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov#include "llvm/ADT/STLExtras.h" 1858a2cbef4aac9ee7d530dfb690c78d6fc11a2371Chandler Carruth#include "llvm/ADT/SmallPtrSet.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/MemoryBuiltins.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ProfileInfo.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ValueTracking.h" 2406cb8ed00696eb14d1b831921452e50ec0568ea2Chandler Carruth#include "llvm/DIBuilder.h" 250bcbd1df7a204e1e512f1a27066d725309de1b13Bill Wendling#include "llvm/DebugInfo.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalAlias.h" 300b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IRBuilder.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 340b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Intrinsics.h" 350b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/MDBuilder.h" 360b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 370b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 38dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner#include "llvm/Support/CFG.h" 39dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner#include "llvm/Support/Debug.h" 40c5f52e6da18e6e8ccb62aac2a4cb431df98e7d6dChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 41c5f52e6da18e6e8ccb62aac2a4cb431df98e7d6dChris Lattner#include "llvm/Support/MathExtras.h" 4219f2dc436df4f768484287a478973e83efd4202aChris Lattner#include "llvm/Support/ValueHandle.h" 43dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner#include "llvm/Support/raw_ostream.h" 44abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattnerusing namespace llvm; 45d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 464d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 473481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local constant propagation. 484d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 494d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 505649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// ConstantFoldTerminator - If a terminator instruction is predicated on a 515649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// constant value, convert it into an unconditional branch to the constant 525649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// destination. This is a nontrivial operation because the successors of this 535649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// basic block must have their PHI nodes updated. 545649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 555649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// conditions and indirectbr addresses this might make dead if 565649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// DeleteDeadConditions is true. 578e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 588e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 5976ae3445f81164aaff9f95123426109c119f27c0Chris Lattner TerminatorInst *T = BB->getTerminator(); 6062fb3556eab41d9d66994e92d15e3e707c181988Devang Patel IRBuilder<> Builder(T); 61fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 624d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Branch - See if we are conditional jumping on constant 634d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 644d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (BI->isUnconditional()) return false; // Can't optimize uncond branch 65c1bb13f1b8794aa6f3219b3ac567f569ad78a6d1Gabor Greif BasicBlock *Dest1 = BI->getSuccessor(0); 66c1bb13f1b8794aa6f3219b3ac567f569ad78a6d1Gabor Greif BasicBlock *Dest2 = BI->getSuccessor(1); 674d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 686b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 694d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Are we branching on constant? 704d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // YES. Change to unconditional branch... 71579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 72579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 734d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 74fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman //cerr << "Function: " << T->getParent()->getParent() 75fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // << "\nRemoving branch from " << T->getParent() 764d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // << "\n\nTo: " << OldDest << endl; 774d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 784d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Let the basic block know that we are letting go of it. Based on this, 794d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // it will adjust it's PHI nodes. 801a0390253b3e7c2327139d81e5a8c16d5bf85aa8Jay Foad OldDest->removePredecessor(BB); 814d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 828f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad // Replace the conditional branch with an unconditional one. 8362fb3556eab41d9d66994e92d15e3e707c181988Devang Patel Builder.CreateBr(Destination); 848f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad BI->eraseFromParent(); 854d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner return true; 860a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 870a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 880a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (Dest2 == Dest1) { // Conditional branch to same location? 89fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // This branch matches something like this: 904d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // br bool %cond, label %Dest, label %Dest 914d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // and changes it into: br label %Dest 924d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 934d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Let the basic block know that we are letting go of one copy of it. 944d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner assert(BI->getParent() && "Terminator not inserted in block!"); 954d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner Dest1->removePredecessor(BI->getParent()); 964d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 978f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad // Replace the conditional branch with an unconditional one. 9862fb3556eab41d9d66994e92d15e3e707c181988Devang Patel Builder.CreateBr(Dest1); 995649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel Value *Cond = BI->getCondition(); 1008f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad BI->eraseFromParent(); 1015649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel if (DeleteDeadConditions) 1028e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 1034d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner return true; 1044d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner } 1050a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner return false; 1060a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 1070a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 1080a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 10910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // If we are switching on a constant, we can convert the switch into a 11010b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // single branch instruction! 11110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 112c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy BasicBlock *TheOnlyDest = SI->getDefaultDest(); 1137d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner BasicBlock *DefaultDest = TheOnlyDest; 11410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 1150a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Figure out which case it goes to. 1163d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 117c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy i != e; ++i) { 11810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Found case matching a constant operand? 119c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy if (i.getCaseValue() == CI) { 120c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy TheOnlyDest = i.getCaseSuccessor(); 12110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner break; 12210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 12310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 1247d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner // Check to see if this branch is going to the same place as the default 1257d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner // dest. If so, eliminate it as an explicit compare. 126c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy if (i.getCaseSuccessor() == DefaultDest) { 127ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); 128ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren // MD should have 2 + NumCases operands. 129ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren if (MD && MD->getNumOperands() == 2 + SI->getNumCases()) { 130ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren // Collect branch weights into a vector. 131ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren SmallVector<uint32_t, 8> Weights; 132ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 133ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren ++MD_i) { 134ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i)); 135ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren assert(CI); 136ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren Weights.push_back(CI->getValue().getZExtValue()); 137ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren } 138ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren // Merge weight of this case to the default weight. 139ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren unsigned idx = i.getCaseIndex(); 140ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren Weights[0] += Weights[idx+1]; 141ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren // Remove weight for this case. 142ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren std::swap(Weights[idx+1], Weights.back()); 143ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren Weights.pop_back(); 144ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren SI->setMetadata(LLVMContext::MD_prof, 145ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren MDBuilder(BB->getContext()). 146ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren createBranchWeights(Weights)); 147ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren } 1480a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Remove this entry. 1497d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner DefaultDest->removePredecessor(SI->getParent()); 1507d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner SI->removeCase(i); 151c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy --i; --e; 1527d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner continue; 1537d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner } 1547d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner 15510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Otherwise, check to see if the switch only branches to one destination. 15610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // We do this by reseting "TheOnlyDest" to null when we find two non-equal 15710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // destinations. 158c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = 0; 15910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 160694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 16110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (CI && !TheOnlyDest) { 16210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Branching on a constant, but not any of the cases, go to the default 16310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // successor. 16410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner TheOnlyDest = SI->getDefaultDest(); 165694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner } 166694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 16710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // If we found a single destination that we can fold the switch into, do so 16810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // now. 16910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (TheOnlyDest) { 1700a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Insert the new branch. 17162fb3556eab41d9d66994e92d15e3e707c181988Devang Patel Builder.CreateBr(TheOnlyDest); 17210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BasicBlock *BB = SI->getParent(); 17310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 17410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Remove entries from PHI nodes which we no longer branch to... 17510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 17610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Found case matching a constant operand? 17710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BasicBlock *Succ = SI->getSuccessor(i); 17810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (Succ == TheOnlyDest) 17910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 18010b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner else 18110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner Succ->removePredecessor(BB); 18210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 18310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 1840a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Delete the old switch. 1855649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel Value *Cond = SI->getCondition(); 1865649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel SI->eraseFromParent(); 1875649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel if (DeleteDeadConditions) 1888e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 18910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner return true; 1900a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 1910a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 19224473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy if (SI->getNumCases() == 1) { 19310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Otherwise, we can fold this switch into a conditional branch 19410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // instruction if it has only one non-default destination. 1953d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy SwitchInst::CaseIt FirstCase = SI->case_begin(); 19647cbc4e0ee6098b7be3c60108000a979f1809949Stepan Dyatkovskiy IntegersSubset& Case = FirstCase.getCaseValueEx(); 19747cbc4e0ee6098b7be3c60108000a979f1809949Stepan Dyatkovskiy if (Case.isSingleNumber()) { 198484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy // FIXME: Currently work with ConstantInt based numbers. 199a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 20047cbc4e0ee6098b7be3c60108000a979f1809949Stepan Dyatkovskiy Case.getSingleNumber(0).toConstantInt(), 201484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy "cond"); 202a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy 203a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy // Insert the new branch. 204ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren BranchInst *NewBr = Builder.CreateCondBr(Cond, 205ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren FirstCase.getCaseSuccessor(), 206ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren SI->getDefaultDest()); 207ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); 208ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren if (MD && MD->getNumOperands() == 3) { 209ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2)); 210ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1)); 211ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren assert(SICase && SIDef); 212ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren // The TrueWeight should be the weight for the single case of SI. 213ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren NewBr->setMetadata(LLVMContext::MD_prof, 214ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren MDBuilder(BB->getContext()). 215ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren createBranchWeights(SICase->getValue().getZExtValue(), 216ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren SIDef->getValue().getZExtValue())); 217ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren } 218a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy 219a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy // Delete the old switch. 220a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy SI->eraseFromParent(); 221a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy return true; 222a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy } 22310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 2240a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner return false; 2250a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2260a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2270a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 2280a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // indirectbr blockaddress(@F, @BB) -> br label @BB 2290a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (BlockAddress *BA = 2300a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 2310a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner BasicBlock *TheOnlyDest = BA->getBasicBlock(); 2320a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Insert the new branch. 23362fb3556eab41d9d66994e92d15e3e707c181988Devang Patel Builder.CreateBr(TheOnlyDest); 2340a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2350a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 2360a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (IBI->getDestination(i) == TheOnlyDest) 2370a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner TheOnlyDest = 0; 2380a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner else 2390a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner IBI->getDestination(i)->removePredecessor(IBI->getParent()); 2400a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2415649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel Value *Address = IBI->getAddress(); 2420a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner IBI->eraseFromParent(); 2435649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel if (DeleteDeadConditions) 2448e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); 2450a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2460a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // If we didn't find our destination in the IBI successor list, then we 2470a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // have undefined behavior. Replace the unconditional branch with an 2480a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // 'unreachable' instruction. 2490a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (TheOnlyDest) { 2500a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner BB->getTerminator()->eraseFromParent(); 2510a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner new UnreachableInst(BB->getContext(), BB); 2520a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2530a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2540a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner return true; 2550a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2564d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner } 2570a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2584d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner return false; 2594d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 2604d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2614d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2624d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 26340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner// Local dead code elimination. 2644d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 2654d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2663481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// isInstructionTriviallyDead - Return true if the result produced by the 2673481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// instruction is not used, and the instruction has no side effects. 2683481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// 2698e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isInstructionTriviallyDead(Instruction *I, 2708e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 271ec710c5b12af647ae90f53917122726269c18738Chris Lattner if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 27200b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 273187b1924a4b68350a6492b116db0fb19c659222fBill Wendling // We don't want the landingpad instruction removed by anything this general. 274187b1924a4b68350a6492b116db0fb19c659222fBill Wendling if (isa<LandingPadInst>(I)) 275187b1924a4b68350a6492b116db0fb19c659222fBill Wendling return false; 276187b1924a4b68350a6492b116db0fb19c659222fBill Wendling 2779c5822a966572ea78f4e818870d4229c7a855749Devang Patel // We don't want debug info removed by anything this general, unless 2789c5822a966572ea78f4e818870d4229c7a855749Devang Patel // debug info is empty. 2799c5822a966572ea78f4e818870d4229c7a855749Devang Patel if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 2803e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky if (DDI->getAddress()) 2819c5822a966572ea78f4e818870d4229c7a855749Devang Patel return false; 282b99462117ebd4be41788346246d7935fc90a11eeDevang Patel return true; 2833e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky } 284b99462117ebd4be41788346246d7935fc90a11eeDevang Patel if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 2859c5822a966572ea78f4e818870d4229c7a855749Devang Patel if (DVI->getValue()) 2869c5822a966572ea78f4e818870d4229c7a855749Devang Patel return false; 287b99462117ebd4be41788346246d7935fc90a11eeDevang Patel return true; 2889c5822a966572ea78f4e818870d4229c7a855749Devang Patel } 2899c5822a966572ea78f4e818870d4229c7a855749Devang Patel 2907af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands if (!I->mayHaveSideEffects()) return true; 2917af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands 2927af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands // Special case intrinsics that "may have side effects" but can be deleted 2937af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands // when dead. 2943e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 295741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner // Safe to delete llvm.stacksave if dead. 296741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner if (II->getIntrinsicID() == Intrinsic::stacksave) 297741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner return true; 2983e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky 2993e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky // Lifetime intrinsics are dead when their right-hand is undef. 3003e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky if (II->getIntrinsicID() == Intrinsic::lifetime_start || 3013e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky II->getIntrinsicID() == Intrinsic::lifetime_end) 3023e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky return isa<UndefValue>(II->getArgOperand(1)); 3033e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky } 3044a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky 3058e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isAllocLikeFn(I, TLI)) return true; 3064a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky 3078e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (CallInst *CI = isFreeCall(I, TLI)) 3084a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 3094a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky return C->isNullValue() || isa<UndefValue>(C); 3104a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky 311ec710c5b12af647ae90f53917122726269c18738Chris Lattner return false; 3124d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 3134d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 3143481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 3153481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// trivially dead instruction, delete it. If that makes any of its operands 31690fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman/// trivially dead, delete them too, recursively. Return true if any 31790fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman/// instructions were deleted. 3188e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool 3198e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerllvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 3208e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 3213481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner Instruction *I = dyn_cast<Instruction>(V); 3228e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI)) 32390fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman return false; 3243481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 3257605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner SmallVector<Instruction*, 16> DeadInsts; 3267605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner DeadInsts.push_back(I); 3273481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 328321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman do { 329e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman I = DeadInsts.pop_back_val(); 3302872177834d83b42cd042a37299cb7089965f36bChris Lattner 3317605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // Null out all of the instruction's operands to see if any operand becomes 3327605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // dead as we go. 3337605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 3347605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner Value *OpV = I->getOperand(i); 3357605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner I->setOperand(i, 0); 3367605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 3377605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner if (!OpV->use_empty()) continue; 3387605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 3397605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // If the operand is an instruction that became dead as we nulled out the 3407605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // operand, and if it is 'trivially' dead, delete it in a future loop 3417605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // iteration. 3427605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 3438e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isInstructionTriviallyDead(OpI, TLI)) 3447605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner DeadInsts.push_back(OpI); 3457605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner } 3467605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 3477605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner I->eraseFromParent(); 348321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman } while (!DeadInsts.empty()); 34990fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman 35090fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman return true; 3514d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 352b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 3531a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky/// areAllUsesEqual - Check whether the uses of a value are all the same. 3541a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky/// This is similar to Instruction::hasOneUse() except this will also return 355b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands/// true when there are no uses or multiple uses that all refer to the same 356b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands/// value. 3571a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewyckystatic bool areAllUsesEqual(Instruction *I) { 3581a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky Value::use_iterator UI = I->use_begin(); 3591a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky Value::use_iterator UE = I->use_end(); 3601a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky if (UI == UE) 361b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands return true; 3621a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky 3631a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky User *TheUse = *UI; 3641a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky for (++UI; UI != UE; ++UI) { 3651a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky if (*UI != TheUse) 3661a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky return false; 3671a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky } 3681a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky return true; 3691a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky} 3701a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky 371afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 372afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// dead PHI node, due to being a def-use chain of single-use nodes that 373afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// either forms a cycle or is terminated by a trivially dead instruction, 374afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// delete it. If that makes any of its operands trivially dead, delete them 3752cfbf018a938d14126b9cb10c600e025f9831d2dDuncan Sands/// too, recursively. Return true if a change was made. 3768e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, 3778e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 378b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands SmallPtrSet<Instruction*, 4> Visited; 379b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 380b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands I = cast<Instruction>(*I->use_begin())) { 381b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands if (I->use_empty()) 3828e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 383afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 384b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands // If we find an instruction more than once, we're on a cycle that 385afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // won't prove fruitful. 386b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands if (!Visited.insert(I)) { 387b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands // Break the cycle and delete the instruction and its operands. 388b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands I->replaceAllUsesWith(UndefValue::get(I->getType())); 3898e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 3902cfbf018a938d14126b9cb10c600e025f9831d2dDuncan Sands return true; 391b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands } 392b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands } 393b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands return false; 394afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman} 3953481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 396e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 397e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// simplify any instructions in it and recursively delete dead instructions. 398e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// 399e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// This returns true if it changed the code, note that it can delete 400e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// instructions in other blocks as well in this block. 4013574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowbool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD, 4028e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 403e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner bool MadeChange = false; 404acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth 405acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth#ifndef NDEBUG 406acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth // In debug builds, ensure that the terminator of the block is never replaced 407acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth // or deleted by these simplifications. The idea of simplification is that it 408acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth // cannot introduce new instructions, and there is no way to replace the 409acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth // terminator of a block without introducing a new instruction. 410acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth AssertingVH<Instruction> TerminatorVH(--BB->end()); 411acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth#endif 412acdae3e25a03e4e08039cb18f50b7788f71c0b2eChandler Carruth 413858cd1c33c6ba47cf3401b1e00862aa22302af10Chandler Carruth for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) { 414858cd1c33c6ba47cf3401b1e00862aa22302af10Chandler Carruth assert(!BI->isTerminator()); 415e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner Instruction *Inst = BI++; 4166b980541df5846ad335c377c8803b517968daee2Chandler Carruth 4176b980541df5846ad335c377c8803b517968daee2Chandler Carruth WeakVH BIHandle(BI); 4186b980541df5846ad335c377c8803b517968daee2Chandler Carruth if (recursivelySimplifyInstruction(Inst, TD)) { 419e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner MadeChange = true; 42035a939b97dba538bfc12010b7ac26bffbf5ec4cbChris Lattner if (BIHandle != BI) 421e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner BI = BB->begin(); 422e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner continue; 423e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner } 42471ad2c9eda710bc26ec1621a9afefad11dd7fad2Eli Friedman 4258e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); 42671ad2c9eda710bc26ec1621a9afefad11dd7fad2Eli Friedman if (BIHandle != BI) 42771ad2c9eda710bc26ec1621a9afefad11dd7fad2Eli Friedman BI = BB->begin(); 428e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner } 429e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner return MadeChange; 430e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner} 431e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner 432b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner//===----------------------------------------------------------------------===// 43340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner// Control Flow Graph Restructuring. 434b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner// 435b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 43640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner 43740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 43840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// method is called when we're about to delete Pred as a predecessor of BB. If 43940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 44040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 44140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 44240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// nodes that collapse into identity values. For example, if we have: 44340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// x = phi(1, 0, 0, 0) 44440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// y = and x, z 44540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 44640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// .. and delete the predecessor corresponding to the '1', this will attempt to 44740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursively fold the and to 0. 44840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 4493574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow DataLayout *TD) { 45040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // This only adjusts blocks with PHI nodes. 45140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner if (!isa<PHINode>(BB->begin())) 45240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner return; 45340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner 45440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 45540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // them down. This will leave us with single entry phi nodes and other phis 45640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // that can be removed. 45740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner BB->removePredecessor(Pred, true); 45840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner 45940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH PhiIt = &BB->front(); 46040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 46140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 4626b980541df5846ad335c377c8803b517968daee2Chandler Carruth Value *OldPhiIt = PhiIt; 4636ac3386e100db376895dbc4a324d56d0ecd666d2Duncan Sands 4646b980541df5846ad335c377c8803b517968daee2Chandler Carruth if (!recursivelySimplifyInstruction(PN, TD)) 4656b980541df5846ad335c377c8803b517968daee2Chandler Carruth continue; 4666ac3386e100db376895dbc4a324d56d0ecd666d2Duncan Sands 46740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // If recursive simplification ended up deleting the next PHI node we would 46840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // iterate to, then our iterator is invalid, restart scanning from the top 46940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // of the block. 47035a939b97dba538bfc12010b7ac26bffbf5ec4cbChris Lattner if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 47140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 47240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 47340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner 47440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner 475b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 476b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// predecessor is known to have one successor (DestBB!). Eliminate the edge 477b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// between them, moving the instructions in the predecessor into DestBB and 478b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// deleting the predecessor block. 479b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// 480ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustiftervoid llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 481b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // If BB has single-entry PHI nodes, fold them. 482b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 483b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner Value *NewVal = PN->getIncomingValue(0); 484b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // Replace self referencing PHI with undef, it must be dead. 4859e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 486b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PN->replaceAllUsesWith(NewVal); 487b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PN->eraseFromParent(); 488b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner } 489b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 490b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner BasicBlock *PredBB = DestBB->getSinglePredecessor(); 491b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner assert(PredBB && "Block doesn't have a single predecessor!"); 492b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 49337914c8e83c43d710925263b66014159f03fa355Chris Lattner // Zap anything that took the address of DestBB. Not doing this will give the 49437914c8e83c43d710925263b66014159f03fa355Chris Lattner // address an invalid value. 49537914c8e83c43d710925263b66014159f03fa355Chris Lattner if (DestBB->hasAddressTaken()) { 49637914c8e83c43d710925263b66014159f03fa355Chris Lattner BlockAddress *BA = BlockAddress::get(DestBB); 49737914c8e83c43d710925263b66014159f03fa355Chris Lattner Constant *Replacement = 49837914c8e83c43d710925263b66014159f03fa355Chris Lattner ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); 49937914c8e83c43d710925263b66014159f03fa355Chris Lattner BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 50037914c8e83c43d710925263b66014159f03fa355Chris Lattner BA->getType())); 50137914c8e83c43d710925263b66014159f03fa355Chris Lattner BA->destroyConstant(); 50237914c8e83c43d710925263b66014159f03fa355Chris Lattner } 503b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 504b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // Anything that branched to PredBB now branches to DestBB. 505b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PredBB->replaceAllUsesWith(DestBB); 506b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 50795c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // Splice all the instructions from PredBB to DestBB. 50895c3e48f9557adb6064d580684bb14cacec2f826Jay Foad PredBB->getTerminator()->eraseFromParent(); 50995c3e48f9557adb6064d580684bb14cacec2f826Jay Foad DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 51095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad 511ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter if (P) { 51280f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); 51380f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich if (DT) { 51480f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); 51580f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->changeImmediateDominator(DestBB, PredBBIDom); 51680f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich DT->eraseNode(PredBB); 51780f6a507d4e11ba066ad0e53e12ad25ad8cf07baCameron Zwarich } 518ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 519ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter if (PI) { 520ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter PI->replaceAllUses(PredBB, DestBB); 521ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); 522ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 523ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 524b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // Nuke BB. 525b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PredBB->eraseFromParent(); 526b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner} 5274afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 528dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 529dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// almost-empty BB ending in an unconditional branch to Succ, into succ. 530dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// 531dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// Assumption: Succ is the single successor for BB. 532dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// 533dce94d92df77da125a1c1256a9294db891a9db9cChris Lattnerstatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 534dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 535dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 536fae7706dfd3591391c03ed1439850edaed9d291cDavid Greene DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 537dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner << Succ->getName() << "\n"); 538dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Shortcut, if there is only a single predecessor it must be BB and merging 539dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // is always safe 540dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (Succ->getSinglePredecessor()) return true; 541dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 542dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Make a list of the predecessors of BB 54388c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 544dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 545dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Look at all the phi nodes in Succ, to see if they present a conflict when 546dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // merging these blocks 547dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 548dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner PHINode *PN = cast<PHINode>(I); 549dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 550dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // If the incoming value from BB is again a PHINode in 551dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // BB which has the same incoming value for *PI as PN does, we can 552dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // merge the phi nodes and then the blocks can still be merged 553dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 554dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (BBPN && BBPN->getParent() == BB) { 55588c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 55688c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer BasicBlock *IBB = PN->getIncomingBlock(PI); 55788c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer if (BBPreds.count(IBB) && 55888c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer BBPN->getIncomingValueForBlock(IBB) != PN->getIncomingValue(PI)) { 559fae7706dfd3591391c03ed1439850edaed9d291cDavid Greene DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 560dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner << Succ->getName() << " is conflicting with " 561dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner << BBPN->getName() << " with regard to common predecessor " 56288c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer << IBB->getName() << "\n"); 563dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner return false; 564dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 565dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 566dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } else { 567dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner Value* Val = PN->getIncomingValueForBlock(BB); 56888c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 569dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // See if the incoming value for the common predecessor is equal to the 570dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // one for BB, in which case this phi node will not prevent the merging 571dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // of the block. 57288c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer BasicBlock *IBB = PN->getIncomingBlock(PI); 57388c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer if (BBPreds.count(IBB) && Val != PN->getIncomingValue(PI)) { 574fae7706dfd3591391c03ed1439850edaed9d291cDavid Greene DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 575dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner << Succ->getName() << " is conflicting with regard to common " 57688c09143b6af07ed7b16381885a03c4b10886f96Benjamin Kramer << "predecessor " << IBB->getName() << "\n"); 577dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner return false; 578dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 579dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 580dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 581dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 582dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 583dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner return true; 584dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner} 585dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 586dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 587dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// unconditional branch, and contains no instructions other than PHI nodes, 58877a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola/// potential side-effect free intrinsics and the branch. If possible, 58977a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola/// eliminate BB by rewriting all the predecessors to branch to the successor 59077a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola/// block and return true. If we can't transform, return false. 591dce94d92df77da125a1c1256a9294db891a9db9cChris Lattnerbool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 592e2c6d131d12c779a410740e0a90545def75e0f48Dan Gohman assert(BB != &BB->getParent()->getEntryBlock() && 593e2c6d131d12c779a410740e0a90545def75e0f48Dan Gohman "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 594e2c6d131d12c779a410740e0a90545def75e0f48Dan Gohman 595dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // We can't eliminate infinite loops. 596dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 597dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (BB == Succ) return false; 598dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 599dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Check to see if merging these blocks would cause conflicts for any of the 600dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // phi nodes in BB or Succ. If not, we can safely merge. 601dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 602dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 603dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Check for cases where Succ has multiple predecessors and a PHI node in BB 604dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // has uses which will not disappear when the PHI nodes are merged. It is 605dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // possible to handle such cases, but difficult: it requires checking whether 606dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // BB dominates Succ, which is non-trivial to calculate in the case where 607dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Succ has multiple predecessors. Also, it requires checking whether 6083a19999413b18304d1a00cbdbe73fc43ea9cb75fAlexey Samsonov // constructing the necessary self-referential PHI node doesn't introduce any 609dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // conflicts; this isn't too difficult, but the previous code for doing this 610dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // was incorrect. 611dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // 612dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Note that if this check finds a live use, BB dominates Succ, so BB is 613dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // something like a loop pre-header (or rarely, a part of an irreducible CFG); 614dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // folding the branch isn't profitable in that case anyway. 615dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (!Succ->getSinglePredecessor()) { 616dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner BasicBlock::iterator BBI = BB->begin(); 617dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner while (isa<PHINode>(*BBI)) { 618dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 619dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner UI != E; ++UI) { 620dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (PHINode* PN = dyn_cast<PHINode>(*UI)) { 621dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (PN->getIncomingBlock(UI) != BB) 622dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner return false; 623dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } else { 624dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner return false; 625dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 626dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 627dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner ++BBI; 628dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 629dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 630dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 631fae7706dfd3591391c03ed1439850edaed9d291cDavid Greene DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 632dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 633dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (isa<PHINode>(Succ->begin())) { 634dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // If there is more than one pred of succ, and there are PHI nodes in 635dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // the successor, then we need to add incoming edges for the PHI nodes 636dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // 637dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 638dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 639dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Loop over all of the PHI nodes in the successor of BB. 640dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 641dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner PHINode *PN = cast<PHINode>(I); 642dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner Value *OldVal = PN->removeIncomingValue(BB, false); 643dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner assert(OldVal && "No entry in PHI for Pred BB!"); 644dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 645dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // If this incoming value is one of the PHI nodes in BB, the new entries 646dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // in the PHI node are the entries from the old PHI. 647dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 648dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner PHINode *OldValPN = cast<PHINode>(OldVal); 649dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 650dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Note that, since we are merging phi nodes and BB and Succ might 651dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // have common predecessors, we could end up with a phi node with 652dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // identical incoming branches. This will be cleaned up later (and 653dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // will trigger asserts if we try to clean it up now, without also 654dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // simplifying the corresponding conditional branch). 655dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner PN->addIncoming(OldValPN->getIncomingValue(i), 656dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner OldValPN->getIncomingBlock(i)); 657dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } else { 658dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Add an incoming value for each of the new incoming values. 659dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) 660dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner PN->addIncoming(OldVal, BBPreds[i]); 661dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 662dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 663dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 664dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 66577a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola if (Succ->getSinglePredecessor()) { 66677a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola // BB is the only predecessor of Succ, so Succ will end up with exactly 66777a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola // the same predecessors BB had. 66877a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola 66977a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola // Copy over any phi, debug or lifetime instruction. 67077a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola BB->getTerminator()->eraseFromParent(); 67177a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); 67277a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola } else { 67377a2c372face15a302f4c9e5cb9acc035b8b3bd3Rafael Espindola while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 674dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 675dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner assert(PN->use_empty() && "There shouldn't be any uses here!"); 676dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner PN->eraseFromParent(); 677dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 678dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner } 679dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 680dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner // Everything that jumped to BB now goes to Succ. 681dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner BB->replaceAllUsesWith(Succ); 682dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (!Succ->hasName()) Succ->takeName(BB); 683dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner BB->eraseFromParent(); // Delete the old basic block. 684dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner return true; 685dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner} 686dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 68743a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 68843a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach/// nodes in this block. This doesn't try to be clever about PHI nodes 68943a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach/// which differ only in the order of the incoming values, but instcombine 69043a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach/// orders them so it usually won't matter. 69143a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach/// 69243a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbachbool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 69343a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach bool Changed = false; 69443a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach 69543a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // This implementation doesn't currently consider undef operands 69689991d44136414c4c74eee7c6dfbdbeab287b881Nick Lewycky // specially. Theoretically, two phis which are identical except for 69743a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // one having an undef where the other doesn't could be collapsed. 69843a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach 69943a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // Map from PHI hash values to PHI nodes. If multiple PHIs have 70043a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // the same hash value, the element is the first PHI in the 70143a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // linked list in CollisionMap. 70243a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach DenseMap<uintptr_t, PHINode *> HashMap; 70343a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach 70443a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // Maintain linked lists of PHI nodes with common hash values. 70543a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach DenseMap<PHINode *, PHINode *> CollisionMap; 70643a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach 70743a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // Examine each PHI. 70843a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach for (BasicBlock::iterator I = BB->begin(); 70943a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach PHINode *PN = dyn_cast<PHINode>(I++); ) { 71043a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // Compute a hash value on the operands. Instcombine will likely have sorted 71143a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // them, which helps expose duplicates, but we have to check all the 71243a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // operands to be safe in case instcombine hasn't run. 71343a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach uintptr_t Hash = 0; 71495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // This hash algorithm is quite weak as hash functions go, but it seems 71595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad // to do a good enough job for this particular purpose, and is very quick. 71643a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { 71743a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); 71843a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 71943a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach } 72095c3e48f9557adb6064d580684bb14cacec2f826Jay Foad for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); 72195c3e48f9557adb6064d580684bb14cacec2f826Jay Foad I != E; ++I) { 72295c3e48f9557adb6064d580684bb14cacec2f826Jay Foad Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); 72395c3e48f9557adb6064d580684bb14cacec2f826Jay Foad Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 72495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad } 7252bc2a08b1bf6b5dcbfa515acc85999d6f884ec1aJakob Stoklund Olesen // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. 7262bc2a08b1bf6b5dcbfa515acc85999d6f884ec1aJakob Stoklund Olesen Hash >>= 1; 72743a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // If we've never seen this hash value before, it's a unique PHI. 72843a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = 72943a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach HashMap.insert(std::make_pair(Hash, PN)); 73043a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach if (Pair.second) continue; 73143a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // Otherwise it's either a duplicate or a hash collision. 73243a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach for (PHINode *OtherPN = Pair.first->second; ; ) { 73343a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach if (OtherPN->isIdenticalTo(PN)) { 73443a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // A duplicate. Replace this PHI with its duplicate. 73543a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach PN->replaceAllUsesWith(OtherPN); 73643a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach PN->eraseFromParent(); 73743a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach Changed = true; 73843a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach break; 73943a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach } 74043a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // A non-duplicate hash collision. 74143a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); 74243a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach if (I == CollisionMap.end()) { 74343a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach // Set this PHI to be the head of the linked list of colliding PHIs. 74443a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach PHINode *Old = Pair.first->second; 74543a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach Pair.first->second = PN; 74643a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach CollisionMap[PN] = Old; 74743a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach break; 74843a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach } 749d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // Proceed to the next PHI in the list. 75043a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach OtherPN = I->second; 75143a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach } 75243a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach } 75343a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach 75443a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach return Changed; 75543a8241b65b70ded3a87fb26852719633908a1e4Jim Grosbach} 756687140c818ba4b896329a83324714140b6580ef8Chris Lattner 757687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// enforceKnownAlignment - If the specified pointer points to an object that 758687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// we control, modify the object's alignment to PrefAlign. This isn't 759687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// often possible though. If alignment is important, a more reliable approach 760687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// is to simply align all global variables and allocation instructions to 761687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// their preferred alignment from the beginning. 762687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// 76319282365147f498a60463d250dbed2f8e1b81861Benjamin Kramerstatic unsigned enforceKnownAlignment(Value *V, unsigned Align, 7643574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow unsigned PrefAlign, const DataLayout *TD) { 765b53c7937c5651e5500b554186657b27838137365Eli Friedman V = V->stripPointerCasts(); 766687140c818ba4b896329a83324714140b6580ef8Chris Lattner 767b53c7937c5651e5500b554186657b27838137365Eli Friedman if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 768bb5b3f33594cfa40e9f53bf9a71af359b080a697Lang Hames // If the preferred alignment is greater than the natural stack alignment 769bb5b3f33594cfa40e9f53bf9a71af359b080a697Lang Hames // then don't round up. This avoids dynamic stack realignment. 770bb5b3f33594cfa40e9f53bf9a71af359b080a697Lang Hames if (TD && TD->exceedsNaturalStackAlignment(PrefAlign)) 771bb5b3f33594cfa40e9f53bf9a71af359b080a697Lang Hames return Align; 772687140c818ba4b896329a83324714140b6580ef8Chris Lattner // If there is a requested alignment and if this is an alloca, round up. 773687140c818ba4b896329a83324714140b6580ef8Chris Lattner if (AI->getAlignment() >= PrefAlign) 774687140c818ba4b896329a83324714140b6580ef8Chris Lattner return AI->getAlignment(); 775687140c818ba4b896329a83324714140b6580ef8Chris Lattner AI->setAlignment(PrefAlign); 776687140c818ba4b896329a83324714140b6580ef8Chris Lattner return PrefAlign; 777687140c818ba4b896329a83324714140b6580ef8Chris Lattner } 778687140c818ba4b896329a83324714140b6580ef8Chris Lattner 779687140c818ba4b896329a83324714140b6580ef8Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 780687140c818ba4b896329a83324714140b6580ef8Chris Lattner // If there is a large requested alignment and we can, bump up the alignment 781687140c818ba4b896329a83324714140b6580ef8Chris Lattner // of the global. 782687140c818ba4b896329a83324714140b6580ef8Chris Lattner if (GV->isDeclaration()) return Align; 783d3a38ccfbb6be0edad037961df77649db2cb9597Duncan Sands // If the memory we set aside for the global may not be the memory used by 784d3a38ccfbb6be0edad037961df77649db2cb9597Duncan Sands // the final program then it is impossible for us to reliably enforce the 785d3a38ccfbb6be0edad037961df77649db2cb9597Duncan Sands // preferred alignment. 786d3a38ccfbb6be0edad037961df77649db2cb9597Duncan Sands if (GV->isWeakForLinker()) return Align; 787687140c818ba4b896329a83324714140b6580ef8Chris Lattner 788687140c818ba4b896329a83324714140b6580ef8Chris Lattner if (GV->getAlignment() >= PrefAlign) 789687140c818ba4b896329a83324714140b6580ef8Chris Lattner return GV->getAlignment(); 790687140c818ba4b896329a83324714140b6580ef8Chris Lattner // We can only increase the alignment of the global if it has no alignment 791687140c818ba4b896329a83324714140b6580ef8Chris Lattner // specified or if it is not assigned a section. If it is assigned a 792687140c818ba4b896329a83324714140b6580ef8Chris Lattner // section, the global could be densely packed with other objects in the 793687140c818ba4b896329a83324714140b6580ef8Chris Lattner // section, increasing the alignment could cause padding issues. 794687140c818ba4b896329a83324714140b6580ef8Chris Lattner if (!GV->hasSection() || GV->getAlignment() == 0) 795687140c818ba4b896329a83324714140b6580ef8Chris Lattner GV->setAlignment(PrefAlign); 796687140c818ba4b896329a83324714140b6580ef8Chris Lattner return GV->getAlignment(); 797687140c818ba4b896329a83324714140b6580ef8Chris Lattner } 798687140c818ba4b896329a83324714140b6580ef8Chris Lattner 799687140c818ba4b896329a83324714140b6580ef8Chris Lattner return Align; 800687140c818ba4b896329a83324714140b6580ef8Chris Lattner} 801687140c818ba4b896329a83324714140b6580ef8Chris Lattner 802687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 803687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 804687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// and it is more than the alignment of the ultimate object, see if we can 805687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// increase the alignment of the ultimate object, making this check succeed. 806687140c818ba4b896329a83324714140b6580ef8Chris Lattnerunsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 8073574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD) { 808687140c818ba4b896329a83324714140b6580ef8Chris Lattner assert(V->getType()->isPointerTy() && 809687140c818ba4b896329a83324714140b6580ef8Chris Lattner "getOrEnforceKnownAlignment expects a pointer!"); 810426c2bf5cdd2173e4a33aea8cb92cf684a724f4bChandler Carruth unsigned BitWidth = TD ? TD->getPointerSizeInBits() : 64; 811687140c818ba4b896329a83324714140b6580ef8Chris Lattner APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 81226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, TD); 813687140c818ba4b896329a83324714140b6580ef8Chris Lattner unsigned TrailZ = KnownZero.countTrailingOnes(); 814687140c818ba4b896329a83324714140b6580ef8Chris Lattner 815687140c818ba4b896329a83324714140b6580ef8Chris Lattner // Avoid trouble with rediculously large TrailZ values, such as 816687140c818ba4b896329a83324714140b6580ef8Chris Lattner // those computed from a null pointer. 817687140c818ba4b896329a83324714140b6580ef8Chris Lattner TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 818687140c818ba4b896329a83324714140b6580ef8Chris Lattner 819687140c818ba4b896329a83324714140b6580ef8Chris Lattner unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); 820687140c818ba4b896329a83324714140b6580ef8Chris Lattner 821687140c818ba4b896329a83324714140b6580ef8Chris Lattner // LLVM doesn't support alignments larger than this currently. 822687140c818ba4b896329a83324714140b6580ef8Chris Lattner Align = std::min(Align, +Value::MaximumAlignment); 823687140c818ba4b896329a83324714140b6580ef8Chris Lattner 824687140c818ba4b896329a83324714140b6580ef8Chris Lattner if (PrefAlign > Align) 825bb5b3f33594cfa40e9f53bf9a71af359b080a697Lang Hames Align = enforceKnownAlignment(V, Align, PrefAlign, TD); 826687140c818ba4b896329a83324714140b6580ef8Chris Lattner 827687140c818ba4b896329a83324714140b6580ef8Chris Lattner // We don't need to make any adjustment. 828687140c818ba4b896329a83324714140b6580ef8Chris Lattner return Align; 829687140c818ba4b896329a83324714140b6580ef8Chris Lattner} 830687140c818ba4b896329a83324714140b6580ef8Chris Lattner 8315ee20680c7ebc765950983633e19fafab5235245Devang Patel///===---------------------------------------------------------------------===// 8325ee20680c7ebc765950983633e19fafab5235245Devang Patel/// Dbg Intrinsic utilities 8335ee20680c7ebc765950983633e19fafab5235245Devang Patel/// 8345ee20680c7ebc765950983633e19fafab5235245Devang Patel 8355ee20680c7ebc765950983633e19fafab5235245Devang Patel/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value 8365ee20680c7ebc765950983633e19fafab5235245Devang Patel/// that has an associated llvm.dbg.decl intrinsic. 8375ee20680c7ebc765950983633e19fafab5235245Devang Patelbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 8385ee20680c7ebc765950983633e19fafab5235245Devang Patel StoreInst *SI, DIBuilder &Builder) { 8395ee20680c7ebc765950983633e19fafab5235245Devang Patel DIVariable DIVar(DDI->getVariable()); 8405ee20680c7ebc765950983633e19fafab5235245Devang Patel if (!DIVar.Verify()) 8415ee20680c7ebc765950983633e19fafab5235245Devang Patel return false; 8425ee20680c7ebc765950983633e19fafab5235245Devang Patel 843227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel Instruction *DbgVal = NULL; 844227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel // If an argument is zero extended then use argument directly. The ZExt 845227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel // may be zapped by an optimization pass in future. 846227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel Argument *ExtendedArg = NULL; 847227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 848227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 849227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 850227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 851227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel if (ExtendedArg) 852227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI); 853227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel else 854227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI); 855227dfdb3c44c5cc5ec140b4be89f618bdc59a133Devang Patel 8565ee20680c7ebc765950983633e19fafab5235245Devang Patel // Propagate any debug metadata from the store onto the dbg.value. 8575ee20680c7ebc765950983633e19fafab5235245Devang Patel DebugLoc SIDL = SI->getDebugLoc(); 8585ee20680c7ebc765950983633e19fafab5235245Devang Patel if (!SIDL.isUnknown()) 8595ee20680c7ebc765950983633e19fafab5235245Devang Patel DbgVal->setDebugLoc(SIDL); 8605ee20680c7ebc765950983633e19fafab5235245Devang Patel // Otherwise propagate debug metadata from dbg.declare. 8615ee20680c7ebc765950983633e19fafab5235245Devang Patel else 8625ee20680c7ebc765950983633e19fafab5235245Devang Patel DbgVal->setDebugLoc(DDI->getDebugLoc()); 8635ee20680c7ebc765950983633e19fafab5235245Devang Patel return true; 8645ee20680c7ebc765950983633e19fafab5235245Devang Patel} 8655ee20680c7ebc765950983633e19fafab5235245Devang Patel 86636fae67831517f132255118b45b21a8cf199a012Devang Patel/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value 86736fae67831517f132255118b45b21a8cf199a012Devang Patel/// that has an associated llvm.dbg.decl intrinsic. 86836fae67831517f132255118b45b21a8cf199a012Devang Patelbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 86936fae67831517f132255118b45b21a8cf199a012Devang Patel LoadInst *LI, DIBuilder &Builder) { 87036fae67831517f132255118b45b21a8cf199a012Devang Patel DIVariable DIVar(DDI->getVariable()); 87136fae67831517f132255118b45b21a8cf199a012Devang Patel if (!DIVar.Verify()) 87236fae67831517f132255118b45b21a8cf199a012Devang Patel return false; 87336fae67831517f132255118b45b21a8cf199a012Devang Patel 87436fae67831517f132255118b45b21a8cf199a012Devang Patel Instruction *DbgVal = 87536fae67831517f132255118b45b21a8cf199a012Devang Patel Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, 87636fae67831517f132255118b45b21a8cf199a012Devang Patel DIVar, LI); 87736fae67831517f132255118b45b21a8cf199a012Devang Patel 87836fae67831517f132255118b45b21a8cf199a012Devang Patel // Propagate any debug metadata from the store onto the dbg.value. 87936fae67831517f132255118b45b21a8cf199a012Devang Patel DebugLoc LIDL = LI->getDebugLoc(); 88036fae67831517f132255118b45b21a8cf199a012Devang Patel if (!LIDL.isUnknown()) 88136fae67831517f132255118b45b21a8cf199a012Devang Patel DbgVal->setDebugLoc(LIDL); 88236fae67831517f132255118b45b21a8cf199a012Devang Patel // Otherwise propagate debug metadata from dbg.declare. 88336fae67831517f132255118b45b21a8cf199a012Devang Patel else 88436fae67831517f132255118b45b21a8cf199a012Devang Patel DbgVal->setDebugLoc(DDI->getDebugLoc()); 88536fae67831517f132255118b45b21a8cf199a012Devang Patel return true; 88636fae67831517f132255118b45b21a8cf199a012Devang Patel} 88736fae67831517f132255118b45b21a8cf199a012Devang Patel 888813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 889813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel/// of llvm.dbg.value intrinsics. 890813c9a0f19c0d27085a3ea81eb44033747007741Devang Patelbool llvm::LowerDbgDeclare(Function &F) { 891813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel DIBuilder DIB(*F.getParent()); 892813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel SmallVector<DbgDeclareInst *, 4> Dbgs; 893813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 894813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) { 895813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(BI)) 896813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel Dbgs.push_back(DDI); 897813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel } 898813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel if (Dbgs.empty()) 899813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel return false; 900813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel 901813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel for (SmallVector<DbgDeclareInst *, 4>::iterator I = Dbgs.begin(), 902813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel E = Dbgs.end(); I != E; ++I) { 903813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel DbgDeclareInst *DDI = *I; 904813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress())) { 90581ad03c020d7c1f73a78ce41ca713f1e425efe3dDevang Patel bool RemoveDDI = true; 906813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 907813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel UI != E; ++UI) 908813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 909813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 91036fae67831517f132255118b45b21a8cf199a012Devang Patel else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 91136fae67831517f132255118b45b21a8cf199a012Devang Patel ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 91281ad03c020d7c1f73a78ce41ca713f1e425efe3dDevang Patel else 91381ad03c020d7c1f73a78ce41ca713f1e425efe3dDevang Patel RemoveDDI = false; 91481ad03c020d7c1f73a78ce41ca713f1e425efe3dDevang Patel if (RemoveDDI) 91581ad03c020d7c1f73a78ce41ca713f1e425efe3dDevang Patel DDI->eraseFromParent(); 916813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel } 917813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel } 918813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel return true; 919813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel} 920c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich 921c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 922c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich/// alloca 'V', if any. 923c827939046670a9800659b83e2048f1d3a79a531Cameron ZwarichDbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { 924c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V)) 925c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich for (Value::use_iterator UI = DebugNode->use_begin(), 926c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich E = DebugNode->use_end(); UI != E; ++UI) 927c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI)) 928c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich return DDI; 929c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich 930c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich return 0; 931c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich} 9321afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov 9331afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonovbool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 9341afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DIBuilder &Builder) { 9351afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI); 9361afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov if (!DDI) 9371afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov return false; 9381afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DIVariable DIVar(DDI->getVariable()); 9391afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov if (!DIVar.Verify()) 9401afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov return false; 9411afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov 9421afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov // Create a copy of the original DIDescriptor for user variable, appending 9431afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov // "deref" operation to a list of address elements, as new llvm.dbg.declare 9441afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov // will take a value storing address of the memory for variable, not 9451afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov // alloca itself. 9461afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov Type *Int64Ty = Type::getInt64Ty(AI->getContext()); 9471afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov SmallVector<Value*, 4> NewDIVarAddress; 9481afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov if (DIVar.hasComplexAddress()) { 9491afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov for (unsigned i = 0, n = DIVar.getNumAddrElements(); i < n; ++i) { 9501afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov NewDIVarAddress.push_back( 9511afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov ConstantInt::get(Int64Ty, DIVar.getAddrElement(i))); 9521afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov } 9531afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov } 9541afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov NewDIVarAddress.push_back(ConstantInt::get(Int64Ty, DIBuilder::OpDeref)); 9551afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DIVariable NewDIVar = Builder.createComplexVariable( 9561afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DIVar.getTag(), DIVar.getContext(), DIVar.getName(), 9571afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DIVar.getFile(), DIVar.getLineNumber(), DIVar.getType(), 9581afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov NewDIVarAddress, DIVar.getArgNumber()); 9591afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov 9601afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov // Insert llvm.dbg.declare in the same basic block as the original alloca, 9611afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov // and remove old llvm.dbg.declare. 9621afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov BasicBlock *BB = AI->getParent(); 9631afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov Builder.insertDeclare(NewAllocaAddress, NewDIVar, BB); 9641afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DDI->eraseFromParent(); 9651afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov return true; 9661afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov} 9673333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov 9683333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanovbool llvm::removeUnreachableBlocks(Function &F) { 9693333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov SmallPtrSet<BasicBlock*, 16> Reachable; 9703333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov SmallVector<BasicBlock*, 128> Worklist; 9713333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov Worklist.push_back(&F.getEntryBlock()); 9723333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov Reachable.insert(&F.getEntryBlock()); 9733333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov do { 9743333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov BasicBlock *BB = Worklist.pop_back_val(); 9753333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 9763333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov if (Reachable.insert(*SI)) 9773333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov Worklist.push_back(*SI); 9783333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov } while (!Worklist.empty()); 9793333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov 9803333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov if (Reachable.size() == F.size()) 9813333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov return false; 9823333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov 9833333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov assert(Reachable.size() < F.size()); 9843333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov for (Function::iterator I = llvm::next(F.begin()), E = F.end(); I != E; ++I) { 9853333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov if (Reachable.count(I)) 9863333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov continue; 9873333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov 9883333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov // Remove the block as predecessor of all its reachable successors. 9893333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov // Unreachable successors don't matter as they'll soon be removed, too. 9903333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov for (succ_iterator SI = succ_begin(I), SE = succ_end(I); SI != SE; ++SI) 9913333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov if (Reachable.count(*SI)) 9923333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov (*SI)->removePredecessor(I); 9933333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov 9943333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov // Zap all instructions in this basic block. 9953333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov while (!I->empty()) { 9963333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov Instruction &Inst = I->back(); 9973333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov if (!Inst.use_empty()) 9983333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov Inst.replaceAllUsesWith(UndefValue::get(Inst.getType())); 9993333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov I->getInstList().pop_back(); 10003333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov } 10013333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov 10023333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov --I; 10033333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov llvm::next(I)->eraseFromParent(); 10043333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov } 10053333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov return true; 10063333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov} 1007