1%% -*- Erlang -*-
2%% -*- erlang-indent-level: 2 -*-
3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4%%
5%% Licensed under the Apache License, Version 2.0 (the "License");
6%% you may not use this file except in compliance with the License.
7%% You may obtain a copy of the License at
8%%
9%%     http://www.apache.org/licenses/LICENSE-2.0
10%%
11%% Unless required by applicable law or agreed to in writing, software
12%% distributed under the License is distributed on an "AS IS" BASIS,
13%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14%% See the License for the specific language governing permissions and
15%% limitations under the License.
16%%
17%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
18%%
19%%			 CONTROL FLOW GRAPHS
20%%
21%% Construct and manipulate the control flow graph of a function (program?).
22%%
23%% Exports:
24%% ~~~~~~~~
25%%  init(Code) - makes a CFG out of code.
26%%  bb(CFG, Label) - returns the basic block named 'Label' from the CFG.
27%%  bb_add(CFG, Label, NewBB) - makes NewBB the basic block associated
28%%       with Label.
29%%  map_bbs(Fun, CFG) - map over all code without changing control flow.
30%%  fold_bbs(Fun, Acc, CFG) - fold over the basic blocks in a CFG.
31%%  succ(Map, Label) - returns a list of successors of basic block 'Label'.
32%%  pred(Map, Label) - returns the predecessors of basic block 'Label'.
33%%  fallthrough(CFG, Label) - returns fall-through successor of basic
34%%       block 'Label' (or 'none').
35%%  conditional(CFG, Label) - returns conditional successor (or 'none')
36%%  start_label(CFG) - returns the label of the entry basic block.
37%%  params(CFG) - returns the list of parameters to the CFG.
38%%  labels(CFG) - returns a list of labels of all basic blocks in the CFG.
39%%  postorder(CFG) - returns a list of labels in postorder.
40%%  reverse_postorder(CFG) - returns a list of labels in reverse postorder.
41%%  cfg_to_linear(CFG) - converts CFG to linearized code.
42%%  remove_trivial_bbs(CFG) - removes empty BBs or BBs with only a goto.
43%%  remove_unreachable_code(CFG) - removes unreachable BBs.
44%%
45%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
46%%
47%% TODO:
48%%
49%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
50
51%%=====================================================================
52%% The following are ugly as hell, but what else can I do???
53%%=====================================================================
54
55-ifdef(GEN_CFG).
56-define(PRED_NEEDED,true).
57-endif.
58
59-ifdef(ICODE_CFG).
60-define(CLOSURE_ARITY_NEEDED,true).
61-define(INFO_NEEDED,true).
62-define(PARAMS_NEEDED,true).
63-define(PARAMS_UPDATE_NEEDED,true).
64-define(PRED_NEEDED,true).
65-define(REMOVE_TRIVIAL_BBS_NEEDED,true).
66-define(REMOVE_UNREACHABLE_CODE,true).
67-define(START_LABEL_UPDATE_NEEDED,true).
68-define(CFG_CAN_HAVE_PHI_NODES,true).
69-endif.
70
71-ifdef(RTL_CFG).
72-define(PREORDER,true).
73-define(FIND_NEW_LABEL_NEEDED,true).
74-define(INFO_NEEDED,true).
75-define(PARAMS_NEEDED,true).
76-define(PARAMS_UPDATE_NEEDED,true).
77-define(PRED_NEEDED,true).
78-define(REMOVE_TRIVIAL_BBS_NEEDED,true).
79-define(REMOVE_UNREACHABLE_CODE,true).
80-define(START_LABEL_UPDATE_NEEDED,true).
81-define(CFG_CAN_HAVE_PHI_NODES,true).
82-endif.
83
84-ifdef(SPARC_CFG).
85-define(BREADTH_ORDER,true). % for linear scan
86-define(PARAMS_NEEDED,true).
87-define(START_LABEL_UPDATE_NEEDED,true).
88-define(MAP_FOLD_NEEDED,true).
89-endif.
90
91%%=====================================================================
92
93-ifdef(START_LABEL_UPDATE_NEEDED).
94-export([start_label_update/2]).
95-endif.
96
97-ifdef(BREADTH_ORDER).
98-export([breadthorder/1]).
99-endif.
100
101-compile(inline).
102
103%%=====================================================================
104%%
105%% Interface functions that MUST be implemented in the including file:
106%%
107%% linear_to_cfg(LinearCode) -> CFG, constructs the cfg.
108%% is_label(Instr) -> boolean(), true if instruction is a label.
109%% label_name(Instr) -> term(), the name of a label.
110%% branch_successors(Instr) -> [term()], the successors of a branch.
111%% fails_to(Instr) -> [term()], the fail-successors of an instruction.
112%% is_branch(Instr) -> boolean(), true if instruction is a branch.
113%% is_comment(Instr) -> boolean(),
114%%       true if instruction is a comment, used by remove dead code.
115%% is_goto(Instr) -> boolean(),
116%%       true if instruction is a pure goto, used by remove dead code.
117%% redirect_jmp(Jmp, ToOld, ToNew) -> NewJmp,
118%% redirect_ops(Labels, CFG, Map) -> CFG.
119%%       Rewrite instructions with labels in operands to use
120%%       the new label as given by map.
121%%       Use find_new_label(OldLab,Map) to get the new label.
122%%       (See hipe_sparc_cfg for example)
123%% pp(CFG) -> ok, do some nifty output.
124%% cfg_to_linear(CFG) -> LinearCode, linearizes the code of CFG
125%% mk_goto(Label) -> instruction
126%% is_phi(Instr) -> boolean(), true if the instruction is a phi-instruction.
127%% phi_remove_pred(PhiInstr, Pred) -> NewPhi,
128%%       Removes the predecessor Pred from the phi instruction.
129%% highest_var(Code) -> term(),
130%%       Returns the highest variable used or defined in the code.
131%%
132%%=====================================================================
133
134%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
135%%
136%% Primitives (not all of these are exported)
137%%
138
139-spec start_label(cfg()) -> cfg_lbl().
140start_label(CFG) -> (CFG#cfg.info)#cfg_info.start_label.
141
142-ifndef(GEN_CFG).
143-spec start_label_update(cfg(), cfg_lbl()) -> cfg().
144start_label_update(CFG, NewStartLabel) ->
145  Info = CFG#cfg.info,
146  CFG#cfg{info = Info#cfg_info{start_label = NewStartLabel}}.
147
148-spec function(cfg()) -> mfa().
149function(CFG) -> (CFG#cfg.info)#cfg_info.'fun'.
150
151-spec is_closure(cfg()) -> boolean().
152is_closure(CFG) -> (CFG#cfg.info)#cfg_info.is_closure.
153
154-spec is_leaf(cfg()) -> boolean().
155is_leaf(CFG) -> (CFG#cfg.info)#cfg_info.is_leaf.
156
157mk_empty_cfg(Fun, StartLbl, Data, Closure, Leaf, Params) ->
158  Info = #cfg_info{'fun' = Fun,
159		   start_label = StartLbl,
160		   is_closure = Closure,
161		   is_leaf = Leaf,
162		   params = Params},
163  #cfg{table = gb_trees:empty(), data = Data, info = Info}.
164
165data(CFG) -> CFG#cfg.data.
166-endif.	% GEN_CFG
167
168-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
169-spec update_data(cfg(), cfg_data()) -> cfg().
170update_data(CFG, D) ->
171  CFG#cfg{data = D}.
172-endif.
173
174-ifdef(PARAMS_NEEDED).
175params(CFG) -> (CFG#cfg.info)#cfg_info.params.
176-endif.
177
178-ifdef(PARAMS_UPDATE_NEEDED).
179params_update(CFG, NewParams) ->
180  Info = CFG#cfg.info,
181  CFG#cfg{info = Info#cfg_info{params = NewParams}}.
182-endif.
183
184-ifdef(CLOSURE_ARITY_NEEDED).
185-spec closure_arity(cfg()) -> arity().
186closure_arity(CFG) ->
187  Info = CFG#cfg.info,
188  Info#cfg_info.closure_arity.
189
190-spec closure_arity_update(cfg(), arity()) -> cfg().
191closure_arity_update(CFG, Arity) ->
192  Info = CFG#cfg.info,
193  CFG#cfg{info = Info#cfg_info{closure_arity = Arity}}.
194-endif.
195
196%% %% Don't forget to do a start_label_update if necessary.
197%% update_code(CFG, NewCode) ->
198%%   take_bbs(NewCode, CFG).
199
200-ifdef(INFO_NEEDED).
201info(CFG) -> (CFG#cfg.info)#cfg_info.info.
202%% info_add(CFG, A) ->
203%%    As = info(CFG),
204%%    Info = CFG#cfg.info,
205%%    CFG#cfg{info = Info#cfg_info{info = [A|As]}}.
206info_update(CFG, I) ->
207  Info = CFG#cfg.info,
208  CFG#cfg{info = Info#cfg_info{info = I}}.
209-endif.
210
211%%=====================================================================
212-ifndef(GEN_CFG).
213
214-spec other_entrypoints(cfg()) -> [cfg_lbl()].
215%% @doc Returns a list of labels that are referred to from the data section.
216
217other_entrypoints(CFG) ->
218  hipe_consttab:referred_labels(data(CFG)).
219
220%% is_entry(Lbl, CFG) ->
221%%   Lbl =:= start_label(CFG) orelse
222%% 	lists:member(Lbl, other_entrypoints(CFG)).
223
224%% @spec bb(CFG::cfg(), Label::cfg_lbl()) -> basic_block()
225%% @doc  Returns the basic block of the CFG which begins at the Label.
226bb(CFG, Label) ->
227  HT = CFG#cfg.table,
228  case gb_trees:lookup(Label, HT) of
229    {value, {Block,_Succ,_Pred}} ->
230      Block;
231    none ->
232      not_found
233  end.
234
235%% Remove duplicates from a list. The first instance (in left-to-right
236%% order) of an element is kept, remaining instances are removed.
237-spec remove_duplicates([cfg_lbl()]) -> [cfg_lbl()].
238remove_duplicates(List) ->
239  remove_duplicates(List, []).
240
241-spec remove_duplicates([cfg_lbl()], [cfg_lbl()]) -> [cfg_lbl()].
242remove_duplicates([H|T], Acc) ->
243  NewAcc =
244    case lists:member(H, Acc) of
245      false -> [H|Acc];
246      true -> Acc
247    end,
248  remove_duplicates(T, NewAcc);
249remove_duplicates([], Acc) ->
250  lists:reverse(Acc).
251
252
253-ifdef(RTL_CFG).	%% this could be CFG_CAN_HAVE_PHI_NODES
254			%% if Icode also starts using this function
255
256%% @spec bb_insert_between(CFG::cfg(),
257%%                         Label::cfg_lbl(), NewBB::basic_block(),
258%%                         Pred::cfg_lbl(), Succ::cfg_lbl()) -> cfg()
259%%
260%% @doc Insert the new basic block with label Label in the edge from
261%%      Pred to Succ
262
263bb_insert_between(CFG, Label, NewBB, Pred, Succ) ->
264  Last = hipe_bb:last(NewBB),
265  %% Asserts that NewBB ends in a label
266  true = is_branch(Last),
267  %% Asserts that the only Successor of NewBB is Succ
268  [Succ] = remove_duplicates(branch_successors(Last)),
269  HT = CFG#cfg.table,
270  %% Asserts that Label does not exist in the CFG
271  none = gb_trees:lookup(Label, HT),
272  %% Updates the predecessor of NewBB
273  {value, {PBB, PSucc, PPred}} = gb_trees:lookup(Pred, HT),
274  NewPSucc = [Label|lists:delete(Succ, PSucc)],
275  PLast = hipe_bb:last(PBB),
276  PButLast = hipe_bb:butlast(PBB),
277  NewPBB = hipe_bb:code_update(PBB, PButLast++[redirect_jmp(PLast, Succ, Label)]),
278  HT1 = gb_trees:update(Pred, {NewPBB,NewPSucc,PPred}, HT),
279  %% Updates the successor of NewBB
280  {value, {SBB, SSucc, SPred}} = gb_trees:lookup(Succ, HT1),
281  NewSPred = [Label|lists:delete(Pred, SPred)],
282  SCode = hipe_bb:code(SBB),
283  NewSCode = redirect_phis(SCode, Pred, Label, []),
284  NewSBB = hipe_bb:code_update(SBB, NewSCode),
285  HT2 = gb_trees:update(Succ, {NewSBB,SSucc,NewSPred}, HT1),
286  %% Enters NewBB into the CFG
287  HT3 = gb_trees:insert(Label, {NewBB,[Succ],[Pred]}, HT2),
288  CFG#cfg{table = HT3}.
289
290redirect_phis([], _OldPred, _NewPred, Acc) ->
291  lists:reverse(Acc);
292redirect_phis([I|Rest], OldPred, NewPred, Acc) ->
293  case is_phi(I) of
294    true ->
295      Phi = phi_redirect_pred(I, OldPred, NewPred),
296      redirect_phis(Rest, OldPred, NewPred, [Phi|Acc]);
297    false ->
298      redirect_phis(Rest, OldPred, NewPred, [I|Acc])
299  end.
300
301-endif.
302
303%% @spec bb_add(CFG::cfg(), Label::cfg_lbl(), NewBB::basic_block()) -> cfg()
304%% @doc  Adds a new basic block to a CFG (or updates an existing block).
305bb_add(CFG, Label, NewBB) ->
306  %% Asserting that the NewBB is a legal basic block
307  Last = assert_bb(NewBB),
308  %% The order of the elements from branch_successors/1 is
309  %% significant. It determines the basic block order when the CFG is
310  %% converted to linear form. That order may have been tuned for
311  %% branch prediction purposes.
312  Succ = remove_duplicates(branch_successors(Last)),
313  HT = CFG#cfg.table,
314  {OldSucc, OldPred} = case gb_trees:lookup(Label, HT) of
315			 {value, {_Block, OSucc, OPred}} ->
316			   {OSucc, OPred};
317			 none ->
318		           {[], []}
319		       end,
320  %% Change this block to contain new BB and new successors, but keep
321  %% the old predecessors which will be updated in the following steps
322  HT1 = gb_trees:enter(Label, {NewBB, Succ, OldPred}, HT),
323  %% Add this block as predecessor to its new successors
324  HT2 = lists:foldl(fun (P, HTAcc) ->
325		      add_pred(HTAcc, P, Label)
326		    end,
327		    HT1, Succ -- OldSucc),
328  %% Remove this block as predecessor of its former successors
329  HT3 = lists:foldl(fun (S, HTAcc) ->
330		      remove_pred(HTAcc, S, Label)
331		    end,
332		    HT2, OldSucc -- Succ),
333  CFG#cfg{table = HT3}.
334
335-ifdef(MAP_FOLD_NEEDED).
336-spec map_bbs(fun((cfg_lbl(), hipe_bb:bb()) -> hipe_bb:bb()), cfg()) -> cfg().
337%% @doc  Map over the code in a CFG without changing any control flow.
338map_bbs(Fun, CFG = #cfg{table=HT0}) ->
339    HT = gb_trees:map(
340	   fun(Lbl, {OldBB, OldSucc, OldPred}) ->
341		   NewBB = Fun(Lbl, OldBB),
342		   %% Assert preconditions
343		   NewLast = assert_bb(NewBB),
344		   OldSucc = remove_duplicates(branch_successors(NewLast)),
345		   {NewBB, OldSucc, OldPred}
346	   end, HT0),
347    CFG#cfg{table=HT}.
348
349-spec fold_bbs(fun((cfg_lbl(), hipe_bb:bb(), Acc) -> Acc), Acc, cfg()) -> Acc.
350%% @doc  Fold over the basic blocks in a CFG in unspecified order.
351fold_bbs(Fun, InitAcc, #cfg{table=HT}) ->
352    gb_trees_fold(fun(Lbl, {BB, _, _}, Acc) -> Fun(Lbl, BB, Acc) end,
353		  InitAcc, HT).
354
355gb_trees_fold(Fun, InitAcc, Tree) ->
356    gb_trees_fold_1(Fun, InitAcc, gb_trees:iterator(Tree)).
357
358gb_trees_fold_1(Fun, InitAcc, Iter0) ->
359    case gb_trees:next(Iter0) of
360	none -> InitAcc;
361	{Key, Value, Iter} ->
362	    gb_trees_fold_1(Fun, Fun(Key, Value, InitAcc), Iter)
363    end.
364-endif. % MAP_FOLD_NEEDED
365
366assert_bb(BB) ->
367    assert_bb_is(hipe_bb:code(BB)).
368
369assert_bb_is([Last]) ->
370    true = is_branch(Last),
371    Last;
372assert_bb_is([I|Is]) ->
373    false = is_branch(I),
374    false = is_label(I),
375    assert_bb_is(Is).
376
377remove_pred(HT, FromL, PredL) ->
378  case gb_trees:lookup(FromL, HT) of
379    {value, {Block, Succ, Preds}} ->
380      Code = hipe_bb:code(Block),
381      NewCode = remove_pred_from_phis(PredL, Code),
382      NewBlock = hipe_bb:code_update(Block, NewCode),
383      gb_trees:update(FromL, {NewBlock,Succ,lists:delete(PredL,Preds)}, HT);
384    none ->
385      HT
386  end.
387
388add_pred(HT, ToL, PredL) ->
389  case gb_trees:lookup(ToL, HT) of
390    {value,{Block,Succ,Preds}} ->
391      gb_trees:update(ToL, {Block,Succ,[PredL|lists:delete(PredL,Preds)]}, HT);
392    none ->
393      gb_trees:insert(ToL, {[],[],[PredL]}, HT)
394  end.
395
396%% find_highest_label(CFG) ->
397%%   Labels = labels(CFG),
398%%   lists:foldl(fun(X, Acc) -> erlang:max(X, Acc) end, 0, Labels).
399%%
400%% find_highest_var(CFG) ->
401%%   Labels = labels(CFG),
402%%   Fun = fun(X, Max) ->
403%% 	    Code = hipe_bb:code(bb(CFG, X)),
404%% 	    NewMax = highest_var(Code),
405%% 	    erlang:max(Max, NewMax)
406%% 	end,
407%%   lists:foldl(Fun, 0, Labels).
408
409-ifdef(CFG_CAN_HAVE_PHI_NODES).
410%% phi-instructions in a removed block's successors must be aware of
411%% the change.
412remove_pred_from_phis(Label, List = [I|Left]) ->
413  case is_phi(I) of
414    true ->
415      NewI = phi_remove_pred(I, Label),
416      [NewI | remove_pred_from_phis(Label, Left)];
417    false ->
418      List
419  end;
420remove_pred_from_phis(_Label, []) ->
421  [].
422-else.
423%% this is used for code representations like those of back-ends which
424%% do not have phi-nodes.
425remove_pred_from_phis(_Label, Code) ->
426  Code.
427-endif.
428
429
430%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
431%%
432%% Constructs a CFG from a list of instructions.
433%%
434
435take_bbs([], CFG) ->
436  CFG;
437take_bbs(Xs, CFG) ->
438  Lbl = hd(Xs),
439  case is_label(Lbl) of
440    true ->
441      case take_bb(tl(Xs), []) of
442	{Code, Rest} ->
443	  NewCFG = bb_add(CFG, label_name(Lbl), hipe_bb:mk_bb(Code)),
444	  take_bbs(Rest, NewCFG)
445      end;
446    false ->
447      erlang:error({?MODULE,"basic block doesn't start with a label",Xs})
448  end.
449
450%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451%%
452%% Take_bb returns:
453%%   - {Code, Rest}.
454%%      * Code is a list of all the instructions.
455%%      * Rest is the remainder of the instructions
456
457take_bb([], Code) ->
458  {lists:reverse(Code), []};
459take_bb([X, Y|Xs], Code) ->
460  case is_label(X) of
461    true -> %% Empty block fallthrough
462      {[mk_goto(label_name(X))], [X,Y|Xs]};
463    false ->
464      case is_branch(X) of
465	true ->
466	  case is_label(Y) of
467	    true ->
468	      {lists:reverse([X|Code]), [Y|Xs]};
469	    false ->
470	      %% This should not happen...
471	      %% move the problem to the next BB.
472	      {lists:reverse([X|Code]), [Y|Xs]}
473	  end;
474	false -> %% X not branch
475	  case is_label(Y) of
476	    true ->
477	      {lists:reverse([mk_goto(label_name(Y)),X|Code]), [Y|Xs]};
478	    false ->
479	      take_bb([Y|Xs], [X|Code])
480	  end
481      end
482  end;
483take_bb([X], []) ->
484  case is_label(X) of
485    true ->
486      %% We don't want the CFG to just end with a label...
487      %% We loop forever instead...
488      {[X,mk_goto(label_name(X))],[]};
489    false ->
490      {[X],[]}
491  end;
492take_bb([X], Code) ->
493  case is_label(X) of
494    true ->
495      %% We don't want the CFG to just end with a label...
496      %% We loop for ever instead...
497      {lists:reverse(Code),[X,mk_goto(label_name(X))]};
498    false ->
499      {lists:reverse([X|Code]),[]}
500  end.
501
502%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
503%%
504%% Functions for extracting the names of the basic blocks in various
505%% orders.
506%%
507
508labels(CFG) ->
509  HT = CFG#cfg.table,
510  gb_trees:keys(HT).
511
512postorder(CFG) ->
513  lists:reverse(reverse_postorder(CFG)).
514
515reverse_postorder(CFG) ->
516  Start = start_label(CFG),
517  {Ordering, _Visited} =
518    depth_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []),
519  Ordering.
520
521depth_search([N|Ns], Visited, CFG, Acc) ->
522  case is_visited(N, Visited) of
523    true ->
524      depth_search(Ns, Visited, CFG, Acc);
525    false ->
526      {Order, Vis} = depth_search(succ(CFG, N), visit(N, Visited), CFG, Acc),
527      depth_search(Ns, Vis, CFG, [N|Order])
528  end;
529depth_search([], Visited, _, Ordering) ->
530  {Ordering, Visited}.
531
532-ifdef(PREORDER).
533preorder(CFG) ->
534  Start = start_label(CFG),
535  {Ordering, _Visited} =
536    preorder_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []),
537  lists:reverse(Ordering).
538
539preorder_search([N|Ns], Visited, CFG, Acc) ->
540  case is_visited(N, Visited) of
541    true ->
542      preorder_search(Ns, Visited, CFG, Acc);
543    false ->
544      {Order, Vis} =
545	preorder_search(succ(CFG, N), visit(N, Visited), CFG, [N|Acc]),
546      preorder_search(Ns, Vis, CFG, Order)
547  end;
548preorder_search([], Visited, _, Ordering) ->
549  {Ordering,Visited}.
550-endif.	% PREORDER
551
552-ifdef(BREADTH_ORDER).
553breadthorder(CFG) ->
554  lists:reverse(reverse_breadthorder(CFG)).
555
556reverse_breadthorder(CFG) ->
557  Start = start_label(CFG),
558  {Vis, RBO1} = breadth_list([Start], none_visited(), CFG, []),
559  {_Vis1, RBO2} = breadth_list(other_entrypoints(CFG), Vis, CFG, RBO1),
560  RBO2.
561
562breadth_list([X|Xs], Vis, CFG, BO) ->
563  case is_visited(X, Vis) of
564    true ->
565      breadth_list(Xs, Vis, CFG, BO);
566    false ->
567      breadth_list(Xs ++ succ(CFG, X), visit(X, Vis), CFG, [X|BO])
568  end;
569breadth_list([], Vis, _CFG, BO) ->
570  {Vis, BO}.
571-endif.
572
573-spec none_visited() -> gb_sets:set().
574none_visited() ->
575  gb_sets:empty().
576
577visit(X, Vis) ->
578  gb_sets:add(X, Vis).
579
580is_visited(X, Vis) ->
581  gb_sets:is_member(X, Vis).
582
583-endif.	% GEN_CFG
584
585%%---------------------------------------------------------------------
586
587succ(SuccMap, Label) ->
588  HT = SuccMap#cfg.table,
589  case gb_trees:lookup(Label, HT) of
590    {value, {_Block,Succ,_Pred}} ->
591      Succ;
592    none ->
593      erlang:error({"successor not found", Label, SuccMap})
594  end.
595
596-ifdef(PRED_NEEDED).
597pred(Map, Label) ->
598  HT = Map#cfg.table,
599  case gb_trees:lookup(Label, HT) of
600    {value, {_Block,_Succ,Pred}} ->
601      Pred;
602    none ->
603      erlang:error({"predecessor not found", Label, Map})
604  end.
605-endif.	% PRED_NEEDED
606
607-ifndef(GEN_CFG).
608fallthrough(CFG, Label) ->
609  HT = CFG#cfg.table,
610  case gb_trees:lookup(Label, HT) of
611    {value, {_Block, Succ, _}} ->
612       case Succ of
613	 [X|_] -> X;
614	 _ -> none
615       end;
616     none ->
617       erlang:error({"fallthrough label not found", Label})
618  end.
619
620conditional(CFG, Label) ->
621  HT = CFG#cfg.table,
622  {value,{_Block,Succ,_}} = gb_trees:lookup(Label, HT),
623  case Succ of
624    [] -> none;
625    [_] -> none;
626    [_|Labels] -> Labels
627  end.
628-endif.	% GEN_CFG
629
630%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
631%%
632%% Linearize the code in a CFG. Returns a list of instructions.
633%%
634
635-ifdef(GEN_CFG).
636-else.
637linearize_cfg(CFG) ->
638  Start = start_label(CFG),
639  Vis = none_visited(),
640  {Vis0, NestedCode} = lin_succ(Start, CFG, Vis),
641  BlocksInData = hipe_consttab:referred_labels(data(CFG)),
642  AllCode = lin_other_entries(NestedCode, CFG, BlocksInData, Vis0),
643  lists:flatten(AllCode).
644
645lin_succ(none, _CFG, Vis) ->
646  {Vis, []};
647lin_succ([Label|Labels], CFG, Vis) ->
648  {Vis1, Code1} = lin_succ(Label, CFG, Vis),
649  {Vis2, Code2} = lin_succ(Labels, CFG, Vis1),
650  {Vis2, [Code1,Code2]};
651lin_succ([], _CFG, Vis) ->
652  {Vis, []};
653lin_succ(Label, CFG, Vis) ->
654  case is_visited(Label, Vis) of
655    true ->
656      {Vis, []};      % already visited
657    false ->
658      Vis0 = visit(Label, Vis),
659      case bb(CFG, Label) of
660	not_found ->
661	  erlang:error({?MODULE, "No basic block with label", Label});
662        BB ->
663	  Fallthrough = fallthrough(CFG, Label),
664	  Cond = conditional(CFG, Label),
665	  LblInstr = mk_label(Label),
666	  {Vis1, Code1} = lin_succ(Fallthrough, CFG, Vis0),
667	  {Vis2, Code2} = lin_succ(Cond, CFG, Vis1),
668	  {Vis2, [[LblInstr|hipe_bb:code(BB)], Code1, Code2]}
669      end
670  end.
671
672lin_other_entries(Code, _CFG, [], _Vis) ->
673  Code;
674lin_other_entries(Code, CFG, [E|Es], Vis) ->
675  {Vis0, MoreCode} = lin_succ(E, CFG, Vis),
676  lin_other_entries([Code, MoreCode], CFG, Es, Vis0).
677-endif.
678
679-ifdef(FIND_NEW_LABEL_NEEDED).
680find_new_label(Old, Map) ->
681  forward(Old, Map).
682-endif.
683
684%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
685%%
686%% Remove empty BBs.
687%%
688%% Removes basic blocks containing only a goto to another BB.
689%% Branches to removed blocks are updated to the successor of the
690%% removed block.
691%% Loads (or other operations) on the label of the BB are also
692%% updated. So are any references from the data section.
693%%
694
695-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
696
697-spec remove_trivial_bbs(cfg()) -> cfg().
698remove_trivial_bbs(CFG) ->
699  ?opt_start_timer("Merge BBs"),
700  CFG0 = merge_bbs(rewrite_trivial_branches(CFG)),
701  ?opt_stop_timer("Merge BBs"),
702  %% pp(CFG0),
703  ?opt_start_timer("FindDead"),
704  {NewMap, CFG1} = remap(labels(CFG0), rd_map_new(), CFG0),
705  ?opt_stop_timer("FindDead"),
706  ?opt_start_timer("Labels"),
707  Labels = labels(CFG1),
708  ?opt_stop_timer("Labels"),
709  ?opt_start_timer("RedirectBranches"),
710  CFG2 = redirect_branches(NewMap, CFG1),
711  ?opt_stop_timer("RedirectBranches"),
712  ?opt_start_timer("RedirectOps"),
713  CFG3 = redirect_ops(Labels, CFG2, NewMap),
714  ?opt_stop_timer("RedirectOps"),
715  ?opt_start_timer("RedirectData"),
716  CFG4 = redirect_data(CFG3, NewMap),
717  ?opt_stop_timer("RedirectData"),
718  ?opt_start_timer("RedirectStart"),
719  CFG5 = redirect_start(CFG4, NewMap),
720  ?opt_stop_timer("RedirectStart"),
721  %% pp(CFG5),
722  CFG5.
723
724redirect_start(CFG, Map) ->
725  Start = start_label(CFG),
726  case forward(Start, Map) of
727    Start -> CFG;
728    NewStart ->
729      start_label_update(CFG, NewStart)
730  end.
731
732redirect_data(CFG, Map) ->
733  Data = data(CFG),
734  NewData = hipe_consttab:update_referred_labels(Data, rd_succs(Map)),
735  update_data(CFG, NewData).
736
737redirect_branches(Map, CFG) ->
738  lists:foldl(fun ({From,{newsuccs,Redirects}}, CFGAcc) ->
739		  lists:foldl(
740		    fun({ToOld,ToNew}, CFG1) ->
741			case bb(CFG1, From) of
742			  not_found ->
743			    CFG1;
744			  _ ->
745			    To = forward(ToNew, Map),
746			    redirect(CFG1, From, ToOld, To)
747			end
748		    end,
749		    CFGAcc,
750		    Redirects);
751		  (_, CFGAcc) -> CFGAcc
752	      end,
753	      CFG,
754	      gb_trees:to_list(Map)).
755
756redirect(CFG, From, ToOld, ToNew) ->
757  BB = bb(CFG, From),
758  LastInstr = hipe_bb:last(BB),
759  NewLastInstr = redirect_jmp(LastInstr, ToOld, ToNew),
760  NewBB = hipe_bb:mk_bb(hipe_bb:butlast(BB) ++ [NewLastInstr]),
761  bb_add(CFG, From, NewBB).
762
763bb_remove(CFG, Label) ->
764  HT = CFG#cfg.table,
765  case gb_trees:lookup(Label, HT) of
766    {value, {_Block, Succ, _Preds}} ->
767      %% Remove this block as a pred from all successors.
768      HT1 = lists:foldl(fun (S,HTAcc) ->
769			    remove_pred(HTAcc, S, Label)
770			end,
771			HT, Succ),
772      CFG#cfg{table = gb_trees:delete(Label, HT1)};
773    none ->
774      CFG
775  end.
776
777remap([L|Rest], Map, CFG) ->
778  case is_empty(bb(CFG, L)) of
779    true ->
780      case succ(CFG, L) of
781	[L] -> %% This is an empty (infinite) self loop. Leave it.
782	  remap(Rest, Map, CFG);
783	[SuccL] ->
784	  CFG1 = bb_remove(CFG, L),
785	  NewMap = remap_to_succ(L, SuccL, Map, CFG),
786	  remap(Rest, NewMap, CFG1)
787      end;
788    false ->
789      remap(Rest, Map, CFG)
790  end;
791remap([], Map, CFG) ->
792  {Map, CFG}.
793
794remap_to_succ(L, SuccL, Map, PredMap) ->
795  insert_remap(L, forward(SuccL,Map), pred(PredMap,L), Map).
796
797%% Find the proxy for a BB
798forward(L, Map) ->
799  case gb_trees:lookup(L, Map) of
800    {value, {dead, To}} ->
801      forward(To, Map); %% Hope this terminates.
802    _ -> L
803  end.
804
805%% A redirection map contains mappings from labels to
806%%  none -> this BB is not affected by the remapping.
807%%  {dead,To} -> this BB is dead, To is the new proxy.
808%%  {newsuccs,[{X,Y}|...]} -> The successor X is redirected to Y.
809
810rd_map_new() -> gb_trees:empty().
811
812rd_succs(M) ->
813  lists:foldl(fun ({From,{dead,To}}, Acc) -> [{From,forward(To,M)}|Acc];
814		  (_, Acc) -> Acc
815	      end,
816	      [],
817	      gb_trees:to_list(M)).
818
819add_redirectedto(L, From, To, Map) ->
820  case gb_trees:lookup(L, Map) of
821    {value, {newsuccs, NS}} ->
822      gb_trees:update(L,{newsuccs,[{From,To}|lists:keydelete(From,1,NS)]},Map);
823    {value, {dead, _}} -> Map;
824    none ->
825      gb_trees:insert(L, {newsuccs, [{From, To}]}, Map)
826  end.
827
828insert_remap(L, ToL, Preds, Map) ->
829  Map2 = gb_trees:enter(L, {dead, ToL}, Map),
830  lists:foldl(fun (Pred, AccMap) ->
831		   add_redirectedto(Pred, L, ToL, AccMap)
832	      end,
833	      Map2,
834	      Preds).
835
836is_empty(BB) ->
837  is_empty_bb(hipe_bb:code(BB)).
838
839is_empty_bb([I]) ->
840  is_goto(I); %% A BB with just a 'goto' is empty.
841is_empty_bb([I|Is]) ->
842  case is_comment(I) of
843    true ->
844      is_empty_bb(Is);
845    false ->
846      false
847  end;
848is_empty_bb([]) ->
849  true.
850
851
852%% Rewrite all pure branches with one successor to goto:s
853
854-spec rewrite_trivial_branches(cfg()) -> cfg().
855rewrite_trivial_branches(CFG) ->
856  rewrite_trivial_branches(postorder(CFG), CFG).
857
858rewrite_trivial_branches([L|Left], CFG) ->
859  BB = bb(CFG, L),
860  Last = hipe_bb:last(BB),
861  case is_goto(Last) of
862    true ->
863      rewrite_trivial_branches(Left, CFG);
864    false ->
865      case is_pure_branch(Last) of
866	false ->
867	  rewrite_trivial_branches(Left, CFG);
868	true ->
869	  case succ(CFG, L) of
870	    [Successor] ->
871	      Head = hipe_bb:butlast(BB),
872	      NewBB = hipe_bb:mk_bb(Head ++ [mk_goto(Successor)]),
873	      NewCFG = bb_add(CFG, L, NewBB),
874	      rewrite_trivial_branches(Left, NewCFG);
875	    _ ->
876	      rewrite_trivial_branches(Left, CFG)
877	  end
878      end
879  end;
880rewrite_trivial_branches([], CFG) ->
881  CFG.
882
883
884%% Go through the CFG and find pairs of BBs that can be merged to one BB.
885%% They are of the form:
886%%
887%%      L
888%%      |
889%%   Successor
890%%
891%% That is, the block L has only one successor (Successor) and that
892%% successor has no other predecessors than L.
893%%
894%% Note: calls might end a basic block
895
896merge_bbs(CFG) ->
897  lists:foldl(fun merge_successor/2, CFG, postorder(CFG)).
898
899%% If L fulfills the requirements, merge it with its successor.
900merge_successor(L, CFG) ->
901  %% Get the BB L (If it still exists).
902  case bb(CFG, L) of
903    not_found -> CFG;
904    BB ->
905      StartLabel = start_label(CFG),
906      Last = hipe_bb:last(BB),
907      %% Note: Cannot use succ/2 since the instruction can have more than
908      %% one successor that are the same label.
909      case {branch_successors(Last), fails_to(Last)} of
910	{[Successor],[Successor]} ->
911	  %% The single successor is the fail-label; don't merge.
912	  CFG;
913	{[Successor],_} when Successor =/= StartLabel ->
914	  %% Make sure the succesor only have this block as predecessor.
915	  case [L] =:= pred(CFG, Successor) of
916	    true ->
917	      %% Remove the goto or remap fall-through in BB and merge the BBs
918	      NewCode = merge(BB, bb(CFG, Successor), Successor),
919	      NewBB = hipe_bb:mk_bb(NewCode),
920	      bb_add(bb_remove(CFG, Successor), L, NewBB);
921	    false ->
922	      CFG
923	  end;
924	_ ->
925	  %% Not exactly one successor or tried to merge with the
926	  %% entry point
927	  CFG
928      end
929  end.
930
931%% Merge BB and BB2
932merge(BB, BB2, BB2_Label) ->
933  Head = hipe_bb:butlast(BB),
934  Last = hipe_bb:last(BB),
935  Tail = hipe_bb:code(BB2),
936  case is_goto(Last) of
937    true ->
938      %% Just ignore the goto.
939      Head ++ Tail;
940    false ->
941      %% The last instr is not a goto,
942      %%  e.g. a call with only fall-through
943      %% Remove the fall-through with the []-label.
944      Head ++ [redirect_jmp(Last, BB2_Label, [])|Tail]
945  end.
946
947-endif.	% REMOVE_TRIVIAL_BBS_NEEDED
948
949
950%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
951%%
952%% Remove unreachable BBs.
953%%
954%% A BB is unreachable if it cannot be reached by any path from the
955%% start label of the function.
956%%
957%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
958
959-ifdef(REMOVE_UNREACHABLE_CODE).
960
961-spec remove_unreachable_code(cfg()) -> cfg().
962
963remove_unreachable_code(CFG) ->
964  Start = start_label(CFG),
965  %% No unreachable block will make another block reachable, so no fixpoint
966  %% looping is required
967  Reachable = find_reachable([], [Start], CFG, #{Start=>[]}),
968  case [L || L <- labels(CFG), not maps:is_key(L, Reachable)] of
969    [] -> CFG;
970    Remove ->
971      HT0 = CFG#cfg.table,
972      HT1 = lists:foldl(fun gb_trees:delete/2, HT0, Remove),
973      ReachableP = fun(Lbl) -> maps:is_key(Lbl, Reachable) end,
974      HT = gb_trees:map(fun(_,B)->prune_preds(B, ReachableP)end, HT1),
975      CFG#cfg{table=HT}
976  end.
977
978find_reachable([], [], _CFG, Acc) -> Acc;
979find_reachable([Succ|Succs], Left, CFG, Acc) ->
980  case Acc of
981    #{Succ := _} -> find_reachable(Succs, Left, CFG, Acc);
982    #{} -> find_reachable(Succs, [Succ|Left], CFG, Acc#{Succ => []})
983  end;
984find_reachable([], [Label|Left], CFG, Acc) ->
985  find_reachable(succ(CFG, Label), Left, CFG, Acc).
986
987%% Batch prune unreachable predecessors. Asymptotically faster than deleting
988%% unreachable blocks one at a time with bb_remove, at least when
989%% CFG_CAN_HAVE_PHI_NODES is undefined. Otherwise a phi_remove_preds might be
990%% needed to achieve that.
991prune_preds(B={Block, Succ, Preds}, ReachableP) ->
992  case lists:partition(ReachableP, Preds) of
993    {_, []} -> B;
994    {NewPreds, Unreach} ->
995      NewCode = remove_preds_from_phis(Unreach, hipe_bb:code(Block)),
996      {hipe_bb:code_update(Block, NewCode), Succ, NewPreds}
997  end.
998
999-ifdef(CFG_CAN_HAVE_PHI_NODES).
1000remove_preds_from_phis(_, []) -> [];
1001remove_preds_from_phis(Preds, List=[I|Left]) ->
1002  case is_phi(I) of
1003    false -> List;
1004    true ->
1005      NewI = lists:foldl(fun(L,IA)->phi_remove_pred(IA,L)end,
1006			 I, Preds),
1007      [NewI | remove_preds_from_phis(Preds, Left)]
1008  end.
1009-else.
1010remove_preds_from_phis(_, Code) -> Code.
1011-endif.
1012
1013-endif. %% -ifdef(REMOVE_UNREACHABLE_CODE)
1014