1
%% -*- erlang-indent-level: 2 -*-
2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4
%% @doc This module performs integer range analysis on ICode.
8
%% <p>iterating, fixing and adding in a happily manner.</p>
11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13
-module(hipe_icode_range_an).
16
-export([to_string/1]).
19
-define(LABELITERATIONS, 10).
20
-define(PHIWIDENING, 4). %< LABELITERATIONS
21
-define(FUNCTION_FIXPOINT_DEPTH, 5).
23
%-define(not_done_debug, fun(X, Y) -> io:format(X, Y) end).
24
-define(not_done_debug, fun(_, _) -> ok end).
26
%-define(call_or_enter_debug, fun(X, Y) -> io:format(X, Y) end).
27
-define(call_or_enter_debug, fun(_, _) -> ok end).
30
-define(TAG_IMMED1_SIZE, 4).
32
-define(BITS, (hipe_rtl_arch:word_size() bsl 3) - ?TAG_IMMED1_SIZE).
33
-define(FIXNUM_UPPER, ((1 bsl (?BITS - 1)) - 1)).
34
-define(FIXNUM_LOWER, -(1 bsl (?BITS - 1))).
35
-define(MAX_BYTE, 255).
36
-define(MAX_CHAR, 16#10ffff).
38
-include("hipe_icode.hrl").
39
-include("../main/hipe.hrl").
42
%-define(DEBUG, false).
45
%% This record is used when returning information
46
-record(range_info, {live_labels,
48
out_label_range_trees,
53
%% This record is used by the range analyser
54
-record(info_struct, {worklist,
55
phi_values=gb_trees:empty(),
56
range_trees=gb_trees:empty(),
57
pred_trees=gb_trees:empty(),
58
current_range_tree=gb_trees:empty(),
62
current_mfa_not_done=false,
63
label_counters=gb_trees:empty(),
67
live_labels=gb_sets:empty(),
69
wideningvalues=[posinf, neginf],
74
%% This is the representation of a range.
75
-record(var_range, {var_name,
83
%% Initializes the analysis
86
init(IC, Options, Server, MFA) ->
87
%%io:format("analysing ~p ~n", [MFA]),
88
%%hipe_icode_pp:pp(hipe_icode_cfg:cfg_to_linear(IC)),
89
case info_struct__init(IC, Server, Options, MFA) of
93
Info2 = analyse_icode(IC, Info),
94
case info_struct__current_mfa_not_done(Info2) of
96
server__update_return_value(Info2),
99
server__update_return_value(Info2), % I Know :)
100
Range_info = range_info_from_info_struct(Info2),
102
SpecIC = specialize_IC(IC, Range_info),
103
%% Optional annotation phase controlled by a compiler option
104
case proplists:get_bool(icode_range_analysis_annotate, Options) of
106
NewIC = annotate_IC(SpecIC, Range_info),
107
print_icode_to_file(NewIC, Info2);
111
case proplists:get_bool(icode_range_analysis_insn_count, Options) of
113
Old = hipe_icode_instruction_counter:cfg(IC, MFA, Options),
114
New = hipe_icode_instruction_counter:cfg(SpecIC, MFA, Options),
115
hipe_icode_instruction_counter:compare(MFA, Old, New);
126
%% Handles communication with the information server
129
server__update_return_value(Info) ->
130
Return_range = return_range(Info),
131
Return_range_is_not_set = var_range__is_empty(Return_range) andalso var_range__is_not_other(Return_range),
132
MFA = info_struct__current_mfa(Info),
133
Not_done = info_struct__current_mfa_not_done(Info),
134
Server = info_struct__server(Info),
135
%%io:format("MFA ~p ~p ~n", [MFA, Return_range]),
136
if not Return_range_is_not_set ->
137
%% We are performing an update
140
Wideningvalues = info_struct__wideningvalues(Info),
142
Fun = fun (MessageTree) ->
143
Key = {MFA, return_range},
144
{State, Prev_return_range} =
145
case gb_trees:lookup(Key, MessageTree) of
147
{0, range_init(return_range, empty, false)};
148
{value, {Lookup_return_range, Prev_state}} ->
149
{Prev_state, Lookup_return_range}
152
if (State > ?FUNCTION_FIXPOINT_DEPTH) ->
153
range_widening(Prev_return_range, Return_range,
158
Is_not_updated = var_range__is_equal(Fixed_return_range,
164
gb_trees:enter(Key, {Fixed_return_range, State + 1},
167
%%io:format("A ~p ~n", [A]),
170
Server ! {self(), {transaction, Fun}};
172
Fun = fun(MessageTree) ->
174
Key = {MFA, return_range},
175
Any = range_init(return_range, {neginf, posinf}, true),
176
case gb_trees:lookup(Key, MessageTree) of
178
%%io:format("no returnpoints ~p ~n", [MFA]),
179
gb_trees:enter(Key, {Any, 1},
185
Server ! {self(), {transaction, Fun}};
190
server__update_call_args(MFA, Args, Info) -> %% TODO Needs comments
191
Server = info_struct__server(Info),
192
Server ! {self(), {load, message, {MFA, args}}},
193
Rename_fun = fun(Arg) ->
194
var_range__copy(get_range_from_arg(Arg, Info), param)
200
Insert_args = lists:map(Rename_fun, Args);
201
{value, {Lookup_args, Lookup_state}} ->
202
%% io:format("Lookup_args ~p ~n MFA ~p ~n", [Lookup_args, MFA]),
203
Arg_ranges = lists:map(Rename_fun, Args), %% this isn't needed
204
Tuple_args_list = lists:zipwith(fun(X, Y) -> [X,Y] end,
205
Arg_ranges, Lookup_args),
206
%% io:format("Tuple ~p ~n", [Tuple_args_list]),
207
Union_args = lists:map(fun(Ranges) -> range_union(param, Ranges) end,
209
%% io:format("Lookup state ~p ~n", [Lookup_state]),
211
if Lookup_state > ?FUNCTION_FIXPOINT_DEPTH ->
212
Widening_range_list = lists:zip(Lookup_args, Union_args),
213
Wideningvalues = info_struct__wideningvalues(Info),
214
Widened_ranges = lists:map(
215
fun({Old_range, New_range}) ->
216
range_widening(Old_range, New_range, Wideningvalues)
218
Widening_range_list),
219
%% io:format("New_wided ~p ~n", [R]),
224
Range_tuple_list = lists:zip(Insert_args, Lookup_args),
225
Args_updated = lists:foldl(
226
fun({Range1, Range2}, Bool) ->
227
(Range1 =/= Range2) or Bool
232
%% io:format("~p Insert_args: ~p ~n Args_updated ~p ~n", [MFA, Insert_args, Args_updated]),
235
?not_done_debug("server_update_args break ~n", []),
236
%%io:format("~p insert args ~p ~n", [MFA, Insert_args]),
237
Server ! {self(), {message, {MFA, args}, {Insert_args, Lookup_state + 1}}},
239
info_struct__set_current_mfa_not_done(Info, true);
246
%%--------------------------------------------------------------------------
247
%% Icode helper functions
248
%%--------------------------------------------------------------------------
250
unannotate_var(An_var) ->
251
case hipe_icode:is_annotated_var(An_var) of
253
hipe_icode:unannotate_var(An_var);
258
name_from_icode_var(An_var) ->
259
Var = unannotate_var(An_var),
260
case hipe_icode:is_var(Var) of
262
hipe_icode:var_name(Var);
270
{f, hipe_icode:fvar_name(Var)}
275
get_range_from_args(Arglist, Info) ->
276
lists:map(fun (Arg) -> get_range_from_arg(Arg, Info) end, Arglist).
278
get_range_from_arg(Arg, Info) ->
279
%% TODO: Constants annotated ??
280
UnannoArg = unannotate_var(Arg),
281
case hipe_icode:is_const(UnannoArg) of
283
Value = hipe_icode:const_value(UnannoArg),
284
case is_integer(Value) of
286
range_init(const, {Value, Value}, false);
288
range_init(const, empty, true)
290
false -> % It is a variable
291
case hipe_icode:is_fvar(Arg) of
293
range_init(Arg, empty, true);
295
Var_name = name_from_icode_var(UnannoArg),
296
info_struct__get_range(Var_name, Info)
300
int_range_from_number_val(Number) ->
304
N when is_integer(N) ->
310
int_range_from_number_vals([]) -> empty;
311
int_range_from_number_vals([First_number|Numbers]) ->
313
fun(Number_val, Acc) ->
316
case int_range_from_number_val(Number_val) of
318
New_min = inf_min([Min1, Min2]),
319
New_max = inf_max([Max1, Max2]),
325
case int_range_from_number_val(Number_val) of
333
lists:foldl(The_union, int_range_from_number_val(First_number), Numbers);
334
int_range_from_number_vals(Number) ->
335
int_range_from_number_val(Number).
337
get_range_from_annotation(Arg_info, Key) ->
338
Is_byte = erl_types:t_is_byte(Arg_info),
339
Is_char = erl_types:t_is_char(Arg_info),
340
Is_integer = erl_types:t_is_integer(Arg_info),
343
{{0, ?MAX_BYTE}, false};
345
{{0, ?MAX_CHAR}, false};
347
{{neginf, posinf}, false};
349
Number_vals = erl_types:t_number_vals(Arg_info),
353
[erl_types:t_integer()|Arg_info];
355
[erl_types:t_integer(),Arg_info]
357
Is_only_int = erl_types:t_is_integer(erl_types:t_sup(Arg)),
358
{int_range_from_number_vals(Number_vals), not Is_only_int}
360
range_init(Key, Int_range, Other).
363
[V || V <- Vars, hipe_icode:is_var(unannotate_var(V))].
365
dont_keep_vars(Vars)->
366
[V || V <- Vars, not hipe_icode:is_var(unannotate_var(V))].
369
keep_vars(hipe_icode:defines(I)).
372
keep_vars(hipe_icode:uses(I)).
375
dont_keep_vars(hipe_icode:args(I)).
380
%% Propagates range information using Icode.
383
analyse_icode(IC, Info) ->
384
{Work, Info2} = info_struct__get_work(Info),
387
case info_struct__set_new_current_tree(Label, Info2) of
389
analyse_icode(IC, Info2);
391
%% io:format("Analysing ~p ~n", [Label]),
392
BB = hipe_icode_cfg:bb(IC, Label),
393
Code = hipe_bb:code(BB),
394
%% hipe_icode_pp:pp_block(Code),
395
Info4 = analyse_BB(Code, Info3),
396
analyse_icode(IC, Info4)
402
analyse_BB([Last], Info) ->
403
analyse_last_insn(Last, Info);
404
analyse_BB([Insn|InsnList], Info) ->
405
case analyse_insn(Insn, Info) of
407
?not_done_debug("analyse_BB break ~n", []),
408
info_struct__set_current_mfa_not_done(NewInfo, true);
409
NewInfo = #info_struct{} ->
410
analyse_BB(InsnList, NewInfo)
413
analyse_insn(Insn, Info) ->
414
%% hipe_icode_pp:pp_block([Insn]),
416
#call{} -> analyse_call(Insn, Info);
417
#move{} -> analyse_move(Insn, Info);
418
#phi{} -> analyse_phi(Insn, Info);
419
#fmove{} -> analyse_fmove(Insn, Info);
420
#begin_handler{} -> analyse_begin_handler(Insn, Info)
423
analyse_last_insn(Insn, Info) ->
424
%% hipe_icode_pp:pp_block([Insn]),
425
Case_return = case Insn of
426
#return{} -> analyse_return(Insn, Info);
427
#enter{} -> analyse_enter(Insn, Info);
428
#switch_val{} -> analyse_switch_val(Insn, Info);
429
#'if'{} -> analyse_if(Insn, Info);
430
#goto{} -> analyse_goto(Insn, Info);
431
#type{} -> analyse_type(Insn, Info);
432
#fail{} -> analyse_fail(Insn, Info);
433
#call{} -> analyse_last_call(Insn, Info);
434
#switch_tuple_arity{} ->
435
analyse_switch_tuple_arity(Insn, Info);
436
#begin_try{} -> analyse_begin_try(Insn, Info)
437
%% #begin_handler{} -> analyse_begin_handler(Insn, Info) %% last insn??
440
{break, Updated_info} ->
441
?not_done_debug("analyse_last_insn break ~p ~n", [Insn]),
442
info_struct__set_current_mfa_not_done(Updated_info, true);
443
Updated_info = #info_struct{} -> %TODO ordning p�� labelar ... vad??
444
{_, Return_info} = info_struct__save_current_range_tree({out_tree, info_struct__current_label(Updated_info)}, Updated_info),
449
%%---------------------------------------------------------------------------
450
%% Analysis for all icode instructions
451
%%---------------------------------------------------------------------------
453
analyse_call(Call, Info) ->
454
Args = hipe_icode:args(Call),
455
Dsts = hipe_icode:call_dstlist(Call),
456
%% io:format("Calltype: ~p ~n", [Call]),
460
undef; %%todo asumption that no real var name can be undef
462
name_from_icode_var(Dst)
464
Fun = hipe_icode:call_fun(Call),
465
Type = hipe_icode:call_type(Call),
466
Analysis_result = analyse_call_or_enter_fun(Fun, Args, Key, Dsts, Info, Type),
467
case Analysis_result of
468
{break, Analyse_info} ->
469
{break, Analyse_info};
470
Dst_range = #var_range{} ->
471
% info_struct__insert_range(Dst_range, Info);
473
Annotation_range = get_range_from_dst_annotation(Key, Dsts),
474
Cut_range = range_cut(Key, [Dst_range, Annotation_range]),
475
Is_different = not var_range__is_equal(Dst_range, Cut_range),
477
Warn = info_struct__warn(Info),
478
warning(Cut_range, Dst_range, Warn);
482
info_struct__insert_range(Cut_range, Info);
486
New_Info = #info_struct{} -> New_Info
489
%Analyses a call that is last in an BB.
490
analyse_last_call(Call, Info) ->
491
%% hipe_icode_pp:pp_block([Insn]),
492
case analyse_call(Call, Info) of
495
Info2 = #info_struct{} ->
496
Continuation = hipe_icode:call_continuation(Call),
497
Current_label = info_struct__current_label(Info2),
498
{Updated_edges, Info3} = info_struct__save_current_range_tree({Current_label, Continuation}, Info2),
499
{_, Labels} = lists:unzip(Updated_edges),
500
{Upd_fail_edge, Info4} =
501
case hipe_icode:call_fail_label(Call) of
503
Label when is_integer(Label) ->
504
info_struct__save_current_range_tree({Current_label, Label}, Info3)
506
Info5 = info_struct__add_work(Info4, Labels),
507
{_, Upd_fail_label} = lists:unzip(Upd_fail_edge),
508
info_struct__add_work(Info5, Upd_fail_label)
511
analyse_fmove(Insn, Info) ->
512
Dst_name = hipe_icode:fmove_dst(Insn),
513
Dst_range = range_init(Dst_name, empty, true),
514
info_struct__insert_range(Dst_range, Info).
516
analyse_move(Insn, Info) ->
517
Src = hipe_icode:move_src(Insn),
518
Dst = hipe_icode:move_dst(Insn),
519
Dst_name = name_from_icode_var(Dst),
520
Dst_range = var_range__copy(get_range_from_arg(Src, Info), Dst_name),
521
info_struct__insert_range(Dst_range, Info).
524
phi_widening(Union_range, Info) ->
525
Name = var_range__name(Union_range),
526
Old_range = info_struct__get_phi_range(Name, Info),
527
Dont_wid_min=inf_geq(var_range__min(Union_range), var_range__min(Old_range)),
528
Dont_wid_max=inf_geq(var_range__max(Old_range), var_range__max(Union_range)),
532
inf_min([var_range__min(Union_range),var_range__min(Old_range)]);
539
inf_max([var_range__max(Union_range), var_range__max(Old_range)]);
544
case (Min =:= empty) or (Max =:= empty) of
550
range_init(Name, Range_range, var_range__other(Union_range)).
553
analyse_phi(Phi, Info) ->
554
{_, Args} = lists:unzip(hipe_icode:phi_arglist(Phi)),
555
Dst = hipe_icode:phi_dst(Phi),
556
Dst_name = name_from_icode_var(Dst),
557
Arg_ranges = get_range_from_args(Args, Info),
558
%io:format("Phi-Arg_ranges: ~p ~n", [Arg_ranges]),
559
Temp_dst_range = range_union(Dst_name, Arg_ranges),
560
Label = info_struct__current_label(Info),
561
Counter = info_struct__counter_from_label(Info, Label),
563
if Counter > ?PHIWIDENING ->
564
phi_widening(Temp_dst_range, Info);
568
%io:format("Phi_Dst_range: ~p ~n", [Dst_range]),
569
Info2 = info_struct__set_phi_range(Dst_range, Info),
570
info_struct__insert_range(Dst_range, Info2).
572
analyse_return(Insn, Info) ->
573
[Var] = hipe_icode:return_vars(Insn),
574
Variable = name_from_icode_var(Var),
575
Info2 = info_struct__add_return_var(Variable, Info),
576
Current_label = info_struct__current_label(Info),
577
{_, Info3} = info_struct__save_current_range_tree({Current_label, return}, Info2),
580
analyse_enter(Insn, Info) ->
581
Current_label = info_struct__current_label(Info),
583
%% io:format("Enter ~p ~n", [Insn]),
584
Args = hipe_icode:enter_args(Insn),
585
Fun = hipe_icode:enter_fun(Insn),
586
Analysis_result = analyse_call_or_enter_fun(Fun, Args, Key, [undef], Info, local),
587
case Analysis_result of
588
{break, Analyse_info} ->
589
{break, Analyse_info};
590
Dst_range = #var_range{} ->
591
Dst_range#var_range{var_name = Key}, %% Assert
592
Info3 = info_struct__insert_range(Dst_range, Info),
593
Info4 = info_struct__add_return_var(Key, Info3),
594
{_, Info5} = info_struct__save_current_range_tree({Current_label, return}, Info4),
597
Info4 = info_struct__add_return_var(Key, Info3),
598
{_, Info5} = info_struct__save_current_range_tree({Current_label, return}, Info4),
602
analyse_begin_try(Insn, Info) ->
603
Label = hipe_icode:begin_try_label(Insn),
604
Successor = hipe_icode:begin_try_successor(Insn),
605
Labels = [Label|[Successor]],
606
%% io:format("begin try labels ~p ~n", [Labels]),
607
{Updated_edges, Info2} = info_struct__save_trees_on_edges(Labels, Info, []),
608
{_, Updated_Labels} = lists:unzip(Updated_edges),
609
info_struct__add_work(Info2, Updated_Labels).
611
analyse_begin_handler(Handler, Info) ->
613
fun (Var, InfoAcc) ->
614
Var_range = range_init(
615
name_from_icode_var(Var), {neginf, posinf}, true),
616
info_struct__insert_range(Var_range, InfoAcc)
619
hipe_icode:begin_handler_dstlist(Handler)).
621
analyse_switch_tuple_arity(Switch, Info) ->
622
Cases = hipe_icode:switch_tuple_arity_cases(Switch),
623
Fail = hipe_icode:switch_tuple_arity_fail_label(Switch),
624
{_, Case_labels} = lists:unzip(Cases),
625
Labels = [Fail|Case_labels],
626
%% io:format("switch labels ~p ~n", [Labels]),
627
{Updated_edges, Info2} = info_struct__save_trees_on_edges(Labels, Info, []),
628
{_, Updated_labels} = lists:unzip(Updated_edges),
629
info_struct__add_work(Info2, Updated_labels).
631
analyse_switch_val(Switch, Info) ->
632
Switch_range = get_range_from_arg(hipe_icode:switch_val_arg(Switch), Info),
633
Cases = hipe_icode:switch_val_cases(Switch),
634
%io:format("switch ~p ~p ~n", [Switch, Cases]),
635
{_, Labels} = lists:unzip(Cases),
636
{Fail_range, Range_label_list} = get_range_label_list(Switch_range, Cases, Info, [], []),
637
Fail_label = hipe_icode:switch_val_fail_label(Switch),
638
{Updated_edges, Info2} = info_struct__save_spec_range_trees(Info, [{Fail_range, Fail_label}|Range_label_list], [Fail_label|Labels]),
639
{_, To_labels} = lists:unzip(Updated_edges),
641
info_struct__add_work(Info3, To_labels).
643
analyse_sane_if(If, Info, [Range_1, Range_2]) ->
644
case hipe_icode:if_op(If) of
646
{True_range_2, True_range_1, False_range_2, False_range_1} =
647
range_inequality_propagation(Range_2, Range_1);
649
{Temp_true_range_1, Temp_true_range_2, False_range_1, False_range_2}=
650
range_equality_propagation(Range_1, Range_2),
651
True_range_1 = var_range__set_other(Temp_true_range_1,
652
var_range__other(Range_1)),
653
True_range_2 = var_range__set_other(Temp_true_range_2,
654
var_range__other(Range_2));
656
{True_range_1, True_range_2, False_range_1, False_range_2} =
657
range_inequality_propagation(Range_1, Range_2);
659
{False_range_1, False_range_2, True_range_1, True_range_2} =
660
range_inequality_propagation(Range_1, Range_2);
662
{False_range_2, False_range_1, True_range_2, True_range_1} =
663
range_inequality_propagation(Range_2, Range_1);
665
{True_range_1, True_range_2, False_range_1, False_range_2}=
666
range_equality_propagation(Range_1, Range_2);
668
{False_range_1, False_range_2, True_range_1, True_range_2} =
669
range_equality_propagation(Range_1, Range_2);
671
{Temp_false_range_1, Temp_false_range_2, True_range_1, True_range_2}=
672
range_equality_propagation(Range_1, Range_2),
673
False_range_1 = var_range__set_other(Temp_false_range_1,
674
var_range__other(Range_1)),
675
False_range_2 = var_range__set_other(Temp_false_range_2,
676
var_range__other(Range_2))
679
%% io:format("~nrange_1: ~p, ~nrange_2: ~p ~n if op: ~p ~ntrue_1: ~p, ~ntrue_2: ~p, ~nfalse_1: ~p, ~nfalse_2: ~p ~n", [Range_1, Range_2, hipe_icode:if_op(If), True_range_1, True_range_2, False_range_1, False_range_2]),
681
True_label = hipe_icode:if_true_label(If),
682
False_label = hipe_icode:if_false_label(If),
684
Substitute_list = [{True_range_1, True_label}, {True_range_2, True_label},
685
{False_range_1, False_label}, {False_range_2, False_label}],
686
{Updated_edges, Info2} = info_struct__save_spec_range_trees(Info, Substitute_list, [True_label, False_label]),
687
{_, To_labels} = lists:unzip(Updated_edges),
688
%% io:format("If ~p ~n", [To_labels]),
690
%% Old_vals = [var_range__min(Range_1), var_range__max(Range_1), var_range__min(Range_2), var_range__max(Range_2)],
692
%% Info3 = lists:foldl(fun (Val, Info) ->
693
%% info_struct__add_wideningvalue(Val, Info)
697
info_struct__add_work(Info2, To_labels).
699
analyse_if(If, Info) ->
700
%% hipe_icode_pp:pp_block([If]),
701
Args = hipe_icode:if_args(If),
702
%% io:format("if args ~p ~n~p ~n", [get_range_from_args(Args, Info), Args]),
703
%% io:format("ifop ~p ~n", [hipe_icode:if_op(If)]),
704
case get_range_from_args(Args, Info) of
706
Current_label = info_struct__current_label(Info),
707
New_work = [hipe_icode:if_true_label(If), hipe_icode:if_false_label(If)],
709
fun (Label, InfoAcc) ->
710
{Updated_edges, InfoAcc2} = info_struct__save_current_range_tree({Current_label, Label}, InfoAcc),
711
{_, To_labels} = lists:unzip(Updated_edges),
712
info_struct__add_work(InfoAcc2, To_labels)
716
[_Range_1, _Range_2] = Ranges ->
717
analyse_sane_if(If, Info, Ranges)
720
analyse_goto(Insn, Info) ->
721
Goto_label = hipe_icode:goto_label(Insn),
722
Current_label = info_struct__current_label(Info),
723
{Updated_edges, Info2} = info_struct__save_current_range_tree({Current_label, Goto_label}, Info),
724
{_, To_labels} = lists:unzip(Updated_edges),
725
info_struct__add_work(Info2, To_labels).
727
analyse_type(Type, Info) ->
728
Type_type = hipe_icode:type_type(Type),
729
[First_arg|_] = hipe_icode:type_args(Type),
730
Var_name = name_from_icode_var(First_arg),
731
Old_var_range = info_struct__get_range(Var_name, Info),
734
True_range = range_cut(Var_name,
735
[range_init(Var_name, {N, N}, false),
739
case var_range__range(Old_var_range) of
741
New_small = inf_geq(Min, N),
742
New_large = inf_geq(N, Max),
758
var_range__other(Old_var_range)
761
%% info_struct__add_wideningvalue(N, Info);
764
True_range = var_range__set_other(Old_var_range, false),
765
False_range = range_init(Var_name, empty, var_range__other(Old_var_range));
767
True_range = var_range__set_other(Old_var_range, true), %%Todo assert, cut
768
False_range = Old_var_range
771
True_label = hipe_icode:type_true_label(Type),
772
False_label = hipe_icode:type_false_label(Type),
773
Updates = [{True_range, True_label}, {False_range, False_label}],
774
Labels = [True_label, False_label],
775
{Updated_edges, Info2} = info_struct__save_spec_range_trees(Info, Updates, Labels),
776
{_, To_labels} = lists:unzip(Updated_edges),
777
info_struct__add_work(Info2, To_labels).
780
analyse_fail(_Fail, Info) ->
781
Current_label = info_struct__current_label(Info),
782
{_, Info2} = info_struct__save_current_range_tree({Current_label, return}, Info),
786
%%---------------------------------------------------------------------------
787
%% Helper functions for icode instructions
788
%%---------------------------------------------------------------------------
790
analyse_other_module_fcall(Key, {M,F,A}, Info, Args) ->
791
%% io:format("fcall to other module ~p ~n", [{M,F,A}]),
792
Mfa_type = erl_bif_types:type(M,F,A),
794
case erl_bif_types:arg_types(M,F,A) of
799
fun (Arg, Arg_type) ->
800
Prop_range = get_range_from_arg(Arg, Info),
801
Name = name_from_icode_var(Arg),
802
Anno_range = get_range_from_annotation(Arg_type, Name),
803
range_cut(Name, [Prop_range, Anno_range])
807
fun (Range, InfoAcc) ->
808
info_struct__insert_range(Range, InfoAcc)
813
Return_range = get_range_from_annotation(Mfa_type, Key),
814
info_struct__insert_range(Return_range, Info2).
816
analyse_fcall(Key, {M,F,A}, Info, Args) ->
817
%io:format("~p fcall ~p ~n", [self(), {M,F,A}]),
818
Current_mfa = info_struct__current_mfa(Info),
819
Server = info_struct__server(Info),
821
if (Current_mfa =:= {M,F,A}) ->
822
info_struct__set_is_recursive(true, Info);
826
Server ! {self(), {load, message, {{M,F,A}, return_range}}},
831
%% is_recursive h��r??
832
%?not_done_debug("need info ~p ~n", [{M,F,A}]),
833
Info3 = server__update_call_args({M,F,A}, Args, Info2),
834
Range = range_init(Key, {neginf, posinf}, true),
835
info_struct__insert_range(Range, Info3);
838
%% doesn't save args info about function in other module
839
analyse_other_module_fcall(Key, {M,F,A}, Info2, Args)
841
{value, {Lookup_range, _Final}} ->
842
Info3 = server__update_call_args({M,F,A}, Args, Info2),
843
Range = var_range__copy(Lookup_range, Key),
844
info_struct__insert_range(Range, Info3)
847
analyse_bs_get_integer_funs(Size, Flags, true) ->
848
Signed = Flags band 4,
850
Max = round(math:pow(2, Size)) - 1,
858
analyse_bs_get_integer_funs(_Size, _Flags, false) -> {neginf, posinf}.
861
get_range_from_dst_annotation(Key, Dsts) ->
864
range_init(Key, {neginf, posinf}, true);
866
range_init(Key, {neginf, posinf}, true);
867
[Dst|_] -> %todo the others are what??
868
case hipe_icode:is_annotated_var(Dst) of
870
get_range_from_annotation(hipe_icode:var_annotation(Dst), Key);
872
range_init(Key, {neginf, posinf}, true)
877
?call_or_enter_debug("fun type ~p ~n", [Fun]),
880
analyse_call_or_enter_fun(Fun, Args, Key, Dsts, Info, CallType) ->
881
%% io:format("Fun ~p ~n", [Fun]),
882
case lasy_type(Fun) of
884
?call_or_enter_debug("bin", []),
885
[Arg_range1|[Arg_range2|[]]] = get_range_from_args(Args, Info),
886
A1_is_empty = var_range__is_empty(Arg_range1),
887
A2_is_empty = var_range__is_empty(Arg_range2),
888
if A1_is_empty or A2_is_empty ->
889
Other = var_range__other(Arg_range1) or var_range__other(Arg_range1),
890
range_init(Key, empty, Other);
892
Operation(Key, Arg_range1, Arg_range2)
894
{unary, Operation} ->
895
?call_or_enter_debug("unary", []),
896
[Arg_range] = get_range_from_args(Args, Info),
897
case var_range__is_empty(Arg_range) of
899
range_init(Key, empty, true);
901
Operation(Key, Arg_range)
904
?call_or_enter_debug("fcall", []),
907
case analyse_fcall(Key, {M,F,A}, Info, Args) of
908
Fcallinfo = #info_struct{} ->
909
Fcall_range = info_struct__get_range(Key, Fcallinfo),
910
Annotation_range = get_range_from_dst_annotation(Key, Dsts),
911
New_range = range_cut(Key, [Fcall_range, Annotation_range]),
912
info_struct__insert_range(New_range, Fcallinfo);
917
analyse_other_module_fcall(Key, {M,F,A}, Info, Args)
919
% get_range_from_dst_annotation(Key, Dsts)
922
?call_or_enter_debug("not int", []),
923
range_init(Key, empty, true);
925
%% [range_init(Key, empty, true),
926
%% get_range_from_dst_annotation(Key, Dsts)]);
929
?call_or_enter_debug("not analysed", []),
930
get_range_from_dst_annotation(Key, Dsts);
931
{hipe_bs_primop, {bs_get_integer, Size, Flags}} ->
932
?call_or_enter_debug("bs1", []),
933
{Min, Max} = analyse_bs_get_integer_funs(Size, Flags, length(Args) =:= 4),
934
range_init(Key, {Min, Max}, false);
935
{hipe_bs_primop, {bs_get_integer_2, Size, Flags}} ->
936
?call_or_enter_debug("bs2", []),
937
{Min, Max} = analyse_bs_get_integer_funs(Size, Flags, length(Args) =:= 1),
938
range_init(Key, {Min, Max}, false);
939
{hipe_bs_primop, _} = Primop ->
940
?call_or_enter_debug("bs3 ~p ~n", [Primop]),
941
Type = hipe_icode_primops:type(Primop),
942
get_range_from_annotation(Type, Key);
943
{hipe_bsi_primop, {bs_get_integer, Size, Flags}} ->
944
?call_or_enter_debug("bs4", []),
945
{Min, Max} = analyse_bs_get_integer_funs(Size, Flags, true),
946
range_init(Key, {Min, Max}, false)
950
%% basic_type/1 specifies how to analyze a call or enter fun
953
%% Arithmetic operations
954
basic_type('+') -> {bin, fun(Name, R1, R2) -> range_add(Name, R1, R2) end};
955
basic_type('-') -> {bin, fun(Name, R1, R2) -> range_sub(Name, R1, R2) end};
956
basic_type('*') -> {bin, fun(Name, R1, R2) -> range_mult(Name, R1, R2) end};
957
basic_type('/') -> not_int;
958
basic_type('div') -> {bin, fun(Name, R1, R2) -> range_div(Name, R1, R2) end};
959
basic_type('rem') -> {bin, fun(Name, R1, R2) -> range_rem(Name, R1, R2) end};
960
basic_type('bor') -> {bin, fun(Name, R1, R2) -> range_bor(Name, R1, R2) end};
961
basic_type('band') -> {bin, fun(Name, R1, R2) -> range_band(Name, R1, R2) end};
962
basic_type('bxor') -> {bin, fun(Name, R1, R2) -> range_bxor(Name, R1, R2) end};
963
basic_type('bnot') -> {unary, fun(Name, R1) -> range_bnot(Name, R1) end};
964
basic_type('bsl') -> {bin, fun(Name, R1, R2) -> range_bsl(Name, R1, R2) end};
965
basic_type('bsr') -> {bin, fun(Name, R1, R2) -> range_bsr(Name, R1, R2) end};
967
basic_type('unsafe_bor') ->
968
{bin, fun(Name, R1, R2) -> range_bor(Name, R1, R2) end};
969
basic_type('unsafe_band') ->
970
{bin, fun(Name, R1, R2) -> range_band(Name, R1, R2) end};
971
basic_type('unsafe_bxor') ->
972
{bin, fun(Name, R1, R2) -> range_bxor(Name, R1, R2) end};
973
basic_type('unsafe_bnot') ->
974
{unary, fun(Name, R1) -> range_bnot(Name, R1) end};
976
basic_type('unsafe_bsl') ->
977
{bin, fun(Name, R1, R2) -> range_bsl(Name, R1, R2) end};
978
basic_type('unsafe_bsr') ->
979
{bin, fun(Name, R1, R2) -> range_bsr(Name, R1, R2) end};
981
basic_type('unsafe_add') ->
982
{bin, fun(Name, R1, R2) -> range_add(Name, R1, R2) end};
983
basic_type('unsafe_sub') ->
984
{bin, fun(Name, R1, R2) -> range_sub(Name, R1, R2) end};
985
basic_type('extra_unsafe_add') ->
986
{bin, fun(Name, R1, R2) -> range_add(Name, R1, R2) end};
987
basic_type('extra_unsafe_sub') ->
988
{bin, fun(Name, R1, R2) -> range_sub(Name, R1, R2) end};
991
basic_type({hipe_bs_primop, Todo}) -> {hipe_bs_primop, Todo};
992
basic_type({hipe_bs_primop2, Todo}) -> {hipe_bs_primop, Todo};
993
basic_type({hipe_bsi_primop,{bs_get_integer, Size, _B, Flags}}) ->
994
{hipe_bsi_primop,{bs_get_integer, Size, Flags}};
995
basic_type({hipe_bsi_primop,bs_get_orig}) -> not_analysed;
996
basic_type({hipe_bsi_primop,bs_get_orig_offset}) -> not_analysed;
997
basic_type({hipe_bsi_primop,bs_get_size}) -> not_analysed;
998
basic_type({hipe_bsi_primop,bs_add}) -> not_analysed;
999
basic_type({hipe_bsi_primop,bs_div_test}) -> not_analysed;
1000
basic_type({hipe_bsi_primop,bs_size_test_all}) -> not_analysed;
1001
basic_type({hipe_bsi_primop,{bs_get_binary_all,_A,_B}}) -> not_analysed;
1002
basic_type({hipe_bsi_primop,{bs_make_size,_A}}) -> not_analysed;
1003
basic_type({hipe_bsi_primop,bs_size_test}) -> not_analysed;
1004
basic_type({hipe_bsi_primop,{bs_get_binary,_A,_B,_C}}) -> not_analysed;
1005
basic_type({hipe_bsi_primop,{bs_get_binary,_A,_B}}) -> not_analysed;
1008
basic_type(call_fun) -> not_analysed;
1009
basic_type({closure_element, _N}) -> not_analysed;
1010
basic_type('redtest') -> not_analysed;
1011
basic_type({gc_test, _}) -> not_analysed;
1012
basic_type(clear_timeout) -> not_analysed;
1013
basic_type(set_timeout) -> not_analysed;
1014
basic_type({apply_N, _N}) -> not_analysed;
1017
basic_type(check_get_msg) -> not_analysed;
1018
basic_type(select_msg) -> not_analysed;
1019
basic_type(next_msg) -> not_analysed;
1020
basic_type(suspend_msg) -> not_analysed;
1023
basic_type({mkfun, _Fun, _N1, _N2}) -> not_int;
1024
basic_type({M,F,A}) -> {fcall, {M,F,A}};
1025
basic_type(enter_fun) -> not_analysed;
1028
basic_type(conv_to_float) -> not_int;
1029
basic_type(fclearerror) -> not_analysed;
1030
basic_type(fp_add) -> not_int;
1031
basic_type(fp_mul) -> not_int;
1032
basic_type(fp_div) -> not_int;
1033
basic_type(fcheckerror) -> not_analysed;
1034
basic_type(unsafe_tag_float) -> not_int;
1035
basic_type(unsafe_untag_float) -> not_int;
1036
basic_type(fp_sub) -> not_int;
1037
basic_type(fnegate) -> not_int;
1039
%% Lists, tuples, records
1040
basic_type(mktuple) -> not_int;
1041
basic_type(cons) -> not_int;
1042
basic_type({unsafe_element, _N}) -> not_analysed;
1043
basic_type(unsafe_hd) -> not_analysed;
1044
basic_type(unsafe_tl) -> not_int;
1045
basic_type({element, _Elems}) -> not_analysed;
1046
basic_type({unsafe_update_element, _N}) -> not_analysed.
1049
%% todo rename switch_val
1050
get_range_label_list(Range, [], _Info, Range_label_list, []) ->
1051
{Range, Range_label_list};
1052
get_range_label_list(Range, [], _Info, Range_label_list, Constants_to_cut) ->
1053
Sorted_constants = lists:sort(Constants_to_cut),
1054
[Smallest|_] = Sorted_constants,
1055
Largest = lists:last(Sorted_constants),
1056
Min_value = var_range__min(Range),
1057
if Min_value >= Smallest ->
1058
Sorted_constants_to_cut = Sorted_constants;
1060
Sorted_constants_to_cut = lists:reverse(Sorted_constants)
1064
fun(Const, Acc_range) ->
1065
Const_range = range_init(const, {Const, Const}, false),
1066
range_remove_constant(Acc_range, Const_range)
1069
Sorted_constants_to_cut),
1071
case var_range__range(New_temp_range) of
1073
New_small = inf_geq(Smallest, Max),
1074
New_large = inf_geq(Min, Largest),
1076
if New_small -> Smallest - 1;
1080
if New_large -> Largest + 1;
1088
%io:format("Range ~p ~n", [New_range_range]),
1089
New_range = range_init(var_range__name(Range), New_range_range, var_range__other(Range)),
1090
{New_range, Range_label_list};
1091
get_range_label_list(Range, [Case|Cases], Info, Range_label_list, Constants_to_cut) ->
1092
{Arg, Label} = Case,
1093
Arg_range = get_range_from_arg(Arg, Info),
1094
Cut_range = range_cut(var_range__name(Range), [Arg_range, Range]),
1095
Arg_name = var_range__name(Arg_range),
1096
Is_const = var_range__is_constant(Arg_range),
1097
Is_empty_arg = var_range__is_empty(Cut_range),
1098
New_constants_to_cut =
1100
{Constant_value, Constant_value} = var_range__range(Arg_range),
1101
[Constant_value|Constants_to_cut];
1105
if not Is_empty_arg ->
1106
Arg_cut_range = var_range__copy(Cut_range, Arg_name),
1107
get_range_label_list(Range, Cases, Info, [{Arg_cut_range, Label},{Cut_range, Label}|Range_label_list], New_constants_to_cut);
1109
get_range_label_list(Range, Cases, Info, Range_label_list, New_constants_to_cut)
1113
%% Icode annotation and pritty print
1115
%% Annotates icode with range information
1118
annotate_IC(IC, Range_info) ->
1119
Label_list = hipe_icode_cfg:labels(IC),
1121
fun (Label, ICAcc) ->
1122
case range_info__is_live(Range_info, Label) of
1124
BB = hipe_icode_cfg:bb(ICAcc, Label),
1125
Code = hipe_bb:code(BB),
1126
NewCode = annotate_BB(Code, Range_info, Label),
1127
NewBB = hipe_bb:code_update(BB, NewCode),
1128
hipe_icode_cfg:bb_add(ICAcc, Label, NewBB);
1136
annotate_BB(Insts, Range_info, Label) ->
1137
lists:map(fun (Inst) -> annotate_insn(Inst, Range_info, Label) end, Insts).
1139
annotate_insn(Insn, Range_info, Current_label) ->
1140
Def = defines(Insn),
1142
Fun = fun (X, Y) -> hipe_icode:annotate_var(X, Y) end,
1143
Lookup_def = fun (Info, Label, Var) ->
1144
range_info__def_range(Info, Label, name_from_icode_var(Var))
1146
Lookup_use = fun (Info, Label, Var) ->
1147
range_info__use_range(Info, Label, name_from_icode_var(Var))
1149
Old_anno = fun (X) -> case hipe_icode:is_annotated_var(X) of
1151
hipe_icode:var_annotation(X);
1156
DefSubst = [{X, Fun(X, {Old_anno(X), Lookup_def(Range_info, Current_label, X)})}||X<-Def],
1157
UseSubst = [{X, Fun(X, {Old_anno(X), Lookup_use(Range_info, Current_label, X)})}||X<-Use],
1158
case DefSubst ++ UseSubst of
1162
hipe_icode:subst(Subst, Insn)
1165
pp_args([]) -> []; %%lists_map ??
1166
pp_args([Param]) -> to_string(Param);
1167
pp_args([Param|Params]) ->
1168
to_string(Param) ++ ", " ++ pp_args(Params).
1170
pp_function_info(Info, File) ->
1171
Return_range = return_range(Info),
1172
Range = var_range__range(Return_range),
1173
Params = input_range(Info),
1175
case var_range__other(Return_range) of
1176
true -> "may return other";
1177
false -> "only integer return values"
1179
{M, F, _A} = info_struct__current_mfa(Info),
1180
ParamsString = lists:flatten(pp_args(Params)),
1181
io:format(File, "~p:~p/(~s) -> ~p, ~s ~n~n",
1182
[M, F, ParamsString, Range, R_other]).
1185
pp_range_tree(Info) ->
1186
List = gb_trees:to_list(info_struct__range_tree(Info)),
1187
io:format("Range List, Label ~p: ~n", [info_struct__current_label(Info)]),
1188
pp_range_list(List).
1192
pp_range_list(List) ->
1193
lists:foreach(fun(R) -> pp_range(R) end, List).
1198
Int_range = var_range__range(Range),
1199
Other = var_range__other(Range),
1200
Name = var_range__name(Range),
1201
io:format("~w, ~w ~w ~n", [Name, Int_range, Other]).
1204
print_icode_to_file(IC, Info) ->
1205
{M,F,A} = info_struct__current_mfa(Info),
1206
FileName = atom_to_list(M) ++ "_" ++ atom_to_list(F) ++ "_" ++ integer_to_list(A) ++ ".anno",
1207
%% io:format("filename ~p ~n", [FileName]),
1208
case file:open(FileName, write) of
1210
pp_function_info(Info, File),
1211
hipe_icode_pp:pp(File, hipe_icode_cfg:cfg_to_linear(IC)),
1220
%% Icode specialization
1222
%% Modifies calls to arithmetic operations
1225
specialize_IC(IC, Range_info) ->
1226
Label_list = hipe_icode_cfg:labels(IC),
1228
fun (Label, ICAcc) ->
1229
%% hipe_icode_pp:pp_block(Code),
1230
case range_info__is_live(Range_info, Label) of
1232
BB = hipe_icode_cfg:bb(ICAcc, Label),
1233
Code = hipe_bb:code(BB),
1234
NewCode = specialize_BB(Code, Range_info, Label),
1235
NewBB = hipe_bb:code_update(BB, NewCode),
1236
hipe_icode_cfg:bb_add(ICAcc, Label, NewBB);
1238
Warn = range_info__warn(Range_info),
1239
warning("Dead code", Label, Warn),
1246
specialize_BB(Insts, Range_info, Label) ->
1247
lists:map(fun (Insn) -> specialize_insn(Insn, Range_info, Label) end, Insts).
1249
specialize_insn(Insn, Range_info, Label) ->
1250
%% hipe_icode_pp:pp_block([Insn]),
1254
specialize_call(Insn, Range_info, Label);
1256
specialize_enter(Insn, Range_info, Label);
1258
specialize_if(Insn, Range_info, Label);
1264
%% specialized_op(op, specialization)
1265
specialized_op('+', safe, _) -> '+';
1266
specialized_op('+', unsafe, _) -> 'unsafe_add';
1267
specialized_op('+', extra_unsafe, _) -> 'extra_unsafe_add';
1269
specialized_op('-', safe, _) -> '-';
1270
specialized_op('-', unsafe, _) -> 'unsafe_sub'; %%??
1271
specialized_op('-', extra_unsafe, _) -> 'extra_unsafe_sub'; %extra
1273
specialized_op('*', safe, _) -> '*';
1274
specialized_op('*', unsafe, Warn) ->
1275
warning('could be unsafe_mult', '*', Warn),
1277
specialized_op('*', extra_unsafe, Warn) ->
1278
warning('could be extra_unsafe_mult', '*', Warn),
1281
specialized_op('band', safe, _) -> 'band';
1282
specialized_op('band', unsafe, _) ->
1283
io:format("band(Fix, Fix) -> Big ~n"), exit(1);
1284
specialized_op('band', extra_unsafe, _) -> 'unsafe_band';
1286
specialized_op('bor', safe, _) -> 'bor';
1287
specialized_op('bor', unsafe, _) ->
1288
io:format("bor(Fix, Fix) -> Big ~n"), exit(1);
1289
specialized_op('bor', extra_unsafe, _) -> 'unsafe_bor';
1291
specialized_op('bxor', safe, _) -> 'bxor';
1292
specialized_op('bxor', unsafe, _) ->
1293
io:format("bxor(Fix, Fix) -> Big ~n"), exit(1);
1294
specialized_op('bxor', extra_unsafe, _) -> 'unsafe_bxor';
1296
specialized_op('bnot', safe, _) -> 'bnot';
1297
specialized_op('bnot', unsafe, _) -> 'bnot'; %% todo correct?
1298
specialized_op('bnot', extra_unsafe, _) -> 'unsafe_bnot';
1300
specialized_op('bsl', safe, _) -> 'bsl';
1301
specialized_op('bsl', unsafe, _) -> 'bsl';
1302
specialized_op('bsl', extra_unsafe, _) -> 'unsafe_bsl';
1304
specialized_op('bsr', safe, _) -> 'bsr';
1305
specialized_op('bsr', unsafe, _) -> 'bsr';
1306
specialized_op('bsr', extra_unsafe, _) -> 'unsafe_bsr';
1308
specialized_op('unsafe_add', safe, Warn) ->
1309
warning('unsafe_add', safe, Warn), 'unsafe_add';
1310
specialized_op('unsafe_add', unsafe, _) -> 'unsafe_add';
1311
specialized_op('unsafe_add', extra_unsafe, _) -> 'extra_unsafe_add';
1313
specialized_op('unsafe_sub', safe, Warn) ->
1314
warning('unsafe_sub', safe, Warn), 'unsafe_sub';
1315
specialized_op('unsafe_sub', unsafe, _) -> 'unsafe_sub';
1316
specialized_op('unsafe_sub', extra_unsafe, _) -> 'unsafe_sub';
1318
%% TODO: remove when not needed
1319
specialized_op('extra_unsafe_add', safe, Warn) ->
1320
warning('extra_unsafe_add', safe, Warn), 'extra_unsafe_add';
1321
specialized_op('extra_unsafe_add', unsafe, Warn) ->
1322
warning('extra_unsafe_add', unsafe, Warn), 'extra_unsafe_add';
1323
specialized_op('extra_unsafe_add', extra_unsafe, _) -> 'extra_unsafe_add';
1325
specialized_op(Op, _, _) -> Op.
1328
specialized_if_op('<', true) -> 'fixnum_lt';
1329
specialized_if_op('=<', true) -> 'fixnum_le';
1330
specialized_if_op('>', true) -> 'fixnum_gt';
1331
specialized_if_op('>=', true) -> 'fixnum_ge';
1332
specialized_if_op('=:=', true) -> 'fixnum_eq';
1333
specialized_if_op('=/=', true) -> 'fixnum_neq';
1334
specialized_if_op(Op, _) -> Op.
1337
make_const({reg, N}, Range_info, Label) ->
1338
range_info__def_range(Range_info, Label, {reg, N});
1339
make_const({const, {flat, N}}, _, _) when is_integer(N) ->
1340
range_init(const, {N, N}, false);
1341
make_const({const, _}, _, _) -> range_init(const, empty, true);
1342
make_const({fvar, _}, _, _) -> range_init(const, empty, true).
1344
specialize_if(If, Range_info, Label) ->
1345
IfOp = hipe_icode:if_op(If),
1346
Use_ranges = lists:map(fun (Var) ->
1347
range_info__use_range(Range_info, Label,
1348
name_from_icode_var(Var))
1350
Use_constants = lists:map(fun (Const) ->
1351
make_const(Const, Range_info, Label)
1353
RangeFun = fun(Range) ->
1354
var_range__is_fixnum(Range) andalso
1355
(var_range__other(Range) =:= false)
1357
New_if_op = specialized_if_op(IfOp,
1358
lists:all(RangeFun, Use_ranges ++ Use_constants)),
1359
hipe_icode:if_op_update(If, New_if_op).
1363
specialize_call(Call, Range_info, Label) ->
1364
Fun = hipe_icode:call_fun(Call),
1365
New_fun = specialize_call_or_enter(Fun, Call, Range_info, Label),
1366
hipe_icode:call_fun_update(Call, New_fun).
1368
specialize_enter(Enter, Range_info, Label) ->
1369
Fun = hipe_icode:enter_fun(Enter),
1370
New_fun = specialize_call_or_enter(Fun, Enter, Range_info, Label),
1371
hipe_icode:enter_fun_update(Enter, New_fun).
1373
%% todo dont do unnecessary work
1374
specialize_call_or_enter(Fun, Operation, Range_info, Label) ->
1375
Warn = range_info__warn(Range_info),
1376
Use_ranges = lists:map(fun (Var) ->
1377
range_info__use_range(Range_info, Label,
1378
name_from_icode_var(Var))
1379
end, uses(Operation)),
1380
Use_constants = lists:map(fun (Const) ->
1381
make_const(Const, Range_info, Label)
1382
end, consts(Operation)),
1383
Def_ranges = lists:map(fun (Var) ->
1384
range_info__def_range(Range_info, Label,
1385
name_from_icode_var(Var))
1386
end, defines(Operation)),
1387
%% Range_list = Use_ranges ++ Def_ranges,
1388
%% io:format("Fun ~p, ~nRange_list: ~p ~n", [Fun, Use_ranges ++ Def_ranges]),
1389
%% pp_range_list(Range_list),
1390
RangeFun = fun(Range) ->
1391
var_range__is_fixnum(Range) andalso
1392
(var_range__other(Range) =:= false)
1394
Use_fixnum = lists:all(RangeFun, Use_ranges ++ Use_constants),
1395
Def_fixnum = lists:all(RangeFun, Def_ranges),
1396
%% todo remove when tired of it.
1397
lists:map(fun(Range) ->
1398
case var_range__is_constant(Range) of
1400
warning('Found constant range', {Range, Label}, Warn);
1405
Use_ranges ++ Def_ranges),
1407
if Use_fixnum and Def_fixnum ->
1414
New_fun = specialized_op(Fun, Fixnums, Warn),
1415
if New_fun =/= Fun ->
1416
info(New_fun, Fun, Warn);
1426
%% Functionallity for the info struct
1429
%%---------------------------------------------------------------------------
1431
%%---------------------------------------------------------------------------
1433
info_struct__init(IC, Server, Options, Current_mfa = {_M, F, A}) ->
1434
Exports = proplists:get_value(exports, Options),
1436
Is_exported = lists:member(Current_fa, Exports),
1437
StartLabel = hipe_icode_cfg:start_label(IC),
1438
Params = hipe_icode_cfg:params(IC),
1439
Liveness = hipe_icode_liveness:analyze(hipe_icode_type:unannotate_cfg(IC)), %todo
1440
Pred_map = hipe_icode_cfg:pred_map(IC),
1441
Is_closure = hipe_icode_cfg:is_closure(IC),
1442
Warn = proplists:get_bool(icode_range_analysis_warn, Options),
1443
%% io:format("~p analysing ~p ~n", [self(), Current_mfa]),
1444
Info = #info_struct{current_mfa=Current_mfa,
1445
startlabel = StartLabel,
1447
liveness = Liveness,
1448
worklist = init_work(),
1452
Server ! {self(), {load, message, {Current_mfa, args}}},
1458
{value, {Lookup_args, _Lookup_state}} ->
1461
%% io:format("MFA: ~p Params: ~p Args: ~p ~n", [info_struct__current_mfa(Info), Params, Arg_ranges]),
1462
case info_struct__add_params(Params, Info, Arg_ranges, Is_exported, Is_closure) of
1466
info_struct__add_work(Info2, [info_struct__startlabel(Info2)])
1469
%%---------------------------------------------------------------------------
1470
%% Set/Get functions
1471
%%---------------------------------------------------------------------------
1473
info_struct__get_range_tree(Tree_name, Info) ->
1474
case gb_trees:lookup(Tree_name, info_struct__range_trees(Info)) of
1481
%%info_struct__add_wideningvalue(_Value, Info) ->
1482
%% Wideningvalues = info_struct__wideningvalues(Info),
1483
%% New_wideningvalues = insert_ordered(Wideningvalues, Value),
1484
%% Info#info_struct{wideningvalues=New_wideningvalues}.
1487
info_struct__wideningvalues(#info_struct{wideningvalues = Values}) -> Values.
1489
info_struct__insert_range(Var_range,Info) ->
1490
Key = var_range__name(Var_range),
1491
Tree = info_struct__range_tree(Info),
1492
Info#info_struct{current_range_tree=gb_trees:enter(Key, Var_range, Tree)}.
1494
info_struct__live_labels(#info_struct{live_labels=Labels}) -> Labels.
1496
info_struct__server(#info_struct{server=Server}) -> Server.
1498
info_struct__live_vars(#info_struct{liveness=Liveness}, Label) ->
1499
hipe_icode_liveness:livein(Liveness, Label).
1501
info_struct__increment_label_counter(Info = #info_struct{label_counters = Counters}, Label) ->
1502
case gb_trees:lookup(Label, Counters) of
1506
NewCounter = Counter + 1
1508
New_label_counter_tree = gb_trees:enter(Label, NewCounter, Counters),
1509
Info#info_struct{label_counters = New_label_counter_tree}.
1511
info_struct__counter_from_label(#info_struct{label_counters = Counters}, Label) ->
1512
case gb_trees:lookup(Label, Counters) of
1519
info_struct__get_phi_range(Dst_name, #info_struct{phi_values=Tree}) ->
1520
case gb_trees:lookup(Dst_name, Tree) of
1522
range_init(Dst_name, empty, false);
1527
info_struct__set_phi_range(Range, #info_struct{phi_values=Tree} = Info) ->
1528
New_tree = gb_trees:enter(var_range__name(Range), Range, Tree),
1529
Info#info_struct{phi_values=New_tree}.
1531
info_struct__current_mfa(#info_struct{current_mfa=Mfa}) -> Mfa.
1533
info_struct__set_current_mfa_not_done(Info, Bool) ->
1534
Info#info_struct{current_mfa_not_done=Bool}.
1536
info_struct__current_mfa_not_done(#info_struct{current_mfa_not_done=NotDone,
1539
is_recursive = Recursive} = Info) ->
1544
Server ! {self(), {load, message, {MFA, return_range}}},
1548
range_init(return_range, empty, false);
1549
{value, {Lookup_range, _Final}} ->
1552
not var_range__is_equal(return_range(Info), Old_return);
1557
info_struct__predmap(#info_struct{predmap=Pred}) -> Pred.
1559
info_struct__range_tree(#info_struct{current_range_tree=Tree}) -> Tree.
1561
info_struct__range_trees(#info_struct{range_trees=Tree}) -> Tree.
1563
info_struct__return_vars(#info_struct{return_vars=Vars}) -> Vars.
1565
info_struct__startlabel(#info_struct{startlabel=StartLabel}) -> StartLabel.
1567
info_struct__worklist(#info_struct{worklist=List}) -> List.
1569
info_struct__add_live_labels(Info, Label_list) ->
1570
lists:foldl(fun(Label, InfoAcc) ->
1571
Labels = info_struct__live_labels(InfoAcc),
1572
Info#info_struct{live_labels = gb_sets:add(Label, Labels)}
1577
info_struct__add_work(Info, NewWork) ->
1578
%% io:format("NewWork ~p ~n", [NewWork]),
1579
Worklist = info_struct__worklist(Info),
1580
New_worklist = add_work(Worklist, NewWork),
1581
Info2 = info_struct__add_live_labels(Info, NewWork),
1582
Info2#info_struct{worklist = New_worklist}.
1584
info_struct__current_label(#info_struct{current_label=Label}) -> Label.
1586
info_struct__add_params([], Info, _, _, _) ->
1587
StartLabel = info_struct__startlabel(Info),
1588
{_, Info2} = info_struct__save_current_range_tree({params, StartLabel}, Info),
1590
info_struct__add_params([Param|ParamList], Info, Arg_range_list,
1591
Is_exported, Is_closure) ->
1592
Key = name_from_icode_var(Param),
1593
{List, Range_info} =
1594
if Is_exported or Is_closure ->
1595
{[], range_init(Key, {neginf, posinf}, true)};
1597
case Arg_range_list of
1598
[Arg_range|Arg_range_tail] -> %% var_range__copy ??
1599
Int_range = var_range__range(Arg_range),
1600
Other = var_range__other(Arg_range),
1601
New_arg_range = range_init(Key, Int_range, Other),
1602
{Arg_range_tail, New_arg_range};
1604
?not_done_debug("In add params ~n", []),
1612
%% `io:format("MFA: ~p arg: ~p ~n", [info_struct__current_mfa(Info), New_range]),
1613
%% io:format("Param ~p range: ~p ~n", [Param, New_range]),
1614
NewInfo = info_struct__insert_range(Range, Info),
1615
info_struct__add_params(ParamList, NewInfo, List, Is_exported, Is_closure)
1618
info_struct__add_return_var(Variable, Info) ->
1619
Return_list = info_struct__return_vars(Info),
1620
Label = info_struct__current_label(Info),
1621
Key = {Variable, Label},
1622
case lists:member(Key, Return_list) of
1626
Info#info_struct{return_vars = [Key|Return_list]}
1629
info_struct__get_range(Var, Info) ->
1630
case gb_trees:lookup(Var, info_struct__range_tree(Info)) of
1632
range_init(Var, empty, false);
1637
%info_struct__is_recursive(#info_struct{is_recursive = Bool}) -> Bool.
1640
info_struct__set_is_recursive(Bool, Info) ->
1641
Info#info_struct{is_recursive = Bool}.
1643
info_struct__warn(#info_struct{warn = Warn}) ->
1646
%%---------------------------------------------------------------------------
1647
%% Loading / Savinging range trees
1648
%%---------------------------------------------------------------------------
1650
info_struct__set_new_current_tree(Label, Info) ->
1652
case info_struct__pred_tree(Label, Info) of
1658
Range_list = gb_trees:values(New_range_tree),
1659
No_not_set = lists:all(
1661
not (var_range__is_empty(Range) andalso
1662
var_range__is_not_other(Range))
1667
Counter = info_struct__counter_from_label(Info, Label),
1668
%% io:format("Counter ~p, Label ~p~n", [Counter, Label]),
1669
if Counter > ?LABELITERATIONS ->
1670
MFA = info_struct__current_mfa(Info),
1671
Label = info_struct__current_label(Info),
1672
Warn = info_struct__warn(Info),
1673
warning('taking forever', {MFA, Label}, Warn);
1677
Info#info_struct{current_range_tree = New_range_tree};
1679
?not_done_debug("set new current tree ~n", []),
1683
%% TODO: byt updatelist till updateset ??
1684
info_struct__save_spec_range_tree(Info, {Range, To_label}, Update_list) ->
1685
%% io:format("Spec_tree Update_list ~p ~n", [Update_list]),
1686
Current_label = info_struct__current_label(Info),
1687
Edge = {Current_label, To_label},
1688
Range_name = var_range__name(Range),
1689
%% io:format("Range_name, Edge: ~p, ~p ~n", [Range_name, Edge]),
1690
case lists:keysearch({Range_name, Edge}, 1, Update_list) of
1691
{value, {_, Old_range}} ->
1692
Insert_range = range_union(Range_name, [Old_range, Range]),
1693
lists:keyreplace({Range_name, Edge}, 1, Update_list, {{Range_name, Edge}, Insert_range});
1695
[{{Range_name, Edge}, Range}|Update_list]
1700
% Update_list is a list of ranges that has been updated on
1703
save_other_ranges(Info, _Update_list, [], Updated_edges) ->
1704
{Updated_edges, Info};
1705
save_other_ranges(Info, Update_list, [Label|Labels], Updated_edges_list) ->
1706
Current_range_tree = info_struct__range_tree(Info),
1707
%% io:format("Update_list ~p ~n", [Update_list]),
1710
fun({{Range_name, {_From_label, To_label}}, Range}, Tree) ->
1711
if (To_label =:= Label) ->
1712
gb_trees:enter(Range_name, Range, Tree); %%Todo union?
1719
{Updated_edges, NewInfo} = info_struct__save_range_tree({info_struct__current_label(Info), Label}, New_range_tree, Info),
1720
save_other_ranges(NewInfo, Update_list, Labels,
1721
Updated_edges_list ++ Updated_edges).
1723
info_struct__save_spec_range_trees(Info, List, Labels) ->
1724
info_struct__save_spec_range_trees(Info, List, [], Labels).
1726
info_struct__save_spec_range_trees(Info, [], Update_list, Labels) ->
1727
save_other_ranges(Info, Update_list, Labels, []);
1728
info_struct__save_spec_range_trees(Info, [{Range, Label}|List], Update_list, Labels) ->
1729
New_update_list = info_struct__save_spec_range_tree(Info, {Range, Label}, Update_list),
1730
info_struct__save_spec_range_trees(Info, List, New_update_list, Labels).
1732
info_struct__save_trees_on_edges([], Info, Updated_edges_list) -> {Updated_edges_list, Info};
1733
info_struct__save_trees_on_edges([To_label|To_label_list], Info, Updated_edges_list) ->
1734
Current_label = info_struct__current_label(Info),
1735
{Updated_edges, NewInfo} = info_struct__save_current_range_tree({Current_label, To_label}, Info),
1736
%% io:format("Updated_edges ~p ~n", [Updated_edges]),
1737
info_struct__save_trees_on_edges(To_label_list, NewInfo, Updated_edges ++ Updated_edges_list).
1739
live_ranges({out_tree, _}, Range_tree, _) -> Range_tree;
1740
live_ranges({_, return}, Range_tree, _) -> Range_tree;
1741
live_ranges({_From_label, To_label}, Range_tree, Info) ->
1742
Livelist = info_struct__live_vars(Info, To_label),
1743
Liveset = gb_sets:from_list(Livelist), %%not linear search todo performance?
1744
Range_list = gb_trees:to_list(Range_tree),
1747
fun({Name, _Range}) -> %%TODO assert:Name should be same as var_range_name
1748
gb_sets:is_element({var, Name}, Liveset)
1751
gb_trees:from_orddict(Live_range_list).
1753
info_struct__pred_tree(Label, #info_struct{pred_trees = Trees}) ->
1754
gb_trees:lookup(Label, Trees).
1756
info_struct__set_pred_tree(Label, Pred_tree, #info_struct{pred_trees = Trees} = Info) ->
1757
Info#info_struct{pred_trees = gb_trees:enter(Label, Pred_tree, Trees)}.
1759
info_struct__save_current_range_tree(Edge, Info) ->
1760
Current_range_tree = info_struct__range_tree(Info),
1761
info_struct__save_range_tree(Edge, Current_range_tree, Info).
1763
info_struct__save_range_tree(Edge, Insert_tree, Info) ->
1764
{_, To_label} = Edge,
1765
Live_tree = live_ranges(Edge, Insert_tree, Info),
1766
{Update_value, New_range_tree, New_pred_tree} =
1767
case info_struct__pred_tree(To_label, Info) of
1769
{true, Live_tree, Live_tree};
1770
{value, Old_pred_tree} ->
1771
Union_pred_tree = range_tree_union([Old_pred_tree,
1773
{range_tree_is_different(Old_pred_tree, Union_pred_tree), Insert_tree, Union_pred_tree}
1776
Final_range_trees = gb_trees:enter(Edge, New_range_tree, info_struct__range_trees(Info)),
1777
Info2 = Info#info_struct{range_trees = Final_range_trees},
1778
if Update_value =:= true ->
1779
{[Edge], info_struct__set_pred_tree(To_label, New_pred_tree, Info2)};
1790
range_tree_is_different(Range_tree1, Range_tree2) ->
1791
case gb_trees:size(Range_tree1) =:= gb_trees:size(Range_tree2) of
1793
Range_list1 = gb_trees:values(Range_tree1),
1794
Range_list2 = gb_trees:values(Range_tree2),
1795
Range_tuple_list = lists:zip(Range_list1, Range_list2),
1797
fun({Range1, Range2}) -> not var_range__is_equal(Range1, Range2) end,
1804
get_edge_tree_list(PredList, Label, Version, Info) ->
1808
if Version =:= old ->
1809
{old, {Pred, Label}};
1813
info_struct__get_range_tree(Search_pattern, Info)
1817
info_struct__merge_pred_range_trees(Label, Version, Info) ->
1818
StartLabel = info_struct__startlabel(Info),
1819
Predmap = info_struct__predmap(Info),
1820
%% io:format("PredMap: ~p, Label: ~p,", [Predmap, Label]),
1821
Pred = hipe_icode_cfg:pred(Predmap, Label),
1822
Pred_range_trees = get_edge_tree_list(Pred, Label, Version, Info),
1823
if Label =:= StartLabel ->
1824
[Params] = get_edge_tree_list([params], Label, Version, Info),
1825
New_pred_range_trees = [Params|Pred_range_trees];
1827
New_pred_range_trees = Pred_range_trees
1829
range_tree_union(New_pred_range_trees).
1831
range_tree_union([]) -> gb_trees:empty();
1832
range_tree_union([Range_tree]) ->
1834
range_tree_union([Range_tree|Range_tree_list]) ->
1835
Range_List = gb_trees:to_list(Range_tree),
1836
range_tree_range_list_union(Range_List, range_tree_union(Range_tree_list)).
1838
range_tree_range_list_union([], Tree) -> Tree;
1839
range_tree_range_list_union([{Name, Range}|Range_list], Tree) ->
1840
case gb_trees:lookup(Name, Tree) of
1842
NewTree = gb_trees:insert(Name, Range, Tree);
1844
NewRange = range_union(Name, [Range,Range2]),
1845
NewTree = gb_trees:update(Name, NewRange, Tree)
1847
range_tree_range_list_union(Range_list, NewTree).
1849
in_range_trees_from_info_struct_1(_Info, [], Label_range_tree) ->
1851
in_range_trees_from_info_struct_1(Info, [Label|Labels], Label_range_tree) ->
1852
Range_tree = info_struct__merge_pred_range_trees(Label, new, Info),
1853
%% io:format("Label ~p, ~nIn_Range_tree ~p ~n", [Label, gb_trees:values(Range_tree)]),
1854
New_label_range_tree = gb_trees:insert(Label, Range_tree, Label_range_tree),
1855
in_range_trees_from_info_struct_1(Info, Labels, New_label_range_tree).
1857
in_range_trees_from_info_struct(Info, Live_labels) ->
1858
Live_labels_list = gb_sets:to_list(Live_labels),
1859
in_range_trees_from_info_struct_1(Info, Live_labels_list, gb_trees:empty()).
1861
out_range_trees_from_info_struct_1(_Info, [], Label_range_tree) ->
1863
out_range_trees_from_info_struct_1(Info, [Label|Labels], Label_range_tree) ->
1864
Range_tree = info_struct__get_range_tree({out_tree, Label}, Info),
1865
%% io:format("Label ~p, ~nOut_range_tree ~p ~n", [Label, gb_trees:values(Range_tree)]),
1866
%% info_struct__merge_succ_range_trees(Label, Info),
1867
New_label_range_tree = gb_trees:insert(Label, Range_tree, Label_range_tree),
1868
out_range_trees_from_info_struct_1(Info, Labels, New_label_range_tree).
1870
out_range_trees_from_info_struct(Info, Live_labels) ->
1871
Live_labels_list = gb_sets:to_list(Live_labels),
1872
out_range_trees_from_info_struct_1(Info, Live_labels_list, gb_trees:empty()).
1874
%%-----------------------------------------------------------------------------
1876
%%-----------------------------------------------------------------------------
1879
{[], [], gb_sets:empty()}.
1881
get_work({[Label|Left], List, Set}) ->
1882
NewWork = {Left, List, gb_sets:delete(Label, Set)},
1884
get_work({[], [], _Set}) ->
1886
get_work({[], List, Set}) ->
1887
get_work({lists:reverse(List), [], Set}).
1889
add_work(Work = {List1, List2, Set},[Label|Left])->
1890
case gb_sets:is_member(Label, Set) of
1892
add_work(Work, Left);
1894
%% io:format("Adding work: ~w\n", [Label]),
1895
add_work({List1, [Label|List2], gb_sets:insert(Label, Set)}, Left)
1897
add_work(Work, []) ->
1900
info_struct__get_work(Info) ->
1901
Worklist = info_struct__worklist(Info),
1902
%% io:format("Worklist ~p ~n", [Worklist]),
1903
case get_work(Worklist) of
1906
{Label, New_worklist} ->
1907
NewWork = {value, Label},
1908
Info2 = Info#info_struct{current_label=Label},
1909
Work = New_worklist,
1910
Info3 = info_struct__increment_label_counter(Info2, Label),
1911
{NewWork, Info3#info_struct{worklist=Work}}
1917
input_range(Info) ->
1918
StartLabel = info_struct__startlabel(Info),
1919
Params = info_struct__get_range_tree({params, StartLabel}, Info),
1920
gb_trees:values(Params).
1922
return_range(Info) ->
1923
Return_info = info_struct__return_vars(Info),
1924
{Return_variables, Return_labels} = lists:unzip(Return_info),
1925
Trees = get_edge_tree_list(Return_labels, return, new, Info),
1926
Return_ranges = return_ranges(Return_variables, Trees, Info),
1927
range_union(return_range, Return_ranges).
1929
return_ranges([], [], _) -> []; %% lists:map ??
1930
return_ranges([Variable|VariableList], [Tree|TreeList], Info) ->
1931
Range = gb_trees:get(Variable, Tree),
1932
[Range | return_ranges(VariableList, TreeList, Info)].
1938
%% Functionallity for the range struct
1942
var_range__is_correct(#var_range{range=empty}) -> true;
1943
var_range__is_correct(#var_range{range={Min, Max}}) when (Min =/= empty),
1948
is_max(posinf) -> true;
1949
is_max(N) when is_integer(N) -> true.
1951
is_min(neginf) -> true;
1952
is_min(N) when is_integer(N) -> true.
1955
range_init_1(Name, empty) ->
1956
#var_range{var_name = Name, range=empty};
1957
range_init_1(Name, {Min, Max}) ->
1960
IsNotEmpty = inf_geq(Max, Min),
1961
if not IsNotEmpty ->
1962
#var_range{var_name=Name, range=empty};
1963
(Min =/= empty) and (Max =/= empty) ->
1964
#var_range{var_name=Name, range={Min, Max}}
1967
range_init(Name, empty, Other) ->
1968
Var_range = range_init_1(Name, empty),
1969
Var_range#var_range{other = Other};
1970
range_init(Name, {Min, Max} = Range, Other) when (Min =/= empty),
1972
Var_range = range_init_1(Name, Range),
1973
Var_range#var_range{other = Other}.
1975
var_range__other(#var_range{other = Other}) -> Other.
1976
var_range__name(#var_range{var_name=Name}) -> Name.
1978
var_range__is_empty(#var_range{range=empty}) -> true;
1979
var_range__is_empty(#var_range{range={Min, Max}})
1980
when (Min =/= empty), (Max =/= empty) -> false. %% force tuple
1982
var_range__is_not_other(#var_range{other=Bool}) -> not Bool.
1984
var_range__range(#var_range{range=Range}) -> Range.
1986
var_range__set_other(Range, Other) ->
1987
Range#var_range{other = Other}.
1989
var_range__max(#var_range{range=empty}) -> empty;
1990
var_range__max(#var_range{range={_, Max}}) when Max =/= empty -> Max.
1992
var_range__min(#var_range{range=empty}) -> empty;
1993
var_range__min(#var_range{range={Min, _}}) when Min =/= empty -> Min.
1995
var_range__is_equal(#var_range{range=empty, other=Bool},
1996
#var_range{range=empty, other=Bool}) -> true;
1997
var_range__is_equal(#var_range{range={Min, Max}, other=Bool},
1998
#var_range{range={Min, Max}, other=Bool}) -> true;
1999
var_range__is_equal(#var_range{}, #var_range{}) -> false.
2001
var_range__copy(Range, Name) ->
2002
Range#var_range{var_name = Name}.
2004
var_range__is_constant(#var_range{range={Min,Max}})
2005
when (Min =/= empty), (Max =/= empty) -> Min =:= Max;
2006
var_range__is_constant(#var_range{range=empty}) -> false.
2008
to_string(#var_range{range = empty, other=false}) ->
2010
to_string(#var_range{range = empty, other=_Other}) ->
2011
"[empty]"; %, other: " ++ atom_to_list(Other);
2013
Min = var_range__min(Range),
2014
Max = var_range__max(Range),
2016
P_Min = atom_to_list(Min);
2018
P_Min = integer_to_list(Min)
2021
P_Max = atom_to_list(Max);
2023
P_Max = integer_to_list(Max)
2025
"[" ++ P_Min ++ ", " ++ P_Max ++ "]".
2026
%% "[" ++ P_Min ++ ", " ++ P_Max ++ "], other: " ++ atom_to_list(Other).
2028
var_range__is_fixnum(Range) ->
2029
Min = var_range__min(Range),
2030
Max = var_range__max(Range),
2031
if is_integer(Min), is_integer(Max) ->
2032
hipe_tagscheme:is_fixnum(Min) andalso hipe_tagscheme:is_fixnum(Max);
2037
%%---------------------------------------------------------------------------
2039
%%---------------------------------------------------------------------------
2043
range_add(Name, Range1, Range2) ->
2044
NewMin = inf_add(var_range__min(Range1), var_range__min(Range2)),
2045
NewMax = inf_add(var_range__max(Range1), var_range__max(Range2)),
2046
Other = var_range__other(Range1) orelse var_range__other(Range2),
2047
range_init(Name, {NewMin, NewMax}, Other).
2050
range_sub(Name, Range1, Range2) ->
2051
Min_sub = inf_min([inf_inv(var_range__max(Range2)), inf_inv(var_range__min(Range2))]),
2052
Max_sub = inf_max([inf_inv(var_range__max(Range2)), inf_inv(var_range__min(Range2))]),
2053
NewMin = inf_add(var_range__min(Range1), Min_sub),
2054
NewMax = inf_add(var_range__max(Range1), Max_sub),
2055
Other = var_range__other(Range1) orelse var_range__other(Range2),
2056
range_init(Name, {NewMin, NewMax}, Other).
2059
range_mult(Name, #var_range{range = empty, other = true}, _Range2) ->
2060
range_init(Name, empty, true);
2061
range_mult(Name, _Range1, #var_range{range = empty, other = true}) ->
2062
range_init(Name, empty, true);
2063
range_mult(Name, Range1, Range2) ->
2064
Min1 = var_range__min(Range1),
2065
Min2 = var_range__min(Range2),
2066
Max1 = var_range__max(Range1),
2067
Max2 = var_range__max(Range2),
2068
GreaterMin1 = inf_greater_zero(Min1),
2069
GreaterMin2 = inf_greater_zero(Min2),
2070
GreaterMax1 = inf_greater_zero(Max1),
2071
GreaterMax2 = inf_greater_zero(Max2),
2073
if GreaterMin1 -> % Kolumn 3
2074
if GreaterMin2 -> % <3,3>
2075
{inf_mult(Min1, Min2), inf_mult(Max1, Max2)};
2076
GreaterMax2 -> % <3,2>
2077
{inf_mult(Min2, Max1), inf_mult(Max2, Max1)};
2079
{inf_mult(Min2, Max1), inf_mult(Max2, Min1)}
2082
GreaterMin2 -> % Kolumn 1 eller 2 rad 3
2083
var_range__range(range_mult(Name, Range2, Range1));
2084
GreaterMax1 -> %Kolumn 2 Rad 1 eller 2
2085
if GreaterMax2 -> % Kolumn 2 Rad 2
2086
NewMin = inf_min([inf_mult(Min2, Max1), inf_mult(Max2, Min1)]),
2087
NewMax = inf_max([inf_mult(Min2, Min1), inf_mult(Max2, Max1)]),
2089
true -> % Kolumn 2 Rad 1
2090
{inf_mult(Min2, Max1), inf_mult(Min2, Min1)}
2092
GreaterMax2 -> % Kolumn 1 Rad 2
2093
var_range__range(range_mult(Name, Range2, Range1));
2094
true -> % Kolumn 1 Rad 1
2095
inf_mult(Min2, Max1)
2097
Other = var_range__other(Range1) orelse var_range__other(Range2),
2098
range_init(Name, Range, Other).
2101
extreme_divisors(#var_range{range={0,0}}) -> {0,0};
2102
extreme_divisors(#var_range{range={0,Max}}) -> {1,Max};
2103
extreme_divisors(#var_range{range={Min,0}}) -> {Min,-1};
2104
extreme_divisors(#var_range{range={Min,Max}}) ->
2105
case inf_geq(Min, 0) of
2108
case inf_geq(0, Max) of
2109
true -> {Min,Max}; %Max < 0
2110
false -> {-1,1} %Max > 0
2114
%% this is div, not /.
2115
range_div(Name, _, #var_range{range={0,0}}) ->
2116
range_init(Name, empty, false);
2117
range_div(Name, #var_range{range=empty}, _) ->
2118
range_init(Name, empty, false);
2119
range_div(Name, Range1, Den) ->
2120
Min1 = var_range__min(Range1),
2121
Max1 = var_range__max(Range1),
2122
{Min2, Max2} = extreme_divisors(Den),
2123
Min_max_list = [inf_div(Min1, Min2), inf_div(Min1, Max2), inf_div(Max1, Min2), inf_div(Max1, Max2)],
2124
range_init(Name, {inf_min(Min_max_list), inf_max(Min_max_list)}, false).
2126
range_rem(Name, Range1, Range2) ->
2127
%% Range1 desides the sign of the answer.
2128
Min1 = var_range__min(Range1),
2129
Max1 = var_range__max(Range1),
2130
Min2 = var_range__min(Range2),
2131
Max2 = var_range__max(Range2),
2132
Min1_geq_zero = inf_geq(Min1, 0),
2133
Max1_leq_zero = inf_geq(0, Max1),
2134
Max_range2 = inf_max([inf_abs(Min2), inf_abs(Max2)]),
2135
Max_range2_leq_zero = inf_geq(0, Max_range2),
2139
Max_range2_leq_zero ->
2147
Max_range2_leq_zero -> %% Max_range2 =:= 0 ??
2148
inf_inv(Max_range2);
2152
range_init(Name, {New_min, New_max}, false).
2156
range_bsr(Name, Range1, Range2=#var_range{range={Min, Max}}) -> %% todo do not match on {Min, Max}, or??
2157
New_Range2 = range_init(var_range__name(Range2), {inf_inv(Max), inf_inv(Min)}, var_range__other(Range2)),
2158
range_bsl(Name, Range1, New_Range2).
2160
range_bsl(Name, Range1, Range2) ->
2161
Min1 = var_range__min(Range1),
2162
Min2 = var_range__min(Range2),
2163
Max1 = var_range__max(Range1),
2164
Max2 = var_range__max(Range2),
2165
%%TODO inte >= 0 !!!
2166
%% io:format("Min1 ~p, Max1 ~p, Min2 ~p, Max2 ~p~n", [Min1, Max1, Min2, Max2]),
2167
%% Not_fixed_return_range =
2170
{inf_bsl(Min1, Min2), inf_bsl(Max1, Max2)};
2173
{inf_bsl(Min1, Max2), inf_bsl(Max1, Min2)};
2175
{inf_bsl(Min1, Max2), inf_bsl(Max1, Max2)}
2180
range_init(Name, {Min, Max}, false).
2182
range_bnot(Name, Range) ->
2183
Minus_one = range_init(const, {-1,-1}, false),
2184
range_add(Name, range_mult(Name, Range, Minus_one), Minus_one).
2186
width({Min, Max}) -> inf_max([width(Min), width(Max)]);
2187
width(posinf) -> posinf;
2188
width(neginf) -> posinf;
2189
width(X) when X >= 0 ->
2191
width(X) when X < 0 ->
2195
case X < (1 bsl N) of
2203
case X > (-1 bsl N) of
2210
range_band(Name, R1, R2) ->
2211
{Min1, Max1} = var_range__range(R1),
2212
{Min2, Max2} = var_range__range(R2),
2213
Width = inf_min([width({Min1, Max1}), width({Min2, Max2})]),
2214
true = inf_geq(Width, 0),
2216
case inf_geq(0, Min1) and inf_geq(0, Min2) of
2223
case inf_geq(0, Max1) and inf_geq(0, Max2) of
2231
range_init(Name, {Min, Max}, false).
2233
range_bor(Name, R1, R2) ->
2234
{Min1, Max1} = var_range__range(R1),
2235
{Min2, Max2} = var_range__range(R2),
2236
Width = width({width({Min1, Max1}), width({Min2, Max2})}),
2238
case inf_geq(Max1, 0) and inf_geq(Max2, 0) of
2245
case inf_geq(Max1, 0) or inf_geq(Max2, 0) of
2253
range_init(Name, {Min, Max}, false).
2255
range_bxor(Name, R1, R2) ->
2256
{Min1, Max1} = var_range__range(R1),
2257
{Min2, Max2} = var_range__range(R2),
2258
Width = width({width({Min1, Max1}), width({Min2, Max2})}),
2260
case inf_geq(Max1, 0) and inf_geq(Max2, 0) of
2267
case inf_geq(Max1, 0) or inf_geq(Max2, 0) of
2275
range_init(Name, {Min, Max}, false).
2279
range_remove_constant(Range1, #var_range{range=empty}) ->
2281
range_remove_constant(Range1, #var_range{range={Const, Const}}) when is_integer(Const) ->
2282
Old_min = var_range__min(Range1),
2283
Old_max = var_range__max(Range1),
2284
if Old_min =:= Const ->
2285
New_min = Old_min + 1;
2289
if Old_max =:= Const ->
2290
New_max = Old_max - 1;
2295
if (New_min =:= empty) or (New_max =:= empty) ->
2301
range_init(var_range__name(Range1), Range_range, var_range__other(Range1)).
2304
%% range_diff(Name, Range1, #var_range{range = empty}) ->
2305
%% var_range__copy(Range1, Name);
2306
%% range_diff(Name, Range1, Range2) ->
2307
%% Min1 = var_range__min(Range1),
2308
%% Max1 = var_range__max(Range1),
2309
%% Min2 = var_range__min(Range2),
2310
%% Max2 = var_range__max(Range2),
2311
%% %io:format("Min1 ~p, Max1 ~p, Min2 ~p, Max2 ~p ~n", [Min1, Max1, Min2, Max2]),
2312
%% if (Min1 =:= empty) ->
2313
%% Int_range = empty;
2315
%% case inf_geq(Min1, Min2) of
2317
%% Min = inf_max([Min1, inf_add(Max2,1)]);
2321
%% case inf_geq(Max2, Max1) of
2323
%% Max = inf_min([Max1, inf_add(Min2,-1)]);
2327
%% Int_range = {Min, Max}
2329
%% Other = var_range__other(Range1),
2331
%% Min_fixed = var_range__min_fixed(Range1) and var_range__min_fixed(Range2),
2332
%% Max_fixed = var_range__max_fixed(Range1) and var_range__max_fixed(Range2),
2333
%% R = range_init(Name, Int_range, {Min_fixed, Max_fixed}, Other),
2334
%% io:format("range diff ~p ~p ~n", [R, Int_range]),
2337
%% todo ska det f��rsta fallet finnas?
2338
%% range_cut(Name, []) -> #var_range{var_name=Name};
2339
range_cut(Name, [#var_range{range=empty, other=false}|_]) ->
2340
range_init(Name, empty, false);
2341
range_cut(Name, [Range|Rangelist]) ->
2342
range_cut(Name, Rangelist, Range).
2344
range_cut(Name, [], Dst_range) ->
2345
var_range__copy(Dst_range, Name);
2346
range_cut(Name, [#var_range{range = empty, other = Other1}|_],
2347
#var_range{other = Other2}) ->
2348
range_init(Name, empty, Other1 and Other2);
2349
range_cut(Name, [Range|Rangelist], Dst_range) ->
2350
Min1 = var_range__min(Range),
2351
Max1 = var_range__max(Range),
2352
Min2 = var_range__min(Dst_range),
2353
Max2 = var_range__max(Dst_range),
2354
if (Min1 =:= empty) orelse (Min2 =:= empty) ->
2357
Min = inf_max([Min1, Min2]),
2358
Max = inf_min([Max1, Max2]),
2359
Int_range = {Min, Max}
2361
Other = var_range__other(Range) andalso var_range__other(Dst_range),
2362
range_cut(Name, Rangelist, range_init(Name, Int_range, Other)).
2364
range_union(Name, []) ->
2365
range_init(Name, empty, false); %#var_range{var_name=Name};
2366
range_union(Name, [Range|Range_list]) ->
2367
%% io:format("range: ~p ~n rangelist: ~p ~n", [Range, Range_list]),
2368
range_union(Name, Range_list, Range).
2370
range_union(Name, [], Dst_range) ->
2371
%% io:format("dstRange: ~p ~n", [DstRange]),
2372
var_range__copy(Dst_range, Name);
2373
range_union(Name, [Range|Rangelist], Dst_range) ->
2374
%% io:format("Range: ~p, DstRange ~p ->", [Range, DstRange]),
2375
Min1 = var_range__min(Range),
2376
Max1 = var_range__max(Range),
2377
Min2 = var_range__min(Dst_range),
2378
Max2 = var_range__max(Dst_range),
2379
Min = inf_min([Min1, Min2]),
2380
Max = inf_max([Max1, Max2]),
2382
if (Min =:= empty) or (Max =:= empty) ->
2387
Other = var_range__other(Range) orelse var_range__other(Dst_range),
2388
%% io:format("{~p, ~p} ~n", [Min, Max]),
2389
range_union(Name, Rangelist,
2390
range_init(Name, Int_range, Other)).
2392
range_equality_propagation(Range_1, Range_2) ->
2393
True_range_1 = range_cut(var_range__name(Range_1), [Range_1, Range_2]),
2394
True_range_2 = range_cut(var_range__name(Range_2), [Range_1, Range_2]),
2396
case var_range__range(Range_1) of
2399
range_remove_constant(Range_2, Range_1);
2407
case var_range__range(Range_2) of
2410
range_remove_constant(Range_1, Range_2);
2417
{True_range_1, True_range_2, False_range_1, False_range_2}.
2420
range_inequality_propagation(Range1, Range2) ->
2421
%% io:format("Range1 ~p, Range2 ~p ~n", [Range1, Range2]),
2422
R1_name = var_range__name(Range1),
2423
R2_name = var_range__name(Range2),
2424
R1_min = var_range__min(Range1),
2425
R2_min = var_range__min(Range2),
2426
R1_max = var_range__max(Range1),
2427
R2_max = var_range__max(Range2),
2428
R1_other = var_range__other(Range1),
2429
R2_other = var_range__other(Range2),
2431
R1_is_empty = var_range__is_empty(Range1),
2432
R2_is_empty = var_range__is_empty(Range2),
2434
{R1_true_range, R1_false_range} =
2438
Range1_range = var_range__range(Range1),
2439
{Range1_range, Range1_range};
2441
R1_true_max = inf_min([R1_max, inf_add(R2_max, -1)]),
2442
R1_false_min = inf_max([R1_min, R2_min]),
2443
{{R1_min, R1_true_max}, {R1_false_min, R1_max}}
2446
{R2_true_range, R2_false_range} =
2450
Range2_range = var_range__range(Range2),
2451
{Range2_range, Range2_range};
2453
R2_true_min = inf_max([inf_add(R1_min,1),R2_min]),
2454
R2_false_max = inf_min([R1_max, R2_max]),
2455
{{R2_true_min, R2_max}, {R2_min, R2_false_max}}
2458
R1_true = range_init(R1_name, R1_true_range, R1_other),
2459
R2_true = range_init(R2_name, R2_true_range, R2_other),
2460
R1_false = range_init(R1_name, R1_false_range, R1_other),
2461
R2_false = range_init(R2_name, R2_false_range, R2_other),
2462
%% io:format("R1T ~p, R1F ~p ~n, R2T ~p, R2F ~p ~n", [R1_true_range, R1_false_range, R2_true_range, R2_false_range]),
2464
{R1_true, R2_true, R1_false, R2_false}.
2469
get_larger_value(Value, List) ->
2470
get_larger_value_1(Value, lists:reverse(List)).
2472
get_larger_value_1(Value, []) -> Value;
2473
get_larger_value_1(Value, [Head|Tail]) ->
2474
case inf_geq(Head, Value) of
2478
get_larger_value_1(Value, Tail)
2481
get_smaller_value(Value, List) ->
2482
get_smaller_value_1(Value, List).
2484
get_smaller_value_1(Value, []) -> Value;
2485
get_smaller_value_1(Value, [Head|Tail]) ->
2486
case inf_geq(Head, Value) and (Head =/= Value) of
2488
get_smaller_value_1(Value, Tail);
2493
range_widening(Old_range, New_range, Wideningvalues) ->
2494
New_min_fixed = inf_geq(var_range__min(New_range), var_range__min(Old_range)),
2495
New_max_fixed = inf_geq(var_range__max(Old_range), var_range__max(New_range)),
2497
Old_empty = var_range__is_empty(Old_range),
2500
if New_min_fixed or Old_empty ->
2501
var_range__min(New_range);
2503
Min = var_range__min(New_range),
2504
get_smaller_value(Min, Wideningvalues)
2507
if New_max_fixed or Old_empty ->
2508
var_range__max(New_range);
2510
Max = var_range__max(New_range),
2511
get_larger_value(Max, Wideningvalues)
2514
if (New_min =:= empty) or (New_max =:= empty) ->
2519
New_other = var_range__other(New_range),
2520
R = range_init(var_range__name(New_range), Range_range, New_other),
2521
% io:format("Range widening ~p~n", [R]),
2524
%%---------------------------------------------------------------------------
2526
%%---------------------------------------------------------------------------
2528
inf_max([]) -> empty;
2535
Geq = inf_geq(Elem, Max),
2536
if not Geq or (Elem =:= empty) ->
2546
inf_min([]) -> empty;
2551
lists:foldl(fun(Elem, Min) ->
2552
Geq = inf_geq(Elem, Min),
2553
if Geq or (Elem =:= empty) ->
2563
inf_abs(posinf) -> posinf;
2564
inf_abs(neginf) -> posinf;
2565
inf_abs(Number) when is_integer(Number), (Number < 0) -> - Number;
2566
inf_abs(Number) when is_integer(Number) -> Number.
2568
inf_add(posinf, _Number) -> posinf;
2569
inf_add(neginf, _Number) -> neginf;
2570
inf_add(_Number, posinf) -> posinf;
2571
inf_add(_Number, neginf) -> neginf;
2572
inf_add(Number1, Number2) when is_integer(Number1), is_integer(Number2) ->
2575
inf_inv(posinf) -> neginf;
2576
inf_inv(neginf) -> posinf;
2577
inf_inv(Number) -> -Number.
2579
inf_geq(posinf, _) -> true;
2580
inf_geq(_, posinf) -> false;
2581
inf_geq(_, neginf) -> true;
2582
inf_geq(neginf, _) -> false;
2583
inf_geq(A, B) -> A >= B.
2585
inf_greater_zero(posinf) -> true;
2586
inf_greater_zero(neginf) -> false;
2587
inf_greater_zero(Number) when Number >= 0 -> true;
2588
inf_greater_zero(Number) when Number < 0 -> false.
2590
inf_div(Number, 0) ->
2591
Greater = inf_greater_zero(Number),
2597
inf_div(posinf, Number) ->
2598
Greater = inf_greater_zero(Number),
2604
inf_div(neginf, Number) ->
2605
Greater = inf_greater_zero(Number),
2611
inf_div(Number, posinf) ->
2612
Greater = inf_greater_zero(Number),
2618
inf_div(Number, neginf) ->
2619
Greater = inf_greater_zero(Number),
2625
inf_div(Number1, Number2) -> Number1 div Number2.
2627
inf_mult(neginf, Number) ->
2628
Greater = inf_greater_zero(Number),
2629
if Greater -> neginf;
2632
inf_mult(posinf, Number) ->
2633
Greater = inf_greater_zero(Number),
2634
if Greater -> posinf;
2637
inf_mult(Number, posinf) -> inf_mult(posinf, Number);
2638
inf_mult(Number, neginf) -> inf_mult(neginf, Number);
2639
inf_mult(Number1, Number2) -> Number1 * Number2.
2641
inf_bsl(posinf, _) -> posinf;
2642
inf_bsl(neginf, _) -> neginf;
2643
inf_bsl(Number, posinf) when Number >= 0 -> posinf;
2644
inf_bsl(_, posinf) -> neginf;
2645
inf_bsl(Number, neginf) when Number >= 0 -> 0;
2646
inf_bsl(_Number, neginf) -> -1;
2647
inf_bsl(Number1, Number2) ->
2649
if Number2 > (Bits bsl 1) -> % (Bits * 2)
2650
inf_bsl(Number1, posinf);
2651
Number2 < (-Bits bsl 1) -> % (-Bits * 2)
2652
inf_bsl(Number1, neginf);
2657
%%---------------------------------------------------------------------------
2659
%%---------------------------------------------------------------------------
2661
range_info_from_info_struct(Info) ->
2662
Live_labels = info_struct__live_labels(Info),
2663
%% io:format("in_label_range_trees = ~p ~n", [in_range_trees_from_info_struct(Info, Live_labels)]),
2664
%% io:format("out_label_range_trees = ~p ~n", [out_range_trees_from_info_struct(Info, Live_labels)]),
2665
#range_info{live_labels = Live_labels,
2666
in_label_range_trees = in_range_trees_from_info_struct(Info, Live_labels),
2667
out_label_range_trees = out_range_trees_from_info_struct(Info, Live_labels),
2668
return_points = info_struct__return_vars(Info),
2669
warn = info_struct__warn(Info)
2672
range_info__def_range(#range_info{out_label_range_trees = Label_tree}, Label, Variable) ->
2673
%% io:format("Def: Label ~p, Var ~p ~n", [Label, Variable]),
2674
Range_tree = gb_trees:get(Label, Label_tree),
2675
case gb_trees:lookup(Variable, Range_tree) of
2677
%% io:format("use_range ~p ~n", [Range]),
2680
range_init(Variable, empty, false)
2683
range_info__use_range(Range_info = #range_info{in_label_range_trees = Label_tree}, Label, Variable) ->
2684
%% io:format("Use: Label ~p, Var ~p ~n", [Label, Variable]),
2685
Range_tree = gb_trees:get(Label, Label_tree),
2686
case gb_trees:lookup(Variable, Range_tree) of
2688
%% io:format("use_range ~p ~n", [Range]),
2691
range_info__def_range(Range_info, Label, Variable)
2694
range_info__is_live(#range_info{live_labels = Labels}, Label) ->
2695
gb_sets:is_member(Label, Labels).
2697
range_info__warn(#range_info{warn = Warn}) ->
2700
%%---------------------------------------------------------------------------
2701
%% Print out messages
2702
%%---------------------------------------------------------------------------
2704
warning(Op, Spec, true) ->
2705
Text = "Icode range analysis not good (~w, ~w)\n",
2708
warning(_, _, false) ->
2711
info(New, Old, true) ->
2712
Text = "Icode range analysis found info (~w, ~w)\n",
2715
info(_, _, false) ->
2718
%%---------------------------------------------------------------------------
2719
%% Print out messages
2720
%%---------------------------------------------------------------------------
2725
% vim: set tabstop=2 ft=erlang
added
removed
lib/hipe/icode/hipe_icode_range_an.erl
