1
1
%% -*- erlang-indent-level: 2 -*-
5
%% Copyright Ericsson AB 2007-2009. All Rights Reserved.
7
%% The contents of this file are subject to the Erlang Public License,
8
%% Version 1.1, (the "License"); you may not use this file except in
9
%% compliance with the License. You should have received a copy of the
10
%% Erlang Public License along with this software. If not, it can be
11
%% retrieved online at http://www.erlang.org/.
13
%% Software distributed under the License is distributed on an "AS IS"
14
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
15
%% the License for the specific language governing rights and limitations
2
20
%%%=======================================================================
3
21
%% File : hipe_icode_ssa_struct_reuse.erl
4
22
%% Author : Ragnar Osterlund <ragoster@gmail.com>
51
70
%% var - maps variables to expression value numbers. These variables are
52
71
%% defined or used by the structure expressions.
54
-record(maps, {var = gb_trees:empty() :: gb_tree(),
73
-record(maps, {var = gb_trees:empty() :: gb_tree(),
55
74
instr = gb_trees:empty() :: gb_tree(),
56
expr = gb_trees:empty() :: gb_tree()
75
expr = gb_trees:empty() :: gb_tree()}).
59
77
maps_var(#maps{var = Out}) -> Out.
60
78
maps_instr(#maps{instr = Out}) -> Out.
152
169
%% exprid - a expression value number which is the expression that
153
170
%% the variable is defined by.
155
-record(varinfo, {use = ?SETS:new() :: ?SET(_),
156
ref = none :: 'none' | {non_neg_integer(),non_neg_integer()},
157
elem = none :: 'none' | {icode_var(), non_neg_integer()},
158
exprid = none :: 'none' | non_neg_integer()}).
172
-record(varinfo, {use = ?SETS:new() :: ?SET(_),
173
ref = none :: 'none' | {non_neg_integer(),non_neg_integer()},
174
elem = none :: 'none' | {icode_var(), non_neg_integer()},
175
exprid = none :: 'none' | non_neg_integer()}).
160
177
varinfo_exprid(#varinfo{exprid = Out}) -> Out.
340
357
%% has been inserted is used to move the reduction test.
342
359
-record(update, {inserted = gb_trees:empty() :: gb_tree(),
343
del_red_test = false :: bool()
360
del_red_test = false :: bool()}).
346
362
update_inserted_lookup(#update{inserted = Inserted}, ExprId) ->
347
363
gb_trees:lookup(ExprId, Inserted).
349
365
update_inserted_add_new(Update = #update{inserted = Inserted}, ExprId, Defs) ->
351
lists:map(fun(Def) ->
352
case hipe_icode:is_var(Def) of
353
true -> hipe_icode:mk_new_var();
355
case hipe_icode:is_reg(Def) of
356
true -> hipe_icode:mk_new_reg();
358
case hipe_icode:is_fvar(Def) of
359
true -> hipe_icode:mk_new_fvar()
366
VarList = [case hipe_icode:is_var(Def) of
367
true -> hipe_icode:mk_new_var();
369
case hipe_icode:is_reg(Def) of
370
true -> hipe_icode:mk_new_reg();
372
true = hipe_icode:is_fvar(Def),
373
hipe_icode:mk_new_fvar()
365
376
NewInserted = gb_trees:enter(ExprId, VarList, Inserted),
366
377
{Update#update{inserted = NewInserted}, VarList}.
443
453
NewNodes = prune_nodes(Nodes, NonFailSet),
445
455
%% fill in misc node tree info
446
Postorder = lists:filter(fun(Label) -> gb_sets:is_member(Label, NonFailSet)
447
end, hipe_icode_cfg:postorder(CFG)),
456
Postorder = [Label || Label <- hipe_icode_cfg:postorder(CFG),
457
gb_sets:is_member(Label, NonFailSet)],
449
459
%% check postorder is valid
450
460
PostOrderTmp = hipe_icode_cfg:postorder(CFG),
463
473
StartLabel = hipe_icode_cfg:start_label(CFG),
464
474
NewTree = gb_trees:balance(nodes_tree(NewNodes)),
467
postorder = Postorder,
468
rev_postorder = RevPostorder,
469
start_label = StartLabel,
476
NewNodes#nodes{postorder = Postorder,
477
rev_postorder = RevPostorder,
478
start_label = StartLabel,
474
482
%%-----------------------------------------------------------------------------
475
%% Constucts a tree of nodes, one node for each basic block in CFG
483
%% Constructs a tree of nodes, one node for each basic block in CFG
477
485
nodes_from_cfg(CFG, DomTree) ->
478
486
lists:foldl(fun(Label, {NodesAcc, NonFailAcc}) ->
585
593
lists:foldl(fun(Node, NodesAcc) ->
586
594
case gb_sets:is_member(node_label(Node), NonFailSet) of
588
NewSucc = lists:filter(fun(Label) ->
589
gb_sets:is_member(Label, NonFailSet) end, node_succ(Node)),
591
NewPred = lists:filter(fun(Label) ->
592
gb_sets:is_member(Label, NonFailSet) end, node_pred(Node)),
596
NewSucc = [L || L <- node_succ(Node), gb_sets:is_member(L, NonFailSet)],
597
NewPred = [L || L <- node_pred(Node), gb_sets:is_member(L, NonFailSet)],
594
598
enter_node(Node#node{succ = NewSucc, pred = NewPred}, NodesAcc);
597
600
remove_node(Node, NodesAcc)
599
602
end, Nodes, nodes_tree_values(Nodes)).
602
604
%%-----------------------------------------------------------------------------
603
605
%% Map calculations.
610
612
Node = get_node(Label, Nodes),
611
613
NewMapsAcc = maps_from_node_struct_type(MapsAcc, Node),
612
614
NewMapsAcc2 = maps_from_node_struct_elems(NewMapsAcc, Node),
613
%NewMapsAcc3 = maps_from_node_atom_type(NewMapsAcc2, Node),
615
%% NewMapsAcc3 = maps_from_node_atom_type(NewMapsAcc2, Node),
614
616
maps_from_node_code(NewMapsAcc2, Node)
615
617
end, #maps{}, nodes_rev_postorder(Nodes)),
616
618
maps_balance(Maps).
620
%%-----------------------------------------------------------------------------
621
%% Add all elements in the struct_type list of Node to Maps as expressions
623
maps_from_node_struct_type(Maps, Node) ->
624
%% debug_struct("Node Label: ", node_label(Node)),
625
%% debug_struct("Node Tuple Type: ", node_struct_type(Node)),
626
lists:foldl(fun({Type, Var, Size}, MapsAcc) ->
627
Key = create_elem_expr_key(Size, Var, []),
628
InstrKey = hipe_icode:mk_primop([], Type, Key),
629
NewExpr2 = expr_create(InstrKey, [Var]),
630
NewExpr3 = expr_direct_replace_set(NewExpr2, true),
631
maps_expr_key_enter(NewExpr3, MapsAcc)
632
end, Maps, node_struct_type(Node)).
618
634
create_elem_expr_key(0, _, Key) -> Key;
619
635
create_elem_expr_key(N, Var, Key) ->
620
636
create_elem_expr_key(N - 1, Var, [{Var, N} | Key]).
623
%%-----------------------------------------------------------------------------
624
%% Add all elements in the struct_type list of Node to Maps as expressions
626
maps_from_node_struct_type(Maps, Node) ->
627
%debug_struct("Node Label: ", node_label(Node)),
628
%debug_struct("Node Tuple Type: ", node_struct_type(Node)),
630
lists:foldl(fun({Type, Var, Size}, MapsAcc) ->
631
Key = create_elem_expr_key(Size, Var, []),
632
InstrKey = hipe_icode:mk_primop([], Type, Key),
634
NewExpr2 = expr_create(InstrKey, [Var]),
635
NewExpr3 = expr_direct_replace_set(NewExpr2, true),
636
NewMapsAcc = maps_expr_key_enter(NewExpr3, MapsAcc),
639
end, Maps, node_struct_type(Node)).
642
638
%%-----------------------------------------------------------------------------
643
639
%%maps_from_node_atom_type(Maps, Node) ->
644
640
%% lists:foldl(fun({Var, Atom}, MapsAcc) ->
679
675
%% Also insert information about all affected variables into Maps.
681
677
maps_from_node_code(Maps, Node) ->
682
%%debug_struct("Node Label: ", Label),
683
%%debug_struct("Node Code: ", Code),
684
%Label = node_label(Node),
678
%% debug_struct("Node Label: ", Label),
679
%% debug_struct("Node Code: ", Code),
680
%% Label = node_label(Node),
686
681
lists:foldl(fun(Instr, MapsAcc) ->
687
682
%% create two keys that are used to reference this structure creation
688
683
%% instruction, so that we can lookup its expression value number
748
743
maps_expr_varinfos_create(Instr, RefKey, Maps) ->
749
744
Defines = hipe_icode:defines(Instr),
751
case maps_instr_lookup(RefKey, Maps) of
755
NewExpr = expr_create(RefKey, Defines),
756
ExprId = expr_id(NewExpr),
757
Maps2 = maps_expr_key_enter(NewExpr, Maps)
746
case maps_instr_lookup(RefKey, Maps) of
750
NewExpr = expr_create(RefKey, Defines),
751
{expr_id(NewExpr), maps_expr_key_enter(NewExpr, Maps)}
760
753
Maps3 = maps_varinfos_create(Defines, ExprId, none, Maps2),
761
754
update_maps_var_use(Instr, ExprId, Maps3).
802
793
update_maps_var_use(Instr, Id, Maps) ->
803
794
lists:foldl(fun(Use, MapsAcc) ->
804
VarInfo = get_varinfo(Use, MapsAcc),
806
NewVarInfo = varinfo_use_add(VarInfo, Id),
807
MapsAcc2 = maps_var_enter(Use, NewVarInfo, MapsAcc),
809
case varinfo_exprid(VarInfo) of
813
Expr = maps_expr_get(VarExprId, MapsAcc2),
814
NewExpr = expr_use_add(Expr, Id),
815
maps_expr_enter(NewExpr, MapsAcc2)
818
end, Maps, hipe_icode:uses(Instr)).
795
VarInfo = get_varinfo(Use, MapsAcc),
796
NewVarInfo = varinfo_use_add(VarInfo, Id),
797
MapsAcc2 = maps_var_enter(Use, NewVarInfo, MapsAcc),
798
case varinfo_exprid(VarInfo) of
802
Expr = maps_expr_get(VarExprId, MapsAcc2),
803
NewExpr = expr_use_add(Expr, Id),
804
maps_expr_enter(NewExpr, MapsAcc2)
806
end, Maps, hipe_icode:uses(Instr)).
820
808
%%-----------------------------------------------------------------------------
821
809
%% Looks up an old variable info or creates a new one if none is found.
836
824
replace_call_variables(Filter, Instr) ->
837
NewArgs = lists:map(fun(Arg) ->
838
case hipe_icode:is_const(Arg) of
839
false -> Filter(Arg);
842
end, hipe_icode:args(Instr)),
825
NewArgs = [case hipe_icode:is_const(Arg) of
826
false -> Filter(Arg);
828
end || Arg <- hipe_icode:args(Instr)],
843
829
hipe_icode:call_args_update(Instr, NewArgs).
845
831
%%-----------------------------------------------------------------------------
867
enter_node(Node#node{
869
killed_expr = KilledExpr,
870
antic_out = AnticOut}, NodesAcc)
851
enter_node(Node#node{up_expr = UEExpr,
852
killed_expr = KilledExpr,
853
antic_out = AnticOut}, NodesAcc)
872
854
end, nodes_all_expr_set(AllExpr, Nodes), nodes_tree_values(Nodes)).
874
856
%%-----------------------------------------------------------------------------
907
889
calc_killed_expr_defs(Defs, UseSet, Maps) ->
908
890
lists:foldl(fun(Def, Acc) ->
909
case maps_var_lookup(Def, Maps) of
912
{value, #varinfo{use = Use}} ->
913
?SETS:union(Acc, calc_killed_expr_use(Use, Maps))
891
case maps_var_lookup(Def, Maps) of
894
{value, #varinfo{use = Use}} ->
895
?SETS:union(Acc, calc_killed_expr_use(Use, Maps))
917
899
calc_killed_expr_use(ExprIds, Maps) ->
918
900
?SETS:fold(fun(Id, Acc) ->
919
Expr = maps_expr_get(Id, Maps),
920
?SETS:union(Acc, calc_killed_expr_use(expr_use(Expr), Maps))
921
end, ExprIds, ExprIds).
901
Expr = maps_expr_get(Id, Maps),
902
?SETS:union(Acc, calc_killed_expr_use(expr_use(Expr), Maps))
903
end, ExprIds, ExprIds).
923
905
%%-----------------------------------------------------------------------------
924
906
%% Calculate the anticipated in and anticipated out sets for each node
1071
1053
rewrite_cfg(CFG, Nodes, Maps) ->
1072
1054
{NewCFG, _Visited} =
1073
1055
rewrite_cfg(CFG, ?SETS:new(), #update{}, Nodes, Maps, [nodes_start_label(Nodes)]),
1075
%debug_struct("Visited: ", _Visited),
1056
%% debug_struct("Visited: ", _Visited),
1079
1059
%%-----------------------------------------------------------------------------
1086
1066
lists:foldl(fun(Label, {CFGAcc, VisitedAcc}) ->
1087
1067
case ?SETS:is_element(Label, VisitedAcc) of
1089
%debug_struct("Visit: ", Label),
1069
%% debug_struct("Visit: ", Label),
1091
1070
Node = get_node(Label, Nodes),
1092
1071
NewVisitedAcc = ?SETS:add_element(Label, VisitedAcc),
1094
1072
{NewCFGAcc, NewUpdate} = rewrite_bb(CFGAcc, Update, Maps, Node),
1095
%debug_struct("Update inserted: ", update_inserted_list(NewUpdate)),
1073
%% debug_struct("Update inserted: ", update_inserted_list(NewUpdate)),
1097
1074
rewrite_cfg(NewCFGAcc, NewVisitedAcc, NewUpdate, Nodes, Maps, node_succ(Node));
1099
1076
{CFGAcc, VisitedAcc}
1101
1078
end, {CFG, Visited}, Labels).
1104
1080
%%-----------------------------------------------------------------------------
1105
1081
%% rewrite one single basic block in the CFG as described by the properties
1106
1082
%% in the Node for that block. Uses the Maps and Update info to lookup
1210
1186
%% check if there exists an identical expression, so that
1211
1187
%% this expression can be replaced directly.
1212
case expr_direct_replace(Expr) of
1214
NewInstr = rewrite_expr(UpdateAcc2, ExprInstr, NewDefs),
1215
CodeAcc2 = [NewInstr | CodeAcc];
1217
CodeAcc2 = mk_defs_moves(CodeAcc, NewDefs, Defs)
1189
case expr_direct_replace(Expr) of
1191
NewInstr = rewrite_expr(UpdateAcc2, ExprInstr, NewDefs),
1192
[NewInstr | CodeAcc];
1194
mk_defs_moves(CodeAcc, NewDefs, Defs)
1220
1196
{CodeAcc2, UpdateAcc2}
1221
1197
end, {CodeRest, NewUpdate}, NewInserts),
1374
1347
Cases = get(Type),
1376
1349
case gb_trees:lookup(Case, Cases) of
1378
gb_trees:enter(Case, Value + 1, Cases);
1379
_ -> gb_trees:insert(Case, 1, Cases)
1350
{value, Value} -> gb_trees:enter(Case, Value + 1, Cases);
1351
none -> gb_trees:insert(Case, 1, Cases)
1381
1353
put(Type, NewCases).
1383
debug_init_case_count(Type) ->
1387
put(Type, gb_trees:empty());
1355
debug_init_case_count(Type) ->
1357
undefined -> put(Type, gb_trees:empty());
1393
1363
debug_struct("Case type: ", Type),
1394
1364
debug_list("Cases: ", gb_trees:to_list(Cases)).
1397
1366
set_debug_flag(Value) ->
1398
put({struct_reuse,debug}, Value).
1367
put({struct_reuse, debug}, Value).
1400
get_debug_flag() -> get({struct_reuse,debug}).
1369
get_debug_flag() -> get({struct_reuse, debug}).
1402
1371
debug_function(FuncName, CFG) ->
1403
1372
Linear = hipe_icode_cfg:cfg_to_linear(CFG),
1404
1373
Func = hipe_icode:icode_fun(Linear),
1406
1374
case Func =:= FuncName orelse FuncName =:= nil of
1408
1376
set_debug_flag(true),
1409
%debug_struct("Code: ", hipe_icode_cfg:bb(CFG, 15)),
1377
%% debug_struct("Code: ", hipe_icode_cfg:bb(CFG, 15)),
1410
1378
debug_struct("~nFunction name :", Func);
1412
1380
set_debug_flag(undefined)