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