1//===- subzero/src/IceDefs.h - Common Subzero declarations ------*- C++ -*-===//
2//
3// The Subzero Code Generator
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9///
10/// \file
11/// \brief Declares various useful types and classes that have widespread use
12/// across Subzero.
13///
14//===----------------------------------------------------------------------===//
15
16#ifndef SUBZERO_SRC_ICEDEFS_H
17#define SUBZERO_SRC_ICEDEFS_H
18
19#include "IceBuildDefs.h" // TODO(stichnot): move into individual files
20#include "IceMemory.h"
21#include "IceTLS.h"
22
23#include "llvm/ADT/ArrayRef.h"
24#include "llvm/ADT/ilist.h"
25#include "llvm/ADT/ilist_node.h"
26#include "llvm/ADT/iterator_range.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/Support/Casting.h"
30#include "llvm/Support/ELF.h"
31#include "llvm/Support/raw_ostream.h"
32
33#include <cassert>
34#include <cstdint>
35#include <cstdio> // snprintf
36#include <functional> // std::less
37#include <limits>
38#include <list>
39#include <map>
40#include <memory>
41#include <mutex>
42#include <set>
43#include <string>
44#include <system_error>
45#include <unordered_map>
46#include <unordered_set>
47#include <utility>
48#include <vector>
49
50#define XSTRINGIFY(x) STRINGIFY(x)
51#define STRINGIFY(x) #x
52
53namespace Ice {
54
55class Assembler;
56template <template <typename> class> class BitVectorTmpl;
57class Cfg;
58class CfgNode;
59class Constant;
60class ELFFileStreamer;
61class ELFObjectWriter;
62class ELFStreamer;
63class FunctionDeclaration;
64class GlobalContext;
65class GlobalDeclaration;
66class Inst;
67class InstAssign;
68class InstJumpTable;
69class InstPhi;
70class InstSwitch;
71class InstTarget;
72class LiveRange;
73class Liveness;
74class Operand;
75class TargetDataLowering;
76class TargetLowering;
77class Variable;
78class VariableDeclaration;
79class VariablesMetadata;
80
81/// SizeT is for holding small-ish limits like number of source operands in an
82/// instruction. It is used instead of size_t (which may be 64-bits wide) when
83/// we want to save space.
84using SizeT = uint32_t;
85
86constexpr char GlobalOffsetTable[] = "_GLOBAL_OFFSET_TABLE_";
87// makeUnique should be used when memory is expected to be allocated from the
88// heap (as opposed to allocated from some Allocator.) It is intended to be
89// used instead of new.
90//
91// The expected usage is as follows
92//
93// class MyClass {
94// public:
95// static std::unique_ptr<MyClass> create(<ctor_args>) {
96// return makeUnique<MyClass>(<ctor_args>);
97// }
98//
99// private:
100// ENABLE_MAKE_UNIQUE;
101//
102// MyClass(<ctor_args>) ...
103// }
104//
105// ENABLE_MAKE_UNIQUE is a trick that is necessary if MyClass' ctor is private.
106// Private ctors are highly encouraged when you're writing a class that you'd
107// like to have allocated with makeUnique as it would prevent users from
108// declaring stack allocated variables.
109namespace Internal {
110struct MakeUniqueEnabler {
111 template <class T, class... Args>
112 static std::unique_ptr<T> create(Args &&... TheArgs) {
113 std::unique_ptr<T> Unique(new T(std::forward<Args>(TheArgs)...));
114 return Unique;
115 }
116};
117} // end of namespace Internal
118
119template <class T, class... Args>
120static std::unique_ptr<T> makeUnique(Args &&... TheArgs) {
121 return ::Ice::Internal::MakeUniqueEnabler::create<T>(
122 std::forward<Args>(TheArgs)...);
123}
124
125#define ENABLE_MAKE_UNIQUE friend struct ::Ice::Internal::MakeUniqueEnabler
126
127using InstList = llvm::ilist<Inst>;
128// Ideally PhiList would be llvm::ilist<InstPhi>, and similar for AssignList,
129// but this runs into issues with SFINAE.
130using PhiList = InstList;
131using AssignList = InstList;
132
133// Standard library containers with CfgLocalAllocator.
134template <typename T> using CfgList = std::list<T, CfgLocalAllocator<T>>;
135template <typename T, typename H = std::hash<T>, typename Eq = std::equal_to<T>>
136using CfgUnorderedSet = std::unordered_set<T, H, Eq, CfgLocalAllocator<T>>;
137template <typename T, typename Cmp = std::less<T>>
138using CfgSet = std::set<T, Cmp, CfgLocalAllocator<T>>;
139template <typename T, typename U, typename H = std::hash<T>,
140 typename Eq = std::equal_to<T>>
141using CfgUnorderedMap =
142 std::unordered_map<T, U, H, Eq, CfgLocalAllocator<std::pair<const T, U>>>;
143template <typename T> using CfgVector = std::vector<T, CfgLocalAllocator<T>>;
144
145// Containers that are arena-allocated from the Cfg's allocator.
146using OperandList = CfgVector<Operand *>;
147using VarList = CfgVector<Variable *>;
148using NodeList = CfgVector<CfgNode *>;
149
150// Containers that use the default (global) allocator.
151using ConstantList = std::vector<Constant *>;
152using FunctionDeclarationList = std::vector<FunctionDeclaration *>;
153
154/// VariableDeclarationList is a container for holding VariableDeclarations --
155/// i.e., Global Variables. It is also used to create said variables, and their
156/// initializers in an arena.
157class VariableDeclarationList {
158 VariableDeclarationList(const VariableDeclarationList &) = delete;
159 VariableDeclarationList &operator=(const VariableDeclarationList &) = delete;
160 VariableDeclarationList(VariableDeclarationList &&) = delete;
161 VariableDeclarationList &operator=(VariableDeclarationList &&) = delete;
162
163public:
164 using VariableDeclarationArray = std::vector<VariableDeclaration *>;
165
166 VariableDeclarationList() : Arena(new ArenaAllocator()) {}
167
168 ~VariableDeclarationList() { clearAndPurge(); }
169
170 template <typename T> T *allocate_initializer(SizeT Count = 1) {
171 static_assert(
172 std::is_trivially_destructible<T>::value,
173 "allocate_initializer can only allocate trivially destructible types.");
174 return Arena->Allocate<T>(Count);
175 }
176
177 template <typename T> T *allocate_variable_declaration() {
178 static_assert(!std::is_trivially_destructible<T>::value,
179 "allocate_variable_declaration expects non-trivially "
180 "destructible types.");
181 T *Ret = Arena->Allocate<T>();
182 Dtors.emplace_back([Ret]() { Ret->~T(); });
183 return Ret;
184 }
185
186 // This do nothing method is invoked when a global variable is created, but it
187 // will not be emitted. If we ever need to track the created variable, having
188 // this hook is handy.
189 void willNotBeEmitted(VariableDeclaration *) {}
190
191 /// Merges Other with this, effectively resetting Other to an empty state.
192 void merge(VariableDeclarationList *Other) {
193 assert(Other != nullptr);
194 addArena(std::move(Other->Arena));
195 for (std::size_t i = 0; i < Other->MergedArenas.size(); ++i) {
196 addArena(std::move(Other->MergedArenas[i]));
197 }
198 Other->MergedArenas.clear();
199
200 Dtors.insert(Dtors.end(), Other->Dtors.begin(), Other->Dtors.end());
201 Other->Dtors.clear();
202
203 Globals.insert(Globals.end(), Other->Globals.begin(), Other->Globals.end());
204 Other->Globals.clear();
205 }
206
207 /// Destroys all GlobalVariables and initializers that this knows about
208 /// (including those merged with it), and releases memory.
209 void clearAndPurge() {
210 if (Arena == nullptr) {
211 // Arena is only null if this was merged, so we ensure there's no state
212 // being held by this.
213 assert(Dtors.empty());
214 assert(Globals.empty());
215 assert(MergedArenas.empty());
216 return;
217 }
218 // Invokes destructors in reverse creation order.
219 for (auto Dtor = Dtors.rbegin(); Dtor != Dtors.rend(); ++Dtor) {
220 (*Dtor)();
221 }
222 Dtors.clear();
223 Globals.clear();
224 MergedArenas.clear();
225 Arena->Reset();
226 }
227
228 /// Adapt the relevant parts of the std::vector<VariableDeclaration *>
229 /// interface.
230 /// @{
231 VariableDeclarationArray::iterator begin() { return Globals.begin(); }
232
233 VariableDeclarationArray::iterator end() { return Globals.end(); }
234
235 VariableDeclarationArray::const_iterator begin() const {
236 return Globals.begin();
237 }
238
239 VariableDeclarationArray::const_iterator end() const { return Globals.end(); }
240
241 bool empty() const { return Globals.empty(); }
242
243 VariableDeclarationArray::size_type size() const { return Globals.size(); }
244
245 VariableDeclarationArray::reference
246 at(VariableDeclarationArray::size_type Pos) {
247 return Globals.at(Pos);
248 }
249
250 void push_back(VariableDeclaration *Global) { Globals.push_back(Global); }
251
252 void reserve(VariableDeclarationArray::size_type Capacity) {
253 Globals.reserve(Capacity);
254 }
255
256 void clear() { Globals.clear(); }
257
258 VariableDeclarationArray::reference back() { return Globals.back(); }
259 /// @}
260
261private:
262 using ArenaPtr = std::unique_ptr<ArenaAllocator>;
263 using DestructorsArray = std::vector<std::function<void()>>;
264
265 void addArena(ArenaPtr NewArena) {
266 MergedArenas.emplace_back(std::move(NewArena));
267 }
268
269 ArenaPtr Arena;
270 VariableDeclarationArray Globals;
271 DestructorsArray Dtors;
272 std::vector<ArenaPtr> MergedArenas;
273};
274
275/// InstNumberT is for holding an instruction number. Instruction numbers are
276/// used for representing Variable live ranges.
277using InstNumberT = int32_t;
278
279/// A LiveBeginEndMapEntry maps a Variable::Number value to an Inst::Number
280/// value, giving the instruction number that begins or ends a variable's live
281/// range.
282template <typename T>
283using LivenessVector = std::vector<T, LivenessAllocator<T>>;
284using LiveBeginEndMapEntry = std::pair<SizeT, InstNumberT>;
285using LiveBeginEndMap = LivenessVector<LiveBeginEndMapEntry>;
286using LivenessBV = BitVectorTmpl<LivenessAllocator>;
287
288using TimerStackIdT = uint32_t;
289using TimerIdT = uint32_t;
290
291/// Use alignas(MaxCacheLineSize) to isolate variables/fields that might be
292/// contended while multithreading. Assumes the maximum cache line size is 64.
293enum { MaxCacheLineSize = 64 };
294// Use ICE_CACHELINE_BOUNDARY to force the next field in a declaration
295// list to be aligned to the next cache line.
296#if defined(_MSC_VER)
297#define ICE_CACHELINE_BOUNDARY __declspec(align(MaxCacheLineSize)) int : 0;
298#else // !defined(_MSC_VER)
299// Note: zero is added to work around the following GCC 4.8 bug (fixed in 4.9):
300// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55382
301#define ICE_CACHELINE_BOUNDARY \
302 __attribute__((aligned(MaxCacheLineSize + 0))) int : 0
303#endif // !defined(_MSC_VER)
304
305/// PNaCl is ILP32, so theoretically we should only need 32-bit offsets.
306using RelocOffsetT = int32_t;
307enum { RelocAddrSize = 4 };
308
309enum LivenessMode {
310 /// Basic version of live-range-end calculation. Marks the last uses of
311 /// variables based on dataflow analysis. Records the set of live-in and
312 /// live-out variables for each block. Identifies and deletes dead
313 /// instructions (primarily stores).
314 Liveness_Basic,
315
316 /// In addition to Liveness_Basic, also calculate the complete live range for
317 /// each variable in a form suitable for interference calculation and register
318 /// allocation.
319 Liveness_Intervals
320};
321
322enum LCSEOptions {
323 LCSE_Disabled,
324 LCSE_EnabledSSA, // Default Mode, assumes SSA.
325 LCSE_EnabledNoSSA // Does not assume SSA, to be enabled if CSE is done later.
326};
327
328enum RegAllocKind {
329 RAK_Unknown,
330 RAK_Global, /// full, global register allocation
331 RAK_SecondChance, /// second-chance bin-packing after full regalloc attempt
332 RAK_Phi, /// infinite-weight Variables with active spilling/filling
333 RAK_InfOnly /// allocation only for infinite-weight Variables
334};
335
336enum VerboseItem {
337 IceV_None = 0,
338 IceV_Instructions = 1 << 0,
339 IceV_Deleted = 1 << 1,
340 IceV_InstNumbers = 1 << 2,
341 IceV_Preds = 1 << 3,
342 IceV_Succs = 1 << 4,
343 IceV_Liveness = 1 << 5,
344 IceV_RegOrigins = 1 << 6,
345 IceV_LinearScan = 1 << 7,
346 IceV_Frame = 1 << 8,
347 IceV_AddrOpt = 1 << 9,
348 IceV_Random = 1 << 10,
349 IceV_Folding = 1 << 11,
350 IceV_RMW = 1 << 12,
351 IceV_Loop = 1 << 13,
352 IceV_Mem = 1 << 14,
353 // Leave some extra space to make it easier to add new per-pass items.
354 IceV_NO_PER_PASS_DUMP_BEYOND = 1 << 19,
355 // Items greater than IceV_NO_PER_PASS_DUMP_BEYOND don't by themselves trigger
356 // per-pass Cfg dump output.
357 IceV_Status = 1 << 20,
358 IceV_AvailableRegs = 1 << 21,
359 IceV_GlobalInit = 1 << 22,
360 IceV_ConstPoolStats = 1 << 23,
361 IceV_Wasm = 1 << 24,
362 IceV_ShufMat = 1 << 25,
363 IceV_All = ~IceV_None,
364 IceV_Most =
365 IceV_All & ~IceV_LinearScan & ~IceV_GlobalInit & ~IceV_ConstPoolStats
366};
367using VerboseMask = uint32_t;
368
369enum FileType {
370 FT_Elf, /// ELF .o file
371 FT_Asm, /// Assembly .s file
372 FT_Iasm /// "Integrated assembler" .byte-style .s file
373};
374
375enum ABI {
376 ABI_PNaCl, /// x32 for unsandboxed 64-bit x86
377 ABI_Platform /// Native executable ABI
378};
379
380using Ostream = llvm::raw_ostream;
381using Fdstream = llvm::raw_fd_ostream;
382
383using GlobalLockType = std::mutex;
384
385/// LockedPtr is an RAII wrapper that allows automatically locked access to a
386/// given pointer, automatically unlocking it when when the LockedPtr goes out
387/// of scope.
388template <typename T> class LockedPtr {
389 LockedPtr() = delete;
390 LockedPtr(const LockedPtr &) = delete;
391 LockedPtr &operator=(const LockedPtr &) = delete;
392
393public:
394 LockedPtr(T *Value, GlobalLockType *Lock) : Value(Value), Lock(Lock) {
395 Lock->lock();
396 }
397 LockedPtr(LockedPtr &&Other) : Value(Other.Value), Lock(Other.Lock) {
398 Other.Value = nullptr;
399 Other.Lock = nullptr;
400 }
401 ~LockedPtr() {
402 if (Lock != nullptr)
403 Lock->unlock();
404 }
405 T *operator->() const { return Value; }
406 T &operator*() const { return *Value; }
407 T *get() { return Value; }
408
409private:
410 T *Value;
411 GlobalLockType *Lock;
412};
413
414enum ErrorCodes { EC_None = 0, EC_Args, EC_Bitcode, EC_Translation };
415
416/// Wrapper around std::error_code for allowing multiple errors to be folded
417/// into one. The current implementation keeps track of the first error, which
418/// is likely to be the most useful one, and this could be extended to e.g.
419/// collect a vector of errors.
420class ErrorCode : public std::error_code {
421 ErrorCode(const ErrorCode &) = delete;
422 ErrorCode &operator=(const ErrorCode &) = delete;
423
424public:
425 ErrorCode() = default;
426 void assign(ErrorCodes Code) {
427 if (!HasError) {
428 HasError = true;
429 std::error_code::assign(Code, std::generic_category());
430 }
431 }
432 void assign(int Code) { assign(static_cast<ErrorCodes>(Code)); }
433
434private:
435 bool HasError = false;
436};
437
438/// Reverse range adaptors written in terms of llvm::make_range().
439template <typename T>
440llvm::iterator_range<typename T::const_reverse_iterator>
441reverse_range(const T &Container) {
442 return llvm::make_range(Container.rbegin(), Container.rend());
443}
444template <typename T>
445llvm::iterator_range<typename T::reverse_iterator> reverse_range(T &Container) {
446 return llvm::make_range(Container.rbegin(), Container.rend());
447}
448
449/// Options for pooling and randomization of immediates.
450enum RandomizeAndPoolImmediatesEnum { RPI_None, RPI_Randomize, RPI_Pool };
451
452/// Salts for Random number generator for different randomization passes.
453enum RandomizationPassesEnum {
454 RPE_BasicBlockReordering,
455 RPE_ConstantBlinding,
456 RPE_FunctionReordering,
457 RPE_GlobalVariableReordering,
458 RPE_NopInsertion,
459 RPE_PooledConstantReordering,
460 RPE_RegAllocRandomization,
461 RPE_num
462};
463
464using RelocOffsetArray = llvm::SmallVector<class RelocOffset *, 4>;
465
466} // end of namespace Ice
467
468#endif // SUBZERO_SRC_ICEDEFS_H
469