LLVM API Documentation

Local.cpp

Go to the documentation of this file.
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