• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- subzero/src/IceCfg.h - Control flow graph ----------------*- 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 the Cfg class, which represents the control flow graph and
12 /// the overall per-function compilation context.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef SUBZERO_SRC_ICECFG_H
17 #define SUBZERO_SRC_ICECFG_H
18 
19 #include "IceAssembler.h"
20 #include "IceClFlags.h"
21 #include "IceDefs.h"
22 #include "IceGlobalContext.h"
23 #include "IceLoopAnalyzer.h"
24 #include "IceStringPool.h"
25 #include "IceTypes.h"
26 
27 namespace Ice {
28 
29 class Cfg {
30   Cfg() = delete;
31   Cfg(const Cfg &) = delete;
32   Cfg &operator=(const Cfg &) = delete;
33 
34   std::unique_ptr<ArenaAllocator> Allocator;
35 
36 public:
37   ~Cfg();
38 
create(GlobalContext * Ctx,uint32_t SequenceNumber)39   static std::unique_ptr<Cfg> create(GlobalContext *Ctx,
40                                      uint32_t SequenceNumber) {
41     return std::unique_ptr<Cfg>(new Cfg(Ctx, SequenceNumber));
42   }
43 
getContext()44   GlobalContext *getContext() const { return Ctx; }
getSequenceNumber()45   uint32_t getSequenceNumber() const { return SequenceNumber; }
getOptLevel()46   OptLevel getOptLevel() const { return OptimizationLevel; }
47 
defaultVerboseMask()48   static constexpr VerboseMask defaultVerboseMask() {
49     return (IceV_NO_PER_PASS_DUMP_BEYOND << 1) - 1;
50   }
51   /// Returns true if any of the specified options in the verbose mask are set.
52   /// If the argument is omitted, it checks if any verbose options at all are
53   /// set.
54   bool isVerbose(VerboseMask Mask = defaultVerboseMask()) const {
55     return VMask & Mask;
56   }
setVerbose(VerboseMask Mask)57   void setVerbose(VerboseMask Mask) { VMask = Mask; }
58 
59   /// \name Manage the name and return type of the function being translated.
60   /// @{
setFunctionName(GlobalString Name)61   void setFunctionName(GlobalString Name) { FunctionName = Name; }
getFunctionName()62   GlobalString getFunctionName() const { return FunctionName; }
63   std::string getFunctionNameAndSize() const;
setReturnType(Type Ty)64   void setReturnType(Type Ty) { ReturnType = Ty; }
getReturnType()65   Type getReturnType() const { return ReturnType; }
66   /// @}
67 
68   /// \name Manage the "internal" attribute of the function.
69   /// @{
setInternal(bool Internal)70   void setInternal(bool Internal) { IsInternalLinkage = Internal; }
getInternal()71   bool getInternal() const { return IsInternalLinkage; }
72   /// @}
73 
74   /// \name Manage errors.
75   /// @{
76 
77   /// Translation error flagging. If support for some construct is known to be
78   /// missing, instead of an assertion failure, setError() should be called and
79   /// the error should be propagated back up. This way, we can gracefully fail
80   /// to translate and let a fallback translator handle the function.
81   void setError(const std::string &Message);
hasError()82   bool hasError() const { return HasError; }
getError()83   std::string getError() const { return ErrorMessage; }
84   /// @}
85 
86   /// \name Manage nodes (a.k.a. basic blocks, CfgNodes).
87   /// @{
setEntryNode(CfgNode * EntryNode)88   void setEntryNode(CfgNode *EntryNode) { Entry = EntryNode; }
getEntryNode()89   CfgNode *getEntryNode() const { return Entry; }
90   /// Create a node and append it to the end of the linearized list. The loop
91   /// nest depth of the new node may not be valid if it is created after
92   /// computeLoopNestDepth.
93   CfgNode *makeNode();
getNumNodes()94   SizeT getNumNodes() const { return Nodes.size(); }
getNodes()95   const NodeList &getNodes() const { return Nodes; }
96   /// Swap nodes of Cfg with given list of nodes.  The number of nodes must
97   /// remain unchanged.
98   void swapNodes(NodeList &NewNodes);
99   /// @}
100 
101   /// String pool for CfgNode::Name values.
getNodeStrings()102   StringPool *getNodeStrings() const { return NodeStrings.get(); }
103   /// String pool for Variable::Name values.
getVarStrings()104   StringPool *getVarStrings() const { return VarStrings.get(); }
105 
106   /// \name Manage instruction numbering.
107   /// @{
newInstNumber()108   InstNumberT newInstNumber() { return NextInstNumber++; }
getNextInstNumber()109   InstNumberT getNextInstNumber() const { return NextInstNumber; }
110   /// @}
111 
112   /// \name Manage Variables.
113   /// @{
114 
115   /// Create a new Variable with a particular type and an optional name. The
116   /// Node argument is the node where the variable is defined.
117   // TODO(jpp): untemplate this with separate methods: makeVariable and
118   // makeStackVariable.
makeVariable(Type Ty)119   template <typename T = Variable> T *makeVariable(Type Ty) {
120     SizeT Index = Variables.size();
121     auto *Var = T::create(this, Ty, Index);
122     Variables.push_back(Var);
123     return Var;
124   }
getNumVariables()125   SizeT getNumVariables() const { return Variables.size(); }
getVariables()126   const VarList &getVariables() const { return Variables; }
127   /// @}
128 
129   /// \name Manage arguments to the function.
130   /// @{
131   void addArg(Variable *Arg);
getArgs()132   const VarList &getArgs() const { return Args; }
getArgs()133   VarList &getArgs() { return Args; }
134   void addImplicitArg(Variable *Arg);
getImplicitArgs()135   const VarList &getImplicitArgs() const { return ImplicitArgs; }
136   /// @}
137 
138   /// \name Manage the jump tables.
139   /// @{
addJumpTable(InstJumpTable * JumpTable)140   void addJumpTable(InstJumpTable *JumpTable) {
141     JumpTables.emplace_back(JumpTable);
142   }
143   /// @}
144 
145   /// \name Manage the Globals used by this function.
146   /// @{
getGlobalInits()147   std::unique_ptr<VariableDeclarationList> getGlobalInits() {
148     return std::move(GlobalInits);
149   }
addGlobal(VariableDeclaration * Global)150   void addGlobal(VariableDeclaration *Global) {
151     if (GlobalInits == nullptr) {
152       GlobalInits.reset(new VariableDeclarationList);
153     }
154     GlobalInits->push_back(Global);
155   }
getGlobalPool()156   VariableDeclarationList *getGlobalPool() {
157     if (GlobalInits == nullptr) {
158       GlobalInits.reset(new VariableDeclarationList);
159     }
160     return GlobalInits.get();
161   }
162   /// @}
163 
164   /// \name Miscellaneous accessors.
165   /// @{
getTarget()166   TargetLowering *getTarget() const { return Target.get(); }
getVMetadata()167   VariablesMetadata *getVMetadata() const { return VMetadata.get(); }
getLiveness()168   Liveness *getLiveness() const { return Live.get(); }
getAssembler()169   template <typename T = Assembler> T *getAssembler() const {
170     return llvm::dyn_cast<T>(TargetAssembler.get());
171   }
releaseAssembler()172   std::unique_ptr<Assembler> releaseAssembler() {
173     return std::move(TargetAssembler);
174   }
175   bool hasComputedFrame() const;
getFocusedTiming()176   bool getFocusedTiming() const { return FocusedTiming; }
setFocusedTiming()177   void setFocusedTiming() { FocusedTiming = true; }
getConstantBlindingCookie()178   uint32_t getConstantBlindingCookie() const { return ConstantBlindingCookie; }
179   /// @}
180 
181   /// Returns true if Var is a global variable that is used by the profiling
182   /// code.
183   static bool isProfileGlobal(const VariableDeclaration &Var);
184 
185   /// Passes over the CFG.
186   void translate();
187   /// After the CFG is fully constructed, iterate over the nodes and compute the
188   /// predecessor and successor edges, in the form of CfgNode::InEdges[] and
189   /// CfgNode::OutEdges[].
190   void computeInOutEdges();
191   /// Renumber the non-deleted instructions in the Cfg.  This needs to be done
192   /// in preparation for live range analysis.  The instruction numbers in a
193   /// block must be monotonically increasing.  The range of instruction numbers
194   /// in a block, from lowest to highest, must not overlap with the range of any
195   /// other block.
196   ///
197   /// Also, if the configuration specifies to do so, remove/unlink all deleted
198   /// instructions from the Cfg, to speed up later passes over the instructions.
199   void renumberInstructions();
200   void placePhiLoads();
201   void placePhiStores();
202   void deletePhis();
203   void advancedPhiLowering();
204   void reorderNodes();
205   void shuffleNodes();
206   void localCSE(bool AssumeSSA);
207   void floatConstantCSE();
208   void shortCircuitJumps();
209   void loopInvariantCodeMotion();
210 
211   /// Scan allocas to determine whether we need to use a frame pointer.
212   /// If SortAndCombine == true, merge all the fixed-size allocas in the
213   /// entry block and emit stack or frame pointer-relative addressing.
214   void processAllocas(bool SortAndCombine);
215   void doAddressOpt();
216   /// Find clusters of insertelement/extractelement instructions that can be
217   /// replaced by a shufflevector instruction.
218   void materializeVectorShuffles();
219   void doArgLowering();
220   void doNopInsertion();
221   void genCode();
222   void genFrame();
223   void generateLoopInfo();
224   void livenessLightweight();
225   void liveness(LivenessMode Mode);
226   bool validateLiveness() const;
227   void contractEmptyNodes();
228   void doBranchOpt();
229   void markNodesForSandboxing();
230 
231   /// \name  Manage the CurrentNode field.
232   /// CurrentNode is used for validating the Variable::DefNode field during
233   /// dumping/emitting.
234   /// @{
setCurrentNode(const CfgNode * Node)235   void setCurrentNode(const CfgNode *Node) { CurrentNode = Node; }
resetCurrentNode()236   void resetCurrentNode() { setCurrentNode(nullptr); }
getCurrentNode()237   const CfgNode *getCurrentNode() const { return CurrentNode; }
238   /// @}
239 
240   /// Get the total amount of memory held by the per-Cfg allocator.
241   size_t getTotalMemoryMB() const;
242 
243   /// Get the current memory usage due to liveness data structures.
244   size_t getLivenessMemoryMB() const;
245 
246   void emit();
247   void emitIAS();
248   static void emitTextHeader(GlobalString Name, GlobalContext *Ctx,
249                              const Assembler *Asm);
250   void dump(const char *Message = "");
251 
252   /// Allocate data of type T using the per-Cfg allocator.
allocate()253   template <typename T> T *allocate() { return Allocator->Allocate<T>(); }
254 
255   /// Allocate an array of data of type T using the per-Cfg allocator.
allocateArrayOf(size_t NumElems)256   template <typename T> T *allocateArrayOf(size_t NumElems) {
257     return Allocator->Allocate<T>(NumElems);
258   }
259 
260   /// Deallocate data that was allocated via allocate<T>().
deallocate(T * Object)261   template <typename T> void deallocate(T *Object) {
262     Allocator->Deallocate(Object);
263   }
264 
265   /// Deallocate data that was allocated via allocateArrayOf<T>().
deallocateArrayOf(T * Array)266   template <typename T> void deallocateArrayOf(T *Array) {
267     Allocator->Deallocate(Array);
268   }
269 
270   /// Update Phi labels with InEdges.
271   ///
272   /// The WASM translator cannot always determine the right incoming edge for a
273   /// value due to the CFG being built incrementally. The fixPhiNodes pass fills
274   /// in the correct information once everything is known.
275   void fixPhiNodes();
276 
277 private:
278   friend class CfgAllocatorTraits; // for Allocator access.
279 
280   Cfg(GlobalContext *Ctx, uint32_t SequenceNumber);
281 
282   /// Adds a call to the ProfileSummary runtime function as the first
283   /// instruction in this CFG's entry block.
284   void addCallToProfileSummary();
285 
286   /// Iterates over the basic blocks in this CFG, adding profiling code to each
287   /// one of them. It returns a list with all the globals that the profiling
288   /// code needs to be defined.
289   void profileBlocks();
290 
291   void createNodeNameDeclaration(const std::string &NodeAsmName);
292   void
293   createBlockProfilingInfoDeclaration(const std::string &NodeAsmName,
294                                       VariableDeclaration *NodeNameDeclaration);
295 
296   /// Iterate through the registered jump tables and emit them.
297   void emitJumpTables();
298 
299   enum AllocaBaseVariableType {
300     BVT_StackPointer,
301     BVT_FramePointer,
302     BVT_UserPointer
303   };
304   void sortAndCombineAllocas(CfgVector<InstAlloca *> &Allocas,
305                              uint32_t CombinedAlignment, InstList &Insts,
306                              AllocaBaseVariableType BaseVariableType);
307   void findRematerializable();
308   CfgVector<Inst *>
309   findLoopInvariantInstructions(const CfgUnorderedSet<SizeT> &Body);
310 
311   static ArenaAllocator *createAllocator();
312 
313   GlobalContext *Ctx;
314   uint32_t SequenceNumber; /// output order for emission
315   OptLevel OptimizationLevel = Opt_m1;
316   uint32_t ConstantBlindingCookie = 0; /// cookie for constant blinding
317   VerboseMask VMask;
318   GlobalString FunctionName;
319   Type ReturnType = IceType_void;
320   bool IsInternalLinkage = false;
321   bool HasError = false;
322   bool FocusedTiming = false;
323   std::string ErrorMessage = "";
324   CfgNode *Entry = nullptr; /// entry basic block
325   NodeList Nodes;           /// linearized node list; Entry should be first
326   InstNumberT NextInstNumber;
327   VarList Variables;
328   VarList Args;         /// subset of Variables, in argument order
329   VarList ImplicitArgs; /// subset of Variables
330   // Separate string pools for CfgNode and Variable names, due to a combination
331   // of the uniqueness requirement, and assumptions in lit tests.
332   std::unique_ptr<StringPool> NodeStrings;
333   std::unique_ptr<StringPool> VarStrings;
334   std::unique_ptr<Liveness> Live;
335   std::unique_ptr<TargetLowering> Target;
336   std::unique_ptr<VariablesMetadata> VMetadata;
337   std::unique_ptr<Assembler> TargetAssembler;
338   /// Globals required by this CFG. Mostly used for the profiler's globals.
339   std::unique_ptr<VariableDeclarationList> GlobalInits;
340   CfgVector<InstJumpTable *> JumpTables;
341   /// CurrentNode is maintained during dumping/emitting just for validating
342   /// Variable::DefNode. Normally, a traversal over CfgNodes maintains this, but
343   /// before global operations like register allocation, resetCurrentNode()
344   /// should be called to avoid spurious validation failures.
345   const CfgNode *CurrentNode = nullptr;
346   CfgVector<Loop> LoopInfo;
347 
348 public:
TlsInit()349   static void TlsInit() { CfgAllocatorTraits::init(); }
350 };
351 
352 template <> Variable *Cfg::makeVariable<Variable>(Type Ty);
353 
354 struct NodeStringPoolTraits {
355   using OwnerType = Cfg;
getStringsNodeStringPoolTraits356   static StringPool *getStrings(const OwnerType *PoolOwner) {
357     return PoolOwner->getNodeStrings();
358   }
359 };
360 using NodeString = StringID<NodeStringPoolTraits>;
361 
362 struct VariableStringPoolTraits {
363   using OwnerType = Cfg;
getStringsVariableStringPoolTraits364   static StringPool *getStrings(const OwnerType *PoolOwner) {
365     return PoolOwner->getVarStrings();
366   }
367 };
368 using VariableString = StringID<VariableStringPoolTraits>;
369 
370 } // end of namespace Ice
371 
372 #endif // SUBZERO_SRC_ICECFG_H
373