LLVM API Documentation
00001 //===-- Local.cpp - Functions to perform local transformations ------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This family of functions perform various local transformations to the 00011 // program. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Transforms/Utils/Local.h" 00016 #include "llvm/Constants.h" 00017 #include "llvm/GlobalAlias.h" 00018 #include "llvm/GlobalVariable.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Instructions.h" 00021 #include "llvm/Intrinsics.h" 00022 #include "llvm/IntrinsicInst.h" 00023 #include "llvm/LLVMContext.h" 00024 #include "llvm/ADT/SmallPtrSet.h" 00025 #include "llvm/Analysis/ConstantFolding.h" 00026 #include "llvm/Analysis/DebugInfo.h" 00027 #include "llvm/Target/TargetData.h" 00028 #include "llvm/Support/GetElementPtrTypeIterator.h" 00029 #include "llvm/Support/MathExtras.h" 00030 using namespace llvm; 00031 00032 //===----------------------------------------------------------------------===// 00033 // Local analysis. 00034 // 00035 00036 /// isSafeToLoadUnconditionally - Return true if we know that executing a load 00037 /// from this value cannot trap. If it is not obviously safe to load from the 00038 /// specified pointer, we do a quick local scan of the basic block containing 00039 /// ScanFrom, to determine if the address is already accessed. 00040 bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) { 00041 // If it is an alloca it is always safe to load from. 00042 if (isa<AllocaInst>(V)) return true; 00043 00044 // If it is a global variable it is mostly safe to load from. 00045 if (const GlobalValue *GV = dyn_cast<GlobalVariable>(V)) 00046 // Don't try to evaluate aliases. External weak GV can be null. 00047 return !isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage(); 00048 00049 // Otherwise, be a little bit agressive by scanning the local block where we 00050 // want to check to see if the pointer is already being loaded or stored 00051 // from/to. If so, the previous load or store would have already trapped, 00052 // so there is no harm doing an extra load (also, CSE will later eliminate 00053 // the load entirely). 00054 BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin(); 00055 00056 while (BBI != E) { 00057 --BBI; 00058 00059 // If we see a free or a call which may write to memory (i.e. which might do 00060 // a free) the pointer could be marked invalid. 00061 if (isa<FreeInst>(BBI) || 00062 (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 00063 !isa<DbgInfoIntrinsic>(BBI))) 00064 return false; 00065 00066 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 00067 if (LI->getOperand(0) == V) return true; 00068 } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 00069 if (SI->getOperand(1) == V) return true; 00070 } 00071 } 00072 return false; 00073 } 00074 00075 00076 //===----------------------------------------------------------------------===// 00077 // Local constant propagation. 00078 // 00079 00080 // ConstantFoldTerminator - If a terminator instruction is predicated on a 00081 // constant value, convert it into an unconditional branch to the constant 00082 // destination. 00083 // 00084 bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 00085 TerminatorInst *T = BB->getTerminator(); 00086 00087 // Branch - See if we are conditional jumping on constant 00088 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 00089 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 00090 BasicBlock *Dest1 = BI->getSuccessor(0); 00091 BasicBlock *Dest2 = BI->getSuccessor(1); 00092 00093 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 00094 // Are we branching on constant? 00095 // YES. Change to unconditional branch... 00096 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 00097 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 00098 00099 //cerr << "Function: " << T->getParent()->getParent() 00100 // << "\nRemoving branch from " << T->getParent() 00101 // << "\n\nTo: " << OldDest << endl; 00102 00103 // Let the basic block know that we are letting go of it. Based on this, 00104 // it will adjust it's PHI nodes. 00105 assert(BI->getParent() && "Terminator not inserted in block!"); 00106 OldDest->removePredecessor(BI->getParent()); 00107 00108 // Set the unconditional destination, and change the insn to be an 00109 // unconditional branch. 00110 BI->setUnconditionalDest(Destination); 00111 return true; 00112 } else if (Dest2 == Dest1) { // Conditional branch to same location? 00113 // This branch matches something like this: 00114 // br bool %cond, label %Dest, label %Dest 00115 // and changes it into: br label %Dest 00116 00117 // Let the basic block know that we are letting go of one copy of it. 00118 assert(BI->getParent() && "Terminator not inserted in block!"); 00119 Dest1->removePredecessor(BI->getParent()); 00120 00121 // Change a conditional branch to unconditional. 00122 BI->setUnconditionalDest(Dest1); 00123 return true; 00124 } 00125 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 00126 // If we are switching on a constant, we can convert the switch into a 00127 // single branch instruction! 00128 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 00129 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 00130 BasicBlock *DefaultDest = TheOnlyDest; 00131 assert(TheOnlyDest == SI->getDefaultDest() && 00132 "Default destination is not successor #0?"); 00133 00134 // Figure out which case it goes to... 00135 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 00136 // Found case matching a constant operand? 00137 if (SI->getSuccessorValue(i) == CI) { 00138 TheOnlyDest = SI->getSuccessor(i); 00139 break; 00140 } 00141 00142 // Check to see if this branch is going to the same place as the default 00143 // dest. If so, eliminate it as an explicit compare. 00144 if (SI->getSuccessor(i) == DefaultDest) { 00145 // Remove this entry... 00146 DefaultDest->removePredecessor(SI->getParent()); 00147 SI->removeCase(i); 00148 --i; --e; // Don't skip an entry... 00149 continue; 00150 } 00151 00152 // Otherwise, check to see if the switch only branches to one destination. 00153 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 00154 // destinations. 00155 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 00156 } 00157 00158 if (CI && !TheOnlyDest) { 00159 // Branching on a constant, but not any of the cases, go to the default 00160 // successor. 00161 TheOnlyDest = SI->getDefaultDest(); 00162 } 00163 00164 // If we found a single destination that we can fold the switch into, do so 00165 // now. 00166 if (TheOnlyDest) { 00167 // Insert the new branch.. 00168 BranchInst::Create(TheOnlyDest, SI); 00169 BasicBlock *BB = SI->getParent(); 00170 00171 // Remove entries from PHI nodes which we no longer branch to... 00172 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 00173 // Found case matching a constant operand? 00174 BasicBlock *Succ = SI->getSuccessor(i); 00175 if (Succ == TheOnlyDest) 00176 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 00177 else 00178 Succ->removePredecessor(BB); 00179 } 00180 00181 // Delete the old switch... 00182 BB->getInstList().erase(SI); 00183 return true; 00184 } else if (SI->getNumSuccessors() == 2) { 00185 // Otherwise, we can fold this switch into a conditional branch 00186 // instruction if it has only one non-default destination. 00187 Value *Cond = new ICmpInst(SI, ICmpInst::ICMP_EQ, SI->getCondition(), 00188 SI->getSuccessorValue(1), "cond"); 00189 // Insert the new branch... 00190 BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 00191 00192 // Delete the old switch... 00193 SI->eraseFromParent(); 00194 return true; 00195 } 00196 } 00197 return false; 00198 } 00199 00200 00201 //===----------------------------------------------------------------------===// 00202 // Local dead code elimination... 00203 // 00204 00205 /// isInstructionTriviallyDead - Return true if the result produced by the 00206 /// instruction is not used, and the instruction has no side effects. 00207 /// 00208 bool llvm::isInstructionTriviallyDead(Instruction *I) { 00209 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 00210 00211 // We don't want debug info removed by anything this general. 00212 if (isa<DbgInfoIntrinsic>(I)) return false; 00213 00214 if (!I->mayHaveSideEffects()) return true; 00215 00216 // Special case intrinsics that "may have side effects" but can be deleted 00217 // when dead. 00218 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 00219 // Safe to delete llvm.stacksave if dead. 00220 if (II->getIntrinsicID() == Intrinsic::stacksave) 00221 return true; 00222 return false; 00223 } 00224 00225 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 00226 /// trivially dead instruction, delete it. If that makes any of its operands 00227 /// trivially dead, delete them too, recursively. 00228 void llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { 00229 Instruction *I = dyn_cast<Instruction>(V); 00230 if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) 00231 return; 00232 00233 SmallVector<Instruction*, 16> DeadInsts; 00234 DeadInsts.push_back(I); 00235 00236 while (!DeadInsts.empty()) { 00237 I = DeadInsts.pop_back_val(); 00238 00239 // Null out all of the instruction's operands to see if any operand becomes 00240 // dead as we go. 00241 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 00242 Value *OpV = I->getOperand(i); 00243 I->setOperand(i, 0); 00244 00245 if (!OpV->use_empty()) continue; 00246 00247 // If the operand is an instruction that became dead as we nulled out the 00248 // operand, and if it is 'trivially' dead, delete it in a future loop 00249 // iteration. 00250 if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 00251 if (isInstructionTriviallyDead(OpI)) 00252 DeadInsts.push_back(OpI); 00253 } 00254 00255 I->eraseFromParent(); 00256 } 00257 } 00258 00259 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 00260 /// dead PHI node, due to being a def-use chain of single-use nodes that 00261 /// either forms a cycle or is terminated by a trivially dead instruction, 00262 /// delete it. If that makes any of its operands trivially dead, delete them 00263 /// too, recursively. 00264 void 00265 llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { 00266 // We can remove a PHI if it is on a cycle in the def-use graph 00267 // where each node in the cycle has degree one, i.e. only one use, 00268 // and is an instruction with no side effects. 00269 if (!PN->hasOneUse()) 00270 return; 00271 00272 SmallPtrSet<PHINode *, 4> PHIs; 00273 PHIs.insert(PN); 00274 for (Instruction *J = cast<Instruction>(*PN->use_begin()); 00275 J->hasOneUse() && !J->mayHaveSideEffects(); 00276 J = cast<Instruction>(*J->use_begin())) 00277 // If we find a PHI more than once, we're on a cycle that 00278 // won't prove fruitful. 00279 if (PHINode *JP = dyn_cast<PHINode>(J)) 00280 if (!PHIs.insert(cast<PHINode>(JP))) { 00281 // Break the cycle and delete the PHI and its operands. 00282 JP->replaceAllUsesWith(UndefValue::get(JP->getType())); 00283 RecursivelyDeleteTriviallyDeadInstructions(JP); 00284 break; 00285 } 00286 } 00287 00288 //===----------------------------------------------------------------------===// 00289 // Control Flow Graph Restructuring... 00290 // 00291 00292 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 00293 /// predecessor is known to have one successor (DestBB!). Eliminate the edge 00294 /// between them, moving the instructions in the predecessor into DestBB and 00295 /// deleting the predecessor block. 00296 /// 00297 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB) { 00298 // If BB has single-entry PHI nodes, fold them. 00299 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 00300 Value *NewVal = PN->getIncomingValue(0); 00301 // Replace self referencing PHI with undef, it must be dead. 00302 if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 00303 PN->replaceAllUsesWith(NewVal); 00304 PN->eraseFromParent(); 00305 } 00306 00307 BasicBlock *PredBB = DestBB->getSinglePredecessor(); 00308 assert(PredBB && "Block doesn't have a single predecessor!"); 00309 00310 // Splice all the instructions from PredBB to DestBB. 00311 PredBB->getTerminator()->eraseFromParent(); 00312 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 00313 00314 // Anything that branched to PredBB now branches to DestBB. 00315 PredBB->replaceAllUsesWith(DestBB); 00316 00317 // Nuke BB. 00318 PredBB->eraseFromParent(); 00319 } 00320 00321 /// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used 00322 /// by DbgIntrinsics. If DbgInUses is specified then the vector is filled 00323 /// with the DbgInfoIntrinsic that use the instruction I. 00324 bool llvm::OnlyUsedByDbgInfoIntrinsics(Instruction *I, 00325 SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses) { 00326 if (DbgInUses) 00327 DbgInUses->clear(); 00328 00329 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; 00330 ++UI) { 00331 if (DbgInfoIntrinsic *DI = dyn_cast<DbgInfoIntrinsic>(*UI)) { 00332 if (DbgInUses) 00333 DbgInUses->push_back(DI); 00334 } else { 00335 if (DbgInUses) 00336 DbgInUses->clear(); 00337 return false; 00338 } 00339 } 00340 return true; 00341 } 00342