LLVM 19.0.0git
SCCPSolver.cpp
Go to the documentation of this file.
1//===- SCCPSolver.cpp - SCCP Utility --------------------------- *- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// \file
10// This file implements the Sparse Conditional Constant Propagation (SCCP)
11// utility.
12//
13//===----------------------------------------------------------------------===//
14
21#include "llvm/IR/InstVisitor.h"
23#include "llvm/Support/Debug.h"
27#include <cassert>
28#include <utility>
29#include <vector>
30
31using namespace llvm;
32
33#define DEBUG_TYPE "sccp"
34
35// The maximum number of range extensions allowed for operations requiring
36// widening.
37static const unsigned MaxNumRangeExtensions = 10;
38
39/// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
43}
44
46 bool UndefAllowed) {
47 assert(Ty->isIntOrIntVectorTy() && "Should be int or int vector");
48 if (LV.isConstantRange(UndefAllowed))
49 return LV.getConstantRange();
50 return ConstantRange::getFull(Ty->getScalarSizeInBits());
51}
52
53namespace llvm {
54
56 return LV.isConstant() ||
58}
59
61 return !LV.isUnknownOrUndef() && !SCCPSolver::isConstant(LV);
62}
63
66 return true;
67
68 // Some instructions can be handled but are rejected above. Catch
69 // those cases by falling through to here.
70 // TODO: Mark globals as being constant earlier, so
71 // TODO: wouldInstructionBeTriviallyDead() knows that atomic loads
72 // TODO: are safe to remove.
73 return isa<LoadInst>(I);
74}
75
77 Constant *Const = getConstantOrNull(V);
78 if (!Const)
79 return false;
80 // Replacing `musttail` instructions with constant breaks `musttail` invariant
81 // unless the call itself can be removed.
82 // Calls with "clang.arc.attachedcall" implicitly use the return value and
83 // those uses cannot be updated with a constant.
84 CallBase *CB = dyn_cast<CallBase>(V);
85 if (CB && ((CB->isMustTailCall() &&
89
90 // Don't zap returns of the callee
91 if (F)
93
94 LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB
95 << " as a constant\n");
96 return false;
97 }
98
99 LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
100
101 // Replaces all of the uses of a variable with uses of the constant.
102 V->replaceAllUsesWith(Const);
103 return true;
104}
105
106/// Try to use \p Inst's value range from \p Solver to infer the NUW flag.
107static bool refineInstruction(SCCPSolver &Solver,
108 const SmallPtrSetImpl<Value *> &InsertedValues,
109 Instruction &Inst) {
110 bool Changed = false;
111 auto GetRange = [&Solver, &InsertedValues](Value *Op) {
112 if (auto *Const = dyn_cast<ConstantInt>(Op))
113 return ConstantRange(Const->getValue());
114 if (isa<Constant>(Op) || InsertedValues.contains(Op)) {
115 unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
116 return ConstantRange::getFull(Bitwidth);
117 }
118 return getConstantRange(Solver.getLatticeValueFor(Op), Op->getType(),
119 /*UndefAllowed=*/false);
120 };
121
122 if (isa<OverflowingBinaryOperator>(Inst)) {
123 if (Inst.hasNoSignedWrap() && Inst.hasNoUnsignedWrap())
124 return false;
125
126 auto RangeA = GetRange(Inst.getOperand(0));
127 auto RangeB = GetRange(Inst.getOperand(1));
128 if (!Inst.hasNoUnsignedWrap()) {
130 Instruction::BinaryOps(Inst.getOpcode()), RangeB,
132 if (NUWRange.contains(RangeA)) {
134 Changed = true;
135 }
136 }
137 if (!Inst.hasNoSignedWrap()) {
139 Instruction::BinaryOps(Inst.getOpcode()), RangeB,
141 if (NSWRange.contains(RangeA)) {
142 Inst.setHasNoSignedWrap();
143 Changed = true;
144 }
145 }
146 } else if (isa<PossiblyNonNegInst>(Inst) && !Inst.hasNonNeg()) {
147 auto Range = GetRange(Inst.getOperand(0));
148 if (Range.isAllNonNegative()) {
149 Inst.setNonNeg();
150 Changed = true;
151 }
152 } else if (TruncInst *TI = dyn_cast<TruncInst>(&Inst)) {
153 if (TI->hasNoSignedWrap() && TI->hasNoUnsignedWrap())
154 return false;
155
156 auto Range = GetRange(Inst.getOperand(0));
157 uint64_t DestWidth = TI->getDestTy()->getScalarSizeInBits();
158 if (!TI->hasNoUnsignedWrap()) {
159 if (Range.getActiveBits() <= DestWidth) {
160 TI->setHasNoUnsignedWrap(true);
161 Changed = true;
162 }
163 }
164 if (!TI->hasNoSignedWrap()) {
165 if (Range.getMinSignedBits() <= DestWidth) {
166 TI->setHasNoSignedWrap(true);
167 Changed = true;
168 }
169 }
170 }
171
172 return Changed;
173}
174
175/// Try to replace signed instructions with their unsigned equivalent.
176static bool replaceSignedInst(SCCPSolver &Solver,
177 SmallPtrSetImpl<Value *> &InsertedValues,
178 Instruction &Inst) {
179 // Determine if a signed value is known to be >= 0.
180 auto isNonNegative = [&Solver](Value *V) {
181 // If this value was constant-folded, it may not have a solver entry.
182 // Handle integers. Otherwise, return false.
183 if (auto *C = dyn_cast<Constant>(V)) {
184 auto *CInt = dyn_cast<ConstantInt>(C);
185 return CInt && !CInt->isNegative();
186 }
187 const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
188 return IV.isConstantRange(/*UndefAllowed=*/false) &&
189 IV.getConstantRange().isAllNonNegative();
190 };
191
192 Instruction *NewInst = nullptr;
193 switch (Inst.getOpcode()) {
194 case Instruction::SIToFP:
195 case Instruction::SExt: {
196 // If the source value is not negative, this is a zext/uitofp.
197 Value *Op0 = Inst.getOperand(0);
198 if (InsertedValues.count(Op0) || !isNonNegative(Op0))
199 return false;
200 NewInst = CastInst::Create(Inst.getOpcode() == Instruction::SExt
201 ? Instruction::ZExt
202 : Instruction::UIToFP,
203 Op0, Inst.getType(), "", Inst.getIterator());
204 NewInst->setNonNeg();
205 break;
206 }
207 case Instruction::AShr: {
208 // If the shifted value is not negative, this is a logical shift right.
209 Value *Op0 = Inst.getOperand(0);
210 if (InsertedValues.count(Op0) || !isNonNegative(Op0))
211 return false;
212 NewInst = BinaryOperator::CreateLShr(Op0, Inst.getOperand(1), "", Inst.getIterator());
213 NewInst->setIsExact(Inst.isExact());
214 break;
215 }
216 case Instruction::SDiv:
217 case Instruction::SRem: {
218 // If both operands are not negative, this is the same as udiv/urem.
219 Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1);
220 if (InsertedValues.count(Op0) || InsertedValues.count(Op1) ||
221 !isNonNegative(Op0) || !isNonNegative(Op1))
222 return false;
223 auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv
224 : Instruction::URem;
225 NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", Inst.getIterator());
226 if (Inst.getOpcode() == Instruction::SDiv)
227 NewInst->setIsExact(Inst.isExact());
228 break;
229 }
230 default:
231 return false;
232 }
233
234 // Wire up the new instruction and update state.
235 assert(NewInst && "Expected replacement instruction");
236 NewInst->takeName(&Inst);
237 InsertedValues.insert(NewInst);
238 Inst.replaceAllUsesWith(NewInst);
239 Solver.removeLatticeValueFor(&Inst);
240 Inst.eraseFromParent();
241 return true;
242}
243
245 SmallPtrSetImpl<Value *> &InsertedValues,
246 Statistic &InstRemovedStat,
247 Statistic &InstReplacedStat) {
248 bool MadeChanges = false;
249 for (Instruction &Inst : make_early_inc_range(BB)) {
250 if (Inst.getType()->isVoidTy())
251 continue;
252 if (tryToReplaceWithConstant(&Inst)) {
253 if (canRemoveInstruction(&Inst))
254 Inst.eraseFromParent();
255
256 MadeChanges = true;
257 ++InstRemovedStat;
258 } else if (replaceSignedInst(*this, InsertedValues, Inst)) {
259 MadeChanges = true;
260 ++InstReplacedStat;
261 } else if (refineInstruction(*this, InsertedValues, Inst)) {
262 MadeChanges = true;
263 }
264 }
265 return MadeChanges;
266}
267
269 BasicBlock *&NewUnreachableBB) const {
270 SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
271 bool HasNonFeasibleEdges = false;
272 for (BasicBlock *Succ : successors(BB)) {
273 if (isEdgeFeasible(BB, Succ))
274 FeasibleSuccessors.insert(Succ);
275 else
276 HasNonFeasibleEdges = true;
277 }
278
279 // All edges feasible, nothing to do.
280 if (!HasNonFeasibleEdges)
281 return false;
282
283 // SCCP can only determine non-feasible edges for br, switch and indirectbr.
284 Instruction *TI = BB->getTerminator();
285 assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
286 isa<IndirectBrInst>(TI)) &&
287 "Terminator must be a br, switch or indirectbr");
288
289 if (FeasibleSuccessors.size() == 0) {
290 // Branch on undef/poison, replace with unreachable.
293 for (BasicBlock *Succ : successors(BB)) {
294 Succ->removePredecessor(BB);
295 if (SeenSuccs.insert(Succ).second)
296 Updates.push_back({DominatorTree::Delete, BB, Succ});
297 }
298 TI->eraseFromParent();
299 new UnreachableInst(BB->getContext(), BB);
300 DTU.applyUpdatesPermissive(Updates);
301 } else if (FeasibleSuccessors.size() == 1) {
302 // Replace with an unconditional branch to the only feasible successor.
303 BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
305 bool HaveSeenOnlyFeasibleSuccessor = false;
306 for (BasicBlock *Succ : successors(BB)) {
307 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
308 // Don't remove the edge to the only feasible successor the first time
309 // we see it. We still do need to remove any multi-edges to it though.
310 HaveSeenOnlyFeasibleSuccessor = true;
311 continue;
312 }
313
314 Succ->removePredecessor(BB);
315 Updates.push_back({DominatorTree::Delete, BB, Succ});
316 }
317
318 BranchInst::Create(OnlyFeasibleSuccessor, BB);
319 TI->eraseFromParent();
320 DTU.applyUpdatesPermissive(Updates);
321 } else if (FeasibleSuccessors.size() > 1) {
322 SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
324
325 // If the default destination is unfeasible it will never be taken. Replace
326 // it with a new block with a single Unreachable instruction.
327 BasicBlock *DefaultDest = SI->getDefaultDest();
328 if (!FeasibleSuccessors.contains(DefaultDest)) {
329 if (!NewUnreachableBB) {
330 NewUnreachableBB =
331 BasicBlock::Create(DefaultDest->getContext(), "default.unreachable",
332 DefaultDest->getParent(), DefaultDest);
333 new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);
334 }
335
336 DefaultDest->removePredecessor(BB);
337 SI->setDefaultDest(NewUnreachableBB);
338 Updates.push_back({DominatorTree::Delete, BB, DefaultDest});
339 Updates.push_back({DominatorTree::Insert, BB, NewUnreachableBB});
340 }
341
342 for (auto CI = SI->case_begin(); CI != SI->case_end();) {
343 if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
344 ++CI;
345 continue;
346 }
347
348 BasicBlock *Succ = CI->getCaseSuccessor();
349 Succ->removePredecessor(BB);
350 Updates.push_back({DominatorTree::Delete, BB, Succ});
351 SI.removeCase(CI);
352 // Don't increment CI, as we removed a case.
353 }
354
355 DTU.applyUpdatesPermissive(Updates);
356 } else {
357 llvm_unreachable("Must have at least one feasible successor");
358 }
359 return true;
360}
361
362/// Helper class for SCCPSolver. This implements the instruction visitor and
363/// holds all the state.
364class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> {
365 const DataLayout &DL;
366 std::function<const TargetLibraryInfo &(Function &)> GetTLI;
367 SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
369 ValueState; // The state each value is in.
370
371 /// StructValueState - This maintains ValueState for values that have
372 /// StructType, for example for formal arguments, calls, insertelement, etc.
374
375 /// GlobalValue - If we are tracking any values for the contents of a global
376 /// variable, we keep a mapping from the constant accessor to the element of
377 /// the global, to the currently known value. If the value becomes
378 /// overdefined, it's entry is simply removed from this map.
380
381 /// TrackedRetVals - If we are tracking arguments into and the return
382 /// value out of a function, it will have an entry in this map, indicating
383 /// what the known return value for the function is.
385
386 /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
387 /// that return multiple values.
389 TrackedMultipleRetVals;
390
391 /// The set of values whose lattice has been invalidated.
392 /// Populated by resetLatticeValueFor(), cleared after resolving undefs.
393 DenseSet<Value *> Invalidated;
394
395 /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
396 /// represented here for efficient lookup.
397 SmallPtrSet<Function *, 16> MRVFunctionsTracked;
398
399 /// A list of functions whose return cannot be modified.
400 SmallPtrSet<Function *, 16> MustPreserveReturnsInFunctions;
401
402 /// TrackingIncomingArguments - This is the set of functions for whose
403 /// arguments we make optimistic assumptions about and try to prove as
404 /// constants.
405 SmallPtrSet<Function *, 16> TrackingIncomingArguments;
406
407 /// The reason for two worklists is that overdefined is the lowest state
408 /// on the lattice, and moving things to overdefined as fast as possible
409 /// makes SCCP converge much faster.
410 ///
411 /// By having a separate worklist, we accomplish this because everything
412 /// possibly overdefined will become overdefined at the soonest possible
413 /// point.
414 SmallVector<Value *, 64> OverdefinedInstWorkList;
415 SmallVector<Value *, 64> InstWorkList;
416
417 // The BasicBlock work list
419
420 /// KnownFeasibleEdges - Entries in this set are edges which have already had
421 /// PHI nodes retriggered.
422 using Edge = std::pair<BasicBlock *, BasicBlock *>;
423 DenseSet<Edge> KnownFeasibleEdges;
424
426
428
429 LLVMContext &Ctx;
430
431private:
432 ConstantInt *getConstantInt(const ValueLatticeElement &IV, Type *Ty) const {
433 return dyn_cast_or_null<ConstantInt>(getConstant(IV, Ty));
434 }
435
436 // pushToWorkList - Helper for markConstant/markOverdefined
437 void pushToWorkList(ValueLatticeElement &IV, Value *V);
438
439 // Helper to push \p V to the worklist, after updating it to \p IV. Also
440 // prints a debug message with the updated value.
441 void pushToWorkListMsg(ValueLatticeElement &IV, Value *V);
442
443 // markConstant - Make a value be marked as "constant". If the value
444 // is not already a constant, add it to the instruction work list so that
445 // the users of the instruction are updated later.
446 bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C,
447 bool MayIncludeUndef = false);
448
449 bool markConstant(Value *V, Constant *C) {
450 assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
451 return markConstant(ValueState[V], V, C);
452 }
453
454 /// markConstantRange - Mark the object as constant range with \p CR. If the
455 /// object is not a constant range with the range \p CR, add it to the
456 /// instruction work list so that the users of the instruction are updated
457 /// later.
458 bool markConstantRange(ValueLatticeElement &IV, Value *V,
459 const ConstantRange &CR);
460
461 // markOverdefined - Make a value be marked as "overdefined". If the
462 // value is not already overdefined, add it to the overdefined instruction
463 // work list so that the users of the instruction are updated later.
464 bool markOverdefined(ValueLatticeElement &IV, Value *V);
465
466 /// Merge \p MergeWithV into \p IV and push \p V to the worklist, if \p IV
467 /// changes.
468 bool mergeInValue(ValueLatticeElement &IV, Value *V,
469 ValueLatticeElement MergeWithV,
471 /*MayIncludeUndef=*/false, /*CheckWiden=*/false});
472
473 bool mergeInValue(Value *V, ValueLatticeElement MergeWithV,
475 /*MayIncludeUndef=*/false, /*CheckWiden=*/false}) {
476 assert(!V->getType()->isStructTy() &&
477 "non-structs should use markConstant");
478 return mergeInValue(ValueState[V], V, MergeWithV, Opts);
479 }
480
481 /// getValueState - Return the ValueLatticeElement object that corresponds to
482 /// the value. This function handles the case when the value hasn't been seen
483 /// yet by properly seeding constants etc.
484 ValueLatticeElement &getValueState(Value *V) {
485 assert(!V->getType()->isStructTy() && "Should use getStructValueState");
486
487 auto I = ValueState.insert(std::make_pair(V, ValueLatticeElement()));
488 ValueLatticeElement &LV = I.first->second;
489
490 if (!I.second)
491 return LV; // Common case, already in the map.
492
493 if (auto *C = dyn_cast<Constant>(V))
494 LV.markConstant(C); // Constants are constant
495
496 // All others are unknown by default.
497 return LV;
498 }
499
500 /// getStructValueState - Return the ValueLatticeElement object that
501 /// corresponds to the value/field pair. This function handles the case when
502 /// the value hasn't been seen yet by properly seeding constants etc.
503 ValueLatticeElement &getStructValueState(Value *V, unsigned i) {
504 assert(V->getType()->isStructTy() && "Should use getValueState");
505 assert(i < cast<StructType>(V->getType())->getNumElements() &&
506 "Invalid element #");
507
508 auto I = StructValueState.insert(
509 std::make_pair(std::make_pair(V, i), ValueLatticeElement()));
510 ValueLatticeElement &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
521 LV.markConstant(Elt); // Constants are constant.
522 }
523
524 // All others are underdefined by default.
525 return LV;
526 }
527
528 /// Traverse the use-def chain of \p Call, marking itself and its users as
529 /// "unknown" on the way.
530 void invalidate(CallBase *Call) {
532 ToInvalidate.push_back(Call);
533
534 while (!ToInvalidate.empty()) {
535 Instruction *Inst = ToInvalidate.pop_back_val();
536
537 if (!Invalidated.insert(Inst).second)
538 continue;
539
540 if (!BBExecutable.count(Inst->getParent()))
541 continue;
542
543 Value *V = nullptr;
544 // For return instructions we need to invalidate the tracked returns map.
545 // Anything else has its lattice in the value map.
546 if (auto *RetInst = dyn_cast<ReturnInst>(Inst)) {
547 Function *F = RetInst->getParent()->getParent();
548 if (auto It = TrackedRetVals.find(F); It != TrackedRetVals.end()) {
549 It->second = ValueLatticeElement();
550 V = F;
551 } else if (MRVFunctionsTracked.count(F)) {
552 auto *STy = cast<StructType>(F->getReturnType());
553 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I)
554 TrackedMultipleRetVals[{F, I}] = ValueLatticeElement();
555 V = F;
556 }
557 } else if (auto *STy = dyn_cast<StructType>(Inst->getType())) {
558 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
559 if (auto It = StructValueState.find({Inst, I});
560 It != StructValueState.end()) {
561 It->second = ValueLatticeElement();
562 V = Inst;
563 }
564 }
565 } else if (auto It = ValueState.find(Inst); It != ValueState.end()) {
566 It->second = ValueLatticeElement();
567 V = Inst;
568 }
569
570 if (V) {
571 LLVM_DEBUG(dbgs() << "Invalidated lattice for " << *V << "\n");
572
573 for (User *U : V->users())
574 if (auto *UI = dyn_cast<Instruction>(U))
575 ToInvalidate.push_back(UI);
576
577 auto It = AdditionalUsers.find(V);
578 if (It != AdditionalUsers.end())
579 for (User *U : It->second)
580 if (auto *UI = dyn_cast<Instruction>(U))
581 ToInvalidate.push_back(UI);
582 }
583 }
584 }
585
586 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
587 /// work list if it is not already executable.
588 bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
589
590 // getFeasibleSuccessors - Return a vector of booleans to indicate which
591 // successors are reachable from a given terminator instruction.
592 void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs);
593
594 // OperandChangedState - This method is invoked on all of the users of an
595 // instruction that was just changed state somehow. Based on this
596 // information, we need to update the specified user of this instruction.
597 void operandChangedState(Instruction *I) {
598 if (BBExecutable.count(I->getParent())) // Inst is executable?
599 visit(*I);
600 }
601
602 // Add U as additional user of V.
603 void addAdditionalUser(Value *V, User *U) {
604 auto Iter = AdditionalUsers.insert({V, {}});
605 Iter.first->second.insert(U);
606 }
607
608 // Mark I's users as changed, including AdditionalUsers.
609 void markUsersAsChanged(Value *I) {
610 // Functions include their arguments in the use-list. Changed function
611 // values mean that the result of the function changed. We only need to
612 // update the call sites with the new function result and do not have to
613 // propagate the call arguments.
614 if (isa<Function>(I)) {
615 for (User *U : I->users()) {
616 if (auto *CB = dyn_cast<CallBase>(U))
617 handleCallResult(*CB);
618 }
619 } else {
620 for (User *U : I->users())
621 if (auto *UI = dyn_cast<Instruction>(U))
622 operandChangedState(UI);
623 }
624
625 auto Iter = AdditionalUsers.find(I);
626 if (Iter != AdditionalUsers.end()) {
627 // Copy additional users before notifying them of changes, because new
628 // users may be added, potentially invalidating the iterator.
630 for (User *U : Iter->second)
631 if (auto *UI = dyn_cast<Instruction>(U))
632 ToNotify.push_back(UI);
633 for (Instruction *UI : ToNotify)
634 operandChangedState(UI);
635 }
636 }
637 void handleCallOverdefined(CallBase &CB);
638 void handleCallResult(CallBase &CB);
639 void handleCallArguments(CallBase &CB);
640 void handleExtractOfWithOverflow(ExtractValueInst &EVI,
641 const WithOverflowInst *WO, unsigned Idx);
642
643private:
644 friend class InstVisitor<SCCPInstVisitor>;
645
646 // visit implementations - Something changed in this instruction. Either an
647 // operand made a transition, or the instruction is newly executable. Change
648 // the value type of I to reflect these changes if appropriate.
649 void visitPHINode(PHINode &I);
650
651 // Terminators
652
653 void visitReturnInst(ReturnInst &I);
654 void visitTerminator(Instruction &TI);
655
656 void visitCastInst(CastInst &I);
657 void visitSelectInst(SelectInst &I);
658 void visitUnaryOperator(Instruction &I);
659 void visitFreezeInst(FreezeInst &I);
660 void visitBinaryOperator(Instruction &I);
661 void visitCmpInst(CmpInst &I);
662 void visitExtractValueInst(ExtractValueInst &EVI);
663 void visitInsertValueInst(InsertValueInst &IVI);
664
665 void visitCatchSwitchInst(CatchSwitchInst &CPI) {
666 markOverdefined(&CPI);
667 visitTerminator(CPI);
668 }
669
670 // Instructions that cannot be folded away.
671
672 void visitStoreInst(StoreInst &I);
673 void visitLoadInst(LoadInst &I);
674 void visitGetElementPtrInst(GetElementPtrInst &I);
675
676 void visitInvokeInst(InvokeInst &II) {
677 visitCallBase(II);
678 visitTerminator(II);
679 }
680
681 void visitCallBrInst(CallBrInst &CBI) {
682 visitCallBase(CBI);
683 visitTerminator(CBI);
684 }
685
686 void visitCallBase(CallBase &CB);
687 void visitResumeInst(ResumeInst &I) { /*returns void*/
688 }
689 void visitUnreachableInst(UnreachableInst &I) { /*returns void*/
690 }
691 void visitFenceInst(FenceInst &I) { /*returns void*/
692 }
693
694 void visitInstruction(Instruction &I);
695
696public:
698 FnPredicateInfo.insert({&F, std::make_unique<PredicateInfo>(F, DT, AC)});
699 }
700
701 void visitCallInst(CallInst &I) { visitCallBase(I); }
702
704
706 auto It = FnPredicateInfo.find(I->getParent()->getParent());
707 if (It == FnPredicateInfo.end())
708 return nullptr;
709 return It->second->getPredicateInfoFor(I);
710 }
711
713 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
714 LLVMContext &Ctx)
715 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
716
718 // We only track the contents of scalar globals.
719 if (GV->getValueType()->isSingleValueType()) {
720 ValueLatticeElement &IV = TrackedGlobals[GV];
721 IV.markConstant(GV->getInitializer());
722 }
723 }
724
726 // Add an entry, F -> undef.
727 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
728 MRVFunctionsTracked.insert(F);
729 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
730 TrackedMultipleRetVals.insert(
731 std::make_pair(std::make_pair(F, i), ValueLatticeElement()));
732 } else if (!F->getReturnType()->isVoidTy())
733 TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement()));
734 }
735
737 MustPreserveReturnsInFunctions.insert(F);
738 }
739
741 return MustPreserveReturnsInFunctions.count(F);
742 }
743
745 TrackingIncomingArguments.insert(F);
746 }
747
749 return TrackingIncomingArguments.count(F);
750 }
751
752 void solve();
753
755
757
759 return BBExecutable.count(BB);
760 }
761
762 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
763
764 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
765 std::vector<ValueLatticeElement> StructValues;
766 auto *STy = dyn_cast<StructType>(V->getType());
767 assert(STy && "getStructLatticeValueFor() can be called only on structs");
768 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
769 auto I = StructValueState.find(std::make_pair(V, i));
770 assert(I != StructValueState.end() && "Value not in valuemap!");
771 StructValues.push_back(I->second);
772 }
773 return StructValues;
774 }
775
776 void removeLatticeValueFor(Value *V) { ValueState.erase(V); }
777
778 /// Invalidate the Lattice Value of \p Call and its users after specializing
779 /// the call. Then recompute it.
781 // Calls to void returning functions do not need invalidation.
782 Function *F = Call->getCalledFunction();
783 (void)F;
784 assert(!F->getReturnType()->isVoidTy() &&
785 (TrackedRetVals.count(F) || MRVFunctionsTracked.count(F)) &&
786 "All non void specializations should be tracked");
787 invalidate(Call);
788 handleCallResult(*Call);
789 }
790
792 assert(!V->getType()->isStructTy() &&
793 "Should use getStructLatticeValueFor");
795 ValueState.find(V);
796 assert(I != ValueState.end() &&
797 "V not found in ValueState nor Paramstate map!");
798 return I->second;
799 }
800
802 return TrackedRetVals;
803 }
804
806 return TrackedGlobals;
807 }
808
810 return MRVFunctionsTracked;
811 }
812
814 if (auto *STy = dyn_cast<StructType>(V->getType()))
815 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
816 markOverdefined(getStructValueState(V, i), V);
817 else
818 markOverdefined(ValueState[V], V);
819 }
820
822 if (A->getType()->isIntegerTy()) {
823 if (std::optional<ConstantRange> Range = A->getRange()) {
824 markConstantRange(ValueState[A], A, *Range);
825 return;
826 }
827 }
828 // Assume nothing about the incoming arguments without range.
829 markOverdefined(A);
830 }
831
833
834 Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const;
835
837
839 return TrackingIncomingArguments;
840 }
841
843 const SmallVectorImpl<ArgInfo> &Args);
844
846 for (auto &BB : *F)
847 BBExecutable.erase(&BB);
848 }
849
851 bool ResolvedUndefs = true;
852 while (ResolvedUndefs) {
853 solve();
854 ResolvedUndefs = false;
855 for (Function &F : M)
856 ResolvedUndefs |= resolvedUndefsIn(F);
857 }
858 }
859
861 bool ResolvedUndefs = true;
862 while (ResolvedUndefs) {
863 solve();
864 ResolvedUndefs = false;
865 for (Function *F : WorkList)
866 ResolvedUndefs |= resolvedUndefsIn(*F);
867 }
868 }
869
871 bool ResolvedUndefs = true;
872 while (ResolvedUndefs) {
873 solve();
874 ResolvedUndefs = false;
875 for (Value *V : Invalidated)
876 if (auto *I = dyn_cast<Instruction>(V))
877 ResolvedUndefs |= resolvedUndef(*I);
878 }
879 Invalidated.clear();
880 }
881};
882
883} // namespace llvm
884
886 if (!BBExecutable.insert(BB).second)
887 return false;
888 LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
889 BBWorkList.push_back(BB); // Add the block to the work list!
890 return true;
891}
892
893void SCCPInstVisitor::pushToWorkList(ValueLatticeElement &IV, Value *V) {
894 if (IV.isOverdefined()) {
895 if (OverdefinedInstWorkList.empty() || OverdefinedInstWorkList.back() != V)
896 OverdefinedInstWorkList.push_back(V);
897 return;
898 }
899 if (InstWorkList.empty() || InstWorkList.back() != V)
900 InstWorkList.push_back(V);
901}
902
903void SCCPInstVisitor::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) {
904 LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
905 pushToWorkList(IV, V);
906}
907
908bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
909 Constant *C, bool MayIncludeUndef) {
910 if (!IV.markConstant(C, MayIncludeUndef))
911 return false;
912 LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
913 pushToWorkList(IV, V);
914 return true;
915}
916
917bool SCCPInstVisitor::markConstantRange(ValueLatticeElement &IV, Value *V,
918 const ConstantRange &CR) {
919 if (!IV.markConstantRange(CR))
920 return false;
921 LLVM_DEBUG(dbgs() << "markConstantRange: " << CR << ": " << *V << '\n');
922 pushToWorkList(IV, V);
923 return true;
924}
925
926bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) {
927 if (!IV.markOverdefined())
928 return false;
929
930 LLVM_DEBUG(dbgs() << "markOverdefined: ";
931 if (auto *F = dyn_cast<Function>(V)) dbgs()
932 << "Function '" << F->getName() << "'\n";
933 else dbgs() << *V << '\n');
934 // Only instructions go on the work list
935 pushToWorkList(IV, V);
936 return true;
937}
938
940 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
941 const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
942 assert(It != TrackedMultipleRetVals.end());
943 ValueLatticeElement LV = It->second;
944 if (!SCCPSolver::isConstant(LV))
945 return false;
946 }
947 return true;
948}
949
951 Type *Ty) const {
952 if (LV.isConstant()) {
953 Constant *C = LV.getConstant();
954 assert(C->getType() == Ty && "Type mismatch");
955 return C;
956 }
957
958 if (LV.isConstantRange()) {
959 const auto &CR = LV.getConstantRange();
960 if (CR.getSingleElement())
961 return ConstantInt::get(Ty, *CR.getSingleElement());
962 }
963 return nullptr;
964}
965
967 Constant *Const = nullptr;
968 if (V->getType()->isStructTy()) {
969 std::vector<ValueLatticeElement> LVs = getStructLatticeValueFor(V);
971 return nullptr;
972 std::vector<Constant *> ConstVals;
973 auto *ST = cast<StructType>(V->getType());
974 for (unsigned I = 0, E = ST->getNumElements(); I != E; ++I) {
975 ValueLatticeElement LV = LVs[I];
976 ConstVals.push_back(SCCPSolver::isConstant(LV)
977 ? getConstant(LV, ST->getElementType(I))
978 : UndefValue::get(ST->getElementType(I)));
979 }
980 Const = ConstantStruct::get(ST, ConstVals);
981 } else {
984 return nullptr;
985 Const = SCCPSolver::isConstant(LV) ? getConstant(LV, V->getType())
986 : UndefValue::get(V->getType());
987 }
988 assert(Const && "Constant is nullptr here!");
989 return Const;
990}
991
993 const SmallVectorImpl<ArgInfo> &Args) {
994 assert(!Args.empty() && "Specialization without arguments");
995 assert(F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
996 "Functions should have the same number of arguments");
997
998 auto Iter = Args.begin();
999 Function::arg_iterator NewArg = F->arg_begin();
1000 Function::arg_iterator OldArg = Args[0].Formal->getParent()->arg_begin();
1001 for (auto End = F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {
1002
1003 LLVM_DEBUG(dbgs() << "SCCP: Marking argument "
1004 << NewArg->getNameOrAsOperand() << "\n");
1005
1006 // Mark the argument constants in the new function
1007 // or copy the lattice state over from the old function.
1008 if (Iter != Args.end() && Iter->Formal == &*OldArg) {
1009 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) {
1010 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1011 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1012 NewValue.markConstant(Iter->Actual->getAggregateElement(I));
1013 }
1014 } else {
1015 ValueState[&*NewArg].markConstant(Iter->Actual);
1016 }
1017 ++Iter;
1018 } else {
1019 if (auto *STy = dyn_cast<StructType>(NewArg->getType())) {
1020 for (unsigned I = 0, E = STy->getNumElements(); I != E; ++I) {
1021 ValueLatticeElement &NewValue = StructValueState[{&*NewArg, I}];
1022 NewValue = StructValueState[{&*OldArg, I}];
1023 }
1024 } else {
1025 ValueLatticeElement &NewValue = ValueState[&*NewArg];
1026 NewValue = ValueState[&*OldArg];
1027 }
1028 }
1029 }
1030}
1031
1032void SCCPInstVisitor::visitInstruction(Instruction &I) {
1033 // All the instructions we don't do any special handling for just
1034 // go to overdefined.
1035 LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n');
1036 markOverdefined(&I);
1037}
1038
1039bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
1040 ValueLatticeElement MergeWithV,
1042 if (IV.mergeIn(MergeWithV, Opts)) {
1043 pushToWorkList(IV, V);
1044 LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
1045 << IV << "\n");
1046 return true;
1047 }
1048 return false;
1049}
1050
1051bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
1052 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
1053 return false; // This edge is already known to be executable!
1054
1055 if (!markBlockExecutable(Dest)) {
1056 // If the destination is already executable, we just made an *edge*
1057 // feasible that wasn't before. Revisit the PHI nodes in the block
1058 // because they have potentially new operands.
1059 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
1060 << " -> " << Dest->getName() << '\n');
1061
1062 for (PHINode &PN : Dest->phis())
1063 visitPHINode(PN);
1064 }
1065 return true;
1066}
1067
1068// getFeasibleSuccessors - Return a vector of booleans to indicate which
1069// successors are reachable from a given terminator instruction.
1070void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
1071 SmallVectorImpl<bool> &Succs) {
1072 Succs.resize(TI.getNumSuccessors());
1073 if (auto *BI = dyn_cast<BranchInst>(&TI)) {
1074 if (BI->isUnconditional()) {
1075 Succs[0] = true;
1076 return;
1077 }
1078
1079 ValueLatticeElement BCValue = getValueState(BI->getCondition());
1080 ConstantInt *CI = getConstantInt(BCValue, BI->getCondition()->getType());
1081 if (!CI) {
1082 // Overdefined condition variables, and branches on unfoldable constant
1083 // conditions, mean the branch could go either way.
1084 if (!BCValue.isUnknownOrUndef())
1085 Succs[0] = Succs[1] = true;
1086 return;
1087 }
1088
1089 // Constant condition variables mean the branch can only go a single way.
1090 Succs[CI->isZero()] = true;
1091 return;
1092 }
1093
1094 // We cannot analyze special terminators, so consider all successors
1095 // executable.
1096 if (TI.isSpecialTerminator()) {
1097 Succs.assign(TI.getNumSuccessors(), true);
1098 return;
1099 }
1100
1101 if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
1102 if (!SI->getNumCases()) {
1103 Succs[0] = true;
1104 return;
1105 }
1106 const ValueLatticeElement &SCValue = getValueState(SI->getCondition());
1107 if (ConstantInt *CI =
1108 getConstantInt(SCValue, SI->getCondition()->getType())) {
1109 Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
1110 return;
1111 }
1112
1113 // TODO: Switch on undef is UB. Stop passing false once the rest of LLVM
1114 // is ready.
1115 if (SCValue.isConstantRange(/*UndefAllowed=*/false)) {
1116 const ConstantRange &Range = SCValue.getConstantRange();
1117 unsigned ReachableCaseCount = 0;
1118 for (const auto &Case : SI->cases()) {
1119 const APInt &CaseValue = Case.getCaseValue()->getValue();
1120 if (Range.contains(CaseValue)) {
1121 Succs[Case.getSuccessorIndex()] = true;
1122 ++ReachableCaseCount;
1123 }
1124 }
1125
1126 Succs[SI->case_default()->getSuccessorIndex()] =
1127 Range.isSizeLargerThan(ReachableCaseCount);
1128 return;
1129 }
1130
1131 // Overdefined or unknown condition? All destinations are executable!
1132 if (!SCValue.isUnknownOrUndef())
1133 Succs.assign(TI.getNumSuccessors(), true);
1134 return;
1135 }
1136
1137 // In case of indirect branch and its address is a blockaddress, we mark
1138 // the target as executable.
1139 if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
1140 // Casts are folded by visitCastInst.
1141 ValueLatticeElement IBRValue = getValueState(IBR->getAddress());
1142 BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(
1143 getConstant(IBRValue, IBR->getAddress()->getType()));
1144 if (!Addr) { // Overdefined or unknown condition?
1145 // All destinations are executable!
1146 if (!IBRValue.isUnknownOrUndef())
1147 Succs.assign(TI.getNumSuccessors(), true);
1148 return;
1149 }
1150
1151 BasicBlock *T = Addr->getBasicBlock();
1152 assert(Addr->getFunction() == T->getParent() &&
1153 "Block address of a different function ?");
1154 for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
1155 // This is the target.
1156 if (IBR->getDestination(i) == T) {
1157 Succs[i] = true;
1158 return;
1159 }
1160 }
1161
1162 // If we didn't find our destination in the IBR successor list, then we
1163 // have undefined behavior. Its ok to assume no successor is executable.
1164 return;
1165 }
1166
1167 LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
1168 llvm_unreachable("SCCP: Don't know how to handle this terminator!");
1169}
1170
1171// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
1172// block to the 'To' basic block is currently feasible.
1174 // Check if we've called markEdgeExecutable on the edge yet. (We could
1175 // be more aggressive and try to consider edges which haven't been marked
1176 // yet, but there isn't any need.)
1177 return KnownFeasibleEdges.count(Edge(From, To));
1178}
1179
1180// visit Implementations - Something changed in this instruction, either an
1181// operand made a transition, or the instruction is newly executable. Change
1182// the value type of I to reflect these changes if appropriate. This method
1183// makes sure to do the following actions:
1184//
1185// 1. If a phi node merges two constants in, and has conflicting value coming
1186// from different branches, or if the PHI node merges in an overdefined
1187// value, then the PHI node becomes overdefined.
1188// 2. If a phi node merges only constants in, and they all agree on value, the
1189// PHI node becomes a constant value equal to that.
1190// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
1191// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
1192// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
1193// 6. If a conditional branch has a value that is constant, make the selected
1194// destination executable
1195// 7. If a conditional branch has a value that is overdefined, make all
1196// successors executable.
1197void SCCPInstVisitor::visitPHINode(PHINode &PN) {
1198 // If this PN returns a struct, just mark the result overdefined.
1199 // TODO: We could do a lot better than this if code actually uses this.
1200 if (PN.getType()->isStructTy())
1201 return (void)markOverdefined(&PN);
1202
1203 if (getValueState(&PN).isOverdefined())
1204 return; // Quick exit
1205
1206 // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
1207 // and slow us down a lot. Just mark them overdefined.
1208 if (PN.getNumIncomingValues() > 64)
1209 return (void)markOverdefined(&PN);
1210
1211 unsigned NumActiveIncoming = 0;
1212
1213 // Look at all of the executable operands of the PHI node. If any of them
1214 // are overdefined, the PHI becomes overdefined as well. If they are all
1215 // constant, and they agree with each other, the PHI becomes the identical
1216 // constant. If they are constant and don't agree, the PHI is a constant
1217 // range. If there are no executable operands, the PHI remains unknown.
1218 ValueLatticeElement PhiState = getValueState(&PN);
1219 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1220 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
1221 continue;
1222
1223 ValueLatticeElement IV = getValueState(PN.getIncomingValue(i));
1224 PhiState.mergeIn(IV);
1225 NumActiveIncoming++;
1226 if (PhiState.isOverdefined())
1227 break;
1228 }
1229
1230 // We allow up to 1 range extension per active incoming value and one
1231 // additional extension. Note that we manually adjust the number of range
1232 // extensions to match the number of active incoming values. This helps to
1233 // limit multiple extensions caused by the same incoming value, if other
1234 // incoming values are equal.
1235 mergeInValue(&PN, PhiState,
1236 ValueLatticeElement::MergeOptions().setMaxWidenSteps(
1237 NumActiveIncoming + 1));
1238 ValueLatticeElement &PhiStateRef = getValueState(&PN);
1239 PhiStateRef.setNumRangeExtensions(
1240 std::max(NumActiveIncoming, PhiStateRef.getNumRangeExtensions()));
1241}
1242
1243void SCCPInstVisitor::visitReturnInst(ReturnInst &I) {
1244 if (I.getNumOperands() == 0)
1245 return; // ret void
1246
1247 Function *F = I.getParent()->getParent();
1248 Value *ResultOp = I.getOperand(0);
1249
1250 // If we are tracking the return value of this function, merge it in.
1251 if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
1252 auto TFRVI = TrackedRetVals.find(F);
1253 if (TFRVI != TrackedRetVals.end()) {
1254 mergeInValue(TFRVI->second, F, getValueState(ResultOp));
1255 return;
1256 }
1257 }
1258
1259 // Handle functions that return multiple values.
1260 if (!TrackedMultipleRetVals.empty()) {
1261 if (auto *STy = dyn_cast<StructType>(ResultOp->getType()))
1262 if (MRVFunctionsTracked.count(F))
1263 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1264 mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F,
1265 getStructValueState(ResultOp, i));
1266 }
1267}
1268
1269void SCCPInstVisitor::visitTerminator(Instruction &TI) {
1270 SmallVector<bool, 16> SuccFeasible;
1271 getFeasibleSuccessors(TI, SuccFeasible);
1272
1273 BasicBlock *BB = TI.getParent();
1274
1275 // Mark all feasible successors executable.
1276 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
1277 if (SuccFeasible[i])
1278 markEdgeExecutable(BB, TI.getSuccessor(i));
1279}
1280
1281void SCCPInstVisitor::visitCastInst(CastInst &I) {
1282 // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1283 // discover a concrete value later.
1284 if (ValueState[&I].isOverdefined())
1285 return;
1286
1287 ValueLatticeElement OpSt = getValueState(I.getOperand(0));
1288 if (OpSt.isUnknownOrUndef())
1289 return;
1290
1291 if (Constant *OpC = getConstant(OpSt, I.getOperand(0)->getType())) {
1292 // Fold the constant as we build.
1293 if (Constant *C =
1294 ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL))
1295 return (void)markConstant(&I, C);
1296 }
1297
1298 if (I.getDestTy()->isIntegerTy() && I.getSrcTy()->isIntOrIntVectorTy()) {
1299 auto &LV = getValueState(&I);
1300 ConstantRange OpRange =
1301 getConstantRange(OpSt, I.getSrcTy(), /*UndefAllowed=*/false);
1302
1303 Type *DestTy = I.getDestTy();
1304 // Vectors where all elements have the same known constant range are treated
1305 // as a single constant range in the lattice. When bitcasting such vectors,
1306 // there is a mis-match between the width of the lattice value (single
1307 // constant range) and the original operands (vector). Go to overdefined in
1308 // that case.
1309 if (I.getOpcode() == Instruction::BitCast &&
1310 I.getOperand(0)->getType()->isVectorTy() &&
1311 OpRange.getBitWidth() < DL.getTypeSizeInBits(DestTy))
1312 return (void)markOverdefined(&I);
1313
1314 ConstantRange Res =
1315 OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
1316 mergeInValue(LV, &I, ValueLatticeElement::getRange(Res));
1317 } else
1318 markOverdefined(&I);
1319}
1320
1321void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,
1322 const WithOverflowInst *WO,
1323 unsigned Idx) {
1324 Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
1325 ValueLatticeElement L = getValueState(LHS);
1326 ValueLatticeElement R = getValueState(RHS);
1327 addAdditionalUser(LHS, &EVI);
1328 addAdditionalUser(RHS, &EVI);
1329 if (L.isUnknownOrUndef() || R.isUnknownOrUndef())
1330 return; // Wait to resolve.
1331
1332 Type *Ty = LHS->getType();
1333 ConstantRange LR = getConstantRange(L, Ty, /*UndefAllowed=*/false);
1334 ConstantRange RR = getConstantRange(R, Ty, /*UndefAllowed=*/false);
1335 if (Idx == 0) {
1336 ConstantRange Res = LR.binaryOp(WO->getBinaryOp(), RR);
1337 mergeInValue(&EVI, ValueLatticeElement::getRange(Res));
1338 } else {
1339 assert(Idx == 1 && "Index can only be 0 or 1");
1341 WO->getBinaryOp(), RR, WO->getNoWrapKind());
1342 if (NWRegion.contains(LR))
1343 return (void)markConstant(&EVI, ConstantInt::getFalse(EVI.getType()));
1344 markOverdefined(&EVI);
1345 }
1346}
1347
1348void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) {
1349 // If this returns a struct, mark all elements over defined, we don't track
1350 // structs in structs.
1351 if (EVI.getType()->isStructTy())
1352 return (void)markOverdefined(&EVI);
1353
1354 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1355 // discover a concrete value later.
1356 if (ValueState[&EVI].isOverdefined())
1357 return (void)markOverdefined(&EVI);
1358
1359 // If this is extracting from more than one level of struct, we don't know.
1360 if (EVI.getNumIndices() != 1)
1361 return (void)markOverdefined(&EVI);
1362
1363 Value *AggVal = EVI.getAggregateOperand();
1364 if (AggVal->getType()->isStructTy()) {
1365 unsigned i = *EVI.idx_begin();
1366 if (auto *WO = dyn_cast<WithOverflowInst>(AggVal))
1367 return handleExtractOfWithOverflow(EVI, WO, i);
1368 ValueLatticeElement EltVal = getStructValueState(AggVal, i);
1369 mergeInValue(getValueState(&EVI), &EVI, EltVal);
1370 } else {
1371 // Otherwise, must be extracting from an array.
1372 return (void)markOverdefined(&EVI);
1373 }
1374}
1375
1376void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) {
1377 auto *STy = dyn_cast<StructType>(IVI.getType());
1378 if (!STy)
1379 return (void)markOverdefined(&IVI);
1380
1381 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1382 // discover a concrete value later.
1383 if (SCCPSolver::isOverdefined(ValueState[&IVI]))
1384 return (void)markOverdefined(&IVI);
1385
1386 // If this has more than one index, we can't handle it, drive all results to
1387 // undef.
1388 if (IVI.getNumIndices() != 1)
1389 return (void)markOverdefined(&IVI);
1390
1391 Value *Aggr = IVI.getAggregateOperand();
1392 unsigned Idx = *IVI.idx_begin();
1393
1394 // Compute the result based on what we're inserting.
1395 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1396 // This passes through all values that aren't the inserted element.
1397 if (i != Idx) {
1398 ValueLatticeElement EltVal = getStructValueState(Aggr, i);
1399 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
1400 continue;
1401 }
1402
1403 Value *Val = IVI.getInsertedValueOperand();
1404 if (Val->getType()->isStructTy())
1405 // We don't track structs in structs.
1406 markOverdefined(getStructValueState(&IVI, i), &IVI);
1407 else {
1408 ValueLatticeElement InVal = getValueState(Val);
1409 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
1410 }
1411 }
1412}
1413
1414void SCCPInstVisitor::visitSelectInst(SelectInst &I) {
1415 // If this select returns a struct, just mark the result overdefined.
1416 // TODO: We could do a lot better than this if code actually uses this.
1417 if (I.getType()->isStructTy())
1418 return (void)markOverdefined(&I);
1419
1420 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1421 // discover a concrete value later.
1422 if (ValueState[&I].isOverdefined())
1423 return (void)markOverdefined(&I);
1424
1425 ValueLatticeElement CondValue = getValueState(I.getCondition());
1426 if (CondValue.isUnknownOrUndef())
1427 return;
1428
1429 if (ConstantInt *CondCB =
1430 getConstantInt(CondValue, I.getCondition()->getType())) {
1431 Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
1432 mergeInValue(&I, getValueState(OpVal));
1433 return;
1434 }
1435
1436 // Otherwise, the condition is overdefined or a constant we can't evaluate.
1437 // See if we can produce something better than overdefined based on the T/F
1438 // value.
1439 ValueLatticeElement TVal = getValueState(I.getTrueValue());
1440 ValueLatticeElement FVal = getValueState(I.getFalseValue());
1441
1442 bool Changed = ValueState[&I].mergeIn(TVal);
1443 Changed |= ValueState[&I].mergeIn(FVal);
1444 if (Changed)
1445 pushToWorkListMsg(ValueState[&I], &I);
1446}
1447
1448// Handle Unary Operators.
1449void SCCPInstVisitor::visitUnaryOperator(Instruction &I) {
1450 ValueLatticeElement V0State = getValueState(I.getOperand(0));
1451
1452 ValueLatticeElement &IV = ValueState[&I];
1453 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1454 // discover a concrete value later.
1456 return (void)markOverdefined(&I);
1457
1458 // If something is unknown/undef, wait for it to resolve.
1459 if (V0State.isUnknownOrUndef())
1460 return;
1461
1462 if (SCCPSolver::isConstant(V0State))
1464 I.getOpcode(), getConstant(V0State, I.getType()), DL))
1465 return (void)markConstant(IV, &I, C);
1466
1467 markOverdefined(&I);
1468}
1469
1470void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) {
1471 // If this freeze returns a struct, just mark the result overdefined.
1472 // TODO: We could do a lot better than this.
1473 if (I.getType()->isStructTy())
1474 return (void)markOverdefined(&I);
1475
1476 ValueLatticeElement V0State = getValueState(I.getOperand(0));
1477 ValueLatticeElement &IV = ValueState[&I];
1478 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1479 // discover a concrete value later.
1481 return (void)markOverdefined(&I);
1482
1483 // If something is unknown/undef, wait for it to resolve.
1484 if (V0State.isUnknownOrUndef())
1485 return;
1486
1487 if (SCCPSolver::isConstant(V0State) &&
1488 isGuaranteedNotToBeUndefOrPoison(getConstant(V0State, I.getType())))
1489 return (void)markConstant(IV, &I, getConstant(V0State, I.getType()));
1490
1491 markOverdefined(&I);
1492}
1493
1494// Handle Binary Operators.
1495void SCCPInstVisitor::visitBinaryOperator(Instruction &I) {
1496 ValueLatticeElement V1State = getValueState(I.getOperand(0));
1497 ValueLatticeElement V2State = getValueState(I.getOperand(1));
1498
1499 ValueLatticeElement &IV = ValueState[&I];
1500 if (IV.isOverdefined())
1501 return;
1502
1503 // If something is undef, wait for it to resolve.
1504 if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
1505 return;
1506
1507 if (V1State.isOverdefined() && V2State.isOverdefined())
1508 return (void)markOverdefined(&I);
1509
1510 // If either of the operands is a constant, try to fold it to a constant.
1511 // TODO: Use information from notconstant better.
1512 if ((V1State.isConstant() || V2State.isConstant())) {
1513 Value *V1 = SCCPSolver::isConstant(V1State)
1514 ? getConstant(V1State, I.getOperand(0)->getType())
1515 : I.getOperand(0);
1516 Value *V2 = SCCPSolver::isConstant(V2State)
1517 ? getConstant(V2State, I.getOperand(1)->getType())
1518 : I.getOperand(1);
1519 Value *R = simplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
1520 auto *C = dyn_cast_or_null<Constant>(R);
1521 if (C) {
1522 // Conservatively assume that the result may be based on operands that may
1523 // be undef. Note that we use mergeInValue to combine the constant with
1524 // the existing lattice value for I, as different constants might be found
1525 // after one of the operands go to overdefined, e.g. due to one operand
1526 // being a special floating value.
1528 NewV.markConstant(C, /*MayIncludeUndef=*/true);
1529 return (void)mergeInValue(&I, NewV);
1530 }
1531 }
1532
1533 // Only use ranges for binary operators on integers.
1534 if (!I.getType()->isIntegerTy())
1535 return markOverdefined(&I);
1536
1537 // Try to simplify to a constant range.
1539 getConstantRange(V1State, I.getType(), /*UndefAllowed=*/false);
1541 getConstantRange(V2State, I.getType(), /*UndefAllowed=*/false);
1542
1543 auto *BO = cast<BinaryOperator>(&I);
1544 ConstantRange R = ConstantRange::getEmpty(I.getType()->getScalarSizeInBits());
1545 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO))
1546 R = A.overflowingBinaryOp(BO->getOpcode(), B, OBO->getNoWrapKind());
1547 else
1548 R = A.binaryOp(BO->getOpcode(), B);
1549 mergeInValue(&I, ValueLatticeElement::getRange(R));
1550
1551 // TODO: Currently we do not exploit special values that produce something
1552 // better than overdefined with an overdefined operand for vector or floating
1553 // point types, like and <4 x i32> overdefined, zeroinitializer.
1554}
1555
1556// Handle ICmpInst instruction.
1557void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
1558 // Do not cache this lookup, getValueState calls later in the function might
1559 // invalidate the reference.
1560 if (SCCPSolver::isOverdefined(ValueState[&I]))
1561 return (void)markOverdefined(&I);
1562
1563 Value *Op1 = I.getOperand(0);
1564 Value *Op2 = I.getOperand(1);
1565
1566 // For parameters, use ParamState which includes constant range info if
1567 // available.
1568 auto V1State = getValueState(Op1);
1569 auto V2State = getValueState(Op2);
1570
1571 Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State, DL);
1572 if (C) {
1574 CV.markConstant(C);
1575 mergeInValue(&I, CV);
1576 return;
1577 }
1578
1579 // If operands are still unknown, wait for it to resolve.
1580 if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
1581 !SCCPSolver::isConstant(ValueState[&I]))
1582 return;
1583
1584 markOverdefined(&I);
1585}
1586
1587// Handle getelementptr instructions. If all operands are constants then we
1588// can turn this into a getelementptr ConstantExpr.
1589void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
1590 if (SCCPSolver::isOverdefined(ValueState[&I]))
1591 return (void)markOverdefined(&I);
1592
1594 Operands.reserve(I.getNumOperands());
1595
1596 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1597 ValueLatticeElement State = getValueState(I.getOperand(i));
1598 if (State.isUnknownOrUndef())
1599 return; // Operands are not resolved yet.
1600
1601 if (SCCPSolver::isOverdefined(State))
1602 return (void)markOverdefined(&I);
1603
1604 if (Constant *C = getConstant(State, I.getOperand(i)->getType())) {
1605 Operands.push_back(C);
1606 continue;
1607 }
1608
1609 return (void)markOverdefined(&I);
1610 }
1611
1613 markConstant(&I, C);
1614}
1615
1616void SCCPInstVisitor::visitStoreInst(StoreInst &SI) {
1617 // If this store is of a struct, ignore it.
1618 if (SI.getOperand(0)->getType()->isStructTy())
1619 return;
1620
1621 if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
1622 return;
1623
1624 GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
1625 auto I = TrackedGlobals.find(GV);
1626 if (I == TrackedGlobals.end())
1627 return;
1628
1629 // Get the value we are storing into the global, then merge it.
1630 mergeInValue(I->second, GV, getValueState(SI.getOperand(0)),
1632 if (I->second.isOverdefined())
1633 TrackedGlobals.erase(I); // No need to keep tracking this!
1634}
1635
1637 if (I->getType()->isIntegerTy()) {
1638 if (MDNode *Ranges = I->getMetadata(LLVMContext::MD_range))
1641
1642 if (const auto *CB = dyn_cast<CallBase>(I))
1643 if (std::optional<ConstantRange> Range = CB->getRange())
1645 }
1646 if (I->hasMetadata(LLVMContext::MD_nonnull))
1648 ConstantPointerNull::get(cast<PointerType>(I->getType())));
1650}
1651
1652// Handle load instructions. If the operand is a constant pointer to a constant
1653// global, we can replace the load with the loaded constant value!
1654void SCCPInstVisitor::visitLoadInst(LoadInst &I) {
1655 // If this load is of a struct or the load is volatile, just mark the result
1656 // as overdefined.
1657 if (I.getType()->isStructTy() || I.isVolatile())
1658 return (void)markOverdefined(&I);
1659
1660 // resolvedUndefsIn might mark I as overdefined. Bail out, even if we would
1661 // discover a concrete value later.
1662 if (ValueState[&I].isOverdefined())
1663 return (void)markOverdefined(&I);
1664
1665 ValueLatticeElement PtrVal = getValueState(I.getOperand(0));
1666 if (PtrVal.isUnknownOrUndef())
1667 return; // The pointer is not resolved yet!
1668
1669 ValueLatticeElement &IV = ValueState[&I];
1670
1671 if (SCCPSolver::isConstant(PtrVal)) {
1672 Constant *Ptr = getConstant(PtrVal, I.getOperand(0)->getType());
1673
1674 // load null is undefined.
1675 if (isa<ConstantPointerNull>(Ptr)) {
1676 if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
1677 return (void)markOverdefined(IV, &I);
1678 else
1679 return;
1680 }
1681
1682 // Transform load (constant global) into the value loaded.
1683 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
1684 if (!TrackedGlobals.empty()) {
1685 // If we are tracking this global, merge in the known value for it.
1686 auto It = TrackedGlobals.find(GV);
1687 if (It != TrackedGlobals.end()) {
1688 mergeInValue(IV, &I, It->second, getMaxWidenStepsOpts());
1689 return;
1690 }
1691 }
1692 }
1693
1694 // Transform load from a constant into a constant if possible.
1695 if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL))
1696 return (void)markConstant(IV, &I, C);
1697 }
1698
1699 // Fall back to metadata.
1700 mergeInValue(&I, getValueFromMetadata(&I));
1701}
1702
1703void SCCPInstVisitor::visitCallBase(CallBase &CB) {
1704 handleCallResult(CB);
1705 handleCallArguments(CB);
1706}
1707
1708void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) {
1710
1711 // Void return and not tracking callee, just bail.
1712 if (CB.getType()->isVoidTy())
1713 return;
1714
1715 // Always mark struct return as overdefined.
1716 if (CB.getType()->isStructTy())
1717 return (void)markOverdefined(&CB);
1718
1719 // Otherwise, if we have a single return value case, and if the function is
1720 // a declaration, maybe we can constant fold it.
1721 if (F && F->isDeclaration() && canConstantFoldCallTo(&CB, F)) {
1723 for (const Use &A : CB.args()) {
1724 if (A.get()->getType()->isStructTy())
1725 return markOverdefined(&CB); // Can't handle struct args.
1726 if (A.get()->getType()->isMetadataTy())
1727 continue; // Carried in CB, not allowed in Operands.
1728 ValueLatticeElement State = getValueState(A);
1729
1730 if (State.isUnknownOrUndef())
1731 return; // Operands are not resolved yet.
1732 if (SCCPSolver::isOverdefined(State))
1733 return (void)markOverdefined(&CB);
1734 assert(SCCPSolver::isConstant(State) && "Unknown state!");
1735 Operands.push_back(getConstant(State, A->getType()));
1736 }
1737
1738 if (SCCPSolver::isOverdefined(getValueState(&CB)))
1739 return (void)markOverdefined(&CB);
1740
1741 // If we can constant fold this, mark the result of the call as a
1742 // constant.
1743 if (Constant *C = ConstantFoldCall(&CB, F, Operands, &GetTLI(*F)))
1744 return (void)markConstant(&CB, C);
1745 }
1746
1747 // Fall back to metadata.
1748 mergeInValue(&CB, getValueFromMetadata(&CB));
1749}
1750
1751void SCCPInstVisitor::handleCallArguments(CallBase &CB) {
1753 // If this is a local function that doesn't have its address taken, mark its
1754 // entry block executable and merge in the actual arguments to the call into
1755 // the formal arguments of the function.
1756 if (TrackingIncomingArguments.count(F)) {
1757 markBlockExecutable(&F->front());
1758
1759 // Propagate information from this call site into the callee.
1760 auto CAI = CB.arg_begin();
1761 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
1762 ++AI, ++CAI) {
1763 // If this argument is byval, and if the function is not readonly, there
1764 // will be an implicit copy formed of the input aggregate.
1765 if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
1766 markOverdefined(&*AI);
1767 continue;
1768 }
1769
1770 if (auto *STy = dyn_cast<StructType>(AI->getType())) {
1771 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1772 ValueLatticeElement CallArg = getStructValueState(*CAI, i);
1773 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1775 }
1776 } else
1777 mergeInValue(&*AI, getValueState(*CAI), getMaxWidenStepsOpts());
1778 }
1779 }
1780}
1781
1782void SCCPInstVisitor::handleCallResult(CallBase &CB) {
1784
1785 if (auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1786 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1787 if (ValueState[&CB].isOverdefined())
1788 return;
1789
1790 Value *CopyOf = CB.getOperand(0);
1791 ValueLatticeElement CopyOfVal = getValueState(CopyOf);
1792 const auto *PI = getPredicateInfoFor(&CB);
1793 assert(PI && "Missing predicate info for ssa.copy");
1794
1795 const std::optional<PredicateConstraint> &Constraint =
1796 PI->getConstraint();
1797 if (!Constraint) {
1798 mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1799 return;
1800 }
1801
1802 CmpInst::Predicate Pred = Constraint->Predicate;
1803 Value *OtherOp = Constraint->OtherOp;
1804
1805 // Wait until OtherOp is resolved.
1806 if (getValueState(OtherOp).isUnknown()) {
1807 addAdditionalUser(OtherOp, &CB);
1808 return;
1809 }
1810
1811 ValueLatticeElement CondVal = getValueState(OtherOp);
1812 ValueLatticeElement &IV = ValueState[&CB];
1813 if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) {
1814 auto ImposedCR =
1815 ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
1816
1817 // Get the range imposed by the condition.
1818 if (CondVal.isConstantRange())
1820 Pred, CondVal.getConstantRange());
1821
1822 // Combine range info for the original value with the new range from the
1823 // condition.
1824 auto CopyOfCR = getConstantRange(CopyOfVal, CopyOf->getType(),
1825 /*UndefAllowed=*/true);
1826 auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1827 // If the existing information is != x, do not use the information from
1828 // a chained predicate, as the != x information is more likely to be
1829 // helpful in practice.
1830 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1831 NewCR = CopyOfCR;
1832
1833 // The new range is based on a branch condition. That guarantees that
1834 // neither of the compare operands can be undef in the branch targets,
1835 // unless we have conditions that are always true/false (e.g. icmp ule
1836 // i32, %a, i32_max). For the latter overdefined/empty range will be
1837 // inferred, but the branch will get folded accordingly anyways.
1838 addAdditionalUser(OtherOp, &CB);
1839 mergeInValue(
1840 IV, &CB,
1841 ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef*/ false));
1842 return;
1843 } else if (Pred == CmpInst::ICMP_EQ &&
1844 (CondVal.isConstant() || CondVal.isNotConstant())) {
1845 // For non-integer values or integer constant expressions, only
1846 // propagate equal constants or not-constants.
1847 addAdditionalUser(OtherOp, &CB);
1848 mergeInValue(IV, &CB, CondVal);
1849 return;
1850 } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {
1851 // Propagate inequalities.
1852 addAdditionalUser(OtherOp, &CB);
1853 mergeInValue(IV, &CB,
1855 return;
1856 }
1857
1858 return (void)mergeInValue(IV, &CB, CopyOfVal);
1859 }
1860
1861 if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
1862 // Compute result range for intrinsics supported by ConstantRange.
1863 // Do this even if we don't know a range for all operands, as we may
1864 // still know something about the result range, e.g. of abs(x).
1866 for (Value *Op : II->args()) {
1867 const ValueLatticeElement &State = getValueState(Op);
1868 if (State.isUnknownOrUndef())
1869 return;
1870 OpRanges.push_back(
1871 getConstantRange(State, Op->getType(), /*UndefAllowed=*/false));
1872 }
1873
1875 ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges);
1876 return (void)mergeInValue(II, ValueLatticeElement::getRange(Result));
1877 }
1878 }
1879
1880 // The common case is that we aren't tracking the callee, either because we
1881 // are not doing interprocedural analysis or the callee is indirect, or is
1882 // external. Handle these cases first.
1883 if (!F || F->isDeclaration())
1884 return handleCallOverdefined(CB);
1885
1886 // If this is a single/zero retval case, see if we're tracking the function.
1887 if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
1888 if (!MRVFunctionsTracked.count(F))
1889 return handleCallOverdefined(CB); // Not tracking this callee.
1890
1891 // If we are tracking this callee, propagate the result of the function
1892 // into this call site.
1893 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1894 mergeInValue(getStructValueState(&CB, i), &CB,
1895 TrackedMultipleRetVals[std::make_pair(F, i)],
1897 } else {
1898 auto TFRVI = TrackedRetVals.find(F);
1899 if (TFRVI == TrackedRetVals.end())
1900 return handleCallOverdefined(CB); // Not tracking this callee.
1901
1902 // If so, propagate the return value of the callee into this call result.
1903 mergeInValue(&CB, TFRVI->second, getMaxWidenStepsOpts());
1904 }
1905}
1906
1908 // Process the work lists until they are empty!
1909 while (!BBWorkList.empty() || !InstWorkList.empty() ||
1910 !OverdefinedInstWorkList.empty()) {
1911 // Process the overdefined instruction's work list first, which drives other
1912 // things to overdefined more quickly.
1913 while (!OverdefinedInstWorkList.empty()) {
1914 Value *I = OverdefinedInstWorkList.pop_back_val();
1915 Invalidated.erase(I);
1916
1917 LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n');
1918
1919 // "I" got into the work list because it either made the transition from
1920 // bottom to constant, or to overdefined.
1921 //
1922 // Anything on this worklist that is overdefined need not be visited
1923 // since all of its users will have already been marked as overdefined
1924 // Update all of the users of this instruction's value.
1925 //
1926 markUsersAsChanged(I);
1927 }
1928
1929 // Process the instruction work list.
1930 while (!InstWorkList.empty()) {
1931 Value *I = InstWorkList.pop_back_val();
1932 Invalidated.erase(I);
1933
1934 LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n');
1935
1936 // "I" got into the work list because it made the transition from undef to
1937 // constant.
1938 //
1939 // Anything on this worklist that is overdefined need not be visited
1940 // since all of its users will have already been marked as overdefined.
1941 // Update all of the users of this instruction's value.
1942 //
1943 if (I->getType()->isStructTy() || !getValueState(I).isOverdefined())
1944 markUsersAsChanged(I);
1945 }
1946
1947 // Process the basic block work list.
1948 while (!BBWorkList.empty()) {
1949 BasicBlock *BB = BBWorkList.pop_back_val();
1950
1951 LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n');
1952
1953 // Notify all instructions in this basic block that they are newly
1954 // executable.
1955 visit(BB);
1956 }
1957 }
1958}
1959
1961 // Look for instructions which produce undef values.
1962 if (I.getType()->isVoidTy())
1963 return false;
1964
1965 if (auto *STy = dyn_cast<StructType>(I.getType())) {
1966 // Only a few things that can be structs matter for undef.
1967
1968 // Tracked calls must never be marked overdefined in resolvedUndefsIn.
1969 if (auto *CB = dyn_cast<CallBase>(&I))
1970 if (Function *F = CB->getCalledFunction())
1971 if (MRVFunctionsTracked.count(F))
1972 return false;
1973
1974 // extractvalue and insertvalue don't need to be marked; they are
1975 // tracked as precisely as their operands.
1976 if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
1977 return false;
1978 // Send the results of everything else to overdefined. We could be
1979 // more precise than this but it isn't worth bothering.
1980 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1981 ValueLatticeElement &LV = getStructValueState(&I, i);
1982 if (LV.isUnknown()) {
1983 markOverdefined(LV, &I);
1984 return true;
1985 }
1986 }
1987 return false;
1988 }
1989
1990 ValueLatticeElement &LV = getValueState(&I);
1991 if (!LV.isUnknown())
1992 return false;
1993
1994 // There are two reasons a call can have an undef result
1995 // 1. It could be tracked.
1996 // 2. It could be constant-foldable.
1997 // Because of the way we solve return values, tracked calls must
1998 // never be marked overdefined in resolvedUndefsIn.
1999 if (auto *CB = dyn_cast<CallBase>(&I))
2000 if (Function *F = CB->getCalledFunction())
2001 if (TrackedRetVals.count(F))
2002 return false;
2003
2004 if (isa<LoadInst>(I)) {
2005 // A load here means one of two things: a load of undef from a global,
2006 // a load from an unknown pointer. Either way, having it return undef
2007 // is okay.
2008 return false;
2009 }
2010
2011 markOverdefined(&I);
2012 return true;
2013}
2014
2015/// While solving the dataflow for a function, we don't compute a result for
2016/// operations with an undef operand, to allow undef to be lowered to a
2017/// constant later. For example, constant folding of "zext i8 undef to i16"
2018/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
2019/// zext result would become "i16 1" and would result into an overdefined
2020/// lattice value once merged with the previous result. Not computing the
2021/// result of the zext (treating undef the same as unknown) allows us to handle
2022/// a later undef->constant lowering more optimally.
2023///
2024/// However, if the operand remains undef when the solver returns, we do need
2025/// to assign some result to the instruction (otherwise we would treat it as
2026/// unreachable). For simplicity, we mark any instructions that are still
2027/// unknown as overdefined.
2029 bool MadeChange = false;
2030 for (BasicBlock &BB : F) {
2031 if (!BBExecutable.count(&BB))
2032 continue;
2033
2034 for (Instruction &I : BB)
2035 MadeChange |= resolvedUndef(I);
2036 }
2037
2038 LLVM_DEBUG(if (MadeChange) dbgs()
2039 << "\nResolved undefs in " << F.getName() << '\n');
2040
2041 return MadeChange;
2042}
2043
2044//===----------------------------------------------------------------------===//
2045//
2046// SCCPSolver implementations
2047//
2049 const DataLayout &DL,
2050 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
2051 LLVMContext &Ctx)
2052 : Visitor(new SCCPInstVisitor(DL, std::move(GetTLI), Ctx)) {}
2053
2054SCCPSolver::~SCCPSolver() = default;
2055
2057 AssumptionCache &AC) {
2058 Visitor->addPredicateInfo(F, DT, AC);
2059}
2060
2062 return Visitor->markBlockExecutable(BB);
2063}
2064
2066 return Visitor->getPredicateInfoFor(I);
2067}
2068
2070 Visitor->trackValueOfGlobalVariable(GV);
2071}
2072
2074 Visitor->addTrackedFunction(F);
2075}
2076
2078 Visitor->addToMustPreserveReturnsInFunctions(F);
2079}
2080
2082 return Visitor->mustPreserveReturn(F);
2083}
2084
2086 Visitor->addArgumentTrackedFunction(F);
2087}
2088
2090 return Visitor->isArgumentTrackedFunction(F);
2091}
2092
2093void SCCPSolver::solve() { Visitor->solve(); }
2094
2096 return Visitor->resolvedUndefsIn(F);
2097}
2098
2100 Visitor->solveWhileResolvedUndefsIn(M);
2101}
2102
2103void
2105 Visitor->solveWhileResolvedUndefsIn(WorkList);
2106}
2107
2109 Visitor->solveWhileResolvedUndefs();
2110}
2111
2113 return Visitor->isBlockExecutable(BB);
2114}
2115
2117 return Visitor->isEdgeFeasible(From, To);
2118}
2119
2120std::vector<ValueLatticeElement>
2122 return Visitor->getStructLatticeValueFor(V);
2123}
2124
2126 return Visitor->removeLatticeValueFor(V);
2127}
2128
2130 Visitor->resetLatticeValueFor(Call);
2131}
2132
2134 return Visitor->getLatticeValueFor(V);
2135}
2136
2139 return Visitor->getTrackedRetVals();
2140}
2141
2144 return Visitor->getTrackedGlobals();
2145}
2146
2148 return Visitor->getMRVFunctionsTracked();
2149}
2150
2151void SCCPSolver::markOverdefined(Value *V) { Visitor->markOverdefined(V); }
2152
2154 Visitor->trackValueOfArgument(V);
2155}
2156
2158 return Visitor->isStructLatticeConstant(F, STy);
2159}
2160
2162 Type *Ty) const {
2163 return Visitor->getConstant(LV, Ty);
2164}
2165
2167 return Visitor->getConstantOrNull(V);
2168}
2169
2171 return Visitor->getArgumentTrackedFunctions();
2172}
2173
2175 const SmallVectorImpl<ArgInfo> &Args) {
2176 Visitor->setLatticeValueForSpecializationArguments(F, Args);
2177}
2178
2180 Visitor->markFunctionUnreachable(F);
2181}
2182
2183void SCCPSolver::visit(Instruction *I) { Visitor->visit(I); }
2184
2185void SCCPSolver::visitCall(CallInst &I) { Visitor->visitCall(I); }
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Addr
bool End
Definition: ELF_riscv.cpp:480
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts()
Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
Definition: SCCPSolver.cpp:40
static const unsigned MaxNumRangeExtensions
Definition: SCCPSolver.cpp:37
static ValueLatticeElement getValueFromMetadata(const Instruction *I)
static ConstantRange getConstantRange(const ValueLatticeElement &LV, Type *Ty, bool UndefAllowed)
Definition: SCCPSolver.cpp:45
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:78
Class for arbitrary precision integers.
Definition: APInt.h:77
This class represents an incoming formal argument to a Function.
Definition: Argument.h:31
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:499
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:199
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:221
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:509
Value * getRHS() const
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Value * getLHS() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
The address of a basic block.
Definition: Constants.h:890
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1494
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:2428
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1750
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1670
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1686
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:601
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:983
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:993
@ ICMP_EQ
equal
Definition: InstrTypes.h:1014
@ ICMP_NE
not equal
Definition: InstrTypes.h:1015
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:206
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:857
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1762
This class represents a range of values.
Definition: ConstantRange.h:47
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
bool isSingleElement() const
Return true if this set contains exactly one member.
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1357
This is an important base class in LLVM.
Definition: Constant.h:41
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:345
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This instruction extracts a struct member or array element value from an aggregate value.
unsigned getNumIndices() const
idx_iterator idx_begin() const
An instruction for ordering other memory operations.
Definition: Instructions.h:461
This class represents a freeze function that returns random concrete value if an operand is either a ...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:974
Type * getValueType() const
Definition: GlobalValue.h:295
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This instruction inserts a struct field of array element value into an aggregate value.
Base class for instruction visitors.
Definition: InstVisitor.h:78
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:87
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
void setNonNeg(bool b=true)
Set or clear the nneg flag on this instruction, which must be a zext instruction.
bool hasNonNeg() const LLVM_READONLY
Determine whether the the nneg flag is set.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:252
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
bool isSpecialTerminator() const
Definition: Instruction.h:262
Invoke instruction.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
An instruction for reading from memory.
Definition: Instructions.h:185
Metadata node.
Definition: Metadata.h:1067
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
size_type count(const KeyT &Key) const
Definition: MapVector.h:165
iterator end()
Definition: MapVector.h:71
iterator find(const KeyT &Key)
Definition: MapVector.h:167
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:141
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Resume the propagation of an exception.
Return a value (possibly void), from a function.
Helper class for SCCPSolver.
Definition: SCCPSolver.cpp:364
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:705
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:764
bool resolvedUndef(Instruction &I)
void markFunctionUnreachable(Function *F)
Definition: SCCPSolver.cpp:845
bool markBlockExecutable(BasicBlock *BB)
Definition: SCCPSolver.cpp:885
bool resolvedUndefsIn(Function &F)
While solving the dataflow for a function, we don't compute a result for operations with an undef ope...
Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const
Definition: SCCPSolver.cpp:950
SCCPInstVisitor(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:712
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:791
void removeLatticeValueFor(Value *V)
Definition: SCCPSolver.cpp:776
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
Definition: SCCPSolver.cpp:805
void trackValueOfArgument(Argument *A)
Definition: SCCPSolver.cpp:821
void visitCallInst(CallInst &I)
Definition: SCCPSolver.cpp:701
void markOverdefined(Value *V)
Definition: SCCPSolver.cpp:813
bool isArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:748
void addTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:725
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Definition: SCCPSolver.cpp:838
void solveWhileResolvedUndefsIn(Module &M)
Definition: SCCPSolver.cpp:850
void trackValueOfGlobalVariable(GlobalVariable *GV)
Definition: SCCPSolver.cpp:717
Constant * getConstantOrNull(Value *V) const
Definition: SCCPSolver.cpp:966
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
Definition: SCCPSolver.cpp:809
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
Definition: SCCPSolver.cpp:780
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
Definition: SCCPSolver.cpp:801
void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
Definition: SCCPSolver.cpp:697
void addToMustPreserveReturnsInFunctions(Function *F)
Definition: SCCPSolver.cpp:736
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:744
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:939
void solveWhileResolvedUndefsIn(SmallVectorImpl< Function * > &WorkList)
Definition: SCCPSolver.cpp:860
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:758
bool mustPreserveReturn(Function *F)
Definition: SCCPSolver.cpp:740
void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Definition: SCCPSolver.cpp:992
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:65
void visitCall(CallInst &I)
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
bool tryToReplaceWithConstant(Value *V)
Definition: SCCPSolver.cpp:76
bool isStructLatticeConstant(Function *F, StructType *STy)
void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
void solve()
Solve - Solve for constants and executable blocks.
void visit(Instruction *I)
void trackValueOfArgument(Argument *V)
trackValueOfArgument - Mark the specified argument overdefined unless it have range attribute.
void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
void solveWhileResolvedUndefsIn(Module &M)
const PredicateBase * getPredicateInfoFor(Instruction *I)
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
void addArgumentTrackedFunction(Function *F)
void solveWhileResolvedUndefs()
void removeLatticeValueFor(Value *V)
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
Constant * getConstantOrNull(Value *V) const
Return either a Constant or nullptr for a given Value.
bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Definition: SCCPSolver.cpp:244
Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
const ValueLatticeElement & getLatticeValueFor(Value *V) const
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const
Definition: SCCPSolver.cpp:268
bool isBlockExecutable(BasicBlock *BB) const
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Set the Lattice Value for the arguments of a specialization F.
static bool isConstant(const ValueLatticeElement &LV)
Definition: SCCPSolver.cpp:55
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
static bool isOverdefined(const ValueLatticeElement &LV)
Definition: SCCPSolver.cpp:60
void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
This class represents the LLVM 'select' instruction.
size_type size() const
Definition: SmallPtrSet.h:94
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
iterator begin() const
Definition: SmallPtrSet.h:380
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:717
void resize(size_type N)
Definition: SmallVector.h:651
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:318
Class to represent struct types.
Definition: DerivedTypes.h:216
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:341
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Provides information about what library functions are available for the current target.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:234
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition: Type.h:287
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:249
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:140
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1795
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Value * getOperand(unsigned i) const
Definition: User.h:169
This class represents lattice values for constants.
Definition: ValueLattice.h:29
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
Definition: ValueLattice.h:214
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
static ValueLatticeElement getNot(Constant *C)
Definition: ValueLattice.h:208
void setNumRangeExtensions(unsigned N)
Definition: ValueLattice.h:456
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:269
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
Definition: ValueLattice.h:249
unsigned getNumRangeExtensions() const
Definition: ValueLattice.h:455
bool isUnknownOrUndef() const
Definition: ValueLattice.h:239
Constant * getConstant() const
Definition: ValueLattice.h:255
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
Definition: ValueLattice.h:385
bool markConstant(Constant *V, bool MayIncludeUndef=false)
Definition: ValueLattice.h:301
static ValueLatticeElement getOverdefined()
Definition: ValueLattice.h:231
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
std::string getNameOrAsOperand() const
Definition: Value.cpp:445
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
self_iterator getIterator()
Definition: ilist_node.h:109
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static bool replaceSignedInst(SCCPSolver &Solver, SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to replace signed instructions with their unsigned equivalent.
Definition: SCCPSolver.cpp:176
bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:656
Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Definition: Function.cpp:2061
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool wouldInstructionBeTriviallyDead(const Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
Definition: Local.cpp:419
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
DWARFExpression::Operation Op
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
static bool canRemoveInstruction(Instruction *I)
Definition: SCCPSolver.cpp:64
Constant * ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty, APInt Offset, const DataLayout &DL)
Return the value that a load from C with offset Offset would produce if it is constant and determinab...
static bool refineInstruction(SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to use Inst's value range from Solver to infer the NUW flag.
Definition: SCCPSolver.cpp:107
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
Struct to control some aspects related to merging constant ranges.
Definition: ValueLattice.h:111
MergeOptions & setMaxWidenSteps(unsigned Steps=1)
Definition: ValueLattice.h:140
MergeOptions & setCheckWiden(bool V=true)
Definition: ValueLattice.h:135