SCCP.cpp revision 2f09625a9fde578e5ca2cc8cc696efaa857c5f59
1//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements sparse conditional constant propagation and merging: 11// 12// Specifically, this: 13// * Assumes values are constant unless proven otherwise 14// * Assumes BasicBlocks are dead unless proven otherwise 15// * Proves values to be constant, and replaces them with constants 16// * Proves conditional branches to be unconditional 17// 18//===----------------------------------------------------------------------===// 19 20#define DEBUG_TYPE "sccp" 21#include "llvm/Transforms/Scalar.h" 22#include "llvm/Transforms/IPO.h" 23#include "llvm/Constants.h" 24#include "llvm/DerivedTypes.h" 25#include "llvm/Instructions.h" 26#include "llvm/Pass.h" 27#include "llvm/Analysis/ConstantFolding.h" 28#include "llvm/Analysis/MemoryBuiltins.h" 29#include "llvm/Analysis/ValueTracking.h" 30#include "llvm/Transforms/Utils/Local.h" 31#include "llvm/Support/CallSite.h" 32#include "llvm/Support/Debug.h" 33#include "llvm/Support/ErrorHandling.h" 34#include "llvm/Support/InstVisitor.h" 35#include "llvm/Support/raw_ostream.h" 36#include "llvm/ADT/DenseMap.h" 37#include "llvm/ADT/DenseSet.h" 38#include "llvm/ADT/PointerIntPair.h" 39#include "llvm/ADT/SmallVector.h" 40#include "llvm/ADT/Statistic.h" 41#include "llvm/ADT/STLExtras.h" 42#include <algorithm> 43#include <map> 44using namespace llvm; 45 46STATISTIC(NumInstRemoved, "Number of instructions removed"); 47STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 48 49STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); 50STATISTIC(IPNumDeadBlocks , "Number of basic blocks unreachable by IPSCCP"); 51STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); 52STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); 53 54namespace { 55/// LatticeVal class - This class represents the different lattice values that 56/// an LLVM value may occupy. It is a simple class with value semantics. 57/// 58class LatticeVal { 59 enum LatticeValueTy { 60 /// undefined - This LLVM Value has no known value yet. 61 undefined, 62 63 /// constant - This LLVM Value has a specific constant value. 64 constant, 65 66 /// forcedconstant - This LLVM Value was thought to be undef until 67 /// ResolvedUndefsIn. This is treated just like 'constant', but if merged 68 /// with another (different) constant, it goes to overdefined, instead of 69 /// asserting. 70 forcedconstant, 71 72 /// overdefined - This instruction is not known to be constant, and we know 73 /// it has a value. 74 overdefined 75 }; 76 77 /// Val: This stores the current lattice value along with the Constant* for 78 /// the constant if this is a 'constant' or 'forcedconstant' value. 79 PointerIntPair<Constant *, 2, LatticeValueTy> Val; 80 81 LatticeValueTy getLatticeValue() const { 82 return Val.getInt(); 83 } 84 85public: 86 inline LatticeVal() : Val(0, undefined) {} 87 88 inline bool isUndefined() const { return getLatticeValue() == undefined; } 89 inline bool isConstant() const { 90 return getLatticeValue() == constant || getLatticeValue() == forcedconstant; 91 } 92 inline bool isOverdefined() const { return getLatticeValue() == overdefined; } 93 94 inline Constant *getConstant() const { 95 assert(isConstant() && "Cannot get the constant of a non-constant!"); 96 return Val.getPointer(); 97 } 98 99 /// markOverdefined - Return true if this is a change in status. 100 inline bool markOverdefined() { 101 if (isOverdefined()) 102 return false; 103 104 Val.setInt(overdefined); 105 return true; 106 } 107 108 /// markConstant - Return true if this is a change in status. 109 inline bool markConstant(Constant *V) { 110 if (isConstant()) { 111 assert(getConstant() == V && "Marking constant with different value"); 112 return false; 113 } 114 115 if (isUndefined()) { 116 Val.setInt(constant); 117 assert(V && "Marking constant with NULL"); 118 Val.setPointer(V); 119 } else { 120 assert(getLatticeValue() == forcedconstant && 121 "Cannot move from overdefined to constant!"); 122 // Stay at forcedconstant if the constant is the same. 123 if (V == getConstant()) return false; 124 125 // Otherwise, we go to overdefined. Assumptions made based on the 126 // forced value are possibly wrong. Assuming this is another constant 127 // could expose a contradiction. 128 Val.setInt(overdefined); 129 } 130 return true; 131 } 132 133 inline void markForcedConstant(Constant *V) { 134 assert(isUndefined() && "Can't force a defined value!"); 135 Val.setInt(forcedconstant); 136 Val.setPointer(V); 137 } 138}; 139 140//===----------------------------------------------------------------------===// 141// 142/// SCCPSolver - This class is a general purpose solver for Sparse Conditional 143/// Constant Propagation. 144/// 145class SCCPSolver : public InstVisitor<SCCPSolver> { 146 DenseSet<BasicBlock*> BBExecutable;// The basic blocks that are executable 147 std::map<Value*, LatticeVal> ValueState; // The state each value is in. 148 149 /// GlobalValue - If we are tracking any values for the contents of a global 150 /// variable, we keep a mapping from the constant accessor to the element of 151 /// the global, to the currently known value. If the value becomes 152 /// overdefined, it's entry is simply removed from this map. 153 DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals; 154 155 /// TrackedRetVals - If we are tracking arguments into and the return 156 /// value out of a function, it will have an entry in this map, indicating 157 /// what the known return value for the function is. 158 DenseMap<Function*, LatticeVal> TrackedRetVals; 159 160 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions 161 /// that return multiple values. 162 DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals; 163 164 // The reason for two worklists is that overdefined is the lowest state 165 // on the lattice, and moving things to overdefined as fast as possible 166 // makes SCCP converge much faster. 167 // By having a separate worklist, we accomplish this because everything 168 // possibly overdefined will become overdefined at the soonest possible 169 // point. 170 SmallVector<Value*, 64> OverdefinedInstWorkList; 171 SmallVector<Value*, 64> InstWorkList; 172 173 174 SmallVector<BasicBlock*, 64> BBWorkList; // The BasicBlock work list 175 176 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not 177 /// overdefined, despite the fact that the PHI node is overdefined. 178 std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs; 179 180 /// KnownFeasibleEdges - Entries in this set are edges which have already had 181 /// PHI nodes retriggered. 182 typedef std::pair<BasicBlock*, BasicBlock*> Edge; 183 DenseSet<Edge> KnownFeasibleEdges; 184public: 185 186 /// MarkBlockExecutable - This method can be used by clients to mark all of 187 /// the blocks that are known to be intrinsically live in the processed unit. 188 void MarkBlockExecutable(BasicBlock *BB) { 189 DEBUG(errs() << "Marking Block Executable: " << BB->getName() << "\n"); 190 BBExecutable.insert(BB); // Basic block is executable! 191 BBWorkList.push_back(BB); // Add the block to the work list! 192 } 193 194 /// TrackValueOfGlobalVariable - Clients can use this method to 195 /// inform the SCCPSolver that it should track loads and stores to the 196 /// specified global variable if it can. This is only legal to call if 197 /// performing Interprocedural SCCP. 198 void TrackValueOfGlobalVariable(GlobalVariable *GV) { 199 const Type *ElTy = GV->getType()->getElementType(); 200 if (ElTy->isFirstClassType()) { 201 LatticeVal &IV = TrackedGlobals[GV]; 202 if (!isa<UndefValue>(GV->getInitializer())) 203 IV.markConstant(GV->getInitializer()); 204 } 205 } 206 207 /// AddTrackedFunction - If the SCCP solver is supposed to track calls into 208 /// and out of the specified function (which cannot have its address taken), 209 /// this method must be called. 210 void AddTrackedFunction(Function *F) { 211 assert(F->hasLocalLinkage() && "Can only track internal functions!"); 212 // Add an entry, F -> undef. 213 if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) { 214 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 215 TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), 216 LatticeVal())); 217 } else 218 TrackedRetVals.insert(std::make_pair(F, LatticeVal())); 219 } 220 221 /// Solve - Solve for constants and executable blocks. 222 /// 223 void Solve(); 224 225 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume 226 /// that branches on undef values cannot reach any of their successors. 227 /// However, this is not a safe assumption. After we solve dataflow, this 228 /// method should be use to handle this. If this returns true, the solver 229 /// should be rerun. 230 bool ResolvedUndefsIn(Function &F); 231 232 bool isBlockExecutable(BasicBlock *BB) const { 233 return BBExecutable.count(BB); 234 } 235 236 /// getValueMapping - Once we have solved for constants, return the mapping of 237 /// LLVM values to LatticeVals. 238 std::map<Value*, LatticeVal> &getValueMapping() { 239 return ValueState; 240 } 241 242 /// getTrackedRetVals - Get the inferred return value map. 243 /// 244 const DenseMap<Function*, LatticeVal> &getTrackedRetVals() { 245 return TrackedRetVals; 246 } 247 248 /// getTrackedGlobals - Get and return the set of inferred initializers for 249 /// global variables. 250 const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() { 251 return TrackedGlobals; 252 } 253 254 inline void markOverdefined(Value *V) { 255 markOverdefined(ValueState[V], V); 256 } 257 258private: 259 // markConstant - Make a value be marked as "constant". If the value 260 // is not already a constant, add it to the instruction work list so that 261 // the users of the instruction are updated later. 262 // 263 inline void markConstant(LatticeVal &IV, Value *V, Constant *C) { 264 if (IV.markConstant(C)) { 265 DEBUG(errs() << "markConstant: " << *C << ": " << *V << '\n'); 266 InstWorkList.push_back(V); 267 } 268 } 269 270 inline void markForcedConstant(LatticeVal &IV, Value *V, Constant *C) { 271 IV.markForcedConstant(C); 272 DEBUG(errs() << "markForcedConstant: " << *C << ": " << *V << '\n'); 273 InstWorkList.push_back(V); 274 } 275 276 inline void markConstant(Value *V, Constant *C) { 277 markConstant(ValueState[V], V, C); 278 } 279 280 // markOverdefined - Make a value be marked as "overdefined". If the 281 // value is not already overdefined, add it to the overdefined instruction 282 // work list so that the users of the instruction are updated later. 283 inline void markOverdefined(LatticeVal &IV, Value *V) { 284 if (IV.markOverdefined()) { 285 DEBUG(errs() << "markOverdefined: "; 286 if (Function *F = dyn_cast<Function>(V)) 287 errs() << "Function '" << F->getName() << "'\n"; 288 else 289 errs() << *V << '\n'); 290 // Only instructions go on the work list 291 OverdefinedInstWorkList.push_back(V); 292 } 293 } 294 295 inline void mergeInValue(LatticeVal &IV, Value *V, LatticeVal &MergeWithV) { 296 if (IV.isOverdefined() || MergeWithV.isUndefined()) 297 return; // Noop. 298 if (MergeWithV.isOverdefined()) 299 markOverdefined(IV, V); 300 else if (IV.isUndefined()) 301 markConstant(IV, V, MergeWithV.getConstant()); 302 else if (IV.getConstant() != MergeWithV.getConstant()) 303 markOverdefined(IV, V); 304 } 305 306 inline void mergeInValue(Value *V, LatticeVal &MergeWithV) { 307 return mergeInValue(ValueState[V], V, MergeWithV); 308 } 309 310 311 // getValueState - Return the LatticeVal object that corresponds to the value. 312 // This function is necessary because not all values should start out in the 313 // underdefined state. Argument's should be overdefined, and 314 // constants should be marked as constants. If a value is not known to be an 315 // Instruction object, then use this accessor to get its value from the map. 316 // 317 inline LatticeVal &getValueState(Value *V) { 318 std::map<Value*, LatticeVal>::iterator I = ValueState.find(V); 319 if (I != ValueState.end()) return I->second; // Common case, in the map 320 321 if (Constant *C = dyn_cast<Constant>(V)) { 322 if (isa<UndefValue>(V)) { 323 // Nothing to do, remain undefined. 324 } else { 325 LatticeVal &LV = ValueState[C]; 326 LV.markConstant(C); // Constants are constant 327 return LV; 328 } 329 } 330 // All others are underdefined by default. 331 return ValueState[V]; 332 } 333 334 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB 335 // work list if it is not already executable. 336 // 337 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 338 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 339 return; // This edge is already known to be executable! 340 341 if (BBExecutable.count(Dest)) { 342 DEBUG(errs() << "Marking Edge Executable: " << Source->getName() 343 << " -> " << Dest->getName() << "\n"); 344 345 // The destination is already executable, but we just made an edge 346 // feasible that wasn't before. Revisit the PHI nodes in the block 347 // because they have potentially new operands. 348 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 349 visitPHINode(*cast<PHINode>(I)); 350 351 } else { 352 MarkBlockExecutable(Dest); 353 } 354 } 355 356 // getFeasibleSuccessors - Return a vector of booleans to indicate which 357 // successors are reachable from a given terminator instruction. 358 // 359 void getFeasibleSuccessors(TerminatorInst &TI, SmallVector<bool, 16> &Succs); 360 361 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 362 // block to the 'To' basic block is currently feasible. 363 // 364 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); 365 366 // OperandChangedState - This method is invoked on all of the users of an 367 // instruction that was just changed state somehow. Based on this 368 // information, we need to update the specified user of this instruction. 369 // 370 void OperandChangedState(User *U) { 371 // Only instructions use other variable values! 372 Instruction &I = cast<Instruction>(*U); 373 if (BBExecutable.count(I.getParent())) // Inst is executable? 374 visit(I); 375 } 376 377private: 378 friend class InstVisitor<SCCPSolver>; 379 380 // visit implementations - Something changed in this instruction. Either an 381 // operand made a transition, or the instruction is newly executable. Change 382 // the value type of I to reflect these changes if appropriate. 383 // 384 void visitPHINode(PHINode &I); 385 386 // Terminators 387 void visitReturnInst(ReturnInst &I); 388 void visitTerminatorInst(TerminatorInst &TI); 389 390 void visitCastInst(CastInst &I); 391 void visitSelectInst(SelectInst &I); 392 void visitBinaryOperator(Instruction &I); 393 void visitCmpInst(CmpInst &I); 394 void visitExtractElementInst(ExtractElementInst &I); 395 void visitInsertElementInst(InsertElementInst &I); 396 void visitShuffleVectorInst(ShuffleVectorInst &I); 397 void visitExtractValueInst(ExtractValueInst &EVI); 398 void visitInsertValueInst(InsertValueInst &IVI); 399 400 // Instructions that cannot be folded away. 401 void visitStoreInst (Instruction &I); 402 void visitLoadInst (LoadInst &I); 403 void visitGetElementPtrInst(GetElementPtrInst &I); 404 void visitCallInst (CallInst &I) { 405 if (isFreeCall(&I)) 406 return; 407 visitCallSite(CallSite::get(&I)); 408 } 409 void visitInvokeInst (InvokeInst &II) { 410 visitCallSite(CallSite::get(&II)); 411 visitTerminatorInst(II); 412 } 413 void visitCallSite (CallSite CS); 414 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ } 415 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ } 416 void visitAllocaInst (Instruction &I) { markOverdefined(&I); } 417 void visitVANextInst (Instruction &I) { markOverdefined(&I); } 418 void visitVAArgInst (Instruction &I) { markOverdefined(&I); } 419 420 void visitInstruction(Instruction &I) { 421 // If a new instruction is added to LLVM that we don't handle. 422 errs() << "SCCP: Don't know how to handle: " << I; 423 markOverdefined(&I); // Just in case 424 } 425}; 426 427} // end anonymous namespace 428 429 430// getFeasibleSuccessors - Return a vector of booleans to indicate which 431// successors are reachable from a given terminator instruction. 432// 433void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI, 434 SmallVector<bool, 16> &Succs) { 435 Succs.resize(TI.getNumSuccessors()); 436 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 437 if (BI->isUnconditional()) { 438 Succs[0] = true; 439 return; 440 } 441 442 LatticeVal &BCValue = getValueState(BI->getCondition()); 443 if (BCValue.isOverdefined() || 444 (BCValue.isConstant() && !isa<ConstantInt>(BCValue.getConstant()))) { 445 // Overdefined condition variables, and branches on unfoldable constant 446 // conditions, mean the branch could go either way. 447 Succs[0] = Succs[1] = true; 448 return; 449 } 450 451 // Constant condition variables mean the branch can only go a single way. 452 Succs[cast<ConstantInt>(BCValue.getConstant())->isZero()] = true; 453 return; 454 } 455 456 if (isa<InvokeInst>(&TI)) { 457 // Invoke instructions successors are always executable. 458 Succs[0] = Succs[1] = true; 459 return; 460 } 461 462 if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) { 463 LatticeVal &SCValue = getValueState(SI->getCondition()); 464 if (SCValue.isOverdefined() || // Overdefined condition? 465 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) { 466 // All destinations are executable! 467 Succs.assign(TI.getNumSuccessors(), true); 468 } else if (SCValue.isConstant()) 469 Succs[SI->findCaseValue(cast<ConstantInt>(SCValue.getConstant()))] = true; 470 return; 471 } 472 473 // TODO: This could be improved if the operand is a [cast of a] BlockAddress. 474 if (isa<IndirectBrInst>(&TI)) { 475 // Just mark all destinations executable! 476 Succs.assign(TI.getNumSuccessors(), true); 477 return; 478 } 479 480#ifndef NDEBUG 481 errs() << "Unknown terminator instruction: " << TI << '\n'; 482#endif 483 llvm_unreachable("SCCP: Don't know how to handle this terminator!"); 484} 485 486 487// isEdgeFeasible - Return true if the control flow edge from the 'From' basic 488// block to the 'To' basic block is currently feasible. 489// 490bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 491 assert(BBExecutable.count(To) && "Dest should always be alive!"); 492 493 // Make sure the source basic block is executable!! 494 if (!BBExecutable.count(From)) return false; 495 496 // Check to make sure this edge itself is actually feasible now. 497 TerminatorInst *TI = From->getTerminator(); 498 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 499 if (BI->isUnconditional()) 500 return true; 501 502 LatticeVal &BCValue = getValueState(BI->getCondition()); 503 504 // Overdefined condition variables mean the branch could go either way, 505 // undef conditions mean that neither edge is feasible yet. 506 if (!BCValue.isConstant()) 507 return BCValue.isOverdefined(); 508 509 // Not branching on an evaluatable constant? 510 if (!isa<ConstantInt>(BCValue.getConstant())) return true; 511 512 // Constant condition variables mean the branch can only go a single way. 513 bool CondIsFalse = cast<ConstantInt>(BCValue.getConstant())->isZero(); 514 return BI->getSuccessor(CondIsFalse) == To; 515 } 516 517 // Invoke instructions successors are always executable. 518 if (isa<InvokeInst>(TI)) 519 return true; 520 521 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 522 LatticeVal &SCValue = getValueState(SI->getCondition()); 523 if (SCValue.isOverdefined()) { // Overdefined condition? 524 // All destinations are executable! 525 return true; 526 } else if (SCValue.isConstant()) { 527 Constant *CPV = SCValue.getConstant(); 528 if (!isa<ConstantInt>(CPV)) 529 return true; // not a foldable constant? 530 531 // Make sure to skip the "default value" which isn't a value 532 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) 533 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch. 534 return SI->getSuccessor(i) == To; 535 536 // If the constant value is not equal to any of the branches, we must 537 // execute default branch. 538 return SI->getDefaultDest() == To; 539 } 540 return false; 541 } 542 543 // Just mark all destinations executable! 544 // TODO: This could be improved if the operand is a [cast of a] BlockAddress. 545 if (isa<IndirectBrInst>(&TI)) 546 return true; 547 548#ifndef NDEBUG 549 errs() << "Unknown terminator instruction: " << *TI << '\n'; 550#endif 551 llvm_unreachable(0); 552} 553 554// visit Implementations - Something changed in this instruction, either an 555// operand made a transition, or the instruction is newly executable. Change 556// the value type of I to reflect these changes if appropriate. This method 557// makes sure to do the following actions: 558// 559// 1. If a phi node merges two constants in, and has conflicting value coming 560// from different branches, or if the PHI node merges in an overdefined 561// value, then the PHI node becomes overdefined. 562// 2. If a phi node merges only constants in, and they all agree on value, the 563// PHI node becomes a constant value equal to that. 564// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 565// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 566// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 567// 6. If a conditional branch has a value that is constant, make the selected 568// destination executable 569// 7. If a conditional branch has a value that is overdefined, make all 570// successors executable. 571// 572void SCCPSolver::visitPHINode(PHINode &PN) { 573 LatticeVal &PNIV = getValueState(&PN); 574 if (PNIV.isOverdefined()) { 575 // There may be instructions using this PHI node that are not overdefined 576 // themselves. If so, make sure that they know that the PHI node operand 577 // changed. 578 std::multimap<PHINode*, Instruction*>::iterator I, E; 579 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); 580 if (I != E) { 581 SmallVector<Instruction*, 16> Users; 582 for (; I != E; ++I) Users.push_back(I->second); 583 while (!Users.empty()) { 584 visit(Users.back()); 585 Users.pop_back(); 586 } 587 } 588 return; // Quick exit 589 } 590 591 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 592 // and slow us down a lot. Just mark them overdefined. 593 if (PN.getNumIncomingValues() > 64) { 594 markOverdefined(PNIV, &PN); 595 return; 596 } 597 598 // Look at all of the executable operands of the PHI node. If any of them 599 // are overdefined, the PHI becomes overdefined as well. If they are all 600 // constant, and they agree with each other, the PHI becomes the identical 601 // constant. If they are constant and don't agree, the PHI is overdefined. 602 // If there are no executable operands, the PHI remains undefined. 603 // 604 Constant *OperandVal = 0; 605 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 606 LatticeVal &IV = getValueState(PN.getIncomingValue(i)); 607 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 608 609 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { 610 if (IV.isOverdefined()) { // PHI node becomes overdefined! 611 markOverdefined(&PN); 612 return; 613 } 614 615 if (OperandVal == 0) { // Grab the first value. 616 OperandVal = IV.getConstant(); 617 } else { // Another value is being merged in! 618 // There is already a reachable operand. If we conflict with it, 619 // then the PHI node becomes overdefined. If we agree with it, we 620 // can continue on. 621 622 // Check to see if there are two different constants merging. 623 if (IV.getConstant() != OperandVal) { 624 // Yes there is. This means the PHI node is not constant. 625 // You must be overdefined poor PHI. 626 // 627 markOverdefined(&PN); // The PHI node now becomes overdefined 628 return; // I'm done analyzing you 629 } 630 } 631 } 632 } 633 634 // If we exited the loop, this means that the PHI node only has constant 635 // arguments that agree with each other(and OperandVal is the constant) or 636 // OperandVal is null because there are no defined incoming arguments. If 637 // this is the case, the PHI remains undefined. 638 // 639 if (OperandVal) 640 markConstant(&PN, OperandVal); // Acquire operand value 641} 642 643void SCCPSolver::visitReturnInst(ReturnInst &I) { 644 if (I.getNumOperands() == 0) return; // Ret void 645 646 Function *F = I.getParent()->getParent(); 647 // If we are tracking the return value of this function, merge it in. 648 if (!F->hasLocalLinkage()) 649 return; 650 651 if (!TrackedRetVals.empty() && I.getNumOperands() == 1) { 652 DenseMap<Function*, LatticeVal>::iterator TFRVI = 653 TrackedRetVals.find(F); 654 if (TFRVI != TrackedRetVals.end() && 655 !TFRVI->second.isOverdefined()) { 656 LatticeVal &IV = getValueState(I.getOperand(0)); 657 mergeInValue(TFRVI->second, F, IV); 658 return; 659 } 660 } 661 662 // Handle functions that return multiple values. 663 if (!TrackedMultipleRetVals.empty() && I.getNumOperands() > 1) { 664 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 665 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 666 It = TrackedMultipleRetVals.find(std::make_pair(F, i)); 667 if (It == TrackedMultipleRetVals.end()) break; 668 mergeInValue(It->second, F, getValueState(I.getOperand(i))); 669 } 670 } else if (!TrackedMultipleRetVals.empty() && 671 I.getNumOperands() == 1 && 672 isa<StructType>(I.getOperand(0)->getType())) { 673 for (unsigned i = 0, e = I.getOperand(0)->getType()->getNumContainedTypes(); 674 i != e; ++i) { 675 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 676 It = TrackedMultipleRetVals.find(std::make_pair(F, i)); 677 if (It == TrackedMultipleRetVals.end()) break; 678 if (Value *Val = FindInsertedValue(I.getOperand(0), i, I.getContext())) 679 mergeInValue(It->second, F, getValueState(Val)); 680 } 681 } 682} 683 684void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) { 685 SmallVector<bool, 16> SuccFeasible; 686 getFeasibleSuccessors(TI, SuccFeasible); 687 688 BasicBlock *BB = TI.getParent(); 689 690 // Mark all feasible successors executable. 691 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 692 if (SuccFeasible[i]) 693 markEdgeExecutable(BB, TI.getSuccessor(i)); 694} 695 696void SCCPSolver::visitCastInst(CastInst &I) { 697 Value *V = I.getOperand(0); 698 LatticeVal &VState = getValueState(V); 699 if (VState.isOverdefined()) // Inherit overdefinedness of operand 700 markOverdefined(&I); 701 else if (VState.isConstant()) // Propagate constant value 702 markConstant(&I, ConstantExpr::getCast(I.getOpcode(), 703 VState.getConstant(), I.getType())); 704} 705 706void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { 707 Value *Aggr = EVI.getAggregateOperand(); 708 709 // If the operand to the extractvalue is an undef, the result is undef. 710 if (isa<UndefValue>(Aggr)) 711 return; 712 713 // Currently only handle single-index extractvalues. 714 if (EVI.getNumIndices() != 1) { 715 markOverdefined(&EVI); 716 return; 717 } 718 719 Function *F = 0; 720 if (CallInst *CI = dyn_cast<CallInst>(Aggr)) 721 F = CI->getCalledFunction(); 722 else if (InvokeInst *II = dyn_cast<InvokeInst>(Aggr)) 723 F = II->getCalledFunction(); 724 725 // TODO: If IPSCCP resolves the callee of this function, we could propagate a 726 // result back! 727 if (F == 0 || TrackedMultipleRetVals.empty()) { 728 markOverdefined(&EVI); 729 return; 730 } 731 732 // See if we are tracking the result of the callee. If not tracking this 733 // function (for example, it is a declaration) just move to overdefined. 734 if (!TrackedMultipleRetVals.count(std::make_pair(F, *EVI.idx_begin()))) { 735 markOverdefined(&EVI); 736 return; 737 } 738 739 // Otherwise, the value will be merged in here as a result of CallSite 740 // handling. 741} 742 743void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { 744 Value *Aggr = IVI.getAggregateOperand(); 745 Value *Val = IVI.getInsertedValueOperand(); 746 747 // If the operands to the insertvalue are undef, the result is undef. 748 if (isa<UndefValue>(Aggr) && isa<UndefValue>(Val)) 749 return; 750 751 // Currently only handle single-index insertvalues. 752 if (IVI.getNumIndices() != 1) { 753 markOverdefined(&IVI); 754 return; 755 } 756 757 // Currently only handle insertvalue instructions that are in a single-use 758 // chain that builds up a return value. 759 for (const InsertValueInst *TmpIVI = &IVI; ; ) { 760 if (!TmpIVI->hasOneUse()) { 761 markOverdefined(&IVI); 762 return; 763 } 764 const Value *V = *TmpIVI->use_begin(); 765 if (isa<ReturnInst>(V)) 766 break; 767 TmpIVI = dyn_cast<InsertValueInst>(V); 768 if (!TmpIVI) { 769 markOverdefined(&IVI); 770 return; 771 } 772 } 773 774 // See if we are tracking the result of the callee. 775 Function *F = IVI.getParent()->getParent(); 776 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 777 It = TrackedMultipleRetVals.find(std::make_pair(F, *IVI.idx_begin())); 778 779 // Merge in the inserted member value. 780 if (It != TrackedMultipleRetVals.end()) 781 mergeInValue(It->second, F, getValueState(Val)); 782 783 // Mark the aggregate result of the IVI overdefined; any tracking that we do 784 // will be done on the individual member values. 785 markOverdefined(&IVI); 786} 787 788void SCCPSolver::visitSelectInst(SelectInst &I) { 789 LatticeVal &CondValue = getValueState(I.getCondition()); 790 if (CondValue.isUndefined()) 791 return; 792 if (CondValue.isConstant()) { 793 if (ConstantInt *CondCB = dyn_cast<ConstantInt>(CondValue.getConstant())){ 794 mergeInValue(&I, getValueState(CondCB->getZExtValue() ? I.getTrueValue() 795 : I.getFalseValue())); 796 return; 797 } 798 } 799 800 // Otherwise, the condition is overdefined or a constant we can't evaluate. 801 // See if we can produce something better than overdefined based on the T/F 802 // value. 803 LatticeVal &TVal = getValueState(I.getTrueValue()); 804 LatticeVal &FVal = getValueState(I.getFalseValue()); 805 806 // select ?, C, C -> C. 807 if (TVal.isConstant() && FVal.isConstant() && 808 TVal.getConstant() == FVal.getConstant()) { 809 markConstant(&I, FVal.getConstant()); 810 return; 811 } 812 813 if (TVal.isUndefined()) { // select ?, undef, X -> X. 814 mergeInValue(&I, FVal); 815 } else if (FVal.isUndefined()) { // select ?, X, undef -> X. 816 mergeInValue(&I, TVal); 817 } else { 818 markOverdefined(&I); 819 } 820} 821 822// Handle BinaryOperators and Shift Instructions. 823void SCCPSolver::visitBinaryOperator(Instruction &I) { 824 LatticeVal &IV = ValueState[&I]; 825 if (IV.isOverdefined()) return; 826 827 LatticeVal &V1State = getValueState(I.getOperand(0)); 828 LatticeVal &V2State = getValueState(I.getOperand(1)); 829 830 if (V1State.isOverdefined() || V2State.isOverdefined()) { 831 // If this is an AND or OR with 0 or -1, it doesn't matter that the other 832 // operand is overdefined. 833 if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) { 834 LatticeVal *NonOverdefVal = 0; 835 if (!V1State.isOverdefined()) { 836 NonOverdefVal = &V1State; 837 } else if (!V2State.isOverdefined()) { 838 NonOverdefVal = &V2State; 839 } 840 841 if (NonOverdefVal) { 842 if (NonOverdefVal->isUndefined()) { 843 // Could annihilate value. 844 if (I.getOpcode() == Instruction::And) 845 markConstant(IV, &I, Constant::getNullValue(I.getType())); 846 else if (const VectorType *PT = dyn_cast<VectorType>(I.getType())) 847 markConstant(IV, &I, Constant::getAllOnesValue(PT)); 848 else 849 markConstant(IV, &I, 850 Constant::getAllOnesValue(I.getType())); 851 return; 852 } else { 853 if (I.getOpcode() == Instruction::And) { 854 if (NonOverdefVal->getConstant()->isNullValue()) { 855 markConstant(IV, &I, NonOverdefVal->getConstant()); 856 return; // X and 0 = 0 857 } 858 } else { 859 if (ConstantInt *CI = 860 dyn_cast<ConstantInt>(NonOverdefVal->getConstant())) 861 if (CI->isAllOnesValue()) { 862 markConstant(IV, &I, NonOverdefVal->getConstant()); 863 return; // X or -1 = -1 864 } 865 } 866 } 867 } 868 } 869 870 871 // If both operands are PHI nodes, it is possible that this instruction has 872 // a constant value, despite the fact that the PHI node doesn't. Check for 873 // this condition now. 874 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 875 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 876 if (PN1->getParent() == PN2->getParent()) { 877 // Since the two PHI nodes are in the same basic block, they must have 878 // entries for the same predecessors. Walk the predecessor list, and 879 // if all of the incoming values are constants, and the result of 880 // evaluating this expression with all incoming value pairs is the 881 // same, then this expression is a constant even though the PHI node 882 // is not a constant! 883 LatticeVal Result; 884 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 885 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 886 BasicBlock *InBlock = PN1->getIncomingBlock(i); 887 LatticeVal &In2 = 888 getValueState(PN2->getIncomingValueForBlock(InBlock)); 889 890 if (In1.isOverdefined() || In2.isOverdefined()) { 891 Result.markOverdefined(); 892 break; // Cannot fold this operation over the PHI nodes! 893 } else if (In1.isConstant() && In2.isConstant()) { 894 Constant *V = 895 ConstantExpr::get(I.getOpcode(), In1.getConstant(), 896 In2.getConstant()); 897 if (Result.isUndefined()) 898 Result.markConstant(V); 899 else if (Result.isConstant() && Result.getConstant() != V) { 900 Result.markOverdefined(); 901 break; 902 } 903 } 904 } 905 906 // If we found a constant value here, then we know the instruction is 907 // constant despite the fact that the PHI nodes are overdefined. 908 if (Result.isConstant()) { 909 markConstant(IV, &I, Result.getConstant()); 910 // Remember that this instruction is virtually using the PHI node 911 // operands. 912 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 913 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 914 return; 915 } else if (Result.isUndefined()) { 916 return; 917 } 918 919 // Okay, this really is overdefined now. Since we might have 920 // speculatively thought that this was not overdefined before, and 921 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 922 // make sure to clean out any entries that we put there, for 923 // efficiency. 924 std::multimap<PHINode*, Instruction*>::iterator It, E; 925 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 926 while (It != E) { 927 if (It->second == &I) { 928 UsersOfOverdefinedPHIs.erase(It++); 929 } else 930 ++It; 931 } 932 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 933 while (It != E) { 934 if (It->second == &I) { 935 UsersOfOverdefinedPHIs.erase(It++); 936 } else 937 ++It; 938 } 939 } 940 941 markOverdefined(IV, &I); 942 } else if (V1State.isConstant() && V2State.isConstant()) { 943 markConstant(IV, &I, 944 ConstantExpr::get(I.getOpcode(), V1State.getConstant(), 945 V2State.getConstant())); 946 } 947} 948 949// Handle ICmpInst instruction. 950void SCCPSolver::visitCmpInst(CmpInst &I) { 951 LatticeVal &IV = ValueState[&I]; 952 if (IV.isOverdefined()) return; 953 954 LatticeVal &V1State = getValueState(I.getOperand(0)); 955 LatticeVal &V2State = getValueState(I.getOperand(1)); 956 957 if (V1State.isOverdefined() || V2State.isOverdefined()) { 958 // If both operands are PHI nodes, it is possible that this instruction has 959 // a constant value, despite the fact that the PHI node doesn't. Check for 960 // this condition now. 961 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 962 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 963 if (PN1->getParent() == PN2->getParent()) { 964 // Since the two PHI nodes are in the same basic block, they must have 965 // entries for the same predecessors. Walk the predecessor list, and 966 // if all of the incoming values are constants, and the result of 967 // evaluating this expression with all incoming value pairs is the 968 // same, then this expression is a constant even though the PHI node 969 // is not a constant! 970 LatticeVal Result; 971 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 972 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i)); 973 BasicBlock *InBlock = PN1->getIncomingBlock(i); 974 LatticeVal &In2 = 975 getValueState(PN2->getIncomingValueForBlock(InBlock)); 976 977 if (In1.isOverdefined() || In2.isOverdefined()) { 978 Result.markOverdefined(); 979 break; // Cannot fold this operation over the PHI nodes! 980 } else if (In1.isConstant() && In2.isConstant()) { 981 Constant *V = ConstantExpr::getCompare(I.getPredicate(), 982 In1.getConstant(), 983 In2.getConstant()); 984 if (Result.isUndefined()) 985 Result.markConstant(V); 986 else if (Result.isConstant() && Result.getConstant() != V) { 987 Result.markOverdefined(); 988 break; 989 } 990 } 991 } 992 993 // If we found a constant value here, then we know the instruction is 994 // constant despite the fact that the PHI nodes are overdefined. 995 if (Result.isConstant()) { 996 markConstant(IV, &I, Result.getConstant()); 997 // Remember that this instruction is virtually using the PHI node 998 // operands. 999 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 1000 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 1001 return; 1002 } else if (Result.isUndefined()) { 1003 return; 1004 } 1005 1006 // Okay, this really is overdefined now. Since we might have 1007 // speculatively thought that this was not overdefined before, and 1008 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 1009 // make sure to clean out any entries that we put there, for 1010 // efficiency. 1011 std::multimap<PHINode*, Instruction*>::iterator It, E; 1012 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 1013 while (It != E) { 1014 if (It->second == &I) { 1015 UsersOfOverdefinedPHIs.erase(It++); 1016 } else 1017 ++It; 1018 } 1019 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 1020 while (It != E) { 1021 if (It->second == &I) { 1022 UsersOfOverdefinedPHIs.erase(It++); 1023 } else 1024 ++It; 1025 } 1026 } 1027 1028 markOverdefined(IV, &I); 1029 } else if (V1State.isConstant() && V2State.isConstant()) { 1030 markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(), 1031 V1State.getConstant(), 1032 V2State.getConstant())); 1033 } 1034} 1035 1036void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) { 1037 // FIXME : SCCP does not handle vectors properly. 1038 markOverdefined(&I); 1039 return; 1040 1041#if 0 1042 LatticeVal &ValState = getValueState(I.getOperand(0)); 1043 LatticeVal &IdxState = getValueState(I.getOperand(1)); 1044 1045 if (ValState.isOverdefined() || IdxState.isOverdefined()) 1046 markOverdefined(&I); 1047 else if(ValState.isConstant() && IdxState.isConstant()) 1048 markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(), 1049 IdxState.getConstant())); 1050#endif 1051} 1052 1053void SCCPSolver::visitInsertElementInst(InsertElementInst &I) { 1054 // FIXME : SCCP does not handle vectors properly. 1055 markOverdefined(&I); 1056 return; 1057#if 0 1058 LatticeVal &ValState = getValueState(I.getOperand(0)); 1059 LatticeVal &EltState = getValueState(I.getOperand(1)); 1060 LatticeVal &IdxState = getValueState(I.getOperand(2)); 1061 1062 if (ValState.isOverdefined() || EltState.isOverdefined() || 1063 IdxState.isOverdefined()) 1064 markOverdefined(&I); 1065 else if(ValState.isConstant() && EltState.isConstant() && 1066 IdxState.isConstant()) 1067 markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(), 1068 EltState.getConstant(), 1069 IdxState.getConstant())); 1070 else if (ValState.isUndefined() && EltState.isConstant() && 1071 IdxState.isConstant()) 1072 markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()), 1073 EltState.getConstant(), 1074 IdxState.getConstant())); 1075#endif 1076} 1077 1078void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) { 1079 // FIXME : SCCP does not handle vectors properly. 1080 markOverdefined(&I); 1081 return; 1082#if 0 1083 LatticeVal &V1State = getValueState(I.getOperand(0)); 1084 LatticeVal &V2State = getValueState(I.getOperand(1)); 1085 LatticeVal &MaskState = getValueState(I.getOperand(2)); 1086 1087 if (MaskState.isUndefined() || 1088 (V1State.isUndefined() && V2State.isUndefined())) 1089 return; // Undefined output if mask or both inputs undefined. 1090 1091 if (V1State.isOverdefined() || V2State.isOverdefined() || 1092 MaskState.isOverdefined()) { 1093 markOverdefined(&I); 1094 } else { 1095 // A mix of constant/undef inputs. 1096 Constant *V1 = V1State.isConstant() ? 1097 V1State.getConstant() : UndefValue::get(I.getType()); 1098 Constant *V2 = V2State.isConstant() ? 1099 V2State.getConstant() : UndefValue::get(I.getType()); 1100 Constant *Mask = MaskState.isConstant() ? 1101 MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType()); 1102 markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask)); 1103 } 1104#endif 1105} 1106 1107// Handle getelementptr instructions. If all operands are constants then we 1108// can turn this into a getelementptr ConstantExpr. 1109// 1110void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { 1111 LatticeVal &IV = ValueState[&I]; 1112 if (IV.isOverdefined()) return; 1113 1114 SmallVector<Constant*, 8> Operands; 1115 Operands.reserve(I.getNumOperands()); 1116 1117 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 1118 LatticeVal &State = getValueState(I.getOperand(i)); 1119 if (State.isUndefined()) 1120 return; // Operands are not resolved yet. 1121 1122 if (State.isOverdefined()) { 1123 markOverdefined(IV, &I); 1124 return; 1125 } 1126 assert(State.isConstant() && "Unknown state!"); 1127 Operands.push_back(State.getConstant()); 1128 } 1129 1130 Constant *Ptr = Operands[0]; 1131 Operands.erase(Operands.begin()); // Erase the pointer from idx list. 1132 1133 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, &Operands[0], 1134 Operands.size())); 1135} 1136 1137void SCCPSolver::visitStoreInst(Instruction &SI) { 1138 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1))) 1139 return; 1140 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); 1141 DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV); 1142 if (I == TrackedGlobals.end() || I->second.isOverdefined()) return; 1143 1144 // Get the value we are storing into the global. 1145 LatticeVal &PtrVal = getValueState(SI.getOperand(0)); 1146 1147 mergeInValue(I->second, GV, PtrVal); 1148 if (I->second.isOverdefined()) 1149 TrackedGlobals.erase(I); // No need to keep tracking this! 1150} 1151 1152 1153// Handle load instructions. If the operand is a constant pointer to a constant 1154// global, we can replace the load with the loaded constant value! 1155void SCCPSolver::visitLoadInst(LoadInst &I) { 1156 LatticeVal &IV = ValueState[&I]; 1157 if (IV.isOverdefined()) return; 1158 1159 LatticeVal &PtrVal = getValueState(I.getOperand(0)); 1160 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! 1161 if (PtrVal.isConstant() && !I.isVolatile()) { 1162 Value *Ptr = PtrVal.getConstant(); 1163 // TODO: Consider a target hook for valid address spaces for this xform. 1164 if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0) { 1165 // load null -> null 1166 markConstant(IV, &I, Constant::getNullValue(I.getType())); 1167 return; 1168 } 1169 1170 // Transform load (constant global) into the value loaded. 1171 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 1172 if (GV->isConstant()) { 1173 if (GV->hasDefinitiveInitializer()) { 1174 markConstant(IV, &I, GV->getInitializer()); 1175 return; 1176 } 1177 } else if (!TrackedGlobals.empty()) { 1178 // If we are tracking this global, merge in the known value for it. 1179 DenseMap<GlobalVariable*, LatticeVal>::iterator It = 1180 TrackedGlobals.find(GV); 1181 if (It != TrackedGlobals.end()) { 1182 mergeInValue(IV, &I, It->second); 1183 return; 1184 } 1185 } 1186 } 1187 1188 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded. 1189 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 1190 if (CE->getOpcode() == Instruction::GetElementPtr) 1191 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 1192 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 1193 if (Constant *V = 1194 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) { 1195 markConstant(IV, &I, V); 1196 return; 1197 } 1198 } 1199 1200 // Otherwise we cannot say for certain what value this load will produce. 1201 // Bail out. 1202 markOverdefined(IV, &I); 1203} 1204 1205void SCCPSolver::visitCallSite(CallSite CS) { 1206 Function *F = CS.getCalledFunction(); 1207 Instruction *I = CS.getInstruction(); 1208 1209 // The common case is that we aren't tracking the callee, either because we 1210 // are not doing interprocedural analysis or the callee is indirect, or is 1211 // external. Handle these cases first. 1212 if (F == 0 || !F->hasLocalLinkage()) { 1213CallOverdefined: 1214 // Void return and not tracking callee, just bail. 1215 if (I->getType()->isVoidTy()) return; 1216 1217 // Otherwise, if we have a single return value case, and if the function is 1218 // a declaration, maybe we can constant fold it. 1219 if (!isa<StructType>(I->getType()) && F && F->isDeclaration() && 1220 canConstantFoldCallTo(F)) { 1221 1222 SmallVector<Constant*, 8> Operands; 1223 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 1224 AI != E; ++AI) { 1225 LatticeVal &State = getValueState(*AI); 1226 if (State.isUndefined()) 1227 return; // Operands are not resolved yet. 1228 else if (State.isOverdefined()) { 1229 markOverdefined(I); 1230 return; 1231 } 1232 assert(State.isConstant() && "Unknown state!"); 1233 Operands.push_back(State.getConstant()); 1234 } 1235 1236 // If we can constant fold this, mark the result of the call as a 1237 // constant. 1238 if (Constant *C = ConstantFoldCall(F, Operands.data(), Operands.size())) { 1239 markConstant(I, C); 1240 return; 1241 } 1242 } 1243 1244 // Otherwise, we don't know anything about this call, mark it overdefined. 1245 markOverdefined(I); 1246 return; 1247 } 1248 1249 // If this is a single/zero retval case, see if we're tracking the function. 1250 DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F); 1251 if (TFRVI != TrackedRetVals.end()) { 1252 // If so, propagate the return value of the callee into this call result. 1253 mergeInValue(I, TFRVI->second); 1254 } else if (isa<StructType>(I->getType())) { 1255 // Check to see if we're tracking this callee, if not, handle it in the 1256 // common path above. 1257 DenseMap<std::pair<Function*, unsigned>, LatticeVal>::iterator 1258 TMRVI = TrackedMultipleRetVals.find(std::make_pair(F, 0)); 1259 if (TMRVI == TrackedMultipleRetVals.end()) 1260 goto CallOverdefined; 1261 1262 // Need to mark as overdefined, otherwise it stays undefined which 1263 // creates extractvalue undef, <idx> 1264 markOverdefined(I); 1265 // If we are tracking this callee, propagate the return values of the call 1266 // into this call site. We do this by walking all the uses. Single-index 1267 // ExtractValueInst uses can be tracked; anything more complicated is 1268 // currently handled conservatively. 1269 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1270 UI != E; ++UI) { 1271 if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(*UI)) { 1272 if (EVI->getNumIndices() == 1) { 1273 mergeInValue(EVI, 1274 TrackedMultipleRetVals[std::make_pair(F, *EVI->idx_begin())]); 1275 continue; 1276 } 1277 } 1278 // The aggregate value is used in a way not handled here. Assume nothing. 1279 markOverdefined(*UI); 1280 } 1281 } else { 1282 // Otherwise we're not tracking this callee, so handle it in the 1283 // common path above. 1284 goto CallOverdefined; 1285 } 1286 1287 // Finally, if this is the first call to the function hit, mark its entry 1288 // block executable. 1289 if (!BBExecutable.count(F->begin())) 1290 MarkBlockExecutable(F->begin()); 1291 1292 // Propagate information from this call site into the callee. 1293 CallSite::arg_iterator CAI = CS.arg_begin(); 1294 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1295 AI != E; ++AI, ++CAI) { 1296 LatticeVal &IV = ValueState[AI]; 1297 if (AI->hasByValAttr() && !F->onlyReadsMemory()) { 1298 IV.markOverdefined(); 1299 continue; 1300 } 1301 if (!IV.isOverdefined()) 1302 mergeInValue(IV, AI, getValueState(*CAI)); 1303 } 1304} 1305 1306void SCCPSolver::Solve() { 1307 // Process the work lists until they are empty! 1308 while (!BBWorkList.empty() || !InstWorkList.empty() || 1309 !OverdefinedInstWorkList.empty()) { 1310 // Process the instruction work list. 1311 while (!OverdefinedInstWorkList.empty()) { 1312 Value *I = OverdefinedInstWorkList.back(); 1313 OverdefinedInstWorkList.pop_back(); 1314 1315 DEBUG(errs() << "\nPopped off OI-WL: " << *I << '\n'); 1316 1317 // "I" got into the work list because it either made the transition from 1318 // bottom to constant 1319 // 1320 // Anything on this worklist that is overdefined need not be visited 1321 // since all of its users will have already been marked as overdefined 1322 // Update all of the users of this instruction's value. 1323 // 1324 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1325 UI != E; ++UI) 1326 OperandChangedState(*UI); 1327 } 1328 1329 // Process the instruction work list. 1330 while (!InstWorkList.empty()) { 1331 Value *I = InstWorkList.back(); 1332 InstWorkList.pop_back(); 1333 1334 DEBUG(errs() << "\nPopped off I-WL: " << *I << '\n'); 1335 1336 // "I" got into the work list because it either made the transition from 1337 // bottom to constant 1338 // 1339 // Anything on this worklist that is overdefined need not be visited 1340 // since all of its users will have already been marked as overdefined. 1341 // Update all of the users of this instruction's value. 1342 // 1343 if (!getValueState(I).isOverdefined()) 1344 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1345 UI != E; ++UI) 1346 OperandChangedState(*UI); 1347 } 1348 1349 // Process the basic block work list. 1350 while (!BBWorkList.empty()) { 1351 BasicBlock *BB = BBWorkList.back(); 1352 BBWorkList.pop_back(); 1353 1354 DEBUG(errs() << "\nPopped off BBWL: " << *BB << '\n'); 1355 1356 // Notify all instructions in this basic block that they are newly 1357 // executable. 1358 visit(BB); 1359 } 1360 } 1361} 1362 1363/// ResolvedUndefsIn - While solving the dataflow for a function, we assume 1364/// that branches on undef values cannot reach any of their successors. 1365/// However, this is not a safe assumption. After we solve dataflow, this 1366/// method should be use to handle this. If this returns true, the solver 1367/// should be rerun. 1368/// 1369/// This method handles this by finding an unresolved branch and marking it one 1370/// of the edges from the block as being feasible, even though the condition 1371/// doesn't say it would otherwise be. This allows SCCP to find the rest of the 1372/// CFG and only slightly pessimizes the analysis results (by marking one, 1373/// potentially infeasible, edge feasible). This cannot usefully modify the 1374/// constraints on the condition of the branch, as that would impact other users 1375/// of the value. 1376/// 1377/// This scan also checks for values that use undefs, whose results are actually 1378/// defined. For example, 'zext i8 undef to i32' should produce all zeros 1379/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero, 1380/// even if X isn't defined. 1381bool SCCPSolver::ResolvedUndefsIn(Function &F) { 1382 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 1383 if (!BBExecutable.count(BB)) 1384 continue; 1385 1386 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 1387 // Look for instructions which produce undef values. 1388 if (I->getType()->isVoidTy()) continue; 1389 1390 LatticeVal &LV = getValueState(I); 1391 if (!LV.isUndefined()) continue; 1392 1393 // Get the lattice values of the first two operands for use below. 1394 LatticeVal &Op0LV = getValueState(I->getOperand(0)); 1395 LatticeVal Op1LV; 1396 if (I->getNumOperands() == 2) { 1397 // If this is a two-operand instruction, and if both operands are 1398 // undefs, the result stays undef. 1399 Op1LV = getValueState(I->getOperand(1)); 1400 if (Op0LV.isUndefined() && Op1LV.isUndefined()) 1401 continue; 1402 } 1403 1404 // If this is an instructions whose result is defined even if the input is 1405 // not fully defined, propagate the information. 1406 const Type *ITy = I->getType(); 1407 switch (I->getOpcode()) { 1408 default: break; // Leave the instruction as an undef. 1409 case Instruction::ZExt: 1410 // After a zero extend, we know the top part is zero. SExt doesn't have 1411 // to be handled here, because we don't know whether the top part is 1's 1412 // or 0's. 1413 assert(Op0LV.isUndefined()); 1414 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1415 return true; 1416 case Instruction::Mul: 1417 case Instruction::And: 1418 // undef * X -> 0. X could be zero. 1419 // undef & X -> 0. X could be zero. 1420 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1421 return true; 1422 1423 case Instruction::Or: 1424 // undef | X -> -1. X could be -1. 1425 if (const VectorType *PTy = dyn_cast<VectorType>(ITy)) 1426 markForcedConstant(LV, I, 1427 Constant::getAllOnesValue(PTy)); 1428 else 1429 markForcedConstant(LV, I, Constant::getAllOnesValue(ITy)); 1430 return true; 1431 1432 case Instruction::SDiv: 1433 case Instruction::UDiv: 1434 case Instruction::SRem: 1435 case Instruction::URem: 1436 // X / undef -> undef. No change. 1437 // X % undef -> undef. No change. 1438 if (Op1LV.isUndefined()) break; 1439 1440 // undef / X -> 0. X could be maxint. 1441 // undef % X -> 0. X could be 1. 1442 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1443 return true; 1444 1445 case Instruction::AShr: 1446 // undef >>s X -> undef. No change. 1447 if (Op0LV.isUndefined()) break; 1448 1449 // X >>s undef -> X. X could be 0, X could have the high-bit known set. 1450 if (Op0LV.isConstant()) 1451 markForcedConstant(LV, I, Op0LV.getConstant()); 1452 else 1453 markOverdefined(LV, I); 1454 return true; 1455 case Instruction::LShr: 1456 case Instruction::Shl: 1457 // undef >> X -> undef. No change. 1458 // undef << X -> undef. No change. 1459 if (Op0LV.isUndefined()) break; 1460 1461 // X >> undef -> 0. X could be 0. 1462 // X << undef -> 0. X could be 0. 1463 markForcedConstant(LV, I, Constant::getNullValue(ITy)); 1464 return true; 1465 case Instruction::Select: 1466 // undef ? X : Y -> X or Y. There could be commonality between X/Y. 1467 if (Op0LV.isUndefined()) { 1468 if (!Op1LV.isConstant()) // Pick the constant one if there is any. 1469 Op1LV = getValueState(I->getOperand(2)); 1470 } else if (Op1LV.isUndefined()) { 1471 // c ? undef : undef -> undef. No change. 1472 Op1LV = getValueState(I->getOperand(2)); 1473 if (Op1LV.isUndefined()) 1474 break; 1475 // Otherwise, c ? undef : x -> x. 1476 } else { 1477 // Leave Op1LV as Operand(1)'s LatticeValue. 1478 } 1479 1480 if (Op1LV.isConstant()) 1481 markForcedConstant(LV, I, Op1LV.getConstant()); 1482 else 1483 markOverdefined(LV, I); 1484 return true; 1485 case Instruction::Call: 1486 // If a call has an undef result, it is because it is constant foldable 1487 // but one of the inputs was undef. Just force the result to 1488 // overdefined. 1489 markOverdefined(LV, I); 1490 return true; 1491 } 1492 } 1493 1494 TerminatorInst *TI = BB->getTerminator(); 1495 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1496 if (!BI->isConditional()) continue; 1497 if (!getValueState(BI->getCondition()).isUndefined()) 1498 continue; 1499 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1500 if (SI->getNumSuccessors() < 2) // no cases 1501 continue; 1502 if (!getValueState(SI->getCondition()).isUndefined()) 1503 continue; 1504 } else { 1505 continue; 1506 } 1507 1508 // If the edge to the second successor isn't thought to be feasible yet, 1509 // mark it so now. We pick the second one so that this goes to some 1510 // enumerated value in a switch instead of going to the default destination. 1511 if (KnownFeasibleEdges.count(Edge(BB, TI->getSuccessor(1)))) 1512 continue; 1513 1514 // Otherwise, it isn't already thought to be feasible. Mark it as such now 1515 // and return. This will make other blocks reachable, which will allow new 1516 // values to be discovered and existing ones to be moved in the lattice. 1517 markEdgeExecutable(BB, TI->getSuccessor(1)); 1518 1519 // This must be a conditional branch of switch on undef. At this point, 1520 // force the old terminator to branch to the first successor. This is 1521 // required because we are now influencing the dataflow of the function with 1522 // the assumption that this edge is taken. If we leave the branch condition 1523 // as undef, then further analysis could think the undef went another way 1524 // leading to an inconsistent set of conclusions. 1525 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1526 BI->setCondition(ConstantInt::getFalse(BI->getContext())); 1527 } else { 1528 SwitchInst *SI = cast<SwitchInst>(TI); 1529 SI->setCondition(SI->getCaseValue(1)); 1530 } 1531 1532 return true; 1533 } 1534 1535 return false; 1536} 1537 1538 1539namespace { 1540 //===--------------------------------------------------------------------===// 1541 // 1542 /// SCCP Class - This class uses the SCCPSolver to implement a per-function 1543 /// Sparse Conditional Constant Propagator. 1544 /// 1545 struct SCCP : public FunctionPass { 1546 static char ID; // Pass identification, replacement for typeid 1547 SCCP() : FunctionPass(&ID) {} 1548 1549 // runOnFunction - Run the Sparse Conditional Constant Propagation 1550 // algorithm, and return true if the function was modified. 1551 // 1552 bool runOnFunction(Function &F); 1553 1554 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1555 AU.setPreservesCFG(); 1556 } 1557 }; 1558} // end anonymous namespace 1559 1560char SCCP::ID = 0; 1561static RegisterPass<SCCP> 1562X("sccp", "Sparse Conditional Constant Propagation"); 1563 1564// createSCCPPass - This is the public interface to this file. 1565FunctionPass *llvm::createSCCPPass() { 1566 return new SCCP(); 1567} 1568 1569 1570// runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, 1571// and return true if the function was modified. 1572// 1573bool SCCP::runOnFunction(Function &F) { 1574 DEBUG(errs() << "SCCP on function '" << F.getName() << "'\n"); 1575 SCCPSolver Solver; 1576 1577 // Mark the first block of the function as being executable. 1578 Solver.MarkBlockExecutable(F.begin()); 1579 1580 // Mark all arguments to the function as being overdefined. 1581 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) 1582 Solver.markOverdefined(AI); 1583 1584 // Solve for constants. 1585 bool ResolvedUndefs = true; 1586 while (ResolvedUndefs) { 1587 Solver.Solve(); 1588 DEBUG(errs() << "RESOLVING UNDEFs\n"); 1589 ResolvedUndefs = Solver.ResolvedUndefsIn(F); 1590 } 1591 1592 bool MadeChanges = false; 1593 1594 // If we decided that there are basic blocks that are dead in this function, 1595 // delete their contents now. Note that we cannot actually delete the blocks, 1596 // as we cannot modify the CFG of the function. 1597 // 1598 SmallVector<Instruction*, 512> Insts; 1599 std::map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 1600 1601 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 1602 if (!Solver.isBlockExecutable(BB)) { 1603 DEBUG(errs() << " BasicBlock Dead:" << *BB); 1604 ++NumDeadBlocks; 1605 1606 // Delete the instructions backwards, as it has a reduced likelihood of 1607 // having to update as many def-use and use-def chains. 1608 for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator(); 1609 I != E; ++I) 1610 Insts.push_back(I); 1611 while (!Insts.empty()) { 1612 Instruction *I = Insts.back(); 1613 Insts.pop_back(); 1614 if (!I->use_empty()) 1615 I->replaceAllUsesWith(UndefValue::get(I->getType())); 1616 BB->getInstList().erase(I); 1617 MadeChanges = true; 1618 ++NumInstRemoved; 1619 } 1620 } else { 1621 // Iterate over all of the instructions in a function, replacing them with 1622 // constants if we have found them to be of constant values. 1623 // 1624 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 1625 Instruction *Inst = BI++; 1626 if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst)) 1627 continue; 1628 1629 LatticeVal &IV = Values[Inst]; 1630 if (!IV.isConstant() && !IV.isUndefined()) 1631 continue; 1632 1633 Constant *Const = IV.isConstant() 1634 ? IV.getConstant() : UndefValue::get(Inst->getType()); 1635 DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); 1636 1637 // Replaces all of the uses of a variable with uses of the constant. 1638 Inst->replaceAllUsesWith(Const); 1639 1640 // Delete the instruction. 1641 Inst->eraseFromParent(); 1642 1643 // Hey, we just changed something! 1644 MadeChanges = true; 1645 ++NumInstRemoved; 1646 } 1647 } 1648 1649 return MadeChanges; 1650} 1651 1652namespace { 1653 //===--------------------------------------------------------------------===// 1654 // 1655 /// IPSCCP Class - This class implements interprocedural Sparse Conditional 1656 /// Constant Propagation. 1657 /// 1658 struct IPSCCP : public ModulePass { 1659 static char ID; 1660 IPSCCP() : ModulePass(&ID) {} 1661 bool runOnModule(Module &M); 1662 }; 1663} // end anonymous namespace 1664 1665char IPSCCP::ID = 0; 1666static RegisterPass<IPSCCP> 1667Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation"); 1668 1669// createIPSCCPPass - This is the public interface to this file. 1670ModulePass *llvm::createIPSCCPPass() { 1671 return new IPSCCP(); 1672} 1673 1674 1675static bool AddressIsTaken(GlobalValue *GV) { 1676 // Delete any dead constantexpr klingons. 1677 GV->removeDeadConstantUsers(); 1678 1679 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 1680 UI != E; ++UI) 1681 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 1682 if (SI->getOperand(0) == GV || SI->isVolatile()) 1683 return true; // Storing addr of GV. 1684 } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) { 1685 // Make sure we are calling the function, not passing the address. 1686 if (UI.getOperandNo() != 0) 1687 return true; 1688 } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 1689 if (LI->isVolatile()) 1690 return true; 1691 } else if (isa<BlockAddress>(*UI)) { 1692 // blockaddress doesn't take the address of the function, it takes addr 1693 // of label. 1694 } else { 1695 return true; 1696 } 1697 return false; 1698} 1699 1700bool IPSCCP::runOnModule(Module &M) { 1701 SCCPSolver Solver; 1702 1703 // Loop over all functions, marking arguments to those with their addresses 1704 // taken or that are external as overdefined. 1705 // 1706 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 1707 if (!F->hasLocalLinkage() || AddressIsTaken(F)) { 1708 if (!F->isDeclaration()) 1709 Solver.MarkBlockExecutable(F->begin()); 1710 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1711 AI != E; ++AI) 1712 Solver.markOverdefined(AI); 1713 } else { 1714 Solver.AddTrackedFunction(F); 1715 } 1716 1717 // Loop over global variables. We inform the solver about any internal global 1718 // variables that do not have their 'addresses taken'. If they don't have 1719 // their addresses taken, we can propagate constants through them. 1720 for (Module::global_iterator G = M.global_begin(), E = M.global_end(); 1721 G != E; ++G) 1722 if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G)) 1723 Solver.TrackValueOfGlobalVariable(G); 1724 1725 // Solve for constants. 1726 bool ResolvedUndefs = true; 1727 while (ResolvedUndefs) { 1728 Solver.Solve(); 1729 1730 DEBUG(errs() << "RESOLVING UNDEFS\n"); 1731 ResolvedUndefs = false; 1732 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 1733 ResolvedUndefs |= Solver.ResolvedUndefsIn(*F); 1734 } 1735 1736 bool MadeChanges = false; 1737 1738 // Iterate over all of the instructions in the module, replacing them with 1739 // constants if we have found them to be of constant values. 1740 // 1741 SmallVector<Instruction*, 512> Insts; 1742 SmallVector<BasicBlock*, 512> BlocksToErase; 1743 std::map<Value*, LatticeVal> &Values = Solver.getValueMapping(); 1744 1745 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 1746 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 1747 AI != E; ++AI) 1748 if (!AI->use_empty()) { 1749 LatticeVal &IV = Values[AI]; 1750 if (IV.isConstant() || IV.isUndefined()) { 1751 Constant *CST = IV.isConstant() ? 1752 IV.getConstant() : UndefValue::get(AI->getType()); 1753 DEBUG(errs() << "*** Arg " << *AI << " = " << *CST <<"\n"); 1754 1755 // Replaces all of the uses of a variable with uses of the 1756 // constant. 1757 AI->replaceAllUsesWith(CST); 1758 ++IPNumArgsElimed; 1759 } 1760 } 1761 1762 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 1763 if (!Solver.isBlockExecutable(BB)) { 1764 DEBUG(errs() << " BasicBlock Dead:" << *BB); 1765 ++IPNumDeadBlocks; 1766 1767 // Delete the instructions backwards, as it has a reduced likelihood of 1768 // having to update as many def-use and use-def chains. 1769 TerminatorInst *TI = BB->getTerminator(); 1770 for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I) 1771 Insts.push_back(I); 1772 1773 while (!Insts.empty()) { 1774 Instruction *I = Insts.back(); 1775 Insts.pop_back(); 1776 if (!I->use_empty()) 1777 I->replaceAllUsesWith(UndefValue::get(I->getType())); 1778 BB->getInstList().erase(I); 1779 MadeChanges = true; 1780 ++IPNumInstRemoved; 1781 } 1782 1783 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 1784 BasicBlock *Succ = TI->getSuccessor(i); 1785 if (!Succ->empty() && isa<PHINode>(Succ->begin())) 1786 TI->getSuccessor(i)->removePredecessor(BB); 1787 } 1788 if (!TI->use_empty()) 1789 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 1790 BB->getInstList().erase(TI); 1791 1792 if (&*BB != &F->front()) 1793 BlocksToErase.push_back(BB); 1794 else 1795 new UnreachableInst(M.getContext(), BB); 1796 1797 } else { 1798 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 1799 Instruction *Inst = BI++; 1800 if (Inst->getType()->isVoidTy()) 1801 continue; 1802 1803 LatticeVal &IV = Values[Inst]; 1804 if (!IV.isConstant() && !IV.isUndefined()) 1805 continue; 1806 1807 Constant *Const = IV.isConstant() 1808 ? IV.getConstant() : UndefValue::get(Inst->getType()); 1809 DEBUG(errs() << " Constant: " << *Const << " = " << *Inst); 1810 1811 // Replaces all of the uses of a variable with uses of the 1812 // constant. 1813 Inst->replaceAllUsesWith(Const); 1814 1815 // Delete the instruction. 1816 if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst)) 1817 Inst->eraseFromParent(); 1818 1819 // Hey, we just changed something! 1820 MadeChanges = true; 1821 ++IPNumInstRemoved; 1822 } 1823 } 1824 1825 // Now that all instructions in the function are constant folded, erase dead 1826 // blocks, because we can now use ConstantFoldTerminator to get rid of 1827 // in-edges. 1828 for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) { 1829 // If there are any PHI nodes in this successor, drop entries for BB now. 1830 BasicBlock *DeadBB = BlocksToErase[i]; 1831 while (!DeadBB->use_empty()) { 1832 Instruction *I = cast<Instruction>(DeadBB->use_back()); 1833 bool Folded = ConstantFoldTerminator(I->getParent()); 1834 if (!Folded) { 1835 // The constant folder may not have been able to fold the terminator 1836 // if this is a branch or switch on undef. Fold it manually as a 1837 // branch to the first successor. 1838#ifndef NDEBUG 1839 if (BranchInst *BI = dyn_cast<BranchInst>(I)) { 1840 assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) && 1841 "Branch should be foldable!"); 1842 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { 1843 assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold"); 1844 } else { 1845 llvm_unreachable("Didn't fold away reference to block!"); 1846 } 1847#endif 1848 1849 // Make this an uncond branch to the first successor. 1850 TerminatorInst *TI = I->getParent()->getTerminator(); 1851 BranchInst::Create(TI->getSuccessor(0), TI); 1852 1853 // Remove entries in successor phi nodes to remove edges. 1854 for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i) 1855 TI->getSuccessor(i)->removePredecessor(TI->getParent()); 1856 1857 // Remove the old terminator. 1858 TI->eraseFromParent(); 1859 } 1860 } 1861 1862 // Finally, delete the basic block. 1863 F->getBasicBlockList().erase(DeadBB); 1864 } 1865 BlocksToErase.clear(); 1866 } 1867 1868 // If we inferred constant or undef return values for a function, we replaced 1869 // all call uses with the inferred value. This means we don't need to bother 1870 // actually returning anything from the function. Replace all return 1871 // instructions with return undef. 1872 // TODO: Process multiple value ret instructions also. 1873 const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals(); 1874 for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(), 1875 E = RV.end(); I != E; ++I) 1876 if (!I->second.isOverdefined() && 1877 !I->first->getReturnType()->isVoidTy()) { 1878 Function *F = I->first; 1879 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 1880 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 1881 if (!isa<UndefValue>(RI->getOperand(0))) 1882 RI->setOperand(0, UndefValue::get(F->getReturnType())); 1883 } 1884 1885 // If we infered constant or undef values for globals variables, we can delete 1886 // the global and any stores that remain to it. 1887 const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals(); 1888 for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(), 1889 E = TG.end(); I != E; ++I) { 1890 GlobalVariable *GV = I->first; 1891 assert(!I->second.isOverdefined() && 1892 "Overdefined values should have been taken out of the map!"); 1893 DEBUG(errs() << "Found that GV '" << GV->getName() << "' is constant!\n"); 1894 while (!GV->use_empty()) { 1895 StoreInst *SI = cast<StoreInst>(GV->use_back()); 1896 SI->eraseFromParent(); 1897 } 1898 M.getGlobalList().erase(GV); 1899 ++IPNumGlobalConst; 1900 } 1901 1902 return MadeChanges; 1903} 1904