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");
47 Statistic<> NumDeadBlocks ("sccp", "Number of basic blocks unreachable");
51 undefined, // This instruction has no known value
52 constant, // This instruction has a constant value
53 overdefined // This instruction has an unknown value
54 } LatticeValue; // The current lattice position
55 Constant *ConstantVal; // If Constant value, the current value
57 inline LatticeVal() : LatticeValue(undefined), ConstantVal(0) {}
59 // markOverdefined - Return true if this is a new status to be in...
60 inline bool markOverdefined() {
61 if (LatticeValue != overdefined) {
62 LatticeValue = overdefined;
68 // markConstant - Return true if this is a new status for us...
69 inline bool markConstant(Constant *V) {
70 if (LatticeValue != constant) {
71 LatticeValue = constant;
75 assert(ConstantVal == V && "Marking constant with different value");
80 inline bool isUndefined() const { return LatticeValue == undefined; }
81 inline bool isConstant() const { return LatticeValue == constant; }
82 inline bool isOverdefined() const { return LatticeValue == overdefined; }
84 inline Constant *getConstant() const {
85 assert(isConstant() && "Cannot get the constant of a non-constant!");
90 } // end anonymous namespace
93 //===----------------------------------------------------------------------===//
95 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
96 /// Constant Propagation.
98 class SCCPSolver : public InstVisitor<SCCPSolver> {
99 std::set<BasicBlock*> BBExecutable;// The basic blocks that are executable
100 hash_map<Value*, LatticeVal> ValueState; // The state each value is in...
102 // The reason for two worklists is that overdefined is the lowest state
103 // on the lattice, and moving things to overdefined as fast as possible
104 // makes SCCP converge much faster.
105 // By having a separate worklist, we accomplish this because everything
106 // possibly overdefined will become overdefined at the soonest possible
108 std::vector<Instruction*> OverdefinedInstWorkList;// The overdefined
109 // instruction work list
110 std::vector<Instruction*> InstWorkList;// The instruction work list
113 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
115 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
116 /// overdefined, despite the fact that the PHI node is overdefined.
117 std::multimap<PHINode*, Instruction*> UsersOfOverdefinedPHIs;
119 /// KnownFeasibleEdges - Entries in this set are edges which have already had
120 /// PHI nodes retriggered.
121 typedef std::pair<BasicBlock*,BasicBlock*> Edge;
122 std::set<Edge> KnownFeasibleEdges;
125 /// MarkBlockExecutable - This method can be used by clients to mark all of
126 /// the blocks that are known to be intrinsically live in the processed unit.
127 void MarkBlockExecutable(BasicBlock *BB) {
128 DEBUG(std::cerr << "Marking Block Executable: " << BB->getName() << "\n");
129 BBExecutable.insert(BB); // Basic block is executable!
130 BBWorkList.push_back(BB); // Add the block to the work list!
133 /// Solve - Solve for constants and executable blocks.
137 /// getExecutableBlocks - Once we have solved for constants, return the set of
138 /// blocks that is known to be executable.
139 std::set<BasicBlock*> &getExecutableBlocks() {
143 /// getValueMapping - Once we have solved for constants, return the mapping of
144 /// LLVM values to LatticeVals.
145 hash_map<Value*, LatticeVal> &getValueMapping() {
150 // markConstant - Make a value be marked as "constant". If the value
151 // is not already a constant, add it to the instruction work list so that
152 // the users of the instruction are updated later.
154 inline void markConstant(LatticeVal &IV, Instruction *I, Constant *C) {
155 if (IV.markConstant(C)) {
156 DEBUG(std::cerr << "markConstant: " << *C << ": " << *I);
157 InstWorkList.push_back(I);
160 inline void markConstant(Instruction *I, Constant *C) {
161 markConstant(ValueState[I], I, C);
164 // markOverdefined - Make a value be marked as "overdefined". If the
165 // value is not already overdefined, add it to the overdefined instruction
166 // work list so that the users of the instruction are updated later.
168 inline void markOverdefined(LatticeVal &IV, Instruction *I) {
169 if (IV.markOverdefined()) {
170 DEBUG(std::cerr << "markOverdefined: " << *I);
171 // Only instructions go on the work list
172 OverdefinedInstWorkList.push_back(I);
175 inline void markOverdefined(Instruction *I) {
176 markOverdefined(ValueState[I], I);
179 // getValueState - Return the LatticeVal object that corresponds to the value.
180 // This function is necessary because not all values should start out in the
181 // underdefined state... Argument's should be overdefined, and
182 // constants should be marked as constants. If a value is not known to be an
183 // Instruction object, then use this accessor to get its value from the map.
185 inline LatticeVal &getValueState(Value *V) {
186 hash_map<Value*, LatticeVal>::iterator I = ValueState.find(V);
187 if (I != ValueState.end()) return I->second; // Common case, in the map
189 if (Constant *CPV = dyn_cast<Constant>(V)) {
190 if (isa<UndefValue>(V)) {
191 // Nothing to do, remain undefined.
193 ValueState[CPV].markConstant(CPV); // Constants are constant
196 // All others are underdefined by default...
197 return ValueState[V];
200 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB
201 // work list if it is not already executable...
203 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
204 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
205 return; // This edge is already known to be executable!
207 if (BBExecutable.count(Dest)) {
208 DEBUG(std::cerr << "Marking Edge Executable: " << Source->getName()
209 << " -> " << Dest->getName() << "\n");
211 // The destination is already executable, but we just made an edge
212 // feasible that wasn't before. Revisit the PHI nodes in the block
213 // because they have potentially new operands.
214 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) {
215 PHINode *PN = cast<PHINode>(I);
220 MarkBlockExecutable(Dest);
224 // getFeasibleSuccessors - Return a vector of booleans to indicate which
225 // successors are reachable from a given terminator instruction.
227 void getFeasibleSuccessors(TerminatorInst &TI, std::vector<bool> &Succs);
229 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
230 // block to the 'To' basic block is currently feasible...
232 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
234 // OperandChangedState - This method is invoked on all of the users of an
235 // instruction that was just changed state somehow.... Based on this
236 // information, we need to update the specified user of this instruction.
238 void OperandChangedState(User *U) {
239 // Only instructions use other variable values!
240 Instruction &I = cast<Instruction>(*U);
241 if (BBExecutable.count(I.getParent())) // Inst is executable?
246 friend class InstVisitor<SCCPSolver>;
248 // visit implementations - Something changed in this instruction... Either an
249 // operand made a transition, or the instruction is newly executable. Change
250 // the value type of I to reflect these changes if appropriate.
252 void visitPHINode(PHINode &I);
255 void visitReturnInst(ReturnInst &I) { /*does not have an effect*/ }
256 void visitTerminatorInst(TerminatorInst &TI);
258 void visitCastInst(CastInst &I);
259 void visitSelectInst(SelectInst &I);
260 void visitBinaryOperator(Instruction &I);
261 void visitShiftInst(ShiftInst &I) { visitBinaryOperator(I); }
263 // Instructions that cannot be folded away...
264 void visitStoreInst (Instruction &I) { /*returns void*/ }
265 void visitLoadInst (LoadInst &I);
266 void visitGetElementPtrInst(GetElementPtrInst &I);
267 void visitCallInst (CallInst &I);
268 void visitInvokeInst (TerminatorInst &I) {
269 if (I.getType() != Type::VoidTy) markOverdefined(&I);
270 visitTerminatorInst(I);
272 void visitUnwindInst (TerminatorInst &I) { /*returns void*/ }
273 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
274 void visitAllocationInst(Instruction &I) { markOverdefined(&I); }
275 void visitVANextInst (Instruction &I) { markOverdefined(&I); }
276 void visitVAArgInst (Instruction &I) { markOverdefined(&I); }
277 void visitFreeInst (Instruction &I) { /*returns void*/ }
279 void visitInstruction(Instruction &I) {
280 // If a new instruction is added to LLVM that we don't handle...
281 std::cerr << "SCCP: Don't know how to handle: " << I;
282 markOverdefined(&I); // Just in case
286 // getFeasibleSuccessors - Return a vector of booleans to indicate which
287 // successors are reachable from a given terminator instruction.
289 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
290 std::vector<bool> &Succs) {
291 Succs.resize(TI.getNumSuccessors());
292 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
293 if (BI->isUnconditional()) {
296 LatticeVal &BCValue = getValueState(BI->getCondition());
297 if (BCValue.isOverdefined() ||
298 (BCValue.isConstant() && !isa<ConstantBool>(BCValue.getConstant()))) {
299 // Overdefined condition variables, and branches on unfoldable constant
300 // conditions, mean the branch could go either way.
301 Succs[0] = Succs[1] = true;
302 } else if (BCValue.isConstant()) {
303 // Constant condition variables mean the branch can only go a single way
304 Succs[BCValue.getConstant() == ConstantBool::False] = true;
307 } else if (InvokeInst *II = dyn_cast<InvokeInst>(&TI)) {
308 // Invoke instructions successors are always executable.
309 Succs[0] = Succs[1] = true;
310 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
311 LatticeVal &SCValue = getValueState(SI->getCondition());
312 if (SCValue.isOverdefined() || // Overdefined condition?
313 (SCValue.isConstant() && !isa<ConstantInt>(SCValue.getConstant()))) {
314 // All destinations are executable!
315 Succs.assign(TI.getNumSuccessors(), true);
316 } else if (SCValue.isConstant()) {
317 Constant *CPV = SCValue.getConstant();
318 // Make sure to skip the "default value" which isn't a value
319 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
320 if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
326 // Constant value not equal to any of the branches... must execute
327 // default branch then...
331 std::cerr << "SCCP: Don't know how to handle: " << TI;
332 Succs.assign(TI.getNumSuccessors(), true);
337 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
338 // block to the 'To' basic block is currently feasible...
340 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
341 assert(BBExecutable.count(To) && "Dest should always be alive!");
343 // Make sure the source basic block is executable!!
344 if (!BBExecutable.count(From)) return false;
346 // Check to make sure this edge itself is actually feasible now...
347 TerminatorInst *TI = From->getTerminator();
348 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
349 if (BI->isUnconditional())
352 LatticeVal &BCValue = getValueState(BI->getCondition());
353 if (BCValue.isOverdefined()) {
354 // Overdefined condition variables mean the branch could go either way.
356 } else if (BCValue.isConstant()) {
357 // Not branching on an evaluatable constant?
358 if (!isa<ConstantBool>(BCValue.getConstant())) return true;
360 // Constant condition variables mean the branch can only go a single way
361 return BI->getSuccessor(BCValue.getConstant() ==
362 ConstantBool::False) == To;
366 } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
367 // Invoke instructions successors are always executable.
369 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
370 LatticeVal &SCValue = getValueState(SI->getCondition());
371 if (SCValue.isOverdefined()) { // Overdefined condition?
372 // All destinations are executable!
374 } else if (SCValue.isConstant()) {
375 Constant *CPV = SCValue.getConstant();
376 if (!isa<ConstantInt>(CPV))
377 return true; // not a foldable constant?
379 // Make sure to skip the "default value" which isn't a value
380 for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i)
381 if (SI->getSuccessorValue(i) == CPV) // Found the taken branch...
382 return SI->getSuccessor(i) == To;
384 // Constant value not equal to any of the branches... must execute
385 // default branch then...
386 return SI->getDefaultDest() == To;
390 std::cerr << "Unknown terminator instruction: " << *TI;
395 // visit Implementations - Something changed in this instruction... Either an
396 // operand made a transition, or the instruction is newly executable. Change
397 // the value type of I to reflect these changes if appropriate. This method
398 // makes sure to do the following actions:
400 // 1. If a phi node merges two constants in, and has conflicting value coming
401 // from different branches, or if the PHI node merges in an overdefined
402 // value, then the PHI node becomes overdefined.
403 // 2. If a phi node merges only constants in, and they all agree on value, the
404 // PHI node becomes a constant value equal to that.
405 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
406 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
407 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
408 // 6. If a conditional branch has a value that is constant, make the selected
409 // destination executable
410 // 7. If a conditional branch has a value that is overdefined, make all
411 // successors executable.
413 void SCCPSolver::visitPHINode(PHINode &PN) {
414 LatticeVal &PNIV = getValueState(&PN);
415 if (PNIV.isOverdefined()) {
416 // There may be instructions using this PHI node that are not overdefined
417 // themselves. If so, make sure that they know that the PHI node operand
419 std::multimap<PHINode*, Instruction*>::iterator I, E;
420 tie(I, E) = UsersOfOverdefinedPHIs.equal_range(&PN);
422 std::vector<Instruction*> Users;
423 Users.reserve(std::distance(I, E));
424 for (; I != E; ++I) Users.push_back(I->second);
425 while (!Users.empty()) {
430 return; // Quick exit
433 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
434 // and slow us down a lot. Just mark them overdefined.
435 if (PN.getNumIncomingValues() > 64) {
436 markOverdefined(PNIV, &PN);
440 // Look at all of the executable operands of the PHI node. If any of them
441 // are overdefined, the PHI becomes overdefined as well. If they are all
442 // constant, and they agree with each other, the PHI becomes the identical
443 // constant. If they are constant and don't agree, the PHI is overdefined.
444 // If there are no executable operands, the PHI remains undefined.
446 Constant *OperandVal = 0;
447 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
448 LatticeVal &IV = getValueState(PN.getIncomingValue(i));
449 if (IV.isUndefined()) continue; // Doesn't influence PHI node.
451 if (isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) {
452 if (IV.isOverdefined()) { // PHI node becomes overdefined!
453 markOverdefined(PNIV, &PN);
457 if (OperandVal == 0) { // Grab the first value...
458 OperandVal = IV.getConstant();
459 } else { // Another value is being merged in!
460 // There is already a reachable operand. If we conflict with it,
461 // then the PHI node becomes overdefined. If we agree with it, we
464 // Check to see if there are two different constants merging...
465 if (IV.getConstant() != OperandVal) {
466 // Yes there is. This means the PHI node is not constant.
467 // You must be overdefined poor PHI.
469 markOverdefined(PNIV, &PN); // The PHI node now becomes overdefined
470 return; // I'm done analyzing you
476 // If we exited the loop, this means that the PHI node only has constant
477 // arguments that agree with each other(and OperandVal is the constant) or
478 // OperandVal is null because there are no defined incoming arguments. If
479 // this is the case, the PHI remains undefined.
482 markConstant(PNIV, &PN, OperandVal); // Acquire operand value
485 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
486 std::vector<bool> SuccFeasible;
487 getFeasibleSuccessors(TI, SuccFeasible);
489 BasicBlock *BB = TI.getParent();
491 // Mark all feasible successors executable...
492 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
494 markEdgeExecutable(BB, TI.getSuccessor(i));
497 void SCCPSolver::visitCastInst(CastInst &I) {
498 Value *V = I.getOperand(0);
499 LatticeVal &VState = getValueState(V);
500 if (VState.isOverdefined()) // Inherit overdefinedness of operand
502 else if (VState.isConstant()) // Propagate constant value
503 markConstant(&I, ConstantExpr::getCast(VState.getConstant(), I.getType()));
506 void SCCPSolver::visitSelectInst(SelectInst &I) {
507 LatticeVal &CondValue = getValueState(I.getCondition());
508 if (CondValue.isOverdefined())
510 else if (CondValue.isConstant()) {
511 if (CondValue.getConstant() == ConstantBool::True) {
512 LatticeVal &Val = getValueState(I.getTrueValue());
513 if (Val.isOverdefined())
515 else if (Val.isConstant())
516 markConstant(&I, Val.getConstant());
517 } else if (CondValue.getConstant() == ConstantBool::False) {
518 LatticeVal &Val = getValueState(I.getFalseValue());
519 if (Val.isOverdefined())
521 else if (Val.isConstant())
522 markConstant(&I, Val.getConstant());
528 // Handle BinaryOperators and Shift Instructions...
529 void SCCPSolver::visitBinaryOperator(Instruction &I) {
530 LatticeVal &IV = ValueState[&I];
531 if (IV.isOverdefined()) return;
533 LatticeVal &V1State = getValueState(I.getOperand(0));
534 LatticeVal &V2State = getValueState(I.getOperand(1));
536 if (V1State.isOverdefined() || V2State.isOverdefined()) {
537 // If both operands are PHI nodes, it is possible that this instruction has
538 // a constant value, despite the fact that the PHI node doesn't. Check for
539 // this condition now.
540 if (PHINode *PN1 = dyn_cast<PHINode>(I.getOperand(0)))
541 if (PHINode *PN2 = dyn_cast<PHINode>(I.getOperand(1)))
542 if (PN1->getParent() == PN2->getParent()) {
543 // Since the two PHI nodes are in the same basic block, they must have
544 // entries for the same predecessors. Walk the predecessor list, and
545 // if all of the incoming values are constants, and the result of
546 // evaluating this expression with all incoming value pairs is the
547 // same, then this expression is a constant even though the PHI node
548 // is not a constant!
550 for (unsigned i = 0, e = PN1->getNumIncomingValues(); i != e; ++i) {
551 LatticeVal &In1 = getValueState(PN1->getIncomingValue(i));
552 BasicBlock *InBlock = PN1->getIncomingBlock(i);
554 getValueState(PN2->getIncomingValueForBlock(InBlock));
556 if (In1.isOverdefined() || In2.isOverdefined()) {
557 Result.markOverdefined();
558 break; // Cannot fold this operation over the PHI nodes!
559 } else if (In1.isConstant() && In2.isConstant()) {
560 Constant *V = ConstantExpr::get(I.getOpcode(), In1.getConstant(),
562 if (Result.isUndefined())
563 Result.markConstant(V);
564 else if (Result.isConstant() && Result.getConstant() != V) {
565 Result.markOverdefined();
571 // If we found a constant value here, then we know the instruction is
572 // constant despite the fact that the PHI nodes are overdefined.
573 if (Result.isConstant()) {
574 markConstant(IV, &I, Result.getConstant());
575 // Remember that this instruction is virtually using the PHI node
577 UsersOfOverdefinedPHIs.insert(std::make_pair(PN1, &I));
578 UsersOfOverdefinedPHIs.insert(std::make_pair(PN2, &I));
580 } else if (Result.isUndefined()) {
584 // Okay, this really is overdefined now. Since we might have
585 // speculatively thought that this was not overdefined before, and
586 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
587 // make sure to clean out any entries that we put there, for
589 std::multimap<PHINode*, Instruction*>::iterator It, E;
590 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN1);
592 if (It->second == &I) {
593 UsersOfOverdefinedPHIs.erase(It++);
597 tie(It, E) = UsersOfOverdefinedPHIs.equal_range(PN2);
599 if (It->second == &I) {
600 UsersOfOverdefinedPHIs.erase(It++);
606 markOverdefined(IV, &I);
607 } else if (V1State.isConstant() && V2State.isConstant()) {
608 markConstant(IV, &I, ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
609 V2State.getConstant()));
613 // Handle getelementptr instructions... if all operands are constants then we
614 // can turn this into a getelementptr ConstantExpr.
616 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
617 LatticeVal &IV = ValueState[&I];
618 if (IV.isOverdefined()) return;
620 std::vector<Constant*> Operands;
621 Operands.reserve(I.getNumOperands());
623 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
624 LatticeVal &State = getValueState(I.getOperand(i));
625 if (State.isUndefined())
626 return; // Operands are not resolved yet...
627 else if (State.isOverdefined()) {
628 markOverdefined(IV, &I);
631 assert(State.isConstant() && "Unknown state!");
632 Operands.push_back(State.getConstant());
635 Constant *Ptr = Operands[0];
636 Operands.erase(Operands.begin()); // Erase the pointer from idx list...
638 markConstant(IV, &I, ConstantExpr::getGetElementPtr(Ptr, Operands));
641 /// GetGEPGlobalInitializer - Given a constant and a getelementptr constantexpr,
642 /// return the constant value being addressed by the constant expression, or
643 /// null if something is funny.
645 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
646 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
647 return 0; // Do not allow stepping over the value!
649 // Loop over all of the operands, tracking down which value we are
651 for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
652 if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
653 ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
654 if (CS == 0) return 0;
655 if (CU->getValue() >= CS->getNumOperands()) return 0;
656 C = CS->getOperand(CU->getValue());
657 } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
658 ConstantArray *CA = dyn_cast<ConstantArray>(C);
659 if (CA == 0) return 0;
660 if ((uint64_t)CS->getValue() >= CA->getNumOperands()) return 0;
661 C = CA->getOperand(CS->getValue());
667 // Handle load instructions. If the operand is a constant pointer to a constant
668 // global, we can replace the load with the loaded constant value!
669 void SCCPSolver::visitLoadInst(LoadInst &I) {
670 LatticeVal &IV = ValueState[&I];
671 if (IV.isOverdefined()) return;
673 LatticeVal &PtrVal = getValueState(I.getOperand(0));
674 if (PtrVal.isUndefined()) return; // The pointer is not resolved yet!
675 if (PtrVal.isConstant() && !I.isVolatile()) {
676 Value *Ptr = PtrVal.getConstant();
677 if (isa<ConstantPointerNull>(Ptr)) {
679 markConstant(IV, &I, Constant::getNullValue(I.getType()));
683 // Transform load (constant global) into the value loaded.
684 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr))
685 if (GV->isConstant() && !GV->isExternal()) {
686 markConstant(IV, &I, GV->getInitializer());
690 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
691 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
692 if (CE->getOpcode() == Instruction::GetElementPtr)
693 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
694 if (GV->isConstant() && !GV->isExternal())
696 GetGEPGlobalInitializer(GV->getInitializer(), CE)) {
697 markConstant(IV, &I, V);
702 // Otherwise we cannot say for certain what value this load will produce.
704 markOverdefined(IV, &I);
707 void SCCPSolver::visitCallInst(CallInst &I) {
708 LatticeVal &IV = ValueState[&I];
709 if (IV.isOverdefined()) return;
711 Function *F = I.getCalledFunction();
712 if (F == 0 || !canConstantFoldCallTo(F)) {
713 markOverdefined(IV, &I);
717 std::vector<Constant*> Operands;
718 Operands.reserve(I.getNumOperands()-1);
720 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
721 LatticeVal &State = getValueState(I.getOperand(i));
722 if (State.isUndefined())
723 return; // Operands are not resolved yet...
724 else if (State.isOverdefined()) {
725 markOverdefined(IV, &I);
728 assert(State.isConstant() && "Unknown state!");
729 Operands.push_back(State.getConstant());
732 if (Constant *C = ConstantFoldCall(F, Operands))
733 markConstant(IV, &I, C);
735 markOverdefined(IV, &I);
739 void SCCPSolver::Solve() {
740 // Process the work lists until they are empty!
741 while (!BBWorkList.empty() || !InstWorkList.empty() ||
742 !OverdefinedInstWorkList.empty()) {
743 // Process the instruction work list...
744 while (!OverdefinedInstWorkList.empty()) {
745 Instruction *I = OverdefinedInstWorkList.back();
746 OverdefinedInstWorkList.pop_back();
748 DEBUG(std::cerr << "\nPopped off OI-WL: " << I);
750 // "I" got into the work list because it either made the transition from
751 // bottom to constant
753 // Anything on this worklist that is overdefined need not be visited
754 // since all of its users will have already been marked as overdefined
755 // Update all of the users of this instruction's value...
757 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
759 OperandChangedState(*UI);
761 // Process the instruction work list...
762 while (!InstWorkList.empty()) {
763 Instruction *I = InstWorkList.back();
764 InstWorkList.pop_back();
766 DEBUG(std::cerr << "\nPopped off I-WL: " << *I);
768 // "I" got into the work list because it either made the transition from
769 // bottom to constant
771 // Anything on this worklist that is overdefined need not be visited
772 // since all of its users will have already been marked as overdefined.
773 // Update all of the users of this instruction's value...
775 if (!getValueState(I).isOverdefined())
776 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
778 OperandChangedState(*UI);
781 // Process the basic block work list...
782 while (!BBWorkList.empty()) {
783 BasicBlock *BB = BBWorkList.back();
784 BBWorkList.pop_back();
786 DEBUG(std::cerr << "\nPopped off BBWL: " << *BB);
788 // Notify all instructions in this basic block that they are newly
797 //===--------------------------------------------------------------------===//
799 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
800 /// Sparse Conditional COnstant Propagator.
802 struct SCCP : public FunctionPass {
803 // runOnFunction - Run the Sparse Conditional Constant Propagation
804 // algorithm, and return true if the function was modified.
806 bool runOnFunction(Function &F);
808 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
809 AU.setPreservesCFG();
813 RegisterOpt<SCCP> X("sccp", "Sparse Conditional Constant Propagation");
814 } // end anonymous namespace
817 // createSCCPPass - This is the public interface to this file...
818 FunctionPass *llvm::createSCCPPass() {
823 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
824 // and return true if the function was modified.
826 bool SCCP::runOnFunction(Function &F) {
827 DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n");
830 // Mark the first block of the function as being executable.
831 Solver.MarkBlockExecutable(F.begin());
833 // Mark all arguments to the function as being overdefined.
834 hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
835 for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI)
836 Values[AI].markOverdefined();
838 // Solve for constants.
841 bool MadeChanges = false;
843 // If we decided that there are basic blocks that are dead in this function,
844 // delete their contents now. Note that we cannot actually delete the blocks,
845 // as we cannot modify the CFG of the function.
847 std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
848 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
849 if (!ExecutableBBs.count(BB)) {
850 DEBUG(std::cerr << " BasicBlock Dead:" << *BB);
853 // Delete the instructions backwards, as it has a reduced likelihood of
854 // having to update as many def-use and use-def chains.
855 std::vector<Instruction*> Insts;
856 for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
859 while (!Insts.empty()) {
860 Instruction *I = Insts.back();
863 I->replaceAllUsesWith(UndefValue::get(I->getType()));
864 BB->getInstList().erase(I);
870 // Iterate over all of the instructions in a function, replacing them with
871 // constants if we have found them to be of constant values.
873 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB)
874 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
875 Instruction *Inst = BI++;
876 if (Inst->getType() != Type::VoidTy) {
877 LatticeVal &IV = Values[Inst];
878 if (IV.isConstant() || IV.isUndefined()) {
880 if (IV.isConstant()) {
881 Const = IV.getConstant();
882 DEBUG(std::cerr << " Constant: " << *Const << " = " << *Inst);
884 Const = UndefValue::get(Inst->getType());
885 DEBUG(std::cerr << " Undefined: " << *Inst);
888 // Replaces all of the uses of a variable with uses of the constant.
889 Inst->replaceAllUsesWith(Const);
891 // Delete the instruction.
892 BB->getInstList().erase(Inst);
894 // Hey, we just changed something!