1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file implements sparse conditional constant propagation and merging:
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
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.
22 //===----------------------------------------------------------------------===//
24 #define DEBUG_TYPE "sccp"
25 #include "llvm/Transforms/Scalar.h"
26 #include "llvm/Constants.h"
27 #include "llvm/Function.h"
28 #include "llvm/GlobalVariable.h"
29 #include "llvm/Instructions.h"
30 #include "llvm/Pass.h"
31 #include "llvm/Type.h"
32 #include "llvm/Support/InstVisitor.h"
33 #include "llvm/Transforms/Utils/Local.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/ADT/hash_map"
36 #include "llvm/ADT/Statistic.h"
37 #include "llvm/ADT/STLExtras.h"
42 // LatticeVal class - This class represents the different lattice values that an
43 // instruction may occupy. It is a simple class with value semantics.
46 Statistic<> NumInstRemoved("sccp", "Number of instructions removed");
50 undefined, // This instruction has no known value
51 constant, // This instruction has a constant value
52 overdefined // This instruction has an unknown value
53 } LatticeValue; // The current lattice position
54 Constant *ConstantVal; // If Constant value, the current value
56 inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {}
58 // markOverdefined - Return true if this is a new status to be in...
59 inline bool markOverdefined() {
60 if (LatticeValue != overdefined) {
61 LatticeValue = overdefined;
67 // markConstant - Return true if this is a new status for us...
68 inline bool markConstant(Constant *V) {
69 if (LatticeValue != constant) {
70 LatticeValue = constant;
74 assert(ConstantVal == V && "Marking constant with different value");
79 inline bool isUndefined() const { return LatticeValue == undefined; }
80 inline bool isConstant() const { return LatticeValue == constant; }
81 inline bool isOverdefined() const { return LatticeValue == overdefined; }
83 inline Constant *getConstant() const {
84 assert(isConstant() && "Cannot get the constant of a non-constant!");
89 } // end anonymous namespace
92 //===----------------------------------------------------------------------===//
94 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
95 /// Constant Propagation.
97 class SCCPSolver : public InstVisitor<SCCPSolver> {
98 std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable
99 hash_map<Value*, LatticeVal> ValueState; // The state each value is in...
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
107 std::vector<Instruction*> OverdefinedInstWorkList;// The overdefined
108 // instruction work list
109 std::vector<Instruction*> InstWorkList;// The instruction work list
112 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
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;
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;
124 /// MarkBlockExecutable - This method can be used by clients to mark all of
125 /// the blocks that are known to be intrinsically live in the processed unit.
126 void MarkBlockExecutable(BasicBlock *BB) {
127 DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n");
128 BBExecutable.insert(BB); // Basic block is executable!
129 BBWorkList.push_back(BB); // Add the block to the work list!
132 /// Solve - Solve for constants and executable blocks.
136 /// getExecutableBlocks - Once we have solved for constants, return the set of
137 /// blocks that is known to be executable.
138 std::set<BasicBlock*> &getExecutableBlocks() {
142 /// getValueMapping - Once we have solved for constants, return the mapping of
143 /// LLVM values to LatticeVals.
144 hash_map<Value*, LatticeVal> &getValueMapping() {
149 // markConstant - Make a value be marked as "constant". If the value
150 // is not already a constant, add it to the instruction work list so that
151 // the users of the instruction are updated later.
153 inline void markConstant(LatticeVal &IV, Instruction *I, Constant *C) {
154 if (IV.markConstant(C)) {
155 DEBUG(std::cerr << "markConstant: " << *C << ": " << *I);
156 InstWorkList.push_back(I);
159 inline void markConstant(Instruction *I, Constant *C) {
160 markConstant(ValueState[I], I, C);
163 // markOverdefined - Make a value be marked as "overdefined". If the
164 // value is not already overdefined, add it to the overdefined instruction
165 // work list so that the users of the instruction are updated later.
167 inline void markOverdefined(LatticeVal &IV, Instruction *I) {
168 if (IV.markOverdefined()) {
169 DEBUG(std::cerr << "markOverdefined: " << *I);
170 // Only instructions go on the work list
171 OverdefinedInstWorkList.push_back(I);
174 inline void markOverdefined(Instruction *I) {
175 markOverdefined(ValueState[I], I);
178 // getValueState - Return the LatticeVal object that corresponds to the value.
179 // This function is necessary because not all values should start out in the
180 // underdefined state... Argument's should be overdefined, and
181 // constants should be marked as constants. If a value is not known to be an
182 // Instruction object, then use this accessor to get its value from the map.
184 inline LatticeVal &getValueState(Value *V) {
185 hash_map<Value*, LatticeVal>::iterator I = ValueState.find(V);
186 if (I != ValueState.end()) return I->second; // Common case, in the map
188 if (isa<UndefValue>(V)) {
189 // Nothing to do, remain undefined.
190 } else if (Constant *CPV = dyn_cast<Constant>(V)) {
191 ValueState[CPV].markConstant(CPV); // Constants are constant
192 } else if (isa<Argument>(V)) { // Arguments are overdefined
193 ValueState[V].markOverdefined();
195 // All others are underdefined by default...
196 return ValueState[V];
199 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB
200 // work list if it is not already executable...
202 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
203 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
204 return; // This edge is already known to be executable!
206 if (BBExecutable.count(Dest)) {
207 DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName()
208 << " -> " << Dest->getName() << "\n");
210 // The destination is already executable, but we just made an edge
211 // feasible that wasn't before. Revisit the PHI nodes in the block
212 // because they have potentially new operands.
213 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) {
214 PHINode *PN = cast<PHINode>(I);
219 MarkBlockExecutable(Dest);
223 // getFeasibleSuccessors - Return a vector of booleans to indicate which
224 // successors are reachable from a given terminator instruction.
226 void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs);
228 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
229 // block to the 'To' basic block is currently feasible...
231 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
233 // OperandChangedState - This method is invoked on all of the users of an
234 // instruction that was just changed state somehow.... Based on this
235 // information, we need to update the specified user of this instruction.
237 void OperandChangedState(User *U) {
238 // Only instructions use other variable values!
239 Instruction &I = cast<Instruction>(*U);
240 if (BBExecutable.count(I.getParent())) // Inst is executable?
245 friend class InstVisitor<SCCPSolver>;
247 // visit implementations - Something changed in this instruction... Either an
248 // operand made a transition, or the instruction is newly executable. Change
249 // the value type of I to reflect these changes if appropriate.
251 void visitPHINode(PHINode &I);
254 void visitReturnInst(ReturnInst &I) { /*does not have an effect*/ }
255 void visitTerminatorInst(TerminatorInst &TI);
257 void visitCastInst(CastInst &I);
258 void visitSelectInst(SelectInst &I);
259 void visitBinaryOperator(Instruction &I);
260 void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); }
262 // Instructions that cannot be folded away...
263 void visitStoreInst (Instruction &I) { /*returns void*/ }
264 void visitLoadInst (LoadInst &I);
265 void visitGetElementPtrInst(GetElementPtrInst &I);
266 void visitCallInst (CallInst &I);
267 void visitInvokeInst (TerminatorInst &I) {
268 if (I.getType() != Type::VoidTy) markOverdefined(&I);
269 visitTerminatorInst(I);
271 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ }
272 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
273 void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
274 void visitVANextInst (Instruction &I) { markOverdefined(&I); }
275 void visitVAArgInst (Instruction &I) { markOverdefined(&I); }
276 void visitFreeInst (Instruction &I) { /*returns void*/ }
278 void visitInstruction(Instruction &I) {
279 // If a new instruction is added to LLVM that we don't handle...
280 std::cerr << "SCCP: Don't know how to handle: " << I;
281 markOverdefined(&I); // Just in case
285 // getFeasibleSuccessors - Return a vector of booleans to indicate which
286 // successors are reachable from a given terminator instruction.
288 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
289 std::vector<bool> &Succs) {
290 Succs.resize(TI.getNumSuccessors());
291 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
292 if (BI->isUnconditional()) {
295 LatticeVal &BCValue = getValueState(BI->getCondition());
296 if (BCValue.isOverdefined() ||
297 (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) {
298 // Overdefined condition variables, and branches on unfoldable constant
299 // conditions, mean the branch could go either way.
300 Succs[0] = Succs[1] = true;
301 } else if (BCValue.isConstant()) {
302 // Constant condition variables mean the branch can only go a single way
303 Succs[BCValue.getConstant() == ConstantBool::False] = true;
306 } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) {
307 // Invoke instructions successors are always executable.
308 Succs[0] = Succs[1] = true;
309 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
310 LatticeVal &SCValue = getValueState(SI->getCondition());
311 if (SCValue.isOverdefined() || // Overdefined condition?
312 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
313 // All destinations are executable!
314 Succs.assign(TI.getNumSuccessors(), true);
315 } else if (SCValue.isConstant()) {
316 Constant *CPV = SCValue.getConstant();
317 // Make sure to skip the "default value" which isn't a value
318 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
319 if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
325 // Constant value not equal to any of the branches... must execute
326 // default branch then...
330 std::cerr << "SCCP: Don't know how to handle: " << TI;
331 Succs.assign(TI.getNumSuccessors(), true);
336 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
337 // block to the 'To' basic block is currently feasible...
339 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
340 assert(BBExecutable.count(To) && "Dest should always be alive!");
342 // Make sure the source basic block is executable!!
343 if (!BBExecutable.count(From)) return false;
345 // Check to make sure this edge itself is actually feasible now...
346 TerminatorInst *TI = From->getTerminator();
347 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
348 if (BI->isUnconditional())
351 LatticeVal &BCValue = getValueState(BI->getCondition());
352 if (BCValue.isOverdefined()) {
353 // Overdefined condition variables mean the branch could go either way.
355 } else if (BCValue.isConstant()) {
356 // Not branching on an evaluatable constant?
357 if (!isa<ConstantBool>(BCValue.getConstant())) return true;
359 // Constant condition variables mean the branch can only go a single way
360 return BI->getSuccessor(BCValue.getConstant() ==
361 ConstantBool::False) == To;
365 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
366 // Invoke instructions successors are always executable.
368 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
369 LatticeVal &SCValue = getValueState(SI->getCondition());
370 if (SCValue.isOverdefined()) { // Overdefined condition?
371 // All destinations are executable!
373 } else if (SCValue.isConstant()) {
374 Constant *CPV = SCValue.getConstant();
375 if (!isa<ConstantInt>(CPV))
376 return true; // not a foldable constant?
378 // Make sure to skip the "default value" which isn't a value
379 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
380 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch...
381 return SI->getSuccessor(i) == To;
383 // Constant value not equal to any of the branches... must execute
384 // default branch then...
385 return SI->getDefaultDest() == To;
389 std::cerr << "Unknown terminator instruction: " << *TI;
394 // visit Implementations - Something changed in this instruction... Either an
395 // operand made a transition, or the instruction is newly executable. Change
396 // the value type of I to reflect these changes if appropriate. This method
397 // makes sure to do the following actions:
399 // 1. If a phi node merges two constants in, and has conflicting value coming
400 // from different branches, or if the PHI node merges in an overdefined
401 // value, then the PHI node becomes overdefined.
402 // 2. If a phi node merges only constants in, and they all agree on value, the
403 // PHI node becomes a constant value equal to that.
404 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
405 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
406 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
407 // 6. If a conditional branch has a value that is constant, make the selected
408 // destination executable
409 // 7. If a conditional branch has a value that is overdefined, make all
410 // successors executable.
412 void SCCPSolver::visitPHINode(PHINode &PN) {
413 LatticeVal &PNIV = getValueState(&PN);
414 if (PNIV.isOverdefined()) {
415 // There may be instructions using this PHI node that are not overdefined
416 // themselves. If so, make sure that they know that the PHI node operand
418 std::multimap<PHINode*, Instruction*>::iterator I, E;
419 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
421 std::vector<Instruction*> Users;
422 Users.reserve(std::distance(I, E));
423 for (; I != E; ++I) Users.push_back(I->second);
424 while (!Users.empty()) {
429 return; // Quick exit
432 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
433 // and slow us down a lot. Just mark them overdefined.
434 if (PN.getNumIncomingValues() > 64) {
435 markOverdefined(PNIV, &PN);
439 // Look at all of the executable operands of the PHI node. If any of them
440 // are overdefined, the PHI becomes overdefined as well. If they are all
441 // constant, and they agree with each other, the PHI becomes the identical
442 // constant. If they are constant and don't agree, the PHI is overdefined.
443 // If there are no executable operands, the PHI remains undefined.
445 Constant *OperandVal = 0;
446 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
447 LatticeVal &IV = getValueState(PN.getIncomingValue(i));
448 if (IV.isUndefined()) continue; // Doesn't influence PHI node.
450 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
451 if (IV.isOverdefined()) { // PHI node becomes overdefined!
452 markOverdefined(PNIV, &PN);
456 if (OperandVal == 0) { // Grab the first value...
457 OperandVal = IV.getConstant();
458 } else { // Another value is being merged in!
459 // There is already a reachable operand. If we conflict with it,
460 // then the PHI node becomes overdefined. If we agree with it, we
463 // Check to see if there are two different constants merging...
464 if (IV.getConstant() != OperandVal) {
465 // Yes there is. This means the PHI node is not constant.
466 // You must be overdefined poor PHI.
468 markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined
469 return; // I'm done analyzing you
475 // If we exited the loop, this means that the PHI node only has constant
476 // arguments that agree with each other(and OperandVal is the constant) or
477 // OperandVal is null because there are no defined incoming arguments. If
478 // this is the case, the PHI remains undefined.
481 markConstant(PNIV, &PN, OperandVal); // Acquire operand value
484 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
485 std::vector<bool> SuccFeasible;
486 getFeasibleSuccessors(TI, SuccFeasible);
488 BasicBlock *BB = TI.getParent();
490 // Mark all feasible successors executable...
491 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
493 markEdgeExecutable(BB, TI.getSuccessor(i));
496 void SCCPSolver::visitCastInst(CastInst &I) {
497 Value *V = I.getOperand(0);
498 LatticeVal &VState = getValueState(V);
499 if (VState.isOverdefined()) // Inherit overdefinedness of operand
501 else if (VState.isConstant()) // Propagate constant value
502 markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType()));
505 void SCCPSolver::visitSelectInst(SelectInst &I) {
506 LatticeVal &CondValue = getValueState(I.getCondition());
507 if (CondValue.isOverdefined())
509 else if (CondValue.isConstant()) {
510 if (CondValue.getConstant() == ConstantBool::True) {
511 LatticeVal &Val = getValueState(I.getTrueValue());
512 if (Val.isOverdefined())
514 else if (Val.isConstant())
515 markConstant(&I, Val.getConstant());
516 } else if (CondValue.getConstant() == ConstantBool::False) {
517 LatticeVal &Val = getValueState(I.getFalseValue());
518 if (Val.isOverdefined())
520 else if (Val.isConstant())
521 markConstant(&I, Val.getConstant());
527 // Handle BinaryOperators and Shift Instructions...
528 void SCCPSolver::visitBinaryOperator(Instruction &I) {
529 LatticeVal &IV = ValueState[&I];
530 if (IV.isOverdefined()) return;
532 LatticeVal &V1State = getValueState(I.getOperand(0));
533 LatticeVal &V2State = getValueState(I.getOperand(1));
535 if (V1State.isOverdefined() || V2State.isOverdefined()) {
536 // If both operands are PHI nodes, it is possible that this instruction has
537 // a constant value, despite the fact that the PHI node doesn't. Check for
538 // this condition now.
539 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
540 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
541 if (PN1->getParent() == PN2->getParent()) {
542 // Since the two PHI nodes are in the same basic block, they must have
543 // entries for the same predecessors. Walk the predecessor list, and
544 // if all of the incoming values are constants, and the result of
545 // evaluating this expression with all incoming value pairs is the
546 // same, then this expression is a constant even though the PHI node
547 // is not a constant!
549 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
550 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
551 BasicBlock *InBlock = PN1->getIncomingBlock(i);
553 getValueState(PN2->getIncomingValueForBlock(InBlock));
555 if (In1.isOverdefined() || In2.isOverdefined()) {
556 Result.markOverdefined();
557 break; // Cannot fold this operation over the PHI nodes!
558 } else if (In1.isConstant() && In2.isConstant()) {
559 Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
561 if (Result.isUndefined())
562 Result.markConstant(V);
563 else if (Result.isConstant() && Result.getConstant() != V) {
564 Result.markOverdefined();
570 // If we found a constant value here, then we know the instruction is
571 // constant despite the fact that the PHI nodes are overdefined.
572 if (Result.isConstant()) {
573 markConstant(IV, &I, Result.getConstant());
574 // Remember that this instruction is virtually using the PHI node
576 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
577 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
579 } else if (Result.isUndefined()) {
583 // Okay, this really is overdefined now. Since we might have
584 // speculatively thought that this was not overdefined before, and
585 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
586 // make sure to clean out any entries that we put there, for
588 std::multimap<PHINode*, Instruction*>::iterator It, E;
589 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
591 if (It->second == &I) {
592 UsersOfOverdefinedPHIs.erase(It++);
596 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
598 if (It->second == &I) {
599 UsersOfOverdefinedPHIs.erase(It++);
605 markOverdefined(IV, &I);
606 } else if (V1State.isConstant() && V2State.isConstant()) {
607 markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
608 V2State.getConstant()));
612 // Handle getelementptr instructions... if all operands are constants then we
613 // can turn this into a getelementptr ConstantExpr.
615 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
616 LatticeVal &IV = ValueState[&I];
617 if (IV.isOverdefined()) return;
619 std::vector<Constant*> Operands;
620 Operands.reserve(I.getNumOperands());
622 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
623 LatticeVal &State = getValueState(I.getOperand(i));
624 if (State.isUndefined())
625 return; // Operands are not resolved yet...
626 else if (State.isOverdefined()) {
627 markOverdefined(IV, &I);
630 assert(State.isConstant() && "Unknown state!");
631 Operands.push_back(State.getConstant());
634 Constant *Ptr = Operands[0];
635 Operands.erase(Operands.begin()); // Erase the pointer from idx list...
637 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands));
640 /// GetGEPGlobalInitializer - Given a constant and a getelementptr constantexpr,
641 /// return the constant value being addressed by the constant expression, or
642 /// null if something is funny.
644 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
645 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
646 return 0; // Do not allow stepping over the value!
648 // Loop over all of the operands, tracking down which value we are
650 for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
651 if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
652 ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
653 if (CS == 0) return 0;
654 if (CU->getValue() >= CS->getNumOperands()) return 0;
655 C = CS->getOperand(CU->getValue());
656 } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
657 ConstantArray *CA = dyn_cast<ConstantArray>(C);
658 if (CA == 0) return 0;
659 if ((uint64_t)CS->getValue() >= CA->getNumOperands()) return 0;
660 C = CA->getOperand(CS->getValue());
666 // Handle load instructions. If the operand is a constant pointer to a constant
667 // global, we can replace the load with the loaded constant value!
668 void SCCPSolver::visitLoadInst(LoadInst &I) {
669 LatticeVal &IV = ValueState[&I];
670 if (IV.isOverdefined()) return;
672 LatticeVal &PtrVal = getValueState(I.getOperand(0));
673 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet!
674 if (PtrVal.isConstant() && !I.isVolatile()) {
675 Value *Ptr = PtrVal.getConstant();
676 if (isa<ConstantPointerNull>(Ptr)) {
678 markConstant(IV, &I, Constant::getNullValue(I.getType()));
682 // Transform load (constant global) into the value loaded.
683 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr))
684 if (GV->isConstant() && !GV->isExternal()) {
685 markConstant(IV, &I, GV->getInitializer());
689 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
690 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
691 if (CE->getOpcode() == Instruction::GetElementPtr)
692 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
693 if (GV->isConstant() && !GV->isExternal())
695 GetGEPGlobalInitializer(GV->getInitializer(), CE)) {
696 markConstant(IV, &I, V);
701 // Otherwise we cannot say for certain what value this load will produce.
703 markOverdefined(IV, &I);
706 void SCCPSolver::visitCallInst(CallInst &I) {
707 LatticeVal &IV = ValueState[&I];
708 if (IV.isOverdefined()) return;
710 Function *F = I.getCalledFunction();
711 if (F == 0 || !canConstantFoldCallTo(F)) {
712 markOverdefined(IV, &I);
716 std::vector<Constant*> Operands;
717 Operands.reserve(I.getNumOperands()-1);
719 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
720 LatticeVal &State = getValueState(I.getOperand(i));
721 if (State.isUndefined())
722 return; // Operands are not resolved yet...
723 else if (State.isOverdefined()) {
724 markOverdefined(IV, &I);
727 assert(State.isConstant() && "Unknown state!");
728 Operands.push_back(State.getConstant());
731 if (Constant *C = ConstantFoldCall(F, Operands))
732 markConstant(IV, &I, C);
734 markOverdefined(IV, &I);
738 void SCCPSolver::Solve() {
739 // Process the work lists until they are empty!
740 while (!BBWorkList.empty() || !InstWorkList.empty() ||
741 !OverdefinedInstWorkList.empty()) {
742 // Process the instruction work list...
743 while (!OverdefinedInstWorkList.empty()) {
744 Instruction *I = OverdefinedInstWorkList.back();
745 OverdefinedInstWorkList.pop_back();
747 DEBUG(std::cerr << "\nPopped off OI-WL: " << I);
749 // "I" got into the work list because it either made the transition from
750 // bottom to constant
752 // Anything on this worklist that is overdefined need not be visited
753 // since all of its users will have already been marked as overdefined
754 // Update all of the users of this instruction's value...
756 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
758 OperandChangedState(*UI);
760 // Process the instruction work list...
761 while (!InstWorkList.empty()) {
762 Instruction *I = InstWorkList.back();
763 InstWorkList.pop_back();
765 DEBUG(std::cerr << "\nPopped off I-WL: " << *I);
767 // "I" got into the work list because it either made the transition from
768 // bottom to constant
770 // Anything on this worklist that is overdefined need not be visited
771 // since all of its users will have already been marked as overdefined.
772 // Update all of the users of this instruction's value...
774 if (!getValueState(I).isOverdefined())
775 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
777 OperandChangedState(*UI);
780 // Process the basic block work list...
781 while (!BBWorkList.empty()) {
782 BasicBlock *BB = BBWorkList.back();
783 BBWorkList.pop_back();
785 DEBUG(std::cerr << "\nPopped off BBWL: " << *BB);
787 // Notify all instructions in this basic block that they are newly
796 //===----------------------------------------------------------------------===//
798 /// SCCP Class - This class does all of the work of Sparse Conditional Constant
801 class SCCP : public FunctionPass, public InstVisitor<SCCP> {
804 // runOnFunction - Run the Sparse Conditional Constant Propagation algorithm,
805 // and return true if the function was modified.
807 bool runOnFunction(Function &F);
809 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
810 AU.setPreservesCFG();
814 RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation");
815 } // end anonymous namespace
818 // createSCCPPass - This is the public interface to this file...
819 FunctionPass *llvm::createSCCPPass() {
824 //===----------------------------------------------------------------------===//
825 // SCCP Class Implementation
828 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
829 // and return true if the function was modified.
831 bool SCCP::runOnFunction(Function &F) {
834 // Mark the first block of the function as being executable.
835 Solver.MarkBlockExecutable(F.begin());
837 // Solve for constants.
840 DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n");
841 DEBUG(std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
842 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
843 if (!ExecutableBBs.count(I))
844 std::cerr << " BasicBlock Dead:" << *I);
846 // Iterate over all of the instructions in a function, replacing them with
847 // constants if we have found them to be of constant values.
849 bool MadeChanges = false;
850 hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
851 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB)
852 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
853 Instruction *Inst = BI++;
854 if (Inst->getType() != Type::VoidTy) {
855 LatticeVal &IV = Values[Inst];
856 if (IV.isConstant() || IV.isUndefined()) {
858 if (IV.isConstant()) {
859 Const = IV.getConstant();
860 DEBUG(std::cerr << " Constant: " << *Const << " = " << *Inst);
862 Const = UndefValue::get(Inst->getType());
863 DEBUG(std::cerr << " Undefined: " << *Inst);
866 // Replaces all of the uses of a variable with uses of the constant.
867 Inst->replaceAllUsesWith(Const);
869 // Delete the instruction.
870 BB->getInstList().erase(Inst);
872 // Hey, we just changed something!