lib/Transforms/Utils/Local.cpp

   1 //===-- Local.cpp - Functions to perform local transformations ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This family of functions perform various local transformations to the
  11 // program.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Utils/Local.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/Instructions.h"
  18 #include <cerrno>
  19 #include <cmath>
  20 using namespace llvm;
  21
  22 //===----------------------------------------------------------------------===//
  23 //  Local constant propagation...
  24 //
  25
  26 /// doConstantPropagation - If an instruction references constants, try to fold
  27 /// them together...
  28 ///
  29 bool llvm::doConstantPropagation(BasicBlock::iterator &II) {
  30   if (Constant *C = ConstantFoldInstruction(II)) {
  31     // Replaces all of the uses of a variable with uses of the constant.
  32     II->replaceAllUsesWith(C);
  33
  34     // Remove the instruction from the basic block...
  35     II = II->getParent()->getInstList().erase(II);
  36     return true;
  37   }
  38
  39   return false;
  40 }
  41
  42 /// ConstantFoldInstruction - Attempt to constant fold the specified
  43 /// instruction.  If successful, the constant result is returned, if not, null
  44 /// is returned.  Note that this function can only fail when attempting to fold
  45 /// instructions like loads and stores, which have no constant expression form.
  46 ///
  47 Constant *llvm::ConstantFoldInstruction(Instruction *I) {
  48   if (PHINode *PN = dyn_cast<PHINode>(I)) {
  49     if (PN->getNumIncomingValues() == 0)
  50       return Constant::getNullValue(PN->getType());
  51
  52     Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
  53     if (Result == 0) return 0;
  54
  55     // Handle PHI nodes specially here...
  56     for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
  57       if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
  58         return 0;   // Not all the same incoming constants...
  59
  60     // If we reach here, all incoming values are the same constant.
  61     return Result;
  62   } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
  63     if (Function *F = CI->getCalledFunction())
  64       if (canConstantFoldCallTo(F)) {
  65         std::vector<Constant*> Args;
  66         for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
  67           if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i)))
  68             Args.push_back(Op);
  69           else
  70             return 0;
  71         return ConstantFoldCall(F, Args);
  72       }
  73     return 0;
  74   }
  75
  76   Constant *Op0 = 0, *Op1 = 0;
  77   switch (I->getNumOperands()) {
  78   default:
  79   case 2:
  80     Op1 = dyn_cast<Constant>(I->getOperand(1));
  81     if (Op1 == 0) return 0;        // Not a constant?, can't fold
  82   case 1:
  83     Op0 = dyn_cast<Constant>(I->getOperand(0));
  84     if (Op0 == 0) return 0;        // Not a constant?, can't fold
  85     break;
  86   case 0: return 0;
  87   }
  88
  89   if (isa<BinaryOperator>(I) || isa<ShiftInst>(I))
  90     return ConstantExpr::get(I->getOpcode(), Op0, Op1);
  91
  92   switch (I->getOpcode()) {
  93   default: return 0;
  94   case Instruction::Cast:
  95     return ConstantExpr::getCast(Op0, I->getType());
  96   case Instruction::Select:
  97     if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2)))
  98       return ConstantExpr::getSelect(Op0, Op1, Op2);
  99     return 0;
 100   case Instruction::GetElementPtr:
 101     std::vector<Constant*> IdxList;
 102     IdxList.reserve(I->getNumOperands()-1);
 103     if (Op1) IdxList.push_back(Op1);
 104     for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i)
 105       if (Constant *C = dyn_cast<Constant>(I->getOperand(i)))
 106         IdxList.push_back(C);
 107       else
 108         return 0;  // Non-constant operand
 109     return ConstantExpr::getGetElementPtr(Op0, IdxList);
 110   }
 111 }
 112
 113 // ConstantFoldTerminator - If a terminator instruction is predicated on a
 114 // constant value, convert it into an unconditional branch to the constant
 115 // destination.
 116 //
 117 bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
 118   TerminatorInst *T = BB->getTerminator();
 119
 120   // Branch - See if we are conditional jumping on constant
 121   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
 122     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
 123     BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
 124     BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
 125
 126     if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
 127       // Are we branching on constant?
 128       // YES.  Change to unconditional branch...
 129       BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
 130       BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
 131
 132       //cerr << "Function: " << T->getParent()->getParent()
 133       //     << "\nRemoving branch from " << T->getParent()
 134       //     << "\n\nTo: " << OldDest << endl;
 135
 136       // Let the basic block know that we are letting go of it.  Based on this,
 137       // it will adjust it's PHI nodes.
 138       assert(BI->getParent() && "Terminator not inserted in block!");
 139       OldDest->removePredecessor(BI->getParent());
 140
 141       // Set the unconditional destination, and change the insn to be an
 142       // unconditional branch.
 143       BI->setUnconditionalDest(Destination);
 144       return true;
 145     } else if (Dest2 == Dest1) {       // Conditional branch to same location?
 146       // This branch matches something like this:
 147       //     br bool %cond, label %Dest, label %Dest
 148       // and changes it into:  br label %Dest
 149
 150       // Let the basic block know that we are letting go of one copy of it.
 151       assert(BI->getParent() && "Terminator not inserted in block!");
 152       Dest1->removePredecessor(BI->getParent());
 153
 154       // Change a conditional branch to unconditional.
 155       BI->setUnconditionalDest(Dest1);
 156       return true;
 157     }
 158   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
 159     // If we are switching on a constant, we can convert the switch into a
 160     // single branch instruction!
 161     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
 162     BasicBlock *TheOnlyDest = SI->getSuccessor(0);  // The default dest
 163     BasicBlock *DefaultDest = TheOnlyDest;
 164     assert(TheOnlyDest == SI->getDefaultDest() &&
 165            "Default destination is not successor #0?");
 166
 167     // Figure out which case it goes to...
 168     for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
 169       // Found case matching a constant operand?
 170       if (SI->getSuccessorValue(i) == CI) {
 171         TheOnlyDest = SI->getSuccessor(i);
 172         break;
 173       }
 174
 175       // Check to see if this branch is going to the same place as the default
 176       // dest.  If so, eliminate it as an explicit compare.
 177       if (SI->getSuccessor(i) == DefaultDest) {
 178         // Remove this entry...
 179         DefaultDest->removePredecessor(SI->getParent());
 180         SI->removeCase(i);
 181         --i; --e;  // Don't skip an entry...
 182         continue;
 183       }
 184
 185       // Otherwise, check to see if the switch only branches to one destination.
 186       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
 187       // destinations.
 188       if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0;
 189     }
 190
 191     if (CI && !TheOnlyDest) {
 192       // Branching on a constant, but not any of the cases, go to the default
 193       // successor.
 194       TheOnlyDest = SI->getDefaultDest();
 195     }
 196
 197     // If we found a single destination that we can fold the switch into, do so
 198     // now.
 199     if (TheOnlyDest) {
 200       // Insert the new branch..
 201       new BranchInst(TheOnlyDest, SI);
 202       BasicBlock *BB = SI->getParent();
 203
 204       // Remove entries from PHI nodes which we no longer branch to...
 205       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
 206         // Found case matching a constant operand?
 207         BasicBlock *Succ = SI->getSuccessor(i);
 208         if (Succ == TheOnlyDest)
 209           TheOnlyDest = 0;  // Don't modify the first branch to TheOnlyDest
 210         else
 211           Succ->removePredecessor(BB);
 212       }
 213
 214       // Delete the old switch...
 215       BB->getInstList().erase(SI);
 216       return true;
 217     } else if (SI->getNumSuccessors() == 2) {
 218       // Otherwise, we can fold this switch into a conditional branch
 219       // instruction if it has only one non-default destination.
 220       Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(),
 221                                     SI->getSuccessorValue(1), "cond", SI);
 222       // Insert the new branch...
 223       new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
 224
 225       // Delete the old switch...
 226       SI->getParent()->getInstList().erase(SI);
 227       return true;
 228     }
 229   }
 230   return false;
 231 }
 232
 233 /// canConstantFoldCallTo - Return true if its even possible to fold a call to
 234 /// the specified function.
 235 bool llvm::canConstantFoldCallTo(Function *F) {
 236   const std::string &Name = F->getName();
 237   return Name == "sin" || Name == "cos" || Name == "tan" || Name == "sqrt" ||
 238          Name == "log" || Name == "log10" || Name == "exp" || Name == "pow";
 239 }
 240
 241 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
 242 /// with the specified arguments, returning null if unsuccessful.
 243 Constant *llvm::ConstantFoldCall(Function *F,
 244                                  const std::vector<Constant*> &Operands) {
 245   const std::string &Name = F->getName();
 246   const Type *Ty = F->getReturnType();
 247
 248   if (Name == "sin") {
 249     if (Operands.size() == 1)
 250       if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0]))
 251         return ConstantFP::get(Ty, sin(CFP->getValue()));
 252
 253   } else if (Name == "cos") {
 254     if (Operands.size() == 1)
 255       if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0]))
 256         return ConstantFP::get(Ty, cos(CFP->getValue()));
 257
 258   } else if (Name == "tan") {
 259     if (Operands.size() == 1)
 260       if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0]))
 261         return ConstantFP::get(Ty, tan(CFP->getValue()));
 262
 263   } else if (Name == "sqrt") {
 264     if (Operands.size() == 1)
 265       if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0]))
 266         if (CFP->getValue() >= 0)
 267           return ConstantFP::get(Ty, sqrt(CFP->getValue()));
 268   } else if (Name == "exp") {
 269     if (Operands.size() == 1)
 270       if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0]))
 271         return ConstantFP::get(Ty, exp(CFP->getValue()));
 272   } else if (Name == "log") {
 273     if (Operands.size() == 1)
 274       if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0]))
 275         if (CFP->getValue() > 0)
 276           return ConstantFP::get(Ty, log(CFP->getValue()));
 277   } else if (Name == "log10") {
 278     if (Operands.size() == 1)
 279       if (ConstantFP *CFP = dyn_cast<ConstantFP>(Operands[0]))
 280         if (CFP->getValue() > 0)
 281           return ConstantFP::get(Ty, log10(CFP->getValue()));
 282   } else if (Name == "pow") {
 283     if (Operands.size() == 2)
 284       if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0]))
 285         if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
 286           errno = 0;
 287           double V = pow(Op1->getValue(), Op2->getValue());
 288           if (errno == 0)
 289             return ConstantFP::get(Ty, V);
 290         }
 291   }
 292   return 0;
 293 }
 294
 295
 296
 297
 298 //===----------------------------------------------------------------------===//
 299 //  Local dead code elimination...
 300 //
 301
 302 bool llvm::isInstructionTriviallyDead(Instruction *I) {
 303   return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I);
 304 }
 305
 306 // dceInstruction - Inspect the instruction at *BBI and figure out if it's
 307 // [trivially] dead.  If so, remove the instruction and update the iterator
 308 // to point to the instruction that immediately succeeded the original
 309 // instruction.
 310 //
 311 bool llvm::dceInstruction(BasicBlock::iterator &BBI) {
 312   // Look for un"used" definitions...
 313   if (isInstructionTriviallyDead(BBI)) {
 314     BBI = BBI->getParent()->getInstList().erase(BBI);   // Bye bye
 315     return true;
 316   }
 317   return false;
 318 }
 319
 320 //===----------------------------------------------------------------------===//
 321 //  PHI Instruction Simplification
 322 //
 323
 324 /// hasConstantValue - If the specified PHI node always merges together the same
 325 /// value, return the value, otherwise return null.
 326 ///
 327 Value *llvm::hasConstantValue(PHINode *PN) {
 328   // If the PHI node only has one incoming value, eliminate the PHI node...
 329   if (PN->getNumIncomingValues() == 1)
 330     return PN->getIncomingValue(0);
 331
 332   // Otherwise if all of the incoming values are the same for the PHI, replace
 333   // the PHI node with the incoming value.
 334   //
 335   Value *InVal = 0;
 336   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 337     if (PN->getIncomingValue(i) != PN)  // Not the PHI node itself...
 338       if (InVal && PN->getIncomingValue(i) != InVal)
 339         return 0;  // Not the same, bail out.
 340       else
 341         InVal = PN->getIncomingValue(i);
 342
 343   // The only case that could cause InVal to be null is if we have a PHI node
 344   // that only has entries for itself.  In this case, there is no entry into the
 345   // loop, so kill the PHI.
 346   //
 347   if (InVal == 0) InVal = Constant::getNullValue(PN->getType());
 348
 349   // All of the incoming values are the same, return the value now.
 350   return InVal;
 351 }