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