File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/Alignment.h |
Warning: | line 85, column 47 The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'uint64_t' |
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 )); } |
1 | //===-- llvm/Support/Alignment.h - Useful alignment functions ---*- 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 | // This file contains types to represent alignments. | |||
10 | // They are instrumented to guarantee some invariants are preserved and prevent | |||
11 | // invalid manipulations. | |||
12 | // | |||
13 | // - Align represents an alignment in bytes, it is always set and always a valid | |||
14 | // power of two, its minimum value is 1 which means no alignment requirements. | |||
15 | // | |||
16 | // - MaybeAlign is an optional type, it may be undefined or set. When it's set | |||
17 | // you can get the underlying Align type by using the getValue() method. | |||
18 | // | |||
19 | //===----------------------------------------------------------------------===// | |||
20 | ||||
21 | #ifndef LLVM_SUPPORT_ALIGNMENT_H_ | |||
22 | #define LLVM_SUPPORT_ALIGNMENT_H_ | |||
23 | ||||
24 | #include "llvm/ADT/Optional.h" | |||
25 | #include "llvm/Support/MathExtras.h" | |||
26 | #include <cassert> | |||
27 | #ifndef NDEBUG1 | |||
28 | #include <string> | |||
29 | #endif // NDEBUG | |||
30 | ||||
31 | namespace llvm { | |||
32 | ||||
33 | #define ALIGN_CHECK_ISPOSITIVE(decl) \ | |||
34 | assert(decl > 0 && (#decl " should be defined"))((void)0) | |||
35 | ||||
36 | /// This struct is a compact representation of a valid (non-zero power of two) | |||
37 | /// alignment. | |||
38 | /// It is suitable for use as static global constants. | |||
39 | struct Align { | |||
40 | private: | |||
41 | uint8_t ShiftValue = 0; /// The log2 of the required alignment. | |||
42 | /// ShiftValue is less than 64 by construction. | |||
43 | ||||
44 | friend struct MaybeAlign; | |||
45 | friend unsigned Log2(Align); | |||
46 | friend bool operator==(Align Lhs, Align Rhs); | |||
47 | friend bool operator!=(Align Lhs, Align Rhs); | |||
48 | friend bool operator<=(Align Lhs, Align Rhs); | |||
49 | friend bool operator>=(Align Lhs, Align Rhs); | |||
50 | friend bool operator<(Align Lhs, Align Rhs); | |||
51 | friend bool operator>(Align Lhs, Align Rhs); | |||
52 | friend unsigned encode(struct MaybeAlign A); | |||
53 | friend struct MaybeAlign decodeMaybeAlign(unsigned Value); | |||
54 | ||||
55 | /// A trivial type to allow construction of constexpr Align. | |||
56 | /// This is currently needed to workaround a bug in GCC 5.3 which prevents | |||
57 | /// definition of constexpr assign operators. | |||
58 | /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic | |||
59 | /// FIXME: Remove this, make all assign operators constexpr and introduce user | |||
60 | /// defined literals when we don't have to support GCC 5.3 anymore. | |||
61 | /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain | |||
62 | struct LogValue { | |||
63 | uint8_t Log; | |||
64 | }; | |||
65 | ||||
66 | public: | |||
67 | /// Default is byte-aligned. | |||
68 | constexpr Align() = default; | |||
69 | /// Do not perform checks in case of copy/move construct/assign, because the | |||
70 | /// checks have been performed when building `Other`. | |||
71 | constexpr Align(const Align &Other) = default; | |||
72 | constexpr Align(Align &&Other) = default; | |||
73 | Align &operator=(const Align &Other) = default; | |||
74 | Align &operator=(Align &&Other) = default; | |||
75 | ||||
76 | explicit Align(uint64_t Value) { | |||
77 | assert(Value > 0 && "Value must not be 0")((void)0); | |||
78 | assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2")((void)0); | |||
79 | ShiftValue = Log2_64(Value); | |||
80 | assert(ShiftValue < 64 && "Broken invariant")((void)0); | |||
81 | } | |||
82 | ||||
83 | /// This is a hole in the type system and should not be abused. | |||
84 | /// Needed to interact with C for instance. | |||
85 | uint64_t value() const { return uint64_t(1) << ShiftValue; } | |||
| ||||
86 | ||||
87 | /// Allow constructions of constexpr Align. | |||
88 | template <size_t kValue> constexpr static LogValue Constant() { | |||
89 | return LogValue{static_cast<uint8_t>(CTLog2<kValue>())}; | |||
90 | } | |||
91 | ||||
92 | /// Allow constructions of constexpr Align from types. | |||
93 | /// Compile time equivalent to Align(alignof(T)). | |||
94 | template <typename T> constexpr static LogValue Of() { | |||
95 | return Constant<std::alignment_of<T>::value>(); | |||
96 | } | |||
97 | ||||
98 | /// Constexpr constructor from LogValue type. | |||
99 | constexpr Align(LogValue CA) : ShiftValue(CA.Log) {} | |||
100 | }; | |||
101 | ||||
102 | /// Treats the value 0 as a 1, so Align is always at least 1. | |||
103 | inline Align assumeAligned(uint64_t Value) { | |||
104 | return Value ? Align(Value) : Align(); | |||
105 | } | |||
106 | ||||
107 | /// This struct is a compact representation of a valid (power of two) or | |||
108 | /// undefined (0) alignment. | |||
109 | struct MaybeAlign : public llvm::Optional<Align> { | |||
110 | private: | |||
111 | using UP = llvm::Optional<Align>; | |||
112 | ||||
113 | public: | |||
114 | /// Default is undefined. | |||
115 | MaybeAlign() = default; | |||
116 | /// Do not perform checks in case of copy/move construct/assign, because the | |||
117 | /// checks have been performed when building `Other`. | |||
118 | MaybeAlign(const MaybeAlign &Other) = default; | |||
119 | MaybeAlign &operator=(const MaybeAlign &Other) = default; | |||
120 | MaybeAlign(MaybeAlign &&Other) = default; | |||
121 | MaybeAlign &operator=(MaybeAlign &&Other) = default; | |||
122 | ||||
123 | /// Use llvm::Optional<Align> constructor. | |||
124 | using UP::UP; | |||
125 | ||||
126 | explicit MaybeAlign(uint64_t Value) { | |||
127 | assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&((void)0) | |||
128 | "Alignment is neither 0 nor a power of 2")((void)0); | |||
129 | if (Value) | |||
130 | emplace(Value); | |||
131 | } | |||
132 | ||||
133 | /// For convenience, returns a valid alignment or 1 if undefined. | |||
134 | Align valueOrOne() const { return hasValue() ? getValue() : Align(); } | |||
135 | }; | |||
136 | ||||
137 | /// Checks that SizeInBytes is a multiple of the alignment. | |||
138 | inline bool isAligned(Align Lhs, uint64_t SizeInBytes) { | |||
139 | return SizeInBytes % Lhs.value() == 0; | |||
140 | } | |||
141 | ||||
142 | /// Checks that Addr is a multiple of the alignment. | |||
143 | inline bool isAddrAligned(Align Lhs, const void *Addr) { | |||
144 | return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr)); | |||
145 | } | |||
146 | ||||
147 | /// Returns a multiple of A needed to store `Size` bytes. | |||
148 | inline uint64_t alignTo(uint64_t Size, Align A) { | |||
149 | const uint64_t Value = A.value(); | |||
150 | // The following line is equivalent to `(Size + Value - 1) / Value * Value`. | |||
151 | ||||
152 | // The division followed by a multiplication can be thought of as a right | |||
153 | // shift followed by a left shift which zeros out the extra bits produced in | |||
154 | // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out | |||
155 | // are just zero. | |||
156 | ||||
157 | // Most compilers can generate this code but the pattern may be missed when | |||
158 | // multiple functions gets inlined. | |||
159 | return (Size + Value - 1) & ~(Value - 1U); | |||
160 | } | |||
161 | ||||
162 | /// If non-zero \p Skew is specified, the return value will be a minimal integer | |||
163 | /// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for | |||
164 | /// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p | |||
165 | /// Skew mod \p A'. | |||
166 | /// | |||
167 | /// Examples: | |||
168 | /// \code | |||
169 | /// alignTo(5, Align(8), 7) = 7 | |||
170 | /// alignTo(17, Align(8), 1) = 17 | |||
171 | /// alignTo(~0LL, Align(8), 3) = 3 | |||
172 | /// \endcode | |||
173 | inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { | |||
174 | const uint64_t Value = A.value(); | |||
175 | Skew %= Value; | |||
176 | return ((Size + Value - 1 - Skew) & ~(Value - 1U)) + Skew; | |||
177 | } | |||
178 | ||||
179 | /// Returns a multiple of A needed to store `Size` bytes. | |||
180 | /// Returns `Size` if current alignment is undefined. | |||
181 | inline uint64_t alignTo(uint64_t Size, MaybeAlign A) { | |||
182 | return A ? alignTo(Size, A.getValue()) : Size; | |||
183 | } | |||
184 | ||||
185 | /// Aligns `Addr` to `Alignment` bytes, rounding up. | |||
186 | inline uintptr_t alignAddr(const void *Addr, Align Alignment) { | |||
187 | uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr); | |||
188 | assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=((void)0) | |||
189 | ArithAddr &&((void)0) | |||
190 | "Overflow")((void)0); | |||
191 | return alignTo(ArithAddr, Alignment); | |||
192 | } | |||
193 | ||||
194 | /// Returns the offset to the next integer (mod 2**64) that is greater than | |||
195 | /// or equal to \p Value and is a multiple of \p Align. | |||
196 | inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) { | |||
197 | return alignTo(Value, Alignment) - Value; | |||
198 | } | |||
199 | ||||
200 | /// Returns the necessary adjustment for aligning `Addr` to `Alignment` | |||
201 | /// bytes, rounding up. | |||
202 | inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) { | |||
203 | return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment); | |||
204 | } | |||
205 | ||||
206 | /// Returns the log2 of the alignment. | |||
207 | inline unsigned Log2(Align A) { return A.ShiftValue; } | |||
208 | ||||
209 | /// Returns the alignment that satisfies both alignments. | |||
210 | /// Same semantic as MinAlign. | |||
211 | inline Align commonAlignment(Align A, Align B) { return std::min(A, B); } | |||
212 | ||||
213 | /// Returns the alignment that satisfies both alignments. | |||
214 | /// Same semantic as MinAlign. | |||
215 | inline Align commonAlignment(Align A, uint64_t Offset) { | |||
216 | return Align(MinAlign(A.value(), Offset)); | |||
217 | } | |||
218 | ||||
219 | /// Returns the alignment that satisfies both alignments. | |||
220 | /// Same semantic as MinAlign. | |||
221 | inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) { | |||
222 | return A && B ? commonAlignment(*A, *B) : A ? A : B; | |||
223 | } | |||
224 | ||||
225 | /// Returns the alignment that satisfies both alignments. | |||
226 | /// Same semantic as MinAlign. | |||
227 | inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) { | |||
228 | return MaybeAlign(MinAlign((*A).value(), Offset)); | |||
229 | } | |||
230 | ||||
231 | /// Returns a representation of the alignment that encodes undefined as 0. | |||
232 | inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; } | |||
233 | ||||
234 | /// Dual operation of the encode function above. | |||
235 | inline MaybeAlign decodeMaybeAlign(unsigned Value) { | |||
236 | if (Value == 0) | |||
237 | return MaybeAlign(); | |||
238 | Align Out; | |||
239 | Out.ShiftValue = Value - 1; | |||
240 | return Out; | |||
241 | } | |||
242 | ||||
243 | /// Returns a representation of the alignment, the encoded value is positive by | |||
244 | /// definition. | |||
245 | inline unsigned encode(Align A) { return encode(MaybeAlign(A)); } | |||
246 | ||||
247 | /// Comparisons between Align and scalars. Rhs must be positive. | |||
248 | inline bool operator==(Align Lhs, uint64_t Rhs) { | |||
249 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
250 | return Lhs.value() == Rhs; | |||
251 | } | |||
252 | inline bool operator!=(Align Lhs, uint64_t Rhs) { | |||
253 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
254 | return Lhs.value() != Rhs; | |||
255 | } | |||
256 | inline bool operator<=(Align Lhs, uint64_t Rhs) { | |||
257 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
258 | return Lhs.value() <= Rhs; | |||
259 | } | |||
260 | inline bool operator>=(Align Lhs, uint64_t Rhs) { | |||
261 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
262 | return Lhs.value() >= Rhs; | |||
263 | } | |||
264 | inline bool operator<(Align Lhs, uint64_t Rhs) { | |||
265 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
266 | return Lhs.value() < Rhs; | |||
267 | } | |||
268 | inline bool operator>(Align Lhs, uint64_t Rhs) { | |||
269 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
270 | return Lhs.value() > Rhs; | |||
271 | } | |||
272 | ||||
273 | /// Comparisons between MaybeAlign and scalars. | |||
274 | inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) { | |||
275 | return Lhs ? (*Lhs).value() == Rhs : Rhs == 0; | |||
276 | } | |||
277 | inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) { | |||
278 | return Lhs ? (*Lhs).value() != Rhs : Rhs != 0; | |||
279 | } | |||
280 | ||||
281 | /// Comparisons operators between Align. | |||
282 | inline bool operator==(Align Lhs, Align Rhs) { | |||
283 | return Lhs.ShiftValue == Rhs.ShiftValue; | |||
284 | } | |||
285 | inline bool operator!=(Align Lhs, Align Rhs) { | |||
286 | return Lhs.ShiftValue != Rhs.ShiftValue; | |||
287 | } | |||
288 | inline bool operator<=(Align Lhs, Align Rhs) { | |||
289 | return Lhs.ShiftValue <= Rhs.ShiftValue; | |||
290 | } | |||
291 | inline bool operator>=(Align Lhs, Align Rhs) { | |||
292 | return Lhs.ShiftValue >= Rhs.ShiftValue; | |||
293 | } | |||
294 | inline bool operator<(Align Lhs, Align Rhs) { | |||
295 | return Lhs.ShiftValue < Rhs.ShiftValue; | |||
296 | } | |||
297 | inline bool operator>(Align Lhs, Align Rhs) { | |||
298 | return Lhs.ShiftValue > Rhs.ShiftValue; | |||
299 | } | |||
300 | ||||
301 | // Don't allow relational comparisons with MaybeAlign. | |||
302 | bool operator<=(Align Lhs, MaybeAlign Rhs) = delete; | |||
303 | bool operator>=(Align Lhs, MaybeAlign Rhs) = delete; | |||
304 | bool operator<(Align Lhs, MaybeAlign Rhs) = delete; | |||
305 | bool operator>(Align Lhs, MaybeAlign Rhs) = delete; | |||
306 | ||||
307 | bool operator<=(MaybeAlign Lhs, Align Rhs) = delete; | |||
308 | bool operator>=(MaybeAlign Lhs, Align Rhs) = delete; | |||
309 | bool operator<(MaybeAlign Lhs, Align Rhs) = delete; | |||
310 | bool operator>(MaybeAlign Lhs, Align Rhs) = delete; | |||
311 | ||||
312 | bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
313 | bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
314 | bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
315 | bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
316 | ||||
317 | inline Align operator*(Align Lhs, uint64_t Rhs) { | |||
318 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
319 | return Align(Lhs.value() * Rhs); | |||
320 | } | |||
321 | ||||
322 | inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) { | |||
323 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
324 | return Lhs ? Lhs.getValue() * Rhs : MaybeAlign(); | |||
325 | } | |||
326 | ||||
327 | inline Align operator/(Align Lhs, uint64_t Divisor) { | |||
328 | assert(llvm::isPowerOf2_64(Divisor) &&((void)0) | |||
329 | "Divisor must be positive and a power of 2")((void)0); | |||
330 | assert(Lhs != 1 && "Can't halve byte alignment")((void)0); | |||
331 | return Align(Lhs.value() / Divisor); | |||
332 | } | |||
333 | ||||
334 | inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) { | |||
335 | assert(llvm::isPowerOf2_64(Divisor) &&((void)0) | |||
336 | "Divisor must be positive and a power of 2")((void)0); | |||
337 | return Lhs ? Lhs.getValue() / Divisor : MaybeAlign(); | |||
338 | } | |||
339 | ||||
340 | inline Align max(MaybeAlign Lhs, Align Rhs) { | |||
341 | return Lhs && *Lhs > Rhs ? *Lhs : Rhs; | |||
342 | } | |||
343 | ||||
344 | inline Align max(Align Lhs, MaybeAlign Rhs) { | |||
345 | return Rhs && *Rhs > Lhs ? *Rhs : Lhs; | |||
346 | } | |||
347 | ||||
348 | #ifndef NDEBUG1 | |||
349 | // For usage in LLVM_DEBUG macros. | |||
350 | inline std::string DebugStr(const Align &A) { | |||
351 | return std::to_string(A.value()); | |||
352 | } | |||
353 | // For usage in LLVM_DEBUG macros. | |||
354 | inline std::string DebugStr(const MaybeAlign &MA) { | |||
355 | if (MA) | |||
356 | return std::to_string(MA->value()); | |||
357 | return "None"; | |||
358 | } | |||
359 | #endif // NDEBUG | |||
360 | ||||
361 | #undef ALIGN_CHECK_ISPOSITIVE | |||
362 | ||||
363 | } // namespace llvm | |||
364 | ||||
365 | #endif // LLVM_SUPPORT_ALIGNMENT_H_ |