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