File: | llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp |
Warning: | line 78, column 16 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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/InitializePasses.h" | |||
22 | #include "llvm/Support/CommandLine.h" | |||
23 | #include "llvm/Support/DebugCounter.h" | |||
24 | #include "llvm/Transforms/Utils/Local.h" | |||
25 | ||||
26 | using namespace llvm; | |||
27 | ||||
28 | namespace llvm { | |||
29 | cl::opt<bool> ShouldPreserveAllAttributes( | |||
30 | "assume-preserve-all", cl::init(false), cl::Hidden, | |||
31 | cl::desc("enable preservation of all attrbitues. even those that are " | |||
32 | "unlikely to be usefull")); | |||
33 | ||||
34 | cl::opt<bool> EnableKnowledgeRetention( | |||
35 | "enable-knowledge-retention", cl::init(false), cl::Hidden, | |||
36 | cl::desc( | |||
37 | "enable preservation of attributes throughout code transformation")); | |||
38 | } // namespace llvm | |||
39 | ||||
40 | #define DEBUG_TYPE"assume-builder" "assume-builder" | |||
41 | ||||
42 | STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder")static llvm::Statistic NumAssumeBuilt = {"assume-builder", "NumAssumeBuilt" , "Number of assume built by the assume builder"}; | |||
43 | STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built")static llvm::Statistic NumBundlesInAssumes = {"assume-builder" , "NumBundlesInAssumes", "Total number of Bundles in the assume built" }; | |||
44 | STATISTIC(NumAssumesMerged,static llvm::Statistic NumAssumesMerged = {"assume-builder", "NumAssumesMerged" , "Number of assume merged by the assume simplify pass"} | |||
45 | "Number of assume merged by the assume simplify pass")static llvm::Statistic NumAssumesMerged = {"assume-builder", "NumAssumesMerged" , "Number of assume merged by the assume simplify pass"}; | |||
46 | STATISTIC(NumAssumesRemoved,static llvm::Statistic NumAssumesRemoved = {"assume-builder", "NumAssumesRemoved", "Number of assume removed by the assume simplify pass" } | |||
47 | "Number of assume removed by the assume simplify pass")static llvm::Statistic NumAssumesRemoved = {"assume-builder", "NumAssumesRemoved", "Number of assume removed by the assume simplify pass" }; | |||
48 | ||||
49 | DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",static const unsigned BuildAssumeCounter = DebugCounter::registerCounter ("assume-builder-counter", "Controls which assumes gets created" ) | |||
50 | "Controls which assumes gets created")static const unsigned BuildAssumeCounter = DebugCounter::registerCounter ("assume-builder-counter", "Controls which assumes gets created" ); | |||
51 | ||||
52 | namespace { | |||
53 | ||||
54 | bool isUsefullToPreserve(Attribute::AttrKind Kind) { | |||
55 | switch (Kind) { | |||
56 | case Attribute::NonNull: | |||
57 | case Attribute::NoUndef: | |||
58 | case Attribute::Alignment: | |||
59 | case Attribute::Dereferenceable: | |||
60 | case Attribute::DereferenceableOrNull: | |||
61 | case Attribute::Cold: | |||
62 | return true; | |||
63 | default: | |||
64 | return false; | |||
65 | } | |||
66 | } | |||
67 | ||||
68 | /// This function will try to transform the given knowledge into a more | |||
69 | /// canonical one. the canonical knowledge maybe the given one. | |||
70 | RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK, DataLayout DL) { | |||
71 | switch (RK.AttrKind) { | |||
72 | default: | |||
73 | return RK; | |||
74 | case Attribute::NonNull: | |||
75 | RK.WasOn = getUnderlyingObject(RK.WasOn); | |||
76 | return RK; | |||
77 | case Attribute::Alignment: { | |||
78 | Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) { | |||
| ||||
79 | if (auto *GEP = dyn_cast<GEPOperator>(Strip)) | |||
80 | RK.ArgValue = | |||
81 | MinAlign(RK.ArgValue, GEP->getMaxPreservedAlignment(DL).value()); | |||
82 | }); | |||
83 | RK.WasOn = V; | |||
84 | return RK; | |||
85 | } | |||
86 | case Attribute::Dereferenceable: | |||
87 | case Attribute::DereferenceableOrNull: { | |||
88 | int64_t Offset = 0; | |||
89 | Value *V = GetPointerBaseWithConstantOffset(RK.WasOn, Offset, DL, | |||
90 | /*AllowNonInBounds*/ false); | |||
91 | if (Offset < 0) | |||
92 | return RK; | |||
93 | RK.ArgValue = RK.ArgValue + Offset; | |||
94 | RK.WasOn = V; | |||
95 | } | |||
96 | } | |||
97 | return RK; | |||
98 | } | |||
99 | ||||
100 | /// This class contain all knowledge that have been gather while building an | |||
101 | /// llvm.assume and the function to manipulate it. | |||
102 | struct AssumeBuilderState { | |||
103 | Module *M; | |||
104 | ||||
105 | using MapKey = std::pair<Value *, Attribute::AttrKind>; | |||
106 | SmallMapVector<MapKey, unsigned, 8> AssumedKnowledgeMap; | |||
107 | Instruction *InstBeingModified = nullptr; | |||
108 | AssumptionCache* AC = nullptr; | |||
109 | DominatorTree* DT = nullptr; | |||
110 | ||||
111 | AssumeBuilderState(Module *M, Instruction *I = nullptr, | |||
112 | AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr) | |||
113 | : M(M), InstBeingModified(I), AC(AC), DT(DT) {} | |||
114 | ||||
115 | bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) { | |||
116 | if (!InstBeingModified || !RK.WasOn) | |||
117 | return false; | |||
118 | bool HasBeenPreserved = false; | |||
119 | Use* ToUpdate = nullptr; | |||
120 | getKnowledgeForValue( | |||
121 | RK.WasOn, {RK.AttrKind}, AC, | |||
122 | [&](RetainedKnowledge RKOther, Instruction *Assume, | |||
123 | const CallInst::BundleOpInfo *Bundle) { | |||
124 | if (!isValidAssumeForContext(Assume, InstBeingModified, DT)) | |||
125 | return false; | |||
126 | if (RKOther.ArgValue >= RK.ArgValue) { | |||
127 | HasBeenPreserved = true; | |||
128 | return true; | |||
129 | } else if (isValidAssumeForContext(InstBeingModified, Assume, DT)) { | |||
130 | HasBeenPreserved = true; | |||
131 | IntrinsicInst *Intr = cast<IntrinsicInst>(Assume); | |||
132 | ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument]; | |||
133 | return true; | |||
134 | } | |||
135 | return false; | |||
136 | }); | |||
137 | if (ToUpdate) | |||
138 | ToUpdate->set( | |||
139 | ConstantInt::get(Type::getInt64Ty(M->getContext()), RK.ArgValue)); | |||
140 | return HasBeenPreserved; | |||
141 | } | |||
142 | ||||
143 | bool isKnowledgeWorthPreserving(RetainedKnowledge RK) { | |||
144 | if (!RK) | |||
145 | return false; | |||
146 | if (!RK.WasOn) | |||
147 | return true; | |||
148 | if (RK.WasOn->getType()->isPointerTy()) { | |||
149 | Value *UnderlyingPtr = getUnderlyingObject(RK.WasOn); | |||
150 | if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr)) | |||
151 | return false; | |||
152 | } | |||
153 | if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) { | |||
154 | if (Arg->hasAttribute(RK.AttrKind) && | |||
155 | (!Attribute::isIntAttrKind(RK.AttrKind) || | |||
156 | Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue)) | |||
157 | return false; | |||
158 | return true; | |||
159 | } | |||
160 | if (auto *Inst = dyn_cast<Instruction>(RK.WasOn)) | |||
161 | if (wouldInstructionBeTriviallyDead(Inst)) { | |||
162 | if (RK.WasOn->use_empty()) | |||
163 | return false; | |||
164 | Use *SingleUse = RK.WasOn->getSingleUndroppableUse(); | |||
165 | if (SingleUse && SingleUse->getUser() == InstBeingModified) | |||
166 | return false; | |||
167 | } | |||
168 | return true; | |||
169 | } | |||
170 | ||||
171 | void addKnowledge(RetainedKnowledge RK) { | |||
172 | RK = canonicalizedKnowledge(RK, M->getDataLayout()); | |||
173 | ||||
174 | if (!isKnowledgeWorthPreserving(RK)) | |||
175 | return; | |||
176 | ||||
177 | if (tryToPreserveWithoutAddingAssume(RK)) | |||
178 | return; | |||
179 | MapKey Key{RK.WasOn, RK.AttrKind}; | |||
180 | auto Lookup = AssumedKnowledgeMap.find(Key); | |||
181 | if (Lookup == AssumedKnowledgeMap.end()) { | |||
182 | AssumedKnowledgeMap[Key] = RK.ArgValue; | |||
183 | return; | |||
184 | } | |||
185 | assert(((Lookup->second == 0 && RK.ArgValue == 0) ||(static_cast<void> (0)) | |||
186 | (Lookup->second != 0 && RK.ArgValue != 0)) &&(static_cast<void> (0)) | |||
187 | "inconsistent argument value")(static_cast<void> (0)); | |||
188 | ||||
189 | /// This is only desirable because for all attributes taking an argument | |||
190 | /// higher is better. | |||
191 | Lookup->second = std::max(Lookup->second, RK.ArgValue); | |||
192 | } | |||
193 | ||||
194 | void addAttribute(Attribute Attr, Value *WasOn) { | |||
195 | if (Attr.isTypeAttribute() || Attr.isStringAttribute() || | |||
196 | (!ShouldPreserveAllAttributes && | |||
197 | !isUsefullToPreserve(Attr.getKindAsEnum()))) | |||
198 | return; | |||
199 | unsigned AttrArg = 0; | |||
200 | if (Attr.isIntAttribute()) | |||
201 | AttrArg = Attr.getValueAsInt(); | |||
202 | addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn}); | |||
203 | } | |||
204 | ||||
205 | void addCall(const CallBase *Call) { | |||
206 | auto addAttrList = [&](AttributeList AttrList, unsigned NumArgs) { | |||
207 | for (unsigned Idx = 0; Idx < NumArgs; Idx++) | |||
208 | for (Attribute Attr : AttrList.getParamAttrs(Idx)) { | |||
209 | bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) || | |||
210 | Attr.hasAttribute(Attribute::Alignment); | |||
211 | if (!IsPoisonAttr || Call->isPassingUndefUB(Idx)) | |||
212 | addAttribute(Attr, Call->getArgOperand(Idx)); | |||
213 | } | |||
214 | for (Attribute Attr : AttrList.getFnAttrs()) | |||
215 | addAttribute(Attr, nullptr); | |||
216 | }; | |||
217 | addAttrList(Call->getAttributes(), Call->arg_size()); | |||
218 | if (Function *Fn = Call->getCalledFunction()) | |||
219 | addAttrList(Fn->getAttributes(), Fn->arg_size()); | |||
220 | } | |||
221 | ||||
222 | AssumeInst *build() { | |||
223 | if (AssumedKnowledgeMap.empty()) | |||
224 | return nullptr; | |||
225 | if (!DebugCounter::shouldExecute(BuildAssumeCounter)) | |||
226 | return nullptr; | |||
227 | Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume); | |||
228 | LLVMContext &C = M->getContext(); | |||
229 | SmallVector<OperandBundleDef, 8> OpBundle; | |||
230 | for (auto &MapElem : AssumedKnowledgeMap) { | |||
231 | SmallVector<Value *, 2> Args; | |||
232 | if (MapElem.first.first) | |||
233 | Args.push_back(MapElem.first.first); | |||
234 | ||||
235 | /// This is only valid because for all attribute that currently exist a | |||
236 | /// value of 0 is useless. and should not be preserved. | |||
237 | if (MapElem.second) | |||
238 | Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()), | |||
239 | MapElem.second)); | |||
240 | OpBundle.push_back(OperandBundleDefT<Value *>( | |||
241 | std::string(Attribute::getNameFromAttrKind(MapElem.first.second)), | |||
242 | Args)); | |||
243 | NumBundlesInAssumes++; | |||
244 | } | |||
245 | NumAssumeBuilt++; | |||
246 | return cast<AssumeInst>(CallInst::Create( | |||
247 | FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle)); | |||
248 | } | |||
249 | ||||
250 | void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType, | |||
251 | MaybeAlign MA) { | |||
252 | unsigned DerefSize = MemInst->getModule() | |||
253 | ->getDataLayout() | |||
254 | .getTypeStoreSize(AccType) | |||
255 | .getKnownMinSize(); | |||
256 | if (DerefSize != 0) { | |||
257 | addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer}); | |||
258 | if (!NullPointerIsDefined(MemInst->getFunction(), | |||
259 | Pointer->getType()->getPointerAddressSpace())) | |||
260 | addKnowledge({Attribute::NonNull, 0u, Pointer}); | |||
261 | } | |||
262 | if (MA.valueOrOne() > 1) | |||
263 | addKnowledge( | |||
264 | {Attribute::Alignment, unsigned(MA.valueOrOne().value()), Pointer}); | |||
265 | } | |||
266 | ||||
267 | void addInstruction(Instruction *I) { | |||
268 | if (auto *Call
| |||
269 | return addCall(Call); | |||
270 | if (auto *Load
| |||
271 | return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(), | |||
272 | Load->getAlign()); | |||
273 | if (auto *Store = dyn_cast<StoreInst>(I)) | |||
274 | return addAccessedPtr(I, Store->getPointerOperand(), | |||
275 | Store->getValueOperand()->getType(), | |||
276 | Store->getAlign()); | |||
277 | // TODO: Add support for the other Instructions. | |||
278 | // TODO: Maybe we should look around and merge with other llvm.assume. | |||
279 | } | |||
280 | }; | |||
281 | ||||
282 | } // namespace | |||
283 | ||||
284 | AssumeInst *llvm::buildAssumeFromInst(Instruction *I) { | |||
285 | if (!EnableKnowledgeRetention) | |||
| ||||
286 | return nullptr; | |||
287 | AssumeBuilderState Builder(I->getModule()); | |||
288 | Builder.addInstruction(I); | |||
289 | return Builder.build(); | |||
290 | } | |||
291 | ||||
292 | void llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC, | |||
293 | DominatorTree *DT) { | |||
294 | if (!EnableKnowledgeRetention || I->isTerminator()) | |||
295 | return; | |||
296 | AssumeBuilderState Builder(I->getModule(), I, AC, DT); | |||
297 | Builder.addInstruction(I); | |||
298 | if (auto *Intr = Builder.build()) { | |||
299 | Intr->insertBefore(I); | |||
300 | if (AC) | |||
301 | AC->registerAssumption(Intr); | |||
302 | } | |||
303 | } | |||
304 | ||||
305 | AssumeInst * | |||
306 | llvm::buildAssumeFromKnowledge(ArrayRef<RetainedKnowledge> Knowledge, | |||
307 | Instruction *CtxI, AssumptionCache *AC, | |||
308 | DominatorTree *DT) { | |||
309 | AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT); | |||
310 | for (const RetainedKnowledge &RK : Knowledge) | |||
311 | Builder.addKnowledge(RK); | |||
312 | return Builder.build(); | |||
313 | } | |||
314 | ||||
315 | RetainedKnowledge llvm::simplifyRetainedKnowledge(AssumeInst *Assume, | |||
316 | RetainedKnowledge RK, | |||
317 | AssumptionCache *AC, | |||
318 | DominatorTree *DT) { | |||
319 | AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT); | |||
320 | RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout()); | |||
321 | ||||
322 | if (!Builder.isKnowledgeWorthPreserving(RK)) | |||
323 | return RetainedKnowledge::none(); | |||
324 | ||||
325 | if (Builder.tryToPreserveWithoutAddingAssume(RK)) | |||
326 | return RetainedKnowledge::none(); | |||
327 | return RK; | |||
328 | } | |||
329 | ||||
330 | namespace { | |||
331 | ||||
332 | struct AssumeSimplify { | |||
333 | Function &F; | |||
334 | AssumptionCache &AC; | |||
335 | DominatorTree *DT; | |||
336 | LLVMContext &C; | |||
337 | SmallDenseSet<IntrinsicInst *> CleanupToDo; | |||
338 | StringMapEntry<uint32_t> *IgnoreTag; | |||
339 | SmallDenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 4>, 8> BBToAssume; | |||
340 | bool MadeChange = false; | |||
341 | ||||
342 | AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT, | |||
343 | LLVMContext &C) | |||
344 | : F(F), AC(AC), DT(DT), C(C), | |||
345 | IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {} | |||
346 | ||||
347 | void buildMapping(bool FilterBooleanArgument) { | |||
348 | BBToAssume.clear(); | |||
349 | for (Value *V : AC.assumptions()) { | |||
350 | if (!V) | |||
351 | continue; | |||
352 | IntrinsicInst *Assume = cast<IntrinsicInst>(V); | |||
353 | if (FilterBooleanArgument) { | |||
354 | auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0)); | |||
355 | if (!Arg || Arg->isZero()) | |||
356 | continue; | |||
357 | } | |||
358 | BBToAssume[Assume->getParent()].push_back(Assume); | |||
359 | } | |||
360 | ||||
361 | for (auto &Elem : BBToAssume) { | |||
362 | llvm::sort(Elem.second, | |||
363 | [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) { | |||
364 | return LHS->comesBefore(RHS); | |||
365 | }); | |||
366 | } | |||
367 | } | |||
368 | ||||
369 | /// Remove all asumes in CleanupToDo if there boolean argument is true and | |||
370 | /// ForceCleanup is set or the assume doesn't hold valuable knowledge. | |||
371 | void RunCleanup(bool ForceCleanup) { | |||
372 | for (IntrinsicInst *Assume : CleanupToDo) { | |||
373 | auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0)); | |||
374 | if (!Arg || Arg->isZero() || | |||
375 | (!ForceCleanup && | |||
376 | !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume)))) | |||
377 | continue; | |||
378 | MadeChange = true; | |||
379 | if (ForceCleanup) | |||
380 | NumAssumesMerged++; | |||
381 | else | |||
382 | NumAssumesRemoved++; | |||
383 | Assume->eraseFromParent(); | |||
384 | } | |||
385 | CleanupToDo.clear(); | |||
386 | } | |||
387 | ||||
388 | /// Remove knowledge stored in assume when it is already know by an attribute | |||
389 | /// or an other assume. This can when valid update an existing knowledge in an | |||
390 | /// attribute or an other assume. | |||
391 | void dropRedundantKnowledge() { | |||
392 | struct MapValue { | |||
393 | IntrinsicInst *Assume; | |||
394 | unsigned ArgValue; | |||
395 | CallInst::BundleOpInfo *BOI; | |||
396 | }; | |||
397 | buildMapping(false); | |||
398 | SmallDenseMap<std::pair<Value *, Attribute::AttrKind>, | |||
399 | SmallVector<MapValue, 2>, 16> | |||
400 | Knowledge; | |||
401 | for (BasicBlock *BB : depth_first(&F)) | |||
402 | for (Value *V : BBToAssume[BB]) { | |||
403 | if (!V) | |||
404 | continue; | |||
405 | IntrinsicInst *Assume = cast<IntrinsicInst>(V); | |||
406 | for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) { | |||
407 | auto RemoveFromAssume = [&]() { | |||
408 | CleanupToDo.insert(Assume); | |||
409 | if (BOI.Begin != BOI.End) { | |||
410 | Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn]; | |||
411 | U->set(UndefValue::get(U->get()->getType())); | |||
412 | } | |||
413 | BOI.Tag = IgnoreTag; | |||
414 | }; | |||
415 | if (BOI.Tag == IgnoreTag) { | |||
416 | CleanupToDo.insert(Assume); | |||
417 | continue; | |||
418 | } | |||
419 | RetainedKnowledge RK = | |||
420 | getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI); | |||
421 | if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) { | |||
422 | bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind); | |||
423 | if (HasSameKindAttr) | |||
424 | if (!Attribute::isIntAttrKind(RK.AttrKind) || | |||
425 | Arg->getAttribute(RK.AttrKind).getValueAsInt() >= | |||
426 | RK.ArgValue) { | |||
427 | RemoveFromAssume(); | |||
428 | continue; | |||
429 | } | |||
430 | if (isValidAssumeForContext( | |||
431 | Assume, &*F.getEntryBlock().getFirstInsertionPt()) || | |||
432 | Assume == &*F.getEntryBlock().getFirstInsertionPt()) { | |||
433 | if (HasSameKindAttr) | |||
434 | Arg->removeAttr(RK.AttrKind); | |||
435 | Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue)); | |||
436 | MadeChange = true; | |||
437 | RemoveFromAssume(); | |||
438 | continue; | |||
439 | } | |||
440 | } | |||
441 | auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}]; | |||
442 | for (MapValue &Elem : Lookup) { | |||
443 | if (!isValidAssumeForContext(Elem.Assume, Assume, DT)) | |||
444 | continue; | |||
445 | if (Elem.ArgValue >= RK.ArgValue) { | |||
446 | RemoveFromAssume(); | |||
447 | continue; | |||
448 | } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) { | |||
449 | Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set( | |||
450 | ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue)); | |||
451 | MadeChange = true; | |||
452 | RemoveFromAssume(); | |||
453 | continue; | |||
454 | } | |||
455 | } | |||
456 | Lookup.push_back({Assume, RK.ArgValue, &BOI}); | |||
457 | } | |||
458 | } | |||
459 | } | |||
460 | ||||
461 | using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator; | |||
462 | ||||
463 | /// Merge all Assumes from Begin to End in and insert the resulting assume as | |||
464 | /// high as possible in the basicblock. | |||
465 | void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) { | |||
466 | if (Begin == End || std::next(Begin) == End) | |||
467 | return; | |||
468 | /// Provide no additional information so that AssumeBuilderState doesn't | |||
469 | /// try to do any punning since it already has been done better. | |||
470 | AssumeBuilderState Builder(F.getParent()); | |||
471 | ||||
472 | /// For now it is initialized to the best value it could have | |||
473 | Instruction *InsertPt = BB->getFirstNonPHI(); | |||
474 | if (isa<LandingPadInst>(InsertPt)) | |||
475 | InsertPt = InsertPt->getNextNode(); | |||
476 | for (IntrinsicInst *I : make_range(Begin, End)) { | |||
477 | CleanupToDo.insert(I); | |||
478 | for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) { | |||
479 | RetainedKnowledge RK = | |||
480 | getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI); | |||
481 | if (!RK) | |||
482 | continue; | |||
483 | Builder.addKnowledge(RK); | |||
484 | if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn)) | |||
485 | if (I->getParent() == InsertPt->getParent() && | |||
486 | (InsertPt->comesBefore(I) || InsertPt == I)) | |||
487 | InsertPt = I->getNextNode(); | |||
488 | } | |||
489 | } | |||
490 | ||||
491 | /// Adjust InsertPt if it is before Begin, since mergeAssumes only | |||
492 | /// guarantees we can place the resulting assume between Begin and End. | |||
493 | if (InsertPt->comesBefore(*Begin)) | |||
494 | for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator(); | |||
495 | It != E; --It) | |||
496 | if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) { | |||
497 | InsertPt = It->getNextNode(); | |||
498 | break; | |||
499 | } | |||
500 | auto *MergedAssume = Builder.build(); | |||
501 | if (!MergedAssume) | |||
502 | return; | |||
503 | MadeChange = true; | |||
504 | MergedAssume->insertBefore(InsertPt); | |||
505 | AC.registerAssumption(MergedAssume); | |||
506 | } | |||
507 | ||||
508 | /// Merge assume when they are in the same BasicBlock and for all instruction | |||
509 | /// between them isGuaranteedToTransferExecutionToSuccessor returns true. | |||
510 | void mergeAssumes() { | |||
511 | buildMapping(true); | |||
512 | ||||
513 | SmallVector<MergeIterator, 4> SplitPoints; | |||
514 | for (auto &Elem : BBToAssume) { | |||
515 | SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second; | |||
516 | if (AssumesInBB.size() < 2) | |||
517 | continue; | |||
518 | /// AssumesInBB is already sorted by order in the block. | |||
519 | ||||
520 | BasicBlock::iterator It = AssumesInBB.front()->getIterator(); | |||
521 | BasicBlock::iterator E = AssumesInBB.back()->getIterator(); | |||
522 | SplitPoints.push_back(AssumesInBB.begin()); | |||
523 | MergeIterator LastSplit = AssumesInBB.begin(); | |||
524 | for (; It != E; ++It) | |||
525 | if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) { | |||
526 | for (; (*LastSplit)->comesBefore(&*It); ++LastSplit) | |||
527 | ; | |||
528 | if (SplitPoints.back() != LastSplit) | |||
529 | SplitPoints.push_back(LastSplit); | |||
530 | } | |||
531 | SplitPoints.push_back(AssumesInBB.end()); | |||
532 | for (auto SplitIt = SplitPoints.begin(); | |||
533 | SplitIt != std::prev(SplitPoints.end()); SplitIt++) { | |||
534 | mergeRange(Elem.first, *SplitIt, *(SplitIt + 1)); | |||
535 | } | |||
536 | SplitPoints.clear(); | |||
537 | } | |||
538 | } | |||
539 | }; | |||
540 | ||||
541 | bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) { | |||
542 | AssumeSimplify AS(F, *AC, DT, F.getContext()); | |||
543 | ||||
544 | /// Remove knowledge that is already known by a dominating other assume or an | |||
545 | /// attribute. | |||
546 | AS.dropRedundantKnowledge(); | |||
547 | ||||
548 | /// Remove assume that are empty. | |||
549 | AS.RunCleanup(false); | |||
550 | ||||
551 | /// Merge assume in the same basicblock when possible. | |||
552 | AS.mergeAssumes(); | |||
553 | ||||
554 | /// Remove assume that were merged. | |||
555 | AS.RunCleanup(true); | |||
556 | return AS.MadeChange; | |||
557 | } | |||
558 | ||||
559 | } // namespace | |||
560 | ||||
561 | PreservedAnalyses AssumeSimplifyPass::run(Function &F, | |||
562 | FunctionAnalysisManager &AM) { | |||
563 | if (!EnableKnowledgeRetention) | |||
564 | return PreservedAnalyses::all(); | |||
565 | simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F), | |||
566 | AM.getCachedResult<DominatorTreeAnalysis>(F)); | |||
567 | return PreservedAnalyses::all(); | |||
568 | } | |||
569 | ||||
570 | namespace { | |||
571 | class AssumeSimplifyPassLegacyPass : public FunctionPass { | |||
572 | public: | |||
573 | static char ID; | |||
574 | ||||
575 | AssumeSimplifyPassLegacyPass() : FunctionPass(ID) { | |||
576 | initializeAssumeSimplifyPassLegacyPassPass( | |||
577 | *PassRegistry::getPassRegistry()); | |||
578 | } | |||
579 | bool runOnFunction(Function &F) override { | |||
580 | if (skipFunction(F) || !EnableKnowledgeRetention) | |||
581 | return false; | |||
582 | AssumptionCache &AC = | |||
583 | getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); | |||
584 | DominatorTreeWrapperPass *DTWP = | |||
585 | getAnalysisIfAvailable<DominatorTreeWrapperPass>(); | |||
586 | return simplifyAssumes(F, &AC, DTWP ? &DTWP->getDomTree() : nullptr); | |||
587 | } | |||
588 | ||||
589 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
590 | AU.addRequired<AssumptionCacheTracker>(); | |||
591 | ||||
592 | AU.setPreservesAll(); | |||
593 | } | |||
594 | }; | |||
595 | } // namespace | |||
596 | ||||
597 | char AssumeSimplifyPassLegacyPass::ID = 0; | |||
598 | ||||
599 | INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",static void *initializeAssumeSimplifyPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
600 | "Assume Simplify", false, false)static void *initializeAssumeSimplifyPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
601 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
602 | INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",PassInfo *PI = new PassInfo( "Assume Simplify", "assume-simplify" , &AssumeSimplifyPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeSimplifyPassLegacyPass>), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeAssumeSimplifyPassLegacyPassPassFlag ; void llvm::initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeSimplifyPassLegacyPassPassFlag , initializeAssumeSimplifyPassLegacyPassPassOnce, std::ref(Registry )); } | |||
603 | "Assume Simplify", false, false)PassInfo *PI = new PassInfo( "Assume Simplify", "assume-simplify" , &AssumeSimplifyPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeSimplifyPassLegacyPass>), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeAssumeSimplifyPassLegacyPassPassFlag ; void llvm::initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeSimplifyPassLegacyPassPassFlag , initializeAssumeSimplifyPassLegacyPassPassOnce, std::ref(Registry )); } | |||
604 | ||||
605 | FunctionPass *llvm::createAssumeSimplifyPass() { | |||
606 | return new AssumeSimplifyPassLegacyPass(); | |||
607 | } | |||
608 | ||||
609 | PreservedAnalyses AssumeBuilderPass::run(Function &F, | |||
610 | FunctionAnalysisManager &AM) { | |||
611 | AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F); | |||
612 | DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(F); | |||
613 | for (Instruction &I : instructions(F)) | |||
614 | salvageKnowledge(&I, AC, DT); | |||
615 | return PreservedAnalyses::all(); | |||
616 | } | |||
617 | ||||
618 | namespace { | |||
619 | class AssumeBuilderPassLegacyPass : public FunctionPass { | |||
620 | public: | |||
621 | static char ID; | |||
622 | ||||
623 | AssumeBuilderPassLegacyPass() : FunctionPass(ID) { | |||
624 | initializeAssumeBuilderPassLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
625 | } | |||
626 | bool runOnFunction(Function &F) override { | |||
627 | AssumptionCache &AC = | |||
628 | getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); | |||
629 | DominatorTreeWrapperPass *DTWP = | |||
630 | getAnalysisIfAvailable<DominatorTreeWrapperPass>(); | |||
631 | for (Instruction &I : instructions(F)) | |||
632 | salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr); | |||
633 | return true; | |||
634 | } | |||
635 | ||||
636 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
637 | AU.addRequired<AssumptionCacheTracker>(); | |||
638 | ||||
639 | AU.setPreservesAll(); | |||
640 | } | |||
641 | }; | |||
642 | } // namespace | |||
643 | ||||
644 | char AssumeBuilderPassLegacyPass::ID = 0; | |||
645 | ||||
646 | INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",static void *initializeAssumeBuilderPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
647 | "Assume Builder", false, false)static void *initializeAssumeBuilderPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
648 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
649 | INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",PassInfo *PI = new PassInfo( "Assume Builder", "assume-builder" , &AssumeBuilderPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeBuilderPassLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeAssumeBuilderPassLegacyPassPassFlag; void llvm::initializeAssumeBuilderPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeBuilderPassLegacyPassPassFlag , initializeAssumeBuilderPassLegacyPassPassOnce, std::ref(Registry )); } | |||
650 | "Assume Builder", false, false)PassInfo *PI = new PassInfo( "Assume Builder", "assume-builder" , &AssumeBuilderPassLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<AssumeBuilderPassLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeAssumeBuilderPassLegacyPassPassFlag; void llvm::initializeAssumeBuilderPassLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeAssumeBuilderPassLegacyPassPassFlag , initializeAssumeBuilderPassLegacyPassPassOnce, std::ref(Registry )); } |