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