1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements sparse conditional constant propagation and merging:
11 //
12 // Specifically, this:
13 // * Assumes values are constant unless proven otherwise
14 // * Assumes BasicBlocks are dead unless proven otherwise
15 // * Proves values to be constant, and replaces them with constants
16 // * Proves conditional branches to be unconditional
17 //
18 //===----------------------------------------------------------------------===//
19
20 #include "llvm/Transforms/Scalar/SCCP.h"
21 #include "llvm/ADT/ArrayRef.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/DenseSet.h"
24 #include "llvm/ADT/PointerIntPair.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/Analysis/ConstantFolding.h"
30 #include "llvm/Analysis/GlobalsModRef.h"
31 #include "llvm/Analysis/TargetLibraryInfo.h"
32 #include "llvm/Transforms/Utils/Local.h"
33 #include "llvm/Analysis/ValueLattice.h"
34 #include "llvm/Analysis/ValueLatticeUtils.h"
35 #include "llvm/IR/BasicBlock.h"
36 #include "llvm/IR/CallSite.h"
37 #include "llvm/IR/Constant.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/DataLayout.h"
40 #include "llvm/IR/DerivedTypes.h"
41 #include "llvm/IR/Function.h"
42 #include "llvm/IR/GlobalVariable.h"
43 #include "llvm/IR/InstVisitor.h"
44 #include "llvm/IR/InstrTypes.h"
45 #include "llvm/IR/Instruction.h"
46 #include "llvm/IR/Instructions.h"
47 #include "llvm/IR/Module.h"
48 #include "llvm/IR/PassManager.h"
49 #include "llvm/IR/Type.h"
50 #include "llvm/IR/User.h"
51 #include "llvm/IR/Value.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Casting.h"
54 #include "llvm/Support/Debug.h"
55 #include "llvm/Support/ErrorHandling.h"
56 #include "llvm/Support/raw_ostream.h"
57 #include "llvm/Transforms/Scalar.h"
58 #include <cassert>
59 #include <utility>
60 #include <vector>
61
62 using namespace llvm;
63
64 #define DEBUG_TYPE "sccp"
65
66 STATISTIC(NumInstRemoved, "Number of instructions removed");
67 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
68
69 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
70 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
71 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
72
73 namespace {
74
75 /// LatticeVal class - This class represents the different lattice values that
76 /// an LLVM value may occupy. It is a simple class with value semantics.
77 ///
78 class LatticeVal {
79 enum LatticeValueTy {
80 /// unknown - This LLVM Value has no known value yet.
81 unknown,
82
83 /// constant - This LLVM Value has a specific constant value.
84 constant,
85
86 /// forcedconstant - This LLVM Value was thought to be undef until
87 /// ResolvedUndefsIn. This is treated just like 'constant', but if merged
88 /// with another (different) constant, it goes to overdefined, instead of
89 /// asserting.
90 forcedconstant,
91
92 /// overdefined - This instruction is not known to be constant, and we know
93 /// it has a value.
94 overdefined
95 };
96
97 /// Val: This stores the current lattice value along with the Constant* for
98 /// the constant if this is a 'constant' or 'forcedconstant' value.
99 PointerIntPair<Constant *, 2, LatticeValueTy> Val;
100
getLatticeValue() const101 LatticeValueTy getLatticeValue() const {
102 return Val.getInt();
103 }
104
105 public:
LatticeVal()106 LatticeVal() : Val(nullptr, unknown) {}
107
isUnknown() const108 bool isUnknown() const { return getLatticeValue() == unknown; }
109
isConstant() const110 bool isConstant() const {
111 return getLatticeValue() == constant || getLatticeValue() == forcedconstant;
112 }
113
isOverdefined() const114 bool isOverdefined() const { return getLatticeValue() == overdefined; }
115
getConstant() const116 Constant *getConstant() const {
117 assert(isConstant() && "Cannot get the constant of a non-constant!");
118 return Val.getPointer();
119 }
120
121 /// markOverdefined - Return true if this is a change in status.
markOverdefined()122 bool markOverdefined() {
123 if (isOverdefined())
124 return false;
125
126 Val.setInt(overdefined);
127 return true;
128 }
129
130 /// markConstant - Return true if this is a change in status.
markConstant(Constant * V)131 bool markConstant(Constant *V) {
132 if (getLatticeValue() == constant) { // Constant but not forcedconstant.
133 assert(getConstant() == V && "Marking constant with different value");
134 return false;
135 }
136
137 if (isUnknown()) {
138 Val.setInt(constant);
139 assert(V && "Marking constant with NULL");
140 Val.setPointer(V);
141 } else {
142 assert(getLatticeValue() == forcedconstant &&
143 "Cannot move from overdefined to constant!");
144 // Stay at forcedconstant if the constant is the same.
145 if (V == getConstant()) return false;
146
147 // Otherwise, we go to overdefined. Assumptions made based on the
148 // forced value are possibly wrong. Assuming this is another constant
149 // could expose a contradiction.
150 Val.setInt(overdefined);
151 }
152 return true;
153 }
154
155 /// getConstantInt - If this is a constant with a ConstantInt value, return it
156 /// otherwise return null.
getConstantInt() const157 ConstantInt *getConstantInt() const {
158 if (isConstant())
159 return dyn_cast<ConstantInt>(getConstant());
160 return nullptr;
161 }
162
163 /// getBlockAddress - If this is a constant with a BlockAddress value, return
164 /// it, otherwise return null.
getBlockAddress() const165 BlockAddress *getBlockAddress() const {
166 if (isConstant())
167 return dyn_cast<BlockAddress>(getConstant());
168 return nullptr;
169 }
170
markForcedConstant(Constant * V)171 void markForcedConstant(Constant *V) {
172 assert(isUnknown() && "Can't force a defined value!");
173 Val.setInt(forcedconstant);
174 Val.setPointer(V);
175 }
176
toValueLattice() const177 ValueLatticeElement toValueLattice() const {
178 if (isOverdefined())
179 return ValueLatticeElement::getOverdefined();
180 if (isConstant())
181 return ValueLatticeElement::get(getConstant());
182 return ValueLatticeElement();
183 }
184 };
185
186 //===----------------------------------------------------------------------===//
187 //
188 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
189 /// Constant Propagation.
190 ///
191 class SCCPSolver : public InstVisitor<SCCPSolver> {
192 const DataLayout &DL;
193 const TargetLibraryInfo *TLI;
194 SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
195 DenseMap<Value *, LatticeVal> ValueState; // The state each value is in.
196 // The state each parameter is in.
197 DenseMap<Value *, ValueLatticeElement> ParamState;
198
199 /// StructValueState - This maintains ValueState for values that have
200 /// StructType, for example for formal arguments, calls, insertelement, etc.
201 DenseMap<std::pair<Value *, unsigned>, LatticeVal> StructValueState;
202
203 /// GlobalValue - If we are tracking any values for the contents of a global
204 /// variable, we keep a mapping from the constant accessor to the element of
205 /// the global, to the currently known value. If the value becomes
206 /// overdefined, it's entry is simply removed from this map.
207 DenseMap<GlobalVariable *, LatticeVal> TrackedGlobals;
208
209 /// TrackedRetVals - If we are tracking arguments into and the return
210 /// value out of a function, it will have an entry in this map, indicating
211 /// what the known return value for the function is.
212 DenseMap<Function *, LatticeVal> TrackedRetVals;
213
214 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
215 /// that return multiple values.
216 DenseMap<std::pair<Function *, unsigned>, LatticeVal> TrackedMultipleRetVals;
217
218 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
219 /// represented here for efficient lookup.
220 SmallPtrSet<Function *, 16> MRVFunctionsTracked;
221
222 /// MustTailFunctions - Each function here is a callee of non-removable
223 /// musttail call site.
224 SmallPtrSet<Function *, 16> MustTailCallees;
225
226 /// TrackingIncomingArguments - This is the set of functions for whose
227 /// arguments we make optimistic assumptions about and try to prove as
228 /// constants.
229 SmallPtrSet<Function *, 16> TrackingIncomingArguments;
230
231 /// The reason for two worklists is that overdefined is the lowest state
232 /// on the lattice, and moving things to overdefined as fast as possible
233 /// makes SCCP converge much faster.
234 ///
235 /// By having a separate worklist, we accomplish this because everything
236 /// possibly overdefined will become overdefined at the soonest possible
237 /// point.
238 SmallVector<Value *, 64> OverdefinedInstWorkList;
239 SmallVector<Value *, 64> InstWorkList;
240
241 // The BasicBlock work list
242 SmallVector<BasicBlock *, 64> BBWorkList;
243
244 /// KnownFeasibleEdges - Entries in this set are edges which have already had
245 /// PHI nodes retriggered.
246 using Edge = std::pair<BasicBlock *, BasicBlock *>;
247 DenseSet<Edge> KnownFeasibleEdges;
248
249 public:
SCCPSolver(const DataLayout & DL,const TargetLibraryInfo * tli)250 SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli)
251 : DL(DL), TLI(tli) {}
252
253 /// MarkBlockExecutable - This method can be used by clients to mark all of
254 /// the blocks that are known to be intrinsically live in the processed unit.
255 ///
256 /// This returns true if the block was not considered live before.
MarkBlockExecutable(BasicBlock * BB)257 bool MarkBlockExecutable(BasicBlock *BB) {
258 if (!BBExecutable.insert(BB).second)
259 return false;
260 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
261 BBWorkList.push_back(BB); // Add the block to the work list!
262 return true;
263 }
264
265 /// TrackValueOfGlobalVariable - Clients can use this method to
266 /// inform the SCCPSolver that it should track loads and stores to the
267 /// specified global variable if it can. This is only legal to call if
268 /// performing Interprocedural SCCP.
TrackValueOfGlobalVariable(GlobalVariable * GV)269 void TrackValueOfGlobalVariable(GlobalVariable *GV) {
270 // We only track the contents of scalar globals.
271 if (GV->getValueType()->isSingleValueType()) {
272 LatticeVal &IV = TrackedGlobals[GV];
273 if (!isa<UndefValue>(GV->getInitializer()))
274 IV.markConstant(GV->getInitializer());
275 }
276 }
277
278 /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
279 /// and out of the specified function (which cannot have its address taken),
280 /// this method must be called.
AddTrackedFunction(Function * F)281 void AddTrackedFunction(Function *F) {
282 // Add an entry, F -> undef.
283 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
284 MRVFunctionsTracked.insert(F);
285 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
286 TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i),
287 LatticeVal()));
288 } else
289 TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
290 }
291
292 /// AddMustTailCallee - If the SCCP solver finds that this function is called
293 /// from non-removable musttail call site.
AddMustTailCallee(Function * F)294 void AddMustTailCallee(Function *F) {
295 MustTailCallees.insert(F);
296 }
297
298 /// Returns true if the given function is called from non-removable musttail
299 /// call site.
isMustTailCallee(Function * F)300 bool isMustTailCallee(Function *F) {
301 return MustTailCallees.count(F);
302 }
303
AddArgumentTrackedFunction(Function * F)304 void AddArgumentTrackedFunction(Function *F) {
305 TrackingIncomingArguments.insert(F);
306 }
307
308 /// Returns true if the given function is in the solver's set of
309 /// argument-tracked functions.
isArgumentTrackedFunction(Function * F)310 bool isArgumentTrackedFunction(Function *F) {
311 return TrackingIncomingArguments.count(F);
312 }
313
314 /// Solve - Solve for constants and executable blocks.
315 void Solve();
316
317 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
318 /// that branches on undef values cannot reach any of their successors.
319 /// However, this is not a safe assumption. After we solve dataflow, this
320 /// method should be use to handle this. If this returns true, the solver
321 /// should be rerun.
322 bool ResolvedUndefsIn(Function &F);
323
isBlockExecutable(BasicBlock * BB) const324 bool isBlockExecutable(BasicBlock *BB) const {
325 return BBExecutable.count(BB);
326 }
327
328 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
329 // block to the 'To' basic block is currently feasible.
330 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
331
getStructLatticeValueFor(Value * V) const332 std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
333 std::vector<LatticeVal> StructValues;
334 auto *STy = dyn_cast<StructType>(V->getType());
335 assert(STy && "getStructLatticeValueFor() can be called only on structs");
336 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
337 auto I = StructValueState.find(std::make_pair(V, i));
338 assert(I != StructValueState.end() && "Value not in valuemap!");
339 StructValues.push_back(I->second);
340 }
341 return StructValues;
342 }
343
getLatticeValueFor(Value * V) const344 const LatticeVal &getLatticeValueFor(Value *V) const {
345 assert(!V->getType()->isStructTy() &&
346 "Should use getStructLatticeValueFor");
347 DenseMap<Value *, LatticeVal>::const_iterator I = ValueState.find(V);
348 assert(I != ValueState.end() &&
349 "V not found in ValueState nor Paramstate map!");
350 return I->second;
351 }
352
353 /// getTrackedRetVals - Get the inferred return value map.
getTrackedRetVals()354 const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
355 return TrackedRetVals;
356 }
357
358 /// getTrackedGlobals - Get and return the set of inferred initializers for
359 /// global variables.
getTrackedGlobals()360 const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() {
361 return TrackedGlobals;
362 }
363
364 /// getMRVFunctionsTracked - Get the set of functions which return multiple
365 /// values tracked by the pass.
getMRVFunctionsTracked()366 const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() {
367 return MRVFunctionsTracked;
368 }
369
370 /// getMustTailCallees - Get the set of functions which are called
371 /// from non-removable musttail call sites.
getMustTailCallees()372 const SmallPtrSet<Function *, 16> getMustTailCallees() {
373 return MustTailCallees;
374 }
375
376 /// markOverdefined - Mark the specified value overdefined. This
377 /// works with both scalars and structs.
markOverdefined(Value * V)378 void markOverdefined(Value *V) {
379 if (auto *STy = dyn_cast<StructType>(V->getType()))
380 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
381 markOverdefined(getStructValueState(V, i), V);
382 else
383 markOverdefined(ValueState[V], V);
384 }
385
386 // isStructLatticeConstant - Return true if all the lattice values
387 // corresponding to elements of the structure are not overdefined,
388 // false otherwise.
isStructLatticeConstant(Function * F,StructType * STy)389 bool isStructLatticeConstant(Function *F, StructType *STy) {
390 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
391 const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
392 assert(It != TrackedMultipleRetVals.end());
393 LatticeVal LV = It->second;
394 if (LV.isOverdefined())
395 return false;
396 }
397 return true;
398 }
399
400 private:
401 // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined
pushToWorkList(LatticeVal & IV,Value * V)402 void pushToWorkList(LatticeVal &IV, Value *V) {
403 if (IV.isOverdefined())
404 return OverdefinedInstWorkList.push_back(V);
405 InstWorkList.push_back(V);
406 }
407
408 // markConstant - Make a value be marked as "constant". If the value
409 // is not already a constant, add it to the instruction work list so that
410 // the users of the instruction are updated later.
markConstant(LatticeVal & IV,Value * V,Constant * C)411 bool markConstant(LatticeVal &IV, Value *V, Constant *C) {
412 if (!IV.markConstant(C)) return false;
413 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
414 pushToWorkList(IV, V);
415 return true;
416 }
417
markConstant(Value * V,Constant * C)418 bool markConstant(Value *V, Constant *C) {
419 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
420 return markConstant(ValueState[V], V, C);
421 }
422
markForcedConstant(Value * V,Constant * C)423 void markForcedConstant(Value *V, Constant *C) {
424 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
425 LatticeVal &IV = ValueState[V];
426 IV.markForcedConstant(C);
427 LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
428 pushToWorkList(IV, V);
429 }
430
431 // markOverdefined - Make a value be marked as "overdefined". If the
432 // value is not already overdefined, add it to the overdefined instruction
433 // work list so that the users of the instruction are updated later.
markOverdefined(LatticeVal & IV,Value * V)434 bool markOverdefined(LatticeVal &IV, Value *V) {
435 if (!IV.markOverdefined()) return false;
436
437 LLVM_DEBUG(dbgs() << "markOverdefined: ";
438 if (auto *F = dyn_cast<Function>(V)) dbgs()
439 << "Function '" << F->getName() << "'\n";
440 else dbgs() << *V << '\n');
441 // Only instructions go on the work list
442 pushToWorkList(IV, V);
443 return true;
444 }
445
mergeInValue(LatticeVal & IV,Value * V,LatticeVal MergeWithV)446 bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) {
447 if (IV.isOverdefined() || MergeWithV.isUnknown())
448 return false; // Noop.
449 if (MergeWithV.isOverdefined())
450 return markOverdefined(IV, V);
451 if (IV.isUnknown())
452 return markConstant(IV, V, MergeWithV.getConstant());
453 if (IV.getConstant() != MergeWithV.getConstant())
454 return markOverdefined(IV, V);
455 return false;
456 }
457
mergeInValue(Value * V,LatticeVal MergeWithV)458 bool mergeInValue(Value *V, LatticeVal MergeWithV) {
459 assert(!V->getType()->isStructTy() &&
460 "non-structs should use markConstant");
461 return mergeInValue(ValueState[V], V, MergeWithV);
462 }
463
464 /// getValueState - Return the LatticeVal object that corresponds to the
465 /// value. This function handles the case when the value hasn't been seen yet
466 /// by properly seeding constants etc.
getValueState(Value * V)467 LatticeVal &getValueState(Value *V) {
468 assert(!V->getType()->isStructTy() && "Should use getStructValueState");
469
470 std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I =
471 ValueState.insert(std::make_pair(V, LatticeVal()));
472 LatticeVal &LV = I.first->second;
473
474 if (!I.second)
475 return LV; // Common case, already in the map.
476
477 if (auto *C = dyn_cast<Constant>(V)) {
478 // Undef values remain unknown.
479 if (!isa<UndefValue>(V))
480 LV.markConstant(C); // Constants are constant
481 }
482
483 // All others are underdefined by default.
484 return LV;
485 }
486
getParamState(Value * V)487 ValueLatticeElement &getParamState(Value *V) {
488 assert(!V->getType()->isStructTy() && "Should use getStructValueState");
489
490 std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool>
491 PI = ParamState.insert(std::make_pair(V, ValueLatticeElement()));
492 ValueLatticeElement &LV = PI.first->second;
493 if (PI.second)
494 LV = getValueState(V).toValueLattice();
495
496 return LV;
497 }
498
499 /// getStructValueState - Return the LatticeVal object that corresponds to the
500 /// value/field pair. This function handles the case when the value hasn't
501 /// been seen yet by properly seeding constants etc.
getStructValueState(Value * V,unsigned i)502 LatticeVal &getStructValueState(Value *V, unsigned i) {
503 assert(V->getType()->isStructTy() && "Should use getValueState");
504 assert(i < cast<StructType>(V->getType())->getNumElements() &&
505 "Invalid element #");
506
507 std::pair<DenseMap<std::pair<Value*, unsigned>, LatticeVal>::iterator,
508 bool> I = StructValueState.insert(
509 std::make_pair(std::make_pair(V, i), LatticeVal()));
510 LatticeVal &LV = I.first->second;
511
512 if (!I.second)
513 return LV; // Common case, already in the map.
514
515 if (auto *C = dyn_cast<Constant>(V)) {
516 Constant *Elt = C->getAggregateElement(i);
517
518 if (!Elt)
519 LV.markOverdefined(); // Unknown sort of constant.
520 else if (isa<UndefValue>(Elt))
521 ; // Undef values remain unknown.
522 else
523 LV.markConstant(Elt); // Constants are constant.
524 }
525
526 // All others are underdefined by default.
527 return LV;
528 }
529
530 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
531 /// work list if it is not already executable.
markEdgeExecutable(BasicBlock * Source,BasicBlock * Dest)532 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
533 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
534 return false; // This edge is already known to be executable!
535
536 if (!MarkBlockExecutable(Dest)) {
537 // If the destination is already executable, we just made an *edge*
538 // feasible that wasn't before. Revisit the PHI nodes in the block
539 // because they have potentially new operands.
540 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
541 << " -> " << Dest->getName() << '\n');
542
543 for (PHINode &PN : Dest->phis())
544 visitPHINode(PN);
545 }
546 return true;
547 }
548
549 // getFeasibleSuccessors - Return a vector of booleans to indicate which
550 // successors are reachable from a given terminator instruction.
551 void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs);
552
553 // OperandChangedState - This method is invoked on all of the users of an
554 // instruction that was just changed state somehow. Based on this
555 // information, we need to update the specified user of this instruction.
OperandChangedState(Instruction * I)556 void OperandChangedState(Instruction *I) {
557 if (BBExecutable.count(I->getParent())) // Inst is executable?
558 visit(*I);
559 }
560
561 private:
562 friend class InstVisitor<SCCPSolver>;
563
564 // visit implementations - Something changed in this instruction. Either an
565 // operand made a transition, or the instruction is newly executable. Change
566 // the value type of I to reflect these changes if appropriate.
567 void visitPHINode(PHINode &I);
568
569 // Terminators
570
571 void visitReturnInst(ReturnInst &I);
572 void visitTerminatorInst(TerminatorInst &TI);
573
574 void visitCastInst(CastInst &I);
575 void visitSelectInst(SelectInst &I);
576 void visitBinaryOperator(Instruction &I);
577 void visitCmpInst(CmpInst &I);
578 void visitExtractValueInst(ExtractValueInst &EVI);
579 void visitInsertValueInst(InsertValueInst &IVI);
580
visitCatchSwitchInst(CatchSwitchInst & CPI)581 void visitCatchSwitchInst(CatchSwitchInst &CPI) {
582 markOverdefined(&CPI);
583 visitTerminatorInst(CPI);
584 }
585
586 // Instructions that cannot be folded away.
587
588 void visitStoreInst (StoreInst &I);
589 void visitLoadInst (LoadInst &I);
590 void visitGetElementPtrInst(GetElementPtrInst &I);
591
visitCallInst(CallInst & I)592 void visitCallInst (CallInst &I) {
593 visitCallSite(&I);
594 }
595
visitInvokeInst(InvokeInst & II)596 void visitInvokeInst (InvokeInst &II) {
597 visitCallSite(&II);
598 visitTerminatorInst(II);
599 }
600
601 void visitCallSite (CallSite CS);
visitResumeInst(TerminatorInst & I)602 void visitResumeInst (TerminatorInst &I) { /*returns void*/ }
visitUnreachableInst(TerminatorInst & I)603 void visitUnreachableInst(TerminatorInst &I) { /*returns void*/ }
visitFenceInst(FenceInst & I)604 void visitFenceInst (FenceInst &I) { /*returns void*/ }
605
visitInstruction(Instruction & I)606 void visitInstruction(Instruction &I) {
607 // All the instructions we don't do any special handling for just
608 // go to overdefined.
609 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
610 markOverdefined(&I);
611 }
612 };
613
614 } // end anonymous namespace
615
616 // getFeasibleSuccessors - Return a vector of booleans to indicate which
617 // successors are reachable from a given terminator instruction.
getFeasibleSuccessors(TerminatorInst & TI,SmallVectorImpl<bool> & Succs)618 void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
619 SmallVectorImpl<bool> &Succs) {
620 Succs.resize(TI.getNumSuccessors());
621 if (auto *BI = dyn_cast<BranchInst>(&TI)) {
622 if (BI->isUnconditional()) {
623 Succs[0] = true;
624 return;
625 }
626
627 LatticeVal BCValue = getValueState(BI->getCondition());
628 ConstantInt *CI = BCValue.getConstantInt();
629 if (!CI) {
630 // Overdefined condition variables, and branches on unfoldable constant
631 // conditions, mean the branch could go either way.
632 if (!BCValue.isUnknown())
633 Succs[0] = Succs[1] = true;
634 return;
635 }
636
637 // Constant condition variables mean the branch can only go a single way.
638 Succs[CI->isZero()] = true;
639 return;
640 }
641
642 // Unwinding instructions successors are always executable.
643 if (TI.isExceptional()) {
644 Succs.assign(TI.getNumSuccessors(), true);
645 return;
646 }
647
648 if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
649 if (!SI->getNumCases()) {
650 Succs[0] = true;
651 return;
652 }
653 LatticeVal SCValue = getValueState(SI->getCondition());
654 ConstantInt *CI = SCValue.getConstantInt();
655
656 if (!CI) { // Overdefined or unknown condition?
657 // All destinations are executable!
658 if (!SCValue.isUnknown())
659 Succs.assign(TI.getNumSuccessors(), true);
660 return;
661 }
662
663 Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
664 return;
665 }
666
667 // In case of indirect branch and its address is a blockaddress, we mark
668 // the target as executable.
669 if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
670 // Casts are folded by visitCastInst.
671 LatticeVal IBRValue = getValueState(IBR->getAddress());
672 BlockAddress *Addr = IBRValue.getBlockAddress();
673 if (!Addr) { // Overdefined or unknown condition?
674 // All destinations are executable!
675 if (!IBRValue.isUnknown())
676 Succs.assign(TI.getNumSuccessors(), true);
677 return;
678 }
679
680 BasicBlock* T = Addr->getBasicBlock();
681 assert(Addr->getFunction() == T->getParent() &&
682 "Block address of a different function ?");
683 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
684 // This is the target.
685 if (IBR->getDestination(i) == T) {
686 Succs[i] = true;
687 return;
688 }
689 }
690
691 // If we didn't find our destination in the IBR successor list, then we
692 // have undefined behavior. Its ok to assume no successor is executable.
693 return;
694 }
695
696 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
697 llvm_unreachable("SCCP: Don't know how to handle this terminator!");
698 }
699
700 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
701 // block to the 'To' basic block is currently feasible.
isEdgeFeasible(BasicBlock * From,BasicBlock * To)702 bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
703 // Check if we've called markEdgeExecutable on the edge yet. (We could
704 // be more aggressive and try to consider edges which haven't been marked
705 // yet, but there isn't any need.)
706 return KnownFeasibleEdges.count(Edge(From, To));
707 }
708
709 // visit Implementations - Something changed in this instruction, either an
710 // operand made a transition, or the instruction is newly executable. Change
711 // the value type of I to reflect these changes if appropriate. This method
712 // makes sure to do the following actions:
713 //
714 // 1. If a phi node merges two constants in, and has conflicting value coming
715 // from different branches, or if the PHI node merges in an overdefined
716 // value, then the PHI node becomes overdefined.
717 // 2. If a phi node merges only constants in, and they all agree on value, the
718 // PHI node becomes a constant value equal to that.
719 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
720 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
721 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
722 // 6. If a conditional branch has a value that is constant, make the selected
723 // destination executable
724 // 7. If a conditional branch has a value that is overdefined, make all
725 // successors executable.
visitPHINode(PHINode & PN)726 void SCCPSolver::visitPHINode(PHINode &PN) {
727 // If this PN returns a struct, just mark the result overdefined.
728 // TODO: We could do a lot better than this if code actually uses this.
729 if (PN.getType()->isStructTy())
730 return (void)markOverdefined(&PN);
731
732 if (getValueState(&PN).isOverdefined())
733 return; // Quick exit
734
735 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
736 // and slow us down a lot. Just mark them overdefined.
737 if (PN.getNumIncomingValues() > 64)
738 return (void)markOverdefined(&PN);
739
740 // Look at all of the executable operands of the PHI node. If any of them
741 // are overdefined, the PHI becomes overdefined as well. If they are all
742 // constant, and they agree with each other, the PHI becomes the identical
743 // constant. If they are constant and don't agree, the PHI is overdefined.
744 // If there are no executable operands, the PHI remains unknown.
745 Constant *OperandVal = nullptr;
746 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
747 LatticeVal IV = getValueState(PN.getIncomingValue(i));
748 if (IV.isUnknown()) continue; // Doesn't influence PHI node.
749
750 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
751 continue;
752
753 if (IV.isOverdefined()) // PHI node becomes overdefined!
754 return (void)markOverdefined(&PN);
755
756 if (!OperandVal) { // Grab the first value.
757 OperandVal = IV.getConstant();
758 continue;
759 }
760
761 // There is already a reachable operand. If we conflict with it,
762 // then the PHI node becomes overdefined. If we agree with it, we
763 // can continue on.
764
765 // Check to see if there are two different constants merging, if so, the PHI
766 // node is overdefined.
767 if (IV.getConstant() != OperandVal)
768 return (void)markOverdefined(&PN);
769 }
770
771 // If we exited the loop, this means that the PHI node only has constant
772 // arguments that agree with each other(and OperandVal is the constant) or
773 // OperandVal is null because there are no defined incoming arguments. If
774 // this is the case, the PHI remains unknown.
775 if (OperandVal)
776 markConstant(&PN, OperandVal); // Acquire operand value
777 }
778
visitReturnInst(ReturnInst & I)779 void SCCPSolver::visitReturnInst(ReturnInst &I) {
780 if (I.getNumOperands() == 0) return; // ret void
781
782 Function *F = I.getParent()->getParent();
783 Value *ResultOp = I.getOperand(0);
784
785 // If we are tracking the return value of this function, merge it in.
786 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
787 DenseMap<Function*, LatticeVal>::iterator TFRVI =
788 TrackedRetVals.find(F);
789 if (TFRVI != TrackedRetVals.end()) {
790 mergeInValue(TFRVI->second, F, getValueState(ResultOp));
791 return;
792 }
793 }
794
795 // Handle functions that return multiple values.
796 if (!TrackedMultipleRetVals.empty()) {
797 if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
798 if (MRVFunctionsTracked.count(F))
799 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
800 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
801 getStructValueState(ResultOp, i));
802 }
803 }
804
visitTerminatorInst(TerminatorInst & TI)805 void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
806 SmallVector<bool, 16> SuccFeasible;
807 getFeasibleSuccessors(TI, SuccFeasible);
808
809 BasicBlock *BB = TI.getParent();
810
811 // Mark all feasible successors executable.
812 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
813 if (SuccFeasible[i])
814 markEdgeExecutable(BB, TI.getSuccessor(i));
815 }
816
visitCastInst(CastInst & I)817 void SCCPSolver::visitCastInst(CastInst &I) {
818 LatticeVal OpSt = getValueState(I.getOperand(0));
819 if (OpSt.isOverdefined()) // Inherit overdefinedness of operand
820 markOverdefined(&I);
821 else if (OpSt.isConstant()) {
822 // Fold the constant as we build.
823 Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(),
824 I.getType(), DL);
825 if (isa<UndefValue>(C))
826 return;
827 // Propagate constant value
828 markConstant(&I, C);
829 }
830 }
831
visitExtractValueInst(ExtractValueInst & EVI)832 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
833 // If this returns a struct, mark all elements over defined, we don't track
834 // structs in structs.
835 if (EVI.getType()->isStructTy())
836 return (void)markOverdefined(&EVI);
837
838 // If this is extracting from more than one level of struct, we don't know.
839 if (EVI.getNumIndices() != 1)
840 return (void)markOverdefined(&EVI);
841
842 Value *AggVal = EVI.getAggregateOperand();
843 if (AggVal->getType()->isStructTy()) {
844 unsigned i = *EVI.idx_begin();
845 LatticeVal EltVal = getStructValueState(AggVal, i);
846 mergeInValue(getValueState(&EVI), &EVI, EltVal);
847 } else {
848 // Otherwise, must be extracting from an array.
849 return (void)markOverdefined(&EVI);
850 }
851 }
852
visitInsertValueInst(InsertValueInst & IVI)853 void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
854 auto *STy = dyn_cast<StructType>(IVI.getType());
855 if (!STy)
856 return (void)markOverdefined(&IVI);
857
858 // If this has more than one index, we can't handle it, drive all results to
859 // undef.
860 if (IVI.getNumIndices() != 1)
861 return (void)markOverdefined(&IVI);
862
863 Value *Aggr = IVI.getAggregateOperand();
864 unsigned Idx = *IVI.idx_begin();
865
866 // Compute the result based on what we're inserting.
867 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
868 // This passes through all values that aren't the inserted element.
869 if (i != Idx) {
870 LatticeVal EltVal = getStructValueState(Aggr, i);
871 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
872 continue;
873 }
874
875 Value *Val = IVI.getInsertedValueOperand();
876 if (Val->getType()->isStructTy())
877 // We don't track structs in structs.
878 markOverdefined(getStructValueState(&IVI, i), &IVI);
879 else {
880 LatticeVal InVal = getValueState(Val);
881 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
882 }
883 }
884 }
885
visitSelectInst(SelectInst & I)886 void SCCPSolver::visitSelectInst(SelectInst &I) {
887 // If this select returns a struct, just mark the result overdefined.
888 // TODO: We could do a lot better than this if code actually uses this.
889 if (I.getType()->isStructTy())
890 return (void)markOverdefined(&I);
891
892 LatticeVal CondValue = getValueState(I.getCondition());
893 if (CondValue.isUnknown())
894 return;
895
896 if (ConstantInt *CondCB = CondValue.getConstantInt()) {
897 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
898 mergeInValue(&I, getValueState(OpVal));
899 return;
900 }
901
902 // Otherwise, the condition is overdefined or a constant we can't evaluate.
903 // See if we can produce something better than overdefined based on the T/F
904 // value.
905 LatticeVal TVal = getValueState(I.getTrueValue());
906 LatticeVal FVal = getValueState(I.getFalseValue());
907
908 // select ?, C, C -> C.
909 if (TVal.isConstant() && FVal.isConstant() &&
910 TVal.getConstant() == FVal.getConstant())
911 return (void)markConstant(&I, FVal.getConstant());
912
913 if (TVal.isUnknown()) // select ?, undef, X -> X.
914 return (void)mergeInValue(&I, FVal);
915 if (FVal.isUnknown()) // select ?, X, undef -> X.
916 return (void)mergeInValue(&I, TVal);
917 markOverdefined(&I);
918 }
919
920 // Handle Binary Operators.
visitBinaryOperator(Instruction & I)921 void SCCPSolver::visitBinaryOperator(Instruction &I) {
922 LatticeVal V1State = getValueState(I.getOperand(0));
923 LatticeVal V2State = getValueState(I.getOperand(1));
924
925 LatticeVal &IV = ValueState[&I];
926 if (IV.isOverdefined()) return;
927
928 if (V1State.isConstant() && V2State.isConstant()) {
929 Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
930 V2State.getConstant());
931 // X op Y -> undef.
932 if (isa<UndefValue>(C))
933 return;
934 return (void)markConstant(IV, &I, C);
935 }
936
937 // If something is undef, wait for it to resolve.
938 if (!V1State.isOverdefined() && !V2State.isOverdefined())
939 return;
940
941 // Otherwise, one of our operands is overdefined. Try to produce something
942 // better than overdefined with some tricks.
943 // If this is 0 / Y, it doesn't matter that the second operand is
944 // overdefined, and we can replace it with zero.
945 if (I.getOpcode() == Instruction::UDiv || I.getOpcode() == Instruction::SDiv)
946 if (V1State.isConstant() && V1State.getConstant()->isNullValue())
947 return (void)markConstant(IV, &I, V1State.getConstant());
948
949 // If this is:
950 // -> AND/MUL with 0
951 // -> OR with -1
952 // it doesn't matter that the other operand is overdefined.
953 if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
954 I.getOpcode() == Instruction::Or) {
955 LatticeVal *NonOverdefVal = nullptr;
956 if (!V1State.isOverdefined())
957 NonOverdefVal = &V1State;
958 else if (!V2State.isOverdefined())
959 NonOverdefVal = &V2State;
960
961 if (NonOverdefVal) {
962 if (NonOverdefVal->isUnknown())
963 return;
964
965 if (I.getOpcode() == Instruction::And ||
966 I.getOpcode() == Instruction::Mul) {
967 // X and 0 = 0
968 // X * 0 = 0
969 if (NonOverdefVal->getConstant()->isNullValue())
970 return (void)markConstant(IV, &I, NonOverdefVal->getConstant());
971 } else {
972 // X or -1 = -1
973 if (ConstantInt *CI = NonOverdefVal->getConstantInt())
974 if (CI->isMinusOne())
975 return (void)markConstant(IV, &I, NonOverdefVal->getConstant());
976 }
977 }
978 }
979
980 markOverdefined(&I);
981 }
982
983 // Handle ICmpInst instruction.
visitCmpInst(CmpInst & I)984 void SCCPSolver::visitCmpInst(CmpInst &I) {
985 LatticeVal &IV = ValueState[&I];
986 if (IV.isOverdefined()) return;
987
988 Value *Op1 = I.getOperand(0);
989 Value *Op2 = I.getOperand(1);
990
991 // For parameters, use ParamState which includes constant range info if
992 // available.
993 auto V1Param = ParamState.find(Op1);
994 ValueLatticeElement V1State = (V1Param != ParamState.end())
995 ? V1Param->second
996 : getValueState(Op1).toValueLattice();
997
998 auto V2Param = ParamState.find(Op2);
999 ValueLatticeElement V2State = V2Param != ParamState.end()
1000 ? V2Param->second
1001 : getValueState(Op2).toValueLattice();
1002
1003 Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
1004 if (C) {
1005 if (isa<UndefValue>(C))
1006 return;
1007 LatticeVal CV;
1008 CV.markConstant(C);
1009 mergeInValue(&I, CV);
1010 return;
1011 }
1012
1013 // If operands are still unknown, wait for it to resolve.
1014 if (!V1State.isOverdefined() && !V2State.isOverdefined() && !IV.isConstant())
1015 return;
1016
1017 markOverdefined(&I);
1018 }
1019
1020 // Handle getelementptr instructions. If all operands are constants then we
1021 // can turn this into a getelementptr ConstantExpr.
visitGetElementPtrInst(GetElementPtrInst & I)1022 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
1023 if (ValueState[&I].isOverdefined()) return;
1024
1025 SmallVector<Constant*, 8> Operands;
1026 Operands.reserve(I.getNumOperands());
1027
1028 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1029 LatticeVal State = getValueState(I.getOperand(i));
1030 if (State.isUnknown())
1031 return; // Operands are not resolved yet.
1032
1033 if (State.isOverdefined())
1034 return (void)markOverdefined(&I);
1035
1036 assert(State.isConstant() && "Unknown state!");
1037 Operands.push_back(State.getConstant());
1038 }
1039
1040 Constant *Ptr = Operands[0];
1041 auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
1042 Constant *C =
1043 ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
1044 if (isa<UndefValue>(C))
1045 return;
1046 markConstant(&I, C);
1047 }
1048
visitStoreInst(StoreInst & SI)1049 void SCCPSolver::visitStoreInst(StoreInst &SI) {
1050 // If this store is of a struct, ignore it.
1051 if (SI.getOperand(0)->getType()->isStructTy())
1052 return;
1053
1054 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1055 return;
1056
1057 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1058 DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV);
1059 if (I == TrackedGlobals.end() || I->second.isOverdefined()) return;
1060
1061 // Get the value we are storing into the global, then merge it.
1062 mergeInValue(I->second, GV, getValueState(SI.getOperand(0)));
1063 if (I->second.isOverdefined())
1064 TrackedGlobals.erase(I); // No need to keep tracking this!
1065 }
1066
1067 // Handle load instructions. If the operand is a constant pointer to a constant
1068 // global, we can replace the load with the loaded constant value!
visitLoadInst(LoadInst & I)1069 void SCCPSolver::visitLoadInst(LoadInst &I) {
1070 // If this load is of a struct, just mark the result overdefined.
1071 if (I.getType()->isStructTy())
1072 return (void)markOverdefined(&I);
1073
1074 LatticeVal PtrVal = getValueState(I.getOperand(0));
1075 if (PtrVal.isUnknown()) return; // The pointer is not resolved yet!
1076
1077 LatticeVal &IV = ValueState[&I];
1078 if (IV.isOverdefined()) return;
1079
1080 if (!PtrVal.isConstant() || I.isVolatile())
1081 return (void)markOverdefined(IV, &I);
1082
1083 Constant *Ptr = PtrVal.getConstant();
1084
1085 // load null is undefined.
1086 if (isa<ConstantPointerNull>(Ptr)) {
1087 if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
1088 return (void)markOverdefined(IV, &I);
1089 else
1090 return;
1091 }
1092
1093 // Transform load (constant global) into the value loaded.
1094 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1095 if (!TrackedGlobals.empty()) {
1096 // If we are tracking this global, merge in the known value for it.
1097 DenseMap<GlobalVariable*, LatticeVal>::iterator It =
1098 TrackedGlobals.find(GV);
1099 if (It != TrackedGlobals.end()) {
1100 mergeInValue(IV, &I, It->second);
1101 return;
1102 }
1103 }
1104 }
1105
1106 // Transform load from a constant into a constant if possible.
1107 if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
1108 if (isa<UndefValue>(C))
1109 return;
1110 return (void)markConstant(IV, &I, C);
1111 }
1112
1113 // Otherwise we cannot say for certain what value this load will produce.
1114 // Bail out.
1115 markOverdefined(IV, &I);
1116 }
1117
visitCallSite(CallSite CS)1118 void SCCPSolver::visitCallSite(CallSite CS) {
1119 Function *F = CS.getCalledFunction();
1120 Instruction *I = CS.getInstruction();
1121
1122 // The common case is that we aren't tracking the callee, either because we
1123 // are not doing interprocedural analysis or the callee is indirect, or is
1124 // external. Handle these cases first.
1125 if (!F || F->isDeclaration()) {
1126 CallOverdefined:
1127 // Void return and not tracking callee, just bail.
1128 if (I->getType()->isVoidTy()) return;
1129
1130 // Otherwise, if we have a single return value case, and if the function is
1131 // a declaration, maybe we can constant fold it.
1132 if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
1133 canConstantFoldCallTo(CS, F)) {
1134 SmallVector<Constant*, 8> Operands;
1135 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
1136 AI != E; ++AI) {
1137 LatticeVal State = getValueState(*AI);
1138
1139 if (State.isUnknown())
1140 return; // Operands are not resolved yet.
1141 if (State.isOverdefined())
1142 return (void)markOverdefined(I);
1143 assert(State.isConstant() && "Unknown state!");
1144 Operands.push_back(State.getConstant());
1145 }
1146
1147 if (getValueState(I).isOverdefined())
1148 return;
1149
1150 // If we can constant fold this, mark the result of the call as a
1151 // constant.
1152 if (Constant *C = ConstantFoldCall(CS, F, Operands, TLI)) {
1153 // call -> undef.
1154 if (isa<UndefValue>(C))
1155 return;
1156 return (void)markConstant(I, C);
1157 }
1158 }
1159
1160 // Otherwise, we don't know anything about this call, mark it overdefined.
1161 return (void)markOverdefined(I);
1162 }
1163
1164 // If this is a local function that doesn't have its address taken, mark its
1165 // entry block executable and merge in the actual arguments to the call into
1166 // the formal arguments of the function.
1167 if (!TrackingIncomingArguments.empty() && TrackingIncomingArguments.count(F)){
1168 MarkBlockExecutable(&F->front());
1169
1170 // Propagate information from this call site into the callee.
1171 CallSite::arg_iterator CAI = CS.arg_begin();
1172 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1173 AI != E; ++AI, ++CAI) {
1174 // If this argument is byval, and if the function is not readonly, there
1175 // will be an implicit copy formed of the input aggregate.
1176 if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1177 markOverdefined(&*AI);
1178 continue;
1179 }
1180
1181 if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1182 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1183 LatticeVal CallArg = getStructValueState(*CAI, i);
1184 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg);
1185 }
1186 } else {
1187 // Most other parts of the Solver still only use the simpler value
1188 // lattice, so we propagate changes for parameters to both lattices.
1189 LatticeVal ConcreteArgument = getValueState(*CAI);
1190 bool ParamChanged =
1191 getParamState(&*AI).mergeIn(ConcreteArgument.toValueLattice(), DL);
1192 bool ValueChanged = mergeInValue(&*AI, ConcreteArgument);
1193 // Add argument to work list, if the state of a parameter changes but
1194 // ValueState does not change (because it is already overdefined there),
1195 // We have to take changes in ParamState into account, as it is used
1196 // when evaluating Cmp instructions.
1197 if (!ValueChanged && ParamChanged)
1198 pushToWorkList(ValueState[&*AI], &*AI);
1199 }
1200 }
1201 }
1202
1203 // If this is a single/zero retval case, see if we're tracking the function.
1204 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1205 if (!MRVFunctionsTracked.count(F))
1206 goto CallOverdefined; // Not tracking this callee.
1207
1208 // If we are tracking this callee, propagate the result of the function
1209 // into this call site.
1210 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1211 mergeInValue(getStructValueState(I, i), I,
1212 TrackedMultipleRetVals[std::make_pair(F, i)]);
1213 } else {
1214 DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
1215 if (TFRVI == TrackedRetVals.end())
1216 goto CallOverdefined; // Not tracking this callee.
1217
1218 // If so, propagate the return value of the callee into this call result.
1219 mergeInValue(I, TFRVI->second);
1220 }
1221 }
1222
Solve()1223 void SCCPSolver::Solve() {
1224 // Process the work lists until they are empty!
1225 while (!BBWorkList.empty() || !InstWorkList.empty() ||
1226 !OverdefinedInstWorkList.empty()) {
1227 // Process the overdefined instruction's work list first, which drives other
1228 // things to overdefined more quickly.
1229 while (!OverdefinedInstWorkList.empty()) {
1230 Value *I = OverdefinedInstWorkList.pop_back_val();
1231
1232 LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1233
1234 // "I" got into the work list because it either made the transition from
1235 // bottom to constant, or to overdefined.
1236 //
1237 // Anything on this worklist that is overdefined need not be visited
1238 // since all of its users will have already been marked as overdefined
1239 // Update all of the users of this instruction's value.
1240 //
1241 for (User *U : I->users())
1242 if (auto *UI = dyn_cast<Instruction>(U))
1243 OperandChangedState(UI);
1244 }
1245
1246 // Process the instruction work list.
1247 while (!InstWorkList.empty()) {
1248 Value *I = InstWorkList.pop_back_val();
1249
1250 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1251
1252 // "I" got into the work list because it made the transition from undef to
1253 // constant.
1254 //
1255 // Anything on this worklist that is overdefined need not be visited
1256 // since all of its users will have already been marked as overdefined.
1257 // Update all of the users of this instruction's value.
1258 //
1259 if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1260 for (User *U : I->users())
1261 if (auto *UI = dyn_cast<Instruction>(U))
1262 OperandChangedState(UI);
1263 }
1264
1265 // Process the basic block work list.
1266 while (!BBWorkList.empty()) {
1267 BasicBlock *BB = BBWorkList.back();
1268 BBWorkList.pop_back();
1269
1270 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1271
1272 // Notify all instructions in this basic block that they are newly
1273 // executable.
1274 visit(BB);
1275 }
1276 }
1277 }
1278
1279 /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
1280 /// that branches on undef values cannot reach any of their successors.
1281 /// However, this is not a safe assumption. After we solve dataflow, this
1282 /// method should be use to handle this. If this returns true, the solver
1283 /// should be rerun.
1284 ///
1285 /// This method handles this by finding an unresolved branch and marking it one
1286 /// of the edges from the block as being feasible, even though the condition
1287 /// doesn't say it would otherwise be. This allows SCCP to find the rest of the
1288 /// CFG and only slightly pessimizes the analysis results (by marking one,
1289 /// potentially infeasible, edge feasible). This cannot usefully modify the
1290 /// constraints on the condition of the branch, as that would impact other users
1291 /// of the value.
1292 ///
1293 /// This scan also checks for values that use undefs, whose results are actually
1294 /// defined. For example, 'zext i8 undef to i32' should produce all zeros
1295 /// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero,
1296 /// even if X isn't defined.
ResolvedUndefsIn(Function & F)1297 bool SCCPSolver::ResolvedUndefsIn(Function &F) {
1298 for (BasicBlock &BB : F) {
1299 if (!BBExecutable.count(&BB))
1300 continue;
1301
1302 for (Instruction &I : BB) {
1303 // Look for instructions which produce undef values.
1304 if (I.getType()->isVoidTy()) continue;
1305
1306 if (auto *STy = dyn_cast<StructType>(I.getType())) {
1307 // Only a few things that can be structs matter for undef.
1308
1309 // Tracked calls must never be marked overdefined in ResolvedUndefsIn.
1310 if (CallSite CS = CallSite(&I))
1311 if (Function *F = CS.getCalledFunction())
1312 if (MRVFunctionsTracked.count(F))
1313 continue;
1314
1315 // extractvalue and insertvalue don't need to be marked; they are
1316 // tracked as precisely as their operands.
1317 if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1318 continue;
1319
1320 // Send the results of everything else to overdefined. We could be
1321 // more precise than this but it isn't worth bothering.
1322 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1323 LatticeVal &LV = getStructValueState(&I, i);
1324 if (LV.isUnknown())
1325 markOverdefined(LV, &I);
1326 }
1327 continue;
1328 }
1329
1330 LatticeVal &LV = getValueState(&I);
1331 if (!LV.isUnknown()) continue;
1332
1333 // extractvalue is safe; check here because the argument is a struct.
1334 if (isa<ExtractValueInst>(I))
1335 continue;
1336
1337 // Compute the operand LatticeVals, for convenience below.
1338 // Anything taking a struct is conservatively assumed to require
1339 // overdefined markings.
1340 if (I.getOperand(0)->getType()->isStructTy()) {
1341 markOverdefined(&I);
1342 return true;
1343 }
1344 LatticeVal Op0LV = getValueState(I.getOperand(0));
1345 LatticeVal Op1LV;
1346 if (I.getNumOperands() == 2) {
1347 if (I.getOperand(1)->getType()->isStructTy()) {
1348 markOverdefined(&I);
1349 return true;
1350 }
1351
1352 Op1LV = getValueState(I.getOperand(1));
1353 }
1354 // If this is an instructions whose result is defined even if the input is
1355 // not fully defined, propagate the information.
1356 Type *ITy = I.getType();
1357 switch (I.getOpcode()) {
1358 case Instruction::Add:
1359 case Instruction::Sub:
1360 case Instruction::Trunc:
1361 case Instruction::FPTrunc:
1362 case Instruction::BitCast:
1363 break; // Any undef -> undef
1364 case Instruction::FSub:
1365 case Instruction::FAdd:
1366 case Instruction::FMul:
1367 case Instruction::FDiv:
1368 case Instruction::FRem:
1369 // Floating-point binary operation: be conservative.
1370 if (Op0LV.isUnknown() && Op1LV.isUnknown())
1371 markForcedConstant(&I, Constant::getNullValue(ITy));
1372 else
1373 markOverdefined(&I);
1374 return true;
1375 case Instruction::ZExt:
1376 case Instruction::SExt:
1377 case Instruction::FPToUI:
1378 case Instruction::FPToSI:
1379 case Instruction::FPExt:
1380 case Instruction::PtrToInt:
1381 case Instruction::IntToPtr:
1382 case Instruction::SIToFP:
1383 case Instruction::UIToFP:
1384 // undef -> 0; some outputs are impossible
1385 markForcedConstant(&I, Constant::getNullValue(ITy));
1386 return true;
1387 case Instruction::Mul:
1388 case Instruction::And:
1389 // Both operands undef -> undef
1390 if (Op0LV.isUnknown() && Op1LV.isUnknown())
1391 break;
1392 // undef * X -> 0. X could be zero.
1393 // undef & X -> 0. X could be zero.
1394 markForcedConstant(&I, Constant::getNullValue(ITy));
1395 return true;
1396 case Instruction::Or:
1397 // Both operands undef -> undef
1398 if (Op0LV.isUnknown() && Op1LV.isUnknown())
1399 break;
1400 // undef | X -> -1. X could be -1.
1401 markForcedConstant(&I, Constant::getAllOnesValue(ITy));
1402 return true;
1403 case Instruction::Xor:
1404 // undef ^ undef -> 0; strictly speaking, this is not strictly
1405 // necessary, but we try to be nice to people who expect this
1406 // behavior in simple cases
1407 if (Op0LV.isUnknown() && Op1LV.isUnknown()) {
1408 markForcedConstant(&I, Constant::getNullValue(ITy));
1409 return true;
1410 }
1411 // undef ^ X -> undef
1412 break;
1413 case Instruction::SDiv:
1414 case Instruction::UDiv:
1415 case Instruction::SRem:
1416 case Instruction::URem:
1417 // X / undef -> undef. No change.
1418 // X % undef -> undef. No change.
1419 if (Op1LV.isUnknown()) break;
1420
1421 // X / 0 -> undef. No change.
1422 // X % 0 -> undef. No change.
1423 if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue())
1424 break;
1425
1426 // undef / X -> 0. X could be maxint.
1427 // undef % X -> 0. X could be 1.
1428 markForcedConstant(&I, Constant::getNullValue(ITy));
1429 return true;
1430 case Instruction::AShr:
1431 // X >>a undef -> undef.
1432 if (Op1LV.isUnknown()) break;
1433
1434 // Shifting by the bitwidth or more is undefined.
1435 if (Op1LV.isConstant()) {
1436 if (auto *ShiftAmt = Op1LV.getConstantInt())
1437 if (ShiftAmt->getLimitedValue() >=
1438 ShiftAmt->getType()->getScalarSizeInBits())
1439 break;
1440 }
1441
1442 // undef >>a X -> 0
1443 markForcedConstant(&I, Constant::getNullValue(ITy));
1444 return true;
1445 case Instruction::LShr:
1446 case Instruction::Shl:
1447 // X << undef -> undef.
1448 // X >> undef -> undef.
1449 if (Op1LV.isUnknown()) break;
1450
1451 // Shifting by the bitwidth or more is undefined.
1452 if (Op1LV.isConstant()) {
1453 if (auto *ShiftAmt = Op1LV.getConstantInt())
1454 if (ShiftAmt->getLimitedValue() >=
1455 ShiftAmt->getType()->getScalarSizeInBits())
1456 break;
1457 }
1458
1459 // undef << X -> 0
1460 // undef >> X -> 0
1461 markForcedConstant(&I, Constant::getNullValue(ITy));
1462 return true;
1463 case Instruction::Select:
1464 Op1LV = getValueState(I.getOperand(1));
1465 // undef ? X : Y -> X or Y. There could be commonality between X/Y.
1466 if (Op0LV.isUnknown()) {
1467 if (!Op1LV.isConstant()) // Pick the constant one if there is any.
1468 Op1LV = getValueState(I.getOperand(2));
1469 } else if (Op1LV.isUnknown()) {
1470 // c ? undef : undef -> undef. No change.
1471 Op1LV = getValueState(I.getOperand(2));
1472 if (Op1LV.isUnknown())
1473 break;
1474 // Otherwise, c ? undef : x -> x.
1475 } else {
1476 // Leave Op1LV as Operand(1)'s LatticeValue.
1477 }
1478
1479 if (Op1LV.isConstant())
1480 markForcedConstant(&I, Op1LV.getConstant());
1481 else
1482 markOverdefined(&I);
1483 return true;
1484 case Instruction::Load:
1485 // A load here means one of two things: a load of undef from a global,
1486 // a load from an unknown pointer. Either way, having it return undef
1487 // is okay.
1488 break;
1489 case Instruction::ICmp:
1490 // X == undef -> undef. Other comparisons get more complicated.
1491 Op0LV = getValueState(I.getOperand(0));
1492 Op1LV = getValueState(I.getOperand(1));
1493
1494 if ((Op0LV.isUnknown() || Op1LV.isUnknown()) &&
1495 cast<ICmpInst>(&I)->isEquality())
1496 break;
1497 markOverdefined(&I);
1498 return true;
1499 case Instruction::Call:
1500 case Instruction::Invoke:
1501 // There are two reasons a call can have an undef result
1502 // 1. It could be tracked.
1503 // 2. It could be constant-foldable.
1504 // Because of the way we solve return values, tracked calls must
1505 // never be marked overdefined in ResolvedUndefsIn.
1506 if (Function *F = CallSite(&I).getCalledFunction())
1507 if (TrackedRetVals.count(F))
1508 break;
1509
1510 // If the call is constant-foldable, we mark it overdefined because
1511 // we do not know what return values are valid.
1512 markOverdefined(&I);
1513 return true;
1514 default:
1515 // If we don't know what should happen here, conservatively mark it
1516 // overdefined.
1517 markOverdefined(&I);
1518 return true;
1519 }
1520 }
1521
1522 // Check to see if we have a branch or switch on an undefined value. If so
1523 // we force the branch to go one way or the other to make the successor
1524 // values live. It doesn't really matter which way we force it.
1525 TerminatorInst *TI = BB.getTerminator();
1526 if (auto *BI = dyn_cast<BranchInst>(TI)) {
1527 if (!BI->isConditional()) continue;
1528 if (!getValueState(BI->getCondition()).isUnknown())
1529 continue;
1530
1531 // If the input to SCCP is actually branch on undef, fix the undef to
1532 // false.
1533 if (isa<UndefValue>(BI->getCondition())) {
1534 BI->setCondition(ConstantInt::getFalse(BI->getContext()));
1535 markEdgeExecutable(&BB, TI->getSuccessor(1));
1536 return true;
1537 }
1538
1539 // Otherwise, it is a branch on a symbolic value which is currently
1540 // considered to be undef. Make sure some edge is executable, so a
1541 // branch on "undef" always flows somewhere.
1542 // FIXME: Distinguish between dead code and an LLVM "undef" value.
1543 BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
1544 if (markEdgeExecutable(&BB, DefaultSuccessor))
1545 return true;
1546
1547 continue;
1548 }
1549
1550 if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
1551 // Indirect branch with no successor ?. Its ok to assume it branches
1552 // to no target.
1553 if (IBR->getNumSuccessors() < 1)
1554 continue;
1555
1556 if (!getValueState(IBR->getAddress()).isUnknown())
1557 continue;
1558
1559 // If the input to SCCP is actually branch on undef, fix the undef to
1560 // the first successor of the indirect branch.
1561 if (isa<UndefValue>(IBR->getAddress())) {
1562 IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
1563 markEdgeExecutable(&BB, IBR->getSuccessor(0));
1564 return true;
1565 }
1566
1567 // Otherwise, it is a branch on a symbolic value which is currently
1568 // considered to be undef. Make sure some edge is executable, so a
1569 // branch on "undef" always flows somewhere.
1570 // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
1571 // we can assume the branch has undefined behavior instead.
1572 BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
1573 if (markEdgeExecutable(&BB, DefaultSuccessor))
1574 return true;
1575
1576 continue;
1577 }
1578
1579 if (auto *SI = dyn_cast<SwitchInst>(TI)) {
1580 if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown())
1581 continue;
1582
1583 // If the input to SCCP is actually switch on undef, fix the undef to
1584 // the first constant.
1585 if (isa<UndefValue>(SI->getCondition())) {
1586 SI->setCondition(SI->case_begin()->getCaseValue());
1587 markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
1588 return true;
1589 }
1590
1591 // Otherwise, it is a branch on a symbolic value which is currently
1592 // considered to be undef. Make sure some edge is executable, so a
1593 // branch on "undef" always flows somewhere.
1594 // FIXME: Distinguish between dead code and an LLVM "undef" value.
1595 BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
1596 if (markEdgeExecutable(&BB, DefaultSuccessor))
1597 return true;
1598
1599 continue;
1600 }
1601 }
1602
1603 return false;
1604 }
1605
tryToReplaceWithConstant(SCCPSolver & Solver,Value * V)1606 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
1607 Constant *Const = nullptr;
1608 if (V->getType()->isStructTy()) {
1609 std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V);
1610 if (llvm::any_of(IVs,
1611 [](const LatticeVal &LV) { return LV.isOverdefined(); }))
1612 return false;
1613 std::vector<Constant *> ConstVals;
1614 auto *ST = dyn_cast<StructType>(V->getType());
1615 for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
1616 LatticeVal V = IVs[i];
1617 ConstVals.push_back(V.isConstant()
1618 ? V.getConstant()
1619 : UndefValue::get(ST->getElementType(i)));
1620 }
1621 Const = ConstantStruct::get(ST, ConstVals);
1622 } else {
1623 const LatticeVal &IV = Solver.getLatticeValueFor(V);
1624 if (IV.isOverdefined())
1625 return false;
1626
1627 Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
1628 }
1629 assert(Const && "Constant is nullptr here!");
1630
1631 // Replacing `musttail` instructions with constant breaks `musttail` invariant
1632 // unless the call itself can be removed
1633 CallInst *CI = dyn_cast<CallInst>(V);
1634 if (CI && CI->isMustTailCall() && !CI->isSafeToRemove()) {
1635 CallSite CS(CI);
1636 Function *F = CS.getCalledFunction();
1637
1638 // Don't zap returns of the callee
1639 if (F)
1640 Solver.AddMustTailCallee(F);
1641
1642 LLVM_DEBUG(dbgs() << " Can\'t treat the result of musttail call : " << *CI
1643 << " as a constant\n");
1644 return false;
1645 }
1646
1647 LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
1648
1649 // Replaces all of the uses of a variable with uses of the constant.
1650 V->replaceAllUsesWith(Const);
1651 return true;
1652 }
1653
1654 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
1655 // and return true if the function was modified.
runSCCP(Function & F,const DataLayout & DL,const TargetLibraryInfo * TLI)1656 static bool runSCCP(Function &F, const DataLayout &DL,
1657 const TargetLibraryInfo *TLI) {
1658 LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
1659 SCCPSolver Solver(DL, TLI);
1660
1661 // Mark the first block of the function as being executable.
1662 Solver.MarkBlockExecutable(&F.front());
1663
1664 // Mark all arguments to the function as being overdefined.
1665 for (Argument &AI : F.args())
1666 Solver.markOverdefined(&AI);
1667
1668 // Solve for constants.
1669 bool ResolvedUndefs = true;
1670 while (ResolvedUndefs) {
1671 Solver.Solve();
1672 LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
1673 ResolvedUndefs = Solver.ResolvedUndefsIn(F);
1674 }
1675
1676 bool MadeChanges = false;
1677
1678 // If we decided that there are basic blocks that are dead in this function,
1679 // delete their contents now. Note that we cannot actually delete the blocks,
1680 // as we cannot modify the CFG of the function.
1681
1682 for (BasicBlock &BB : F) {
1683 if (!Solver.isBlockExecutable(&BB)) {
1684 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
1685
1686 ++NumDeadBlocks;
1687 NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB);
1688
1689 MadeChanges = true;
1690 continue;
1691 }
1692
1693 // Iterate over all of the instructions in a function, replacing them with
1694 // constants if we have found them to be of constant values.
1695 for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
1696 Instruction *Inst = &*BI++;
1697 if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst))
1698 continue;
1699
1700 if (tryToReplaceWithConstant(Solver, Inst)) {
1701 if (isInstructionTriviallyDead(Inst))
1702 Inst->eraseFromParent();
1703 // Hey, we just changed something!
1704 MadeChanges = true;
1705 ++NumInstRemoved;
1706 }
1707 }
1708 }
1709
1710 return MadeChanges;
1711 }
1712
run(Function & F,FunctionAnalysisManager & AM)1713 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
1714 const DataLayout &DL = F.getParent()->getDataLayout();
1715 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1716 if (!runSCCP(F, DL, &TLI))
1717 return PreservedAnalyses::all();
1718
1719 auto PA = PreservedAnalyses();
1720 PA.preserve<GlobalsAA>();
1721 PA.preserveSet<CFGAnalyses>();
1722 return PA;
1723 }
1724
1725 namespace {
1726
1727 //===--------------------------------------------------------------------===//
1728 //
1729 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
1730 /// Sparse Conditional Constant Propagator.
1731 ///
1732 class SCCPLegacyPass : public FunctionPass {
1733 public:
1734 // Pass identification, replacement for typeid
1735 static char ID;
1736
SCCPLegacyPass()1737 SCCPLegacyPass() : FunctionPass(ID) {
1738 initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry());
1739 }
1740
getAnalysisUsage(AnalysisUsage & AU) const1741 void getAnalysisUsage(AnalysisUsage &AU) const override {
1742 AU.addRequired<TargetLibraryInfoWrapperPass>();
1743 AU.addPreserved<GlobalsAAWrapperPass>();
1744 AU.setPreservesCFG();
1745 }
1746
1747 // runOnFunction - Run the Sparse Conditional Constant Propagation
1748 // algorithm, and return true if the function was modified.
runOnFunction(Function & F)1749 bool runOnFunction(Function &F) override {
1750 if (skipFunction(F))
1751 return false;
1752 const DataLayout &DL = F.getParent()->getDataLayout();
1753 const TargetLibraryInfo *TLI =
1754 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1755 return runSCCP(F, DL, TLI);
1756 }
1757 };
1758
1759 } // end anonymous namespace
1760
1761 char SCCPLegacyPass::ID = 0;
1762
1763 INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp",
1764 "Sparse Conditional Constant Propagation", false, false)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)1765 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1766 INITIALIZE_PASS_END(SCCPLegacyPass, "sccp",
1767 "Sparse Conditional Constant Propagation", false, false)
1768
1769 // createSCCPPass - This is the public interface to this file.
1770 FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); }
1771
findReturnsToZap(Function & F,SmallVector<ReturnInst *,8> & ReturnsToZap,SCCPSolver & Solver)1772 static void findReturnsToZap(Function &F,
1773 SmallVector<ReturnInst *, 8> &ReturnsToZap,
1774 SCCPSolver &Solver) {
1775 // We can only do this if we know that nothing else can call the function.
1776 if (!Solver.isArgumentTrackedFunction(&F))
1777 return;
1778
1779 // There is a non-removable musttail call site of this function. Zapping
1780 // returns is not allowed.
1781 if (Solver.isMustTailCallee(&F)) {
1782 LLVM_DEBUG(dbgs() << "Can't zap returns of the function : " << F.getName()
1783 << " due to present musttail call of it\n");
1784 return;
1785 }
1786
1787 for (BasicBlock &BB : F) {
1788 if (CallInst *CI = BB.getTerminatingMustTailCall()) {
1789 LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
1790 << "musttail call : " << *CI << "\n");
1791 (void)CI;
1792 return;
1793 }
1794
1795 if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
1796 if (!isa<UndefValue>(RI->getOperand(0)))
1797 ReturnsToZap.push_back(RI);
1798 }
1799 }
1800
runIPSCCP(Module & M,const DataLayout & DL,const TargetLibraryInfo * TLI)1801 bool llvm::runIPSCCP(Module &M, const DataLayout &DL,
1802 const TargetLibraryInfo *TLI) {
1803 SCCPSolver Solver(DL, TLI);
1804
1805 // Loop over all functions, marking arguments to those with their addresses
1806 // taken or that are external as overdefined.
1807 for (Function &F : M) {
1808 if (F.isDeclaration())
1809 continue;
1810
1811 // Determine if we can track the function's return values. If so, add the
1812 // function to the solver's set of return-tracked functions.
1813 if (canTrackReturnsInterprocedurally(&F))
1814 Solver.AddTrackedFunction(&F);
1815
1816 // Determine if we can track the function's arguments. If so, add the
1817 // function to the solver's set of argument-tracked functions.
1818 if (canTrackArgumentsInterprocedurally(&F)) {
1819 Solver.AddArgumentTrackedFunction(&F);
1820 continue;
1821 }
1822
1823 // Assume the function is called.
1824 Solver.MarkBlockExecutable(&F.front());
1825
1826 // Assume nothing about the incoming arguments.
1827 for (Argument &AI : F.args())
1828 Solver.markOverdefined(&AI);
1829 }
1830
1831 // Determine if we can track any of the module's global variables. If so, add
1832 // the global variables we can track to the solver's set of tracked global
1833 // variables.
1834 for (GlobalVariable &G : M.globals()) {
1835 G.removeDeadConstantUsers();
1836 if (canTrackGlobalVariableInterprocedurally(&G))
1837 Solver.TrackValueOfGlobalVariable(&G);
1838 }
1839
1840 // Solve for constants.
1841 bool ResolvedUndefs = true;
1842 Solver.Solve();
1843 while (ResolvedUndefs) {
1844 LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
1845 ResolvedUndefs = false;
1846 for (Function &F : M)
1847 if (Solver.ResolvedUndefsIn(F)) {
1848 // We run Solve() after we resolved an undef in a function, because
1849 // we might deduce a fact that eliminates an undef in another function.
1850 Solver.Solve();
1851 ResolvedUndefs = true;
1852 }
1853 }
1854
1855 bool MadeChanges = false;
1856
1857 // Iterate over all of the instructions in the module, replacing them with
1858 // constants if we have found them to be of constant values.
1859 SmallVector<BasicBlock*, 512> BlocksToErase;
1860
1861 for (Function &F : M) {
1862 if (F.isDeclaration())
1863 continue;
1864
1865 if (Solver.isBlockExecutable(&F.front()))
1866 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;
1867 ++AI) {
1868 if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI)) {
1869 ++IPNumArgsElimed;
1870 continue;
1871 }
1872 }
1873
1874 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1875 if (!Solver.isBlockExecutable(&*BB)) {
1876 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
1877 ++NumDeadBlocks;
1878
1879 MadeChanges = true;
1880
1881 if (&*BB != &F.front())
1882 BlocksToErase.push_back(&*BB);
1883 continue;
1884 }
1885
1886 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
1887 Instruction *Inst = &*BI++;
1888 if (Inst->getType()->isVoidTy())
1889 continue;
1890 if (tryToReplaceWithConstant(Solver, Inst)) {
1891 if (Inst->isSafeToRemove())
1892 Inst->eraseFromParent();
1893 // Hey, we just changed something!
1894 MadeChanges = true;
1895 ++IPNumInstRemoved;
1896 }
1897 }
1898 }
1899
1900 // Change dead blocks to unreachable. We do it after replacing constants in
1901 // all executable blocks, because changeToUnreachable may remove PHI nodes
1902 // in executable blocks we found values for. The function's entry block is
1903 // not part of BlocksToErase, so we have to handle it separately.
1904 for (BasicBlock *BB : BlocksToErase)
1905 NumInstRemoved +=
1906 changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false);
1907 if (!Solver.isBlockExecutable(&F.front()))
1908 NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
1909 /*UseLLVMTrap=*/false);
1910
1911 // Now that all instructions in the function are constant folded, erase dead
1912 // blocks, because we can now use ConstantFoldTerminator to get rid of
1913 // in-edges.
1914 for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
1915 // If there are any PHI nodes in this successor, drop entries for BB now.
1916 BasicBlock *DeadBB = BlocksToErase[i];
1917 for (Value::user_iterator UI = DeadBB->user_begin(),
1918 UE = DeadBB->user_end();
1919 UI != UE;) {
1920 // Grab the user and then increment the iterator early, as the user
1921 // will be deleted. Step past all adjacent uses from the same user.
1922 auto *I = dyn_cast<Instruction>(*UI);
1923 do { ++UI; } while (UI != UE && *UI == I);
1924
1925 // Ignore blockaddress users; BasicBlock's dtor will handle them.
1926 if (!I) continue;
1927
1928 bool Folded = ConstantFoldTerminator(I->getParent());
1929 if (!Folded) {
1930 // If the branch can't be folded, we must have forced an edge
1931 // for an indeterminate value. Force the terminator to fold
1932 // to that edge.
1933 Constant *C;
1934 BasicBlock *Dest;
1935 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
1936 Dest = SI->case_begin()->getCaseSuccessor();
1937 C = SI->case_begin()->getCaseValue();
1938 } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1939 Dest = BI->getSuccessor(1);
1940 C = ConstantInt::getFalse(BI->getContext());
1941 } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) {
1942 Dest = IBR->getSuccessor(0);
1943 C = BlockAddress::get(IBR->getSuccessor(0));
1944 } else {
1945 llvm_unreachable("Unexpected terminator instruction");
1946 }
1947 assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
1948 "Didn't find feasible edge?");
1949 (void)Dest;
1950
1951 I->setOperand(0, C);
1952 Folded = ConstantFoldTerminator(I->getParent());
1953 }
1954 assert(Folded &&
1955 "Expect TermInst on constantint or blockaddress to be folded");
1956 (void) Folded;
1957 }
1958
1959 // Finally, delete the basic block.
1960 F.getBasicBlockList().erase(DeadBB);
1961 }
1962 BlocksToErase.clear();
1963 }
1964
1965 // If we inferred constant or undef return values for a function, we replaced
1966 // all call uses with the inferred value. This means we don't need to bother
1967 // actually returning anything from the function. Replace all return
1968 // instructions with return undef.
1969 //
1970 // Do this in two stages: first identify the functions we should process, then
1971 // actually zap their returns. This is important because we can only do this
1972 // if the address of the function isn't taken. In cases where a return is the
1973 // last use of a function, the order of processing functions would affect
1974 // whether other functions are optimizable.
1975 SmallVector<ReturnInst*, 8> ReturnsToZap;
1976
1977 const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
1978 for (const auto &I : RV) {
1979 Function *F = I.first;
1980 if (I.second.isOverdefined() || F->getReturnType()->isVoidTy())
1981 continue;
1982 findReturnsToZap(*F, ReturnsToZap, Solver);
1983 }
1984
1985 for (const auto &F : Solver.getMRVFunctionsTracked()) {
1986 assert(F->getReturnType()->isStructTy() &&
1987 "The return type should be a struct");
1988 StructType *STy = cast<StructType>(F->getReturnType());
1989 if (Solver.isStructLatticeConstant(F, STy))
1990 findReturnsToZap(*F, ReturnsToZap, Solver);
1991 }
1992
1993 // Zap all returns which we've identified as zap to change.
1994 for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
1995 Function *F = ReturnsToZap[i]->getParent()->getParent();
1996 ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
1997 }
1998
1999 // If we inferred constant or undef values for globals variables, we can
2000 // delete the global and any stores that remain to it.
2001 const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
2002 for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
2003 E = TG.end(); I != E; ++I) {
2004 GlobalVariable *GV = I->first;
2005 assert(!I->second.isOverdefined() &&
2006 "Overdefined values should have been taken out of the map!");
2007 LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
2008 << "' is constant!\n");
2009 while (!GV->use_empty()) {
2010 StoreInst *SI = cast<StoreInst>(GV->user_back());
2011 SI->eraseFromParent();
2012 }
2013 M.getGlobalList().erase(GV);
2014 ++IPNumGlobalConst;
2015 }
2016
2017 return MadeChanges;
2018 }
2019