LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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/Support/MathExtras.h"
00016 #include "llvm/Transforms/Utils/Local.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/Instructions.h"
00019 #include "llvm/Intrinsics.h"
00020 #include <cerrno>
00021 #include <cmath>
00022 using namespace llvm;
00023 
00024 //===----------------------------------------------------------------------===//
00025 //  Local constant propagation...
00026 //
00027 
00028 /// doConstantPropagation - If an instruction references constants, try to fold
00029 /// them together...
00030 ///
00031 bool llvm::doConstantPropagation(BasicBlock::iterator &II) {
00032   if (Constant *C = ConstantFoldInstruction(II)) {
00033     // Replaces all of the uses of a variable with uses of the constant.
00034     II->replaceAllUsesWith(C);
00035     
00036     // Remove the instruction from the basic block...
00037     II = II->getParent()->getInstList().erase(II);
00038     return true;
00039   }
00040 
00041   return false;
00042 }
00043 
00044 /// ConstantFoldInstruction - Attempt to constant fold the specified
00045 /// instruction.  If successful, the constant result is returned, if not, null
00046 /// is returned.  Note that this function can only fail when attempting to fold
00047 /// instructions like loads and stores, which have no constant expression form.
00048 ///
00049 Constant *llvm::ConstantFoldInstruction(Instruction *I) {
00050   if (PHINode *PN = dyn_cast<PHINode>(I)) {
00051     if (PN->getNumIncomingValues() == 0)
00052       return Constant::getNullValue(PN->getType());
00053     
00054     Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
00055     if (Result == 0) return 0;
00056 
00057     // Handle PHI nodes specially here...
00058     for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
00059       if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
00060         return 0;   // Not all the same incoming constants...
00061     
00062     // If we reach here, all incoming values are the same constant.
00063     return Result;
00064   } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
00065     if (Function *F = CI->getCalledFunction())
00066       if (canConstantFoldCallTo(F)) {
00067         std::vector<Constant*> Args;
00068         for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
00069           if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i)))
00070             Args.push_back(Op);
00071           else
00072             return 0;
00073         return ConstantFoldCall(F, Args);
00074       }
00075     return 0;
00076   }
00077 
00078   Constant *Op0 = 0, *Op1 = 0;
00079   switch (I->getNumOperands()) {
00080   default:
00081   case 2:
00082     Op1 = dyn_cast<Constant>(I->getOperand(1));
00083     if (Op1 == 0) return 0;        // Not a constant?, can't fold
00084   case 1:
00085     Op0 = dyn_cast<Constant>(I->getOperand(0));
00086     if (Op0 == 0) return 0;        // Not a constant?, can't fold
00087     break;
00088   case 0: return 0;
00089   }
00090 
00091   if (isa<BinaryOperator>(I) || isa<ShiftInst>(I))
00092     return ConstantExpr::get(I->getOpcode(), Op0, Op1);    
00093 
00094   switch (I->getOpcode()) {
00095   default: return 0;
00096   case Instruction::Cast:
00097     return ConstantExpr::getCast(Op0, I->getType());
00098   case Instruction::Select:
00099     if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2)))
00100       return ConstantExpr::getSelect(Op0, Op1, Op2);
00101     return 0;
00102   case Instruction::GetElementPtr:
00103     std::vector<Constant*> IdxList;
00104     IdxList.reserve(I->getNumOperands()-1);
00105     if (Op1) IdxList.push_back(Op1);
00106     for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i)
00107       if (Constant *C = dyn_cast<Constant>(I->getOperand(i)))
00108         IdxList.push_back(C);
00109       else
00110         return 0;  // Non-constant operand
00111     return ConstantExpr::getGetElementPtr(Op0, IdxList);
00112   }
00113 }
00114 
00115 // ConstantFoldTerminator - If a terminator instruction is predicated on a
00116 // constant value, convert it into an unconditional branch to the constant
00117 // destination.
00118 //
00119 bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
00120   TerminatorInst *T = BB->getTerminator();
00121       
00122   // Branch - See if we are conditional jumping on constant
00123   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
00124     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
00125     BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
00126     BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
00127 
00128     if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
00129       // Are we branching on constant?
00130       // YES.  Change to unconditional branch...
00131       BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
00132       BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
00133 
00134       //cerr << "Function: " << T->getParent()->getParent() 
00135       //     << "\nRemoving branch from " << T->getParent() 
00136       //     << "\n\nTo: " << OldDest << endl;
00137 
00138       // Let the basic block know that we are letting go of it.  Based on this,
00139       // it will adjust it's PHI nodes.
00140       assert(BI->getParent() && "Terminator not inserted in block!");
00141       OldDest->removePredecessor(BI->getParent());
00142 
00143       // Set the unconditional destination, and change the insn to be an
00144       // unconditional branch.
00145       BI->setUnconditionalDest(Destination);
00146       return true;
00147     } else if (Dest2 == Dest1) {       // Conditional branch to same location?
00148       // This branch matches something like this:  
00149       //     br bool %cond, label %Dest, label %Dest
00150       // and changes it into:  br label %Dest
00151 
00152       // Let the basic block know that we are letting go of one copy of it.
00153       assert(BI->getParent() && "Terminator not inserted in block!");
00154       Dest1->removePredecessor(BI->getParent());
00155 
00156       // Change a conditional branch to unconditional.
00157       BI->setUnconditionalDest(Dest1);
00158       return true;
00159     }
00160   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
00161     // If we are switching on a constant, we can convert the switch into a
00162     // single branch instruction!
00163     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
00164     BasicBlock *TheOnlyDest = SI->getSuccessor(0);  // The default dest
00165     BasicBlock *DefaultDest = TheOnlyDest;
00166     assert(TheOnlyDest == SI->getDefaultDest() &&
00167            "Default destination is not successor #0?");
00168 
00169     // Figure out which case it goes to...
00170     for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
00171       // Found case matching a constant operand?
00172       if (SI->getSuccessorValue(i) == CI) {
00173         TheOnlyDest = SI->getSuccessor(i);
00174         break;
00175       }
00176 
00177       // Check to see if this branch is going to the same place as the default
00178       // dest.  If so, eliminate it as an explicit compare.
00179       if (SI->getSuccessor(i) == DefaultDest) {
00180         // Remove this entry...
00181         DefaultDest->removePredecessor(SI->getParent());
00182         SI->removeCase(i);
00183         --i; --e;  // Don't skip an entry...
00184         continue;
00185       }
00186 
00187       // Otherwise, check to see if the switch only branches to one destination.
00188       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
00189       // destinations.
00190       if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
00191     }
00192 
00193     if (CI && !TheOnlyDest) {
00194       // Branching on a constant, but not any of the cases, go to the default
00195       // successor.
00196       TheOnlyDest = SI->getDefaultDest();
00197     }
00198 
00199     // If we found a single destination that we can fold the switch into, do so
00200     // now.
00201     if (TheOnlyDest) {
00202       // Insert the new branch..
00203       new BranchInst(TheOnlyDest, SI);
00204       BasicBlock *BB = SI->getParent();
00205 
00206       // Remove entries from PHI nodes which we no longer branch to...
00207       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
00208         // Found case matching a constant operand?
00209         BasicBlock *Succ = SI->getSuccessor(i);
00210         if (Succ == TheOnlyDest)
00211           TheOnlyDest = 0;  // Don't modify the first branch to TheOnlyDest
00212         else
00213           Succ->removePredecessor(BB);
00214       }
00215 
00216       // Delete the old switch...
00217       BB->getInstList().erase(SI);
00218       return true;
00219     } else if (SI->getNumSuccessors() == 2) {
00220       // Otherwise, we can fold this switch into a conditional branch
00221       // instruction if it has only one non-default destination.
00222       Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(),
00223                                     SI->getSuccessorValue(1), "cond", SI);
00224       // Insert the new branch...
00225       new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
00226 
00227       // Delete the old switch...
00228       SI->getParent()->getInstList().erase(SI);
00229       return true;
00230     }
00231   }
00232   return false;
00233 }
00234 
00235 /// canConstantFoldCallTo - Return true if its even possible to fold a call to
00236 /// the specified function.
00237 bool llvm::canConstantFoldCallTo(Function *F) {
00238   const std::string &Name = F->getName();
00239 
00240   switch (F->getIntrinsicID()) {
00241   case Intrinsic::isunordered: return true;
00242   default: break;
00243   }
00244 
00245   return Name == "sin" || Name == "cos" || Name == "tan" || Name == "sqrt" ||
00246          Name == "log" || Name == "log10" || Name == "exp" || Name == "pow" ||
00247          Name == "acos" || Name == "asin" || Name == "atan" || Name == "fmod";
00248 }
00249 
00250 static Constant *ConstantFoldFP(double (*NativeFP)(double), double V,
00251                                 const Type *Ty) {
00252   errno = 0;
00253   V = NativeFP(V);
00254   if (errno == 0)
00255     return ConstantFP::get(Ty, V);
00256   return 0;
00257 }
00258 
00259 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
00260 /// with the specified arguments, returning null if unsuccessful.
00261 Constant *llvm::ConstantFoldCall(Function *F,
00262                                  const std::vector<Constant*> &Operands) {
00263   const std::string &Name = F->getName();
00264   const Type *Ty = F->getReturnType();
00265 
00266   if (Operands.size() == 1) {
00267     if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) {
00268       double V = Op->getValue();
00269       if (Name == "sin")
00270         return ConstantFP::get(Ty, sin(V));
00271       else if (Name == "cos")
00272         return ConstantFP::get(Ty, cos(V));
00273       else if (Name == "tan")
00274         return ConstantFP::get(Ty, tan(V));
00275       else if (Name == "sqrt" && V >= 0)
00276         return ConstantFP::get(Ty, sqrt(V));
00277       else if (Name == "exp")
00278         return ConstantFP::get(Ty, exp(V));
00279       else if (Name == "log" && V > 0)
00280         return ConstantFP::get(Ty, log(V));
00281       else if (Name == "log10")
00282         return ConstantFoldFP(log10, V, Ty);
00283       else if (Name == "acos")
00284         return ConstantFoldFP(acos, V, Ty);
00285       else if (Name == "asin")
00286         return ConstantFoldFP(asin, V, Ty);
00287       else if (Name == "atan")
00288         return ConstantFP::get(Ty, atan(V));
00289     }
00290   } else if (Operands.size() == 2) {
00291     if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0]))
00292       if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
00293         double Op1V = Op1->getValue(), Op2V = Op2->getValue();
00294 
00295         if (Name == "llvm.isunordered")
00296           return ConstantBool::get(IsNAN(Op1V) || IsNAN(Op2V));
00297         else 
00298         if (Name == "pow") {
00299           errno = 0;
00300           double V = pow(Op1V, Op2V);
00301           if (errno == 0)
00302             return ConstantFP::get(Ty, V);
00303         } else if (Name == "fmod") {
00304           errno = 0;
00305           double V = fmod(Op1V, Op2V);
00306           if (errno == 0)
00307             return ConstantFP::get(Ty, V);
00308         }
00309       }
00310   }
00311   return 0;
00312 }
00313 
00314 
00315 
00316 
00317 //===----------------------------------------------------------------------===//
00318 //  Local dead code elimination...
00319 //
00320 
00321 bool llvm::isInstructionTriviallyDead(Instruction *I) {
00322   return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I);
00323 }
00324 
00325 // dceInstruction - Inspect the instruction at *BBI and figure out if it's
00326 // [trivially] dead.  If so, remove the instruction and update the iterator
00327 // to point to the instruction that immediately succeeded the original
00328 // instruction.
00329 //
00330 bool llvm::dceInstruction(BasicBlock::iterator &BBI) {
00331   // Look for un"used" definitions...
00332   if (isInstructionTriviallyDead(BBI)) {
00333     BBI = BBI->getParent()->getInstList().erase(BBI);   // Bye bye
00334     return true;
00335   }
00336   return false;
00337 }
00338 
00339 //===----------------------------------------------------------------------===//
00340 //  PHI Instruction Simplification
00341 //
00342 
00343 /// hasConstantValue - If the specified PHI node always merges together the same
00344 /// value, return the value, otherwise return null.
00345 ///
00346 Value *llvm::hasConstantValue(PHINode *PN) {
00347   // If the PHI node only has one incoming value, eliminate the PHI node...
00348   if (PN->getNumIncomingValues() == 1)
00349     return PN->getIncomingValue(0);
00350 
00351   // Otherwise if all of the incoming values are the same for the PHI, replace
00352   // the PHI node with the incoming value.
00353   //
00354   Value *InVal = 0;
00355   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00356     if (PN->getIncomingValue(i) != PN &&  // Not the PHI node itself...
00357         !isa<UndefValue>(PN->getIncomingValue(i)))
00358       if (InVal && PN->getIncomingValue(i) != InVal)
00359         return 0;  // Not the same, bail out.
00360       else
00361         InVal = PN->getIncomingValue(i);
00362 
00363   // The only case that could cause InVal to be null is if we have a PHI node
00364   // that only has entries for itself.  In this case, there is no entry into the
00365   // loop, so kill the PHI.
00366   //
00367   if (InVal == 0) InVal = UndefValue::get(PN->getType());
00368 
00369   // All of the incoming values are the same, return the value now.
00370   return InVal;
00371 }