Local.cpp revision 0a4c6789d5adafb6eb33080fe1833b416a152d7c
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" 1681ebc300891a81c305258aed980567514dff952dChris Lattner#include "llvm/Constants.h" 176cc8a93c486f889c5767278508bc655942ba408eChris Lattner#include "llvm/GlobalAlias.h" 18c79e1182470ed12f1f3d0d35c1725366519a9af7Devang Patel#include "llvm/GlobalVariable.h" 19c5f52e6da18e6e8ccb62aac2a4cb431df98e7d6dChris Lattner#include "llvm/DerivedTypes.h" 207822c2ae077429d7bf6eb3f6ebf99d61f359b601Chris Lattner#include "llvm/Instructions.h" 21cf11035a6f9973d68d8eaf837d71dcf272d36b79Chris Lattner#include "llvm/Intrinsics.h" 22741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner#include "llvm/IntrinsicInst.h" 230a205a459884ec745df1c529396dd921f029dafdOwen Anderson#include "llvm/LLVMContext.h" 24afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman#include "llvm/ADT/SmallPtrSet.h" 25cbbc6b74e357afbf8fb37fdeb177ed78021092d3Chris Lattner#include "llvm/Analysis/ConstantFolding.h" 26c79e1182470ed12f1f3d0d35c1725366519a9af7Devang Patel#include "llvm/Analysis/DebugInfo.h" 27f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 28ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter#include "llvm/Analysis/ProfileInfo.h" 299fa038dc21e966dceb23f9410351e863e3ce1114Chris Lattner#include "llvm/Target/TargetData.h" 30c5f52e6da18e6e8ccb62aac2a4cb431df98e7d6dChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 31c5f52e6da18e6e8ccb62aac2a4cb431df98e7d6dChris Lattner#include "llvm/Support/MathExtras.h" 32abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattnerusing namespace llvm; 33d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 344d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 356cc8a93c486f889c5767278508bc655942ba408eChris Lattner// Local analysis. 366cc8a93c486f889c5767278508bc655942ba408eChris Lattner// 376cc8a93c486f889c5767278508bc655942ba408eChris Lattner 386cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// isSafeToLoadUnconditionally - Return true if we know that executing a load 396cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// from this value cannot trap. If it is not obviously safe to load from the 406cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// specified pointer, we do a quick local scan of the basic block containing 416cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// ScanFrom, to determine if the address is already accessed. 426cc8a93c486f889c5767278508bc655942ba408eChris Lattnerbool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) { 436cc8a93c486f889c5767278508bc655942ba408eChris Lattner // If it is an alloca it is always safe to load from. 446cc8a93c486f889c5767278508bc655942ba408eChris Lattner if (isa<AllocaInst>(V)) return true; 456cc8a93c486f889c5767278508bc655942ba408eChris Lattner 466cc8a93c486f889c5767278508bc655942ba408eChris Lattner // If it is a global variable it is mostly safe to load from. 476cc8a93c486f889c5767278508bc655942ba408eChris Lattner if (const GlobalValue *GV = dyn_cast<GlobalVariable>(V)) 486cc8a93c486f889c5767278508bc655942ba408eChris Lattner // Don't try to evaluate aliases. External weak GV can be null. 496cc8a93c486f889c5767278508bc655942ba408eChris Lattner return !isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage(); 506cc8a93c486f889c5767278508bc655942ba408eChris Lattner 516cc8a93c486f889c5767278508bc655942ba408eChris Lattner // Otherwise, be a little bit agressive by scanning the local block where we 526cc8a93c486f889c5767278508bc655942ba408eChris Lattner // want to check to see if the pointer is already being loaded or stored 536cc8a93c486f889c5767278508bc655942ba408eChris Lattner // from/to. If so, the previous load or store would have already trapped, 546cc8a93c486f889c5767278508bc655942ba408eChris Lattner // so there is no harm doing an extra load (also, CSE will later eliminate 556cc8a93c486f889c5767278508bc655942ba408eChris Lattner // the load entirely). 566cc8a93c486f889c5767278508bc655942ba408eChris Lattner BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin(); 576cc8a93c486f889c5767278508bc655942ba408eChris Lattner 586cc8a93c486f889c5767278508bc655942ba408eChris Lattner while (BBI != E) { 596cc8a93c486f889c5767278508bc655942ba408eChris Lattner --BBI; 606cc8a93c486f889c5767278508bc655942ba408eChris Lattner 616cc8a93c486f889c5767278508bc655942ba408eChris Lattner // If we see a free or a call which may write to memory (i.e. which might do 626cc8a93c486f889c5767278508bc655942ba408eChris Lattner // a free) the pointer could be marked invalid. 63046e78ce55a7c3d82b7b6758d2d77f2d99f970bfVictor Hernandez if (isFreeCall(BBI) || (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 64046e78ce55a7c3d82b7b6758d2d77f2d99f970bfVictor Hernandez !isa<DbgInfoIntrinsic>(BBI))) 656cc8a93c486f889c5767278508bc655942ba408eChris Lattner return false; 666cc8a93c486f889c5767278508bc655942ba408eChris Lattner 676cc8a93c486f889c5767278508bc655942ba408eChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 686cc8a93c486f889c5767278508bc655942ba408eChris Lattner if (LI->getOperand(0) == V) return true; 696cc8a93c486f889c5767278508bc655942ba408eChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 706cc8a93c486f889c5767278508bc655942ba408eChris Lattner if (SI->getOperand(1) == V) return true; 716cc8a93c486f889c5767278508bc655942ba408eChris Lattner } 726cc8a93c486f889c5767278508bc655942ba408eChris Lattner } 736cc8a93c486f889c5767278508bc655942ba408eChris Lattner return false; 746cc8a93c486f889c5767278508bc655942ba408eChris Lattner} 756cc8a93c486f889c5767278508bc655942ba408eChris Lattner 766cc8a93c486f889c5767278508bc655942ba408eChris Lattner 776cc8a93c486f889c5767278508bc655942ba408eChris Lattner//===----------------------------------------------------------------------===// 783481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local constant propagation. 794d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 804d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 814d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// ConstantFoldTerminator - If a terminator instruction is predicated on a 824d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// constant value, convert it into an unconditional branch to the constant 834d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// destination. 844d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 85abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattnerbool llvm::ConstantFoldTerminator(BasicBlock *BB) { 8676ae3445f81164aaff9f95123426109c119f27c0Chris Lattner TerminatorInst *T = BB->getTerminator(); 87fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 884d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Branch - See if we are conditional jumping on constant 894d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 904d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (BI->isUnconditional()) return false; // Can't optimize uncond branch 91c1bb13f1b8794aa6f3219b3ac567f569ad78a6d1Gabor Greif BasicBlock *Dest1 = BI->getSuccessor(0); 92c1bb13f1b8794aa6f3219b3ac567f569ad78a6d1Gabor Greif BasicBlock *Dest2 = BI->getSuccessor(1); 934d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 946b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 954d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Are we branching on constant? 964d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // YES. Change to unconditional branch... 97579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 98579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 994d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 100fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman //cerr << "Function: " << T->getParent()->getParent() 101fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // << "\nRemoving branch from " << T->getParent() 1024d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // << "\n\nTo: " << OldDest << endl; 1034d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 1044d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Let the basic block know that we are letting go of it. Based on this, 1054d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // it will adjust it's PHI nodes. 1064d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner assert(BI->getParent() && "Terminator not inserted in block!"); 1074d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner OldDest->removePredecessor(BI->getParent()); 1084d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 1094d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Set the unconditional destination, and change the insn to be an 1104d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // unconditional branch. 1114d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner BI->setUnconditionalDest(Destination); 1124d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner return true; 1130a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 1140a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 1150a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (Dest2 == Dest1) { // Conditional branch to same location? 116fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // This branch matches something like this: 1174d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // br bool %cond, label %Dest, label %Dest 1184d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // and changes it into: br label %Dest 1194d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 1204d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Let the basic block know that we are letting go of one copy of it. 1214d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner assert(BI->getParent() && "Terminator not inserted in block!"); 1224d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner Dest1->removePredecessor(BI->getParent()); 1234d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 1244d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Change a conditional branch to unconditional. 1254d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner BI->setUnconditionalDest(Dest1); 1264d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner return true; 1274d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner } 1280a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner return false; 1290a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 1300a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 1310a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 13210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // If we are switching on a constant, we can convert the switch into a 13310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // single branch instruction! 13410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 13510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 1367d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner BasicBlock *DefaultDest = TheOnlyDest; 1377d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner assert(TheOnlyDest == SI->getDefaultDest() && 1387d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner "Default destination is not successor #0?"); 13910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 1400a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Figure out which case it goes to. 14110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 14210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Found case matching a constant operand? 14310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (SI->getSuccessorValue(i) == CI) { 14410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner TheOnlyDest = SI->getSuccessor(i); 14510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner break; 14610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 14710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 1487d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner // Check to see if this branch is going to the same place as the default 1497d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner // dest. If so, eliminate it as an explicit compare. 1507d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner if (SI->getSuccessor(i) == DefaultDest) { 1510a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Remove this entry. 1527d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner DefaultDest->removePredecessor(SI->getParent()); 1537d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner SI->removeCase(i); 1547d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner --i; --e; // Don't skip an entry... 1557d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner continue; 1567d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner } 1577d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner 15810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Otherwise, check to see if the switch only branches to one destination. 15910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // We do this by reseting "TheOnlyDest" to null when we find two non-equal 16010b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // destinations. 16110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 16210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 163694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 16410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (CI && !TheOnlyDest) { 16510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Branching on a constant, but not any of the cases, go to the default 16610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // successor. 16710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner TheOnlyDest = SI->getDefaultDest(); 168694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner } 169694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 17010b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // If we found a single destination that we can fold the switch into, do so 17110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // now. 17210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (TheOnlyDest) { 1730a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Insert the new branch. 174051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(TheOnlyDest, SI); 17510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BasicBlock *BB = SI->getParent(); 17610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 17710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Remove entries from PHI nodes which we no longer branch to... 17810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 17910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Found case matching a constant operand? 18010b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BasicBlock *Succ = SI->getSuccessor(i); 18110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (Succ == TheOnlyDest) 18210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 18310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner else 18410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner Succ->removePredecessor(BB); 18510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 18610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 1870a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Delete the old switch. 18810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BB->getInstList().erase(SI); 18910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner return true; 1900a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 1910a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 1920a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (SI->getNumSuccessors() == 2) { 19310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Otherwise, we can fold this switch into a conditional branch 19410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // instruction if it has only one non-default destination. 195333c40096561218bc3597cf153c0a3895274414cOwen Anderson Value *Cond = new ICmpInst(SI, ICmpInst::ICMP_EQ, SI->getCondition(), 196333c40096561218bc3597cf153c0a3895274414cOwen Anderson SI->getSuccessorValue(1), "cond"); 1970a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Insert the new branch. 198051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 19910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 2000a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Delete the old switch. 2011adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman SI->eraseFromParent(); 20210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner return true; 20310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 2040a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner return false; 2050a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2060a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2070a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 2080a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // indirectbr blockaddress(@F, @BB) -> br label @BB 2090a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (BlockAddress *BA = 2100a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 2110a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner BasicBlock *TheOnlyDest = BA->getBasicBlock(); 2120a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Insert the new branch. 2130a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner BranchInst::Create(TheOnlyDest, IBI); 2140a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2150a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 2160a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (IBI->getDestination(i) == TheOnlyDest) 2170a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner TheOnlyDest = 0; 2180a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner else 2190a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner IBI->getDestination(i)->removePredecessor(IBI->getParent()); 2200a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2210a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner IBI->eraseFromParent(); 2220a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2230a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // If we didn't find our destination in the IBI successor list, then we 2240a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // have undefined behavior. Replace the unconditional branch with an 2250a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // 'unreachable' instruction. 2260a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (TheOnlyDest) { 2270a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner BB->getTerminator()->eraseFromParent(); 2280a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner new UnreachableInst(BB->getContext(), BB); 2290a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2300a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2310a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner return true; 2320a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2334d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner } 2340a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2354d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner return false; 2364d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 2374d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2384d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2394d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 2404d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// Local dead code elimination... 2414d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 2424d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2433481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// isInstructionTriviallyDead - Return true if the result produced by the 2443481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// instruction is not used, and the instruction has no side effects. 2453481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// 246abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattnerbool llvm::isInstructionTriviallyDead(Instruction *I) { 247ec710c5b12af647ae90f53917122726269c18738Chris Lattner if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 24800b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 249127a7936dea7b86e5cad337ad4b537bc115c2588Dale Johannesen // We don't want debug info removed by anything this general. 250127a7936dea7b86e5cad337ad4b537bc115c2588Dale Johannesen if (isa<DbgInfoIntrinsic>(I)) return false; 251ec710c5b12af647ae90f53917122726269c18738Chris Lattner 2527af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands if (!I->mayHaveSideEffects()) return true; 2537af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands 2547af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands // Special case intrinsics that "may have side effects" but can be deleted 2557af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands // when dead. 256741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 257741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner // Safe to delete llvm.stacksave if dead. 258741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner if (II->getIntrinsicID() == Intrinsic::stacksave) 259741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner return true; 260ec710c5b12af647ae90f53917122726269c18738Chris Lattner return false; 2614d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 2624d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2633481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 2643481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// trivially dead instruction, delete it. If that makes any of its operands 2653481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// trivially dead, delete them too, recursively. 26635738ac150afafe2359268d4b2169498c6c98c5fDan Gohmanvoid llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { 2673481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner Instruction *I = dyn_cast<Instruction>(V); 2687605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) 2697605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner return; 2703481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 2717605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner SmallVector<Instruction*, 16> DeadInsts; 2727605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner DeadInsts.push_back(I); 2733481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 2747605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner while (!DeadInsts.empty()) { 275e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman I = DeadInsts.pop_back_val(); 2762872177834d83b42cd042a37299cb7089965f36bChris Lattner 2777605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // Null out all of the instruction's operands to see if any operand becomes 2787605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // dead as we go. 2797605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 2807605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner Value *OpV = I->getOperand(i); 2817605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner I->setOperand(i, 0); 2827605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 2837605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner if (!OpV->use_empty()) continue; 2847605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 2857605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // If the operand is an instruction that became dead as we nulled out the 2867605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // operand, and if it is 'trivially' dead, delete it in a future loop 2877605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // iteration. 2887605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 2897605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner if (isInstructionTriviallyDead(OpI)) 2907605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner DeadInsts.push_back(OpI); 2917605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner } 2927605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 2937605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner I->eraseFromParent(); 2944d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner } 2954d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 296b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 297afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 298afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// dead PHI node, due to being a def-use chain of single-use nodes that 299afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// either forms a cycle or is terminated by a trivially dead instruction, 300afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// delete it. If that makes any of its operands trivially dead, delete them 301afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// too, recursively. 302afc36a9520971832dfbebc0333593bf5d3098296Dan Gohmanvoid 30335738ac150afafe2359268d4b2169498c6c98c5fDan Gohmanllvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { 304afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // We can remove a PHI if it is on a cycle in the def-use graph 305afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // where each node in the cycle has degree one, i.e. only one use, 306afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // and is an instruction with no side effects. 307afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman if (!PN->hasOneUse()) 308afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman return; 309afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 310afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman SmallPtrSet<PHINode *, 4> PHIs; 311afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman PHIs.insert(PN); 312afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman for (Instruction *J = cast<Instruction>(*PN->use_begin()); 3137af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands J->hasOneUse() && !J->mayHaveSideEffects(); 314afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman J = cast<Instruction>(*J->use_begin())) 315afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // If we find a PHI more than once, we're on a cycle that 316afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // won't prove fruitful. 317afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman if (PHINode *JP = dyn_cast<PHINode>(J)) 318afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman if (!PHIs.insert(cast<PHINode>(JP))) { 319afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // Break the cycle and delete the PHI and its operands. 3209e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson JP->replaceAllUsesWith(UndefValue::get(JP->getType())); 32135738ac150afafe2359268d4b2169498c6c98c5fDan Gohman RecursivelyDeleteTriviallyDeadInstructions(JP); 322afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman break; 323afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman } 324afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman} 3253481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 326b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner//===----------------------------------------------------------------------===// 327b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner// Control Flow Graph Restructuring... 328b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner// 329b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 330b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 331b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// predecessor is known to have one successor (DestBB!). Eliminate the edge 332b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// between them, moving the instructions in the predecessor into DestBB and 333b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// deleting the predecessor block. 334b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// 335ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustiftervoid llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 336b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // If BB has single-entry PHI nodes, fold them. 337b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 338b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner Value *NewVal = PN->getIncomingValue(0); 339b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // Replace self referencing PHI with undef, it must be dead. 3409e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 341b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PN->replaceAllUsesWith(NewVal); 342b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PN->eraseFromParent(); 343b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner } 344b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 345b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner BasicBlock *PredBB = DestBB->getSinglePredecessor(); 346b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner assert(PredBB && "Block doesn't have a single predecessor!"); 347b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 348b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // Splice all the instructions from PredBB to DestBB. 349b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PredBB->getTerminator()->eraseFromParent(); 350b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 351b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 352b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // Anything that branched to PredBB now branches to DestBB. 353b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PredBB->replaceAllUsesWith(DestBB); 354b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 355ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter if (P) { 356ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 357ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter if (PI) { 358ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter PI->replaceAllUses(PredBB, DestBB); 359ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); 360ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 361ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustifter } 362b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner // Nuke BB. 363b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner PredBB->eraseFromParent(); 364b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner} 3654afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 3664afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used 3674afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// by DbgIntrinsics. If DbgInUses is specified then the vector is filled 3684afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// with the DbgInfoIntrinsic that use the instruction I. 3694afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patelbool llvm::OnlyUsedByDbgInfoIntrinsics(Instruction *I, 3704afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses) { 3714afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (DbgInUses) 3724afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DbgInUses->clear(); 3734afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 3744afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; 3754afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel ++UI) { 3764afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (DbgInfoIntrinsic *DI = dyn_cast<DbgInfoIntrinsic>(*UI)) { 3774afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (DbgInUses) 3784afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DbgInUses->push_back(DI); 3794afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } else { 3804afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (DbgInUses) 3814afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DbgInUses->clear(); 3824afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel return false; 3834afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 3844afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 3854afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel return true; 3864afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel} 387c79e1182470ed12f1f3d0d35c1725366519a9af7Devang Patel 388