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