• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
53 namespace Ice {
54 
55 class Assembler;
56 template <template <typename> class> class BitVectorTmpl;
57 class Cfg;
58 class CfgNode;
59 class Constant;
60 class ELFFileStreamer;
61 class ELFObjectWriter;
62 class ELFStreamer;
63 class FunctionDeclaration;
64 class GlobalContext;
65 class GlobalDeclaration;
66 class Inst;
67 class InstAssign;
68 class InstJumpTable;
69 class InstPhi;
70 class InstSwitch;
71 class InstTarget;
72 class LiveRange;
73 class Liveness;
74 class Operand;
75 class TargetDataLowering;
76 class TargetLowering;
77 class Variable;
78 class VariableDeclaration;
79 class 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.
84 using SizeT = uint32_t;
85 
86 constexpr 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.
109 namespace Internal {
110 struct MakeUniqueEnabler {
111   template <class T, class... Args>
createMakeUniqueEnabler112   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 
119 template <class T, class... Args>
makeUnique(Args &&...TheArgs)120 static 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 
127 using InstList = llvm::ilist<Inst>;
128 // Ideally PhiList would be llvm::ilist<InstPhi>, and similar for AssignList,
129 // but this runs into issues with SFINAE.
130 using PhiList = InstList;
131 using AssignList = InstList;
132 
133 // Standard library containers with CfgLocalAllocator.
134 template <typename T> using CfgList = std::list<T, CfgLocalAllocator<T>>;
135 template <typename T, typename H = std::hash<T>, typename Eq = std::equal_to<T>>
136 using CfgUnorderedSet = std::unordered_set<T, H, Eq, CfgLocalAllocator<T>>;
137 template <typename T, typename Cmp = std::less<T>>
138 using CfgSet = std::set<T, Cmp, CfgLocalAllocator<T>>;
139 template <typename T, typename U, typename H = std::hash<T>,
140           typename Eq = std::equal_to<T>>
141 using CfgUnorderedMap =
142     std::unordered_map<T, U, H, Eq, CfgLocalAllocator<std::pair<const T, U>>>;
143 template <typename T> using CfgVector = std::vector<T, CfgLocalAllocator<T>>;
144 
145 // Containers that are arena-allocated from the Cfg's allocator.
146 using OperandList = CfgVector<Operand *>;
147 using VarList = CfgVector<Variable *>;
148 using NodeList = CfgVector<CfgNode *>;
149 
150 // Containers that use the default (global) allocator.
151 using ConstantList = std::vector<Constant *>;
152 using 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.
157 class VariableDeclarationList {
158   VariableDeclarationList(const VariableDeclarationList &) = delete;
159   VariableDeclarationList &operator=(const VariableDeclarationList &) = delete;
160   VariableDeclarationList(VariableDeclarationList &&) = delete;
161   VariableDeclarationList &operator=(VariableDeclarationList &&) = delete;
162 
163 public:
164   using VariableDeclarationArray = std::vector<VariableDeclaration *>;
165 
VariableDeclarationList()166   VariableDeclarationList() : Arena(new ArenaAllocator()) {}
167 
~VariableDeclarationList()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 
allocate_variable_declaration()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.
willNotBeEmitted(VariableDeclaration *)189   void willNotBeEmitted(VariableDeclaration *) {}
190 
191   /// Merges Other with this, effectively resetting Other to an empty state.
merge(VariableDeclarationList * Other)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.
clearAndPurge()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   /// @{
begin()231   VariableDeclarationArray::iterator begin() { return Globals.begin(); }
232 
end()233   VariableDeclarationArray::iterator end() { return Globals.end(); }
234 
begin()235   VariableDeclarationArray::const_iterator begin() const {
236     return Globals.begin();
237   }
238 
end()239   VariableDeclarationArray::const_iterator end() const { return Globals.end(); }
240 
empty()241   bool empty() const { return Globals.empty(); }
242 
size()243   VariableDeclarationArray::size_type size() const { return Globals.size(); }
244 
245   VariableDeclarationArray::reference
at(VariableDeclarationArray::size_type Pos)246   at(VariableDeclarationArray::size_type Pos) {
247     return Globals.at(Pos);
248   }
249 
push_back(VariableDeclaration * Global)250   void push_back(VariableDeclaration *Global) { Globals.push_back(Global); }
251 
reserve(VariableDeclarationArray::size_type Capacity)252   void reserve(VariableDeclarationArray::size_type Capacity) {
253     Globals.reserve(Capacity);
254   }
255 
clear()256   void clear() { Globals.clear(); }
257 
back()258   VariableDeclarationArray::reference back() { return Globals.back(); }
259   /// @}
260 
261 private:
262   using ArenaPtr = std::unique_ptr<ArenaAllocator>;
263   using DestructorsArray = std::vector<std::function<void()>>;
264 
addArena(ArenaPtr NewArena)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.
277 using 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.
282 template <typename T>
283 using LivenessVector = std::vector<T, LivenessAllocator<T>>;
284 using LiveBeginEndMapEntry = std::pair<SizeT, InstNumberT>;
285 using LiveBeginEndMap = LivenessVector<LiveBeginEndMapEntry>;
286 using LivenessBV = BitVectorTmpl<LivenessAllocator>;
287 
288 using TimerStackIdT = uint32_t;
289 using 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.
293 enum { 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.
306 using RelocOffsetT = int32_t;
307 enum { RelocAddrSize = 4 };
308 
309 enum 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 
322 enum 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 
328 enum 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 
336 enum 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 };
367 using VerboseMask = uint32_t;
368 
369 enum FileType {
370   FT_Elf, /// ELF .o file
371   FT_Asm, /// Assembly .s file
372   FT_Iasm /// "Integrated assembler" .byte-style .s file
373 };
374 
375 enum ABI {
376   ABI_PNaCl,   /// x32 for unsandboxed 64-bit x86
377   ABI_Platform /// Native executable ABI
378 };
379 
380 using Ostream = llvm::raw_ostream;
381 using Fdstream = llvm::raw_fd_ostream;
382 
383 using 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.
388 template <typename T> class LockedPtr {
389   LockedPtr() = delete;
390   LockedPtr(const LockedPtr &) = delete;
391   LockedPtr &operator=(const LockedPtr &) = delete;
392 
393 public:
LockedPtr(T * Value,GlobalLockType * Lock)394   LockedPtr(T *Value, GlobalLockType *Lock) : Value(Value), Lock(Lock) {
395     Lock->lock();
396   }
LockedPtr(LockedPtr && Other)397   LockedPtr(LockedPtr &&Other) : Value(Other.Value), Lock(Other.Lock) {
398     Other.Value = nullptr;
399     Other.Lock = nullptr;
400   }
~LockedPtr()401   ~LockedPtr() {
402     if (Lock != nullptr)
403       Lock->unlock();
404   }
405   T *operator->() const { return Value; }
406   T &operator*() const { return *Value; }
get()407   T *get() { return Value; }
408 
409 private:
410   T *Value;
411   GlobalLockType *Lock;
412 };
413 
414 enum 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.
420 class ErrorCode : public std::error_code {
421   ErrorCode(const ErrorCode &) = delete;
422   ErrorCode &operator=(const ErrorCode &) = delete;
423 
424 public:
425   ErrorCode() = default;
assign(ErrorCodes Code)426   void assign(ErrorCodes Code) {
427     if (!HasError) {
428       HasError = true;
429       std::error_code::assign(Code, std::generic_category());
430     }
431   }
assign(int Code)432   void assign(int Code) { assign(static_cast<ErrorCodes>(Code)); }
433 
434 private:
435   bool HasError = false;
436 };
437 
438 /// Reverse range adaptors written in terms of llvm::make_range().
439 template <typename T>
440 llvm::iterator_range<typename T::const_reverse_iterator>
reverse_range(const T & Container)441 reverse_range(const T &Container) {
442   return llvm::make_range(Container.rbegin(), Container.rend());
443 }
444 template <typename T>
reverse_range(T & Container)445 llvm::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.
450 enum RandomizeAndPoolImmediatesEnum { RPI_None, RPI_Randomize, RPI_Pool };
451 
452 /// Salts for Random number generator for different randomization passes.
453 enum 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 
464 using RelocOffsetArray = llvm::SmallVector<class RelocOffset *, 4>;
465 
466 } // end of namespace Ice
467 
468 #endif // SUBZERO_SRC_ICEDEFS_H
469