1//===- AssumeBundleBuilder.cpp - tools to preserve informations -*- 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/Utils/AssumeBundleBuilder.h"
10#include "llvm/ADT/DepthFirstIterator.h"
11#include "llvm/ADT/MapVector.h"
12#include "llvm/ADT/Statistic.h"
13#include "llvm/Analysis/AssumeBundleQueries.h"
14#include "llvm/Analysis/AssumptionCache.h"
15#include "llvm/Analysis/ValueTracking.h"
16#include "llvm/IR/Dominators.h"
17#include "llvm/IR/Function.h"
18#include "llvm/IR/InstIterator.h"
19#include "llvm/IR/IntrinsicInst.h"
20#include "llvm/IR/Module.h"
21#include "llvm/IR/Operator.h"
22#include "llvm/Support/CommandLine.h"
23#include "llvm/Support/DebugCounter.h"
24#include "llvm/Transforms/Utils/Local.h"
25
26using namespace llvm;
27
28namespace llvm {
29cl::opt<bool> EnableKnowledgeRetention(
30 "enable-knowledge-retention", cl::init(Val: false), cl::Hidden,
31 cl::desc(
32 "enable preservation of attributes throughout code transformation"));
33} // namespace llvm
34
35#define DEBUG_TYPE "assume-builder"
36
37STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");
38STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");
39
40DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",
41 "Controls which assumes gets created");
42
43namespace {
44
45bool isUsefullToPreserve(Attribute::AttrKind Kind) {
46 switch (Kind) {
47 case Attribute::NonNull:
48 case Attribute::NoUndef:
49 case Attribute::Alignment:
50 case Attribute::Dereferenceable:
51 case Attribute::DereferenceableOrNull:
52 case Attribute::Cold:
53 return true;
54 default:
55 return false;
56 }
57}
58
59/// This function will try to transform the given knowledge into a more
60/// canonical one. the canonical knowledge maybe the given one.
61RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK,
62 const DataLayout &DL) {
63 switch (RK.AttrKind) {
64 default:
65 return RK;
66 case Attribute::NonNull:
67 RK.WasOn = RK.WasOn->stripInBoundsOffsets();
68 return RK;
69 case Attribute::Alignment: {
70 Value *V = RK.WasOn->stripInBoundsOffsets(Func: [&](const Value *Strip) {
71 if (auto *GEP = dyn_cast<GEPOperator>(Val: Strip))
72 RK.ArgValue =
73 MinAlign(A: RK.ArgValue, B: GEP->getMaxPreservedAlignment(DL).value());
74 });
75 RK.WasOn = V;
76 return RK;
77 }
78 case Attribute::Dereferenceable:
79 case Attribute::DereferenceableOrNull: {
80 int64_t Offset = 0;
81 Value *V = GetPointerBaseWithConstantOffset(Ptr: RK.WasOn, Offset, DL,
82 /*AllowNonInBounds*/ AllowNonInbounds: false);
83 if (Offset < 0)
84 return RK;
85 RK.ArgValue = RK.ArgValue + Offset;
86 RK.WasOn = V;
87 }
88 }
89 return RK;
90}
91
92/// This class contain all knowledge that have been gather while building an
93/// llvm.assume and the function to manipulate it.
94struct AssumeBuilderState {
95 Module *M;
96
97 using MapKey = std::pair<Value *, Attribute::AttrKind>;
98 SmallMapVector<MapKey, uint64_t, 8> AssumedKnowledgeMap;
99 Instruction *InstBeingModified = nullptr;
100 AssumptionCache* AC = nullptr;
101 DominatorTree* DT = nullptr;
102
103 AssumeBuilderState(Module *M, Instruction *I = nullptr,
104 AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)
105 : M(M), InstBeingModified(I), AC(AC), DT(DT) {}
106
107 bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {
108 if (!InstBeingModified || !RK.WasOn || !AC)
109 return false;
110 bool HasBeenPreserved = false;
111 Use* ToUpdate = nullptr;
112 getKnowledgeForValue(
113 V: RK.WasOn, AttrKinds: {RK.AttrKind}, AC&: *AC,
114 Filter: [&](RetainedKnowledge RKOther, Instruction *Assume,
115 const CallInst::BundleOpInfo *Bundle) {
116 if (!isValidAssumeForContext(I: Assume, CtxI: InstBeingModified, DT))
117 return false;
118 if (RKOther.ArgValue >= RK.ArgValue) {
119 HasBeenPreserved = true;
120 return true;
121 } else if (isValidAssumeForContext(I: InstBeingModified, CtxI: Assume, DT)) {
122 HasBeenPreserved = true;
123 IntrinsicInst *Intr = cast<IntrinsicInst>(Val: Assume);
124 ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];
125 return true;
126 }
127 return false;
128 });
129 if (ToUpdate)
130 ToUpdate->set(
131 ConstantInt::get(Ty: Type::getInt64Ty(C&: M->getContext()), V: RK.ArgValue));
132 return HasBeenPreserved;
133 }
134
135 bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
136 if (!RK)
137 return false;
138 if (!RK.WasOn)
139 return true;
140 if (RK.WasOn->getType()->isPointerTy()) {
141 Value *UnderlyingPtr = getUnderlyingObject(V: RK.WasOn);
142 if (isa<AllocaInst>(Val: UnderlyingPtr) || isa<GlobalValue>(Val: UnderlyingPtr))
143 return false;
144 }
145 if (auto *Arg = dyn_cast<Argument>(Val: RK.WasOn)) {
146 if (Arg->hasAttribute(Kind: RK.AttrKind) &&
147 (!Attribute::isIntAttrKind(Kind: RK.AttrKind) ||
148 Arg->getAttribute(Kind: RK.AttrKind).getValueAsInt() >= RK.ArgValue))
149 return false;
150 return true;
151 }
152 if (auto *Inst = dyn_cast<Instruction>(Val: RK.WasOn))
153 if (wouldInstructionBeTriviallyDead(I: Inst)) {
154 if (RK.WasOn->use_empty())
155 return false;
156 Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
157 if (SingleUse && SingleUse->getUser() == InstBeingModified)
158 return false;
159 }
160 return true;
161 }
162
163 void addKnowledge(RetainedKnowledge RK) {
164 RK = canonicalizedKnowledge(RK, DL: M->getDataLayout());
165
166 if (!isKnowledgeWorthPreserving(RK))
167 return;
168
169 if (tryToPreserveWithoutAddingAssume(RK))
170 return;
171 MapKey Key{RK.WasOn, RK.AttrKind};
172 auto [Lookup, Inserted] = AssumedKnowledgeMap.try_emplace(Key, Args&: RK.ArgValue);
173 if (Inserted)
174 return;
175 assert(((Lookup->second == 0 && RK.ArgValue == 0) ||
176 (Lookup->second != 0 && RK.ArgValue != 0)) &&
177 "inconsistent argument value");
178
179 /// This is only desirable because for all attributes taking an argument
180 /// higher is better.
181 Lookup->second = std::max(a: Lookup->second, b: RK.ArgValue);
182 }
183
184 void addAttribute(Attribute Attr, Value *WasOn) {
185 if (Attr.isTypeAttribute() || Attr.isStringAttribute() ||
186 !isUsefullToPreserve(Kind: Attr.getKindAsEnum()))
187 return;
188 uint64_t AttrArg = 0;
189 if (Attr.isIntAttribute())
190 AttrArg = Attr.getValueAsInt();
191 addKnowledge(RK: {Attr.getKindAsEnum(), AttrArg, WasOn});
192 }
193
194 void addCall(const CallBase *Call) {
195 auto addAttrList = [&](AttributeList AttrList, unsigned NumArgs) {
196 for (unsigned Idx = 0; Idx < NumArgs; Idx++)
197 for (Attribute Attr : AttrList.getParamAttrs(ArgNo: Idx)) {
198 bool IsPoisonAttr = Attr.hasAttribute(Val: Attribute::NonNull) ||
199 Attr.hasAttribute(Val: Attribute::Alignment);
200 if (!IsPoisonAttr || Call->isPassingUndefUB(ArgNo: Idx))
201 addAttribute(Attr, WasOn: Call->getArgOperand(i: Idx));
202 }
203 for (Attribute Attr : AttrList.getFnAttrs())
204 addAttribute(Attr, WasOn: nullptr);
205 };
206 addAttrList(Call->getAttributes(), Call->arg_size());
207 if (Function *Fn = Call->getCalledFunction())
208 addAttrList(Fn->getAttributes(), Fn->arg_size());
209 }
210
211 AssumeInst *build() {
212 if (AssumedKnowledgeMap.empty())
213 return nullptr;
214 if (!DebugCounter::shouldExecute(Counter&: BuildAssumeCounter))
215 return nullptr;
216 Function *FnAssume =
217 Intrinsic::getOrInsertDeclaration(M, id: Intrinsic::assume);
218 LLVMContext &C = M->getContext();
219 SmallVector<OperandBundleDef, 8> OpBundle;
220 for (auto &MapElem : AssumedKnowledgeMap) {
221 SmallVector<Value *, 2> Args;
222 if (MapElem.first.first)
223 Args.push_back(Elt: MapElem.first.first);
224
225 /// This is only valid because for all attribute that currently exist a
226 /// value of 0 is useless. and should not be preserved.
227 if (MapElem.second)
228 Args.push_back(Elt: ConstantInt::get(Ty: Type::getInt64Ty(C&: M->getContext()),
229 V: MapElem.second));
230 OpBundle.push_back(Elt: OperandBundleDefT<Value *>(
231 std::string(Attribute::getNameFromAttrKind(AttrKind: MapElem.first.second)),
232 Args));
233 NumBundlesInAssumes++;
234 }
235 NumAssumeBuilt++;
236 return cast<AssumeInst>(Val: CallInst::Create(
237 Func: FnAssume, Args: ArrayRef<Value *>({ConstantInt::getTrue(Context&: C)}), Bundles: OpBundle));
238 }
239
240 void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType,
241 MaybeAlign MA) {
242 unsigned DerefSize = MemInst->getModule()
243 ->getDataLayout()
244 .getTypeStoreSize(Ty: AccType)
245 .getKnownMinValue();
246 if (DerefSize != 0) {
247 addKnowledge(RK: {Attribute::Dereferenceable, DerefSize, Pointer});
248 if (!NullPointerIsDefined(F: MemInst->getFunction(),
249 AS: Pointer->getType()->getPointerAddressSpace()))
250 addKnowledge(RK: {Attribute::NonNull, 0u, Pointer});
251 }
252 if (MA.valueOrOne() > 1)
253 addKnowledge(RK: {Attribute::Alignment, MA.valueOrOne().value(), Pointer});
254 }
255
256 void addInstruction(Instruction *I) {
257 if (auto *Call = dyn_cast<CallBase>(Val: I))
258 return addCall(Call);
259 if (auto *Load = dyn_cast<LoadInst>(Val: I))
260 return addAccessedPtr(MemInst: I, Pointer: Load->getPointerOperand(), AccType: Load->getType(),
261 MA: Load->getAlign());
262 if (auto *Store = dyn_cast<StoreInst>(Val: I))
263 return addAccessedPtr(MemInst: I, Pointer: Store->getPointerOperand(),
264 AccType: Store->getValueOperand()->getType(),
265 MA: Store->getAlign());
266 if (auto *RMW = dyn_cast<AtomicRMWInst>(Val: I))
267 return addAccessedPtr(MemInst: I, Pointer: RMW->getPointerOperand(),
268 AccType: RMW->getValOperand()->getType(), MA: RMW->getAlign());
269 if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(Val: I))
270 return addAccessedPtr(MemInst: I, Pointer: CmpXchg->getPointerOperand(),
271 AccType: CmpXchg->getCompareOperand()->getType(),
272 MA: CmpXchg->getAlign());
273 // TODO: Maybe we should look around and merge with other llvm.assume.
274 }
275};
276
277} // namespace
278
279AssumeInst *llvm::buildAssumeFromInst(Instruction *I) {
280 if (!EnableKnowledgeRetention)
281 return nullptr;
282 AssumeBuilderState Builder(I->getModule());
283 Builder.addInstruction(I);
284 return Builder.build();
285}
286
287bool llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC,
288 DominatorTree *DT) {
289 if (!EnableKnowledgeRetention || I->isTerminator())
290 return false;
291 bool Changed = false;
292 AssumeBuilderState Builder(I->getModule(), I, AC, DT);
293 Builder.addInstruction(I);
294 if (auto *Intr = Builder.build()) {
295 Intr->insertBefore(InsertPos: I->getIterator());
296 Changed = true;
297 if (AC)
298 AC->registerAssumption(CI: Intr);
299 }
300 return Changed;
301}
302
303PreservedAnalyses AssumeBuilderPass::run(Function &F,
304 FunctionAnalysisManager &AM) {
305 AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(IR&: F);
306 DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
307 bool Changed = false;
308 for (Instruction &I : instructions(F))
309 Changed |= salvageKnowledge(I: &I, AC, DT);
310 if (!Changed)
311 PreservedAnalyses::all();
312 PreservedAnalyses PA;
313 PA.preserveSet<CFGAnalyses>();
314 return PA;
315}
316