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
18
//===----------------------------------------------------------------------===//
20
#include "llvm/Transforms/Scalar.h"
21
#include "llvm/ADT/DenseMap.h"
22
#include "llvm/ADT/DenseSet.h"
23
#include "llvm/ADT/PointerIntPair.h"
24
#include "llvm/ADT/SmallPtrSet.h"
25
#include "llvm/ADT/SmallVector.h"
26
#include "llvm/ADT/Statistic.h"
27
#include "llvm/Analysis/ConstantFolding.h"
28
#include "llvm/Analysis/TargetLibraryInfo.h"
29
#include "llvm/IR/CallSite.h"
30
#include "llvm/IR/Constants.h"
31
#include "llvm/IR/DataLayout.h"
32
#include "llvm/IR/DerivedTypes.h"
33
#include "llvm/IR/InstVisitor.h"
34
#include "llvm/IR/Instructions.h"
35
#include "llvm/Pass.h"
36
#include "llvm/Support/Debug.h"
37
#include "llvm/Support/ErrorHandling.h"
38
#include "llvm/Support/raw_ostream.h"
39
#include "llvm/Transforms/IPO.h"
40
#include "llvm/Transforms/Utils/Local.h"
44
#define DEBUG_TYPE "sccp"
46
STATISTIC(NumInstRemoved, "Number of instructions removed");
47
STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
49
STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
50
STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
51
STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
54
/// LatticeVal class - This class represents the different lattice values that
55
/// an LLVM value may occupy. It is a simple class with value semantics.
59
/// undefined - This LLVM Value has no known value yet.
62
/// constant - This LLVM Value has a specific constant value.
65
/// forcedconstant - This LLVM Value was thought to be undef until
66
/// ResolvedUndefsIn. This is treated just like 'constant', but if merged
67
/// with another (different) constant, it goes to overdefined, instead of
71
/// overdefined - This instruction is not known to be constant, and we know
76
/// Val: This stores the current lattice value along with the Constant* for
77
/// the constant if this is a 'constant' or 'forcedconstant' value.
78
PointerIntPair<Constant *, 2, LatticeValueTy> Val;
80
LatticeValueTy getLatticeValue() const {
85
LatticeVal() : Val(nullptr, undefined) {}
87
bool isUndefined() const { return getLatticeValue() == undefined; }
88
bool isConstant() const {
89
return getLatticeValue() == constant || getLatticeValue() == forcedconstant;
91
bool isOverdefined() const { return getLatticeValue() == overdefined; }
93
Constant *getConstant() const {
94
assert(isConstant() && "Cannot get the constant of a non-constant!");
95
return Val.getPointer();
98
/// markOverdefined - Return true if this is a change in status.
99
bool markOverdefined() {
103
Val.setInt(overdefined);
107
/// markConstant - Return true if this is a change in status.
108
bool markConstant(Constant *V) {
109
if (getLatticeValue() == constant) { // Constant but not forcedconstant.
110
assert(getConstant() == V && "Marking constant with different value");
115
Val.setInt(constant);
116
assert(V && "Marking constant with NULL");
119
assert(getLatticeValue() == forcedconstant &&
120
"Cannot move from overdefined to constant!");
121
// Stay at forcedconstant if the constant is the same.
122
if (V == getConstant()) return false;
124
// Otherwise, we go to overdefined. Assumptions made based on the
125
// forced value are possibly wrong. Assuming this is another constant
126
// could expose a contradiction.
127
Val.setInt(overdefined);
132
/// getConstantInt - If this is a constant with a ConstantInt value, return it
133
/// otherwise return null.
134
ConstantInt *getConstantInt() const {
136
return dyn_cast<ConstantInt>(getConstant());
140
void markForcedConstant(Constant *V) {
141
assert(isUndefined() && "Can't force a defined value!");
142
Val.setInt(forcedconstant);
146
} // end anonymous namespace.
151
//===----------------------------------------------------------------------===//
153
/// SCCPSolver - This class is a general purpose solver for Sparse Conditional
154
/// Constant Propagation.
156
class SCCPSolver : public InstVisitor<SCCPSolver> {
157
const DataLayout &DL;
158
const TargetLibraryInfo *TLI;
159
SmallPtrSet<BasicBlock*, 8> BBExecutable; // The BBs that are executable.
160
DenseMap<Value*, LatticeVal> ValueState; // The state each value is in.
162
/// StructValueState - This maintains ValueState for values that have
163
/// StructType, for example for formal arguments, calls, insertelement, etc.
165
DenseMap<std::pair<Value*, unsigned>, LatticeVal> StructValueState;
167
/// GlobalValue - If we are tracking any values for the contents of a global
168
/// variable, we keep a mapping from the constant accessor to the element of
169
/// the global, to the currently known value. If the value becomes
170
/// overdefined, it's entry is simply removed from this map.
171
DenseMap<GlobalVariable*, LatticeVal> TrackedGlobals;
173
/// TrackedRetVals - If we are tracking arguments into and the return
174
/// value out of a function, it will have an entry in this map, indicating
175
/// what the known return value for the function is.
176
DenseMap<Function*, LatticeVal> TrackedRetVals;
178
/// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
179
/// that return multiple values.
180
DenseMap<std::pair<Function*, unsigned>, LatticeVal> TrackedMultipleRetVals;
182
/// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
183
/// represented here for efficient lookup.
184
SmallPtrSet<Function*, 16> MRVFunctionsTracked;
186
/// TrackingIncomingArguments - This is the set of functions for whose
187
/// arguments we make optimistic assumptions about and try to prove as
189
SmallPtrSet<Function*, 16> TrackingIncomingArguments;
191
/// The reason for two worklists is that overdefined is the lowest state
192
/// on the lattice, and moving things to overdefined as fast as possible
193
/// makes SCCP converge much faster.
195
/// By having a separate worklist, we accomplish this because everything
196
/// possibly overdefined will become overdefined at the soonest possible
198
SmallVector<Value*, 64> OverdefinedInstWorkList;
199
SmallVector<Value*, 64> InstWorkList;
202
SmallVector<BasicBlock*, 64> BBWorkList; // The BasicBlock work list
204
/// KnownFeasibleEdges - Entries in this set are edges which have already had
205
/// PHI nodes retriggered.
206
typedef std::pair<BasicBlock*, BasicBlock*> Edge;
207
DenseSet<Edge> KnownFeasibleEdges;
209
SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli)
210
: DL(DL), TLI(tli) {}
212
/// MarkBlockExecutable - This method can be used by clients to mark all of
213
/// the blocks that are known to be intrinsically live in the processed unit.
215
/// This returns true if the block was not considered live before.
216
bool MarkBlockExecutable(BasicBlock *BB) {
217
if (!BBExecutable.insert(BB).second)
219
DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
220
BBWorkList.push_back(BB); // Add the block to the work list!
224
/// TrackValueOfGlobalVariable - Clients can use this method to
225
/// inform the SCCPSolver that it should track loads and stores to the
226
/// specified global variable if it can. This is only legal to call if
227
/// performing Interprocedural SCCP.
228
void TrackValueOfGlobalVariable(GlobalVariable *GV) {
229
// We only track the contents of scalar globals.
230
if (GV->getType()->getElementType()->isSingleValueType()) {
231
LatticeVal &IV = TrackedGlobals[GV];
232
if (!isa<UndefValue>(GV->getInitializer()))
233
IV.markConstant(GV->getInitializer());
237
/// AddTrackedFunction - If the SCCP solver is supposed to track calls into
238
/// and out of the specified function (which cannot have its address taken),
239
/// this method must be called.
240
void AddTrackedFunction(Function *F) {
241
// Add an entry, F -> undef.
242
if (StructType *STy = dyn_cast<StructType>(F->getReturnType())) {
243
MRVFunctionsTracked.insert(F);
244
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
245
TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i),
248
TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
251
void AddArgumentTrackedFunction(Function *F) {
252
TrackingIncomingArguments.insert(F);
255
/// Solve - Solve for constants and executable blocks.
259
/// ResolvedUndefsIn - While solving the dataflow for a function, we assume
260
/// that branches on undef values cannot reach any of their successors.
261
/// However, this is not a safe assumption. After we solve dataflow, this
262
/// method should be use to handle this. If this returns true, the solver
264
bool ResolvedUndefsIn(Function &F);
266
bool isBlockExecutable(BasicBlock *BB) const {
267
return BBExecutable.count(BB);
270
LatticeVal getLatticeValueFor(Value *V) const {
271
DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
272
assert(I != ValueState.end() && "V is not in valuemap!");
276
/// getTrackedRetVals - Get the inferred return value map.
278
const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
279
return TrackedRetVals;
282
/// getTrackedGlobals - Get and return the set of inferred initializers for
283
/// global variables.
284
const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() {
285
return TrackedGlobals;
288
void markOverdefined(Value *V) {
289
assert(!V->getType()->isStructTy() && "Should use other method");
290
markOverdefined(ValueState[V], V);
293
/// markAnythingOverdefined - Mark the specified value overdefined. This
294
/// works with both scalars and structs.
295
void markAnythingOverdefined(Value *V) {
296
if (StructType *STy = dyn_cast<StructType>(V->getType()))
297
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
298
markOverdefined(getStructValueState(V, i), V);
304
// markConstant - Make a value be marked as "constant". If the value
305
// is not already a constant, add it to the instruction work list so that
306
// the users of the instruction are updated later.
308
void markConstant(LatticeVal &IV, Value *V, Constant *C) {
309
if (!IV.markConstant(C)) return;
310
DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
311
if (IV.isOverdefined())
312
OverdefinedInstWorkList.push_back(V);
314
InstWorkList.push_back(V);
317
void markConstant(Value *V, Constant *C) {
318
assert(!V->getType()->isStructTy() && "Should use other method");
319
markConstant(ValueState[V], V, C);
322
void markForcedConstant(Value *V, Constant *C) {
323
assert(!V->getType()->isStructTy() && "Should use other method");
324
LatticeVal &IV = ValueState[V];
325
IV.markForcedConstant(C);
326
DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
327
if (IV.isOverdefined())
328
OverdefinedInstWorkList.push_back(V);
330
InstWorkList.push_back(V);
334
// markOverdefined - Make a value be marked as "overdefined". If the
335
// value is not already overdefined, add it to the overdefined instruction
336
// work list so that the users of the instruction are updated later.
337
void markOverdefined(LatticeVal &IV, Value *V) {
338
if (!IV.markOverdefined()) return;
340
DEBUG(dbgs() << "markOverdefined: ";
341
if (Function *F = dyn_cast<Function>(V))
342
dbgs() << "Function '" << F->getName() << "'\n";
344
dbgs() << *V << '\n');
345
// Only instructions go on the work list
346
OverdefinedInstWorkList.push_back(V);
349
void mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) {
350
if (IV.isOverdefined() || MergeWithV.isUndefined())
352
if (MergeWithV.isOverdefined())
353
markOverdefined(IV, V);
354
else if (IV.isUndefined())
355
markConstant(IV, V, MergeWithV.getConstant());
356
else if (IV.getConstant() != MergeWithV.getConstant())
357
markOverdefined(IV, V);
360
void mergeInValue(Value *V, LatticeVal MergeWithV) {
361
assert(!V->getType()->isStructTy() && "Should use other method");
362
mergeInValue(ValueState[V], V, MergeWithV);
366
/// getValueState - Return the LatticeVal object that corresponds to the
367
/// value. This function handles the case when the value hasn't been seen yet
368
/// by properly seeding constants etc.
369
LatticeVal &getValueState(Value *V) {
370
assert(!V->getType()->isStructTy() && "Should use getStructValueState");
372
std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I =
373
ValueState.insert(std::make_pair(V, LatticeVal()));
374
LatticeVal &LV = I.first->second;
377
return LV; // Common case, already in the map.
379
if (Constant *C = dyn_cast<Constant>(V)) {
380
// Undef values remain undefined.
381
if (!isa<UndefValue>(V))
382
LV.markConstant(C); // Constants are constant
385
// All others are underdefined by default.
389
/// getStructValueState - Return the LatticeVal object that corresponds to the
390
/// value/field pair. This function handles the case when the value hasn't
391
/// been seen yet by properly seeding constants etc.
392
LatticeVal &getStructValueState(Value *V, unsigned i) {
393
assert(V->getType()->isStructTy() && "Should use getValueState");
394
assert(i < cast<StructType>(V->getType())->getNumElements() &&
395
"Invalid element #");
397
std::pair<DenseMap<std::pair<Value*, unsigned>, LatticeVal>::iterator,
398
bool> I = StructValueState.insert(
399
std::make_pair(std::make_pair(V, i), LatticeVal()));
400
LatticeVal &LV = I.first->second;
403
return LV; // Common case, already in the map.
405
if (Constant *C = dyn_cast<Constant>(V)) {
406
Constant *Elt = C->getAggregateElement(i);
409
LV.markOverdefined(); // Unknown sort of constant.
410
else if (isa<UndefValue>(Elt))
411
; // Undef values remain undefined.
413
LV.markConstant(Elt); // Constants are constant.
416
// All others are underdefined by default.
421
/// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
422
/// work list if it is not already executable.
423
void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
424
if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
425
return; // This edge is already known to be executable!
427
if (!MarkBlockExecutable(Dest)) {
428
// If the destination is already executable, we just made an *edge*
429
// feasible that wasn't before. Revisit the PHI nodes in the block
430
// because they have potentially new operands.
431
DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
432
<< " -> " << Dest->getName() << '\n');
435
for (BasicBlock::iterator I = Dest->begin();
436
(PN = dyn_cast<PHINode>(I)); ++I)
441
// getFeasibleSuccessors - Return a vector of booleans to indicate which
442
// successors are reachable from a given terminator instruction.
444
void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs);
446
// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
447
// block to the 'To' basic block is currently feasible.
449
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
451
// OperandChangedState - This method is invoked on all of the users of an
452
// instruction that was just changed state somehow. Based on this
453
// information, we need to update the specified user of this instruction.
455
void OperandChangedState(Instruction *I) {
456
if (BBExecutable.count(I->getParent())) // Inst is executable?
461
friend class InstVisitor<SCCPSolver>;
463
// visit implementations - Something changed in this instruction. Either an
464
// operand made a transition, or the instruction is newly executable. Change
465
// the value type of I to reflect these changes if appropriate.
466
void visitPHINode(PHINode &I);
469
void visitReturnInst(ReturnInst &I);
470
void visitTerminatorInst(TerminatorInst &TI);
472
void visitCastInst(CastInst &I);
473
void visitSelectInst(SelectInst &I);
474
void visitBinaryOperator(Instruction &I);
475
void visitCmpInst(CmpInst &I);
476
void visitExtractElementInst(ExtractElementInst &I);
477
void visitInsertElementInst(InsertElementInst &I);
478
void visitShuffleVectorInst(ShuffleVectorInst &I);
479
void visitExtractValueInst(ExtractValueInst &EVI);
480
void visitInsertValueInst(InsertValueInst &IVI);
481
void visitLandingPadInst(LandingPadInst &I) { markAnythingOverdefined(&I); }
483
// Instructions that cannot be folded away.
484
void visitStoreInst (StoreInst &I);
485
void visitLoadInst (LoadInst &I);
486
void visitGetElementPtrInst(GetElementPtrInst &I);
487
void visitCallInst (CallInst &I) {
490
void visitInvokeInst (InvokeInst &II) {
492
visitTerminatorInst(II);
494
void visitCallSite (CallSite CS);
495
void visitResumeInst (TerminatorInst &I) { /*returns void*/ }
496
void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
497
void visitFenceInst (FenceInst &I) { /*returns void*/ }
498
void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) {
499
markAnythingOverdefined(&I);
501
void visitAtomicRMWInst (AtomicRMWInst &I) { markOverdefined(&I); }
502
void visitAllocaInst (Instruction &I) { markOverdefined(&I); }
503
void visitVAArgInst (Instruction &I) { markAnythingOverdefined(&I); }
505
void visitInstruction(Instruction &I) {
506
// If a new instruction is added to LLVM that we don't handle.
507
dbgs() << "SCCP: Don't know how to handle: " << I << '\n';
508
markAnythingOverdefined(&I); // Just in case
512
} // end anonymous namespace
515
// getFeasibleSuccessors - Return a vector of booleans to indicate which
516
// successors are reachable from a given terminator instruction.
518
void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
519
SmallVectorImpl<bool> &Succs) {
520
Succs.resize(TI.getNumSuccessors());
521
if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
522
if (BI->isUnconditional()) {
527
LatticeVal BCValue = getValueState(BI->getCondition());
528
ConstantInt *CI = BCValue.getConstantInt();
530
// Overdefined condition variables, and branches on unfoldable constant
531
// conditions, mean the branch could go either way.
532
if (!BCValue.isUndefined())
533
Succs[0] = Succs[1] = true;
537
// Constant condition variables mean the branch can only go a single way.
538
Succs[CI->isZero()] = true;
542
if (isa<InvokeInst>(TI)) {
543
// Invoke instructions successors are always executable.
544
Succs[0] = Succs[1] = true;
548
if (SwitchInst *SI = dyn_cast<SwitchInst>(&TI)) {
549
if (!SI->getNumCases()) {
553
LatticeVal SCValue = getValueState(SI->getCondition());
554
ConstantInt *CI = SCValue.getConstantInt();
556
if (!CI) { // Overdefined or undefined condition?
557
// All destinations are executable!
558
if (!SCValue.isUndefined())
559
Succs.assign(TI.getNumSuccessors(), true);
563
Succs[SI->findCaseValue(CI).getSuccessorIndex()] = true;
567
// TODO: This could be improved if the operand is a [cast of a] BlockAddress.
568
if (isa<IndirectBrInst>(&TI)) {
569
// Just mark all destinations executable!
570
Succs.assign(TI.getNumSuccessors(), true);
575
dbgs() << "Unknown terminator instruction: " << TI << '\n';
577
llvm_unreachable("SCCP: Don't know how to handle this terminator!");
581
// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
582
// block to the 'To' basic block is currently feasible.
584
bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
585
assert(BBExecutable.count(To) && "Dest should always be alive!");
587
// Make sure the source basic block is executable!!
588
if (!BBExecutable.count(From)) return false;
590
// Check to make sure this edge itself is actually feasible now.
591
TerminatorInst *TI = From->getTerminator();
592
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
593
if (BI->isUnconditional())
596
LatticeVal BCValue = getValueState(BI->getCondition());
598
// Overdefined condition variables mean the branch could go either way,
599
// undef conditions mean that neither edge is feasible yet.
600
ConstantInt *CI = BCValue.getConstantInt();
602
return !BCValue.isUndefined();
604
// Constant condition variables mean the branch can only go a single way.
605
return BI->getSuccessor(CI->isZero()) == To;
608
// Invoke instructions successors are always executable.
609
if (isa<InvokeInst>(TI))
612
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
613
if (SI->getNumCases() < 1)
616
LatticeVal SCValue = getValueState(SI->getCondition());
617
ConstantInt *CI = SCValue.getConstantInt();
620
return !SCValue.isUndefined();
622
return SI->findCaseValue(CI).getCaseSuccessor() == To;
625
// Just mark all destinations executable!
626
// TODO: This could be improved if the operand is a [cast of a] BlockAddress.
627
if (isa<IndirectBrInst>(TI))
631
dbgs() << "Unknown terminator instruction: " << *TI << '\n';
633
llvm_unreachable(nullptr);
636
// visit Implementations - Something changed in this instruction, either an
637
// operand made a transition, or the instruction is newly executable. Change
638
// the value type of I to reflect these changes if appropriate. This method
639
// makes sure to do the following actions:
641
// 1. If a phi node merges two constants in, and has conflicting value coming
642
// from different branches, or if the PHI node merges in an overdefined
643
// value, then the PHI node becomes overdefined.
644
// 2. If a phi node merges only constants in, and they all agree on value, the
645
// PHI node becomes a constant value equal to that.
646
// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
647
// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
648
// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
649
// 6. If a conditional branch has a value that is constant, make the selected
650
// destination executable
651
// 7. If a conditional branch has a value that is overdefined, make all
652
// successors executable.
654
void SCCPSolver::visitPHINode(PHINode &PN) {
655
// If this PN returns a struct, just mark the result overdefined.
656
// TODO: We could do a lot better than this if code actually uses this.
657
if (PN.getType()->isStructTy())
658
return markAnythingOverdefined(&PN);
660
if (getValueState(&PN).isOverdefined())
661
return; // Quick exit
663
// Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
664
// and slow us down a lot. Just mark them overdefined.
665
if (PN.getNumIncomingValues() > 64)
666
return markOverdefined(&PN);
668
// Look at all of the executable operands of the PHI node. If any of them
669
// are overdefined, the PHI becomes overdefined as well. If they are all
670
// constant, and they agree with each other, the PHI becomes the identical
671
// constant. If they are constant and don't agree, the PHI is overdefined.
672
// If there are no executable operands, the PHI remains undefined.
674
Constant *OperandVal = nullptr;
675
for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
676
LatticeVal IV = getValueState(PN.getIncomingValue(i));
677
if (IV.isUndefined()) continue; // Doesn't influence PHI node.
679
if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
682
if (IV.isOverdefined()) // PHI node becomes overdefined!
683
return markOverdefined(&PN);
685
if (!OperandVal) { // Grab the first value.
686
OperandVal = IV.getConstant();
690
// There is already a reachable operand. If we conflict with it,
691
// then the PHI node becomes overdefined. If we agree with it, we
694
// Check to see if there are two different constants merging, if so, the PHI
695
// node is overdefined.
696
if (IV.getConstant() != OperandVal)
697
return markOverdefined(&PN);
700
// If we exited the loop, this means that the PHI node only has constant
701
// arguments that agree with each other(and OperandVal is the constant) or
702
// OperandVal is null because there are no defined incoming arguments. If
703
// this is the case, the PHI remains undefined.
706
markConstant(&PN, OperandVal); // Acquire operand value
709
void SCCPSolver::visitReturnInst(ReturnInst &I) {
710
if (I.getNumOperands() == 0) return; // ret void
712
Function *F = I.getParent()->getParent();
713
Value *ResultOp = I.getOperand(0);
715
// If we are tracking the return value of this function, merge it in.
716
if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
717
DenseMap<Function*, LatticeVal>::iterator TFRVI =
718
TrackedRetVals.find(F);
719
if (TFRVI != TrackedRetVals.end()) {
720
mergeInValue(TFRVI->second, F, getValueState(ResultOp));
725
// Handle functions that return multiple values.
726
if (!TrackedMultipleRetVals.empty()) {
727
if (StructType *STy = dyn_cast<StructType>(ResultOp->getType()))
728
if (MRVFunctionsTracked.count(F))
729
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
730
mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
731
getStructValueState(ResultOp, i));
736
void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
737
SmallVector<bool, 16> SuccFeasible;
738
getFeasibleSuccessors(TI, SuccFeasible);
740
BasicBlock *BB = TI.getParent();
742
// Mark all feasible successors executable.
743
for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
745
markEdgeExecutable(BB, TI.getSuccessor(i));
748
void SCCPSolver::visitCastInst(CastInst &I) {
749
LatticeVal OpSt = getValueState(I.getOperand(0));
750
if (OpSt.isOverdefined()) // Inherit overdefinedness of operand
752
else if (OpSt.isConstant()) // Propagate constant value
753
markConstant(&I, ConstantExpr::getCast(I.getOpcode(),
754
OpSt.getConstant(), I.getType()));
758
void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
759
// If this returns a struct, mark all elements over defined, we don't track
760
// structs in structs.
761
if (EVI.getType()->isStructTy())
762
return markAnythingOverdefined(&EVI);
764
// If this is extracting from more than one level of struct, we don't know.
765
if (EVI.getNumIndices() != 1)
766
return markOverdefined(&EVI);
768
Value *AggVal = EVI.getAggregateOperand();
769
if (AggVal->getType()->isStructTy()) {
770
unsigned i = *EVI.idx_begin();
771
LatticeVal EltVal = getStructValueState(AggVal, i);
772
mergeInValue(getValueState(&EVI), &EVI, EltVal);
774
// Otherwise, must be extracting from an array.
775
return markOverdefined(&EVI);
779
void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
780
StructType *STy = dyn_cast<StructType>(IVI.getType());
782
return markOverdefined(&IVI);
784
// If this has more than one index, we can't handle it, drive all results to
786
if (IVI.getNumIndices() != 1)
787
return markAnythingOverdefined(&IVI);
789
Value *Aggr = IVI.getAggregateOperand();
790
unsigned Idx = *IVI.idx_begin();
792
// Compute the result based on what we're inserting.
793
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
794
// This passes through all values that aren't the inserted element.
796
LatticeVal EltVal = getStructValueState(Aggr, i);
797
mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
801
Value *Val = IVI.getInsertedValueOperand();
802
if (Val->getType()->isStructTy())
803
// We don't track structs in structs.
804
markOverdefined(getStructValueState(&IVI, i), &IVI);
806
LatticeVal InVal = getValueState(Val);
807
mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
812
void SCCPSolver::visitSelectInst(SelectInst &I) {
813
// If this select returns a struct, just mark the result overdefined.
814
// TODO: We could do a lot better than this if code actually uses this.
815
if (I.getType()->isStructTy())
816
return markAnythingOverdefined(&I);
818
LatticeVal CondValue = getValueState(I.getCondition());
819
if (CondValue.isUndefined())
822
if (ConstantInt *CondCB = CondValue.getConstantInt()) {
823
Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
824
mergeInValue(&I, getValueState(OpVal));
828
// Otherwise, the condition is overdefined or a constant we can't evaluate.
829
// See if we can produce something better than overdefined based on the T/F
831
LatticeVal TVal = getValueState(I.getTrueValue());
832
LatticeVal FVal = getValueState(I.getFalseValue());
834
// select ?, C, C -> C.
835
if (TVal.isConstant() && FVal.isConstant() &&
836
TVal.getConstant() == FVal.getConstant())
837
return markConstant(&I, FVal.getConstant());
839
if (TVal.isUndefined()) // select ?, undef, X -> X.
840
return mergeInValue(&I, FVal);
841
if (FVal.isUndefined()) // select ?, X, undef -> X.
842
return mergeInValue(&I, TVal);
846
// Handle Binary Operators.
847
void SCCPSolver::visitBinaryOperator(Instruction &I) {
848
LatticeVal V1State = getValueState(I.getOperand(0));
849
LatticeVal V2State = getValueState(I.getOperand(1));
851
LatticeVal &IV = ValueState[&I];
852
if (IV.isOverdefined()) return;
854
if (V1State.isConstant() && V2State.isConstant())
855
return markConstant(IV, &I,
856
ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
857
V2State.getConstant()));
859
// If something is undef, wait for it to resolve.
860
if (!V1State.isOverdefined() && !V2State.isOverdefined())
863
// Otherwise, one of our operands is overdefined. Try to produce something
864
// better than overdefined with some tricks.
866
// If this is an AND or OR with 0 or -1, it doesn't matter that the other
867
// operand is overdefined.
868
if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) {
869
LatticeVal *NonOverdefVal = nullptr;
870
if (!V1State.isOverdefined())
871
NonOverdefVal = &V1State;
872
else if (!V2State.isOverdefined())
873
NonOverdefVal = &V2State;
876
if (NonOverdefVal->isUndefined()) {
877
// Could annihilate value.
878
if (I.getOpcode() == Instruction::And)
879
markConstant(IV, &I, Constant::getNullValue(I.getType()));
880
else if (VectorType *PT = dyn_cast<VectorType>(I.getType()))
881
markConstant(IV, &I, Constant::getAllOnesValue(PT));
884
Constant::getAllOnesValue(I.getType()));
888
if (I.getOpcode() == Instruction::And) {
890
if (NonOverdefVal->getConstant()->isNullValue())
891
return markConstant(IV, &I, NonOverdefVal->getConstant());
893
if (ConstantInt *CI = NonOverdefVal->getConstantInt())
894
if (CI->isAllOnesValue()) // X or -1 = -1
895
return markConstant(IV, &I, NonOverdefVal->getConstant());
904
// Handle ICmpInst instruction.
905
void SCCPSolver::visitCmpInst(CmpInst &I) {
906
LatticeVal V1State = getValueState(I.getOperand(0));
907
LatticeVal V2State = getValueState(I.getOperand(1));
909
LatticeVal &IV = ValueState[&I];
910
if (IV.isOverdefined()) return;
912
if (V1State.isConstant() && V2State.isConstant())
913
return markConstant(IV, &I, ConstantExpr::getCompare(I.getPredicate(),
914
V1State.getConstant(),
915
V2State.getConstant()));
917
// If operands are still undefined, wait for it to resolve.
918
if (!V1State.isOverdefined() && !V2State.isOverdefined())
924
void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) {
925
// TODO : SCCP does not handle vectors properly.
926
return markOverdefined(&I);
929
LatticeVal &ValState = getValueState(I.getOperand(0));
930
LatticeVal &IdxState = getValueState(I.getOperand(1));
932
if (ValState.isOverdefined() || IdxState.isOverdefined())
934
else if(ValState.isConstant() && IdxState.isConstant())
935
markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(),
936
IdxState.getConstant()));
940
void SCCPSolver::visitInsertElementInst(InsertElementInst &I) {
941
// TODO : SCCP does not handle vectors properly.
942
return markOverdefined(&I);
944
LatticeVal &ValState = getValueState(I.getOperand(0));
945
LatticeVal &EltState = getValueState(I.getOperand(1));
946
LatticeVal &IdxState = getValueState(I.getOperand(2));
948
if (ValState.isOverdefined() || EltState.isOverdefined() ||
949
IdxState.isOverdefined())
951
else if(ValState.isConstant() && EltState.isConstant() &&
952
IdxState.isConstant())
953
markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(),
954
EltState.getConstant(),
955
IdxState.getConstant()));
956
else if (ValState.isUndefined() && EltState.isConstant() &&
957
IdxState.isConstant())
958
markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()),
959
EltState.getConstant(),
960
IdxState.getConstant()));
964
void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) {
965
// TODO : SCCP does not handle vectors properly.
966
return markOverdefined(&I);
968
LatticeVal &V1State = getValueState(I.getOperand(0));
969
LatticeVal &V2State = getValueState(I.getOperand(1));
970
LatticeVal &MaskState = getValueState(I.getOperand(2));
972
if (MaskState.isUndefined() ||
973
(V1State.isUndefined() && V2State.isUndefined()))
974
return; // Undefined output if mask or both inputs undefined.
976
if (V1State.isOverdefined() || V2State.isOverdefined() ||
977
MaskState.isOverdefined()) {
980
// A mix of constant/undef inputs.
981
Constant *V1 = V1State.isConstant() ?
982
V1State.getConstant() : UndefValue::get(I.getType());
983
Constant *V2 = V2State.isConstant() ?
984
V2State.getConstant() : UndefValue::get(I.getType());
985
Constant *Mask = MaskState.isConstant() ?
986
MaskState.getConstant() : UndefValue::get(I.getOperand(2)->getType());
987
markConstant(&I, ConstantExpr::getShuffleVector(V1, V2, Mask));
992
// Handle getelementptr instructions. If all operands are constants then we
993
// can turn this into a getelementptr ConstantExpr.
995
void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
996
if (ValueState[&I].isOverdefined()) return;
998
SmallVector<Constant*, 8> Operands;
999
Operands.reserve(I.getNumOperands());
1001
for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1002
LatticeVal State = getValueState(I.getOperand(i));
1003
if (State.isUndefined())
1004
return; // Operands are not resolved yet.
1006
if (State.isOverdefined())
1007
return markOverdefined(&I);
1009
assert(State.isConstant() && "Unknown state!");
1010
Operands.push_back(State.getConstant());
1013
Constant *Ptr = Operands[0];
1014
auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1015
markConstant(&I, ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr,
1019
void SCCPSolver::visitStoreInst(StoreInst &SI) {
1020
// If this store is of a struct, ignore it.
1021
if (SI.getOperand(0)->getType()->isStructTy())
1024
if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1027
GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1028
DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV);
1029
if (I == TrackedGlobals.end() || I->second.isOverdefined()) return;
1031
// Get the value we are storing into the global, then merge it.
1032
mergeInValue(I->second, GV, getValueState(SI.getOperand(0)));
1033
if (I->second.isOverdefined())
1034
TrackedGlobals.erase(I); // No need to keep tracking this!
1038
// Handle load instructions. If the operand is a constant pointer to a constant
1039
// global, we can replace the load with the loaded constant value!
1040
void SCCPSolver::visitLoadInst(LoadInst &I) {
1041
// If this load is of a struct, just mark the result overdefined.
1042
if (I.getType()->isStructTy())
1043
return markAnythingOverdefined(&I);
1045
LatticeVal PtrVal = getValueState(I.getOperand(0));
1046
if (PtrVal.isUndefined()) return; // The pointer is not resolved yet!
1048
LatticeVal &IV = ValueState[&I];
1049
if (IV.isOverdefined()) return;
1051
if (!PtrVal.isConstant() || I.isVolatile())
1052
return markOverdefined(IV, &I);
1054
Constant *Ptr = PtrVal.getConstant();
1056
// load null -> null
1057
if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0)
1058
return markConstant(IV, &I, UndefValue::get(I.getType()));
1060
// Transform load (constant global) into the value loaded.
1061
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
1062
if (!TrackedGlobals.empty()) {
1063
// If we are tracking this global, merge in the known value for it.
1064
DenseMap<GlobalVariable*, LatticeVal>::iterator It =
1065
TrackedGlobals.find(GV);
1066
if (It != TrackedGlobals.end()) {
1067
mergeInValue(IV, &I, It->second);
1073
// Transform load from a constant into a constant if possible.
1074
if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, DL))
1075
return markConstant(IV, &I, C);
1077
// Otherwise we cannot say for certain what value this load will produce.
1079
markOverdefined(IV, &I);
1082
void SCCPSolver::visitCallSite(CallSite CS) {
1083
Function *F = CS.getCalledFunction();
1084
Instruction *I = CS.getInstruction();
1086
// The common case is that we aren't tracking the callee, either because we
1087
// are not doing interprocedural analysis or the callee is indirect, or is
1088
// external. Handle these cases first.
1089
if (!F || F->isDeclaration()) {
1091
// Void return and not tracking callee, just bail.
1092
if (I->getType()->isVoidTy()) return;
1094
// Otherwise, if we have a single return value case, and if the function is
1095
// a declaration, maybe we can constant fold it.
1096
if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
1097
canConstantFoldCallTo(F)) {
1099
SmallVector<Constant*, 8> Operands;
1100
for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
1102
LatticeVal State = getValueState(*AI);
1104
if (State.isUndefined())
1105
return; // Operands are not resolved yet.
1106
if (State.isOverdefined())
1107
return markOverdefined(I);
1108
assert(State.isConstant() && "Unknown state!");
1109
Operands.push_back(State.getConstant());
1112
if (getValueState(I).isOverdefined())
1115
// If we can constant fold this, mark the result of the call as a
1117
if (Constant *C = ConstantFoldCall(F, Operands, TLI))
1118
return markConstant(I, C);
1121
// Otherwise, we don't know anything about this call, mark it overdefined.
1122
return markAnythingOverdefined(I);
1125
// If this is a local function that doesn't have its address taken, mark its
1126
// entry block executable and merge in the actual arguments to the call into
1127
// the formal arguments of the function.
1128
if (!TrackingIncomingArguments.empty() && TrackingIncomingArguments.count(F)){
1129
MarkBlockExecutable(F->begin());
1131
// Propagate information from this call site into the callee.
1132
CallSite::arg_iterator CAI = CS.arg_begin();
1133
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1134
AI != E; ++AI, ++CAI) {
1135
// If this argument is byval, and if the function is not readonly, there
1136
// will be an implicit copy formed of the input aggregate.
1137
if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1138
markOverdefined(AI);
1142
if (StructType *STy = dyn_cast<StructType>(AI->getType())) {
1143
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1144
LatticeVal CallArg = getStructValueState(*CAI, i);
1145
mergeInValue(getStructValueState(AI, i), AI, CallArg);
1148
mergeInValue(AI, getValueState(*CAI));
1153
// If this is a single/zero retval case, see if we're tracking the function.
1154
if (StructType *STy = dyn_cast<StructType>(F->getReturnType())) {
1155
if (!MRVFunctionsTracked.count(F))
1156
goto CallOverdefined; // Not tracking this callee.
1158
// If we are tracking this callee, propagate the result of the function
1159
// into this call site.
1160
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1161
mergeInValue(getStructValueState(I, i), I,
1162
TrackedMultipleRetVals[std::make_pair(F, i)]);
1164
DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
1165
if (TFRVI == TrackedRetVals.end())
1166
goto CallOverdefined; // Not tracking this callee.
1168
// If so, propagate the return value of the callee into this call result.
1169
mergeInValue(I, TFRVI->second);
1173
void SCCPSolver::Solve() {
1174
// Process the work lists until they are empty!
1175
while (!BBWorkList.empty() || !InstWorkList.empty() ||
1176
!OverdefinedInstWorkList.empty()) {
1177
// Process the overdefined instruction's work list first, which drives other
1178
// things to overdefined more quickly.
1179
while (!OverdefinedInstWorkList.empty()) {
1180
Value *I = OverdefinedInstWorkList.pop_back_val();
1182
DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1184
// "I" got into the work list because it either made the transition from
1185
// bottom to constant, or to overdefined.
1187
// Anything on this worklist that is overdefined need not be visited
1188
// since all of its users will have already been marked as overdefined
1189
// Update all of the users of this instruction's value.
1191
for (User *U : I->users())
1192
if (Instruction *UI = dyn_cast<Instruction>(U))
1193
OperandChangedState(UI);
1196
// Process the instruction work list.
1197
while (!InstWorkList.empty()) {
1198
Value *I = InstWorkList.pop_back_val();
1200
DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1202
// "I" got into the work list because it made the transition from undef to
1205
// Anything on this worklist that is overdefined need not be visited
1206
// since all of its users will have already been marked as overdefined.
1207
// Update all of the users of this instruction's value.
1209
if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1210
for (User *U : I->users())
1211
if (Instruction *UI = dyn_cast<Instruction>(U))
1212
OperandChangedState(UI);
1215
// Process the basic block work list.
1216
while (!BBWorkList.empty()) {
1217
BasicBlock *BB = BBWorkList.back();
1218
BBWorkList.pop_back();
1220
DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1222
// Notify all instructions in this basic block that they are newly
1229
/// ResolvedUndefsIn - While solving the dataflow for a function, we assume
1230
/// that branches on undef values cannot reach any of their successors.
1231
/// However, this is not a safe assumption. After we solve dataflow, this
1232
/// method should be use to handle this. If this returns true, the solver
1233
/// should be rerun.
1235
/// This method handles this by finding an unresolved branch and marking it one
1236
/// of the edges from the block as being feasible, even though the condition
1237
/// doesn't say it would otherwise be. This allows SCCP to find the rest of the
1238
/// CFG and only slightly pessimizes the analysis results (by marking one,
1239
/// potentially infeasible, edge feasible). This cannot usefully modify the
1240
/// constraints on the condition of the branch, as that would impact other users
1243
/// This scan also checks for values that use undefs, whose results are actually
1244
/// defined. For example, 'zext i8 undef to i32' should produce all zeros
1245
/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero,
1246
/// even if X isn't defined.
1247
bool SCCPSolver::ResolvedUndefsIn(Function &F) {
1248
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1249
if (!BBExecutable.count(BB))
1252
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1253
// Look for instructions which produce undef values.
1254
if (I->getType()->isVoidTy()) continue;
1256
if (StructType *STy = dyn_cast<StructType>(I->getType())) {
1257
// Only a few things that can be structs matter for undef.
1259
// Tracked calls must never be marked overdefined in ResolvedUndefsIn.
1260
if (CallSite CS = CallSite(I))
1261
if (Function *F = CS.getCalledFunction())
1262
if (MRVFunctionsTracked.count(F))
1265
// extractvalue and insertvalue don't need to be marked; they are
1266
// tracked as precisely as their operands.
1267
if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1270
// Send the results of everything else to overdefined. We could be
1271
// more precise than this but it isn't worth bothering.
1272
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1273
LatticeVal &LV = getStructValueState(I, i);
1274
if (LV.isUndefined())
1275
markOverdefined(LV, I);
1280
LatticeVal &LV = getValueState(I);
1281
if (!LV.isUndefined()) continue;
1283
// extractvalue is safe; check here because the argument is a struct.
1284
if (isa<ExtractValueInst>(I))
1287
// Compute the operand LatticeVals, for convenience below.
1288
// Anything taking a struct is conservatively assumed to require
1289
// overdefined markings.
1290
if (I->getOperand(0)->getType()->isStructTy()) {
1294
LatticeVal Op0LV = getValueState(I->getOperand(0));
1296
if (I->getNumOperands() == 2) {
1297
if (I->getOperand(1)->getType()->isStructTy()) {
1302
Op1LV = getValueState(I->getOperand(1));
1304
// If this is an instructions whose result is defined even if the input is
1305
// not fully defined, propagate the information.
1306
Type *ITy = I->getType();
1307
switch (I->getOpcode()) {
1308
case Instruction::Add:
1309
case Instruction::Sub:
1310
case Instruction::Trunc:
1311
case Instruction::FPTrunc:
1312
case Instruction::BitCast:
1313
break; // Any undef -> undef
1314
case Instruction::FSub:
1315
case Instruction::FAdd:
1316
case Instruction::FMul:
1317
case Instruction::FDiv:
1318
case Instruction::FRem:
1319
// Floating-point binary operation: be conservative.
1320
if (Op0LV.isUndefined() && Op1LV.isUndefined())
1321
markForcedConstant(I, Constant::getNullValue(ITy));
1325
case Instruction::ZExt:
1326
case Instruction::SExt:
1327
case Instruction::FPToUI:
1328
case Instruction::FPToSI:
1329
case Instruction::FPExt:
1330
case Instruction::PtrToInt:
1331
case Instruction::IntToPtr:
1332
case Instruction::SIToFP:
1333
case Instruction::UIToFP:
1334
// undef -> 0; some outputs are impossible
1335
markForcedConstant(I, Constant::getNullValue(ITy));
1337
case Instruction::Mul:
1338
case Instruction::And:
1339
// Both operands undef -> undef
1340
if (Op0LV.isUndefined() && Op1LV.isUndefined())
1342
// undef * X -> 0. X could be zero.
1343
// undef & X -> 0. X could be zero.
1344
markForcedConstant(I, Constant::getNullValue(ITy));
1347
case Instruction::Or:
1348
// Both operands undef -> undef
1349
if (Op0LV.isUndefined() && Op1LV.isUndefined())
1351
// undef | X -> -1. X could be -1.
1352
markForcedConstant(I, Constant::getAllOnesValue(ITy));
1355
case Instruction::Xor:
1356
// undef ^ undef -> 0; strictly speaking, this is not strictly
1357
// necessary, but we try to be nice to people who expect this
1358
// behavior in simple cases
1359
if (Op0LV.isUndefined() && Op1LV.isUndefined()) {
1360
markForcedConstant(I, Constant::getNullValue(ITy));
1363
// undef ^ X -> undef
1366
case Instruction::SDiv:
1367
case Instruction::UDiv:
1368
case Instruction::SRem:
1369
case Instruction::URem:
1370
// X / undef -> undef. No change.
1371
// X % undef -> undef. No change.
1372
if (Op1LV.isUndefined()) break;
1374
// undef / X -> 0. X could be maxint.
1375
// undef % X -> 0. X could be 1.
1376
markForcedConstant(I, Constant::getNullValue(ITy));
1379
case Instruction::AShr:
1380
// X >>a undef -> undef.
1381
if (Op1LV.isUndefined()) break;
1383
// undef >>a X -> all ones
1384
markForcedConstant(I, Constant::getAllOnesValue(ITy));
1386
case Instruction::LShr:
1387
case Instruction::Shl:
1388
// X << undef -> undef.
1389
// X >> undef -> undef.
1390
if (Op1LV.isUndefined()) break;
1394
markForcedConstant(I, Constant::getNullValue(ITy));
1396
case Instruction::Select:
1397
Op1LV = getValueState(I->getOperand(1));
1398
// undef ? X : Y -> X or Y. There could be commonality between X/Y.
1399
if (Op0LV.isUndefined()) {
1400
if (!Op1LV.isConstant()) // Pick the constant one if there is any.
1401
Op1LV = getValueState(I->getOperand(2));
1402
} else if (Op1LV.isUndefined()) {
1403
// c ? undef : undef -> undef. No change.
1404
Op1LV = getValueState(I->getOperand(2));
1405
if (Op1LV.isUndefined())
1407
// Otherwise, c ? undef : x -> x.
1409
// Leave Op1LV as Operand(1)'s LatticeValue.
1412
if (Op1LV.isConstant())
1413
markForcedConstant(I, Op1LV.getConstant());
1417
case Instruction::Load:
1418
// A load here means one of two things: a load of undef from a global,
1419
// a load from an unknown pointer. Either way, having it return undef
1422
case Instruction::ICmp:
1423
// X == undef -> undef. Other comparisons get more complicated.
1424
if (cast<ICmpInst>(I)->isEquality())
1428
case Instruction::Call:
1429
case Instruction::Invoke: {
1430
// There are two reasons a call can have an undef result
1431
// 1. It could be tracked.
1432
// 2. It could be constant-foldable.
1433
// Because of the way we solve return values, tracked calls must
1434
// never be marked overdefined in ResolvedUndefsIn.
1435
if (Function *F = CallSite(I).getCalledFunction())
1436
if (TrackedRetVals.count(F))
1439
// If the call is constant-foldable, we mark it overdefined because
1440
// we do not know what return values are valid.
1445
// If we don't know what should happen here, conservatively mark it
1452
// Check to see if we have a branch or switch on an undefined value. If so
1453
// we force the branch to go one way or the other to make the successor
1454
// values live. It doesn't really matter which way we force it.
1455
TerminatorInst *TI = BB->getTerminator();
1456
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1457
if (!BI->isConditional()) continue;
1458
if (!getValueState(BI->getCondition()).isUndefined())
1461
// If the input to SCCP is actually branch on undef, fix the undef to
1463
if (isa<UndefValue>(BI->getCondition())) {
1464
BI->setCondition(ConstantInt::getFalse(BI->getContext()));
1465
markEdgeExecutable(BB, TI->getSuccessor(1));
1469
// Otherwise, it is a branch on a symbolic value which is currently
1470
// considered to be undef. Handle this by forcing the input value to the
1472
markForcedConstant(BI->getCondition(),
1473
ConstantInt::getFalse(TI->getContext()));
1477
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
1478
if (!SI->getNumCases())
1480
if (!getValueState(SI->getCondition()).isUndefined())
1483
// If the input to SCCP is actually switch on undef, fix the undef to
1484
// the first constant.
1485
if (isa<UndefValue>(SI->getCondition())) {
1486
SI->setCondition(SI->case_begin().getCaseValue());
1487
markEdgeExecutable(BB, SI->case_begin().getCaseSuccessor());
1491
markForcedConstant(SI->getCondition(), SI->case_begin().getCaseValue());
1501
//===--------------------------------------------------------------------===//
1503
/// SCCP Class - This class uses the SCCPSolver to implement a per-function
1504
/// Sparse Conditional Constant Propagator.
1506
struct SCCP : public FunctionPass {
1507
void getAnalysisUsage(AnalysisUsage &AU) const override {
1508
AU.addRequired<TargetLibraryInfoWrapperPass>();
1510
static char ID; // Pass identification, replacement for typeid
1511
SCCP() : FunctionPass(ID) {
1512
initializeSCCPPass(*PassRegistry::getPassRegistry());
1515
// runOnFunction - Run the Sparse Conditional Constant Propagation
1516
// algorithm, and return true if the function was modified.
1518
bool runOnFunction(Function &F) override;
1520
} // end anonymous namespace
1523
INITIALIZE_PASS(SCCP, "sccp",
1524
"Sparse Conditional Constant Propagation", false, false)
1526
// createSCCPPass - This is the public interface to this file.
1527
FunctionPass *llvm::createSCCPPass() {
1531
static void DeleteInstructionInBlock(BasicBlock *BB) {
1532
DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
1535
// Check to see if there are non-terminating instructions to delete.
1536
if (isa<TerminatorInst>(BB->begin()))
1539
// Delete the instructions backwards, as it has a reduced likelihood of having
1540
// to update as many def-use and use-def chains.
1541
Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
1542
while (EndInst != BB->begin()) {
1543
// Delete the next to last instruction.
1544
BasicBlock::iterator I = EndInst;
1545
Instruction *Inst = --I;
1546
if (!Inst->use_empty())
1547
Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
1548
if (isa<LandingPadInst>(Inst)) {
1552
BB->getInstList().erase(Inst);
1557
// runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
1558
// and return true if the function was modified.
1560
bool SCCP::runOnFunction(Function &F) {
1561
if (skipOptnoneFunction(F))
1564
DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
1565
const DataLayout &DL = F.getParent()->getDataLayout();
1566
const TargetLibraryInfo *TLI =
1567
&getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1568
SCCPSolver Solver(DL, TLI);
1570
// Mark the first block of the function as being executable.
1571
Solver.MarkBlockExecutable(F.begin());
1573
// Mark all arguments to the function as being overdefined.
1574
for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI)
1575
Solver.markAnythingOverdefined(AI);
1577
// Solve for constants.
1578
bool ResolvedUndefs = true;
1579
while (ResolvedUndefs) {
1581
DEBUG(dbgs() << "RESOLVING UNDEFs\n");
1582
ResolvedUndefs = Solver.ResolvedUndefsIn(F);
1585
bool MadeChanges = false;
1587
// If we decided that there are basic blocks that are dead in this function,
1588
// delete their contents now. Note that we cannot actually delete the blocks,
1589
// as we cannot modify the CFG of the function.
1591
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1592
if (!Solver.isBlockExecutable(BB)) {
1593
DeleteInstructionInBlock(BB);
1598
// Iterate over all of the instructions in a function, replacing them with
1599
// constants if we have found them to be of constant values.
1601
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
1602
Instruction *Inst = BI++;
1603
if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst))
1606
// TODO: Reconstruct structs from their elements.
1607
if (Inst->getType()->isStructTy())
1610
LatticeVal IV = Solver.getLatticeValueFor(Inst);
1611
if (IV.isOverdefined())
1614
Constant *Const = IV.isConstant()
1615
? IV.getConstant() : UndefValue::get(Inst->getType());
1616
DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n');
1618
// Replaces all of the uses of a variable with uses of the constant.
1619
Inst->replaceAllUsesWith(Const);
1621
// Delete the instruction.
1622
Inst->eraseFromParent();
1624
// Hey, we just changed something!
1634
//===--------------------------------------------------------------------===//
1636
/// IPSCCP Class - This class implements interprocedural Sparse Conditional
1637
/// Constant Propagation.
1639
struct IPSCCP : public ModulePass {
1640
void getAnalysisUsage(AnalysisUsage &AU) const override {
1641
AU.addRequired<TargetLibraryInfoWrapperPass>();
1644
IPSCCP() : ModulePass(ID) {
1645
initializeIPSCCPPass(*PassRegistry::getPassRegistry());
1647
bool runOnModule(Module &M) override;
1649
} // end anonymous namespace
1651
char IPSCCP::ID = 0;
1652
INITIALIZE_PASS_BEGIN(IPSCCP, "ipsccp",
1653
"Interprocedural Sparse Conditional Constant Propagation",
1655
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1656
INITIALIZE_PASS_END(IPSCCP, "ipsccp",
1657
"Interprocedural Sparse Conditional Constant Propagation",
1660
// createIPSCCPPass - This is the public interface to this file.
1661
ModulePass *llvm::createIPSCCPPass() {
1662
return new IPSCCP();
1666
static bool AddressIsTaken(const GlobalValue *GV) {
1667
// Delete any dead constantexpr klingons.
1668
GV->removeDeadConstantUsers();
1670
for (const Use &U : GV->uses()) {
1671
const User *UR = U.getUser();
1672
if (const StoreInst *SI = dyn_cast<StoreInst>(UR)) {
1673
if (SI->getOperand(0) == GV || SI->isVolatile())
1674
return true; // Storing addr of GV.
1675
} else if (isa<InvokeInst>(UR) || isa<CallInst>(UR)) {
1676
// Make sure we are calling the function, not passing the address.
1677
ImmutableCallSite CS(cast<Instruction>(UR));
1678
if (!CS.isCallee(&U))
1680
} else if (const LoadInst *LI = dyn_cast<LoadInst>(UR)) {
1681
if (LI->isVolatile())
1683
} else if (isa<BlockAddress>(UR)) {
1684
// blockaddress doesn't take the address of the function, it takes addr
1693
bool IPSCCP::runOnModule(Module &M) {
1694
const DataLayout &DL = M.getDataLayout();
1695
const TargetLibraryInfo *TLI =
1696
&getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1697
SCCPSolver Solver(DL, TLI);
1699
// AddressTakenFunctions - This set keeps track of the address-taken functions
1700
// that are in the input. As IPSCCP runs through and simplifies code,
1701
// functions that were address taken can end up losing their
1702
// address-taken-ness. Because of this, we keep track of their addresses from
1703
// the first pass so we can use them for the later simplification pass.
1704
SmallPtrSet<Function*, 32> AddressTakenFunctions;
1706
// Loop over all functions, marking arguments to those with their addresses
1707
// taken or that are external as overdefined.
1709
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
1710
if (F->isDeclaration())
1713
// If this is a strong or ODR definition of this function, then we can
1714
// propagate information about its result into callsites of it.
1715
if (!F->mayBeOverridden())
1716
Solver.AddTrackedFunction(F);
1718
// If this function only has direct calls that we can see, we can track its
1719
// arguments and return value aggressively, and can assume it is not called
1720
// unless we see evidence to the contrary.
1721
if (F->hasLocalLinkage()) {
1722
if (AddressIsTaken(F))
1723
AddressTakenFunctions.insert(F);
1725
Solver.AddArgumentTrackedFunction(F);
1730
// Assume the function is called.
1731
Solver.MarkBlockExecutable(F->begin());
1733
// Assume nothing about the incoming arguments.
1734
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1736
Solver.markAnythingOverdefined(AI);
1739
// Loop over global variables. We inform the solver about any internal global
1740
// variables that do not have their 'addresses taken'. If they don't have
1741
// their addresses taken, we can propagate constants through them.
1742
for (Module::global_iterator G = M.global_begin(), E = M.global_end();
1744
if (!G->isConstant() && G->hasLocalLinkage() && !AddressIsTaken(G))
1745
Solver.TrackValueOfGlobalVariable(G);
1747
// Solve for constants.
1748
bool ResolvedUndefs = true;
1749
while (ResolvedUndefs) {
1752
DEBUG(dbgs() << "RESOLVING UNDEFS\n");
1753
ResolvedUndefs = false;
1754
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
1755
ResolvedUndefs |= Solver.ResolvedUndefsIn(*F);
1758
bool MadeChanges = false;
1760
// Iterate over all of the instructions in the module, replacing them with
1761
// constants if we have found them to be of constant values.
1763
SmallVector<BasicBlock*, 512> BlocksToErase;
1765
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
1766
if (Solver.isBlockExecutable(F->begin())) {
1767
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1769
if (AI->use_empty() || AI->getType()->isStructTy()) continue;
1771
// TODO: Could use getStructLatticeValueFor to find out if the entire
1772
// result is a constant and replace it entirely if so.
1774
LatticeVal IV = Solver.getLatticeValueFor(AI);
1775
if (IV.isOverdefined()) continue;
1777
Constant *CST = IV.isConstant() ?
1778
IV.getConstant() : UndefValue::get(AI->getType());
1779
DEBUG(dbgs() << "*** Arg " << *AI << " = " << *CST <<"\n");
1781
// Replaces all of the uses of a variable with uses of the
1783
AI->replaceAllUsesWith(CST);
1788
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
1789
if (!Solver.isBlockExecutable(BB)) {
1790
DeleteInstructionInBlock(BB);
1793
TerminatorInst *TI = BB->getTerminator();
1794
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
1795
BasicBlock *Succ = TI->getSuccessor(i);
1796
if (!Succ->empty() && isa<PHINode>(Succ->begin()))
1797
TI->getSuccessor(i)->removePredecessor(BB);
1799
if (!TI->use_empty())
1800
TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
1801
TI->eraseFromParent();
1802
new UnreachableInst(M.getContext(), BB);
1804
if (&*BB != &F->front())
1805
BlocksToErase.push_back(BB);
1809
for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
1810
Instruction *Inst = BI++;
1811
if (Inst->getType()->isVoidTy() || Inst->getType()->isStructTy())
1814
// TODO: Could use getStructLatticeValueFor to find out if the entire
1815
// result is a constant and replace it entirely if so.
1817
LatticeVal IV = Solver.getLatticeValueFor(Inst);
1818
if (IV.isOverdefined())
1821
Constant *Const = IV.isConstant()
1822
? IV.getConstant() : UndefValue::get(Inst->getType());
1823
DEBUG(dbgs() << " Constant: " << *Const << " = " << *Inst << '\n');
1825
// Replaces all of the uses of a variable with uses of the
1827
Inst->replaceAllUsesWith(Const);
1829
// Delete the instruction.
1830
if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst))
1831
Inst->eraseFromParent();
1833
// Hey, we just changed something!
1839
// Now that all instructions in the function are constant folded, erase dead
1840
// blocks, because we can now use ConstantFoldTerminator to get rid of
1842
for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
1843
// If there are any PHI nodes in this successor, drop entries for BB now.
1844
BasicBlock *DeadBB = BlocksToErase[i];
1845
for (Value::user_iterator UI = DeadBB->user_begin(),
1846
UE = DeadBB->user_end();
1848
// Grab the user and then increment the iterator early, as the user
1849
// will be deleted. Step past all adjacent uses from the same user.
1850
Instruction *I = dyn_cast<Instruction>(*UI);
1851
do { ++UI; } while (UI != UE && *UI == I);
1853
// Ignore blockaddress users; BasicBlock's dtor will handle them.
1856
bool Folded = ConstantFoldTerminator(I->getParent());
1858
// The constant folder may not have been able to fold the terminator
1859
// if this is a branch or switch on undef. Fold it manually as a
1860
// branch to the first successor.
1862
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1863
assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) &&
1864
"Branch should be foldable!");
1865
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
1866
assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold");
1868
llvm_unreachable("Didn't fold away reference to block!");
1872
// Make this an uncond branch to the first successor.
1873
TerminatorInst *TI = I->getParent()->getTerminator();
1874
BranchInst::Create(TI->getSuccessor(0), TI);
1876
// Remove entries in successor phi nodes to remove edges.
1877
for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i)
1878
TI->getSuccessor(i)->removePredecessor(TI->getParent());
1880
// Remove the old terminator.
1881
TI->eraseFromParent();
1885
// Finally, delete the basic block.
1886
F->getBasicBlockList().erase(DeadBB);
1888
BlocksToErase.clear();
1891
// If we inferred constant or undef return values for a function, we replaced
1892
// all call uses with the inferred value. This means we don't need to bother
1893
// actually returning anything from the function. Replace all return
1894
// instructions with return undef.
1896
// Do this in two stages: first identify the functions we should process, then
1897
// actually zap their returns. This is important because we can only do this
1898
// if the address of the function isn't taken. In cases where a return is the
1899
// last use of a function, the order of processing functions would affect
1900
// whether other functions are optimizable.
1901
SmallVector<ReturnInst*, 8> ReturnsToZap;
1903
// TODO: Process multiple value ret instructions also.
1904
const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
1905
for (DenseMap<Function*, LatticeVal>::const_iterator I = RV.begin(),
1906
E = RV.end(); I != E; ++I) {
1907
Function *F = I->first;
1908
if (I->second.isOverdefined() || F->getReturnType()->isVoidTy())
1911
// We can only do this if we know that nothing else can call the function.
1912
if (!F->hasLocalLinkage() || AddressTakenFunctions.count(F))
1915
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
1916
if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
1917
if (!isa<UndefValue>(RI->getOperand(0)))
1918
ReturnsToZap.push_back(RI);
1921
// Zap all returns which we've identified as zap to change.
1922
for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
1923
Function *F = ReturnsToZap[i]->getParent()->getParent();
1924
ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
1927
// If we inferred constant or undef values for globals variables, we can
1928
// delete the global and any stores that remain to it.
1929
const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
1930
for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
1931
E = TG.end(); I != E; ++I) {
1932
GlobalVariable *GV = I->first;
1933
assert(!I->second.isOverdefined() &&
1934
"Overdefined values should have been taken out of the map!");
1935
DEBUG(dbgs() << "Found that GV '" << GV->getName() << "' is constant!\n");
1936
while (!GV->use_empty()) {
1937
StoreInst *SI = cast<StoreInst>(GV->user_back());
1938
SI->eraseFromParent();
1940
M.getGlobalList().erase(GV);
added
removed
lib/Transforms/Scalar/SCCP.cpp
