[v1,01/18] graph: build the CFG reverse postorder traversal

Commit Message

Luc Van Oostenryck March 20, 2018, 12:52 a.m. UTC

Do a DFS on the CFG and record the (reverse) postorder.
Use this order for the normal BB traversal (ep->bbs).

Signed-off-by: Luc Van Oostenryck <[e-mail]>
---
 Makefile    |  1 +
 flowgraph.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 flowgraph.h |  8 ++++++++
 linearize.h |  5 ++++-
 4 files changed, 78 insertions(+), 1 deletion(-)
 create mode 100644 flowgraph.c
 create mode 100644 flowgraph.h

Patch

diff --git a/Makefile b/Makefile
index 5548f8483..329e792ff 100644
--- a/Makefile
+++ b/Makefile
@@ -41,6 +41,7 @@  LIB_OBJS += evaluate.o
 LIB_OBJS += expand.o
 LIB_OBJS += expression.o
 LIB_OBJS += flow.o
+LIB_OBJS += flowgraph.o
 LIB_OBJS += inline.o
 LIB_OBJS += lib.o
 LIB_OBJS += linearize.o
diff --git a/flowgraph.c b/flowgraph.c
new file mode 100644
index 000000000..89897fa48
--- /dev/null
+++ b/flowgraph.c
@@ -0,0 +1,65 @@ 
+// SPDX-License-Identifier: MIT
+//
+// Various utilities for flowgraphs.
+//
+// Copyright (c) 2017 Luc Van Oostenryck.
+//
+
+#include "flowgraph.h"
+#include "linearize.h"
+#include "flow.h"			// for bb_generation
+
+
+struct cfg_info {
+	struct basic_block_list *list;
+	unsigned long gen;
+	unsigned int nr;
+};
+
+
+static void label_postorder(struct basic_block *bb, struct cfg_info *info)
+{
+	struct basic_block *child;
+
+	if (bb->generation == info->gen)
+		return;
+
+	bb->generation = info->gen;
+	FOR_EACH_PTR_REVERSE(bb->children, child) {
+		label_postorder(child, info);
+	} END_FOR_EACH_PTR_REVERSE(child);
+
+	bb->postorder_nr = info->nr++;
+	add_bb(&info->list, bb);
+}
+
+static void reverse_bbs(struct basic_block_list **dst, struct basic_block_list *src)
+{
+	struct basic_block *bb;
+	FOR_EACH_PTR_REVERSE(src, bb) {
+		add_bb(dst, bb);
+	} END_FOR_EACH_PTR_REVERSE(bb);
+}
+
+//
+// cfg_postorder - Set the BB's reverse postorder links
+//
+// Do a postorder DFS walk and set the links
+// (which will do the reverse part).
+//
+int cfg_postorder(struct entrypoint *ep)
+{
+	struct cfg_info info = {
+		.gen = ++bb_generation,
+	};
+
+	label_postorder(ep->entry->bb, &info);
+
+	// OK, now info.list contains the node in postorder
+	// Reuse ep->bbs for the reverse postorder.
+	free_ptr_list(&ep->bbs);
+	ep->bbs = NULL;
+	reverse_bbs(&ep->bbs, info.list);
+	free_ptr_list(&info.list);
+	return info.nr;
+}
diff --git a/flowgraph.h b/flowgraph.h
new file mode 100644
index 000000000..676c5b2d8
--- /dev/null
+++ b/flowgraph.h
@@ -0,0 +1,8 @@ 
+#ifndef FLOWGRAPH_H
+#define FLOWGRAPH_H
+
+struct entrypoint;
+
+int cfg_postorder(struct entrypoint *ep);
+
+#endif
diff --git a/linearize.h b/linearize.h
index 8790b7e58..50738a9d8 100644
--- a/linearize.h
+++ b/linearize.h
@@ -257,7 +257,10 @@  struct instruction_list;
 struct basic_block {
 	struct position pos;
 	unsigned long generation;
-	int context;
+	union {
+		int context;
+		int postorder_nr;	/* postorder number */
+	};
 	struct entrypoint *ep;
 	struct basic_block_list *parents; /* sources */
 	struct basic_block_list *children; /* destinations */