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