Local.cpp revision 051a950000e21935165db56695e35bade668193b
1//===-- Local.cpp - Functions to perform local transformations ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This family of functions perform various local transformations to the 11// program. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/Transforms/Utils/Local.h" 16#include "llvm/Constants.h" 17#include "llvm/DerivedTypes.h" 18#include "llvm/Instructions.h" 19#include "llvm/Intrinsics.h" 20#include "llvm/IntrinsicInst.h" 21#include "llvm/Analysis/ConstantFolding.h" 22#include "llvm/Target/TargetData.h" 23#include "llvm/Support/GetElementPtrTypeIterator.h" 24#include "llvm/Support/MathExtras.h" 25#include <cerrno> 26using namespace llvm; 27 28//===----------------------------------------------------------------------===// 29// Local constant propagation... 30// 31 32/// doConstantPropagation - If an instruction references constants, try to fold 33/// them together... 34/// 35bool llvm::doConstantPropagation(BasicBlock::iterator &II, 36 const TargetData *TD) { 37 if (Constant *C = ConstantFoldInstruction(II, TD)) { 38 // Replaces all of the uses of a variable with uses of the constant. 39 II->replaceAllUsesWith(C); 40 41 // Remove the instruction from the basic block... 42 II = II->getParent()->getInstList().erase(II); 43 return true; 44 } 45 46 return false; 47} 48 49// ConstantFoldTerminator - If a terminator instruction is predicated on a 50// constant value, convert it into an unconditional branch to the constant 51// destination. 52// 53bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 54 TerminatorInst *T = BB->getTerminator(); 55 56 // Branch - See if we are conditional jumping on constant 57 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 58 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 59 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 60 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 61 62 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 63 // Are we branching on constant? 64 // YES. Change to unconditional branch... 65 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 66 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 67 68 //cerr << "Function: " << T->getParent()->getParent() 69 // << "\nRemoving branch from " << T->getParent() 70 // << "\n\nTo: " << OldDest << endl; 71 72 // Let the basic block know that we are letting go of it. Based on this, 73 // it will adjust it's PHI nodes. 74 assert(BI->getParent() && "Terminator not inserted in block!"); 75 OldDest->removePredecessor(BI->getParent()); 76 77 // Set the unconditional destination, and change the insn to be an 78 // unconditional branch. 79 BI->setUnconditionalDest(Destination); 80 return true; 81 } else if (Dest2 == Dest1) { // Conditional branch to same location? 82 // This branch matches something like this: 83 // br bool %cond, label %Dest, label %Dest 84 // and changes it into: br label %Dest 85 86 // Let the basic block know that we are letting go of one copy of it. 87 assert(BI->getParent() && "Terminator not inserted in block!"); 88 Dest1->removePredecessor(BI->getParent()); 89 90 // Change a conditional branch to unconditional. 91 BI->setUnconditionalDest(Dest1); 92 return true; 93 } 94 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 95 // If we are switching on a constant, we can convert the switch into a 96 // single branch instruction! 97 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 98 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 99 BasicBlock *DefaultDest = TheOnlyDest; 100 assert(TheOnlyDest == SI->getDefaultDest() && 101 "Default destination is not successor #0?"); 102 103 // Figure out which case it goes to... 104 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 105 // Found case matching a constant operand? 106 if (SI->getSuccessorValue(i) == CI) { 107 TheOnlyDest = SI->getSuccessor(i); 108 break; 109 } 110 111 // Check to see if this branch is going to the same place as the default 112 // dest. If so, eliminate it as an explicit compare. 113 if (SI->getSuccessor(i) == DefaultDest) { 114 // Remove this entry... 115 DefaultDest->removePredecessor(SI->getParent()); 116 SI->removeCase(i); 117 --i; --e; // Don't skip an entry... 118 continue; 119 } 120 121 // Otherwise, check to see if the switch only branches to one destination. 122 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 123 // destinations. 124 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 125 } 126 127 if (CI && !TheOnlyDest) { 128 // Branching on a constant, but not any of the cases, go to the default 129 // successor. 130 TheOnlyDest = SI->getDefaultDest(); 131 } 132 133 // If we found a single destination that we can fold the switch into, do so 134 // now. 135 if (TheOnlyDest) { 136 // Insert the new branch.. 137 BranchInst::Create(TheOnlyDest, SI); 138 BasicBlock *BB = SI->getParent(); 139 140 // Remove entries from PHI nodes which we no longer branch to... 141 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 142 // Found case matching a constant operand? 143 BasicBlock *Succ = SI->getSuccessor(i); 144 if (Succ == TheOnlyDest) 145 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 146 else 147 Succ->removePredecessor(BB); 148 } 149 150 // Delete the old switch... 151 BB->getInstList().erase(SI); 152 return true; 153 } else if (SI->getNumSuccessors() == 2) { 154 // Otherwise, we can fold this switch into a conditional branch 155 // instruction if it has only one non-default destination. 156 Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, SI->getCondition(), 157 SI->getSuccessorValue(1), "cond", SI); 158 // Insert the new branch... 159 BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 160 161 // Delete the old switch... 162 SI->getParent()->getInstList().erase(SI); 163 return true; 164 } 165 } 166 return false; 167} 168 169 170//===----------------------------------------------------------------------===// 171// Local dead code elimination... 172// 173 174bool llvm::isInstructionTriviallyDead(Instruction *I) { 175 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 176 177 if (!I->mayWriteToMemory()) 178 return true; 179 180 // Special case intrinsics that "may write to memory" but can be deleted when 181 // dead. 182 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 183 // Safe to delete llvm.stacksave if dead. 184 if (II->getIntrinsicID() == Intrinsic::stacksave) 185 return true; 186 187 return false; 188} 189 190// dceInstruction - Inspect the instruction at *BBI and figure out if it's 191// [trivially] dead. If so, remove the instruction and update the iterator 192// to point to the instruction that immediately succeeded the original 193// instruction. 194// 195bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 196 // Look for un"used" definitions... 197 if (isInstructionTriviallyDead(BBI)) { 198 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 199 return true; 200 } 201 return false; 202} 203