1//===------------------------------------------------------------*- 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#include "llvm/Transforms/Scalar/DropUnnecessaryAssumes.h"
10#include "llvm/ADT/SetVector.h"
11#include "llvm/Analysis/AssumptionCache.h"
12#include "llvm/Analysis/ValueTracking.h"
13#include "llvm/IR/IntrinsicInst.h"
14#include "llvm/IR/PatternMatch.h"
15#include "llvm/Transforms/Utils/Local.h"
16
17using namespace llvm;
18using namespace llvm::PatternMatch;
19
20static bool affectedValuesAreEphemeral(ArrayRef<Value *> Affected) {
21 // Check whether all the uses are ephemeral, i.e. recursively only used
22 // by assumes. In that case, the assume does not provide useful information.
23 // Note that additional users may appear as a result of inlining and CSE,
24 // so we should only make this assumption late in the optimization pipeline.
25 SmallSetVector<Instruction *, 32> Worklist;
26 auto AddUsers = [&](Value *V) {
27 for (User *U : V->users()) {
28 // Bail out if we need to inspect too many users.
29 if (Worklist.size() >= 32)
30 return false;
31 Worklist.insert(X: cast<Instruction>(Val: U));
32 }
33 return true;
34 };
35
36 for (Value *V : Affected) {
37 // Do not handle assumes on globals for now. The use list for them may
38 // contain uses in other functions.
39 if (!isa<Instruction, Argument>(Val: V))
40 return false;
41
42 if (!AddUsers(V))
43 return false;
44 }
45
46 for (unsigned Idx = 0; Idx < Worklist.size(); ++Idx) {
47 Instruction *I = Worklist[Idx];
48
49 // Use in assume is ephemeral.
50 if (isa<AssumeInst>(Val: I))
51 continue;
52
53 // Use in side-effecting instruction is non-ephemeral.
54 if (I->mayHaveSideEffects() || I->isTerminator())
55 return false;
56
57 // Otherwise, recursively look at the users.
58 if (!AddUsers(I))
59 return false;
60 }
61
62 return true;
63}
64
65PreservedAnalyses
66DropUnnecessaryAssumesPass::run(Function &F, FunctionAnalysisManager &FAM) {
67 AssumptionCache &AC = FAM.getResult<AssumptionAnalysis>(IR&: F);
68 bool Changed = false;
69
70 for (const WeakVH &Elem : AC.assumptions()) {
71 auto *Assume = cast_or_null<AssumeInst>(Val: Elem);
72 if (!Assume)
73 continue;
74
75 if (Assume->hasOperandBundles()) {
76 // Handle operand bundle assumptions.
77 SmallVector<WeakTrackingVH> DeadBundleArgs;
78 SmallVector<OperandBundleDef> KeptBundles;
79 unsigned NumBundles = Assume->getNumOperandBundles();
80 for (unsigned I = 0; I != NumBundles; ++I) {
81 auto IsDead = [&](OperandBundleUse Bundle) {
82 // "ignore" operand bundles are always dead.
83 if (Bundle.getTagName() == "ignore")
84 return true;
85
86 // "dereferenceable" operand bundles are only dropped if requested
87 // (e.g., after loop vectorization has run).
88 if (Bundle.getTagName() == "dereferenceable")
89 return DropDereferenceable;
90
91 // Bundles without arguments do not affect any specific values.
92 // Always keep them for now.
93 if (Bundle.Inputs.empty())
94 return false;
95
96 SmallVector<Value *> Affected;
97 AssumptionCache::findValuesAffectedByOperandBundle(
98 Bundle, InsertAffected: [&](Value *A) { Affected.push_back(Elt: A); });
99
100 return affectedValuesAreEphemeral(Affected);
101 };
102
103 OperandBundleUse Bundle = Assume->getOperandBundleAt(Index: I);
104 if (IsDead(Bundle))
105 append_range(C&: DeadBundleArgs, R&: Bundle.Inputs);
106 else
107 KeptBundles.emplace_back(Args&: Bundle);
108 }
109
110 if (KeptBundles.size() != NumBundles) {
111 if (KeptBundles.empty()) {
112 // All operand bundles are dead, remove the whole assume.
113 Assume->eraseFromParent();
114 } else {
115 // Otherwise only drop the dead operand bundles.
116 CallBase *NewAssume =
117 CallBase::Create(CB: Assume, Bundles: KeptBundles, InsertPt: Assume->getIterator());
118 AC.registerAssumption(CI: cast<AssumeInst>(Val: NewAssume));
119 Assume->eraseFromParent();
120 }
121
122 RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts&: DeadBundleArgs);
123 Changed = true;
124 }
125 continue;
126 }
127
128 Value *Cond = Assume->getArgOperand(i: 0);
129 // Don't drop type tests, which have special semantics.
130 if (match(V: Cond, P: m_Intrinsic<Intrinsic::type_test>()) ||
131 match(V: Cond, P: m_Intrinsic<Intrinsic::public_type_test>()))
132 continue;
133
134 SmallVector<Value *> Affected;
135 findValuesAffectedByCondition(Cond, /*IsAssume=*/true,
136 InsertAffected: [&](Value *A) { Affected.push_back(Elt: A); });
137
138 if (!affectedValuesAreEphemeral(Affected))
139 continue;
140
141 Assume->eraseFromParent();
142 RecursivelyDeleteTriviallyDeadInstructions(V: Cond);
143 Changed = true;
144 }
145
146 if (Changed) {
147 PreservedAnalyses PA;
148 PA.preserveSet<CFGAnalyses>();
149 return PA;
150 }
151 return PreservedAnalyses::all();
152}
153