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 <luc.vanoostenryck@xxxxxxxxx>
---
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
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 */
--
2.16.2
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
