Local.cpp revision 564c0a233010cb1ff2f9ee2d4d16870284d72487
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 "llvm/ADT/SmallPtrSet.h" 26using namespace llvm; 27 28//===----------------------------------------------------------------------===// 29// Local constant propagation. 30// 31 32// ConstantFoldTerminator - If a terminator instruction is predicated on a 33// constant value, convert it into an unconditional branch to the constant 34// destination. 35// 36bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 37 TerminatorInst *T = BB->getTerminator(); 38 39 // Branch - See if we are conditional jumping on constant 40 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 41 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 42 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 43 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 44 45 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 46 // Are we branching on constant? 47 // YES. Change to unconditional branch... 48 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 49 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 50 51 //cerr << "Function: " << T->getParent()->getParent() 52 // << "\nRemoving branch from " << T->getParent() 53 // << "\n\nTo: " << OldDest << endl; 54 55 // Let the basic block know that we are letting go of it. Based on this, 56 // it will adjust it's PHI nodes. 57 assert(BI->getParent() && "Terminator not inserted in block!"); 58 OldDest->removePredecessor(BI->getParent()); 59 60 // Set the unconditional destination, and change the insn to be an 61 // unconditional branch. 62 BI->setUnconditionalDest(Destination); 63 return true; 64 } else if (Dest2 == Dest1) { // Conditional branch to same location? 65 // This branch matches something like this: 66 // br bool %cond, label %Dest, label %Dest 67 // and changes it into: br label %Dest 68 69 // Let the basic block know that we are letting go of one copy of it. 70 assert(BI->getParent() && "Terminator not inserted in block!"); 71 Dest1->removePredecessor(BI->getParent()); 72 73 // Change a conditional branch to unconditional. 74 BI->setUnconditionalDest(Dest1); 75 return true; 76 } 77 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 78 // If we are switching on a constant, we can convert the switch into a 79 // single branch instruction! 80 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 81 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 82 BasicBlock *DefaultDest = TheOnlyDest; 83 assert(TheOnlyDest == SI->getDefaultDest() && 84 "Default destination is not successor #0?"); 85 86 // Figure out which case it goes to... 87 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 88 // Found case matching a constant operand? 89 if (SI->getSuccessorValue(i) == CI) { 90 TheOnlyDest = SI->getSuccessor(i); 91 break; 92 } 93 94 // Check to see if this branch is going to the same place as the default 95 // dest. If so, eliminate it as an explicit compare. 96 if (SI->getSuccessor(i) == DefaultDest) { 97 // Remove this entry... 98 DefaultDest->removePredecessor(SI->getParent()); 99 SI->removeCase(i); 100 --i; --e; // Don't skip an entry... 101 continue; 102 } 103 104 // Otherwise, check to see if the switch only branches to one destination. 105 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 106 // destinations. 107 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 108 } 109 110 if (CI && !TheOnlyDest) { 111 // Branching on a constant, but not any of the cases, go to the default 112 // successor. 113 TheOnlyDest = SI->getDefaultDest(); 114 } 115 116 // If we found a single destination that we can fold the switch into, do so 117 // now. 118 if (TheOnlyDest) { 119 // Insert the new branch.. 120 BranchInst::Create(TheOnlyDest, SI); 121 BasicBlock *BB = SI->getParent(); 122 123 // Remove entries from PHI nodes which we no longer branch to... 124 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 125 // Found case matching a constant operand? 126 BasicBlock *Succ = SI->getSuccessor(i); 127 if (Succ == TheOnlyDest) 128 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 129 else 130 Succ->removePredecessor(BB); 131 } 132 133 // Delete the old switch... 134 BB->getInstList().erase(SI); 135 return true; 136 } else if (SI->getNumSuccessors() == 2) { 137 // Otherwise, we can fold this switch into a conditional branch 138 // instruction if it has only one non-default destination. 139 Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, SI->getCondition(), 140 SI->getSuccessorValue(1), "cond", SI); 141 // Insert the new branch... 142 BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 143 144 // Delete the old switch... 145 SI->eraseFromParent(); 146 return true; 147 } 148 } 149 return false; 150} 151 152 153//===----------------------------------------------------------------------===// 154// Local dead code elimination... 155// 156 157/// isInstructionTriviallyDead - Return true if the result produced by the 158/// instruction is not used, and the instruction has no side effects. 159/// 160bool llvm::isInstructionTriviallyDead(Instruction *I) { 161 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 162 163 if (!I->mayWriteToMemory()) 164 return true; 165 166 // Special case intrinsics that "may write to memory" but can be deleted when 167 // dead. 168 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 169 // Safe to delete llvm.stacksave if dead. 170 if (II->getIntrinsicID() == Intrinsic::stacksave) 171 return true; 172 173 return false; 174} 175 176/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 177/// trivially dead instruction, delete it. If that makes any of its operands 178/// trivially dead, delete them too, recursively. 179/// 180/// If DeadInst is specified, the vector is filled with the instructions that 181/// are actually deleted. 182void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 183 SmallVectorImpl<Instruction*> *DeadInst) { 184 Instruction *I = dyn_cast<Instruction>(V); 185 if (!I || !I->use_empty()) return; 186 187 SmallPtrSet<Instruction*, 16> Insts; 188 Insts.insert(I); 189 190 while (!Insts.empty()) { 191 I = *Insts.begin(); 192 Insts.erase(I); 193 194 // If this is a PHI node, we may be able to make it dead if we know all the 195 // input values are the same. 196 if (PHINode *PN = dyn_cast<PHINode>(I)) { 197 if (Value *PNV = PN->hasConstantValue()) 198 PN->replaceAllUsesWith(PNV); 199 } 200 201 // Okay, if the instruction is dead, delete it. 202 if (!isInstructionTriviallyDead(I)) 203 continue; 204 205 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 206 if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) 207 Insts.insert(U); 208 I->eraseFromParent(); 209 210 if (DeadInst) 211 DeadInst->push_back(I); 212 } 213} 214 215 216//===----------------------------------------------------------------------===// 217// Control Flow Graph Restructuring... 218// 219 220/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 221/// predecessor is known to have one successor (DestBB!). Eliminate the edge 222/// between them, moving the instructions in the predecessor into DestBB and 223/// deleting the predecessor block. 224/// 225void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB) { 226 // If BB has single-entry PHI nodes, fold them. 227 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 228 Value *NewVal = PN->getIncomingValue(0); 229 // Replace self referencing PHI with undef, it must be dead. 230 if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 231 PN->replaceAllUsesWith(NewVal); 232 PN->eraseFromParent(); 233 } 234 235 BasicBlock *PredBB = DestBB->getSinglePredecessor(); 236 assert(PredBB && "Block doesn't have a single predecessor!"); 237 238 // Splice all the instructions from PredBB to DestBB. 239 PredBB->getTerminator()->eraseFromParent(); 240 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 241 242 // Anything that branched to PredBB now branches to DestBB. 243 PredBB->replaceAllUsesWith(DestBB); 244 245 // Nuke BB. 246 PredBB->eraseFromParent(); 247} 248