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