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 /flowgraph.c | |
| 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>
Diffstat (limited to 'flowgraph.c')
| -rw-r--r-- | flowgraph.c | 65 |
1 files changed, 65 insertions, 0 deletions
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; +} |