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 | |
26 | using namespace llvm; |
27 | |
28 | namespace llvm { |
29 | cl::opt<bool> ShouldPreserveAllAttributes( |
30 | "assume-preserve-all" , cl::init(Val: 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(Val: false), cl::Hidden, |
36 | cl::desc( |
37 | "enable preservation of attributes throughout code transformation" )); |
38 | } // namespace llvm |
39 | |
40 | #define DEBUG_TYPE "assume-builder" |
41 | |
42 | STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder" ); |
43 | STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built" ); |
44 | STATISTIC(NumAssumesMerged, |
45 | "Number of assume merged by the assume simplify pass" ); |
46 | STATISTIC(NumAssumesRemoved, |
47 | "Number of assume removed by the assume simplify pass" ); |
48 | |
49 | DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter" , |
50 | "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, |
71 | const DataLayout &DL) { |
72 | switch (RK.AttrKind) { |
73 | default: |
74 | return RK; |
75 | case Attribute::NonNull: |
76 | RK.WasOn = getUnderlyingObject(V: RK.WasOn); |
77 | return RK; |
78 | case Attribute::Alignment: { |
79 | Value *V = RK.WasOn->stripInBoundsOffsets(Func: [&](const Value *Strip) { |
80 | if (auto *GEP = dyn_cast<GEPOperator>(Val: Strip)) |
81 | RK.ArgValue = |
82 | MinAlign(A: RK.ArgValue, B: GEP->getMaxPreservedAlignment(DL).value()); |
83 | }); |
84 | RK.WasOn = V; |
85 | return RK; |
86 | } |
87 | case Attribute::Dereferenceable: |
88 | case Attribute::DereferenceableOrNull: { |
89 | int64_t Offset = 0; |
90 | Value *V = GetPointerBaseWithConstantOffset(Ptr: RK.WasOn, Offset, DL, |
91 | /*AllowNonInBounds*/ AllowNonInbounds: false); |
92 | if (Offset < 0) |
93 | return RK; |
94 | RK.ArgValue = RK.ArgValue + Offset; |
95 | RK.WasOn = V; |
96 | } |
97 | } |
98 | return RK; |
99 | } |
100 | |
101 | /// This class contain all knowledge that have been gather while building an |
102 | /// llvm.assume and the function to manipulate it. |
103 | struct AssumeBuilderState { |
104 | Module *M; |
105 | |
106 | using MapKey = std::pair<Value *, Attribute::AttrKind>; |
107 | SmallMapVector<MapKey, uint64_t, 8> AssumedKnowledgeMap; |
108 | Instruction *InstBeingModified = nullptr; |
109 | AssumptionCache* AC = nullptr; |
110 | DominatorTree* DT = nullptr; |
111 | |
112 | AssumeBuilderState(Module *M, Instruction *I = nullptr, |
113 | AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr) |
114 | : M(M), InstBeingModified(I), AC(AC), DT(DT) {} |
115 | |
116 | bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) { |
117 | if (!InstBeingModified || !RK.WasOn) |
118 | return false; |
119 | bool HasBeenPreserved = false; |
120 | Use* ToUpdate = nullptr; |
121 | getKnowledgeForValue( |
122 | V: RK.WasOn, AttrKinds: {RK.AttrKind}, AC, |
123 | Filter: [&](RetainedKnowledge RKOther, Instruction *Assume, |
124 | const CallInst::BundleOpInfo *Bundle) { |
125 | if (!isValidAssumeForContext(I: Assume, CxtI: InstBeingModified, DT)) |
126 | return false; |
127 | if (RKOther.ArgValue >= RK.ArgValue) { |
128 | HasBeenPreserved = true; |
129 | return true; |
130 | } else if (isValidAssumeForContext(I: InstBeingModified, CxtI: Assume, DT)) { |
131 | HasBeenPreserved = true; |
132 | IntrinsicInst *Intr = cast<IntrinsicInst>(Val: Assume); |
133 | ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument]; |
134 | return true; |
135 | } |
136 | return false; |
137 | }); |
138 | if (ToUpdate) |
139 | ToUpdate->set( |
140 | ConstantInt::get(Ty: Type::getInt64Ty(C&: M->getContext()), V: RK.ArgValue)); |
141 | return HasBeenPreserved; |
142 | } |
143 | |
144 | bool isKnowledgeWorthPreserving(RetainedKnowledge RK) { |
145 | if (!RK) |
146 | return false; |
147 | if (!RK.WasOn) |
148 | return true; |
149 | if (RK.WasOn->getType()->isPointerTy()) { |
150 | Value *UnderlyingPtr = getUnderlyingObject(V: RK.WasOn); |
151 | if (isa<AllocaInst>(Val: UnderlyingPtr) || isa<GlobalValue>(Val: UnderlyingPtr)) |
152 | return false; |
153 | } |
154 | if (auto *Arg = dyn_cast<Argument>(Val: RK.WasOn)) { |
155 | if (Arg->hasAttribute(Kind: RK.AttrKind) && |
156 | (!Attribute::isIntAttrKind(Kind: RK.AttrKind) || |
157 | Arg->getAttribute(Kind: RK.AttrKind).getValueAsInt() >= RK.ArgValue)) |
158 | return false; |
159 | return true; |
160 | } |
161 | if (auto *Inst = dyn_cast<Instruction>(Val: RK.WasOn)) |
162 | if (wouldInstructionBeTriviallyDead(I: Inst)) { |
163 | if (RK.WasOn->use_empty()) |
164 | return false; |
165 | Use *SingleUse = RK.WasOn->getSingleUndroppableUse(); |
166 | if (SingleUse && SingleUse->getUser() == InstBeingModified) |
167 | return false; |
168 | } |
169 | return true; |
170 | } |
171 | |
172 | void addKnowledge(RetainedKnowledge RK) { |
173 | RK = canonicalizedKnowledge(RK, DL: M->getDataLayout()); |
174 | |
175 | if (!isKnowledgeWorthPreserving(RK)) |
176 | return; |
177 | |
178 | if (tryToPreserveWithoutAddingAssume(RK)) |
179 | return; |
180 | MapKey Key{RK.WasOn, RK.AttrKind}; |
181 | auto Lookup = AssumedKnowledgeMap.find(Key); |
182 | if (Lookup == AssumedKnowledgeMap.end()) { |
183 | AssumedKnowledgeMap[Key] = RK.ArgValue; |
184 | return; |
185 | } |
186 | assert(((Lookup->second == 0 && RK.ArgValue == 0) || |
187 | (Lookup->second != 0 && RK.ArgValue != 0)) && |
188 | "inconsistent argument value" ); |
189 | |
190 | /// This is only desirable because for all attributes taking an argument |
191 | /// higher is better. |
192 | Lookup->second = std::max(a: Lookup->second, b: RK.ArgValue); |
193 | } |
194 | |
195 | void addAttribute(Attribute Attr, Value *WasOn) { |
196 | if (Attr.isTypeAttribute() || Attr.isStringAttribute() || |
197 | (!ShouldPreserveAllAttributes && |
198 | !isUsefullToPreserve(Kind: Attr.getKindAsEnum()))) |
199 | return; |
200 | uint64_t AttrArg = 0; |
201 | if (Attr.isIntAttribute()) |
202 | AttrArg = Attr.getValueAsInt(); |
203 | addKnowledge(RK: {.AttrKind: Attr.getKindAsEnum(), .ArgValue: AttrArg, .WasOn: WasOn}); |
204 | } |
205 | |
206 | void addCall(const CallBase *Call) { |
207 | auto addAttrList = [&](AttributeList AttrList, unsigned NumArgs) { |
208 | for (unsigned Idx = 0; Idx < NumArgs; Idx++) |
209 | for (Attribute Attr : AttrList.getParamAttrs(ArgNo: Idx)) { |
210 | bool IsPoisonAttr = Attr.hasAttribute(Val: Attribute::NonNull) || |
211 | Attr.hasAttribute(Val: Attribute::Alignment); |
212 | if (!IsPoisonAttr || Call->isPassingUndefUB(ArgNo: Idx)) |
213 | addAttribute(Attr, WasOn: Call->getArgOperand(i: Idx)); |
214 | } |
215 | for (Attribute Attr : AttrList.getFnAttrs()) |
216 | addAttribute(Attr, WasOn: nullptr); |
217 | }; |
218 | addAttrList(Call->getAttributes(), Call->arg_size()); |
219 | if (Function *Fn = Call->getCalledFunction()) |
220 | addAttrList(Fn->getAttributes(), Fn->arg_size()); |
221 | } |
222 | |
223 | AssumeInst *build() { |
224 | if (AssumedKnowledgeMap.empty()) |
225 | return nullptr; |
226 | if (!DebugCounter::shouldExecute(CounterName: BuildAssumeCounter)) |
227 | return nullptr; |
228 | Function *FnAssume = Intrinsic::getDeclaration(M, id: 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(Elt: 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(Elt: ConstantInt::get(Ty: Type::getInt64Ty(C&: M->getContext()), |
240 | V: MapElem.second)); |
241 | OpBundle.push_back(Elt: OperandBundleDefT<Value *>( |
242 | std::string(Attribute::getNameFromAttrKind(AttrKind: MapElem.first.second)), |
243 | Args)); |
244 | NumBundlesInAssumes++; |
245 | } |
246 | NumAssumeBuilt++; |
247 | return cast<AssumeInst>(Val: CallInst::Create( |
248 | Func: FnAssume, Args: ArrayRef<Value *>({ConstantInt::getTrue(Context&: C)}), Bundles: OpBundle)); |
249 | } |
250 | |
251 | void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType, |
252 | MaybeAlign MA) { |
253 | unsigned DerefSize = MemInst->getModule() |
254 | ->getDataLayout() |
255 | .getTypeStoreSize(Ty: AccType) |
256 | .getKnownMinValue(); |
257 | if (DerefSize != 0) { |
258 | addKnowledge(RK: {.AttrKind: Attribute::Dereferenceable, .ArgValue: DerefSize, .WasOn: Pointer}); |
259 | if (!NullPointerIsDefined(F: MemInst->getFunction(), |
260 | AS: Pointer->getType()->getPointerAddressSpace())) |
261 | addKnowledge(RK: {.AttrKind: Attribute::NonNull, .ArgValue: 0u, .WasOn: Pointer}); |
262 | } |
263 | if (MA.valueOrOne() > 1) |
264 | addKnowledge(RK: {.AttrKind: Attribute::Alignment, .ArgValue: MA.valueOrOne().value(), .WasOn: Pointer}); |
265 | } |
266 | |
267 | void addInstruction(Instruction *I) { |
268 | if (auto *Call = dyn_cast<CallBase>(Val: I)) |
269 | return addCall(Call); |
270 | if (auto *Load = dyn_cast<LoadInst>(Val: I)) |
271 | return addAccessedPtr(MemInst: I, Pointer: Load->getPointerOperand(), AccType: Load->getType(), |
272 | MA: Load->getAlign()); |
273 | if (auto *Store = dyn_cast<StoreInst>(Val: I)) |
274 | return addAccessedPtr(MemInst: I, Pointer: Store->getPointerOperand(), |
275 | AccType: Store->getValueOperand()->getType(), |
276 | MA: 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 | bool llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC, |
293 | DominatorTree *DT) { |
294 | if (!EnableKnowledgeRetention || I->isTerminator()) |
295 | return false; |
296 | bool Changed = false; |
297 | AssumeBuilderState Builder(I->getModule(), I, AC, DT); |
298 | Builder.addInstruction(I); |
299 | if (auto *Intr = Builder.build()) { |
300 | Intr->insertBefore(InsertPos: I); |
301 | Changed = true; |
302 | if (AC) |
303 | AC->registerAssumption(CI: Intr); |
304 | } |
305 | return Changed; |
306 | } |
307 | |
308 | AssumeInst * |
309 | llvm::buildAssumeFromKnowledge(ArrayRef<RetainedKnowledge> Knowledge, |
310 | Instruction *CtxI, AssumptionCache *AC, |
311 | DominatorTree *DT) { |
312 | AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT); |
313 | for (const RetainedKnowledge &RK : Knowledge) |
314 | Builder.addKnowledge(RK); |
315 | return Builder.build(); |
316 | } |
317 | |
318 | RetainedKnowledge llvm::simplifyRetainedKnowledge(AssumeInst *Assume, |
319 | RetainedKnowledge RK, |
320 | AssumptionCache *AC, |
321 | DominatorTree *DT) { |
322 | AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT); |
323 | RK = canonicalizedKnowledge(RK, DL: Assume->getDataLayout()); |
324 | |
325 | if (!Builder.isKnowledgeWorthPreserving(RK)) |
326 | return RetainedKnowledge::none(); |
327 | |
328 | if (Builder.tryToPreserveWithoutAddingAssume(RK)) |
329 | return RetainedKnowledge::none(); |
330 | return RK; |
331 | } |
332 | |
333 | namespace { |
334 | |
335 | struct AssumeSimplify { |
336 | Function &F; |
337 | AssumptionCache &AC; |
338 | DominatorTree *DT; |
339 | LLVMContext &C; |
340 | SmallDenseSet<IntrinsicInst *> CleanupToDo; |
341 | StringMapEntry<uint32_t> *IgnoreTag; |
342 | SmallDenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 4>, 8> BBToAssume; |
343 | bool MadeChange = false; |
344 | |
345 | AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT, |
346 | LLVMContext &C) |
347 | : F(F), AC(AC), DT(DT), C(C), |
348 | IgnoreTag(C.getOrInsertBundleTag(TagName: IgnoreBundleTag)) {} |
349 | |
350 | void buildMapping(bool FilterBooleanArgument) { |
351 | BBToAssume.clear(); |
352 | for (Value *V : AC.assumptions()) { |
353 | if (!V) |
354 | continue; |
355 | IntrinsicInst *Assume = cast<IntrinsicInst>(Val: V); |
356 | if (FilterBooleanArgument) { |
357 | auto *Arg = dyn_cast<ConstantInt>(Val: Assume->getOperand(i_nocapture: 0)); |
358 | if (!Arg || Arg->isZero()) |
359 | continue; |
360 | } |
361 | BBToAssume[Assume->getParent()].push_back(Elt: Assume); |
362 | } |
363 | |
364 | for (auto &Elem : BBToAssume) { |
365 | llvm::sort(C&: Elem.second, |
366 | Comp: [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) { |
367 | return LHS->comesBefore(Other: RHS); |
368 | }); |
369 | } |
370 | } |
371 | |
372 | /// Remove all asumes in CleanupToDo if there boolean argument is true and |
373 | /// ForceCleanup is set or the assume doesn't hold valuable knowledge. |
374 | void RunCleanup(bool ForceCleanup) { |
375 | for (IntrinsicInst *Assume : CleanupToDo) { |
376 | auto *Arg = dyn_cast<ConstantInt>(Val: Assume->getOperand(i_nocapture: 0)); |
377 | if (!Arg || Arg->isZero() || |
378 | (!ForceCleanup && |
379 | !isAssumeWithEmptyBundle(Assume: cast<AssumeInst>(Val&: *Assume)))) |
380 | continue; |
381 | MadeChange = true; |
382 | if (ForceCleanup) |
383 | NumAssumesMerged++; |
384 | else |
385 | NumAssumesRemoved++; |
386 | Assume->eraseFromParent(); |
387 | } |
388 | CleanupToDo.clear(); |
389 | } |
390 | |
391 | /// Remove knowledge stored in assume when it is already know by an attribute |
392 | /// or an other assume. This can when valid update an existing knowledge in an |
393 | /// attribute or an other assume. |
394 | void dropRedundantKnowledge() { |
395 | struct MapValue { |
396 | IntrinsicInst *Assume; |
397 | uint64_t ArgValue; |
398 | CallInst::BundleOpInfo *BOI; |
399 | }; |
400 | buildMapping(FilterBooleanArgument: false); |
401 | SmallDenseMap<std::pair<Value *, Attribute::AttrKind>, |
402 | SmallVector<MapValue, 2>, 16> |
403 | Knowledge; |
404 | for (BasicBlock *BB : depth_first(G: &F)) |
405 | for (Value *V : BBToAssume[BB]) { |
406 | if (!V) |
407 | continue; |
408 | IntrinsicInst *Assume = cast<IntrinsicInst>(Val: V); |
409 | for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) { |
410 | auto RemoveFromAssume = [&]() { |
411 | CleanupToDo.insert(V: Assume); |
412 | if (BOI.Begin != BOI.End) { |
413 | Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn]; |
414 | U->set(UndefValue::get(T: U->get()->getType())); |
415 | } |
416 | BOI.Tag = IgnoreTag; |
417 | }; |
418 | if (BOI.Tag == IgnoreTag) { |
419 | CleanupToDo.insert(V: Assume); |
420 | continue; |
421 | } |
422 | RetainedKnowledge RK = |
423 | getKnowledgeFromBundle(Assume&: cast<AssumeInst>(Val&: *Assume), BOI); |
424 | if (auto *Arg = dyn_cast_or_null<Argument>(Val: RK.WasOn)) { |
425 | bool HasSameKindAttr = Arg->hasAttribute(Kind: RK.AttrKind); |
426 | if (HasSameKindAttr) |
427 | if (!Attribute::isIntAttrKind(Kind: RK.AttrKind) || |
428 | Arg->getAttribute(Kind: RK.AttrKind).getValueAsInt() >= |
429 | RK.ArgValue) { |
430 | RemoveFromAssume(); |
431 | continue; |
432 | } |
433 | if (isValidAssumeForContext( |
434 | I: Assume, CxtI: &*F.getEntryBlock().getFirstInsertionPt()) || |
435 | Assume == &*F.getEntryBlock().getFirstInsertionPt()) { |
436 | if (HasSameKindAttr) |
437 | Arg->removeAttr(Kind: RK.AttrKind); |
438 | Arg->addAttr(Attr: Attribute::get(Context&: C, Kind: RK.AttrKind, Val: RK.ArgValue)); |
439 | MadeChange = true; |
440 | RemoveFromAssume(); |
441 | continue; |
442 | } |
443 | } |
444 | auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}]; |
445 | for (MapValue &Elem : Lookup) { |
446 | if (!isValidAssumeForContext(I: Elem.Assume, CxtI: Assume, DT)) |
447 | continue; |
448 | if (Elem.ArgValue >= RK.ArgValue) { |
449 | RemoveFromAssume(); |
450 | continue; |
451 | } else if (isValidAssumeForContext(I: Assume, CxtI: Elem.Assume, DT)) { |
452 | Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set( |
453 | ConstantInt::get(Ty: Type::getInt64Ty(C), V: RK.ArgValue)); |
454 | MadeChange = true; |
455 | RemoveFromAssume(); |
456 | continue; |
457 | } |
458 | } |
459 | Lookup.push_back(Elt: {.Assume: Assume, .ArgValue: RK.ArgValue, .BOI: &BOI}); |
460 | } |
461 | } |
462 | } |
463 | |
464 | using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator; |
465 | |
466 | /// Merge all Assumes from Begin to End in and insert the resulting assume as |
467 | /// high as possible in the basicblock. |
468 | void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) { |
469 | if (Begin == End || std::next(x: Begin) == End) |
470 | return; |
471 | /// Provide no additional information so that AssumeBuilderState doesn't |
472 | /// try to do any punning since it already has been done better. |
473 | AssumeBuilderState Builder(F.getParent()); |
474 | |
475 | /// For now it is initialized to the best value it could have |
476 | Instruction *InsertPt = BB->getFirstNonPHI(); |
477 | if (isa<LandingPadInst>(Val: InsertPt)) |
478 | InsertPt = InsertPt->getNextNode(); |
479 | for (IntrinsicInst *I : make_range(x: Begin, y: End)) { |
480 | CleanupToDo.insert(V: I); |
481 | for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) { |
482 | RetainedKnowledge RK = |
483 | getKnowledgeFromBundle(Assume&: cast<AssumeInst>(Val&: *I), BOI); |
484 | if (!RK) |
485 | continue; |
486 | Builder.addKnowledge(RK); |
487 | if (auto *I = dyn_cast_or_null<Instruction>(Val: RK.WasOn)) |
488 | if (I->getParent() == InsertPt->getParent() && |
489 | (InsertPt->comesBefore(Other: I) || InsertPt == I)) |
490 | InsertPt = I->getNextNode(); |
491 | } |
492 | } |
493 | |
494 | /// Adjust InsertPt if it is before Begin, since mergeAssumes only |
495 | /// guarantees we can place the resulting assume between Begin and End. |
496 | if (InsertPt->comesBefore(Other: *Begin)) |
497 | for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator(); |
498 | It != E; --It) |
499 | if (!isGuaranteedToTransferExecutionToSuccessor(I: &*It)) { |
500 | InsertPt = It->getNextNode(); |
501 | break; |
502 | } |
503 | auto *MergedAssume = Builder.build(); |
504 | if (!MergedAssume) |
505 | return; |
506 | MadeChange = true; |
507 | MergedAssume->insertBefore(InsertPos: InsertPt); |
508 | AC.registerAssumption(CI: MergedAssume); |
509 | } |
510 | |
511 | /// Merge assume when they are in the same BasicBlock and for all instruction |
512 | /// between them isGuaranteedToTransferExecutionToSuccessor returns true. |
513 | void mergeAssumes() { |
514 | buildMapping(FilterBooleanArgument: true); |
515 | |
516 | SmallVector<MergeIterator, 4> SplitPoints; |
517 | for (auto &Elem : BBToAssume) { |
518 | SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second; |
519 | if (AssumesInBB.size() < 2) |
520 | continue; |
521 | /// AssumesInBB is already sorted by order in the block. |
522 | |
523 | BasicBlock::iterator It = AssumesInBB.front()->getIterator(); |
524 | BasicBlock::iterator E = AssumesInBB.back()->getIterator(); |
525 | SplitPoints.push_back(Elt: AssumesInBB.begin()); |
526 | MergeIterator LastSplit = AssumesInBB.begin(); |
527 | for (; It != E; ++It) |
528 | if (!isGuaranteedToTransferExecutionToSuccessor(I: &*It)) { |
529 | for (; (*LastSplit)->comesBefore(Other: &*It); ++LastSplit) |
530 | ; |
531 | if (SplitPoints.back() != LastSplit) |
532 | SplitPoints.push_back(Elt: LastSplit); |
533 | } |
534 | SplitPoints.push_back(Elt: AssumesInBB.end()); |
535 | for (auto SplitIt = SplitPoints.begin(); |
536 | SplitIt != std::prev(x: SplitPoints.end()); SplitIt++) { |
537 | mergeRange(BB: Elem.first, Begin: *SplitIt, End: *(SplitIt + 1)); |
538 | } |
539 | SplitPoints.clear(); |
540 | } |
541 | } |
542 | }; |
543 | |
544 | bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) { |
545 | AssumeSimplify AS(F, *AC, DT, F.getContext()); |
546 | |
547 | /// Remove knowledge that is already known by a dominating other assume or an |
548 | /// attribute. |
549 | AS.dropRedundantKnowledge(); |
550 | |
551 | /// Remove assume that are empty. |
552 | AS.RunCleanup(ForceCleanup: false); |
553 | |
554 | /// Merge assume in the same basicblock when possible. |
555 | AS.mergeAssumes(); |
556 | |
557 | /// Remove assume that were merged. |
558 | AS.RunCleanup(ForceCleanup: true); |
559 | return AS.MadeChange; |
560 | } |
561 | |
562 | } // namespace |
563 | |
564 | PreservedAnalyses AssumeSimplifyPass::run(Function &F, |
565 | FunctionAnalysisManager &AM) { |
566 | if (!EnableKnowledgeRetention) |
567 | return PreservedAnalyses::all(); |
568 | if (!simplifyAssumes(F, AC: &AM.getResult<AssumptionAnalysis>(IR&: F), |
569 | DT: AM.getCachedResult<DominatorTreeAnalysis>(IR&: F))) |
570 | return PreservedAnalyses::all(); |
571 | PreservedAnalyses PA; |
572 | PA.preserveSet<CFGAnalyses>(); |
573 | return PA; |
574 | } |
575 | |
576 | PreservedAnalyses AssumeBuilderPass::run(Function &F, |
577 | FunctionAnalysisManager &AM) { |
578 | AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(IR&: F); |
579 | DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F); |
580 | bool Changed = false; |
581 | for (Instruction &I : instructions(F)) |
582 | Changed |= salvageKnowledge(I: &I, AC, DT); |
583 | if (!Changed) |
584 | PreservedAnalyses::all(); |
585 | PreservedAnalyses PA; |
586 | PA.preserveSet<CFGAnalyses>(); |
587 | return PA; |
588 | } |
589 | |