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