blob: 89897fa48bbc5bba7d5a5a3125c6869966e36c60 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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;
}
|
