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 was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source 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/DerivedTypes.h"
00018 #include "llvm/Instructions.h"
00019 #include "llvm/Intrinsics.h"
00020 #include "llvm/Analysis/ConstantFolding.h"
00021 #include "llvm/Support/GetElementPtrTypeIterator.h"
00022 #include "llvm/Support/MathExtras.h"
00023 #include <cerrno>
00024 #include <cmath>
00025 using namespace llvm;
00026 
00027 //===----------------------------------------------------------------------===//
00028 //  Local constant propagation...
00029 //
00030 
00031 /// doConstantPropagation - If an instruction references constants, try to fold
00032 /// them together...
00033 ///
00034 bool llvm::doConstantPropagation(BasicBlock::iterator &II) {
00035   if (Constant *C = ConstantFoldInstruction(II)) {
00036     // Replaces all of the uses of a variable with uses of the constant.
00037     II->replaceAllUsesWith(C);
00038 
00039     // Remove the instruction from the basic block...
00040     II = II->getParent()->getInstList().erase(II);
00041     return true;
00042   }
00043 
00044   return false;
00045 }
00046 
00047 /// ConstantFoldInstruction - Attempt to constant fold the specified
00048 /// instruction.  If successful, the constant result is returned, if not, null
00049 /// is returned.  Note that this function can only fail when attempting to fold
00050 /// instructions like loads and stores, which have no constant expression form.
00051 ///
00052 Constant *llvm::ConstantFoldInstruction(Instruction *I) {
00053   if (PHINode *PN = dyn_cast<PHINode>(I)) {
00054     if (PN->getNumIncomingValues() == 0)
00055       return Constant::getNullValue(PN->getType());
00056 
00057     Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
00058     if (Result == 0) return 0;
00059 
00060     // Handle PHI nodes specially here...
00061     for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
00062       if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
00063         return 0;   // Not all the same incoming constants...
00064 
00065     // If we reach here, all incoming values are the same constant.
00066     return Result;
00067   } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
00068     if (Function *F = CI->getCalledFunction())
00069       if (canConstantFoldCallTo(F)) {
00070         std::vector<Constant*> Args;
00071         for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
00072           if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i)))
00073             Args.push_back(Op);
00074           else
00075             return 0;
00076         return ConstantFoldCall(F, Args);
00077       }
00078     return 0;
00079   }
00080 
00081   Constant *Op0 = 0, *Op1 = 0;
00082   switch (I->getNumOperands()) {
00083   default:
00084   case 2:
00085     Op1 = dyn_cast<Constant>(I->getOperand(1));
00086     if (Op1 == 0) return 0;        // Not a constant?, can't fold
00087   case 1:
00088     Op0 = dyn_cast<Constant>(I->getOperand(0));
00089     if (Op0 == 0) return 0;        // Not a constant?, can't fold
00090     break;
00091   case 0: return 0;
00092   }
00093 
00094   if (isa<BinaryOperator>(I) || isa<ShiftInst>(I))
00095     return ConstantExpr::get(I->getOpcode(), Op0, Op1);
00096 
00097   switch (I->getOpcode()) {
00098   default: return 0;
00099   case Instruction::Cast:
00100     return ConstantExpr::getCast(Op0, I->getType());
00101   case Instruction::Select:
00102     if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2)))
00103       return ConstantExpr::getSelect(Op0, Op1, Op2);
00104     return 0;
00105   case Instruction::ExtractElement:
00106     return ConstantExpr::getExtractElement(Op0, Op1);
00107   case Instruction::InsertElement:
00108     if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2)))
00109       return ConstantExpr::getInsertElement(Op0, Op1, Op2);
00110     return 0;
00111   case Instruction::ShuffleVector:
00112     if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2)))
00113       return ConstantExpr::getShuffleVector(Op0, Op1, Op2);
00114     return 0;
00115   case Instruction::GetElementPtr:
00116     std::vector<Constant*> IdxList;
00117     IdxList.reserve(I->getNumOperands()-1);
00118     if (Op1) IdxList.push_back(Op1);
00119     for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i)
00120       if (Constant *C = dyn_cast<Constant>(I->getOperand(i)))
00121         IdxList.push_back(C);
00122       else
00123         return 0;  // Non-constant operand
00124     return ConstantExpr::getGetElementPtr(Op0, IdxList);
00125   }
00126 }
00127 
00128 // ConstantFoldTerminator - If a terminator instruction is predicated on a
00129 // constant value, convert it into an unconditional branch to the constant
00130 // destination.
00131 //
00132 bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
00133   TerminatorInst *T = BB->getTerminator();
00134 
00135   // Branch - See if we are conditional jumping on constant
00136   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
00137     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
00138     BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
00139     BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
00140 
00141     if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
00142       // Are we branching on constant?
00143       // YES.  Change to unconditional branch...
00144       BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
00145       BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
00146 
00147       //cerr << "Function: " << T->getParent()->getParent()
00148       //     << "\nRemoving branch from " << T->getParent()
00149       //     << "\n\nTo: " << OldDest << endl;
00150 
00151       // Let the basic block know that we are letting go of it.  Based on this,
00152       // it will adjust it's PHI nodes.
00153       assert(BI->getParent() && "Terminator not inserted in block!");
00154       OldDest->removePredecessor(BI->getParent());
00155 
00156       // Set the unconditional destination, and change the insn to be an
00157       // unconditional branch.
00158       BI->setUnconditionalDest(Destination);
00159       return true;
00160     } else if (Dest2 == Dest1) {       // Conditional branch to same location?
00161       // This branch matches something like this:
00162       //     br bool %cond, label %Dest, label %Dest
00163       // and changes it into:  br label %Dest
00164 
00165       // Let the basic block know that we are letting go of one copy of it.
00166       assert(BI->getParent() && "Terminator not inserted in block!");
00167       Dest1->removePredecessor(BI->getParent());
00168 
00169       // Change a conditional branch to unconditional.
00170       BI->setUnconditionalDest(Dest1);
00171       return true;
00172     }
00173   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
00174     // If we are switching on a constant, we can convert the switch into a
00175     // single branch instruction!
00176     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
00177     BasicBlock *TheOnlyDest = SI->getSuccessor(0);  // The default dest
00178     BasicBlock *DefaultDest = TheOnlyDest;
00179     assert(TheOnlyDest == SI->getDefaultDest() &&
00180            "Default destination is not successor #0?");
00181 
00182     // Figure out which case it goes to...
00183     for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
00184       // Found case matching a constant operand?
00185       if (SI->getSuccessorValue(i) == CI) {
00186         TheOnlyDest = SI->getSuccessor(i);
00187         break;
00188       }
00189 
00190       // Check to see if this branch is going to the same place as the default
00191       // dest.  If so, eliminate it as an explicit compare.
00192       if (SI->getSuccessor(i) == DefaultDest) {
00193         // Remove this entry...
00194         DefaultDest->removePredecessor(SI->getParent());
00195         SI->removeCase(i);
00196         --i; --e;  // Don't skip an entry...
00197         continue;
00198       }
00199 
00200       // Otherwise, check to see if the switch only branches to one destination.
00201       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
00202       // destinations.
00203       if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
00204     }
00205 
00206     if (CI && !TheOnlyDest) {
00207       // Branching on a constant, but not any of the cases, go to the default
00208       // successor.
00209       TheOnlyDest = SI->getDefaultDest();
00210     }
00211 
00212     // If we found a single destination that we can fold the switch into, do so
00213     // now.
00214     if (TheOnlyDest) {
00215       // Insert the new branch..
00216       new BranchInst(TheOnlyDest, SI);
00217       BasicBlock *BB = SI->getParent();
00218 
00219       // Remove entries from PHI nodes which we no longer branch to...
00220       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
00221         // Found case matching a constant operand?
00222         BasicBlock *Succ = SI->getSuccessor(i);
00223         if (Succ == TheOnlyDest)
00224           TheOnlyDest = 0;  // Don't modify the first branch to TheOnlyDest
00225         else
00226           Succ->removePredecessor(BB);
00227       }
00228 
00229       // Delete the old switch...
00230       BB->getInstList().erase(SI);
00231       return true;
00232     } else if (SI->getNumSuccessors() == 2) {
00233       // Otherwise, we can fold this switch into a conditional branch
00234       // instruction if it has only one non-default destination.
00235       Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(),
00236                                     SI->getSuccessorValue(1), "cond", SI);
00237       // Insert the new branch...
00238       new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
00239 
00240       // Delete the old switch...
00241       SI->getParent()->getInstList().erase(SI);
00242       return true;
00243     }
00244   }
00245   return false;
00246 }
00247 
00248 /// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
00249 /// getelementptr constantexpr, return the constant value being addressed by the
00250 /// constant expression, or null if something is funny and we can't decide.
00251 Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 
00252                                                        ConstantExpr *CE) {
00253   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
00254     return 0;  // Do not allow stepping over the value!
00255   
00256   // Loop over all of the operands, tracking down which value we are
00257   // addressing...
00258   gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
00259   for (++I; I != E; ++I)
00260     if (const StructType *STy = dyn_cast<StructType>(*I)) {
00261       ConstantUInt *CU = cast<ConstantUInt>(I.getOperand());
00262       assert(CU->getValue() < STy->getNumElements() &&
00263              "Struct index out of range!");
00264       unsigned El = (unsigned)CU->getValue();
00265       if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
00266         C = CS->getOperand(El);
00267       } else if (isa<ConstantAggregateZero>(C)) {
00268         C = Constant::getNullValue(STy->getElementType(El));
00269       } else if (isa<UndefValue>(C)) {
00270         C = UndefValue::get(STy->getElementType(El));
00271       } else {
00272         return 0;
00273       }
00274     } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
00275       if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) {
00276         if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0;
00277         if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
00278           C = CA->getOperand((unsigned)CI->getRawValue());
00279         else if (isa<ConstantAggregateZero>(C))
00280           C = Constant::getNullValue(ATy->getElementType());
00281         else if (isa<UndefValue>(C))
00282           C = UndefValue::get(ATy->getElementType());
00283         else
00284           return 0;
00285       } else if (const PackedType *PTy = dyn_cast<PackedType>(*I)) {
00286         if ((uint64_t)CI->getRawValue() >= PTy->getNumElements()) return 0;
00287         if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C))
00288           C = CP->getOperand((unsigned)CI->getRawValue());
00289         else if (isa<ConstantAggregateZero>(C))
00290           C = Constant::getNullValue(PTy->getElementType());
00291         else if (isa<UndefValue>(C))
00292           C = UndefValue::get(PTy->getElementType());
00293         else
00294           return 0;
00295       } else {
00296         return 0;
00297       }
00298     } else {
00299       return 0;
00300     }
00301   return C;
00302 }
00303 
00304 
00305 //===----------------------------------------------------------------------===//
00306 //  Local dead code elimination...
00307 //
00308 
00309 bool llvm::isInstructionTriviallyDead(Instruction *I) {
00310   if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
00311 
00312   if (!I->mayWriteToMemory()) return true;
00313 
00314   if (CallInst *CI = dyn_cast<CallInst>(I))
00315     if (Function *F = CI->getCalledFunction()) {
00316       unsigned IntrinsicID = F->getIntrinsicID();
00317 #define GET_SIDE_EFFECT_INFO
00318 #include "llvm/Intrinsics.gen"
00319 #undef GET_SIDE_EFFECT_INFO
00320     }
00321   return false;
00322 }
00323 
00324 // dceInstruction - Inspect the instruction at *BBI and figure out if it's
00325 // [trivially] dead.  If so, remove the instruction and update the iterator
00326 // to point to the instruction that immediately succeeded the original
00327 // instruction.
00328 //
00329 bool llvm::dceInstruction(BasicBlock::iterator &BBI) {
00330   // Look for un"used" definitions...
00331   if (isInstructionTriviallyDead(BBI)) {
00332     BBI = BBI->getParent()->getInstList().erase(BBI);   // Bye bye
00333     return true;
00334   }
00335   return false;
00336 }