Local.cpp revision 9fa038dc21e966dceb23f9410351e863e3ce1114
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/Target/TargetData.h" 22#include "llvm/Support/GetElementPtrTypeIterator.h" 23#include "llvm/Support/MathExtras.h" 24#include "llvm/ADT/SmallVector.h" 25#include <cerrno> 26using namespace llvm; 27 28//===----------------------------------------------------------------------===// 29// Local constant propagation... 30// 31 32/// doConstantPropagation - If an instruction references constants, try to fold 33/// them together... 34/// 35bool llvm::doConstantPropagation(BasicBlock::iterator &II, 36 const TargetData *TD) { 37 if (Constant *C = ConstantFoldInstruction(II, TD)) { 38 // Replaces all of the uses of a variable with uses of the constant. 39 II->replaceAllUsesWith(C); 40 41 // Remove the instruction from the basic block... 42 II = II->getParent()->getInstList().erase(II); 43 return true; 44 } 45 46 return false; 47} 48 49/// ConstantFoldInstruction - Attempt to constant fold the specified 50/// instruction. If successful, the constant result is returned, if not, null 51/// is returned. Note that this function can only fail when attempting to fold 52/// instructions like loads and stores, which have no constant expression form. 53/// 54Constant *llvm::ConstantFoldInstruction(Instruction *I, const TargetData *TD) { 55 if (PHINode *PN = dyn_cast<PHINode>(I)) { 56 if (PN->getNumIncomingValues() == 0) 57 return Constant::getNullValue(PN->getType()); 58 59 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); 60 if (Result == 0) return 0; 61 62 // Handle PHI nodes specially here... 63 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 64 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) 65 return 0; // Not all the same incoming constants... 66 67 // If we reach here, all incoming values are the same constant. 68 return Result; 69 } 70 71 Constant *Op0 = 0, *Op1 = 0; 72 switch (I->getNumOperands()) { 73 default: 74 case 2: 75 Op1 = dyn_cast<Constant>(I->getOperand(1)); 76 if (Op1 == 0) return 0; // Not a constant?, can't fold 77 /* FALL THROUGH */ 78 case 1: 79 Op0 = dyn_cast<Constant>(I->getOperand(0)); 80 if (Op0 == 0) return 0; // Not a constant?, can't fold 81 break; 82 case 0: return 0; 83 } 84 85 // Scan the operand list, checking to see if they are all constants, if so, 86 // hand off to ConstantFoldInstOperands. 87 SmallVector<Constant*, 8> Ops; 88 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 89 if (Constant *Op = dyn_cast<Constant>(I->getOperand(i))) 90 Ops.push_back(Op); 91 else 92 return 0; // All operands not constant! 93 94 return ConstantFoldInstOperands(I, &Ops[0], Ops.size()); 95} 96 97/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the 98/// specified opcode and operands. If successful, the constant result is 99/// returned, if not, null is returned. Note that this function can fail when 100/// attempting to fold instructions like loads and stores, which have no 101/// constant expression form. 102/// 103Constant *llvm::ConstantFoldInstOperands(const Instruction* I, 104 Constant** Ops, unsigned NumOps, 105 const TargetData *TD) { 106 unsigned Opc = I->getOpcode(); 107 const Type *DestTy = I->getType(); 108 109 // Handle easy binops first 110 if (isa<BinaryOperator>(I)) 111 return ConstantExpr::get(Opc, Ops[0], Ops[1]); 112 113 switch (Opc) { 114 default: return 0; 115 case Instruction::Call: 116 if (Function *F = dyn_cast<Function>(Ops[0])) 117 if (canConstantFoldCallTo(F)) 118 return ConstantFoldCall(F, Ops+1, NumOps); 119 return 0; 120 case Instruction::ICmp: 121 case Instruction::FCmp: 122 return ConstantExpr::getCompare(cast<CmpInst>(I)->getPredicate(), Ops[0], 123 Ops[1]); 124 case Instruction::Shl: 125 case Instruction::LShr: 126 case Instruction::AShr: 127 return ConstantExpr::get(Opc, Ops[0], Ops[1]); 128 case Instruction::Trunc: 129 case Instruction::ZExt: 130 case Instruction::SExt: 131 case Instruction::FPTrunc: 132 case Instruction::FPExt: 133 case Instruction::UIToFP: 134 case Instruction::SIToFP: 135 case Instruction::FPToUI: 136 case Instruction::FPToSI: 137 case Instruction::PtrToInt: 138 case Instruction::IntToPtr: 139 case Instruction::BitCast: 140 return ConstantExpr::getCast(Opc, Ops[0], DestTy); 141 case Instruction::Select: 142 return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]); 143 case Instruction::ExtractElement: 144 return ConstantExpr::getExtractElement(Ops[0], Ops[1]); 145 case Instruction::InsertElement: 146 return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]); 147 case Instruction::ShuffleVector: 148 return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]); 149 case Instruction::GetElementPtr: 150 return ConstantExpr::getGetElementPtr(Ops[0], 151 std::vector<Constant*>(Ops+1, 152 Ops+NumOps)); 153 } 154} 155 156// ConstantFoldTerminator - If a terminator instruction is predicated on a 157// constant value, convert it into an unconditional branch to the constant 158// destination. 159// 160bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 161 TerminatorInst *T = BB->getTerminator(); 162 163 // Branch - See if we are conditional jumping on constant 164 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 165 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 166 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 167 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 168 169 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 170 // Are we branching on constant? 171 // YES. Change to unconditional branch... 172 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 173 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 174 175 //cerr << "Function: " << T->getParent()->getParent() 176 // << "\nRemoving branch from " << T->getParent() 177 // << "\n\nTo: " << OldDest << endl; 178 179 // Let the basic block know that we are letting go of it. Based on this, 180 // it will adjust it's PHI nodes. 181 assert(BI->getParent() && "Terminator not inserted in block!"); 182 OldDest->removePredecessor(BI->getParent()); 183 184 // Set the unconditional destination, and change the insn to be an 185 // unconditional branch. 186 BI->setUnconditionalDest(Destination); 187 return true; 188 } else if (Dest2 == Dest1) { // Conditional branch to same location? 189 // This branch matches something like this: 190 // br bool %cond, label %Dest, label %Dest 191 // and changes it into: br label %Dest 192 193 // Let the basic block know that we are letting go of one copy of it. 194 assert(BI->getParent() && "Terminator not inserted in block!"); 195 Dest1->removePredecessor(BI->getParent()); 196 197 // Change a conditional branch to unconditional. 198 BI->setUnconditionalDest(Dest1); 199 return true; 200 } 201 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 202 // If we are switching on a constant, we can convert the switch into a 203 // single branch instruction! 204 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 205 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 206 BasicBlock *DefaultDest = TheOnlyDest; 207 assert(TheOnlyDest == SI->getDefaultDest() && 208 "Default destination is not successor #0?"); 209 210 // Figure out which case it goes to... 211 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 212 // Found case matching a constant operand? 213 if (SI->getSuccessorValue(i) == CI) { 214 TheOnlyDest = SI->getSuccessor(i); 215 break; 216 } 217 218 // Check to see if this branch is going to the same place as the default 219 // dest. If so, eliminate it as an explicit compare. 220 if (SI->getSuccessor(i) == DefaultDest) { 221 // Remove this entry... 222 DefaultDest->removePredecessor(SI->getParent()); 223 SI->removeCase(i); 224 --i; --e; // Don't skip an entry... 225 continue; 226 } 227 228 // Otherwise, check to see if the switch only branches to one destination. 229 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 230 // destinations. 231 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 232 } 233 234 if (CI && !TheOnlyDest) { 235 // Branching on a constant, but not any of the cases, go to the default 236 // successor. 237 TheOnlyDest = SI->getDefaultDest(); 238 } 239 240 // If we found a single destination that we can fold the switch into, do so 241 // now. 242 if (TheOnlyDest) { 243 // Insert the new branch.. 244 new BranchInst(TheOnlyDest, SI); 245 BasicBlock *BB = SI->getParent(); 246 247 // Remove entries from PHI nodes which we no longer branch to... 248 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 249 // Found case matching a constant operand? 250 BasicBlock *Succ = SI->getSuccessor(i); 251 if (Succ == TheOnlyDest) 252 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 253 else 254 Succ->removePredecessor(BB); 255 } 256 257 // Delete the old switch... 258 BB->getInstList().erase(SI); 259 return true; 260 } else if (SI->getNumSuccessors() == 2) { 261 // Otherwise, we can fold this switch into a conditional branch 262 // instruction if it has only one non-default destination. 263 Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, SI->getCondition(), 264 SI->getSuccessorValue(1), "cond", SI); 265 // Insert the new branch... 266 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 267 268 // Delete the old switch... 269 SI->getParent()->getInstList().erase(SI); 270 return true; 271 } 272 } 273 return false; 274} 275 276/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 277/// getelementptr constantexpr, return the constant value being addressed by the 278/// constant expression, or null if something is funny and we can't decide. 279Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 280 ConstantExpr *CE) { 281 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 282 return 0; // Do not allow stepping over the value! 283 284 // Loop over all of the operands, tracking down which value we are 285 // addressing... 286 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 287 for (++I; I != E; ++I) 288 if (const StructType *STy = dyn_cast<StructType>(*I)) { 289 ConstantInt *CU = cast<ConstantInt>(I.getOperand()); 290 assert(CU->getZExtValue() < STy->getNumElements() && 291 "Struct index out of range!"); 292 unsigned El = (unsigned)CU->getZExtValue(); 293 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 294 C = CS->getOperand(El); 295 } else if (isa<ConstantAggregateZero>(C)) { 296 C = Constant::getNullValue(STy->getElementType(El)); 297 } else if (isa<UndefValue>(C)) { 298 C = UndefValue::get(STy->getElementType(El)); 299 } else { 300 return 0; 301 } 302 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 303 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 304 if (CI->getZExtValue() >= ATy->getNumElements()) 305 return 0; 306 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 307 C = CA->getOperand(CI->getZExtValue()); 308 else if (isa<ConstantAggregateZero>(C)) 309 C = Constant::getNullValue(ATy->getElementType()); 310 else if (isa<UndefValue>(C)) 311 C = UndefValue::get(ATy->getElementType()); 312 else 313 return 0; 314 } else if (const PackedType *PTy = dyn_cast<PackedType>(*I)) { 315 if (CI->getZExtValue() >= PTy->getNumElements()) 316 return 0; 317 if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) 318 C = CP->getOperand(CI->getZExtValue()); 319 else if (isa<ConstantAggregateZero>(C)) 320 C = Constant::getNullValue(PTy->getElementType()); 321 else if (isa<UndefValue>(C)) 322 C = UndefValue::get(PTy->getElementType()); 323 else 324 return 0; 325 } else { 326 return 0; 327 } 328 } else { 329 return 0; 330 } 331 return C; 332} 333 334 335//===----------------------------------------------------------------------===// 336// Local dead code elimination... 337// 338 339bool llvm::isInstructionTriviallyDead(Instruction *I) { 340 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 341 342 if (!I->mayWriteToMemory()) return true; 343 344 if (CallInst *CI = dyn_cast<CallInst>(I)) 345 if (Function *F = CI->getCalledFunction()) { 346 unsigned IntrinsicID = F->getIntrinsicID(); 347#define GET_SIDE_EFFECT_INFO 348#include "llvm/Intrinsics.gen" 349#undef GET_SIDE_EFFECT_INFO 350 } 351 return false; 352} 353 354// dceInstruction - Inspect the instruction at *BBI and figure out if it's 355// [trivially] dead. If so, remove the instruction and update the iterator 356// to point to the instruction that immediately succeeded the original 357// instruction. 358// 359bool llvm::dceInstruction(BasicBlock::iterator &BBI) { 360 // Look for un"used" definitions... 361 if (isInstructionTriviallyDead(BBI)) { 362 BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye 363 return true; 364 } 365 return false; 366} 367