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