Initial skeleton of Subzero.

src/IceCfg.h

+//===- 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.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares the IceCfg class, which represents the control
+// flow graph and the overall per-function compilation context.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SUBZERO_SRC_ICECFG_H
+#define SUBZERO_SRC_ICECFG_H
+
+#include "IceDefs.h"
+#include "IceTypes.h"
+#include "IceGlobalContext.h"
+
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/Support/Allocator.h"
+
+class IceCfg {
+public:
+  IceCfg(IceGlobalContext *Ctx);
+  ~IceCfg();
+
+  IceGlobalContext *getContext() const { return Ctx; }
+
+  // Manage the name and return type of the function being translated.
+  void setName(const IceString &FunctionName) { Name = FunctionName; }
+  IceString getName() const { return Name; }
+  void setReturnType(IceType ReturnType) { Type = ReturnType; }
+
+  // Manage the "internal" attribute of the function.
+  void setInternal(bool Internal) { IsInternal = Internal; }
+  bool getInternal() const { return IsInternal; }
+
+  // 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 IceString &Message);
+  bool hasError() const { return HasError; }
+  IceString getError() const { return ErrorMessage; }
+
+  // Manage nodes (a.k.a. basic blocks, IceCfgNodes).
+  void setEntryNode(IceCfgNode *EntryNode) { Entry = EntryNode; }
+  IceCfgNode *getEntryNode() const { return Entry; }
+  // Create a node and append it to the end of the linearized list.
+  IceCfgNode *makeNode(const IceString &Name = "");

[JF, 2014/04/16 01:27:32]

Your CFG doesn't seem to have an exit node? How do you determine exit, by doing
RPO and traversing?

I get that any block could have a return instruction, but it seems useful for
some algorithms to have an exit node with edges from each of those node.

Or maybe that's just what I'm used to.

[Jim Stichnoth, 2014/04/21 20:26:40]

So far, the only Subzero pass/algorithm that iterates over nodes in non
arbitrary order is liveness analysis.  However, liveness analysis doesn't need
to know about exit nodes.  It just has to iterate over the nodes until
convergence, and convergence may happen sooner iteration happens in reverse
topological order (and the upstream LLVM tools happen to produce a topological
sort).

In any case, the next CL will have a bool IceCfgNode::HasReturn flag in each
node, to help quickly find nodes that need epilog insertion.  This could be
generalized to all exit nodes (not just those that need epilogs) and collected
into IceCfg, but I'd rather hold off until a concrete need arises.

[JF, 2014/04/23 03:51:28]

My point is: if each return is succeeded by the exit node then what you describe
isn't needed :-)

I can wait to see what it looks like next time around.

[Jim Stichnoth, 2014/04/26 15:02:11]

OK, I think what you're saying/suggesting would be absolutely true if lowered
ICE were guaranteed to have a single epilog.  For now, I'm allowing multiple
epilogs in a function until we find a reason to restrict them.

+  uint32_t getNumNodes() const { return Nodes.size(); }
+  const IceNodeList &getNodes() const { return Nodes; }
+
+  // Manage instruction numbering.
+  int newInstNumber() { return NextInstNumber++; }
+
+  // Manage IceVariables.
+  IceVariable *makeVariable(IceType Type, const IceCfgNode *Node,
+                            const IceString &Name = "");
+  uint32_t getNumVariables() const { return Variables.size(); }
+  const IceVarList &getVariables() const { return Variables; }
+
+  // Manage arguments to the function.
+  void addArg(IceVariable *Arg);
+  const IceVarList &getArgs() const { return Args; }
+
+  void registerEdges();

[JF, 2014/04/16 01:27:32]

What does this do?

[Jim Stichnoth, 2014/04/21 20:26:40]

This was documented in IceCfgNode::registerEdges(), but yeah.

I changed the name registerEdges --> computePredecessors and added a bit of
documentation here.

+  void setCurrentNode(const IceCfgNode *Node) { CurrentNode = Node; }
+  const IceCfgNode *getCurrentNode() const { return CurrentNode; }

[JF, 2014/04/16 01:27:32]

What are current nodes in a CFG?

[Jim Stichnoth, 2014/04/21 20:26:40]

This is described in the documentation below of the CurrentNode field.  I added
a bit of text here as well.

However, I'm having second thoughts about this whole approach of incrementally
computing whether variables are entirely block-local, versus "global".  It might
be better, less fragile, to construct this information in a separate pass.

[JF, 2014/04/23 03:51:28]

As discussed offline, add a TODO to remove the premature optimization later
(since it will be used in the next CL).

[Jim Stichnoth, 2014/04/26 15:02:11]

Done.

+  void dump();

[JF, 2014/04/16 01:27:32]

Your other dump functions seem to take in a stream to dump to.

[Jim Stichnoth, 2014/04/21 20:26:40]

Are you looking at the latest patchset?  The dump() routines are now taking an
IceCfg* argument, which seems unnecessary for IceCfg::dump().

+
+  // Allocate data of type T using the per-Cfg allocator.
+  template <typename T> T *allocate() { return Allocator.Allocate<T>(); }
+
+  // Allocate an instruction of type T using the per-Cfg instruction allocator.
+  template <typename T> T *allocateInst() { 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);
+  }
+
+private:
+  // TODO: for now, everything is allocated from the same allocator. In the
+  // future we may want to split this to several allocators, for example in
+  // order to use a "Recycler" to preserve memory. If we keep all allocation
+  // requests from the Cfg exposed via methods, we can always switch the
+  // implementation over at a later point.
+  llvm::BumpPtrAllocator Allocator;
+
+  IceGlobalContext *Ctx;
+  IceString Name;  // function name
+  IceType Type;    // return type
+  bool IsInternal; // internal linkage

[JF, 2014/04/16 01:27:32]

The comments above could just be the variable names instead.

[Jim Stichnoth, 2014/04/21 20:26:40]

Done.

+  bool HasError;

[JF, 2014/04/16 01:27:32]

Isn't that just ErrorMessage.size() != 0 ?

[Jim Stichnoth, 2014/04/21 20:26:40]

Not if you call setError("blah") followed by setError("").  Once an error,
always an error.

There's no strong need to save a word of space at the CFG level, so I'd prefer
not to use sentinel values here.

+  IceString ErrorMessage;
+  IceCfgNode *Entry; // entry basic block
+  IceNodeList Nodes; // linearized node list; Entry should be first
+  int NextInstNumber;
+  IceVarList Variables;
+  IceVarList Args; // subset of Variables, in argument order
+
+  // CurrentNode is maintained during dumping/emitting just for
+  // validating IceVariable::DefNode.  Normally, a traversal over
+  // IceCfgNodes maintains this, but before global operations like
+  // register allocation, setCurrentNode(NULL) should be called to
+  // avoid spurious validation failures.
+  const IceCfgNode *CurrentNode;
+
+  IceCfg(const IceCfg &) LLVM_DELETED_FUNCTION;
+  IceCfg &operator=(const IceCfg &) LLVM_DELETED_FUNCTION;
+};
+
+#endif // SUBZERO_SRC_ICECFG_H