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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
%-----------------------------------------------------------------------------%
% Copyright (C) 1997-1999 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
%
% Main author: zs.
%
% This module defines a representation for basic blocks, sequences of
% instructions with one entry and one exit, and provides predicates
% that convert a list of instructions into a list of basic blocks
% and vice versa.
%-----------------------------------------------------------------------------%
:- module basic_block.
:- interface.
:- import_module llds.
:- import_module list, map, std_util.
:- type block_map == map(label, block_info).
:- type block_info
---> block_info(
label,
% The label starting the block.
instruction,
% The instruction containing the label.
list(instruction),
% The code of the block without the initial
% label.
list(label),
% The labels we can jump to
% (not falling through).
maybe(label)
% The label we fall through to
% (if there is one).
).
:- pred create_basic_blocks(list(instruction)::in, list(instruction)::out,
proc_label::out, int::out, list(label)::out, block_map::out) is det.
:- pred flatten_basic_blocks(list(label)::in, block_map::in,
list(instruction)::out) is det.
%-----------------------------------------------------------------------------%
:- implementation.
:- import_module opt_util.
:- import_module bool, int, require.
create_basic_blocks(Instrs0, Comments, ProcLabel, N,
LabelSeq, BlockMap) :-
opt_util__get_prologue(Instrs0, ProcLabel, LabelInstr,
Comments, AfterLabelInstrs),
Instrs1 = [LabelInstr | AfterLabelInstrs],
opt_util__new_label_no(Instrs0, 1000, N0),
map__init(BlockMap0),
build_block_map(Instrs1, LabelSeq, BlockMap0, BlockMap,
ProcLabel, N0, N).
% Add labels to the given instruction sequence so that
% every basic block has labels around it.
%-----------------------------------------------------------------------------%
:- pred build_block_map(list(instruction)::in, list(label)::out,
block_map::in, block_map::out, proc_label::in, int::in, int::out)
is det.
build_block_map([], [], BlockMap, BlockMap, _, N, N).
build_block_map([OrigInstr0 | OrigInstrs0], LabelSeq, BlockMap0, BlockMap,
ProcLabel, N0, N) :-
( OrigInstr0 = label(OrigLabel) - _ ->
Label = OrigLabel,
LabelInstr = OrigInstr0,
RestInstrs = OrigInstrs0,
N1 = N0
;
N1 is N0 + 1,
Label = local(ProcLabel, N0),
LabelInstr = label(Label) - "",
RestInstrs = [OrigInstr0 | OrigInstrs0]
),
(
take_until_end_of_block(RestInstrs, BlockInstrs, Instrs1),
build_block_map(Instrs1, LabelSeq0,
BlockMap0, BlockMap1, ProcLabel, N1, N),
( list__last(BlockInstrs, LastInstr) ->
LastInstr = LastUinstr - _,
possible_targets(LastUinstr, SideLabels),
opt_util__can_instr_fall_through(LastUinstr,
CanFallThrough),
( CanFallThrough = yes ->
get_fallthrough_from_seq(LabelSeq0,
MaybeFallThrough)
;
MaybeFallThrough = no
)
;
SideLabels = [],
get_fallthrough_from_seq(LabelSeq0,
MaybeFallThrough)
),
BlockInfo = block_info(Label, LabelInstr, BlockInstrs,
SideLabels, MaybeFallThrough),
map__det_insert(BlockMap1, Label, BlockInfo, BlockMap),
LabelSeq = [Label | LabelSeq0]
).
%-----------------------------------------------------------------------------%
:- pred take_until_end_of_block(list(instruction)::in,
list(instruction)::out, list(instruction)::out) is det.
take_until_end_of_block([], [], []).
take_until_end_of_block([Instr0 | Instrs0], BlockInstrs, Rest) :-
Instr0 = Uinstr0 - _Comment,
( Uinstr0 = label(_) ->
BlockInstrs = [],
Rest = [Instr0 | Instrs0]
; opt_util__can_instr_branch_away(Uinstr0, yes) ->
BlockInstrs = [Instr0],
Rest = Instrs0
;
take_until_end_of_block(Instrs0, BlockInstrs1, Rest),
BlockInstrs = [Instr0 | BlockInstrs1]
).
%-----------------------------------------------------------------------------%
:- pred get_fallthrough_from_seq(list(label)::in, maybe(label)::out) is det.
get_fallthrough_from_seq(LabelSeq, MaybeFallThrough) :-
( LabelSeq = [NextLabel | _] ->
MaybeFallThrough = yes(NextLabel)
;
MaybeFallThrough = no
).
%-----------------------------------------------------------------------------%
flatten_basic_blocks([], _, []).
flatten_basic_blocks([Label | Labels], BlockMap, Instrs) :-
flatten_basic_blocks(Labels, BlockMap, RestInstrs),
map__lookup(BlockMap, Label, BlockInfo),
BlockInfo = block_info(_, BlockLabelInstr, BlockInstrs, _, _),
list__append([BlockLabelInstr | BlockInstrs], RestInstrs, Instrs).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
|
