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 | //===- CSEInfo.cpp ------------------------------===// | |||
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 | // | |||
10 | //===----------------------------------------------------------------------===// | |||
11 | #include "llvm/CodeGen/GlobalISel/CSEInfo.h" | |||
12 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
13 | #include "llvm/InitializePasses.h" | |||
14 | #include "llvm/Support/Error.h" | |||
15 | ||||
16 | #define DEBUG_TYPE"cseinfo" "cseinfo" | |||
17 | ||||
18 | using namespace llvm; | |||
19 | char llvm::GISelCSEAnalysisWrapperPass::ID = 0; | |||
20 | GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass() | |||
21 | : MachineFunctionPass(ID) { | |||
22 | initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry()); | |||
23 | } | |||
24 | INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,static void *initializeGISelCSEAnalysisWrapperPassPassOnce(PassRegistry &Registry) { | |||
25 | "Analysis containing CSE Info", false, true)static void *initializeGISelCSEAnalysisWrapperPassPassOnce(PassRegistry &Registry) { | |||
26 | INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Analysis containing CSE Info", "cseinfo" , &GISelCSEAnalysisWrapperPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<GISelCSEAnalysisWrapperPass>), false, true ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeGISelCSEAnalysisWrapperPassPassFlag; void llvm::initializeGISelCSEAnalysisWrapperPassPass(PassRegistry &Registry) { llvm::call_once(InitializeGISelCSEAnalysisWrapperPassPassFlag , initializeGISelCSEAnalysisWrapperPassPassOnce, std::ref(Registry )); } | |||
27 | "Analysis containing CSE Info", false, true)PassInfo *PI = new PassInfo( "Analysis containing CSE Info", "cseinfo" , &GISelCSEAnalysisWrapperPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<GISelCSEAnalysisWrapperPass>), false, true ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeGISelCSEAnalysisWrapperPassPassFlag; void llvm::initializeGISelCSEAnalysisWrapperPassPass(PassRegistry &Registry) { llvm::call_once(InitializeGISelCSEAnalysisWrapperPassPassFlag , initializeGISelCSEAnalysisWrapperPassPassOnce, std::ref(Registry )); } | |||
28 | ||||
29 | /// -------- UniqueMachineInstr -------------// | |||
30 | ||||
31 | void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) { | |||
32 | GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI); | |||
33 | } | |||
34 | /// ----------------------------------------- | |||
35 | ||||
36 | /// --------- CSEConfigFull ---------- /// | |||
37 | bool CSEConfigFull::shouldCSEOpc(unsigned Opc) { | |||
38 | switch (Opc) { | |||
39 | default: | |||
40 | break; | |||
41 | case TargetOpcode::G_ADD: | |||
42 | case TargetOpcode::G_AND: | |||
43 | case TargetOpcode::G_ASHR: | |||
44 | case TargetOpcode::G_LSHR: | |||
45 | case TargetOpcode::G_MUL: | |||
46 | case TargetOpcode::G_OR: | |||
47 | case TargetOpcode::G_SHL: | |||
48 | case TargetOpcode::G_SUB: | |||
49 | case TargetOpcode::G_XOR: | |||
50 | case TargetOpcode::G_UDIV: | |||
51 | case TargetOpcode::G_SDIV: | |||
52 | case TargetOpcode::G_UREM: | |||
53 | case TargetOpcode::G_SREM: | |||
54 | case TargetOpcode::G_CONSTANT: | |||
55 | case TargetOpcode::G_FCONSTANT: | |||
56 | case TargetOpcode::G_IMPLICIT_DEF: | |||
57 | case TargetOpcode::G_ZEXT: | |||
58 | case TargetOpcode::G_SEXT: | |||
59 | case TargetOpcode::G_ANYEXT: | |||
60 | case TargetOpcode::G_UNMERGE_VALUES: | |||
61 | case TargetOpcode::G_TRUNC: | |||
62 | case TargetOpcode::G_PTR_ADD: | |||
63 | case TargetOpcode::G_EXTRACT: | |||
64 | return true; | |||
65 | } | |||
66 | return false; | |||
67 | } | |||
68 | ||||
69 | bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) { | |||
70 | return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_IMPLICIT_DEF; | |||
71 | } | |||
72 | ||||
73 | std::unique_ptr<CSEConfigBase> | |||
74 | llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) { | |||
75 | std::unique_ptr<CSEConfigBase> Config; | |||
76 | if (Level == CodeGenOpt::None) | |||
77 | Config = std::make_unique<CSEConfigConstantOnly>(); | |||
78 | else | |||
79 | Config = std::make_unique<CSEConfigFull>(); | |||
80 | return Config; | |||
81 | } | |||
82 | ||||
83 | /// ----------------------------------------- | |||
84 | ||||
85 | /// -------- GISelCSEInfo -------------// | |||
86 | void GISelCSEInfo::setMF(MachineFunction &MF) { | |||
87 | this->MF = &MF; | |||
88 | this->MRI = &MF.getRegInfo(); | |||
89 | } | |||
90 | ||||
91 | GISelCSEInfo::~GISelCSEInfo() {} | |||
92 | ||||
93 | bool GISelCSEInfo::isUniqueMachineInstValid( | |||
94 | const UniqueMachineInstr &UMI) const { | |||
95 | // Should we check here and assert that the instruction has been fully | |||
96 | // constructed? | |||
97 | // FIXME: Any other checks required to be done here? Remove this method if | |||
98 | // none. | |||
99 | return true; | |||
100 | } | |||
101 | ||||
102 | void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) { | |||
103 | bool Removed = CSEMap.RemoveNode(UMI); | |||
104 | (void)Removed; | |||
105 | assert(Removed && "Invalidation called on invalid UMI")((void)0); | |||
106 | // FIXME: Should UMI be deallocated/destroyed? | |||
107 | } | |||
108 | ||||
109 | UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID, | |||
110 | MachineBasicBlock *MBB, | |||
111 | void *&InsertPos) { | |||
112 | auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos); | |||
113 | if (Node) { | |||
114 | if (!isUniqueMachineInstValid(*Node)) { | |||
115 | invalidateUniqueMachineInstr(Node); | |||
116 | return nullptr; | |||
117 | } | |||
118 | ||||
119 | if (Node->MI->getParent() != MBB) | |||
120 | return nullptr; | |||
121 | } | |||
122 | return Node; | |||
123 | } | |||
124 | ||||
125 | void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) { | |||
126 | handleRecordedInsts(); | |||
127 | assert(UMI)((void)0); | |||
128 | UniqueMachineInstr *MaybeNewNode = UMI; | |||
129 | if (InsertPos) | |||
130 | CSEMap.InsertNode(UMI, InsertPos); | |||
131 | else | |||
132 | MaybeNewNode = CSEMap.GetOrInsertNode(UMI); | |||
133 | if (MaybeNewNode != UMI) { | |||
134 | // A similar node exists in the folding set. Let's ignore this one. | |||
135 | return; | |||
136 | } | |||
137 | assert(InstrMapping.count(UMI->MI) == 0 &&((void)0) | |||
138 | "This instruction should not be in the map")((void)0); | |||
139 | InstrMapping[UMI->MI] = MaybeNewNode; | |||
140 | } | |||
141 | ||||
142 | UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) { | |||
143 | assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node")((void)0); | |||
144 | auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI); | |||
145 | return Node; | |||
146 | } | |||
147 | ||||
148 | void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) { | |||
149 | assert(MI)((void)0); | |||
150 | // If it exists in temporary insts, remove it. | |||
151 | TemporaryInsts.remove(MI); | |||
152 | auto *Node = getUniqueInstrForMI(MI); | |||
153 | insertNode(Node, InsertPos); | |||
154 | } | |||
155 | ||||
156 | MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID, | |||
157 | MachineBasicBlock *MBB, | |||
158 | void *&InsertPos) { | |||
159 | handleRecordedInsts(); | |||
160 | if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) { | |||
161 | LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;)do { } while (false); | |||
162 | return const_cast<MachineInstr *>(Inst->MI); | |||
163 | } | |||
164 | return nullptr; | |||
165 | } | |||
166 | ||||
167 | void GISelCSEInfo::countOpcodeHit(unsigned Opc) { | |||
168 | #ifndef NDEBUG1 | |||
169 | if (OpcodeHitTable.count(Opc)) | |||
170 | OpcodeHitTable[Opc] += 1; | |||
171 | else | |||
172 | OpcodeHitTable[Opc] = 1; | |||
173 | #endif | |||
174 | // Else do nothing. | |||
175 | } | |||
176 | ||||
177 | void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) { | |||
178 | if (shouldCSE(MI->getOpcode())) { | |||
179 | TemporaryInsts.insert(MI); | |||
180 | LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI)do { } while (false); | |||
181 | } | |||
182 | } | |||
183 | ||||
184 | void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) { | |||
185 | assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE")((void)0); | |||
186 | auto *UMI = InstrMapping.lookup(MI); | |||
187 | LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI)do { } while (false); | |||
188 | if (UMI) { | |||
189 | // Invalidate this MI. | |||
190 | invalidateUniqueMachineInstr(UMI); | |||
191 | InstrMapping.erase(MI); | |||
192 | } | |||
193 | /// Now insert the new instruction. | |||
194 | if (UMI) { | |||
195 | /// We'll reuse the same UniqueMachineInstr to avoid the new | |||
196 | /// allocation. | |||
197 | *UMI = UniqueMachineInstr(MI); | |||
198 | insertNode(UMI, nullptr); | |||
199 | } else { | |||
200 | /// This is a new instruction. Allocate a new UniqueMachineInstr and | |||
201 | /// Insert. | |||
202 | insertInstr(MI); | |||
203 | } | |||
204 | } | |||
205 | ||||
206 | void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) { | |||
207 | if (auto *UMI = InstrMapping.lookup(MI)) { | |||
208 | invalidateUniqueMachineInstr(UMI); | |||
209 | InstrMapping.erase(MI); | |||
210 | } | |||
211 | TemporaryInsts.remove(MI); | |||
212 | } | |||
213 | ||||
214 | void GISelCSEInfo::handleRecordedInsts() { | |||
215 | while (!TemporaryInsts.empty()) { | |||
216 | auto *MI = TemporaryInsts.pop_back_val(); | |||
217 | handleRecordedInst(MI); | |||
218 | } | |||
219 | } | |||
220 | ||||
221 | bool GISelCSEInfo::shouldCSE(unsigned Opc) const { | |||
222 | assert(CSEOpt.get() && "CSEConfig not set")((void)0); | |||
223 | return CSEOpt->shouldCSEOpc(Opc); | |||
224 | } | |||
225 | ||||
226 | void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); } | |||
227 | void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); } | |||
228 | void GISelCSEInfo::changingInstr(MachineInstr &MI) { | |||
229 | // For now, perform erase, followed by insert. | |||
230 | erasingInstr(MI); | |||
231 | createdInstr(MI); | |||
232 | } | |||
233 | void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); } | |||
234 | ||||
235 | void GISelCSEInfo::analyze(MachineFunction &MF) { | |||
236 | setMF(MF); | |||
237 | for (auto &MBB : MF) { | |||
238 | if (MBB.empty()) | |||
239 | continue; | |||
240 | for (MachineInstr &MI : MBB) { | |||
241 | if (!shouldCSE(MI.getOpcode())) | |||
242 | continue; | |||
243 | LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI)do { } while (false); | |||
244 | insertInstr(&MI); | |||
245 | } | |||
246 | } | |||
247 | } | |||
248 | ||||
249 | void GISelCSEInfo::releaseMemory() { | |||
250 | print(); | |||
251 | CSEMap.clear(); | |||
252 | InstrMapping.clear(); | |||
253 | UniqueInstrAllocator.Reset(); | |||
254 | TemporaryInsts.clear(); | |||
255 | CSEOpt.reset(); | |||
256 | MRI = nullptr; | |||
257 | MF = nullptr; | |||
258 | #ifndef NDEBUG1 | |||
259 | OpcodeHitTable.clear(); | |||
260 | #endif | |||
261 | } | |||
262 | ||||
263 | #ifndef NDEBUG1 | |||
264 | static const char *stringify(const MachineInstr *MI, std::string &S) { | |||
265 | raw_string_ostream OS(S); | |||
266 | OS << *MI; | |||
267 | return OS.str().c_str(); | |||
268 | } | |||
269 | #endif | |||
270 | ||||
271 | Error GISelCSEInfo::verify() { | |||
272 | #ifndef NDEBUG1 | |||
273 | std::string S1, S2; | |||
274 | handleRecordedInsts(); | |||
275 | // For each instruction in map from MI -> UMI, | |||
276 | // Profile(MI) and make sure UMI is found for that profile. | |||
277 | for (auto &It : InstrMapping) { | |||
278 | FoldingSetNodeID TmpID; | |||
279 | GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first); | |||
280 | void *InsertPos; | |||
281 | UniqueMachineInstr *FoundNode = | |||
282 | CSEMap.FindNodeOrInsertPos(TmpID, InsertPos); | |||
283 | if (FoundNode != It.second) | |||
284 | return createStringError(std::errc::not_supported, | |||
285 | "CSEMap mismatch, InstrMapping has MIs without " | |||
286 | "corresponding Nodes in CSEMap:\n%s", | |||
287 | stringify(It.second->MI, S1)); | |||
288 | } | |||
289 | ||||
290 | // For every node in the CSEMap, make sure that the InstrMapping | |||
291 | // points to it. | |||
292 | for (const UniqueMachineInstr &UMI : CSEMap) { | |||
293 | if (!InstrMapping.count(UMI.MI)) | |||
294 | return createStringError(std::errc::not_supported, | |||
295 | "Node in CSE without InstrMapping:\n%s", | |||
296 | stringify(UMI.MI, S1)); | |||
297 | ||||
298 | if (InstrMapping[UMI.MI] != &UMI) | |||
299 | return createStringError(std::make_error_code(std::errc::not_supported), | |||
300 | "Mismatch in CSE mapping:\n%s\n%s", | |||
301 | stringify(InstrMapping[UMI.MI]->MI, S1), | |||
302 | stringify(UMI.MI, S2)); | |||
303 | } | |||
304 | #endif | |||
305 | return Error::success(); | |||
306 | } | |||
307 | ||||
308 | void GISelCSEInfo::print() { | |||
309 | LLVM_DEBUG(for (auto &Itdo { } while (false) | |||
310 | : OpcodeHitTable) {do { } while (false) | |||
311 | dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.seconddo { } while (false) | |||
312 | << "\n";do { } while (false) | |||
313 | };)do { } while (false); | |||
314 | } | |||
315 | /// ----------------------------------------- | |||
316 | // ---- Profiling methods for FoldingSetNode --- // | |||
317 | const GISelInstProfileBuilder & | |||
318 | GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const { | |||
319 | addNodeIDMBB(MI->getParent()); | |||
320 | addNodeIDOpcode(MI->getOpcode()); | |||
321 | for (auto &Op : MI->operands()) | |||
322 | addNodeIDMachineOperand(Op); | |||
323 | addNodeIDFlag(MI->getFlags()); | |||
324 | return *this; | |||
325 | } | |||
326 | ||||
327 | const GISelInstProfileBuilder & | |||
328 | GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const { | |||
329 | ID.AddInteger(Opc); | |||
330 | return *this; | |||
331 | } | |||
332 | ||||
333 | const GISelInstProfileBuilder & | |||
334 | GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const { | |||
335 | uint64_t Val = Ty.getUniqueRAWLLTData(); | |||
336 | ID.AddInteger(Val); | |||
337 | return *this; | |||
338 | } | |||
339 | ||||
340 | const GISelInstProfileBuilder & | |||
341 | GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const { | |||
342 | ID.AddPointer(RC); | |||
343 | return *this; | |||
344 | } | |||
345 | ||||
346 | const GISelInstProfileBuilder & | |||
347 | GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const { | |||
348 | ID.AddPointer(RB); | |||
349 | return *this; | |||
350 | } | |||
351 | ||||
352 | const GISelInstProfileBuilder & | |||
353 | GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const { | |||
354 | ID.AddInteger(Imm); | |||
355 | return *this; | |||
356 | } | |||
357 | ||||
358 | const GISelInstProfileBuilder & | |||
359 | GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const { | |||
360 | ID.AddInteger(Reg); | |||
361 | return *this; | |||
362 | } | |||
363 | ||||
364 | const GISelInstProfileBuilder & | |||
365 | GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const { | |||
366 | addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false)); | |||
367 | return *this; | |||
368 | } | |||
369 | ||||
370 | const GISelInstProfileBuilder & | |||
371 | GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const { | |||
372 | ID.AddPointer(MBB); | |||
373 | return *this; | |||
374 | } | |||
375 | ||||
376 | const GISelInstProfileBuilder & | |||
377 | GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const { | |||
378 | if (Flag) | |||
379 | ID.AddInteger(Flag); | |||
380 | return *this; | |||
381 | } | |||
382 | ||||
383 | const GISelInstProfileBuilder & | |||
384 | GISelInstProfileBuilder::addNodeIDReg(Register Reg) const { | |||
385 | LLT Ty = MRI.getType(Reg); | |||
386 | if (Ty.isValid()) | |||
387 | addNodeIDRegType(Ty); | |||
388 | ||||
389 | if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) { | |||
390 | if (const auto *RB = RCOrRB.dyn_cast<const RegisterBank *>()) | |||
391 | addNodeIDRegType(RB); | |||
392 | else if (const auto *RC = RCOrRB.dyn_cast<const TargetRegisterClass *>()) | |||
393 | addNodeIDRegType(RC); | |||
394 | } | |||
395 | return *this; | |||
396 | } | |||
397 | ||||
398 | const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand( | |||
399 | const MachineOperand &MO) const { | |||
400 | if (MO.isReg()) { | |||
401 | Register Reg = MO.getReg(); | |||
402 | if (!MO.isDef()) | |||
403 | addNodeIDRegNum(Reg); | |||
404 | ||||
405 | // Profile the register properties. | |||
406 | addNodeIDReg(Reg); | |||
407 | assert(!MO.isImplicit() && "Unhandled case")((void)0); | |||
408 | } else if (MO.isImm()) | |||
409 | ID.AddInteger(MO.getImm()); | |||
410 | else if (MO.isCImm()) | |||
411 | ID.AddPointer(MO.getCImm()); | |||
412 | else if (MO.isFPImm()) | |||
413 | ID.AddPointer(MO.getFPImm()); | |||
414 | else if (MO.isPredicate()) | |||
415 | ID.AddInteger(MO.getPredicate()); | |||
416 | else | |||
417 | llvm_unreachable("Unhandled operand type")__builtin_unreachable(); | |||
418 | // Handle other types | |||
419 | return *this; | |||
420 | } | |||
421 | ||||
422 | GISelCSEInfo & | |||
423 | GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt, | |||
424 | bool Recompute) { | |||
425 | if (!AlreadyComputed || Recompute) { | |||
| ||||
426 | Info.releaseMemory(); | |||
427 | Info.setCSEConfig(std::move(CSEOpt)); | |||
428 | Info.analyze(*MF); | |||
429 | AlreadyComputed = true; | |||
430 | } | |||
431 | return Info; | |||
432 | } | |||
433 | void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { | |||
434 | AU.setPreservesAll(); | |||
435 | MachineFunctionPass::getAnalysisUsage(AU); | |||
436 | } | |||
437 | ||||
438 | bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) { | |||
439 | releaseMemory(); | |||
440 | Wrapper.setMF(MF); | |||
441 | return false; | |||
442 | } |
1 | //===- Allocator.h - Simple memory allocation abstraction -------*- 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 | /// \file |
9 | /// |
10 | /// This file defines the BumpPtrAllocator interface. BumpPtrAllocator conforms |
11 | /// to the LLVM "Allocator" concept and is similar to MallocAllocator, but |
12 | /// objects cannot be deallocated. Their lifetime is tied to the lifetime of the |
13 | /// allocator. |
14 | /// |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_SUPPORT_ALLOCATOR_H |
18 | #define LLVM_SUPPORT_ALLOCATOR_H |
19 | |
20 | #include "llvm/ADT/Optional.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include "llvm/Support/Alignment.h" |
23 | #include "llvm/Support/AllocatorBase.h" |
24 | #include "llvm/Support/Compiler.h" |
25 | #include "llvm/Support/ErrorHandling.h" |
26 | #include "llvm/Support/MathExtras.h" |
27 | #include "llvm/Support/MemAlloc.h" |
28 | #include <algorithm> |
29 | #include <cassert> |
30 | #include <cstddef> |
31 | #include <cstdint> |
32 | #include <cstdlib> |
33 | #include <iterator> |
34 | #include <type_traits> |
35 | #include <utility> |
36 | |
37 | namespace llvm { |
38 | |
39 | namespace detail { |
40 | |
41 | // We call out to an external function to actually print the message as the |
42 | // printing code uses Allocator.h in its implementation. |
43 | void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated, |
44 | size_t TotalMemory); |
45 | |
46 | } // end namespace detail |
47 | |
48 | /// Allocate memory in an ever growing pool, as if by bump-pointer. |
49 | /// |
50 | /// This isn't strictly a bump-pointer allocator as it uses backing slabs of |
51 | /// memory rather than relying on a boundless contiguous heap. However, it has |
52 | /// bump-pointer semantics in that it is a monotonically growing pool of memory |
53 | /// where every allocation is found by merely allocating the next N bytes in |
54 | /// the slab, or the next N bytes in the next slab. |
55 | /// |
56 | /// Note that this also has a threshold for forcing allocations above a certain |
57 | /// size into their own slab. |
58 | /// |
59 | /// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator |
60 | /// object, which wraps malloc, to allocate memory, but it can be changed to |
61 | /// use a custom allocator. |
62 | /// |
63 | /// The GrowthDelay specifies after how many allocated slabs the allocator |
64 | /// increases the size of the slabs. |
65 | template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096, |
66 | size_t SizeThreshold = SlabSize, size_t GrowthDelay = 128> |
67 | class BumpPtrAllocatorImpl |
68 | : public AllocatorBase<BumpPtrAllocatorImpl<AllocatorT, SlabSize, |
69 | SizeThreshold, GrowthDelay>>, |
70 | private AllocatorT { |
71 | public: |
72 | static_assert(SizeThreshold <= SlabSize, |
73 | "The SizeThreshold must be at most the SlabSize to ensure " |
74 | "that objects larger than a slab go into their own memory " |
75 | "allocation."); |
76 | static_assert(GrowthDelay > 0, |
77 | "GrowthDelay must be at least 1 which already increases the" |
78 | "slab size after each allocated slab."); |
79 | |
80 | BumpPtrAllocatorImpl() = default; |
81 | |
82 | template <typename T> |
83 | BumpPtrAllocatorImpl(T &&Allocator) |
84 | : AllocatorT(std::forward<T &&>(Allocator)) {} |
85 | |
86 | // Manually implement a move constructor as we must clear the old allocator's |
87 | // slabs as a matter of correctness. |
88 | BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old) |
89 | : AllocatorT(static_cast<AllocatorT &&>(Old)), CurPtr(Old.CurPtr), |
90 | End(Old.End), Slabs(std::move(Old.Slabs)), |
91 | CustomSizedSlabs(std::move(Old.CustomSizedSlabs)), |
92 | BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize) { |
93 | Old.CurPtr = Old.End = nullptr; |
94 | Old.BytesAllocated = 0; |
95 | Old.Slabs.clear(); |
96 | Old.CustomSizedSlabs.clear(); |
97 | } |
98 | |
99 | ~BumpPtrAllocatorImpl() { |
100 | DeallocateSlabs(Slabs.begin(), Slabs.end()); |
101 | DeallocateCustomSizedSlabs(); |
102 | } |
103 | |
104 | BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) { |
105 | DeallocateSlabs(Slabs.begin(), Slabs.end()); |
106 | DeallocateCustomSizedSlabs(); |
107 | |
108 | CurPtr = RHS.CurPtr; |
109 | End = RHS.End; |
110 | BytesAllocated = RHS.BytesAllocated; |
111 | RedZoneSize = RHS.RedZoneSize; |
112 | Slabs = std::move(RHS.Slabs); |
113 | CustomSizedSlabs = std::move(RHS.CustomSizedSlabs); |
114 | AllocatorT::operator=(static_cast<AllocatorT &&>(RHS)); |
115 | |
116 | RHS.CurPtr = RHS.End = nullptr; |
117 | RHS.BytesAllocated = 0; |
118 | RHS.Slabs.clear(); |
119 | RHS.CustomSizedSlabs.clear(); |
120 | return *this; |
121 | } |
122 | |
123 | /// Deallocate all but the current slab and reset the current pointer |
124 | /// to the beginning of it, freeing all memory allocated so far. |
125 | void Reset() { |
126 | // Deallocate all but the first slab, and deallocate all custom-sized slabs. |
127 | DeallocateCustomSizedSlabs(); |
128 | CustomSizedSlabs.clear(); |
129 | |
130 | if (Slabs.empty()) |
131 | return; |
132 | |
133 | // Reset the state. |
134 | BytesAllocated = 0; |
135 | CurPtr = (char *)Slabs.front(); |
136 | End = CurPtr + SlabSize; |
137 | |
138 | __asan_poison_memory_region(*Slabs.begin(), computeSlabSize(0)); |
139 | DeallocateSlabs(std::next(Slabs.begin()), Slabs.end()); |
140 | Slabs.erase(std::next(Slabs.begin()), Slabs.end()); |
141 | } |
142 | |
143 | /// Allocate space at the specified alignment. |
144 | LLVM_ATTRIBUTE_RETURNS_NONNULL__attribute__((returns_nonnull)) LLVM_ATTRIBUTE_RETURNS_NOALIAS__attribute__((__malloc__)) void * |
145 | Allocate(size_t Size, Align Alignment) { |
146 | // Keep track of how many bytes we've allocated. |
147 | BytesAllocated += Size; |
148 | |
149 | size_t Adjustment = offsetToAlignedAddr(CurPtr, Alignment); |
150 | assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow")((void)0); |
151 | |
152 | size_t SizeToAllocate = Size; |
153 | #if LLVM_ADDRESS_SANITIZER_BUILD0 |
154 | // Add trailing bytes as a "red zone" under ASan. |
155 | SizeToAllocate += RedZoneSize; |
156 | #endif |
157 | |
158 | // Check if we have enough space. |
159 | if (Adjustment + SizeToAllocate <= size_t(End - CurPtr)) { |
160 | char *AlignedPtr = CurPtr + Adjustment; |
161 | CurPtr = AlignedPtr + SizeToAllocate; |
162 | // Update the allocation point of this memory block in MemorySanitizer. |
163 | // Without this, MemorySanitizer messages for values originated from here |
164 | // will point to the allocation of the entire slab. |
165 | __msan_allocated_memory(AlignedPtr, Size); |
166 | // Similarly, tell ASan about this space. |
167 | __asan_unpoison_memory_region(AlignedPtr, Size); |
168 | return AlignedPtr; |
169 | } |
170 | |
171 | // If Size is really big, allocate a separate slab for it. |
172 | size_t PaddedSize = SizeToAllocate + Alignment.value() - 1; |
173 | if (PaddedSize > SizeThreshold) { |
174 | void *NewSlab = |
175 | AllocatorT::Allocate(PaddedSize, alignof(std::max_align_t)); |
176 | // We own the new slab and don't want anyone reading anyting other than |
177 | // pieces returned from this method. So poison the whole slab. |
178 | __asan_poison_memory_region(NewSlab, PaddedSize); |
179 | CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize)); |
180 | |
181 | uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment); |
182 | assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize)((void)0); |
183 | char *AlignedPtr = (char*)AlignedAddr; |
184 | __msan_allocated_memory(AlignedPtr, Size); |
185 | __asan_unpoison_memory_region(AlignedPtr, Size); |
186 | return AlignedPtr; |
187 | } |
188 | |
189 | // Otherwise, start a new slab and try again. |
190 | StartNewSlab(); |
191 | uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment); |
192 | assert(AlignedAddr + SizeToAllocate <= (uintptr_t)End &&((void)0) |
193 | "Unable to allocate memory!")((void)0); |
194 | char *AlignedPtr = (char*)AlignedAddr; |
195 | CurPtr = AlignedPtr + SizeToAllocate; |
196 | __msan_allocated_memory(AlignedPtr, Size); |
197 | __asan_unpoison_memory_region(AlignedPtr, Size); |
198 | return AlignedPtr; |
199 | } |
200 | |
201 | inline LLVM_ATTRIBUTE_RETURNS_NONNULL__attribute__((returns_nonnull)) LLVM_ATTRIBUTE_RETURNS_NOALIAS__attribute__((__malloc__)) void * |
202 | Allocate(size_t Size, size_t Alignment) { |
203 | assert(Alignment > 0 && "0-byte alignment is not allowed. Use 1 instead.")((void)0); |
204 | return Allocate(Size, Align(Alignment)); |
205 | } |
206 | |
207 | // Pull in base class overloads. |
208 | using AllocatorBase<BumpPtrAllocatorImpl>::Allocate; |
209 | |
210 | // Bump pointer allocators are expected to never free their storage; and |
211 | // clients expect pointers to remain valid for non-dereferencing uses even |
212 | // after deallocation. |
213 | void Deallocate(const void *Ptr, size_t Size, size_t /*Alignment*/) { |
214 | __asan_poison_memory_region(Ptr, Size); |
215 | } |
216 | |
217 | // Pull in base class overloads. |
218 | using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate; |
219 | |
220 | size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); } |
221 | |
222 | /// \return An index uniquely and reproducibly identifying |
223 | /// an input pointer \p Ptr in the given allocator. |
224 | /// The returned value is negative iff the object is inside a custom-size |
225 | /// slab. |
226 | /// Returns an empty optional if the pointer is not found in the allocator. |
227 | llvm::Optional<int64_t> identifyObject(const void *Ptr) { |
228 | const char *P = static_cast<const char *>(Ptr); |
229 | int64_t InSlabIdx = 0; |
230 | for (size_t Idx = 0, E = Slabs.size(); Idx < E; Idx++) { |
231 | const char *S = static_cast<const char *>(Slabs[Idx]); |
232 | if (P >= S && P < S + computeSlabSize(Idx)) |
233 | return InSlabIdx + static_cast<int64_t>(P - S); |
234 | InSlabIdx += static_cast<int64_t>(computeSlabSize(Idx)); |
235 | } |
236 | |
237 | // Use negative index to denote custom sized slabs. |
238 | int64_t InCustomSizedSlabIdx = -1; |
239 | for (size_t Idx = 0, E = CustomSizedSlabs.size(); Idx < E; Idx++) { |
240 | const char *S = static_cast<const char *>(CustomSizedSlabs[Idx].first); |
241 | size_t Size = CustomSizedSlabs[Idx].second; |
242 | if (P >= S && P < S + Size) |
243 | return InCustomSizedSlabIdx - static_cast<int64_t>(P - S); |
244 | InCustomSizedSlabIdx -= static_cast<int64_t>(Size); |
245 | } |
246 | return None; |
247 | } |
248 | |
249 | /// A wrapper around identifyObject that additionally asserts that |
250 | /// the object is indeed within the allocator. |
251 | /// \return An index uniquely and reproducibly identifying |
252 | /// an input pointer \p Ptr in the given allocator. |
253 | int64_t identifyKnownObject(const void *Ptr) { |
254 | Optional<int64_t> Out = identifyObject(Ptr); |
255 | assert(Out && "Wrong allocator used")((void)0); |
256 | return *Out; |
257 | } |
258 | |
259 | /// A wrapper around identifyKnownObject. Accepts type information |
260 | /// about the object and produces a smaller identifier by relying on |
261 | /// the alignment information. Note that sub-classes may have different |
262 | /// alignment, so the most base class should be passed as template parameter |
263 | /// in order to obtain correct results. For that reason automatic template |
264 | /// parameter deduction is disabled. |
265 | /// \return An index uniquely and reproducibly identifying |
266 | /// an input pointer \p Ptr in the given allocator. This identifier is |
267 | /// different from the ones produced by identifyObject and |
268 | /// identifyAlignedObject. |
269 | template <typename T> |
270 | int64_t identifyKnownAlignedObject(const void *Ptr) { |
271 | int64_t Out = identifyKnownObject(Ptr); |
272 | assert(Out % alignof(T) == 0 && "Wrong alignment information")((void)0); |
273 | return Out / alignof(T); |
274 | } |
275 | |
276 | size_t getTotalMemory() const { |
277 | size_t TotalMemory = 0; |
278 | for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I) |
279 | TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I)); |
280 | for (auto &PtrAndSize : CustomSizedSlabs) |
281 | TotalMemory += PtrAndSize.second; |
282 | return TotalMemory; |
283 | } |
284 | |
285 | size_t getBytesAllocated() const { return BytesAllocated; } |
286 | |
287 | void setRedZoneSize(size_t NewSize) { |
288 | RedZoneSize = NewSize; |
289 | } |
290 | |
291 | void PrintStats() const { |
292 | detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated, |
293 | getTotalMemory()); |
294 | } |
295 | |
296 | private: |
297 | /// The current pointer into the current slab. |
298 | /// |
299 | /// This points to the next free byte in the slab. |
300 | char *CurPtr = nullptr; |
301 | |
302 | /// The end of the current slab. |
303 | char *End = nullptr; |
304 | |
305 | /// The slabs allocated so far. |
306 | SmallVector<void *, 4> Slabs; |
307 | |
308 | /// Custom-sized slabs allocated for too-large allocation requests. |
309 | SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs; |
310 | |
311 | /// How many bytes we've allocated. |
312 | /// |
313 | /// Used so that we can compute how much space was wasted. |
314 | size_t BytesAllocated = 0; |
315 | |
316 | /// The number of bytes to put between allocations when running under |
317 | /// a sanitizer. |
318 | size_t RedZoneSize = 1; |
319 | |
320 | static size_t computeSlabSize(unsigned SlabIdx) { |
321 | // Scale the actual allocated slab size based on the number of slabs |
322 | // allocated. Every GrowthDelay slabs allocated, we double |
323 | // the allocated size to reduce allocation frequency, but saturate at |
324 | // multiplying the slab size by 2^30. |
325 | return SlabSize * |
326 | ((size_t)1 << std::min<size_t>(30, SlabIdx / GrowthDelay)); |
327 | } |
328 | |
329 | /// Allocate a new slab and move the bump pointers over into the new |
330 | /// slab, modifying CurPtr and End. |
331 | void StartNewSlab() { |
332 | size_t AllocatedSlabSize = computeSlabSize(Slabs.size()); |
333 | |
334 | void *NewSlab = |
335 | AllocatorT::Allocate(AllocatedSlabSize, alignof(std::max_align_t)); |
336 | // We own the new slab and don't want anyone reading anything other than |
337 | // pieces returned from this method. So poison the whole slab. |
338 | __asan_poison_memory_region(NewSlab, AllocatedSlabSize); |
339 | |
340 | Slabs.push_back(NewSlab); |
341 | CurPtr = (char *)(NewSlab); |
342 | End = ((char *)NewSlab) + AllocatedSlabSize; |
343 | } |
344 | |
345 | /// Deallocate a sequence of slabs. |
346 | void DeallocateSlabs(SmallVectorImpl<void *>::iterator I, |
347 | SmallVectorImpl<void *>::iterator E) { |
348 | for (; I != E; ++I) { |
349 | size_t AllocatedSlabSize = |
350 | computeSlabSize(std::distance(Slabs.begin(), I)); |
351 | AllocatorT::Deallocate(*I, AllocatedSlabSize, alignof(std::max_align_t)); |
352 | } |
353 | } |
354 | |
355 | /// Deallocate all memory for custom sized slabs. |
356 | void DeallocateCustomSizedSlabs() { |
357 | for (auto &PtrAndSize : CustomSizedSlabs) { |
358 | void *Ptr = PtrAndSize.first; |
359 | size_t Size = PtrAndSize.second; |
360 | AllocatorT::Deallocate(Ptr, Size, alignof(std::max_align_t)); |
361 | } |
362 | } |
363 | |
364 | template <typename T> friend class SpecificBumpPtrAllocator; |
365 | }; |
366 | |
367 | /// The standard BumpPtrAllocator which just uses the default template |
368 | /// parameters. |
369 | typedef BumpPtrAllocatorImpl<> BumpPtrAllocator; |
370 | |
371 | /// A BumpPtrAllocator that allows only elements of a specific type to be |
372 | /// allocated. |
373 | /// |
374 | /// This allows calling the destructor in DestroyAll() and when the allocator is |
375 | /// destroyed. |
376 | template <typename T> class SpecificBumpPtrAllocator { |
377 | BumpPtrAllocator Allocator; |
378 | |
379 | public: |
380 | SpecificBumpPtrAllocator() { |
381 | // Because SpecificBumpPtrAllocator walks the memory to call destructors, |
382 | // it can't have red zones between allocations. |
383 | Allocator.setRedZoneSize(0); |
384 | } |
385 | SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old) |
386 | : Allocator(std::move(Old.Allocator)) {} |
387 | ~SpecificBumpPtrAllocator() { DestroyAll(); } |
388 | |
389 | SpecificBumpPtrAllocator &operator=(SpecificBumpPtrAllocator &&RHS) { |
390 | Allocator = std::move(RHS.Allocator); |
391 | return *this; |
392 | } |
393 | |
394 | /// Call the destructor of each allocated object and deallocate all but the |
395 | /// current slab and reset the current pointer to the beginning of it, freeing |
396 | /// all memory allocated so far. |
397 | void DestroyAll() { |
398 | auto DestroyElements = [](char *Begin, char *End) { |
399 | assert(Begin == (char *)alignAddr(Begin, Align::Of<T>()))((void)0); |
400 | for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T)) |
401 | reinterpret_cast<T *>(Ptr)->~T(); |
402 | }; |
403 | |
404 | for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E; |
405 | ++I) { |
406 | size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize( |
407 | std::distance(Allocator.Slabs.begin(), I)); |
408 | char *Begin = (char *)alignAddr(*I, Align::Of<T>()); |
409 | char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr |
410 | : (char *)*I + AllocatedSlabSize; |
411 | |
412 | DestroyElements(Begin, End); |
413 | } |
414 | |
415 | for (auto &PtrAndSize : Allocator.CustomSizedSlabs) { |
416 | void *Ptr = PtrAndSize.first; |
417 | size_t Size = PtrAndSize.second; |
418 | DestroyElements((char *)alignAddr(Ptr, Align::Of<T>()), |
419 | (char *)Ptr + Size); |
420 | } |
421 | |
422 | Allocator.Reset(); |
423 | } |
424 | |
425 | /// Allocate space for an array of objects without constructing them. |
426 | T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); } |
427 | }; |
428 | |
429 | } // end namespace llvm |
430 | |
431 | template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold, |
432 | size_t GrowthDelay> |
433 | void * |
434 | operator new(size_t Size, |
435 | llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold, |
436 | GrowthDelay> &Allocator) { |
437 | return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size), |
438 | alignof(std::max_align_t))); |
439 | } |
440 | |
441 | template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold, |
442 | size_t GrowthDelay> |
443 | void operator delete(void *, |
444 | llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, |
445 | SizeThreshold, GrowthDelay> &) { |
446 | } |
447 | |
448 | #endif // LLVM_SUPPORT_ALLOCATOR_H |
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_ |