Local.cpp revision df95a2f6a90d81100972ccf3a22fca4b637806ac
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/GlobalVariable.h" 18#include "llvm/DerivedTypes.h" 19#include "llvm/Instructions.h" 20#include "llvm/Intrinsics.h" 21#include "llvm/IntrinsicInst.h" 22#include "llvm/Analysis/ConstantFolding.h" 23#include "llvm/Analysis/DebugInfo.h" 24#include "llvm/Target/TargetData.h" 25#include "llvm/Support/GetElementPtrTypeIterator.h" 26#include "llvm/Support/MathExtras.h" 27using namespace llvm; 28 29//===----------------------------------------------------------------------===// 30// Local constant propagation. 31// 32 33// ConstantFoldTerminator - If a terminator instruction is predicated on a 34// constant value, convert it into an unconditional branch to the constant 35// destination. 36// 37bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 38 TerminatorInst *T = BB->getTerminator(); 39 40 // Branch - See if we are conditional jumping on constant 41 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 42 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 43 BasicBlock *Dest1 = BI->getSuccessor(0); 44 BasicBlock *Dest2 = BI->getSuccessor(1); 45 46 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 47 // Are we branching on constant? 48 // YES. Change to unconditional branch... 49 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 50 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 51 52 //cerr << "Function: " << T->getParent()->getParent() 53 // << "\nRemoving branch from " << T->getParent() 54 // << "\n\nTo: " << OldDest << endl; 55 56 // Let the basic block know that we are letting go of it. Based on this, 57 // it will adjust it's PHI nodes. 58 assert(BI->getParent() && "Terminator not inserted in block!"); 59 OldDest->removePredecessor(BI->getParent()); 60 61 // Set the unconditional destination, and change the insn to be an 62 // unconditional branch. 63 BI->setUnconditionalDest(Destination); 64 return true; 65 } else if (Dest2 == Dest1) { // Conditional branch to same location? 66 // This branch matches something like this: 67 // br bool %cond, label %Dest, label %Dest 68 // and changes it into: br label %Dest 69 70 // Let the basic block know that we are letting go of one copy of it. 71 assert(BI->getParent() && "Terminator not inserted in block!"); 72 Dest1->removePredecessor(BI->getParent()); 73 74 // Change a conditional branch to unconditional. 75 BI->setUnconditionalDest(Dest1); 76 return true; 77 } 78 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 79 // If we are switching on a constant, we can convert the switch into a 80 // single branch instruction! 81 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 82 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 83 BasicBlock *DefaultDest = TheOnlyDest; 84 assert(TheOnlyDest == SI->getDefaultDest() && 85 "Default destination is not successor #0?"); 86 87 // Figure out which case it goes to... 88 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 89 // Found case matching a constant operand? 90 if (SI->getSuccessorValue(i) == CI) { 91 TheOnlyDest = SI->getSuccessor(i); 92 break; 93 } 94 95 // Check to see if this branch is going to the same place as the default 96 // dest. If so, eliminate it as an explicit compare. 97 if (SI->getSuccessor(i) == DefaultDest) { 98 // Remove this entry... 99 DefaultDest->removePredecessor(SI->getParent()); 100 SI->removeCase(i); 101 --i; --e; // Don't skip an entry... 102 continue; 103 } 104 105 // Otherwise, check to see if the switch only branches to one destination. 106 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 107 // destinations. 108 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 109 } 110 111 if (CI && !TheOnlyDest) { 112 // Branching on a constant, but not any of the cases, go to the default 113 // successor. 114 TheOnlyDest = SI->getDefaultDest(); 115 } 116 117 // If we found a single destination that we can fold the switch into, do so 118 // now. 119 if (TheOnlyDest) { 120 // Insert the new branch.. 121 BranchInst::Create(TheOnlyDest, SI); 122 BasicBlock *BB = SI->getParent(); 123 124 // Remove entries from PHI nodes which we no longer branch to... 125 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 126 // Found case matching a constant operand? 127 BasicBlock *Succ = SI->getSuccessor(i); 128 if (Succ == TheOnlyDest) 129 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 130 else 131 Succ->removePredecessor(BB); 132 } 133 134 // Delete the old switch... 135 BB->getInstList().erase(SI); 136 return true; 137 } else if (SI->getNumSuccessors() == 2) { 138 // Otherwise, we can fold this switch into a conditional branch 139 // instruction if it has only one non-default destination. 140 Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, SI->getCondition(), 141 SI->getSuccessorValue(1), "cond", SI); 142 // Insert the new branch... 143 BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 144 145 // Delete the old switch... 146 SI->eraseFromParent(); 147 return true; 148 } 149 } 150 return false; 151} 152 153 154//===----------------------------------------------------------------------===// 155// Local dead code elimination... 156// 157 158/// isInstructionTriviallyDead - Return true if the result produced by the 159/// instruction is not used, and the instruction has no side effects. 160/// 161bool llvm::isInstructionTriviallyDead(Instruction *I) { 162 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 163 164 // We don't want debug info removed by anything this general. 165 if (isa<DbgInfoIntrinsic>(I)) return false; 166 167 if (!I->mayWriteToMemory()) 168 return true; 169 170 // Special case intrinsics that "may write to memory" but can be deleted when 171 // dead. 172 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 173 // Safe to delete llvm.stacksave if dead. 174 if (II->getIntrinsicID() == Intrinsic::stacksave) 175 return true; 176 177 return false; 178} 179 180/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 181/// trivially dead instruction, delete it. If that makes any of its operands 182/// trivially dead, delete them too, recursively. 183/// 184/// If DeadInst is specified, the vector is filled with the instructions that 185/// are actually deleted. 186void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 187 SmallVectorImpl<Instruction*> *DeadInst) { 188 Instruction *I = dyn_cast<Instruction>(V); 189 if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) 190 return; 191 192 SmallVector<Instruction*, 16> DeadInsts; 193 DeadInsts.push_back(I); 194 195 while (!DeadInsts.empty()) { 196 I = DeadInsts.back(); 197 DeadInsts.pop_back(); 198 199 // If the client wanted to know, tell it about deleted instructions. 200 if (DeadInst) 201 DeadInst->push_back(I); 202 203 // Null out all of the instruction's operands to see if any operand becomes 204 // dead as we go. 205 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 206 Value *OpV = I->getOperand(i); 207 I->setOperand(i, 0); 208 209 if (!OpV->use_empty()) continue; 210 211 // If the operand is an instruction that became dead as we nulled out the 212 // operand, and if it is 'trivially' dead, delete it in a future loop 213 // iteration. 214 if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 215 if (isInstructionTriviallyDead(OpI)) 216 DeadInsts.push_back(OpI); 217 } 218 219 I->eraseFromParent(); 220 } 221} 222 223 224//===----------------------------------------------------------------------===// 225// Control Flow Graph Restructuring... 226// 227 228/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 229/// predecessor is known to have one successor (DestBB!). Eliminate the edge 230/// between them, moving the instructions in the predecessor into DestBB and 231/// deleting the predecessor block. 232/// 233void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB) { 234 // If BB has single-entry PHI nodes, fold them. 235 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 236 Value *NewVal = PN->getIncomingValue(0); 237 // Replace self referencing PHI with undef, it must be dead. 238 if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 239 PN->replaceAllUsesWith(NewVal); 240 PN->eraseFromParent(); 241 } 242 243 BasicBlock *PredBB = DestBB->getSinglePredecessor(); 244 assert(PredBB && "Block doesn't have a single predecessor!"); 245 246 // Splice all the instructions from PredBB to DestBB. 247 PredBB->getTerminator()->eraseFromParent(); 248 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 249 250 // Anything that branched to PredBB now branches to DestBB. 251 PredBB->replaceAllUsesWith(DestBB); 252 253 // Nuke BB. 254 PredBB->eraseFromParent(); 255} 256 257/// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used 258/// by DbgIntrinsics. If DbgInUses is specified then the vector is filled 259/// with the DbgInfoIntrinsic that use the instruction I. 260bool llvm::OnlyUsedByDbgInfoIntrinsics(Instruction *I, 261 SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses) { 262 if (DbgInUses) 263 DbgInUses->clear(); 264 265 if (I->use_empty()) 266 return false; 267 268 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; 269 ++UI) { 270 if (DbgInfoIntrinsic *DI = dyn_cast<DbgInfoIntrinsic>(*UI)) { 271 if (DbgInUses) 272 DbgInUses->push_back(DI); 273 } else { 274 if (DbgInUses) 275 DbgInUses->clear(); 276 return false; 277 } 278 } 279 return true; 280} 281 282/// UserIsDebugInfo - Return true if U is a constant expr used by 283/// llvm.dbg.variable or llvm.dbg.global_variable 284bool llvm::UserIsDebugInfo(User *U) { 285 ConstantExpr *CE = dyn_cast<ConstantExpr>(U); 286 287 if (!CE || CE->getNumUses() != 1) 288 return false; 289 290 Constant *Init = dyn_cast<Constant>(CE->use_back()); 291 if (!Init || Init->getNumUses() != 1) 292 return false; 293 294 GlobalVariable *GV = dyn_cast<GlobalVariable>(Init->use_back()); 295 if (!GV || !GV->hasInitializer() || GV->getInitializer() != Init) 296 return false; 297 298 DIVariable DV(GV); 299 if (!DV.isNull()) 300 return true; // User is llvm.dbg.variable 301 302 DIGlobalVariable DGV(GV); 303 if (!DGV.isNull()) 304 return true; // User is llvm.dbg.global_variable 305 306 return false; 307} 308 309/// RemoveDbgInfoUser - Remove an User which is representing debug info. 310void llvm::RemoveDbgInfoUser(User *U) { 311 assert (UserIsDebugInfo(U) && "Unexpected User!"); 312 ConstantExpr *CE = cast<ConstantExpr>(U); 313 while (!CE->use_empty()) { 314 Constant *C = cast<Constant>(CE->use_back()); 315 while (!C->use_empty()) { 316 GlobalVariable *GV = cast<GlobalVariable>(C->use_back()); 317 GV->eraseFromParent(); 318 } 319 C->destroyConstant(); 320 } 321 CE->destroyConstant(); 322} 323