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