Local.cpp revision d900c6a8b3de655bac138cfdf4b9a85b7e64ec1c
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/DerivedTypes.h" 18#include "llvm/Instructions.h" 19#include "llvm/Intrinsics.h" 20#include "llvm/Analysis/ConstantFolding.h" 21#include "llvm/Support/GetElementPtrTypeIterator.h" 22#include "llvm/Support/MathExtras.h" 23#include <cerrno> 24#include <cmath> 25using namespace llvm; 26 27//===----------------------------------------------------------------------===// 28// Local constant propagation... 29// 30 31/// doConstantPropagation - If an instruction references constants, try to fold 32/// them together... 33/// 34bool llvm::doConstantPropagation(BasicBlock::iterator &II) { 35 if (Constant *C = ConstantFoldInstruction(II)) { 36 // Replaces all of the uses of a variable with uses of the constant. 37 II->replaceAllUsesWith(C); 38 39 // Remove the instruction from the basic block... 40 II = II->getParent()->getInstList().erase(II); 41 return true; 42 } 43 44 return false; 45} 46 47/// ConstantFoldInstruction - Attempt to constant fold the specified 48/// instruction. If successful, the constant result is returned, if not, null 49/// is returned. Note that this function can only fail when attempting to fold 50/// instructions like loads and stores, which have no constant expression form. 51/// 52Constant *llvm::ConstantFoldInstruction(Instruction *I) { 53 if (PHINode *PN = dyn_cast<PHINode>(I)) { 54 if (PN->getNumIncomingValues() == 0) 55 return Constant::getNullValue(PN->getType()); 56 57 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); 58 if (Result == 0) return 0; 59 60 // Handle PHI nodes specially here... 61 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 62 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) 63 return 0; // Not all the same incoming constants... 64 65 // If we reach here, all incoming values are the same constant. 66 return Result; 67 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 68 if (Function *F = CI->getCalledFunction()) 69 if (canConstantFoldCallTo(F)) { 70 std::vector<Constant*> Args; 71 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 72 if (Constant *Op = dyn_cast<Constant>(CI->getOperand(i))) 73 Args.push_back(Op); 74 else 75 return 0; 76 return ConstantFoldCall(F, Args); 77 } 78 return 0; 79 } 80 81 Constant *Op0 = 0, *Op1 = 0; 82 switch (I->getNumOperands()) { 83 default: 84 case 2: 85 Op1 = dyn_cast<Constant>(I->getOperand(1)); 86 if (Op1 == 0) return 0; // Not a constant?, can't fold 87 case 1: 88 Op0 = dyn_cast<Constant>(I->getOperand(0)); 89 if (Op0 == 0) return 0; // Not a constant?, can't fold 90 break; 91 case 0: return 0; 92 } 93 94 if (isa<BinaryOperator>(I) || isa<ShiftInst>(I)) 95 return ConstantExpr::get(I->getOpcode(), Op0, Op1); 96 97 switch (I->getOpcode()) { 98 default: return 0; 99 case Instruction::Cast: 100 return ConstantExpr::getCast(Op0, I->getType()); 101 case Instruction::Select: 102 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 103 return ConstantExpr::getSelect(Op0, Op1, Op2); 104 return 0; 105 case Instruction::ExtractElement: 106 return ConstantExpr::getExtractElement(Op0, Op1); 107 case Instruction::InsertElement: 108 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 109 return ConstantExpr::getInsertElement(Op0, Op1, Op2); 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/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 244/// getelementptr constantexpr, return the constant value being addressed by the 245/// constant expression, or null if something is funny and we can't decide. 246Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 247 ConstantExpr *CE) { 248 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 249 return 0; // Do not allow stepping over the value! 250 251 // Loop over all of the operands, tracking down which value we are 252 // addressing... 253 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 254 for (++I; I != E; ++I) 255 if (const StructType *STy = dyn_cast<StructType>(*I)) { 256 ConstantUInt *CU = cast<ConstantUInt>(I.getOperand()); 257 assert(CU->getValue() < STy->getNumElements() && 258 "Struct index out of range!"); 259 unsigned El = (unsigned)CU->getValue(); 260 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 261 C = CS->getOperand(El); 262 } else if (isa<ConstantAggregateZero>(C)) { 263 C = Constant::getNullValue(STy->getElementType(El)); 264 } else if (isa<UndefValue>(C)) { 265 C = UndefValue::get(STy->getElementType(El)); 266 } else { 267 return 0; 268 } 269 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 270 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 271 if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0; 272 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 273 C = CA->getOperand((unsigned)CI->getRawValue()); 274 else if (isa<ConstantAggregateZero>(C)) 275 C = Constant::getNullValue(ATy->getElementType()); 276 else if (isa<UndefValue>(C)) 277 C = UndefValue::get(ATy->getElementType()); 278 else 279 return 0; 280 } else if (const PackedType *PTy = dyn_cast<PackedType>(*I)) { 281 if ((uint64_t)CI->getRawValue() >= PTy->getNumElements()) return 0; 282 if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) 283 C = CP->getOperand((unsigned)CI->getRawValue()); 284 else if (isa<ConstantAggregateZero>(C)) 285 C = Constant::getNullValue(PTy->getElementType()); 286 else if (isa<UndefValue>(C)) 287 C = UndefValue::get(PTy->getElementType()); 288 else 289 return 0; 290 } else { 291 return 0; 292 } 293 } else { 294 return 0; 295 } 296 return C; 297} 298 299 300//===----------------------------------------------------------------------===// 301// Local dead code elimination... 302// 303 304bool llvm::isInstructionTriviallyDead(Instruction *I) { 305 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 306 307 if (!I->mayWriteToMemory()) return true; 308 309 if (CallInst *CI = dyn_cast<CallInst>(I)) 310 if (Function *F = CI->getCalledFunction()) 311 switch (F->getIntrinsicID()) { 312 default: break; 313 case Intrinsic::returnaddress: 314 case Intrinsic::frameaddress: 315 case Intrinsic::stacksave: 316 case Intrinsic::isunordered_f32: 317 case Intrinsic::isunordered_f64: 318 case Intrinsic::bswap_i16: 319 case Intrinsic::bswap_i32: 320 case Intrinsic::bswap_i64: 321 case Intrinsic::ctpop_i8: 322 case Intrinsic::ctpop_i16: 323 case Intrinsic::ctpop_i32: 324 case Intrinsic::ctpop_i64: 325 case Intrinsic::ctlz_i8: 326 case Intrinsic::ctlz_i16: 327 case Intrinsic::ctlz_i32: 328 case Intrinsic::ctlz_i64: 329 case Intrinsic::cttz_i8: 330 case Intrinsic::cttz_i16: 331 case Intrinsic::cttz_i32: 332 case Intrinsic::cttz_i64: 333 case Intrinsic::sqrt_f32: 334 case Intrinsic::sqrt_f64: 335 return true; // These intrinsics have no side effects. 336 } 337 return false; 338} 339 340// dceInstruction - Inspect the instruction at *BBI and figure out if it's 341// [trivially] dead. If so, remove the instruction and update the iterator 342// to point to the instruction that immediately succeeded the original 343// instruction. 344// 345bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 346 // Look for un"used" definitions... 347 if (isInstructionTriviallyDead(BBI)) { 348 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 349 return true; 350 } 351 return false; 352} 353