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