LLVM API Documentation

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