Local.cpp revision a04c0c417b335d15b6a6efa8092f8f3bb3a7ce16
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 return 0; 111 case Instruction::ShuffleVector: 112 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(2))) 113 return ConstantExpr::getShuffleVector(Op0, Op1, Op2); 114 return 0; 115 case Instruction::GetElementPtr: 116 std::vector<Constant*> IdxList; 117 IdxList.reserve(I->getNumOperands()-1); 118 if (Op1) IdxList.push_back(Op1); 119 for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i) 120 if (Constant *C = dyn_cast<Constant>(I->getOperand(i))) 121 IdxList.push_back(C); 122 else 123 return 0; // Non-constant operand 124 return ConstantExpr::getGetElementPtr(Op0, IdxList); 125 } 126} 127 128// ConstantFoldTerminator - If a terminator instruction is predicated on a 129// constant value, convert it into an unconditional branch to the constant 130// destination. 131// 132bool llvm::ConstantFoldTerminator(BasicBlock *BB) { 133 TerminatorInst *T = BB->getTerminator(); 134 135 // Branch - See if we are conditional jumping on constant 136 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 137 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 138 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 139 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 140 141 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) { 142 // Are we branching on constant? 143 // YES. Change to unconditional branch... 144 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; 145 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; 146 147 //cerr << "Function: " << T->getParent()->getParent() 148 // << "\nRemoving branch from " << T->getParent() 149 // << "\n\nTo: " << OldDest << endl; 150 151 // Let the basic block know that we are letting go of it. Based on this, 152 // it will adjust it's PHI nodes. 153 assert(BI->getParent() && "Terminator not inserted in block!"); 154 OldDest->removePredecessor(BI->getParent()); 155 156 // Set the unconditional destination, and change the insn to be an 157 // unconditional branch. 158 BI->setUnconditionalDest(Destination); 159 return true; 160 } else if (Dest2 == Dest1) { // Conditional branch to same location? 161 // This branch matches something like this: 162 // br bool %cond, label %Dest, label %Dest 163 // and changes it into: br label %Dest 164 165 // Let the basic block know that we are letting go of one copy of it. 166 assert(BI->getParent() && "Terminator not inserted in block!"); 167 Dest1->removePredecessor(BI->getParent()); 168 169 // Change a conditional branch to unconditional. 170 BI->setUnconditionalDest(Dest1); 171 return true; 172 } 173 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 174 // If we are switching on a constant, we can convert the switch into a 175 // single branch instruction! 176 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 177 BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest 178 BasicBlock *DefaultDest = TheOnlyDest; 179 assert(TheOnlyDest == SI->getDefaultDest() && 180 "Default destination is not successor #0?"); 181 182 // Figure out which case it goes to... 183 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 184 // Found case matching a constant operand? 185 if (SI->getSuccessorValue(i) == CI) { 186 TheOnlyDest = SI->getSuccessor(i); 187 break; 188 } 189 190 // Check to see if this branch is going to the same place as the default 191 // dest. If so, eliminate it as an explicit compare. 192 if (SI->getSuccessor(i) == DefaultDest) { 193 // Remove this entry... 194 DefaultDest->removePredecessor(SI->getParent()); 195 SI->removeCase(i); 196 --i; --e; // Don't skip an entry... 197 continue; 198 } 199 200 // Otherwise, check to see if the switch only branches to one destination. 201 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 202 // destinations. 203 if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; 204 } 205 206 if (CI && !TheOnlyDest) { 207 // Branching on a constant, but not any of the cases, go to the default 208 // successor. 209 TheOnlyDest = SI->getDefaultDest(); 210 } 211 212 // If we found a single destination that we can fold the switch into, do so 213 // now. 214 if (TheOnlyDest) { 215 // Insert the new branch.. 216 new BranchInst(TheOnlyDest, SI); 217 BasicBlock *BB = SI->getParent(); 218 219 // Remove entries from PHI nodes which we no longer branch to... 220 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 221 // Found case matching a constant operand? 222 BasicBlock *Succ = SI->getSuccessor(i); 223 if (Succ == TheOnlyDest) 224 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 225 else 226 Succ->removePredecessor(BB); 227 } 228 229 // Delete the old switch... 230 BB->getInstList().erase(SI); 231 return true; 232 } else if (SI->getNumSuccessors() == 2) { 233 // Otherwise, we can fold this switch into a conditional branch 234 // instruction if it has only one non-default destination. 235 Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), 236 SI->getSuccessorValue(1), "cond", SI); 237 // Insert the new branch... 238 new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); 239 240 // Delete the old switch... 241 SI->getParent()->getInstList().erase(SI); 242 return true; 243 } 244 } 245 return false; 246} 247 248/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 249/// getelementptr constantexpr, return the constant value being addressed by the 250/// constant expression, or null if something is funny and we can't decide. 251Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 252 ConstantExpr *CE) { 253 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 254 return 0; // Do not allow stepping over the value! 255 256 // Loop over all of the operands, tracking down which value we are 257 // addressing... 258 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 259 for (++I; I != E; ++I) 260 if (const StructType *STy = dyn_cast<StructType>(*I)) { 261 ConstantUInt *CU = cast<ConstantUInt>(I.getOperand()); 262 assert(CU->getValue() < STy->getNumElements() && 263 "Struct index out of range!"); 264 unsigned El = (unsigned)CU->getValue(); 265 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 266 C = CS->getOperand(El); 267 } else if (isa<ConstantAggregateZero>(C)) { 268 C = Constant::getNullValue(STy->getElementType(El)); 269 } else if (isa<UndefValue>(C)) { 270 C = UndefValue::get(STy->getElementType(El)); 271 } else { 272 return 0; 273 } 274 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 275 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 276 if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) 277 C = UndefValue::get(ATy->getElementType()); 278 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 279 C = CA->getOperand((unsigned)CI->getRawValue()); 280 else if (isa<ConstantAggregateZero>(C)) 281 C = Constant::getNullValue(ATy->getElementType()); 282 else if (isa<UndefValue>(C)) 283 C = UndefValue::get(ATy->getElementType()); 284 else 285 return 0; 286 } else if (const PackedType *PTy = dyn_cast<PackedType>(*I)) { 287 if ((uint64_t)CI->getRawValue() >= PTy->getNumElements()) 288 C = UndefValue::get(PTy->getElementType()); 289 if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) 290 C = CP->getOperand((unsigned)CI->getRawValue()); 291 else if (isa<ConstantAggregateZero>(C)) 292 C = Constant::getNullValue(PTy->getElementType()); 293 else if (isa<UndefValue>(C)) 294 C = UndefValue::get(PTy->getElementType()); 295 else 296 return 0; 297 } else { 298 return 0; 299 } 300 } else { 301 return 0; 302 } 303 return C; 304} 305 306 307//===----------------------------------------------------------------------===// 308// Local dead code elimination... 309// 310 311bool llvm::isInstructionTriviallyDead(Instruction *I) { 312 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 313 314 if (!I->mayWriteToMemory()) return true; 315 316 if (CallInst *CI = dyn_cast<CallInst>(I)) 317 if (Function *F = CI->getCalledFunction()) { 318 unsigned IntrinsicID = F->getIntrinsicID(); 319#define GET_SIDE_EFFECT_INFO 320#include "llvm/Intrinsics.gen" 321#undef GET_SIDE_EFFECT_INFO 322 } 323 return false; 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