blob: 3a3dcbfdf709392c088b0e6ca4e6a3ec08e2ffba [file] [log] [blame]
//===- subzero/src/IceCfg.h - Control flow graph ----------------*- C++ -*-===//
// The Subzero Code Generator
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
/// \file
/// \brief Declares the Cfg class, which represents the control flow graph and
/// the overall per-function compilation context.
#include "IceAssembler.h"
#include "IceClFlags.h"
#include "IceDefs.h"
#include "IceGlobalContext.h"
#include "IceLoopAnalyzer.h"
#include "IceStringPool.h"
#include "IceTypes.h"
namespace Ice {
class Cfg {
Cfg() = delete;
Cfg(const Cfg &) = delete;
Cfg &operator=(const Cfg &) = delete;
std::unique_ptr<ArenaAllocator> Allocator;
static std::unique_ptr<Cfg> create(GlobalContext *Ctx,
uint32_t SequenceNumber) {
return std::unique_ptr<Cfg>(new Cfg(Ctx, SequenceNumber));
GlobalContext *getContext() const { return Ctx; }
uint32_t getSequenceNumber() const { return SequenceNumber; }
OptLevel getOptLevel() const { return OptimizationLevel; }
static constexpr VerboseMask defaultVerboseMask() {
return (IceV_NO_PER_PASS_DUMP_BEYOND << 1) - 1;
/// Returns true if any of the specified options in the verbose mask are set.
/// If the argument is omitted, it checks if any verbose options at all are
/// set.
bool isVerbose(VerboseMask Mask = defaultVerboseMask()) const {
return VMask & Mask;
void setVerbose(VerboseMask Mask) { VMask = Mask; }
/// \name Manage the name and return type of the function being translated.
/// @{
void setFunctionName(GlobalString Name) { FunctionName = Name; }
GlobalString getFunctionName() const { return FunctionName; }
std::string getFunctionNameAndSize() const;
void setReturnType(Type Ty) { ReturnType = Ty; }
Type getReturnType() const { return ReturnType; }
/// @}
/// \name Manage the "internal" attribute of the function.
/// @{
void setInternal(bool Internal) { IsInternalLinkage = Internal; }
bool getInternal() const { return IsInternalLinkage; }
/// @}
/// \name Manage errors.
/// @{
/// Translation error flagging. If support for some construct is known to be
/// missing, instead of an assertion failure, setError() should be called and
/// the error should be propagated back up. This way, we can gracefully fail
/// to translate and let a fallback translator handle the function.
void setError(const std::string &Message);
bool hasError() const { return HasError; }
std::string getError() const { return ErrorMessage; }
/// @}
/// \name Manage nodes (a.k.a. basic blocks, CfgNodes).
/// @{
void setEntryNode(CfgNode *EntryNode) { Entry = EntryNode; }
CfgNode *getEntryNode() const { return Entry; }
/// Create a node and append it to the end of the linearized list. The loop
/// nest depth of the new node may not be valid if it is created after
/// computeLoopNestDepth.
CfgNode *makeNode();
SizeT getNumNodes() const { return Nodes.size(); }
const NodeList &getNodes() const { return Nodes; }
/// Swap nodes of Cfg with given list of nodes. The number of nodes must
/// remain unchanged.
void swapNodes(NodeList &NewNodes);
/// @}
/// String pool for CfgNode::Name values.
StringPool *getNodeStrings() const { return NodeStrings.get(); }
/// String pool for Variable::Name values.
StringPool *getVarStrings() const { return VarStrings.get(); }
/// \name Manage instruction numbering.
/// @{
InstNumberT newInstNumber() { return NextInstNumber++; }
InstNumberT getNextInstNumber() const { return NextInstNumber; }
/// @}
/// \name Manage Variables.
/// @{
/// Create a new Variable with a particular type and an optional name. The
/// Node argument is the node where the variable is defined.
// TODO(jpp): untemplate this with separate methods: makeVariable and
// makeStackVariable.
template <typename T = Variable> T *makeVariable(Type Ty) {
SizeT Index = Variables.size();
auto *Var = T::create(this, Ty, Index);
return Var;
SizeT getNumVariables() const { return Variables.size(); }
const VarList &getVariables() const { return Variables; }
/// @}
/// \name Manage arguments to the function.
/// @{
void addArg(Variable *Arg);
const VarList &getArgs() const { return Args; }
VarList &getArgs() { return Args; }
void addImplicitArg(Variable *Arg);
const VarList &getImplicitArgs() const { return ImplicitArgs; }
/// @}
/// \name Manage the jump tables.
/// @{
void addJumpTable(InstJumpTable *JumpTable) {
/// @}
/// \name Manage the Globals used by this function.
/// @{
std::unique_ptr<VariableDeclarationList> getGlobalInits() {
return std::move(GlobalInits);
void addGlobal(VariableDeclaration *Global) {
if (GlobalInits == nullptr) {
GlobalInits.reset(new VariableDeclarationList);
VariableDeclarationList *getGlobalPool() {
if (GlobalInits == nullptr) {
GlobalInits.reset(new VariableDeclarationList);
return GlobalInits.get();
/// @}
/// \name Miscellaneous accessors.
/// @{
TargetLowering *getTarget() const { return Target.get(); }
VariablesMetadata *getVMetadata() const { return VMetadata.get(); }
Liveness *getLiveness() const { return Live.get(); }
template <typename T = Assembler> T *getAssembler() const {
return llvm::dyn_cast<T>(TargetAssembler.get());
std::unique_ptr<Assembler> releaseAssembler() {
return std::move(TargetAssembler);
bool hasComputedFrame() const;
bool getFocusedTiming() const { return FocusedTiming; }
void setFocusedTiming() { FocusedTiming = true; }
uint32_t getConstantBlindingCookie() const { return ConstantBlindingCookie; }
/// @}
/// Returns true if Var is a global variable that is used by the profiling
/// code.
static bool isProfileGlobal(const VariableDeclaration &Var);
/// Passes over the CFG.
void translate();
/// After the CFG is fully constructed, iterate over the nodes and compute the
/// predecessor and successor edges, in the form of CfgNode::InEdges[] and
/// CfgNode::OutEdges[].
void computeInOutEdges();
/// Renumber the non-deleted instructions in the Cfg. This needs to be done
/// in preparation for live range analysis. The instruction numbers in a
/// block must be monotonically increasing. The range of instruction numbers
/// in a block, from lowest to highest, must not overlap with the range of any
/// other block.
/// Also, if the configuration specifies to do so, remove/unlink all deleted
/// instructions from the Cfg, to speed up later passes over the instructions.
void renumberInstructions();
void placePhiLoads();
void placePhiStores();
void deletePhis();
void advancedPhiLowering();
void reorderNodes();
void shuffleNodes();
void localCSE(bool AssumeSSA);
void floatConstantCSE();
void shortCircuitJumps();
void loopInvariantCodeMotion();
/// Scan allocas to determine whether we need to use a frame pointer.
/// If SortAndCombine == true, merge all the fixed-size allocas in the
/// entry block and emit stack or frame pointer-relative addressing.
void processAllocas(bool SortAndCombine);
void doAddressOpt();
/// Find clusters of insertelement/extractelement instructions that can be
/// replaced by a shufflevector instruction.
void materializeVectorShuffles();
void doArgLowering();
void doNopInsertion();
void genCode();
void genFrame();
void generateLoopInfo();
void livenessLightweight();
void liveness(LivenessMode Mode);
bool validateLiveness() const;
void contractEmptyNodes();
void doBranchOpt();
void markNodesForSandboxing();
/// \name Manage the CurrentNode field.
/// CurrentNode is used for validating the Variable::DefNode field during
/// dumping/emitting.
/// @{
void setCurrentNode(const CfgNode *Node) { CurrentNode = Node; }
void resetCurrentNode() { setCurrentNode(nullptr); }
const CfgNode *getCurrentNode() const { return CurrentNode; }
/// @}
/// Get the total amount of memory held by the per-Cfg allocator.
size_t getTotalMemoryMB() const;
/// Get the current memory usage due to liveness data structures.
size_t getLivenessMemoryMB() const;
void emit();
void emitIAS();
static void emitTextHeader(GlobalString Name, GlobalContext *Ctx,
const Assembler *Asm);
void dump(const char *Message = "");
/// Allocate data of type T using the per-Cfg allocator.
template <typename T> T *allocate() { return Allocator->Allocate<T>(); }
/// Allocate an array of data of type T using the per-Cfg allocator.
template <typename T> T *allocateArrayOf(size_t NumElems) {
return Allocator->Allocate<T>(NumElems);
/// Deallocate data that was allocated via allocate<T>().
template <typename T> void deallocate(T *Object) {
/// Deallocate data that was allocated via allocateArrayOf<T>().
template <typename T> void deallocateArrayOf(T *Array) {
/// Update Phi labels with InEdges.
/// The WASM translator cannot always determine the right incoming edge for a
/// value due to the CFG being built incrementally. The fixPhiNodes pass fills
/// in the correct information once everything is known.
void fixPhiNodes();
friend class CfgAllocatorTraits; // for Allocator access.
Cfg(GlobalContext *Ctx, uint32_t SequenceNumber);
/// Adds a call to the ProfileSummary runtime function as the first
/// instruction in this CFG's entry block.
void addCallToProfileSummary();
/// Iterates over the basic blocks in this CFG, adding profiling code to each
/// one of them. It returns a list with all the globals that the profiling
/// code needs to be defined.
void profileBlocks();
void createNodeNameDeclaration(const std::string &NodeAsmName);
createBlockProfilingInfoDeclaration(const std::string &NodeAsmName,
VariableDeclaration *NodeNameDeclaration);
/// Iterate through the registered jump tables and emit them.
void emitJumpTables();
enum AllocaBaseVariableType {
void sortAndCombineAllocas(CfgVector<InstAlloca *> &Allocas,
uint32_t CombinedAlignment, InstList &Insts,
AllocaBaseVariableType BaseVariableType);
void findRematerializable();
CfgVector<Inst *>
findLoopInvariantInstructions(const CfgUnorderedSet<SizeT> &Body);
static ArenaAllocator *createAllocator();
GlobalContext *Ctx;
uint32_t SequenceNumber; /// output order for emission
OptLevel OptimizationLevel = Opt_m1;
uint32_t ConstantBlindingCookie = 0; /// cookie for constant blinding
VerboseMask VMask;
GlobalString FunctionName;
Type ReturnType = IceType_void;
bool IsInternalLinkage = false;
bool HasError = false;
bool FocusedTiming = false;
std::string ErrorMessage = "";
CfgNode *Entry = nullptr; /// entry basic block
NodeList Nodes; /// linearized node list; Entry should be first
InstNumberT NextInstNumber;
VarList Variables;
VarList Args; /// subset of Variables, in argument order
VarList ImplicitArgs; /// subset of Variables
// Separate string pools for CfgNode and Variable names, due to a combination
// of the uniqueness requirement, and assumptions in lit tests.
std::unique_ptr<StringPool> NodeStrings;
std::unique_ptr<StringPool> VarStrings;
std::unique_ptr<Liveness> Live;
std::unique_ptr<TargetLowering> Target;
std::unique_ptr<VariablesMetadata> VMetadata;
std::unique_ptr<Assembler> TargetAssembler;
/// Globals required by this CFG. Mostly used for the profiler's globals.
std::unique_ptr<VariableDeclarationList> GlobalInits;
CfgVector<InstJumpTable *> JumpTables;
/// CurrentNode is maintained during dumping/emitting just for validating
/// Variable::DefNode. Normally, a traversal over CfgNodes maintains this, but
/// before global operations like register allocation, resetCurrentNode()
/// should be called to avoid spurious validation failures.
const CfgNode *CurrentNode = nullptr;
CfgVector<Loop> LoopInfo;
static void TlsInit() { CfgAllocatorTraits::init(); }
template <> Variable *Cfg::makeVariable<Variable>(Type Ty);
struct NodeStringPoolTraits {
using OwnerType = Cfg;
static StringPool *getStrings(const OwnerType *PoolOwner) {
return PoolOwner->getNodeStrings();
using NodeString = StringID<NodeStringPoolTraits>;
struct VariableStringPoolTraits {
using OwnerType = Cfg;
static StringPool *getStrings(const OwnerType *PoolOwner) {
return PoolOwner->getVarStrings();
using VariableString = StringID<VariableStringPoolTraits>;
} // end of namespace Ice