diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2017-08-26 06:42:39 +0200 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-01 00:18:44 +0200 |
| commit | 8cc064e5c87bdebbdf6528cf77dd4a4ad6161fa2 (patch) | |
| tree | c1dbf562c2815572c7c6aeba58a9df975fd5a87e | |
| parent | d64adff1bac01dbb9c574655540328be434779f6 (diff) | |
| download | sparse-dev-8cc064e5c87bdebbdf6528cf77dd4a4ad6161fa2.tar.gz | |
graph: build the CFG reverse postorder traversal
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@gmail.com>
| -rw-r--r-- | Makefile | 1 | ||||
| -rw-r--r-- | flowgraph.c | 65 | ||||
| -rw-r--r-- | flowgraph.h | 8 | ||||
| -rw-r--r-- | linearize.h | 5 |
4 files changed, 78 insertions, 1 deletions
@@ -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 += ir.o LIB_OBJS += lib.o diff --git a/flowgraph.c b/flowgraph.c new file mode 100644 index 00000000..89897fa4 --- /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 00000000..676c5b2d --- /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 092e1ac2..c52c6ca5 100644 --- a/linearize.h +++ b/linearize.h @@ -265,7 +265,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 */ |