SCCP.cpp revision 15876bb28c9c0983279c30a123c13224648574c1
1//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This 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#include "llvm/Transforms/Scalar.h" 25#include "llvm/Constants.h" 26#include "llvm/Function.h" 27#include "llvm/GlobalVariable.h" 28#include "llvm/Instructions.h" 29#include "llvm/Pass.h" 30#include "llvm/Type.h" 31#include "llvm/Support/InstVisitor.h" 32#include "llvm/Transforms/Utils/Local.h" 33#include "Support/Debug.h" 34#include "Support/hash_map" 35#include "Support/Statistic.h" 36#include "Support/STLExtras.h" 37#include <algorithm> 38#include <set> 39using namespace llvm; 40 41// InstVal class - This class represents the different lattice values that an 42// instruction may occupy. It is a simple class with value semantics. 43// 44namespace { 45 Statistic<> NumInstRemoved("sccp", "Number of instructions removed"); 46 47class InstVal { 48 enum { 49 undefined, // This instruction has no known value 50 constant, // This instruction has a constant value 51 overdefined // This instruction has an unknown value 52 } LatticeValue; // The current lattice position 53 Constant *ConstantVal; // If Constant value, the current value 54public: 55 inline InstVal() : LatticeValue(undefined), ConstantVal(0) {} 56 57 // markOverdefined - Return true if this is a new status to be in... 58 inline bool markOverdefined() { 59 if (LatticeValue != overdefined) { 60 LatticeValue = overdefined; 61 return true; 62 } 63 return false; 64 } 65 66 // markConstant - Return true if this is a new status for us... 67 inline bool markConstant(Constant *V) { 68 if (LatticeValue != constant) { 69 LatticeValue = constant; 70 ConstantVal = V; 71 return true; 72 } else { 73 assert(ConstantVal == V && "Marking constant with different value"); 74 } 75 return false; 76 } 77 78 inline bool isUndefined() const { return LatticeValue == undefined; } 79 inline bool isConstant() const { return LatticeValue == constant; } 80 inline bool isOverdefined() const { return LatticeValue == overdefined; } 81 82 inline Constant *getConstant() const { 83 assert(isConstant() && "Cannot get the constant of a non-constant!"); 84 return ConstantVal; 85 } 86}; 87 88} // end anonymous namespace 89 90 91//===----------------------------------------------------------------------===// 92// SCCP Class 93// 94// This class does all of the work of Sparse Conditional Constant Propagation. 95// 96namespace { 97class SCCP : public FunctionPass, public InstVisitor<SCCP> { 98 std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable 99 hash_map<Value*, InstVal> ValueState; // The state each value is in... 100 101 // The reason for two worklists is that overdefined is the lowest state 102 // on the lattice, and moving things to overdefined as fast as possible 103 // makes SCCP converge much faster. 104 // By having a separate worklist, we accomplish this because everything 105 // possibly overdefined will become overdefined at the soonest possible 106 // point. 107 std::vector<Instruction*> OverdefinedInstWorkList;// The overdefined 108 // instruction work list 109 std::vector<Instruction*> InstWorkList;// The instruction work list 110 111 112 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 113 114 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not 115 /// overdefined, despite the fact that the PHI node is overdefined. 116 std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs; 117 118 /// KnownFeasibleEdges - Entries in this set are edges which have already had 119 /// PHI nodes retriggered. 120 typedef std::pair<BasicBlock*,BasicBlock*> Edge; 121 std::set<Edge> KnownFeasibleEdges; 122public: 123 124 // runOnFunction - Run the Sparse Conditional Constant Propagation algorithm, 125 // and return true if the function was modified. 126 // 127 bool runOnFunction(Function &F); 128 129 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 130 AU.setPreservesCFG(); 131 } 132 133 134 //===--------------------------------------------------------------------===// 135 // The implementation of this class 136 // 137private: 138 friend class InstVisitor<SCCP>; // Allow callbacks from visitor 139 140 // markConstant - Make a value be marked as "constant". If the value 141 // is not already a constant, add it to the instruction work list so that 142 // the users of the instruction are updated later. 143 // 144 inline void markConstant(InstVal &IV, Instruction *I, Constant *C) { 145 if (IV.markConstant(C)) { 146 DEBUG(std::cerr << "markConstant: " << *C << ": " << *I); 147 InstWorkList.push_back(I); 148 } 149 } 150 inline void markConstant(Instruction *I, Constant *C) { 151 markConstant(ValueState[I], I, C); 152 } 153 154 // markOverdefined - Make a value be marked as "overdefined". If the 155 // value is not already overdefined, add it to the overdefined instruction 156 // work list so that the users of the instruction are updated later. 157 158 inline void markOverdefined(InstVal &IV, Instruction *I) { 159 if (IV.markOverdefined()) { 160 DEBUG(std::cerr << "markOverdefined: " << *I); 161 OverdefinedInstWorkList.push_back(I); // Only instructions go on the work list 162 } 163 } 164 inline void markOverdefined(Instruction *I) { 165 markOverdefined(ValueState[I], I); 166 } 167 168 // getValueState - Return the InstVal object that corresponds to the value. 169 // This function is necessary because not all values should start out in the 170 // underdefined state... Argument's should be overdefined, and 171 // constants should be marked as constants. If a value is not known to be an 172 // Instruction object, then use this accessor to get its value from the map. 173 // 174 inline InstVal &getValueState(Value *V) { 175 hash_map<Value*, InstVal>::iterator I = ValueState.find(V); 176 if (I != ValueState.end()) return I->second; // Common case, in the map 177 178 if (Constant *CPV = dyn_cast<Constant>(V)) { // Constants are constant 179 ValueState[CPV].markConstant(CPV); 180 } else if (isa<Argument>(V)) { // Arguments are overdefined 181 ValueState[V].markOverdefined(); 182 } 183 // All others are underdefined by default... 184 return ValueState[V]; 185 } 186 187 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB 188 // work list if it is not already executable... 189 // 190 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 191 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 192 return; // This edge is already known to be executable! 193 194 if (BBExecutable.count(Dest)) { 195 DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName() 196 << " -> " << Dest->getName() << "\n"); 197 198 // The destination is already executable, but we just made an edge 199 // feasible that wasn't before. Revisit the PHI nodes in the block 200 // because they have potentially new operands. 201 for (BasicBlock::iterator I = Dest->begin(); 202 PHINode *PN = dyn_cast<PHINode>(I); ++I) 203 visitPHINode(*PN); 204 205 } else { 206 DEBUG(std::cerr << "Marking Block Executable: " << Dest->getName()<<"\n"); 207 BBExecutable.insert(Dest); // Basic block is executable! 208 BBWorkList.push_back(Dest); // Add the block to the work list! 209 } 210 } 211 212 213 // visit implementations - Something changed in this instruction... Either an 214 // operand made a transition, or the instruction is newly executable. Change 215 // the value type of I to reflect these changes if appropriate. 216 // 217 void visitPHINode(PHINode &I); 218 219 // Terminators 220 void visitReturnInst(ReturnInst &I) { /*does not have an effect*/ } 221 void visitTerminatorInst(TerminatorInst &TI); 222 223 void visitCastInst(CastInst &I); 224 void visitSelectInst(SelectInst &I); 225 void visitBinaryOperator(Instruction &I); 226 void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); } 227 228 // Instructions that cannot be folded away... 229 void visitStoreInst (Instruction &I) { /*returns void*/ } 230 void visitLoadInst (LoadInst &I); 231 void visitGetElementPtrInst(GetElementPtrInst &I); 232 void visitCallInst (CallInst &I); 233 void visitInvokeInst (TerminatorInst &I) { 234 if (I.getType() != Type::VoidTy) markOverdefined(&I); 235 visitTerminatorInst(I); 236 } 237 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ } 238 void visitAllocationInst(Instruction &I) { markOverdefined(&I); } 239 void visitVANextInst (Instruction &I) { markOverdefined(&I); } 240 void visitVAArgInst (Instruction &I) { markOverdefined(&I); } 241 void visitFreeInst (Instruction &I) { /*returns void*/ } 242 243 void visitInstruction(Instruction &I) { 244 // If a new instruction is added to LLVM that we don't handle... 245 std::cerr << "SCCP: Don't know how to handle: " << I; 246 markOverdefined(&I); // Just in case 247 } 248 249 // getFeasibleSuccessors - Return a vector of booleans to indicate which 250 // successors are reachable from a given terminator instruction. 251 // 252 void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs); 253 254 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic 255 // block to the 'To' basic block is currently feasible... 256 // 257 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); 258 259 // OperandChangedState - This method is invoked on all of the users of an 260 // instruction that was just changed state somehow.... Based on this 261 // information, we need to update the specified user of this instruction. 262 // 263 void OperandChangedState(User *U) { 264 // Only instructions use other variable values! 265 Instruction &I = cast<Instruction>(*U); 266 if (BBExecutable.count(I.getParent())) // Inst is executable? 267 visit(I); 268 } 269}; 270 271 RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation"); 272} // end anonymous namespace 273 274 275// createSCCPPass - This is the public interface to this file... 276Pass *llvm::createSCCPPass() { 277 return new SCCP(); 278} 279 280 281//===----------------------------------------------------------------------===// 282// SCCP Class Implementation 283 284 285// runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm, 286// and return true if the function was modified. 287// 288bool SCCP::runOnFunction(Function &F) { 289 // Mark the first block of the function as being executable... 290 BBExecutable.insert(F.begin()); // Basic block is executable! 291 BBWorkList.push_back(F.begin()); // Add the block to the work list! 292 293 // Process the work lists until they are empty! 294 while (!BBWorkList.empty() || !InstWorkList.empty() || 295 !OverdefinedInstWorkList.empty()) { 296 // Process the instruction work list... 297 while (!OverdefinedInstWorkList.empty()) { 298 Instruction *I = OverdefinedInstWorkList.back(); 299 OverdefinedInstWorkList.pop_back(); 300 301 DEBUG(std::cerr << "\nPopped off OI-WL: " << I); 302 303 // "I" got into the work list because it either made the transition from 304 // bottom to constant 305 // 306 // Anything on this worklist that is overdefined need not be visited 307 // since all of its users will have already been marked as overdefined 308 // Update all of the users of this instruction's value... 309 // 310 for_each(I->use_begin(), I->use_end(), 311 bind_obj(this, &SCCP::OperandChangedState)); 312 } 313 // Process the instruction work list... 314 while (!InstWorkList.empty()) { 315 Instruction *I = InstWorkList.back(); 316 InstWorkList.pop_back(); 317 318 DEBUG(std::cerr << "\nPopped off I-WL: " << *I); 319 320 // "I" got into the work list because it either made the transition from 321 // bottom to constant 322 // 323 // Anything on this worklist that is overdefined need not be visited 324 // since all of its users will have already been marked as overdefined. 325 // Update all of the users of this instruction's value... 326 // 327 InstVal &Ival = getValueState (I); 328 if (!Ival.isOverdefined()) 329 for_each(I->use_begin(), I->use_end(), 330 bind_obj(this, &SCCP::OperandChangedState)); 331 } 332 333 // Process the basic block work list... 334 while (!BBWorkList.empty()) { 335 BasicBlock *BB = BBWorkList.back(); 336 BBWorkList.pop_back(); 337 338 DEBUG(std::cerr << "\nPopped off BBWL: " << *BB); 339 340 // Notify all instructions in this basic block that they are newly 341 // executable. 342 visit(BB); 343 } 344 } 345 346 if (DebugFlag) { 347 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 348 if (!BBExecutable.count(I)) 349 std::cerr << "BasicBlock Dead:" << *I; 350 } 351 352 // Iterate over all of the instructions in a function, replacing them with 353 // constants if we have found them to be of constant values. 354 // 355 bool MadeChanges = false; 356 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) 357 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) { 358 Instruction &Inst = *BI; 359 InstVal &IV = ValueState[&Inst]; 360 if (IV.isConstant()) { 361 Constant *Const = IV.getConstant(); 362 DEBUG(std::cerr << "Constant: " << *Const << " = " << Inst); 363 364 // Replaces all of the uses of a variable with uses of the constant. 365 Inst.replaceAllUsesWith(Const); 366 367 // Remove the operator from the list of definitions... and delete it. 368 BI = BB->getInstList().erase(BI); 369 370 // Hey, we just changed something! 371 MadeChanges = true; 372 ++NumInstRemoved; 373 } else { 374 ++BI; 375 } 376 } 377 378 // Reset state so that the next invocation will have empty data structures 379 BBExecutable.clear(); 380 ValueState.clear(); 381 std::vector<Instruction*>().swap(OverdefinedInstWorkList); 382 std::vector<Instruction*>().swap(InstWorkList); 383 std::vector<BasicBlock*>().swap(BBWorkList); 384 385 return MadeChanges; 386} 387 388 389// getFeasibleSuccessors - Return a vector of booleans to indicate which 390// successors are reachable from a given terminator instruction. 391// 392void SCCP::getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs) { 393 Succs.resize(TI.getNumSuccessors()); 394 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 395 if (BI->isUnconditional()) { 396 Succs[0] = true; 397 } else { 398 InstVal &BCValue = getValueState(BI->getCondition()); 399 if (BCValue.isOverdefined() || 400 (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) { 401 // Overdefined condition variables, and branches on unfoldable constant 402 // conditions, mean the branch could go either way. 403 Succs[0] = Succs[1] = true; 404 } else if (BCValue.isConstant()) { 405 // Constant condition variables mean the branch can only go a single way 406 Succs[BCValue.getConstant() == ConstantBool::False] = true; 407 } 408 } 409 } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) { 410 // Invoke instructions successors are always executable. 411 Succs[0] = Succs[1] = true; 412 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) { 413 InstVal &SCValue = getValueState(SI->getCondition()); 414 if (SCValue.isOverdefined() || // Overdefined condition? 415 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) { 416 // All destinations are executable! 417 Succs.assign(TI.getNumSuccessors(), true); 418 } else if (SCValue.isConstant()) { 419 Constant *CPV = SCValue.getConstant(); 420 // Make sure to skip the "default value" which isn't a value 421 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) { 422 if (SI->getSuccessorValue(i) == CPV) {// Found the right branch... 423 Succs[i] = true; 424 return; 425 } 426 } 427 428 // Constant value not equal to any of the branches... must execute 429 // default branch then... 430 Succs[0] = true; 431 } 432 } else { 433 std::cerr << "SCCP: Don't know how to handle: " << TI; 434 Succs.assign(TI.getNumSuccessors(), true); 435 } 436} 437 438 439// isEdgeFeasible - Return true if the control flow edge from the 'From' basic 440// block to the 'To' basic block is currently feasible... 441// 442bool SCCP::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { 443 assert(BBExecutable.count(To) && "Dest should always be alive!"); 444 445 // Make sure the source basic block is executable!! 446 if (!BBExecutable.count(From)) return false; 447 448 // Check to make sure this edge itself is actually feasible now... 449 TerminatorInst *TI = From->getTerminator(); 450 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 451 if (BI->isUnconditional()) 452 return true; 453 else { 454 InstVal &BCValue = getValueState(BI->getCondition()); 455 if (BCValue.isOverdefined()) { 456 // Overdefined condition variables mean the branch could go either way. 457 return true; 458 } else if (BCValue.isConstant()) { 459 // Not branching on an evaluatable constant? 460 if (!isa<ConstantBool>(BCValue.getConstant())) return true; 461 462 // Constant condition variables mean the branch can only go a single way 463 return BI->getSuccessor(BCValue.getConstant() == 464 ConstantBool::False) == To; 465 } 466 return false; 467 } 468 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 469 // Invoke instructions successors are always executable. 470 return true; 471 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 472 InstVal &SCValue = getValueState(SI->getCondition()); 473 if (SCValue.isOverdefined()) { // Overdefined condition? 474 // All destinations are executable! 475 return true; 476 } else if (SCValue.isConstant()) { 477 Constant *CPV = SCValue.getConstant(); 478 if (!isa<ConstantInt>(CPV)) 479 return true; // not a foldable constant? 480 481 // Make sure to skip the "default value" which isn't a value 482 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) 483 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch... 484 return SI->getSuccessor(i) == To; 485 486 // Constant value not equal to any of the branches... must execute 487 // default branch then... 488 return SI->getDefaultDest() == To; 489 } 490 return false; 491 } else { 492 std::cerr << "Unknown terminator instruction: " << *TI; 493 abort(); 494 } 495} 496 497// visit Implementations - Something changed in this instruction... Either an 498// operand made a transition, or the instruction is newly executable. Change 499// the value type of I to reflect these changes if appropriate. This method 500// makes sure to do the following actions: 501// 502// 1. If a phi node merges two constants in, and has conflicting value coming 503// from different branches, or if the PHI node merges in an overdefined 504// value, then the PHI node becomes overdefined. 505// 2. If a phi node merges only constants in, and they all agree on value, the 506// PHI node becomes a constant value equal to that. 507// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant 508// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined 509// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined 510// 6. If a conditional branch has a value that is constant, make the selected 511// destination executable 512// 7. If a conditional branch has a value that is overdefined, make all 513// successors executable. 514// 515void SCCP::visitPHINode(PHINode &PN) { 516 InstVal &PNIV = getValueState(&PN); 517 if (PNIV.isOverdefined()) { 518 // There may be instructions using this PHI node that are not overdefined 519 // themselves. If so, make sure that they know that the PHI node operand 520 // changed. 521 std::multimap<PHINode*, Instruction*>::iterator I, E; 522 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN); 523 if (I != E) { 524 std::vector<Instruction*> Users; 525 Users.reserve(std::distance(I, E)); 526 for (; I != E; ++I) Users.push_back(I->second); 527 while (!Users.empty()) { 528 visit(Users.back()); 529 Users.pop_back(); 530 } 531 } 532 return; // Quick exit 533 } 534 535 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, 536 // and slow us down a lot. Just mark them overdefined. 537 if (PN.getNumIncomingValues() > 64) { 538 markOverdefined(PNIV, &PN); 539 return; 540 } 541 542 // Look at all of the executable operands of the PHI node. If any of them 543 // are overdefined, the PHI becomes overdefined as well. If they are all 544 // constant, and they agree with each other, the PHI becomes the identical 545 // constant. If they are constant and don't agree, the PHI is overdefined. 546 // If there are no executable operands, the PHI remains undefined. 547 // 548 Constant *OperandVal = 0; 549 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 550 InstVal &IV = getValueState(PN.getIncomingValue(i)); 551 if (IV.isUndefined()) continue; // Doesn't influence PHI node. 552 553 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) { 554 if (IV.isOverdefined()) { // PHI node becomes overdefined! 555 markOverdefined(PNIV, &PN); 556 return; 557 } 558 559 if (OperandVal == 0) { // Grab the first value... 560 OperandVal = IV.getConstant(); 561 } else { // Another value is being merged in! 562 // There is already a reachable operand. If we conflict with it, 563 // then the PHI node becomes overdefined. If we agree with it, we 564 // can continue on. 565 566 // Check to see if there are two different constants merging... 567 if (IV.getConstant() != OperandVal) { 568 // Yes there is. This means the PHI node is not constant. 569 // You must be overdefined poor PHI. 570 // 571 markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined 572 return; // I'm done analyzing you 573 } 574 } 575 } 576 } 577 578 // If we exited the loop, this means that the PHI node only has constant 579 // arguments that agree with each other(and OperandVal is the constant) or 580 // OperandVal is null because there are no defined incoming arguments. If 581 // this is the case, the PHI remains undefined. 582 // 583 if (OperandVal) 584 markConstant(PNIV, &PN, OperandVal); // Acquire operand value 585} 586 587void SCCP::visitTerminatorInst(TerminatorInst &TI) { 588 std::vector<bool> SuccFeasible; 589 getFeasibleSuccessors(TI, SuccFeasible); 590 591 BasicBlock *BB = TI.getParent(); 592 593 // Mark all feasible successors executable... 594 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 595 if (SuccFeasible[i]) 596 markEdgeExecutable(BB, TI.getSuccessor(i)); 597} 598 599void SCCP::visitCastInst(CastInst &I) { 600 Value *V = I.getOperand(0); 601 InstVal &VState = getValueState(V); 602 if (VState.isOverdefined()) // Inherit overdefinedness of operand 603 markOverdefined(&I); 604 else if (VState.isConstant()) // Propagate constant value 605 markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType())); 606} 607 608void SCCP::visitSelectInst(SelectInst &I) { 609 InstVal &CondValue = getValueState(I.getCondition()); 610 if (CondValue.isOverdefined()) 611 markOverdefined(&I); 612 else if (CondValue.isConstant()) { 613 if (CondValue.getConstant() == ConstantBool::True) { 614 InstVal &Val = getValueState(I.getTrueValue()); 615 if (Val.isOverdefined()) 616 markOverdefined(&I); 617 else if (Val.isConstant()) 618 markConstant(&I, Val.getConstant()); 619 } else if (CondValue.getConstant() == ConstantBool::False) { 620 InstVal &Val = getValueState(I.getFalseValue()); 621 if (Val.isOverdefined()) 622 markOverdefined(&I); 623 else if (Val.isConstant()) 624 markConstant(&I, Val.getConstant()); 625 } else 626 markOverdefined(&I); 627 } 628} 629 630// Handle BinaryOperators and Shift Instructions... 631void SCCP::visitBinaryOperator(Instruction &I) { 632 InstVal &IV = ValueState[&I]; 633 if (IV.isOverdefined()) return; 634 635 InstVal &V1State = getValueState(I.getOperand(0)); 636 InstVal &V2State = getValueState(I.getOperand(1)); 637 638 if (V1State.isOverdefined() || V2State.isOverdefined()) { 639 // If both operands are PHI nodes, it is possible that this instruction has 640 // a constant value, despite the fact that the PHI node doesn't. Check for 641 // this condition now. 642 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0))) 643 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1))) 644 if (PN1->getParent() == PN2->getParent()) { 645 // Since the two PHI nodes are in the same basic block, they must have 646 // entries for the same predecessors. Walk the predecessor list, and 647 // if all of the incoming values are constants, and the result of 648 // evaluating this expression with all incoming value pairs is the 649 // same, then this expression is a constant even though the PHI node 650 // is not a constant! 651 InstVal Result; 652 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) { 653 InstVal &In1 = getValueState(PN1->getIncomingValue(i)); 654 BasicBlock *InBlock = PN1->getIncomingBlock(i); 655 InstVal &In2 =getValueState(PN2->getIncomingValueForBlock(InBlock)); 656 657 if (In1.isOverdefined() || In2.isOverdefined()) { 658 Result.markOverdefined(); 659 break; // Cannot fold this operation over the PHI nodes! 660 } else if (In1.isConstant() && In2.isConstant()) { 661 Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(), 662 In2.getConstant()); 663 if (Result.isUndefined()) 664 Result.markConstant(V); 665 else if (Result.isConstant() && Result.getConstant() != V) { 666 Result.markOverdefined(); 667 break; 668 } 669 } 670 } 671 672 // If we found a constant value here, then we know the instruction is 673 // constant despite the fact that the PHI nodes are overdefined. 674 if (Result.isConstant()) { 675 markConstant(IV, &I, Result.getConstant()); 676 // Remember that this instruction is virtually using the PHI node 677 // operands. 678 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I)); 679 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I)); 680 return; 681 } else if (Result.isUndefined()) { 682 return; 683 } 684 685 // Okay, this really is overdefined now. Since we might have 686 // speculatively thought that this was not overdefined before, and 687 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs, 688 // make sure to clean out any entries that we put there, for 689 // efficiency. 690 std::multimap<PHINode*, Instruction*>::iterator It, E; 691 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1); 692 while (It != E) { 693 if (It->second == &I) { 694 UsersOfOverdefinedPHIs.erase(It++); 695 } else 696 ++It; 697 } 698 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2); 699 while (It != E) { 700 if (It->second == &I) { 701 UsersOfOverdefinedPHIs.erase(It++); 702 } else 703 ++It; 704 } 705 } 706 707 markOverdefined(IV, &I); 708 } else if (V1State.isConstant() && V2State.isConstant()) { 709 markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(), 710 V2State.getConstant())); 711 } 712} 713 714// Handle getelementptr instructions... if all operands are constants then we 715// can turn this into a getelementptr ConstantExpr. 716// 717void SCCP::visitGetElementPtrInst(GetElementPtrInst &I) { 718 InstVal &IV = ValueState[&I]; 719 if (IV.isOverdefined()) return; 720 721 std::vector<Constant*> Operands; 722 Operands.reserve(I.getNumOperands()); 723 724 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 725 InstVal &State = getValueState(I.getOperand(i)); 726 if (State.isUndefined()) 727 return; // Operands are not resolved yet... 728 else if (State.isOverdefined()) { 729 markOverdefined(IV, &I); 730 return; 731 } 732 assert(State.isConstant() && "Unknown state!"); 733 Operands.push_back(State.getConstant()); 734 } 735 736 Constant *Ptr = Operands[0]; 737 Operands.erase(Operands.begin()); // Erase the pointer from idx list... 738 739 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands)); 740} 741 742/// GetGEPGlobalInitializer - Given a constant and a getelementptr constantexpr, 743/// return the constant value being addressed by the constant expression, or 744/// null if something is funny. 745/// 746static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) { 747 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 748 return 0; // Do not allow stepping over the value! 749 750 // Loop over all of the operands, tracking down which value we are 751 // addressing... 752 for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i) 753 if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) { 754 ConstantStruct *CS = dyn_cast<ConstantStruct>(C); 755 if (CS == 0) return 0; 756 if (CU->getValue() >= CS->getNumOperands()) return 0; 757 C = CS->getOperand(CU->getValue()); 758 } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) { 759 ConstantArray *CA = dyn_cast<ConstantArray>(C); 760 if (CA == 0) return 0; 761 if ((uint64_t)CS->getValue() >= CA->getNumOperands()) return 0; 762 C = CA->getOperand(CS->getValue()); 763 } else 764 return 0; 765 return C; 766} 767 768// Handle load instructions. If the operand is a constant pointer to a constant 769// global, we can replace the load with the loaded constant value! 770void SCCP::visitLoadInst(LoadInst &I) { 771 InstVal &IV = ValueState[&I]; 772 if (IV.isOverdefined()) return; 773 774 InstVal &PtrVal = getValueState(I.getOperand(0)); 775 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet! 776 if (PtrVal.isConstant() && !I.isVolatile()) { 777 Value *Ptr = PtrVal.getConstant(); 778 if (isa<ConstantPointerNull>(Ptr)) { 779 // load null -> null 780 markConstant(IV, &I, Constant::getNullValue(I.getType())); 781 return; 782 } 783 784 // Transform load (constant global) into the value loaded. 785 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) 786 if (GV->isConstant() && !GV->isExternal()) { 787 markConstant(IV, &I, GV->getInitializer()); 788 return; 789 } 790 791 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded. 792 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 793 if (CE->getOpcode() == Instruction::GetElementPtr) 794 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 795 if (GV->isConstant() && !GV->isExternal()) 796 if (Constant *V = 797 GetGEPGlobalInitializer(GV->getInitializer(), CE)) { 798 markConstant(IV, &I, V); 799 return; 800 } 801 } 802 803 // Otherwise we cannot say for certain what value this load will produce. 804 // Bail out. 805 markOverdefined(IV, &I); 806} 807 808void SCCP::visitCallInst(CallInst &I) { 809 InstVal &IV = ValueState[&I]; 810 if (IV.isOverdefined()) return; 811 812 Function *F = I.getCalledFunction(); 813 if (F == 0 || !canConstantFoldCallTo(F)) { 814 markOverdefined(IV, &I); 815 return; 816 } 817 818 std::vector<Constant*> Operands; 819 Operands.reserve(I.getNumOperands()-1); 820 821 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 822 InstVal &State = getValueState(I.getOperand(i)); 823 if (State.isUndefined()) 824 return; // Operands are not resolved yet... 825 else if (State.isOverdefined()) { 826 markOverdefined(IV, &I); 827 return; 828 } 829 assert(State.isConstant() && "Unknown state!"); 830 Operands.push_back(State.getConstant()); 831 } 832 833 if (Constant *C = ConstantFoldCall(F, Operands)) 834 markConstant(IV, &I, C); 835 else 836 markOverdefined(IV, &I); 837} 838