File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/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) ||((void)0) | |||
186 | (Lookup->second != 0 && RK.ArgValue != 0)) &&((void)0) | |||
187 | "inconsistent argument value")((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) { | |||
207 | for (unsigned Idx = AttributeList::FirstArgIndex; | |||
208 | Idx < AttrList.getNumAttrSets(); Idx++) | |||
209 | for (Attribute Attr : AttrList.getAttributes(Idx)) { | |||
210 | bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) || | |||
211 | Attr.hasAttribute(Attribute::Alignment); | |||
212 | if (!IsPoisonAttr || Call->isPassingUndefUB(Idx - 1)) | |||
213 | addAttribute(Attr, Call->getArgOperand(Idx - 1)); | |||
214 | } | |||
215 | for (Attribute Attr : AttrList.getFnAttributes()) | |||
216 | addAttribute(Attr, nullptr); | |||
217 | }; | |||
218 | addAttrList(Call->getAttributes()); | |||
219 | if (Function *Fn = Call->getCalledFunction()) | |||
220 | addAttrList(Fn->getAttributes()); | |||
221 | } | |||
222 | ||||
223 | AssumeInst *build() { | |||
224 | if (AssumedKnowledgeMap.empty()) | |||
225 | return nullptr; | |||
226 | if (!DebugCounter::shouldExecute(BuildAssumeCounter)) | |||
227 | return nullptr; | |||
228 | Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume); | |||
229 | LLVMContext &C = M->getContext(); | |||
230 | SmallVector<OperandBundleDef, 8> OpBundle; | |||
231 | for (auto &MapElem : AssumedKnowledgeMap) { | |||
232 | SmallVector<Value *, 2> Args; | |||
233 | if (MapElem.first.first) | |||
234 | Args.push_back(MapElem.first.first); | |||
235 | ||||
236 | /// This is only valid because for all attribute that currently exist a | |||
237 | /// value of 0 is useless. and should not be preserved. | |||
238 | if (MapElem.second) | |||
239 | Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()), | |||
240 | MapElem.second)); | |||
241 | OpBundle.push_back(OperandBundleDefT<Value *>( | |||
242 | std::string(Attribute::getNameFromAttrKind(MapElem.first.second)), | |||
243 | Args)); | |||
244 | NumBundlesInAssumes++; | |||
245 | } | |||
246 | NumAssumeBuilt++; | |||
247 | return cast<AssumeInst>(CallInst::Create( | |||
248 | FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle)); | |||
249 | } | |||
250 | ||||
251 | void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType, | |||
252 | MaybeAlign MA) { | |||
253 | unsigned DerefSize = MemInst->getModule() | |||
254 | ->getDataLayout() | |||
255 | .getTypeStoreSize(AccType) | |||
256 | .getKnownMinSize(); | |||
257 | if (DerefSize != 0) { | |||
258 | addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer}); | |||
259 | if (!NullPointerIsDefined(MemInst->getFunction(), | |||
260 | Pointer->getType()->getPointerAddressSpace())) | |||
261 | addKnowledge({Attribute::NonNull, 0u, Pointer}); | |||
262 | } | |||
263 | if (MA.valueOrOne() > 1) | |||
264 | addKnowledge( | |||
265 | {Attribute::Alignment, unsigned(MA.valueOrOne().value()), Pointer}); | |||
266 | } | |||
267 | ||||
268 | void addInstruction(Instruction *I) { | |||
269 | if (auto *Call
| |||
270 | return addCall(Call); | |||
271 | if (auto *Load
| |||
272 | return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(), | |||
273 | Load->getAlign()); | |||
274 | if (auto *Store = dyn_cast<StoreInst>(I)) | |||
275 | return addAccessedPtr(I, Store->getPointerOperand(), | |||
276 | Store->getValueOperand()->getType(), | |||
277 | Store->getAlign()); | |||
278 | // TODO: Add support for the other Instructions. | |||
279 | // TODO: Maybe we should look around and merge with other llvm.assume. | |||
280 | } | |||
281 | }; | |||
282 | ||||
283 | } // namespace | |||
284 | ||||
285 | AssumeInst *llvm::buildAssumeFromInst(Instruction *I) { | |||
286 | if (!EnableKnowledgeRetention) | |||
| ||||
287 | return nullptr; | |||
288 | AssumeBuilderState Builder(I->getModule()); | |||
289 | Builder.addInstruction(I); | |||
290 | return Builder.build(); | |||
291 | } | |||
292 | ||||
293 | void llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC, | |||
294 | DominatorTree *DT) { | |||
295 | if (!EnableKnowledgeRetention || I->isTerminator()) | |||
296 | return; | |||
297 | AssumeBuilderState Builder(I->getModule(), I, AC, DT); | |||
298 | Builder.addInstruction(I); | |||
299 | if (auto *Intr = Builder.build()) { | |||
300 | Intr->insertBefore(I); | |||
301 | if (AC) | |||
302 | AC->registerAssumption(Intr); | |||
303 | } | |||
304 | } | |||
305 | ||||
306 | AssumeInst * | |||
307 | llvm::buildAssumeFromKnowledge(ArrayRef<RetainedKnowledge> Knowledge, | |||
308 | Instruction *CtxI, AssumptionCache *AC, | |||
309 | DominatorTree *DT) { | |||
310 | AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT); | |||
311 | for (const RetainedKnowledge &RK : Knowledge) | |||
312 | Builder.addKnowledge(RK); | |||
313 | return Builder.build(); | |||
314 | } | |||
315 | ||||
316 | RetainedKnowledge llvm::simplifyRetainedKnowledge(AssumeInst *Assume, | |||
317 | RetainedKnowledge RK, | |||
318 | AssumptionCache *AC, | |||
319 | DominatorTree *DT) { | |||
320 | AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT); | |||
321 | RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout()); | |||
322 | ||||
323 | if (!Builder.isKnowledgeWorthPreserving(RK)) | |||
324 | return RetainedKnowledge::none(); | |||
325 | ||||
326 | if (Builder.tryToPreserveWithoutAddingAssume(RK)) | |||
327 | return RetainedKnowledge::none(); | |||
328 | return RK; | |||
329 | } | |||
330 | ||||
331 | namespace { | |||
332 | ||||
333 | struct AssumeSimplify { | |||
334 | Function &F; | |||
335 | AssumptionCache &AC; | |||
336 | DominatorTree *DT; | |||
337 | LLVMContext &C; | |||
338 | SmallDenseSet<IntrinsicInst *> CleanupToDo; | |||
339 | StringMapEntry<uint32_t> *IgnoreTag; | |||
340 | SmallDenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 4>, 8> BBToAssume; | |||
341 | bool MadeChange = false; | |||
342 | ||||
343 | AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT, | |||
344 | LLVMContext &C) | |||
345 | : F(F), AC(AC), DT(DT), C(C), | |||
346 | IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {} | |||
347 | ||||
348 | void buildMapping(bool FilterBooleanArgument) { | |||
349 | BBToAssume.clear(); | |||
350 | for (Value *V : AC.assumptions()) { | |||
351 | if (!V) | |||
352 | continue; | |||
353 | IntrinsicInst *Assume = cast<IntrinsicInst>(V); | |||
354 | if (FilterBooleanArgument) { | |||
355 | auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0)); | |||
356 | if (!Arg || Arg->isZero()) | |||
357 | continue; | |||
358 | } | |||
359 | BBToAssume[Assume->getParent()].push_back(Assume); | |||
360 | } | |||
361 | ||||
362 | for (auto &Elem : BBToAssume) { | |||
363 | llvm::sort(Elem.second, | |||
364 | [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) { | |||
365 | return LHS->comesBefore(RHS); | |||
366 | }); | |||
367 | } | |||
368 | } | |||
369 | ||||
370 | /// Remove all asumes in CleanupToDo if there boolean argument is true and | |||
371 | /// ForceCleanup is set or the assume doesn't hold valuable knowledge. | |||
372 | void RunCleanup(bool ForceCleanup) { | |||
373 | for (IntrinsicInst *Assume : CleanupToDo) { | |||
374 | auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0)); | |||
375 | if (!Arg || Arg->isZero() || | |||
376 | (!ForceCleanup && | |||
377 | !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume)))) | |||
378 | continue; | |||
379 | MadeChange = true; | |||
380 | if (ForceCleanup) | |||
381 | NumAssumesMerged++; | |||
382 | else | |||
383 | NumAssumesRemoved++; | |||
384 | Assume->eraseFromParent(); | |||
385 | } | |||
386 | CleanupToDo.clear(); | |||
387 | } | |||
388 | ||||
389 | /// Remove knowledge stored in assume when it is already know by an attribute | |||
390 | /// or an other assume. This can when valid update an existing knowledge in an | |||
391 | /// attribute or an other assume. | |||
392 | void dropRedundantKnowledge() { | |||
393 | struct MapValue { | |||
394 | IntrinsicInst *Assume; | |||
395 | unsigned ArgValue; | |||
396 | CallInst::BundleOpInfo *BOI; | |||
397 | }; | |||
398 | buildMapping(false); | |||
399 | SmallDenseMap<std::pair<Value *, Attribute::AttrKind>, | |||
400 | SmallVector<MapValue, 2>, 16> | |||
401 | Knowledge; | |||
402 | for (BasicBlock *BB : depth_first(&F)) | |||
403 | for (Value *V : BBToAssume[BB]) { | |||
404 | if (!V) | |||
405 | continue; | |||
406 | IntrinsicInst *Assume = cast<IntrinsicInst>(V); | |||
407 | for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) { | |||
408 | auto RemoveFromAssume = [&]() { | |||
409 | CleanupToDo.insert(Assume); | |||
410 | if (BOI.Begin != BOI.End) { | |||
411 | Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn]; | |||
412 | U->set(UndefValue::get(U->get()->getType())); | |||
413 | } | |||
414 | BOI.Tag = IgnoreTag; | |||
415 | }; | |||
416 | if (BOI.Tag == IgnoreTag) { | |||
417 | CleanupToDo.insert(Assume); | |||
418 | continue; | |||
419 | } | |||
420 | RetainedKnowledge RK = | |||
421 | getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI); | |||
422 | if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) { | |||
423 | bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind); | |||
424 | if (HasSameKindAttr) | |||
425 | if (!Attribute::isIntAttrKind(RK.AttrKind) || | |||
426 | Arg->getAttribute(RK.AttrKind).getValueAsInt() >= | |||
427 | RK.ArgValue) { | |||
428 | RemoveFromAssume(); | |||
429 | continue; | |||
430 | } | |||
431 | if (isValidAssumeForContext( | |||
432 | Assume, &*F.getEntryBlock().getFirstInsertionPt()) || | |||
433 | Assume == &*F.getEntryBlock().getFirstInsertionPt()) { | |||
434 | if (HasSameKindAttr) | |||
435 | Arg->removeAttr(RK.AttrKind); | |||
436 | Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue)); | |||
437 | MadeChange = true; | |||
438 | RemoveFromAssume(); | |||
439 | continue; | |||
440 | } | |||
441 | } | |||
442 | auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}]; | |||
443 | for (MapValue &Elem : Lookup) { | |||
444 | if (!isValidAssumeForContext(Elem.Assume, Assume, DT)) | |||
445 | continue; | |||
446 | if (Elem.ArgValue >= RK.ArgValue) { | |||
447 | RemoveFromAssume(); | |||
448 | continue; | |||
449 | } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) { | |||
450 | Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set( | |||
451 | ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue)); | |||
452 | MadeChange = true; | |||
453 | RemoveFromAssume(); | |||
454 | continue; | |||
455 | } | |||
456 | } | |||
457 | Lookup.push_back({Assume, RK.ArgValue, &BOI}); | |||
458 | } | |||
459 | } | |||
460 | } | |||
461 | ||||
462 | using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator; | |||
463 | ||||
464 | /// Merge all Assumes from Begin to End in and insert the resulting assume as | |||
465 | /// high as possible in the basicblock. | |||
466 | void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) { | |||
467 | if (Begin == End || std::next(Begin) == End) | |||
468 | return; | |||
469 | /// Provide no additional information so that AssumeBuilderState doesn't | |||
470 | /// try to do any punning since it already has been done better. | |||
471 | AssumeBuilderState Builder(F.getParent()); | |||
472 | ||||
473 | /// For now it is initialized to the best value it could have | |||
474 | Instruction *InsertPt = BB->getFirstNonPHI(); | |||
475 | if (isa<LandingPadInst>(InsertPt)) | |||
476 | InsertPt = InsertPt->getNextNode(); | |||
477 | for (IntrinsicInst *I : make_range(Begin, End)) { | |||
478 | CleanupToDo.insert(I); | |||
479 | for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) { | |||
480 | RetainedKnowledge RK = | |||
481 | getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI); | |||
482 | if (!RK) | |||
483 | continue; | |||
484 | Builder.addKnowledge(RK); | |||
485 | if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn)) | |||
486 | if (I->getParent() == InsertPt->getParent() && | |||
487 | (InsertPt->comesBefore(I) || InsertPt == I)) | |||
488 | InsertPt = I->getNextNode(); | |||
489 | } | |||
490 | } | |||
491 | ||||
492 | /// Adjust InsertPt if it is before Begin, since mergeAssumes only | |||
493 | /// guarantees we can place the resulting assume between Begin and End. | |||
494 | if (InsertPt->comesBefore(*Begin)) | |||
495 | for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator(); | |||
496 | It != E; --It) | |||
497 | if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) { | |||
498 | InsertPt = It->getNextNode(); | |||
499 | break; | |||
500 | } | |||
501 | auto *MergedAssume = Builder.build(); | |||
502 | if (!MergedAssume) | |||
503 | return; | |||
504 | MadeChange = true; | |||
505 | MergedAssume->insertBefore(InsertPt); | |||
506 | AC.registerAssumption(MergedAssume); | |||
507 | } | |||
508 | ||||
509 | /// Merge assume when they are in the same BasicBlock and for all instruction | |||
510 | /// between them isGuaranteedToTransferExecutionToSuccessor returns true. | |||
511 | void mergeAssumes() { | |||
512 | buildMapping(true); | |||
513 | ||||
514 | SmallVector<MergeIterator, 4> SplitPoints; | |||
515 | for (auto &Elem : BBToAssume) { | |||
516 | SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second; | |||
517 | if (AssumesInBB.size() < 2) | |||
518 | continue; | |||
519 | /// AssumesInBB is already sorted by order in the block. | |||
520 | ||||
521 | BasicBlock::iterator It = AssumesInBB.front()->getIterator(); | |||
522 | BasicBlock::iterator E = AssumesInBB.back()->getIterator(); | |||
523 | SplitPoints.push_back(AssumesInBB.begin()); | |||
524 | MergeIterator LastSplit = AssumesInBB.begin(); | |||
525 | for (; It != E; ++It) | |||
526 | if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) { | |||
527 | for (; (*LastSplit)->comesBefore(&*It); ++LastSplit) | |||
528 | ; | |||
529 | if (SplitPoints.back() != LastSplit) | |||
530 | SplitPoints.push_back(LastSplit); | |||
531 | } | |||
532 | SplitPoints.push_back(AssumesInBB.end()); | |||
533 | for (auto SplitIt = SplitPoints.begin(); | |||
534 | SplitIt != std::prev(SplitPoints.end()); SplitIt++) { | |||
535 | mergeRange(Elem.first, *SplitIt, *(SplitIt + 1)); | |||
536 | } | |||
537 | SplitPoints.clear(); | |||
538 | } | |||
539 | } | |||
540 | }; | |||
541 | ||||
542 | bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) { | |||
543 | AssumeSimplify AS(F, *AC, DT, F.getContext()); | |||
544 | ||||
545 | /// Remove knowledge that is already known by a dominating other assume or an | |||
546 | /// attribute. | |||
547 | AS.dropRedundantKnowledge(); | |||
548 | ||||
549 | /// Remove assume that are empty. | |||
550 | AS.RunCleanup(false); | |||
551 | ||||
552 | /// Merge assume in the same basicblock when possible. | |||
553 | AS.mergeAssumes(); | |||
554 | ||||
555 | /// Remove assume that were merged. | |||
556 | AS.RunCleanup(true); | |||
557 | return AS.MadeChange; | |||
558 | } | |||
559 | ||||
560 | } // namespace | |||
561 | ||||
562 | PreservedAnalyses AssumeSimplifyPass::run(Function &F, | |||
563 | FunctionAnalysisManager &AM) { | |||
564 | if (!EnableKnowledgeRetention) | |||
565 | return PreservedAnalyses::all(); | |||
566 | simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F), | |||
567 | AM.getCachedResult<DominatorTreeAnalysis>(F)); | |||
568 | return PreservedAnalyses::all(); | |||
569 | } | |||
570 | ||||
571 | namespace { | |||
572 | class AssumeSimplifyPassLegacyPass : public FunctionPass { | |||
573 | public: | |||
574 | static char ID; | |||
575 | ||||
576 | AssumeSimplifyPassLegacyPass() : FunctionPass(ID) { | |||
577 | initializeAssumeSimplifyPassLegacyPassPass( | |||
578 | *PassRegistry::getPassRegistry()); | |||
579 | } | |||
580 | bool runOnFunction(Function &F) override { | |||
581 | if (skipFunction(F) || !EnableKnowledgeRetention) | |||
582 | return false; | |||
583 | AssumptionCache &AC = | |||
584 | getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); | |||
585 | DominatorTreeWrapperPass *DTWP = | |||
586 | getAnalysisIfAvailable<DominatorTreeWrapperPass>(); | |||
587 | return simplifyAssumes(F, &AC, DTWP ? &DTWP->getDomTree() : nullptr); | |||
588 | } | |||
589 | ||||
590 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
591 | AU.addRequired<AssumptionCacheTracker>(); | |||
592 | ||||
593 | AU.setPreservesAll(); | |||
594 | } | |||
595 | }; | |||
596 | } // namespace | |||
597 | ||||
598 | char AssumeSimplifyPassLegacyPass::ID = 0; | |||
599 | ||||
600 | INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",static void *initializeAssumeSimplifyPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
601 | "Assume Simplify", false, false)static void *initializeAssumeSimplifyPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
602 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
603 | 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 )); } | |||
604 | "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 )); } | |||
605 | ||||
606 | FunctionPass *llvm::createAssumeSimplifyPass() { | |||
607 | return new AssumeSimplifyPassLegacyPass(); | |||
608 | } | |||
609 | ||||
610 | PreservedAnalyses AssumeBuilderPass::run(Function &F, | |||
611 | FunctionAnalysisManager &AM) { | |||
612 | AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F); | |||
613 | DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(F); | |||
614 | for (Instruction &I : instructions(F)) | |||
615 | salvageKnowledge(&I, AC, DT); | |||
616 | return PreservedAnalyses::all(); | |||
617 | } | |||
618 | ||||
619 | namespace { | |||
620 | class AssumeBuilderPassLegacyPass : public FunctionPass { | |||
621 | public: | |||
622 | static char ID; | |||
623 | ||||
624 | AssumeBuilderPassLegacyPass() : FunctionPass(ID) { | |||
625 | initializeAssumeBuilderPassLegacyPassPass(*PassRegistry::getPassRegistry()); | |||
626 | } | |||
627 | bool runOnFunction(Function &F) override { | |||
628 | AssumptionCache &AC = | |||
629 | getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); | |||
630 | DominatorTreeWrapperPass *DTWP = | |||
631 | getAnalysisIfAvailable<DominatorTreeWrapperPass>(); | |||
632 | for (Instruction &I : instructions(F)) | |||
633 | salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr); | |||
634 | return true; | |||
635 | } | |||
636 | ||||
637 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
638 | AU.addRequired<AssumptionCacheTracker>(); | |||
639 | ||||
640 | AU.setPreservesAll(); | |||
641 | } | |||
642 | }; | |||
643 | } // namespace | |||
644 | ||||
645 | char AssumeBuilderPassLegacyPass::ID = 0; | |||
646 | ||||
647 | INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",static void *initializeAssumeBuilderPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
648 | "Assume Builder", false, false)static void *initializeAssumeBuilderPassLegacyPassPassOnce(PassRegistry &Registry) { | |||
649 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
650 | 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 )); } | |||
651 | "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 )); } |