1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // 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/Transforms/IPO.h"
27 #include "llvm/Constants.h"
28 #include "llvm/DerivedTypes.h"
29 #include "llvm/Instructions.h"
30 #include "llvm/LLVMContext.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Analysis/ConstantFolding.h"
33 #include "llvm/Analysis/ValueTracking.h"
34 #include "llvm/Transforms/Utils/Local.h"
35 #include "llvm/Support/CallSite.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/InstVisitor.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include "llvm/ADT/DenseMap.h"
41 #include "llvm/ADT/DenseSet.h"
42 #include "llvm/ADT/SmallSet.h"
43 #include "llvm/ADT/SmallVector.h"
44 #include "llvm/ADT/Statistic.h"
45 #include "llvm/ADT/STLExtras.h"
50 STATISTIC(NumInstRemoved
, "Number of instructions removed");
51 STATISTIC(NumDeadBlocks
, "Number of basic blocks unreachable");
53 STATISTIC(IPNumInstRemoved
, "Number of instructions removed by IPSCCP");
54 STATISTIC(IPNumDeadBlocks
, "Number of basic blocks unreachable by IPSCCP");
55 STATISTIC(IPNumArgsElimed
,"Number of arguments constant propagated by IPSCCP");
56 STATISTIC(IPNumGlobalConst
, "Number of globals found to be constant by IPSCCP");
59 /// LatticeVal class - This class represents the different lattice values that
60 /// an LLVM value may occupy. It is a simple class with value semantics.
64 /// undefined - This LLVM Value has no known value yet.
67 /// constant - This LLVM Value has a specific constant value.
70 /// forcedconstant - This LLVM Value was thought to be undef until
71 /// ResolvedUndefsIn. This is treated just like 'constant', but if merged
72 /// with another (different) constant, it goes to overdefined, instead of
76 /// overdefined - This instruction is not known to be constant, and we know
79 } LatticeValue
; // The current lattice position
81 Constant
*ConstantVal
; // If Constant value, the current value
83 inline LatticeVal() : LatticeValue(undefined
), ConstantVal(0) {}
85 // markOverdefined - Return true if this is a new status to be in...
86 inline bool markOverdefined() {
87 if (LatticeValue
!= overdefined
) {
88 LatticeValue
= overdefined
;
94 // markConstant - Return true if this is a new status for us.
95 inline bool markConstant(Constant
*V
) {
96 if (LatticeValue
!= constant
) {
97 if (LatticeValue
== undefined
) {
98 LatticeValue
= constant
;
99 assert(V
&& "Marking constant with NULL");
102 assert(LatticeValue
== forcedconstant
&&
103 "Cannot move from overdefined to constant!");
104 // Stay at forcedconstant if the constant is the same.
105 if (V
== ConstantVal
) return false;
107 // Otherwise, we go to overdefined. Assumptions made based on the
108 // forced value are possibly wrong. Assuming this is another constant
109 // could expose a contradiction.
110 LatticeValue
= overdefined
;
114 assert(ConstantVal
== V
&& "Marking constant with different value");
119 inline void markForcedConstant(Constant
*V
) {
120 assert(LatticeValue
== undefined
&& "Can't force a defined value!");
121 LatticeValue
= forcedconstant
;
125 inline bool isUndefined() const { return LatticeValue
== undefined
; }
126 inline bool isConstant() const {
127 return LatticeValue
== constant
|| LatticeValue
== forcedconstant
;
129 inline bool isOverdefined() const { return LatticeValue
== overdefined
; }
131 inline Constant
*getConstant() const {
132 assert(isConstant() && "Cannot get the constant of a non-constant!");
137 //===----------------------------------------------------------------------===//
139 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
140 /// Constant Propagation.
142 class SCCPSolver
: public InstVisitor
<SCCPSolver
> {
143 LLVMContext
*Context
;
144 DenseSet
<BasicBlock
*> BBExecutable
;// The basic blocks that are executable
145 std::map
<Value
*, LatticeVal
> ValueState
; // The state each value is in.
147 /// GlobalValue - If we are tracking any values for the contents of a global
148 /// variable, we keep a mapping from the constant accessor to the element of
149 /// the global, to the currently known value. If the value becomes
150 /// overdefined, it's entry is simply removed from this map.
151 DenseMap
<GlobalVariable
*, LatticeVal
> TrackedGlobals
;
153 /// TrackedRetVals - If we are tracking arguments into and the return
154 /// value out of a function, it will have an entry in this map, indicating
155 /// what the known return value for the function is.
156 DenseMap
<Function
*, LatticeVal
> TrackedRetVals
;
158 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
159 /// that return multiple values.
160 DenseMap
<std::pair
<Function
*, unsigned>, LatticeVal
> TrackedMultipleRetVals
;
162 // The reason for two worklists is that overdefined is the lowest state
163 // on the lattice, and moving things to overdefined as fast as possible
164 // makes SCCP converge much faster.
165 // By having a separate worklist, we accomplish this because everything
166 // possibly overdefined will become overdefined at the soonest possible
168 SmallVector
<Value
*, 64> OverdefinedInstWorkList
;
169 SmallVector
<Value
*, 64> InstWorkList
;
172 SmallVector
<BasicBlock
*, 64> BBWorkList
; // The BasicBlock work list
174 /// UsersOfOverdefinedPHIs - Keep track of any users of PHI nodes that are not
175 /// overdefined, despite the fact that the PHI node is overdefined.
176 std::multimap
<PHINode
*, Instruction
*> UsersOfOverdefinedPHIs
;
178 /// KnownFeasibleEdges - Entries in this set are edges which have already had
179 /// PHI nodes retriggered.
180 typedef std::pair
<BasicBlock
*, BasicBlock
*> Edge
;
181 DenseSet
<Edge
> KnownFeasibleEdges
;
183 void setContext(LLVMContext
*C
) { Context
= C
; }
185 /// MarkBlockExecutable - This method can be used by clients to mark all of
186 /// the blocks that are known to be intrinsically live in the processed unit.
187 void MarkBlockExecutable(BasicBlock
*BB
) {
188 DEBUG(errs() << "Marking Block Executable: " << BB
->getName() << "\n");
189 BBExecutable
.insert(BB
); // Basic block is executable!
190 BBWorkList
.push_back(BB
); // Add the block to the work list!
193 /// TrackValueOfGlobalVariable - Clients can use this method to
194 /// inform the SCCPSolver that it should track loads and stores to the
195 /// specified global variable if it can. This is only legal to call if
196 /// performing Interprocedural SCCP.
197 void TrackValueOfGlobalVariable(GlobalVariable
*GV
) {
198 const Type
*ElTy
= GV
->getType()->getElementType();
199 if (ElTy
->isFirstClassType()) {
200 LatticeVal
&IV
= TrackedGlobals
[GV
];
201 if (!isa
<UndefValue
>(GV
->getInitializer()))
202 IV
.markConstant(GV
->getInitializer());
206 /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
207 /// and out of the specified function (which cannot have its address taken),
208 /// this method must be called.
209 void AddTrackedFunction(Function
*F
) {
210 assert(F
->hasLocalLinkage() && "Can only track internal functions!");
211 // Add an entry, F -> undef.
212 if (const StructType
*STy
= dyn_cast
<StructType
>(F
->getReturnType())) {
213 for (unsigned i
= 0, e
= STy
->getNumElements(); i
!= e
; ++i
)
214 TrackedMultipleRetVals
.insert(std::make_pair(std::make_pair(F
, i
),
217 TrackedRetVals
.insert(std::make_pair(F
, LatticeVal()));
220 /// Solve - Solve for constants and executable blocks.
224 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
225 /// that branches on undef values cannot reach any of their successors.
226 /// However, this is not a safe assumption. After we solve dataflow, this
227 /// method should be use to handle this. If this returns true, the solver
229 bool ResolvedUndefsIn(Function
&F
);
231 bool isBlockExecutable(BasicBlock
*BB
) const {
232 return BBExecutable
.count(BB
);
235 /// getValueMapping - Once we have solved for constants, return the mapping of
236 /// LLVM values to LatticeVals.
237 std::map
<Value
*, LatticeVal
> &getValueMapping() {
241 /// getTrackedRetVals - Get the inferred return value map.
243 const DenseMap
<Function
*, LatticeVal
> &getTrackedRetVals() {
244 return TrackedRetVals
;
247 /// getTrackedGlobals - Get and return the set of inferred initializers for
248 /// global variables.
249 const DenseMap
<GlobalVariable
*, LatticeVal
> &getTrackedGlobals() {
250 return TrackedGlobals
;
253 inline void markOverdefined(Value
*V
) {
254 markOverdefined(ValueState
[V
], V
);
258 // markConstant - Make a value be marked as "constant". If the value
259 // is not already a constant, add it to the instruction work list so that
260 // the users of the instruction are updated later.
262 inline void markConstant(LatticeVal
&IV
, Value
*V
, Constant
*C
) {
263 if (IV
.markConstant(C
)) {
264 DEBUG(errs() << "markConstant: " << *C
<< ": " << *V
<< '\n');
265 InstWorkList
.push_back(V
);
269 inline void markForcedConstant(LatticeVal
&IV
, Value
*V
, Constant
*C
) {
270 IV
.markForcedConstant(C
);
271 DEBUG(errs() << "markForcedConstant: " << *C
<< ": " << *V
<< '\n');
272 InstWorkList
.push_back(V
);
275 inline void markConstant(Value
*V
, Constant
*C
) {
276 markConstant(ValueState
[V
], V
, C
);
279 // markOverdefined - Make a value be marked as "overdefined". If the
280 // value is not already overdefined, add it to the overdefined instruction
281 // work list so that the users of the instruction are updated later.
282 inline void markOverdefined(LatticeVal
&IV
, Value
*V
) {
283 if (IV
.markOverdefined()) {
284 DEBUG(errs() << "markOverdefined: ";
285 if (Function
*F
= dyn_cast
<Function
>(V
))
286 errs() << "Function '" << F
->getName() << "'\n";
288 errs() << *V
<< '\n');
289 // Only instructions go on the work list
290 OverdefinedInstWorkList
.push_back(V
);
294 inline void mergeInValue(LatticeVal
&IV
, Value
*V
, LatticeVal
&MergeWithV
) {
295 if (IV
.isOverdefined() || MergeWithV
.isUndefined())
297 if (MergeWithV
.isOverdefined())
298 markOverdefined(IV
, V
);
299 else if (IV
.isUndefined())
300 markConstant(IV
, V
, MergeWithV
.getConstant());
301 else if (IV
.getConstant() != MergeWithV
.getConstant())
302 markOverdefined(IV
, V
);
305 inline void mergeInValue(Value
*V
, LatticeVal
&MergeWithV
) {
306 return mergeInValue(ValueState
[V
], V
, MergeWithV
);
310 // getValueState - Return the LatticeVal object that corresponds to the value.
311 // This function is necessary because not all values should start out in the
312 // underdefined state... Argument's should be overdefined, and
313 // constants should be marked as constants. If a value is not known to be an
314 // Instruction object, then use this accessor to get its value from the map.
316 inline LatticeVal
&getValueState(Value
*V
) {
317 std::map
<Value
*, LatticeVal
>::iterator I
= ValueState
.find(V
);
318 if (I
!= ValueState
.end()) return I
->second
; // Common case, in the map
320 if (Constant
*C
= dyn_cast
<Constant
>(V
)) {
321 if (isa
<UndefValue
>(V
)) {
322 // Nothing to do, remain undefined.
324 LatticeVal
&LV
= ValueState
[C
];
325 LV
.markConstant(C
); // Constants are constant
329 // All others are underdefined by default...
330 return ValueState
[V
];
333 // markEdgeExecutable - Mark a basic block as executable, adding it to the BB
334 // work list if it is not already executable...
336 void markEdgeExecutable(BasicBlock
*Source
, BasicBlock
*Dest
) {
337 if (!KnownFeasibleEdges
.insert(Edge(Source
, Dest
)).second
)
338 return; // This edge is already known to be executable!
340 if (BBExecutable
.count(Dest
)) {
341 DEBUG(errs() << "Marking Edge Executable: " << Source
->getName()
342 << " -> " << Dest
->getName() << "\n");
344 // The destination is already executable, but we just made an edge
345 // feasible that wasn't before. Revisit the PHI nodes in the block
346 // because they have potentially new operands.
347 for (BasicBlock::iterator I
= Dest
->begin(); isa
<PHINode
>(I
); ++I
)
348 visitPHINode(*cast
<PHINode
>(I
));
351 MarkBlockExecutable(Dest
);
355 // getFeasibleSuccessors - Return a vector of booleans to indicate which
356 // successors are reachable from a given terminator instruction.
358 void getFeasibleSuccessors(TerminatorInst
&TI
, SmallVector
<bool, 16> &Succs
);
360 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
361 // block to the 'To' basic block is currently feasible...
363 bool isEdgeFeasible(BasicBlock
*From
, BasicBlock
*To
);
365 // OperandChangedState - This method is invoked on all of the users of an
366 // instruction that was just changed state somehow.... Based on this
367 // information, we need to update the specified user of this instruction.
369 void OperandChangedState(User
*U
) {
370 // Only instructions use other variable values!
371 Instruction
&I
= cast
<Instruction
>(*U
);
372 if (BBExecutable
.count(I
.getParent())) // Inst is executable?
377 friend class InstVisitor
<SCCPSolver
>;
379 // visit implementations - Something changed in this instruction... Either an
380 // operand made a transition, or the instruction is newly executable. Change
381 // the value type of I to reflect these changes if appropriate.
383 void visitPHINode(PHINode
&I
);
386 void visitReturnInst(ReturnInst
&I
);
387 void visitTerminatorInst(TerminatorInst
&TI
);
389 void visitCastInst(CastInst
&I
);
390 void visitSelectInst(SelectInst
&I
);
391 void visitBinaryOperator(Instruction
&I
);
392 void visitCmpInst(CmpInst
&I
);
393 void visitExtractElementInst(ExtractElementInst
&I
);
394 void visitInsertElementInst(InsertElementInst
&I
);
395 void visitShuffleVectorInst(ShuffleVectorInst
&I
);
396 void visitExtractValueInst(ExtractValueInst
&EVI
);
397 void visitInsertValueInst(InsertValueInst
&IVI
);
399 // Instructions that cannot be folded away...
400 void visitStoreInst (Instruction
&I
);
401 void visitLoadInst (LoadInst
&I
);
402 void visitGetElementPtrInst(GetElementPtrInst
&I
);
403 void visitCallInst (CallInst
&I
) { visitCallSite(CallSite::get(&I
)); }
404 void visitInvokeInst (InvokeInst
&II
) {
405 visitCallSite(CallSite::get(&II
));
406 visitTerminatorInst(II
);
408 void visitCallSite (CallSite CS
);
409 void visitUnwindInst (TerminatorInst
&I
) { /*returns void*/ }
410 void visitUnreachableInst(TerminatorInst
&I
) { /*returns void*/ }
411 void visitAllocationInst(Instruction
&I
) { markOverdefined(&I
); }
412 void visitVANextInst (Instruction
&I
) { markOverdefined(&I
); }
413 void visitVAArgInst (Instruction
&I
) { markOverdefined(&I
); }
414 void visitFreeInst (Instruction
&I
) { /*returns void*/ }
416 void visitInstruction(Instruction
&I
) {
417 // If a new instruction is added to LLVM that we don't handle...
418 errs() << "SCCP: Don't know how to handle: " << I
;
419 markOverdefined(&I
); // Just in case
423 } // end anonymous namespace
426 // getFeasibleSuccessors - Return a vector of booleans to indicate which
427 // successors are reachable from a given terminator instruction.
429 void SCCPSolver::getFeasibleSuccessors(TerminatorInst
&TI
,
430 SmallVector
<bool, 16> &Succs
) {
431 Succs
.resize(TI
.getNumSuccessors());
432 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(&TI
)) {
433 if (BI
->isUnconditional()) {
436 LatticeVal
&BCValue
= getValueState(BI
->getCondition());
437 if (BCValue
.isOverdefined() ||
438 (BCValue
.isConstant() && !isa
<ConstantInt
>(BCValue
.getConstant()))) {
439 // Overdefined condition variables, and branches on unfoldable constant
440 // conditions, mean the branch could go either way.
441 Succs
[0] = Succs
[1] = true;
442 } else if (BCValue
.isConstant()) {
443 // Constant condition variables mean the branch can only go a single way
444 Succs
[BCValue
.getConstant() == ConstantInt::getFalse(*Context
)] = true;
447 } else if (isa
<InvokeInst
>(&TI
)) {
448 // Invoke instructions successors are always executable.
449 Succs
[0] = Succs
[1] = true;
450 } else if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(&TI
)) {
451 LatticeVal
&SCValue
= getValueState(SI
->getCondition());
452 if (SCValue
.isOverdefined() || // Overdefined condition?
453 (SCValue
.isConstant() && !isa
<ConstantInt
>(SCValue
.getConstant()))) {
454 // All destinations are executable!
455 Succs
.assign(TI
.getNumSuccessors(), true);
456 } else if (SCValue
.isConstant())
457 Succs
[SI
->findCaseValue(cast
<ConstantInt
>(SCValue
.getConstant()))] = true;
459 llvm_unreachable("SCCP: Don't know how to handle this terminator!");
464 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
465 // block to the 'To' basic block is currently feasible...
467 bool SCCPSolver::isEdgeFeasible(BasicBlock
*From
, BasicBlock
*To
) {
468 assert(BBExecutable
.count(To
) && "Dest should always be alive!");
470 // Make sure the source basic block is executable!!
471 if (!BBExecutable
.count(From
)) return false;
473 // Check to make sure this edge itself is actually feasible now...
474 TerminatorInst
*TI
= From
->getTerminator();
475 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(TI
)) {
476 if (BI
->isUnconditional())
479 LatticeVal
&BCValue
= getValueState(BI
->getCondition());
480 if (BCValue
.isOverdefined()) {
481 // Overdefined condition variables mean the branch could go either way.
483 } else if (BCValue
.isConstant()) {
484 // Not branching on an evaluatable constant?
485 if (!isa
<ConstantInt
>(BCValue
.getConstant())) return true;
487 // Constant condition variables mean the branch can only go a single way
488 return BI
->getSuccessor(BCValue
.getConstant() ==
489 ConstantInt::getFalse(*Context
)) == To
;
493 } else if (isa
<InvokeInst
>(TI
)) {
494 // Invoke instructions successors are always executable.
496 } else if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(TI
)) {
497 LatticeVal
&SCValue
= getValueState(SI
->getCondition());
498 if (SCValue
.isOverdefined()) { // Overdefined condition?
499 // All destinations are executable!
501 } else if (SCValue
.isConstant()) {
502 Constant
*CPV
= SCValue
.getConstant();
503 if (!isa
<ConstantInt
>(CPV
))
504 return true; // not a foldable constant?
506 // Make sure to skip the "default value" which isn't a value
507 for (unsigned i
= 1, E
= SI
->getNumSuccessors(); i
!= E
; ++i
)
508 if (SI
->getSuccessorValue(i
) == CPV
) // Found the taken branch...
509 return SI
->getSuccessor(i
) == To
;
511 // Constant value not equal to any of the branches... must execute
512 // default branch then...
513 return SI
->getDefaultDest() == To
;
518 errs() << "Unknown terminator instruction: " << *TI
<< '\n';
524 // visit Implementations - Something changed in this instruction... Either an
525 // operand made a transition, or the instruction is newly executable. Change
526 // the value type of I to reflect these changes if appropriate. This method
527 // makes sure to do the following actions:
529 // 1. If a phi node merges two constants in, and has conflicting value coming
530 // from different branches, or if the PHI node merges in an overdefined
531 // value, then the PHI node becomes overdefined.
532 // 2. If a phi node merges only constants in, and they all agree on value, the
533 // PHI node becomes a constant value equal to that.
534 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
535 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
536 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
537 // 6. If a conditional branch has a value that is constant, make the selected
538 // destination executable
539 // 7. If a conditional branch has a value that is overdefined, make all
540 // successors executable.
542 void SCCPSolver::visitPHINode(PHINode
&PN
) {
543 LatticeVal
&PNIV
= getValueState(&PN
);
544 if (PNIV
.isOverdefined()) {
545 // There may be instructions using this PHI node that are not overdefined
546 // themselves. If so, make sure that they know that the PHI node operand
548 std::multimap
<PHINode
*, Instruction
*>::iterator I
, E
;
549 tie(I
, E
) = UsersOfOverdefinedPHIs
.equal_range(&PN
);
551 SmallVector
<Instruction
*, 16> Users
;
552 for (; I
!= E
; ++I
) Users
.push_back(I
->second
);
553 while (!Users
.empty()) {
558 return; // Quick exit
561 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
562 // and slow us down a lot. Just mark them overdefined.
563 if (PN
.getNumIncomingValues() > 64) {
564 markOverdefined(PNIV
, &PN
);
568 // Look at all of the executable operands of the PHI node. If any of them
569 // are overdefined, the PHI becomes overdefined as well. If they are all
570 // constant, and they agree with each other, the PHI becomes the identical
571 // constant. If they are constant and don't agree, the PHI is overdefined.
572 // If there are no executable operands, the PHI remains undefined.
574 Constant
*OperandVal
= 0;
575 for (unsigned i
= 0, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
576 LatticeVal
&IV
= getValueState(PN
.getIncomingValue(i
));
577 if (IV
.isUndefined()) continue; // Doesn't influence PHI node.
579 if (isEdgeFeasible(PN
.getIncomingBlock(i
), PN
.getParent())) {
580 if (IV
.isOverdefined()) { // PHI node becomes overdefined!
581 markOverdefined(&PN
);
585 if (OperandVal
== 0) { // Grab the first value...
586 OperandVal
= IV
.getConstant();
587 } else { // Another value is being merged in!
588 // There is already a reachable operand. If we conflict with it,
589 // then the PHI node becomes overdefined. If we agree with it, we
592 // Check to see if there are two different constants merging...
593 if (IV
.getConstant() != OperandVal
) {
594 // Yes there is. This means the PHI node is not constant.
595 // You must be overdefined poor PHI.
597 markOverdefined(&PN
); // The PHI node now becomes overdefined
598 return; // I'm done analyzing you
604 // If we exited the loop, this means that the PHI node only has constant
605 // arguments that agree with each other(and OperandVal is the constant) or
606 // OperandVal is null because there are no defined incoming arguments. If
607 // this is the case, the PHI remains undefined.
610 markConstant(&PN
, OperandVal
); // Acquire operand value
613 void SCCPSolver::visitReturnInst(ReturnInst
&I
) {
614 if (I
.getNumOperands() == 0) return; // Ret void
616 Function
*F
= I
.getParent()->getParent();
617 // If we are tracking the return value of this function, merge it in.
618 if (!F
->hasLocalLinkage())
621 if (!TrackedRetVals
.empty() && I
.getNumOperands() == 1) {
622 DenseMap
<Function
*, LatticeVal
>::iterator TFRVI
=
623 TrackedRetVals
.find(F
);
624 if (TFRVI
!= TrackedRetVals
.end() &&
625 !TFRVI
->second
.isOverdefined()) {
626 LatticeVal
&IV
= getValueState(I
.getOperand(0));
627 mergeInValue(TFRVI
->second
, F
, IV
);
632 // Handle functions that return multiple values.
633 if (!TrackedMultipleRetVals
.empty() && I
.getNumOperands() > 1) {
634 for (unsigned i
= 0, e
= I
.getNumOperands(); i
!= e
; ++i
) {
635 DenseMap
<std::pair
<Function
*, unsigned>, LatticeVal
>::iterator
636 It
= TrackedMultipleRetVals
.find(std::make_pair(F
, i
));
637 if (It
== TrackedMultipleRetVals
.end()) break;
638 mergeInValue(It
->second
, F
, getValueState(I
.getOperand(i
)));
640 } else if (!TrackedMultipleRetVals
.empty() &&
641 I
.getNumOperands() == 1 &&
642 isa
<StructType
>(I
.getOperand(0)->getType())) {
643 for (unsigned i
= 0, e
= I
.getOperand(0)->getType()->getNumContainedTypes();
645 DenseMap
<std::pair
<Function
*, unsigned>, LatticeVal
>::iterator
646 It
= TrackedMultipleRetVals
.find(std::make_pair(F
, i
));
647 if (It
== TrackedMultipleRetVals
.end()) break;
648 if (Value
*Val
= FindInsertedValue(I
.getOperand(0), i
, I
.getContext()))
649 mergeInValue(It
->second
, F
, getValueState(Val
));
654 void SCCPSolver::visitTerminatorInst(TerminatorInst
&TI
) {
655 SmallVector
<bool, 16> SuccFeasible
;
656 getFeasibleSuccessors(TI
, SuccFeasible
);
658 BasicBlock
*BB
= TI
.getParent();
660 // Mark all feasible successors executable...
661 for (unsigned i
= 0, e
= SuccFeasible
.size(); i
!= e
; ++i
)
663 markEdgeExecutable(BB
, TI
.getSuccessor(i
));
666 void SCCPSolver::visitCastInst(CastInst
&I
) {
667 Value
*V
= I
.getOperand(0);
668 LatticeVal
&VState
= getValueState(V
);
669 if (VState
.isOverdefined()) // Inherit overdefinedness of operand
671 else if (VState
.isConstant()) // Propagate constant value
672 markConstant(&I
, ConstantExpr::getCast(I
.getOpcode(),
673 VState
.getConstant(), I
.getType()));
676 void SCCPSolver::visitExtractValueInst(ExtractValueInst
&EVI
) {
677 Value
*Aggr
= EVI
.getAggregateOperand();
679 // If the operand to the extractvalue is an undef, the result is undef.
680 if (isa
<UndefValue
>(Aggr
))
683 // Currently only handle single-index extractvalues.
684 if (EVI
.getNumIndices() != 1) {
685 markOverdefined(&EVI
);
690 if (CallInst
*CI
= dyn_cast
<CallInst
>(Aggr
))
691 F
= CI
->getCalledFunction();
692 else if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(Aggr
))
693 F
= II
->getCalledFunction();
695 // TODO: If IPSCCP resolves the callee of this function, we could propagate a
697 if (F
== 0 || TrackedMultipleRetVals
.empty()) {
698 markOverdefined(&EVI
);
702 // See if we are tracking the result of the callee. If not tracking this
703 // function (for example, it is a declaration) just move to overdefined.
704 if (!TrackedMultipleRetVals
.count(std::make_pair(F
, *EVI
.idx_begin()))) {
705 markOverdefined(&EVI
);
709 // Otherwise, the value will be merged in here as a result of CallSite
713 void SCCPSolver::visitInsertValueInst(InsertValueInst
&IVI
) {
714 Value
*Aggr
= IVI
.getAggregateOperand();
715 Value
*Val
= IVI
.getInsertedValueOperand();
717 // If the operands to the insertvalue are undef, the result is undef.
718 if (isa
<UndefValue
>(Aggr
) && isa
<UndefValue
>(Val
))
721 // Currently only handle single-index insertvalues.
722 if (IVI
.getNumIndices() != 1) {
723 markOverdefined(&IVI
);
727 // Currently only handle insertvalue instructions that are in a single-use
728 // chain that builds up a return value.
729 for (const InsertValueInst
*TmpIVI
= &IVI
; ; ) {
730 if (!TmpIVI
->hasOneUse()) {
731 markOverdefined(&IVI
);
734 const Value
*V
= *TmpIVI
->use_begin();
735 if (isa
<ReturnInst
>(V
))
737 TmpIVI
= dyn_cast
<InsertValueInst
>(V
);
739 markOverdefined(&IVI
);
744 // See if we are tracking the result of the callee.
745 Function
*F
= IVI
.getParent()->getParent();
746 DenseMap
<std::pair
<Function
*, unsigned>, LatticeVal
>::iterator
747 It
= TrackedMultipleRetVals
.find(std::make_pair(F
, *IVI
.idx_begin()));
749 // Merge in the inserted member value.
750 if (It
!= TrackedMultipleRetVals
.end())
751 mergeInValue(It
->second
, F
, getValueState(Val
));
753 // Mark the aggregate result of the IVI overdefined; any tracking that we do
754 // will be done on the individual member values.
755 markOverdefined(&IVI
);
758 void SCCPSolver::visitSelectInst(SelectInst
&I
) {
759 LatticeVal
&CondValue
= getValueState(I
.getCondition());
760 if (CondValue
.isUndefined())
762 if (CondValue
.isConstant()) {
763 if (ConstantInt
*CondCB
= dyn_cast
<ConstantInt
>(CondValue
.getConstant())){
764 mergeInValue(&I
, getValueState(CondCB
->getZExtValue() ? I
.getTrueValue()
765 : I
.getFalseValue()));
770 // Otherwise, the condition is overdefined or a constant we can't evaluate.
771 // See if we can produce something better than overdefined based on the T/F
773 LatticeVal
&TVal
= getValueState(I
.getTrueValue());
774 LatticeVal
&FVal
= getValueState(I
.getFalseValue());
776 // select ?, C, C -> C.
777 if (TVal
.isConstant() && FVal
.isConstant() &&
778 TVal
.getConstant() == FVal
.getConstant()) {
779 markConstant(&I
, FVal
.getConstant());
783 if (TVal
.isUndefined()) { // select ?, undef, X -> X.
784 mergeInValue(&I
, FVal
);
785 } else if (FVal
.isUndefined()) { // select ?, X, undef -> X.
786 mergeInValue(&I
, TVal
);
792 // Handle BinaryOperators and Shift Instructions...
793 void SCCPSolver::visitBinaryOperator(Instruction
&I
) {
794 LatticeVal
&IV
= ValueState
[&I
];
795 if (IV
.isOverdefined()) return;
797 LatticeVal
&V1State
= getValueState(I
.getOperand(0));
798 LatticeVal
&V2State
= getValueState(I
.getOperand(1));
800 if (V1State
.isOverdefined() || V2State
.isOverdefined()) {
801 // If this is an AND or OR with 0 or -1, it doesn't matter that the other
802 // operand is overdefined.
803 if (I
.getOpcode() == Instruction::And
|| I
.getOpcode() == Instruction::Or
) {
804 LatticeVal
*NonOverdefVal
= 0;
805 if (!V1State
.isOverdefined()) {
806 NonOverdefVal
= &V1State
;
807 } else if (!V2State
.isOverdefined()) {
808 NonOverdefVal
= &V2State
;
812 if (NonOverdefVal
->isUndefined()) {
813 // Could annihilate value.
814 if (I
.getOpcode() == Instruction::And
)
815 markConstant(IV
, &I
, Constant::getNullValue(I
.getType()));
816 else if (const VectorType
*PT
= dyn_cast
<VectorType
>(I
.getType()))
817 markConstant(IV
, &I
, Constant::getAllOnesValue(PT
));
820 Constant::getAllOnesValue(I
.getType()));
823 if (I
.getOpcode() == Instruction::And
) {
824 if (NonOverdefVal
->getConstant()->isNullValue()) {
825 markConstant(IV
, &I
, NonOverdefVal
->getConstant());
826 return; // X and 0 = 0
829 if (ConstantInt
*CI
=
830 dyn_cast
<ConstantInt
>(NonOverdefVal
->getConstant()))
831 if (CI
->isAllOnesValue()) {
832 markConstant(IV
, &I
, NonOverdefVal
->getConstant());
833 return; // X or -1 = -1
841 // If both operands are PHI nodes, it is possible that this instruction has
842 // a constant value, despite the fact that the PHI node doesn't. Check for
843 // this condition now.
844 if (PHINode
*PN1
= dyn_cast
<PHINode
>(I
.getOperand(0)))
845 if (PHINode
*PN2
= dyn_cast
<PHINode
>(I
.getOperand(1)))
846 if (PN1
->getParent() == PN2
->getParent()) {
847 // Since the two PHI nodes are in the same basic block, they must have
848 // entries for the same predecessors. Walk the predecessor list, and
849 // if all of the incoming values are constants, and the result of
850 // evaluating this expression with all incoming value pairs is the
851 // same, then this expression is a constant even though the PHI node
852 // is not a constant!
854 for (unsigned i
= 0, e
= PN1
->getNumIncomingValues(); i
!= e
; ++i
) {
855 LatticeVal
&In1
= getValueState(PN1
->getIncomingValue(i
));
856 BasicBlock
*InBlock
= PN1
->getIncomingBlock(i
);
858 getValueState(PN2
->getIncomingValueForBlock(InBlock
));
860 if (In1
.isOverdefined() || In2
.isOverdefined()) {
861 Result
.markOverdefined();
862 break; // Cannot fold this operation over the PHI nodes!
863 } else if (In1
.isConstant() && In2
.isConstant()) {
865 ConstantExpr::get(I
.getOpcode(), In1
.getConstant(),
867 if (Result
.isUndefined())
868 Result
.markConstant(V
);
869 else if (Result
.isConstant() && Result
.getConstant() != V
) {
870 Result
.markOverdefined();
876 // If we found a constant value here, then we know the instruction is
877 // constant despite the fact that the PHI nodes are overdefined.
878 if (Result
.isConstant()) {
879 markConstant(IV
, &I
, Result
.getConstant());
880 // Remember that this instruction is virtually using the PHI node
882 UsersOfOverdefinedPHIs
.insert(std::make_pair(PN1
, &I
));
883 UsersOfOverdefinedPHIs
.insert(std::make_pair(PN2
, &I
));
885 } else if (Result
.isUndefined()) {
889 // Okay, this really is overdefined now. Since we might have
890 // speculatively thought that this was not overdefined before, and
891 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
892 // make sure to clean out any entries that we put there, for
894 std::multimap
<PHINode
*, Instruction
*>::iterator It
, E
;
895 tie(It
, E
) = UsersOfOverdefinedPHIs
.equal_range(PN1
);
897 if (It
->second
== &I
) {
898 UsersOfOverdefinedPHIs
.erase(It
++);
902 tie(It
, E
) = UsersOfOverdefinedPHIs
.equal_range(PN2
);
904 if (It
->second
== &I
) {
905 UsersOfOverdefinedPHIs
.erase(It
++);
911 markOverdefined(IV
, &I
);
912 } else if (V1State
.isConstant() && V2State
.isConstant()) {
914 ConstantExpr::get(I
.getOpcode(), V1State
.getConstant(),
915 V2State
.getConstant()));
919 // Handle ICmpInst instruction...
920 void SCCPSolver::visitCmpInst(CmpInst
&I
) {
921 LatticeVal
&IV
= ValueState
[&I
];
922 if (IV
.isOverdefined()) return;
924 LatticeVal
&V1State
= getValueState(I
.getOperand(0));
925 LatticeVal
&V2State
= getValueState(I
.getOperand(1));
927 if (V1State
.isOverdefined() || V2State
.isOverdefined()) {
928 // If both operands are PHI nodes, it is possible that this instruction has
929 // a constant value, despite the fact that the PHI node doesn't. Check for
930 // this condition now.
931 if (PHINode
*PN1
= dyn_cast
<PHINode
>(I
.getOperand(0)))
932 if (PHINode
*PN2
= dyn_cast
<PHINode
>(I
.getOperand(1)))
933 if (PN1
->getParent() == PN2
->getParent()) {
934 // Since the two PHI nodes are in the same basic block, they must have
935 // entries for the same predecessors. Walk the predecessor list, and
936 // if all of the incoming values are constants, and the result of
937 // evaluating this expression with all incoming value pairs is the
938 // same, then this expression is a constant even though the PHI node
939 // is not a constant!
941 for (unsigned i
= 0, e
= PN1
->getNumIncomingValues(); i
!= e
; ++i
) {
942 LatticeVal
&In1
= getValueState(PN1
->getIncomingValue(i
));
943 BasicBlock
*InBlock
= PN1
->getIncomingBlock(i
);
945 getValueState(PN2
->getIncomingValueForBlock(InBlock
));
947 if (In1
.isOverdefined() || In2
.isOverdefined()) {
948 Result
.markOverdefined();
949 break; // Cannot fold this operation over the PHI nodes!
950 } else if (In1
.isConstant() && In2
.isConstant()) {
951 Constant
*V
= ConstantExpr::getCompare(I
.getPredicate(),
954 if (Result
.isUndefined())
955 Result
.markConstant(V
);
956 else if (Result
.isConstant() && Result
.getConstant() != V
) {
957 Result
.markOverdefined();
963 // If we found a constant value here, then we know the instruction is
964 // constant despite the fact that the PHI nodes are overdefined.
965 if (Result
.isConstant()) {
966 markConstant(IV
, &I
, Result
.getConstant());
967 // Remember that this instruction is virtually using the PHI node
969 UsersOfOverdefinedPHIs
.insert(std::make_pair(PN1
, &I
));
970 UsersOfOverdefinedPHIs
.insert(std::make_pair(PN2
, &I
));
972 } else if (Result
.isUndefined()) {
976 // Okay, this really is overdefined now. Since we might have
977 // speculatively thought that this was not overdefined before, and
978 // added ourselves to the UsersOfOverdefinedPHIs list for the PHIs,
979 // make sure to clean out any entries that we put there, for
981 std::multimap
<PHINode
*, Instruction
*>::iterator It
, E
;
982 tie(It
, E
) = UsersOfOverdefinedPHIs
.equal_range(PN1
);
984 if (It
->second
== &I
) {
985 UsersOfOverdefinedPHIs
.erase(It
++);
989 tie(It
, E
) = UsersOfOverdefinedPHIs
.equal_range(PN2
);
991 if (It
->second
== &I
) {
992 UsersOfOverdefinedPHIs
.erase(It
++);
998 markOverdefined(IV
, &I
);
999 } else if (V1State
.isConstant() && V2State
.isConstant()) {
1000 markConstant(IV
, &I
, ConstantExpr::getCompare(I
.getPredicate(),
1001 V1State
.getConstant(),
1002 V2State
.getConstant()));
1006 void SCCPSolver::visitExtractElementInst(ExtractElementInst
&I
) {
1007 // FIXME : SCCP does not handle vectors properly.
1008 markOverdefined(&I
);
1012 LatticeVal
&ValState
= getValueState(I
.getOperand(0));
1013 LatticeVal
&IdxState
= getValueState(I
.getOperand(1));
1015 if (ValState
.isOverdefined() || IdxState
.isOverdefined())
1016 markOverdefined(&I
);
1017 else if(ValState
.isConstant() && IdxState
.isConstant())
1018 markConstant(&I
, ConstantExpr::getExtractElement(ValState
.getConstant(),
1019 IdxState
.getConstant()));
1023 void SCCPSolver::visitInsertElementInst(InsertElementInst
&I
) {
1024 // FIXME : SCCP does not handle vectors properly.
1025 markOverdefined(&I
);
1028 LatticeVal
&ValState
= getValueState(I
.getOperand(0));
1029 LatticeVal
&EltState
= getValueState(I
.getOperand(1));
1030 LatticeVal
&IdxState
= getValueState(I
.getOperand(2));
1032 if (ValState
.isOverdefined() || EltState
.isOverdefined() ||
1033 IdxState
.isOverdefined())
1034 markOverdefined(&I
);
1035 else if(ValState
.isConstant() && EltState
.isConstant() &&
1036 IdxState
.isConstant())
1037 markConstant(&I
, ConstantExpr::getInsertElement(ValState
.getConstant(),
1038 EltState
.getConstant(),
1039 IdxState
.getConstant()));
1040 else if (ValState
.isUndefined() && EltState
.isConstant() &&
1041 IdxState
.isConstant())
1042 markConstant(&I
,ConstantExpr::getInsertElement(UndefValue::get(I
.getType()),
1043 EltState
.getConstant(),
1044 IdxState
.getConstant()));
1048 void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst
&I
) {
1049 // FIXME : SCCP does not handle vectors properly.
1050 markOverdefined(&I
);
1053 LatticeVal
&V1State
= getValueState(I
.getOperand(0));
1054 LatticeVal
&V2State
= getValueState(I
.getOperand(1));
1055 LatticeVal
&MaskState
= getValueState(I
.getOperand(2));
1057 if (MaskState
.isUndefined() ||
1058 (V1State
.isUndefined() && V2State
.isUndefined()))
1059 return; // Undefined output if mask or both inputs undefined.
1061 if (V1State
.isOverdefined() || V2State
.isOverdefined() ||
1062 MaskState
.isOverdefined()) {
1063 markOverdefined(&I
);
1065 // A mix of constant/undef inputs.
1066 Constant
*V1
= V1State
.isConstant() ?
1067 V1State
.getConstant() : UndefValue::get(I
.getType());
1068 Constant
*V2
= V2State
.isConstant() ?
1069 V2State
.getConstant() : UndefValue::get(I
.getType());
1070 Constant
*Mask
= MaskState
.isConstant() ?
1071 MaskState
.getConstant() : UndefValue::get(I
.getOperand(2)->getType());
1072 markConstant(&I
, ConstantExpr::getShuffleVector(V1
, V2
, Mask
));
1077 // Handle getelementptr instructions... if all operands are constants then we
1078 // can turn this into a getelementptr ConstantExpr.
1080 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst
&I
) {
1081 LatticeVal
&IV
= ValueState
[&I
];
1082 if (IV
.isOverdefined()) return;
1084 SmallVector
<Constant
*, 8> Operands
;
1085 Operands
.reserve(I
.getNumOperands());
1087 for (unsigned i
= 0, e
= I
.getNumOperands(); i
!= e
; ++i
) {
1088 LatticeVal
&State
= getValueState(I
.getOperand(i
));
1089 if (State
.isUndefined())
1090 return; // Operands are not resolved yet...
1091 else if (State
.isOverdefined()) {
1092 markOverdefined(IV
, &I
);
1095 assert(State
.isConstant() && "Unknown state!");
1096 Operands
.push_back(State
.getConstant());
1099 Constant
*Ptr
= Operands
[0];
1100 Operands
.erase(Operands
.begin()); // Erase the pointer from idx list...
1102 markConstant(IV
, &I
, ConstantExpr::getGetElementPtr(Ptr
, &Operands
[0],
1106 void SCCPSolver::visitStoreInst(Instruction
&SI
) {
1107 if (TrackedGlobals
.empty() || !isa
<GlobalVariable
>(SI
.getOperand(1)))
1109 GlobalVariable
*GV
= cast
<GlobalVariable
>(SI
.getOperand(1));
1110 DenseMap
<GlobalVariable
*, LatticeVal
>::iterator I
= TrackedGlobals
.find(GV
);
1111 if (I
== TrackedGlobals
.end() || I
->second
.isOverdefined()) return;
1113 // Get the value we are storing into the global.
1114 LatticeVal
&PtrVal
= getValueState(SI
.getOperand(0));
1116 mergeInValue(I
->second
, GV
, PtrVal
);
1117 if (I
->second
.isOverdefined())
1118 TrackedGlobals
.erase(I
); // No need to keep tracking this!
1122 // Handle load instructions. If the operand is a constant pointer to a constant
1123 // global, we can replace the load with the loaded constant value!
1124 void SCCPSolver::visitLoadInst(LoadInst
&I
) {
1125 LatticeVal
&IV
= ValueState
[&I
];
1126 if (IV
.isOverdefined()) return;
1128 LatticeVal
&PtrVal
= getValueState(I
.getOperand(0));
1129 if (PtrVal
.isUndefined()) return; // The pointer is not resolved yet!
1130 if (PtrVal
.isConstant() && !I
.isVolatile()) {
1131 Value
*Ptr
= PtrVal
.getConstant();
1132 // TODO: Consider a target hook for valid address spaces for this xform.
1133 if (isa
<ConstantPointerNull
>(Ptr
) && I
.getPointerAddressSpace() == 0) {
1134 // load null -> null
1135 markConstant(IV
, &I
, Constant::getNullValue(I
.getType()));
1139 // Transform load (constant global) into the value loaded.
1140 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(Ptr
)) {
1141 if (GV
->isConstant()) {
1142 if (GV
->hasDefinitiveInitializer()) {
1143 markConstant(IV
, &I
, GV
->getInitializer());
1146 } else if (!TrackedGlobals
.empty()) {
1147 // If we are tracking this global, merge in the known value for it.
1148 DenseMap
<GlobalVariable
*, LatticeVal
>::iterator It
=
1149 TrackedGlobals
.find(GV
);
1150 if (It
!= TrackedGlobals
.end()) {
1151 mergeInValue(IV
, &I
, It
->second
);
1157 // Transform load (constantexpr_GEP global, 0, ...) into the value loaded.
1158 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(Ptr
))
1159 if (CE
->getOpcode() == Instruction::GetElementPtr
)
1160 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(CE
->getOperand(0)))
1161 if (GV
->isConstant() && GV
->hasDefinitiveInitializer())
1163 ConstantFoldLoadThroughGEPConstantExpr(GV
->getInitializer(), CE
,
1165 markConstant(IV
, &I
, V
);
1170 // Otherwise we cannot say for certain what value this load will produce.
1172 markOverdefined(IV
, &I
);
1175 void SCCPSolver::visitCallSite(CallSite CS
) {
1176 Function
*F
= CS
.getCalledFunction();
1177 Instruction
*I
= CS
.getInstruction();
1179 // The common case is that we aren't tracking the callee, either because we
1180 // are not doing interprocedural analysis or the callee is indirect, or is
1181 // external. Handle these cases first.
1182 if (F
== 0 || !F
->hasLocalLinkage()) {
1184 // Void return and not tracking callee, just bail.
1185 if (I
->getType() == Type::getVoidTy(I
->getContext())) return;
1187 // Otherwise, if we have a single return value case, and if the function is
1188 // a declaration, maybe we can constant fold it.
1189 if (!isa
<StructType
>(I
->getType()) && F
&& F
->isDeclaration() &&
1190 canConstantFoldCallTo(F
)) {
1192 SmallVector
<Constant
*, 8> Operands
;
1193 for (CallSite::arg_iterator AI
= CS
.arg_begin(), E
= CS
.arg_end();
1195 LatticeVal
&State
= getValueState(*AI
);
1196 if (State
.isUndefined())
1197 return; // Operands are not resolved yet.
1198 else if (State
.isOverdefined()) {
1202 assert(State
.isConstant() && "Unknown state!");
1203 Operands
.push_back(State
.getConstant());
1206 // If we can constant fold this, mark the result of the call as a
1208 if (Constant
*C
= ConstantFoldCall(F
, Operands
.data(), Operands
.size())) {
1214 // Otherwise, we don't know anything about this call, mark it overdefined.
1219 // If this is a single/zero retval case, see if we're tracking the function.
1220 DenseMap
<Function
*, LatticeVal
>::iterator TFRVI
= TrackedRetVals
.find(F
);
1221 if (TFRVI
!= TrackedRetVals
.end()) {
1222 // If so, propagate the return value of the callee into this call result.
1223 mergeInValue(I
, TFRVI
->second
);
1224 } else if (isa
<StructType
>(I
->getType())) {
1225 // Check to see if we're tracking this callee, if not, handle it in the
1226 // common path above.
1227 DenseMap
<std::pair
<Function
*, unsigned>, LatticeVal
>::iterator
1228 TMRVI
= TrackedMultipleRetVals
.find(std::make_pair(F
, 0));
1229 if (TMRVI
== TrackedMultipleRetVals
.end())
1230 goto CallOverdefined
;
1232 // If we are tracking this callee, propagate the return values of the call
1233 // into this call site. We do this by walking all the uses. Single-index
1234 // ExtractValueInst uses can be tracked; anything more complicated is
1235 // currently handled conservatively.
1236 for (Value::use_iterator UI
= I
->use_begin(), E
= I
->use_end();
1238 if (ExtractValueInst
*EVI
= dyn_cast
<ExtractValueInst
>(*UI
)) {
1239 if (EVI
->getNumIndices() == 1) {
1241 TrackedMultipleRetVals
[std::make_pair(F
, *EVI
->idx_begin())]);
1245 // The aggregate value is used in a way not handled here. Assume nothing.
1246 markOverdefined(*UI
);
1249 // Otherwise we're not tracking this callee, so handle it in the
1250 // common path above.
1251 goto CallOverdefined
;
1254 // Finally, if this is the first call to the function hit, mark its entry
1255 // block executable.
1256 if (!BBExecutable
.count(F
->begin()))
1257 MarkBlockExecutable(F
->begin());
1259 // Propagate information from this call site into the callee.
1260 CallSite::arg_iterator CAI
= CS
.arg_begin();
1261 for (Function::arg_iterator AI
= F
->arg_begin(), E
= F
->arg_end();
1262 AI
!= E
; ++AI
, ++CAI
) {
1263 LatticeVal
&IV
= ValueState
[AI
];
1264 if (!IV
.isOverdefined())
1265 mergeInValue(IV
, AI
, getValueState(*CAI
));
1270 void SCCPSolver::Solve() {
1271 // Process the work lists until they are empty!
1272 while (!BBWorkList
.empty() || !InstWorkList
.empty() ||
1273 !OverdefinedInstWorkList
.empty()) {
1274 // Process the instruction work list...
1275 while (!OverdefinedInstWorkList
.empty()) {
1276 Value
*I
= OverdefinedInstWorkList
.back();
1277 OverdefinedInstWorkList
.pop_back();
1279 DEBUG(errs() << "\nPopped off OI-WL: " << *I
<< '\n');
1281 // "I" got into the work list because it either made the transition from
1282 // bottom to constant
1284 // Anything on this worklist that is overdefined need not be visited
1285 // since all of its users will have already been marked as overdefined
1286 // Update all of the users of this instruction's value...
1288 for (Value::use_iterator UI
= I
->use_begin(), E
= I
->use_end();
1290 OperandChangedState(*UI
);
1292 // Process the instruction work list...
1293 while (!InstWorkList
.empty()) {
1294 Value
*I
= InstWorkList
.back();
1295 InstWorkList
.pop_back();
1297 DEBUG(errs() << "\nPopped off I-WL: " << *I
<< '\n');
1299 // "I" got into the work list because it either made the transition from
1300 // bottom to constant
1302 // Anything on this worklist that is overdefined need not be visited
1303 // since all of its users will have already been marked as overdefined.
1304 // Update all of the users of this instruction's value...
1306 if (!getValueState(I
).isOverdefined())
1307 for (Value::use_iterator UI
= I
->use_begin(), E
= I
->use_end();
1309 OperandChangedState(*UI
);
1312 // Process the basic block work list...
1313 while (!BBWorkList
.empty()) {
1314 BasicBlock
*BB
= BBWorkList
.back();
1315 BBWorkList
.pop_back();
1317 DEBUG(errs() << "\nPopped off BBWL: " << *BB
<< '\n');
1319 // Notify all instructions in this basic block that they are newly
1326 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
1327 /// that branches on undef values cannot reach any of their successors.
1328 /// However, this is not a safe assumption. After we solve dataflow, this
1329 /// method should be use to handle this. If this returns true, the solver
1330 /// should be rerun.
1332 /// This method handles this by finding an unresolved branch and marking it one
1333 /// of the edges from the block as being feasible, even though the condition
1334 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the
1335 /// CFG and only slightly pessimizes the analysis results (by marking one,
1336 /// potentially infeasible, edge feasible). This cannot usefully modify the
1337 /// constraints on the condition of the branch, as that would impact other users
1340 /// This scan also checks for values that use undefs, whose results are actually
1341 /// defined. For example, 'zext i8 undef to i32' should produce all zeros
1342 /// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero,
1343 /// even if X isn't defined.
1344 bool SCCPSolver::ResolvedUndefsIn(Function
&F
) {
1345 for (Function::iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
; ++BB
) {
1346 if (!BBExecutable
.count(BB
))
1349 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->end(); I
!= E
; ++I
) {
1350 // Look for instructions which produce undef values.
1351 if (I
->getType() == Type::getVoidTy(F
.getContext())) continue;
1353 LatticeVal
&LV
= getValueState(I
);
1354 if (!LV
.isUndefined()) continue;
1356 // Get the lattice values of the first two operands for use below.
1357 LatticeVal
&Op0LV
= getValueState(I
->getOperand(0));
1359 if (I
->getNumOperands() == 2) {
1360 // If this is a two-operand instruction, and if both operands are
1361 // undefs, the result stays undef.
1362 Op1LV
= getValueState(I
->getOperand(1));
1363 if (Op0LV
.isUndefined() && Op1LV
.isUndefined())
1367 // If this is an instructions whose result is defined even if the input is
1368 // not fully defined, propagate the information.
1369 const Type
*ITy
= I
->getType();
1370 switch (I
->getOpcode()) {
1371 default: break; // Leave the instruction as an undef.
1372 case Instruction::ZExt
:
1373 // After a zero extend, we know the top part is zero. SExt doesn't have
1374 // to be handled here, because we don't know whether the top part is 1's
1376 assert(Op0LV
.isUndefined());
1377 markForcedConstant(LV
, I
, Constant::getNullValue(ITy
));
1379 case Instruction::Mul
:
1380 case Instruction::And
:
1381 // undef * X -> 0. X could be zero.
1382 // undef & X -> 0. X could be zero.
1383 markForcedConstant(LV
, I
, Constant::getNullValue(ITy
));
1386 case Instruction::Or
:
1387 // undef | X -> -1. X could be -1.
1388 if (const VectorType
*PTy
= dyn_cast
<VectorType
>(ITy
))
1389 markForcedConstant(LV
, I
,
1390 Constant::getAllOnesValue(PTy
));
1392 markForcedConstant(LV
, I
, Constant::getAllOnesValue(ITy
));
1395 case Instruction::SDiv
:
1396 case Instruction::UDiv
:
1397 case Instruction::SRem
:
1398 case Instruction::URem
:
1399 // X / undef -> undef. No change.
1400 // X % undef -> undef. No change.
1401 if (Op1LV
.isUndefined()) break;
1403 // undef / X -> 0. X could be maxint.
1404 // undef % X -> 0. X could be 1.
1405 markForcedConstant(LV
, I
, Constant::getNullValue(ITy
));
1408 case Instruction::AShr
:
1409 // undef >>s X -> undef. No change.
1410 if (Op0LV
.isUndefined()) break;
1412 // X >>s undef -> X. X could be 0, X could have the high-bit known set.
1413 if (Op0LV
.isConstant())
1414 markForcedConstant(LV
, I
, Op0LV
.getConstant());
1416 markOverdefined(LV
, I
);
1418 case Instruction::LShr
:
1419 case Instruction::Shl
:
1420 // undef >> X -> undef. No change.
1421 // undef << X -> undef. No change.
1422 if (Op0LV
.isUndefined()) break;
1424 // X >> undef -> 0. X could be 0.
1425 // X << undef -> 0. X could be 0.
1426 markForcedConstant(LV
, I
, Constant::getNullValue(ITy
));
1428 case Instruction::Select
:
1429 // undef ? X : Y -> X or Y. There could be commonality between X/Y.
1430 if (Op0LV
.isUndefined()) {
1431 if (!Op1LV
.isConstant()) // Pick the constant one if there is any.
1432 Op1LV
= getValueState(I
->getOperand(2));
1433 } else if (Op1LV
.isUndefined()) {
1434 // c ? undef : undef -> undef. No change.
1435 Op1LV
= getValueState(I
->getOperand(2));
1436 if (Op1LV
.isUndefined())
1438 // Otherwise, c ? undef : x -> x.
1440 // Leave Op1LV as Operand(1)'s LatticeValue.
1443 if (Op1LV
.isConstant())
1444 markForcedConstant(LV
, I
, Op1LV
.getConstant());
1446 markOverdefined(LV
, I
);
1448 case Instruction::Call
:
1449 // If a call has an undef result, it is because it is constant foldable
1450 // but one of the inputs was undef. Just force the result to
1452 markOverdefined(LV
, I
);
1457 TerminatorInst
*TI
= BB
->getTerminator();
1458 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(TI
)) {
1459 if (!BI
->isConditional()) continue;
1460 if (!getValueState(BI
->getCondition()).isUndefined())
1462 } else if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(TI
)) {
1463 if (SI
->getNumSuccessors()<2) // no cases
1465 if (!getValueState(SI
->getCondition()).isUndefined())
1471 // If the edge to the second successor isn't thought to be feasible yet,
1472 // mark it so now. We pick the second one so that this goes to some
1473 // enumerated value in a switch instead of going to the default destination.
1474 if (KnownFeasibleEdges
.count(Edge(BB
, TI
->getSuccessor(1))))
1477 // Otherwise, it isn't already thought to be feasible. Mark it as such now
1478 // and return. This will make other blocks reachable, which will allow new
1479 // values to be discovered and existing ones to be moved in the lattice.
1480 markEdgeExecutable(BB
, TI
->getSuccessor(1));
1482 // This must be a conditional branch of switch on undef. At this point,
1483 // force the old terminator to branch to the first successor. This is
1484 // required because we are now influencing the dataflow of the function with
1485 // the assumption that this edge is taken. If we leave the branch condition
1486 // as undef, then further analysis could think the undef went another way
1487 // leading to an inconsistent set of conclusions.
1488 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(TI
)) {
1489 BI
->setCondition(ConstantInt::getFalse(*Context
));
1491 SwitchInst
*SI
= cast
<SwitchInst
>(TI
);
1492 SI
->setCondition(SI
->getCaseValue(1));
1503 //===--------------------------------------------------------------------===//
1505 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
1506 /// Sparse Conditional Constant Propagator.
1508 struct SCCP
: public FunctionPass
{
1509 static char ID
; // Pass identification, replacement for typeid
1510 SCCP() : FunctionPass(&ID
) {}
1512 // runOnFunction - Run the Sparse Conditional Constant Propagation
1513 // algorithm, and return true if the function was modified.
1515 bool runOnFunction(Function
&F
);
1517 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
1518 AU
.setPreservesCFG();
1521 } // end anonymous namespace
1524 static RegisterPass
<SCCP
>
1525 X("sccp", "Sparse Conditional Constant Propagation");
1527 // createSCCPPass - This is the public interface to this file...
1528 FunctionPass
*llvm::createSCCPPass() {
1533 // runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
1534 // and return true if the function was modified.
1536 bool SCCP::runOnFunction(Function
&F
) {
1537 DEBUG(errs() << "SCCP on function '" << F
.getName() << "'\n");
1539 Solver
.setContext(&F
.getContext());
1541 // Mark the first block of the function as being executable.
1542 Solver
.MarkBlockExecutable(F
.begin());
1544 // Mark all arguments to the function as being overdefined.
1545 for (Function::arg_iterator AI
= F
.arg_begin(), E
= F
.arg_end(); AI
!= E
;++AI
)
1546 Solver
.markOverdefined(AI
);
1548 // Solve for constants.
1549 bool ResolvedUndefs
= true;
1550 while (ResolvedUndefs
) {
1552 DEBUG(errs() << "RESOLVING UNDEFs\n");
1553 ResolvedUndefs
= Solver
.ResolvedUndefsIn(F
);
1556 bool MadeChanges
= false;
1558 // If we decided that there are basic blocks that are dead in this function,
1559 // delete their contents now. Note that we cannot actually delete the blocks,
1560 // as we cannot modify the CFG of the function.
1562 SmallVector
<Instruction
*, 512> Insts
;
1563 std::map
<Value
*, LatticeVal
> &Values
= Solver
.getValueMapping();
1565 for (Function::iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
; ++BB
)
1566 if (!Solver
.isBlockExecutable(BB
)) {
1567 DEBUG(errs() << " BasicBlock Dead:" << *BB
);
1570 // Delete the instructions backwards, as it has a reduced likelihood of
1571 // having to update as many def-use and use-def chains.
1572 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->getTerminator();
1575 while (!Insts
.empty()) {
1576 Instruction
*I
= Insts
.back();
1578 if (!I
->use_empty())
1579 I
->replaceAllUsesWith(UndefValue::get(I
->getType()));
1580 BB
->getInstList().erase(I
);
1585 // Iterate over all of the instructions in a function, replacing them with
1586 // constants if we have found them to be of constant values.
1588 for (BasicBlock::iterator BI
= BB
->begin(), E
= BB
->end(); BI
!= E
; ) {
1589 Instruction
*Inst
= BI
++;
1590 if (Inst
->getType() == Type::getVoidTy(F
.getContext()) ||
1591 isa
<TerminatorInst
>(Inst
))
1594 LatticeVal
&IV
= Values
[Inst
];
1595 if (!IV
.isConstant() && !IV
.isUndefined())
1598 Constant
*Const
= IV
.isConstant()
1599 ? IV
.getConstant() : UndefValue::get(Inst
->getType());
1600 DEBUG(errs() << " Constant: " << *Const
<< " = " << *Inst
);
1602 // Replaces all of the uses of a variable with uses of the constant.
1603 Inst
->replaceAllUsesWith(Const
);
1605 // Delete the instruction.
1606 Inst
->eraseFromParent();
1608 // Hey, we just changed something!
1618 //===--------------------------------------------------------------------===//
1620 /// IPSCCP Class - This class implements interprocedural Sparse Conditional
1621 /// Constant Propagation.
1623 struct IPSCCP
: public ModulePass
{
1625 IPSCCP() : ModulePass(&ID
) {}
1626 bool runOnModule(Module
&M
);
1628 } // end anonymous namespace
1630 char IPSCCP::ID
= 0;
1631 static RegisterPass
<IPSCCP
>
1632 Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
1634 // createIPSCCPPass - This is the public interface to this file...
1635 ModulePass
*llvm::createIPSCCPPass() {
1636 return new IPSCCP();
1640 static bool AddressIsTaken(GlobalValue
*GV
) {
1641 // Delete any dead constantexpr klingons.
1642 GV
->removeDeadConstantUsers();
1644 for (Value::use_iterator UI
= GV
->use_begin(), E
= GV
->use_end();
1646 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(*UI
)) {
1647 if (SI
->getOperand(0) == GV
|| SI
->isVolatile())
1648 return true; // Storing addr of GV.
1649 } else if (isa
<InvokeInst
>(*UI
) || isa
<CallInst
>(*UI
)) {
1650 // Make sure we are calling the function, not passing the address.
1651 CallSite CS
= CallSite::get(cast
<Instruction
>(*UI
));
1652 if (CS
.hasArgument(GV
))
1654 } else if (LoadInst
*LI
= dyn_cast
<LoadInst
>(*UI
)) {
1655 if (LI
->isVolatile())
1663 bool IPSCCP::runOnModule(Module
&M
) {
1664 LLVMContext
*Context
= &M
.getContext();
1667 Solver
.setContext(Context
);
1669 // Loop over all functions, marking arguments to those with their addresses
1670 // taken or that are external as overdefined.
1672 for (Module::iterator F
= M
.begin(), E
= M
.end(); F
!= E
; ++F
)
1673 if (!F
->hasLocalLinkage() || AddressIsTaken(F
)) {
1674 if (!F
->isDeclaration())
1675 Solver
.MarkBlockExecutable(F
->begin());
1676 for (Function::arg_iterator AI
= F
->arg_begin(), E
= F
->arg_end();
1678 Solver
.markOverdefined(AI
);
1680 Solver
.AddTrackedFunction(F
);
1683 // Loop over global variables. We inform the solver about any internal global
1684 // variables that do not have their 'addresses taken'. If they don't have
1685 // their addresses taken, we can propagate constants through them.
1686 for (Module::global_iterator G
= M
.global_begin(), E
= M
.global_end();
1688 if (!G
->isConstant() && G
->hasLocalLinkage() && !AddressIsTaken(G
))
1689 Solver
.TrackValueOfGlobalVariable(G
);
1691 // Solve for constants.
1692 bool ResolvedUndefs
= true;
1693 while (ResolvedUndefs
) {
1696 DEBUG(errs() << "RESOLVING UNDEFS\n");
1697 ResolvedUndefs
= false;
1698 for (Module::iterator F
= M
.begin(), E
= M
.end(); F
!= E
; ++F
)
1699 ResolvedUndefs
|= Solver
.ResolvedUndefsIn(*F
);
1702 bool MadeChanges
= false;
1704 // Iterate over all of the instructions in the module, replacing them with
1705 // constants if we have found them to be of constant values.
1707 SmallVector
<Instruction
*, 512> Insts
;
1708 SmallVector
<BasicBlock
*, 512> BlocksToErase
;
1709 std::map
<Value
*, LatticeVal
> &Values
= Solver
.getValueMapping();
1711 for (Module::iterator F
= M
.begin(), E
= M
.end(); F
!= E
; ++F
) {
1712 for (Function::arg_iterator AI
= F
->arg_begin(), E
= F
->arg_end();
1714 if (!AI
->use_empty()) {
1715 LatticeVal
&IV
= Values
[AI
];
1716 if (IV
.isConstant() || IV
.isUndefined()) {
1717 Constant
*CST
= IV
.isConstant() ?
1718 IV
.getConstant() : UndefValue::get(AI
->getType());
1719 DEBUG(errs() << "*** Arg " << *AI
<< " = " << *CST
<<"\n");
1721 // Replaces all of the uses of a variable with uses of the
1723 AI
->replaceAllUsesWith(CST
);
1728 for (Function::iterator BB
= F
->begin(), E
= F
->end(); BB
!= E
; ++BB
)
1729 if (!Solver
.isBlockExecutable(BB
)) {
1730 DEBUG(errs() << " BasicBlock Dead:" << *BB
);
1733 // Delete the instructions backwards, as it has a reduced likelihood of
1734 // having to update as many def-use and use-def chains.
1735 TerminatorInst
*TI
= BB
->getTerminator();
1736 for (BasicBlock::iterator I
= BB
->begin(), E
= TI
; I
!= E
; ++I
)
1739 while (!Insts
.empty()) {
1740 Instruction
*I
= Insts
.back();
1742 if (!I
->use_empty())
1743 I
->replaceAllUsesWith(UndefValue::get(I
->getType()));
1744 BB
->getInstList().erase(I
);
1749 for (unsigned i
= 0, e
= TI
->getNumSuccessors(); i
!= e
; ++i
) {
1750 BasicBlock
*Succ
= TI
->getSuccessor(i
);
1751 if (!Succ
->empty() && isa
<PHINode
>(Succ
->begin()))
1752 TI
->getSuccessor(i
)->removePredecessor(BB
);
1754 if (!TI
->use_empty())
1755 TI
->replaceAllUsesWith(UndefValue::get(TI
->getType()));
1756 BB
->getInstList().erase(TI
);
1758 if (&*BB
!= &F
->front())
1759 BlocksToErase
.push_back(BB
);
1761 new UnreachableInst(M
.getContext(), BB
);
1764 for (BasicBlock::iterator BI
= BB
->begin(), E
= BB
->end(); BI
!= E
; ) {
1765 Instruction
*Inst
= BI
++;
1766 if (Inst
->getType() == Type::getVoidTy(M
.getContext()))
1769 LatticeVal
&IV
= Values
[Inst
];
1770 if (!IV
.isConstant() && !IV
.isUndefined())
1773 Constant
*Const
= IV
.isConstant()
1774 ? IV
.getConstant() : UndefValue::get(Inst
->getType());
1775 DEBUG(errs() << " Constant: " << *Const
<< " = " << *Inst
);
1777 // Replaces all of the uses of a variable with uses of the
1779 Inst
->replaceAllUsesWith(Const
);
1781 // Delete the instruction.
1782 if (!isa
<CallInst
>(Inst
) && !isa
<TerminatorInst
>(Inst
))
1783 Inst
->eraseFromParent();
1785 // Hey, we just changed something!
1791 // Now that all instructions in the function are constant folded, erase dead
1792 // blocks, because we can now use ConstantFoldTerminator to get rid of
1794 for (unsigned i
= 0, e
= BlocksToErase
.size(); i
!= e
; ++i
) {
1795 // If there are any PHI nodes in this successor, drop entries for BB now.
1796 BasicBlock
*DeadBB
= BlocksToErase
[i
];
1797 while (!DeadBB
->use_empty()) {
1798 Instruction
*I
= cast
<Instruction
>(DeadBB
->use_back());
1799 bool Folded
= ConstantFoldTerminator(I
->getParent());
1801 // The constant folder may not have been able to fold the terminator
1802 // if this is a branch or switch on undef. Fold it manually as a
1803 // branch to the first successor.
1805 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(I
)) {
1806 assert(BI
->isConditional() && isa
<UndefValue
>(BI
->getCondition()) &&
1807 "Branch should be foldable!");
1808 } else if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(I
)) {
1809 assert(isa
<UndefValue
>(SI
->getCondition()) && "Switch should fold");
1811 llvm_unreachable("Didn't fold away reference to block!");
1815 // Make this an uncond branch to the first successor.
1816 TerminatorInst
*TI
= I
->getParent()->getTerminator();
1817 BranchInst::Create(TI
->getSuccessor(0), TI
);
1819 // Remove entries in successor phi nodes to remove edges.
1820 for (unsigned i
= 1, e
= TI
->getNumSuccessors(); i
!= e
; ++i
)
1821 TI
->getSuccessor(i
)->removePredecessor(TI
->getParent());
1823 // Remove the old terminator.
1824 TI
->eraseFromParent();
1828 // Finally, delete the basic block.
1829 F
->getBasicBlockList().erase(DeadBB
);
1831 BlocksToErase
.clear();
1834 // If we inferred constant or undef return values for a function, we replaced
1835 // all call uses with the inferred value. This means we don't need to bother
1836 // actually returning anything from the function. Replace all return
1837 // instructions with return undef.
1838 // TODO: Process multiple value ret instructions also.
1839 const DenseMap
<Function
*, LatticeVal
> &RV
= Solver
.getTrackedRetVals();
1840 for (DenseMap
<Function
*, LatticeVal
>::const_iterator I
= RV
.begin(),
1841 E
= RV
.end(); I
!= E
; ++I
)
1842 if (!I
->second
.isOverdefined() &&
1843 I
->first
->getReturnType() != Type::getVoidTy(M
.getContext())) {
1844 Function
*F
= I
->first
;
1845 for (Function::iterator BB
= F
->begin(), E
= F
->end(); BB
!= E
; ++BB
)
1846 if (ReturnInst
*RI
= dyn_cast
<ReturnInst
>(BB
->getTerminator()))
1847 if (!isa
<UndefValue
>(RI
->getOperand(0)))
1848 RI
->setOperand(0, UndefValue::get(F
->getReturnType()));
1851 // If we infered constant or undef values for globals variables, we can delete
1852 // the global and any stores that remain to it.
1853 const DenseMap
<GlobalVariable
*, LatticeVal
> &TG
= Solver
.getTrackedGlobals();
1854 for (DenseMap
<GlobalVariable
*, LatticeVal
>::const_iterator I
= TG
.begin(),
1855 E
= TG
.end(); I
!= E
; ++I
) {
1856 GlobalVariable
*GV
= I
->first
;
1857 assert(!I
->second
.isOverdefined() &&
1858 "Overdefined values should have been taken out of the map!");
1859 DEBUG(errs() << "Found that GV '" << GV
->getName() << "' is constant!\n");
1860 while (!GV
->use_empty()) {
1861 StoreInst
*SI
= cast
<StoreInst
>(GV
->use_back());
1862 SI
->eraseFromParent();
1864 M
.getGlobalList().erase(GV
);