Local.cpp revision 8dfe5705b16eeebec701f725351cc5a6102e0dfd
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> 20using namespace llvm; 21 22//===----------------------------------------------------------------------===// 23// Local constant propagation... 24// 25 26/// doConstantPropagation - If an instruction references constants, try to fold 27/// them together... 28/// 29bool 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/// 47Constant *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// 117bool 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. 235bool 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 Name == "acos" || Name == "asin" || Name == "atan" || Name == "fmod"; 240} 241 242static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 243 const Type *Ty) { 244 errno = 0; 245 V = NativeFP(V); 246 if (errno == 0) 247 return ConstantFP::get(Ty, V); 248 return 0; 249} 250 251/// ConstantFoldCall - Attempt to constant fold a call to the specified function 252/// with the specified arguments, returning null if unsuccessful. 253Constant *llvm::ConstantFoldCall(Function *F, 254 const std::vector<Constant*> &Operands) { 255 const std::string &Name = F->getName(); 256 const Type *Ty = F->getReturnType(); 257 258 if (Operands.size() == 1) { 259 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) { 260 double V = Op->getValue(); 261 if (Name == "sin") 262 return ConstantFP::get(Ty, sin(V)); 263 else if (Name == "cos") 264 return ConstantFP::get(Ty, cos(V)); 265 else if (Name == "tan") 266 return ConstantFP::get(Ty, tan(V)); 267 else if (Name == "sqrt" && V >= 0) 268 return ConstantFP::get(Ty, sqrt(V)); 269 else if (Name == "exp") 270 return ConstantFP::get(Ty, exp(V)); 271 else if (Name == "log" && V > 0) 272 return ConstantFP::get(Ty, log(V)); 273 else if (Name == "log10") 274 return ConstantFoldFP(log10, V, Ty); 275 else if (Name == "acos") 276 return ConstantFoldFP(acos, V, Ty); 277 else if (Name == "asin") 278 return ConstantFoldFP(asin, V, Ty); 279 else if (Name == "atan") 280 return ConstantFP::get(Ty, atan(V)); 281 } 282 } else if (Operands.size() == 2) { 283 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) 284 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) { 285 double Op1V = Op1->getValue(), Op2V = Op2->getValue(); 286 287 if (Name == "pow") { 288 errno = 0; 289 double V = pow(Op1V, Op2V); 290 if (errno == 0) 291 return ConstantFP::get(Ty, V); 292 } else if (Name == "fmod") { 293 errno = 0; 294 double V = fmod(Op1V, Op2V); 295 if (errno == 0) 296 return ConstantFP::get(Ty, V); 297 } 298 } 299 } 300 return 0; 301} 302 303 304 305 306//===----------------------------------------------------------------------===// 307// Local dead code elimination... 308// 309 310bool llvm::isInstructionTriviallyDead(Instruction *I) { 311 return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I); 312} 313 314// dceInstruction - Inspect the instruction at *BBI and figure out if it's 315// [trivially] dead. If so, remove the instruction and update the iterator 316// to point to the instruction that immediately succeeded the original 317// instruction. 318// 319bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 320 // Look for un"used" definitions... 321 if (isInstructionTriviallyDead(BBI)) { 322 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 323 return true; 324 } 325 return false; 326} 327 328//===----------------------------------------------------------------------===// 329// PHI Instruction Simplification 330// 331 332/// hasConstantValue - If the specified PHI node always merges together the same 333/// value, return the value, otherwise return null. 334/// 335Value *llvm::hasConstantValue(PHINode *PN) { 336 // If the PHI node only has one incoming value, eliminate the PHI node... 337 if (PN->getNumIncomingValues() == 1) 338 return PN->getIncomingValue(0); 339 340 // Otherwise if all of the incoming values are the same for the PHI, replace 341 // the PHI node with the incoming value. 342 // 343 Value *InVal = 0; 344 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 345 if (PN->getIncomingValue(i) != PN) // Not the PHI node itself... 346 if (InVal && PN->getIncomingValue(i) != InVal) 347 return 0; // Not the same, bail out. 348 else 349 InVal = PN->getIncomingValue(i); 350 351 // The only case that could cause InVal to be null is if we have a PHI node 352 // that only has entries for itself. In this case, there is no entry into the 353 // loop, so kill the PHI. 354 // 355 if (InVal == 0) InVal = Constant::getNullValue(PN->getType()); 356 357 // All of the incoming values are the same, return the value now. 358 return InVal; 359} 360