← Back to branch summary

~ubuntu-branches/ubuntu/trusty/erlang/trusty

« back to all changes in this revision

Viewing changes to lib/hipe/icode/hipe_icode_range.erl

  • Committer: Bazaar Package Importer
  • Author(s): Clint Byrum
  • Date: 2011-05-05 15:48:43 UTC
  • mfrom: (3.5.13 sid)
  • Revision ID: james.westby@ubuntu.com-20110505154843-0om6ekzg6m7ugj27
Tags: 1:14.b.2-dfsg-3ubuntu1
* Merge from debian unstable.  Remaining changes:
  - Drop libwxgtk2.8-dev build dependency. Wx isn't in main, and not
    supposed to.
  - Drop erlang-wx binary.
  - Drop erlang-wx dependency from -megaco, -common-test, and -reltool, they
    do not really need wx. Also drop it from -debugger; the GUI needs wx,
    but it apparently has CLI bits as well, and is also needed by -megaco,
    so let's keep the package for now.
  - debian/patches/series: Do what I meant, and enable build-options.patch
    instead.
* Additional changes:
  - Drop erlang-wx from -et
* Dropped Changes:
  - patches/pcre-crash.patch: CVE-2008-2371: outer level option with
    alternatives caused crash. (Applied Upstream)
  - fix for ssl certificate verification in newSSL: 
    ssl_cacertfile_fix.patch (Applied Upstream)
  - debian/patches/series: Enable native.patch again, to get stripped beam
    files and reduce the package size again. (build-options is what
    actually accomplished this)
  - Remove build-options.patch on advice from upstream and because it caused
    odd build failures.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/hipe/icode/hipe_icode_range.erl
1
1
%% -*- erlang-indent-level: 2 -*-
2
2
%%
3
3
%% %CopyrightBegin%
4
 
%% 
5
 
%% Copyright Ericsson AB 2007-2009. All Rights Reserved.
6
 
%% 
 
4
%%
 
5
%% Copyright Ericsson AB 2007-2011. All Rights Reserved.
 
6
%%
7
7
%% The contents of this file are subject to the Erlang Public License,
8
8
%% Version 1.1, (the "License"); you may not use this file except in
9
9
%% compliance with the License. You should have received a copy of the
10
10
%% Erlang Public License along with this software. If not, it can be
11
11
%% retrieved online at http://www.erlang.org/.
12
 
%% 
 
12
%%
13
13
%% Software distributed under the License is distributed on an "AS IS"
14
14
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
15
15
%% the License for the specific language governing rights and limitations
16
16
%% under the License.
17
 
%% 
 
17
%%
18
18
%% %CopyrightEnd%
19
19
%%
20
20
%%%-------------------------------------------------------------------
59
59
 
60
60
-record(range, {range :: range_rep(),
61
61
                other :: boolean()}).
 
62
-type range() :: #range{}.
62
63
 
63
 
-record(ann,   {range :: #range{},
 
64
-record(ann,   {range :: range(),
64
65
                type  :: erl_types:erl_type(),
65
66
                count :: integer()}).
 
67
-type ann() :: #ann{}.
66
68
 
67
 
-type range_anno() :: {range_anno, #ann{}, fun((#ann{}) -> string())}.
68
 
-type args_fun() :: fun((mfa(),cfg()) -> [#range{}]).
69
 
-type call_fun() :: fun((mfa(),[#range{}]) -> #range{}).                      
70
 
-type final_fun() :: fun((mfa(),[#range{}]) -> ok).
 
69
-type range_anno() :: {'range_anno', ann(), fun((ann()) -> string())}.
 
70
-type args_fun() :: fun((mfa(), cfg()) -> [range()]).
 
71
-type call_fun() :: fun((mfa(), [range()]) -> range()).
 
72
-type final_fun() :: fun((mfa(), [range()]) -> 'ok').
71
73
-type data() :: {mfa(), args_fun(), call_fun(), final_fun()}.
72
74
-type label() :: non_neg_integer().
73
75
-type info() :: gb_tree().
75
77
-type variable() :: #icode_variable{}.
76
78
-type annotated_variable() :: #icode_variable{}.
77
79
-type argument() :: #icode_const{} | variable().
78
 
-type three_range_fun()   :: fun((#range{},#range{},#range{}) -> #range{}).
 
80
-type three_range_fun()   :: fun((range(),range(),range()) -> range()).
79
81
-type instr_split_info()  :: {icode_instr(), [{label(),info()}]}.
80
 
-type last_instr_return() :: {instr_split_info(), #range{}}.
 
82
-type last_instr_return() :: {instr_split_info(), range()}.
81
83
 
82
84
-record(state, {info_map = gb_trees:empty()     :: info(), 
83
85
                counter  = dict:new()           :: dict(), 
84
86
                cfg                             :: cfg(), 
85
87
                liveness = gb_trees:empty()     :: gb_tree(), 
86
 
                ret_type                        :: #range{}, 
 
88
                ret_type                        :: range(),
87
89
                lookup_fun                      :: call_fun(),
88
90
                result_action                   :: final_fun()}).
89
91
 
108
110
-spec concurrent_cfg(cfg(), mfa(), pid()) -> cfg().
109
111
 
110
112
concurrent_cfg(Cfg, MFA, CompServer) ->
111
 
  CompServer ! {ready, {MFA,self()}},
112
 
  {ArgsFun,CallFun,FinalFun} = do_analysis(Cfg, MFA),
 
113
  CompServer ! {ready, {MFA, self()}},
 
114
  {ArgsFun, CallFun, FinalFun} = do_analysis(Cfg, MFA),
113
115
  Ans = do_rewrite(Cfg, MFA, ArgsFun, CallFun, FinalFun),
114
116
  CompServer ! {done_rewrite, MFA},
115
117
  Ans.
227
229
  state__update_info(State2, InfoList, Rewrite).
228
230
 
229
231
-spec analyse_BB([icode_instr()], info(), [icode_instr()], boolean(), call_fun()) ->
230
 
         {[icode_instr()], [{label(),info()}], #range{}}.
 
232
         {[icode_instr()], [{label(),info()}], range()}.
231
233
 
232
234
analyse_BB([Last], Info, Code, Rewrite, LookupFun) ->
233
235
  {{NewI, LabelInfoList}, RetType} =
266
268
  %% io:format("Uses: ~p~nRanges: ~p~n", [Uses, PresentRanges]),
267
269
  JoinFun = fun(Var, Range) -> update_info(Var, Range, WidenFun) end,
268
270
  NewUses = lists:zipwith(JoinFun, Uses, PresentRanges),
269
 
  hipe_icode:subst_uses(lists:zip(Uses, NewUses),I).
 
271
  hipe_icode:subst_uses(lists:zip(Uses, NewUses), I).
270
272
 
271
 
-spec join_info(#ann{}, #range{}, three_range_fun()) -> #ann{}.
 
273
-spec join_info(ann(), range(), three_range_fun()) -> ann().
272
274
 
273
275
join_info(Ann = #ann{range = R1, type = Type, count = ?WIDEN}, R2, Fun) ->
274
276
  Ann#ann{range = Fun(R1, R2, range_from_simple_type(Type))};
278
280
    NewR -> Ann#ann{range = NewR, count = C+1}
279
281
  end.
280
282
 
281
 
-spec join_three(#range{}, #range{}, #range{}) -> #range{}.
 
283
-spec join_three(range(), range(), range()) -> range().
282
284
 
283
285
join_three(R1, R2, R3) ->
284
286
  inf(sup(R1, R2), R3).
285
287
 
286
 
-spec update_info(variable(), #range{}) -> annotated_variable().
 
288
-spec update_info(variable(), range()) -> annotated_variable().
287
289
 
288
290
update_info(Var, Range) ->
289
291
  update_info(Var, Range, fun update_three/3).
290
292
 
291
 
-spec update_info(variable(), #range{}, three_range_fun()) -> annotated_variable().
 
293
-spec update_info(variable(), range(), three_range_fun()) -> annotated_variable().
292
294
 
293
295
update_info(Arg, R, Fun) ->
294
296
  case hipe_icode:is_annotated_variable(Arg) of
299
301
      Arg
300
302
  end.
301
303
 
302
 
-spec update_info1(any(), #range{}, three_range_fun()) -> range_anno().
 
304
-spec update_info1(any(), range(), three_range_fun()) -> range_anno().
303
305
 
304
306
update_info1({range_anno, Ann, _}, R2, Fun) ->
305
307
  make_range_anno(update_ann(Ann,R2,Fun));
314
316
    NewR -> Ann#ann{range = NewR, count = C+1}
315
317
  end.
316
318
 
317
 
-spec type_to_ann(erl_types:erl_type()) -> #ann{}.
 
319
-spec type_to_ann(erl_types:erl_type()) -> ann().
318
320
 
319
321
type_to_ann(Type) ->
320
 
  #ann{range = range_from_simple_type(Type), type = t_limit(Type,1), count=1}.
 
322
  #ann{range = range_from_simple_type(Type), type = t_limit(Type,1), count = 1}.
321
323
 
322
 
-spec make_range_anno(#ann{}) -> range_anno().
 
324
-spec make_range_anno(ann()) -> range_anno().
323
325
 
324
326
make_range_anno(Ann) ->
325
327
  {range_anno, Ann, fun pp_ann/1}. 
326
328
 
327
 
-spec update_three(#range{}, #range{}, #range{}) -> #range{}.
 
329
-spec update_three(range(), range(), range()) -> range().
328
330
 
329
331
update_three(_R1, R2, R3) ->
330
332
  inf(R2, R3).
331
333
 
332
 
-spec safe_widen(#range{}, #range{}, #range{}) -> #range{}.
 
334
-spec safe_widen(range(), range(), range()) -> range().
333
335
 
334
336
safe_widen(#range{range=Old}, #range{range=New}, T = #range{range=Wide}) ->
335
337
  ResRange =
336
 
    case {Old,New,Wide} of
337
 
      {{Min,Max1},{Min,Max2},{_,Max}} ->
338
 
        case inf_geq(OMax = next_up_limit(inf_max([Max1,Max2])),Max) of
 
338
    case {Old, New, Wide} of
 
339
      {{Min,Max1}, {Min,Max2}, {_,Max}} ->
 
340
        case inf_geq(OMax = next_up_limit(inf_max([Max1, Max2])), Max) of
339
341
          true -> {Min,Max};
340
342
          false -> {Min,OMax}
341
343
        end;
342
 
      {{Min1,Max},{Min2,Max},{Min,_}} ->
343
 
        case inf_geq(Min, OMin = next_down_limit(inf_min([Min1,Min2]))) of
 
344
      {{Min1,Max}, {Min2,Max}, {Min,_}} ->
 
345
        case inf_geq(Min, OMin = next_down_limit(inf_min([Min1, Min2]))) of
344
346
          true -> {Min,Max};
345
347
          false -> {OMin,Max}
346
348
        end;
347
 
      {{Min1,Max1},{Min2,Max2},{Min,Max}} -> 
 
349
      {{Min1,Max1}, {Min2,Max2}, {Min,Max}} ->
348
350
        RealMax =
349
 
          case inf_geq(OMax = next_up_limit(inf_max([Max1,Max2])),Max) of
 
351
          case inf_geq(OMax = next_up_limit(inf_max([Max1, Max2])), Max) of
350
352
            true -> Max;
351
353
            false -> OMax
352
354
          end,
353
355
        RealMin = 
354
 
          case inf_geq(Min, OMin = next_down_limit(inf_min([Min1,Min2]))) of
 
356
          case inf_geq(Min, OMin = next_down_limit(inf_min([Min1, Min2]))) of
355
357
            true -> Min;
356
358
            false -> OMin
357
359
          end,
358
 
        {RealMin,RealMax};
 
360
        {RealMin, RealMax};
359
361
      _ ->
360
362
        Wide
361
363
    end,
362
 
  T#range{range=ResRange}.
 
364
  T#range{range = ResRange}.
363
365
 
364
 
-spec widen(#range{}, #range{}, #range{}) -> #range{}.
 
366
-spec widen(range(), range(), range()) -> range().
365
367
 
366
368
widen(#range{range=Old}, #range{range=New}, T = #range{range=Wide}) ->
367
369
  ResRange =
368
 
    case {Old,New,Wide} of
369
 
      {{Min,_},{Min,Max2},{_,Max}} ->
370
 
        case inf_geq(OMax = next_up_limit(Max2),Max) of
 
370
    case {Old, New, Wide} of
 
371
      {{Min,_}, {Min,Max2}, {_,Max}} ->
 
372
        case inf_geq(OMax = next_up_limit(Max2), Max) of
371
373
          true -> {Min,Max};
372
374
          false -> {Min,OMax}
373
375
        end;
374
 
      {{_,Max},{Min2,Max},{Min,_}} ->
 
376
      {{_,Max}, {Min2,Max}, {Min,_}} ->
375
377
        case inf_geq(Min, OMin = next_down_limit(Min2)) of
376
378
          true -> {Min,Max};
377
379
          false -> {OMin,Max}
378
380
        end;
379
 
      {_,{Min2,Max2},{Min,Max}} -> 
 
381
      {_, {Min2,Max2}, {Min,Max}} ->
380
382
        RealMax =
381
 
          case inf_geq(OMax = next_up_limit(Max2),Max) of
 
383
          case inf_geq(OMax = next_up_limit(Max2), Max) of
382
384
            true -> Max;
383
385
            false -> OMax
384
386
          end,
387
389
            true -> Min;
388
390
            false -> OMin
389
391
          end,
390
 
        {RealMin,RealMax};
 
392
        {RealMin, RealMax};
391
393
      _ ->
392
394
        Wide
393
395
    end,
394
 
  T#range{range=ResRange}.
 
396
  T#range{range = ResRange}.
395
397
 
396
398
-spec analyse_call(#icode_call{}, call_fun()) -> #icode_call{}.
397
399
 
421
423
 
422
424
analyse_begin_handler(Handler) ->
423
425
  SubstList =
424
 
    [{Dst,update_info(Dst,any_type())} || 
 
426
    [{Dst, update_info(Dst, any_type())} ||
425
427
      Dst <- hipe_icode:begin_handler_dstlist(Handler)],
426
428
  hipe_icode:subst_defines(SubstList, Handler).
427
429
 
494
496
      end
495
497
  end.
496
498
 
497
 
-spec update_infos(argument(), info(), [{#range{},label()}]) -> [{label(),info()}].
 
499
-spec update_infos(argument(), info(), [{range(),label()}]) -> [{label(),info()}].
498
500
 
499
501
update_infos(Arg, Info, [{Range, Label}|Rest]) ->
500
 
  [{Label,enter_define({Arg,Range},Info)} | update_infos(Arg,Info,Rest)];
 
502
  [{Label,enter_define({Arg,Range},Info)} | update_infos(Arg, Info, Rest)];
501
503
update_infos(_, _, []) -> [].
502
504
 
503
 
-spec get_range_label_list([{argument(),label()}], #range{}, [{#range{},label()}]) ->
504
 
         {#range{},[{#range{},label()}]}.
 
505
-spec get_range_label_list([{argument(),label()}], range(), [{range(),label()}]) ->
 
506
         {range(),[{range(),label()}]}.
505
507
 
506
508
get_range_label_list([{Val,Label}|Cases], SRange, Acc) ->
507
509
  VRange = get_range_from_arg(Val),
516
518
  {PointTypes, _} = lists:unzip(Acc),
517
519
  {remove_point_types(SRange, PointTypes), Acc}.
518
520
 
519
 
-spec update_switch(#icode_switch_val{}, [{#range{},label()}], boolean()) ->
 
521
-spec update_switch(#icode_switch_val{}, [{range(),label()}], boolean()) ->
520
522
         #icode_switch_val{}.
521
523
 
522
524
update_switch(Switch, LabelRangeList, KeepFail) ->
524
526
    case label_range_list_to_cases(LabelRangeList, []) of
525
527
      no_update ->
526
528
        Switch;
527
 
      Cases -> 
 
529
      Cases ->
528
530
        hipe_icode:switch_val_cases_update(Switch, Cases)
529
531
    end,
530
532
  if KeepFail -> S2;
531
533
     true -> S2
532
534
  end.
533
535
 
534
 
-spec label_range_list_to_cases([{#range{},label()}], [{#icode_const{},label()}]) ->
 
536
-spec label_range_list_to_cases([{range(),label()}], [{#icode_const{},label()}]) ->
535
537
         'no_update' | [{#icode_const{},label()}].
536
538
 
537
539
label_range_list_to_cases([{#range{range={C,C},other=false},Label}|Rest],
586
588
  NewInfo = enter_vals(NewI, Info),
587
589
  case hipe_icode:call_fail_label(Call) of
588
590
    [] -> 
589
 
      {NewI, [{Continuation,NewInfo}]};
 
591
      {NewI, [{Continuation, NewInfo}]};
590
592
    Fail ->
591
 
      {NewI, [{Continuation,NewInfo}, {Fail,Info}]}
 
593
      {NewI, [{Continuation, NewInfo}, {Fail, Info}]}
592
594
  end.
593
595
 
594
596
-spec analyse_if(#icode_if{}, info(), boolean()) ->
596
598
 
597
599
analyse_if(If, Info, Rewrite) ->
598
600
  case hipe_icode:if_args(If) of
599
 
    Args = [_,_] ->
 
601
    [_, _] = Args ->
600
602
      analyse_sane_if(If, Info, Args, get_range_from_args(Args), Rewrite);
601
603
    _ ->
602
604
      TrueLabel = hipe_icode:if_true_label(If),
603
605
      FalseLabel = hipe_icode:if_false_label(If),
604
 
      {If, [{TrueLabel,Info},{FalseLabel,Info}]}
 
606
      {If, [{TrueLabel, Info}, {FalseLabel, Info}]}
605
607
  end.
606
608
 
607
609
-spec analyse_sane_if(#icode_if{}, info(), [argument(),...],
608
 
                      [#range{},...], boolean()) ->
 
610
                      [range(),...], boolean()) ->
609
611
         {#icode_goto{} | #icode_if{}, [{label(), info()}]}.
610
612
 
611
613
analyse_sane_if(If, Info, [Arg1, Arg2], [Range1, Range2], Rewrite) ->
613
615
    '>' ->
614
616
      {TrueRange2, TrueRange1, FalseRange2, FalseRange1} = 
615
617
        range_inequality_propagation(Range2, Range1);
616
 
    '==' -> 
617
 
      {TempTrueRange1, TempTrueRange2, FalseRange1, FalseRange2}=
618
 
        range_equality_propagation(Range1, Range2),
619
 
      TrueRange1 = set_other(TempTrueRange1,other(Range1)),
620
 
      TrueRange2 = set_other(TempTrueRange2,other(Range2));
621
618
    '<' ->
622
 
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2} = 
 
619
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2} =
623
620
        range_inequality_propagation(Range1, Range2);
624
621
    '>=' ->
625
622
      {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
626
623
        range_inequality_propagation(Range1, Range2);
627
624
    '=<' ->
628
 
      {FalseRange2, FalseRange1, TrueRange2, TrueRange1} = 
 
625
      {FalseRange2, FalseRange1, TrueRange2, TrueRange1} =
629
626
        range_inequality_propagation(Range2, Range1);
630
627
    '=:=' ->
631
 
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2}=
 
628
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2} =
632
629
        range_equality_propagation(Range1, Range2);
633
630
    '=/=' ->
634
631
      {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
635
632
        range_equality_propagation(Range1, Range2);
 
633
    '==' ->
 
634
      {TempTrueRange1, TempTrueRange2, FalseRange1, FalseRange2} =
 
635
        range_equality_propagation(Range1, Range2),
 
636
      TrueRange1 = set_other(TempTrueRange1, other(Range1)),
 
637
      TrueRange2 = set_other(TempTrueRange2, other(Range2));
636
638
    '/=' -> 
637
 
      {TempFalseRange1, TempFalseRange2, TrueRange1, TrueRange2}=
 
639
      {TempFalseRange1, TempFalseRange2, TrueRange1, TrueRange2} =
638
640
        range_equality_propagation(Range1, Range2),
639
 
      FalseRange1 = set_other(TempFalseRange1,other(Range1)),
640
 
      FalseRange2 = set_other(TempFalseRange2,other(Range2))
 
641
      FalseRange1 = set_other(TempFalseRange1, other(Range1)),
 
642
      FalseRange2 = set_other(TempFalseRange2, other(Range2))
641
643
  end,
642
 
  TrueLabel = hipe_icode:if_true_label(If),
643
 
  FalseLabel = hipe_icode:if_false_label(If),
644
 
  TrueInfo = 
645
 
    enter_defines([{Arg1,TrueRange1}, {Arg2,TrueRange2}],Info),
646
 
  FalseInfo = 
647
 
    enter_defines([{Arg1,FalseRange1}, {Arg2,FalseRange2}],Info),
648
 
  True = 
649
 
    case lists:any(fun range__is_none/1,[TrueRange1,TrueRange2]) of
650
 
      true -> [];
651
 
      false -> [{TrueLabel,TrueInfo}]
652
 
    end,
653
 
  False = 
654
 
    case lists:any(fun range__is_none/1, [FalseRange1,FalseRange2]) of
655
 
      true -> [];
656
 
      false -> [{FalseLabel,FalseInfo}]
657
 
    end,
658
 
  UpdateInfo = True++False,
 
644
  %% io:format("TR1 = ~w\nTR2 = ~w\n", [TrueRange1, TrueRange2]),
 
645
  True =
 
646
    case lists:all(fun range__is_none/1, [TrueRange1, TrueRange2]) of
 
647
      true -> [];
 
648
      false ->
 
649
        TrueLabel = hipe_icode:if_true_label(If),
 
650
        TrueArgRanges = [{Arg1, TrueRange1}, {Arg2, TrueRange2}],
 
651
        TrueInfo = enter_defines(TrueArgRanges, Info),
 
652
        [{TrueLabel, TrueInfo}]
 
653
    end,
 
654
  %% io:format("FR1 = ~w\nFR2 = ~w\n", [FalseRange1, FalseRange2]),
 
655
  False =
 
656
    case lists:all(fun range__is_none/1, [FalseRange1, FalseRange2]) of
 
657
      true -> [];
 
658
      false ->
 
659
        FalseLabel = hipe_icode:if_false_label(If),
 
660
        FalseArgRanges = [{Arg1, FalseRange1}, {Arg2, FalseRange2}],
 
661
        FalseInfo = enter_defines(FalseArgRanges, Info),
 
662
        [{FalseLabel, FalseInfo}]
 
663
    end,
 
664
  UpdateInfo = True ++ False,
659
665
  NewIF =
660
666
    if Rewrite ->
661
 
        %%io:format("~w~n~w~n", [{Arg1,FalseRange1},{Arg2,FalseRange2}]),
662
 
        %%io:format("Any none: ~w~n", [lists:any(fun range__is_none/1,[FalseRange1,FalseRange2])]),
663
667
        case UpdateInfo of
664
 
          [] -> %%This is weird
 
668
          [] -> %% This is weird
665
669
            If;
666
 
          [{Label,_Info}] ->
 
670
          [{Label, _Info}] ->
667
671
            hipe_icode:mk_goto(Label);
668
 
          [_,_] ->
 
672
          [_, _] ->
669
673
            If
670
674
        end;
671
675
       true ->
686
690
    Name -> Name
687
691
  end.
688
692
 
689
 
-spec range_equality_propagation(#range{}, #range{}) ->
690
 
          {#range{}, #range{}, #range{}, #range{}}.
 
693
-spec range_equality_propagation(range(), range()) ->
 
694
          {range(), range(), range(), range()}.
691
695
 
692
696
range_equality_propagation(Range_1, Range_2) ->  
693
697
  True_range = inf(Range_1, Range_2),
694
698
  case {range(Range_1), range(Range_2)} of
695
 
    {{N,N},{ N,N}} ->
 
699
    {{N,N}, {N,N}} ->
696
700
      False_range_1 = none_range(),
697
701
      False_range_2 = none_range();
698
702
    {{N1,N1}, {N2,N2}} ->
710
714
  end,
711
715
  {True_range, True_range, False_range_1, False_range_2}.
712
716
 
713
 
-spec range_inequality_propagation(#range{}, #range{}) ->
714
 
          {#range{}, #range{}, #range{}, #range{}}.
 
717
-spec range_inequality_propagation(range(), range()) ->
 
718
          {range(), range(), range(), range()}.
715
719
 
716
720
%% Range1 < Range2
717
721
range_inequality_propagation(Range1, Range2) ->
781
785
      TrueRange = inf(any_range(), OldVarRange),
782
786
      FalseRange = inf(none_range(), OldVarRange);
783
787
    _ ->
784
 
      TrueRange = inf(none_range(),OldVarRange),
 
788
      TrueRange = inf(none_range(), OldVarRange),
785
789
      FalseRange = OldVarRange
786
790
  end,
787
791
  TrueLabel = hipe_icode:type_true_label(Type),
788
792
  FalseLabel = hipe_icode:type_false_label(Type),
789
 
  TrueInfo = 
790
 
    enter_define({Arg,TrueRange},Info),
791
 
  FalseInfo = 
792
 
    enter_define({Arg,FalseRange},Info),
793
 
  True = 
 
793
  TrueInfo = enter_define({Arg, TrueRange}, Info),
 
794
  FalseInfo = enter_define({Arg, FalseRange}, Info),
 
795
  True =
794
796
    case range__is_none(TrueRange) of
795
797
      true -> [];
796
 
      false -> [{TrueLabel,TrueInfo}]
 
798
      false -> [{TrueLabel, TrueInfo}]
797
799
    end,
798
 
  False = 
 
800
  False =
799
801
    case range__is_none(FalseRange) of
800
802
      true -> [];
801
 
      false -> [{FalseLabel,FalseInfo}]
 
803
      false -> [{FalseLabel, FalseInfo}]
802
804
    end,
803
 
  UpdateInfo = True++False,
 
805
  UpdateInfo = True ++ False,
804
806
  NewType =
805
807
    if Rewrite ->
806
808
        case UpdateInfo of
808
810
            Type;
809
811
          [{Label,_Info}] ->
810
812
            hipe_icode:mk_goto(Label);
811
 
          [_,_] ->
 
813
          [_, _] ->
812
814
            Type
813
815
        end;
814
816
       true ->
815
817
        Type
816
818
    end,
817
 
  {NewType,True ++ False}.
 
819
  {NewType, True ++ False}.
818
820
 
819
 
-spec compare_with_integer(integer(), #range{}) -> {#range{}, #range{}}.
 
821
-spec compare_with_integer(integer(), range()) -> {range(), range()}.
820
822
 
821
823
compare_with_integer(N, OldVarRange) ->
822
824
  TestRange = range_init({N, N}, false),
843
845
 
844
846
%%== Ranges ==================================================================
845
847
 
846
 
-spec pp_ann(#ann{} | erl_types:erl_type()) -> [string()].
 
848
-spec pp_ann(ann() | erl_types:erl_type()) -> string().
847
849
 
848
 
pp_ann(#ann{range=#range{range=R, other=false}}) ->
 
850
pp_ann(#ann{range = #range{range = R, other = false}}) ->
849
851
  pp_range(R);
850
 
pp_ann(#ann{range=#range{range=empty, other=true}, type=Type}) ->
 
852
pp_ann(#ann{range = #range{range = empty, other = true}, type = Type}) ->
851
853
  t_to_string(Type);
852
 
pp_ann(#ann{range=#range{range=R, other=true}, type=Type}) ->
 
854
pp_ann(#ann{range = #range{range = R, other = true}, type = Type}) ->
853
855
  pp_range(R) ++ " | " ++ t_to_string(Type);
854
856
pp_ann(Type) ->
855
857
  t_to_string(Type).
867
869
val_to_string(neg_inf) -> "-inf";
868
870
val_to_string(X) when is_integer(X) -> integer_to_list(X).
869
871
 
870
 
-spec range_from_type(erl_types:erl_type()) -> [#range{}].
 
872
-spec range_from_type(erl_types:erl_type()) -> [range()].
871
873
 
872
874
range_from_type(Type) ->
873
875
  [range_from_simple_type(T) || T <- t_to_tlist(Type)].
874
876
  
875
 
-spec range_from_simple_type(erl_types:erl_type()) -> #range{}.
 
877
-spec range_from_simple_type(erl_types:erl_type()) -> range().
876
878
 
877
879
range_from_simple_type(Type) ->
878
880
  None = t_none(),
887
889
      #range{range = Range, other = true}
888
890
  end.
889
891
 
890
 
-spec range_init(range_rep(), boolean()) -> #range{}.
 
892
-spec range_init(range_rep(), boolean()) -> range().
891
893
 
892
894
range_init({Min, Max} = Range, Other) ->
893
895
  case inf_geq(Max, Min) of
899
901
range_init(empty, Other) ->
900
902
  #range{range = empty, other = Other}.
901
903
 
902
 
-spec range(#range{}) -> range_rep().
 
904
-spec range(range()) -> range_rep().
903
905
 
904
906
range(#range{range = R}) -> R.
905
907
 
906
 
-spec other(#range{}) -> boolean().
 
908
-spec other(range()) -> boolean().
907
909
 
908
910
other(#range{other = O}) -> O.
909
911
 
910
 
-spec set_other(#range{}, boolean()) -> #range{}.
 
912
-spec set_other(range(), boolean()) -> range().
911
913
 
912
914
set_other(R, O) -> R#range{other = O}.
913
915
 
914
 
-spec range__min(#range{}) -> 'empty' | 'neg_inf' | integer().
915
 
 
916
 
range__min(#range{range=empty}) -> empty;
917
 
range__min(#range{range={Min,_}}) -> Min.
918
 
 
919
 
-spec range__max(#range{}) -> 'empty' | 'pos_inf' | integer().
920
 
 
921
 
range__max(#range{range=empty}) -> empty;
922
 
range__max(#range{range={_,Max}}) -> Max.
923
 
 
924
 
-spec range__is_none(#range{}) -> boolean().
925
 
 
926
 
range__is_none(#range{range=empty, other=false}) -> true;
 
916
-spec range__min(range()) -> 'empty' | 'neg_inf' | integer().
 
917
 
 
918
range__min(#range{range = empty}) -> empty;
 
919
range__min(#range{range = {Min,_}}) -> Min.
 
920
 
 
921
-spec range__max(range()) -> 'empty' | 'pos_inf' | integer().
 
922
 
 
923
range__max(#range{range = empty}) -> empty;
 
924
range__max(#range{range = {_,Max}}) -> Max.
 
925
 
 
926
-spec range__is_none(range()) -> boolean().
 
927
 
 
928
range__is_none(#range{range = empty, other = false}) -> true;
927
929
range__is_none(#range{}) -> false.
928
930
 
929
 
-spec range__is_empty(#range{}) -> boolean().
930
 
 
931
 
range__is_empty(#range{range=empty}) -> true;
932
 
range__is_empty(#range{range={_,_}}) -> false.
933
 
 
934
 
-spec remove_point_types(#range{}, [#range{}]) -> #range{}.
 
931
-spec range__is_empty(range()) -> boolean().
 
932
 
 
933
range__is_empty(#range{range = empty}) -> true;
 
934
range__is_empty(#range{range = {_,_}}) -> false.
 
935
 
 
936
-spec remove_point_types(range(), [range()]) -> range().
935
937
 
936
938
remove_point_types(Range, Ranges) ->
937
939
  Sorted = lists:sort(Ranges),
939
941
  Range1 = lists:foldl(FoldFun, Range, Sorted),
940
942
  lists:foldl(FoldFun, Range1, lists:reverse(Sorted)).
941
943
 
942
 
-spec range__remove_constant(#range{}, #range{}) -> #range{}.
 
944
-spec range__remove_constant(range(), range()) -> range().
943
945
 
944
 
range__remove_constant(R = #range{range={C,C}}, #range{range={C,C}}) ->
945
 
  R#range{range=empty};
946
 
range__remove_constant(R = #range{range={C,H}}, #range{range={C,C}}) ->
947
 
  R#range{range={C+1,H}};
948
 
range__remove_constant(R = #range{range={L,C}}, #range{range={C,C}}) ->
949
 
  R#range{range={L,C-1}};
950
 
range__remove_constant(R = #range{}, #range{range={C,C}}) ->
 
946
range__remove_constant(#range{range = {C, C}} = R, #range{range = {C, C}}) ->
 
947
  R#range{range = empty};
 
948
range__remove_constant(#range{range = {C, H}} = R, #range{range = {C, C}}) ->
 
949
  R#range{range = {C+1, H}};
 
950
range__remove_constant(#range{range = {L, C}} = R, #range{range = {C, C}}) ->
 
951
  R#range{range = {L, C-1}};
 
952
range__remove_constant(#range{} = R, #range{range = {C,C}}) ->
951
953
  R;
952
 
range__remove_constant(R = #range{}, _) ->
 
954
range__remove_constant(#range{} = R, _) ->
953
955
  R.
954
956
 
955
 
-spec any_type() -> #range{}.
 
957
-spec any_type() -> range().
956
958
 
957
959
any_type() ->
958
 
  #range{range=any_r(), other=true}.
 
960
  #range{range = any_r(), other = true}.
959
961
 
960
 
-spec any_range() -> #range{}.
 
962
-spec any_range() -> range().
961
963
 
962
964
any_range() ->
963
 
  #range{range=any_r(), other=false}.
 
965
  #range{range = any_r(), other = false}.
964
966
 
965
 
-spec none_range() -> #range{}.
 
967
-spec none_range() -> range().
966
968
 
967
969
none_range() ->
968
 
  #range{range=empty, other=true}.
 
970
  #range{range = empty, other = true}.
969
971
 
970
 
-spec none_type() -> #range{}.
 
972
-spec none_type() -> range().
971
973
 
972
974
none_type() ->
973
975
  #range{range = empty, other = false}.
976
978
 
977
979
any_r() -> {neg_inf, pos_inf}.
978
980
 
979
 
-spec get_range_from_args([argument()]) -> [#range{}].
 
981
-spec get_range_from_args([argument()]) -> [range()].
980
982
  
981
983
get_range_from_args(Args) ->
982
984
  [get_range_from_arg(Arg) || Arg <- Args].
983
985
 
984
 
-spec get_range_from_arg(argument()) -> #range{}.
 
986
-spec get_range_from_arg(argument()) -> range().
985
987
 
986
988
get_range_from_arg(Arg) ->
987
989
  case hipe_icode:is_const(Arg) of
989
991
      Value = hipe_icode:const_value(Arg),
990
992
      case is_integer(Value) of
991
993
        true ->
992
 
          #range{range={Value,Value}, other=false};
 
994
          #range{range = {Value, Value}, other = false};
993
995
        false ->
994
 
          #range{range=empty, other=true}
 
996
          #range{range = empty, other = true}
995
997
      end;
996
998
    false ->
997
999
      case hipe_icode:is_annotated_variable(Arg) of
998
1000
        true ->
999
1001
          case hipe_icode:variable_annotation(Arg) of
1000
 
            {range_anno, #ann{range=Range}, _} ->
 
1002
            {range_anno, #ann{range = Range}, _} ->
1001
1003
              Range;
1002
1004
            {type_anno, Type, _} ->
1003
1005
              range_from_simple_type(Type)
1012
1014
%% inf([R1,R2|Rest]) ->
1013
1015
%%   inf([inf(R1,R2)|Rest]).
1014
1016
 
1015
 
-spec inf(#range{}, #range{}) -> #range{}.
 
1017
-spec inf(range(), range()) -> range().
1016
1018
 
1017
1019
inf(#range{range=R1, other=O1}, #range{range=R2, other=O2}) -> 
1018
1020
  #range{range=range_inf(R1,R2), other=other_inf(O1,O2)}.
1022
1024
range_inf(empty, _) -> empty;
1023
1025
range_inf(_, empty) -> empty;
1024
1026
range_inf({Min1,Max1}, {Min2,Max2}) ->
1025
 
  NewMin = inf_max([Min1,Min2]),
1026
 
  NewMax = inf_min([Max1,Max2]),
 
1027
  NewMin = inf_max([Min1, Min2]),
 
1028
  NewMax = inf_min([Max1, Max2]),
1027
1029
  case inf_geq(NewMax, NewMin) of
1028
1030
    true ->
1029
1031
      {NewMin, NewMax};
1035
1037
 
1036
1038
other_inf(O1, O2) -> O1 and O2.
1037
1039
 
1038
 
-spec sup([#range{},...]) -> #range{}.
 
1040
-spec sup([range(),...]) -> range().
1039
1041
 
1040
1042
sup([R]) ->
1041
1043
  R;
1042
1044
sup([R1,R2|Rest]) ->
1043
1045
  sup([sup(R1, R2)|Rest]).
1044
1046
 
1045
 
-spec sup(#range{}, #range{}) -> #range{}.
 
1047
-spec sup(range(), range()) -> range().
1046
1048
 
1047
1049
sup(#range{range=R1,other=O1}, #range{range=R2,other=O2}) -> 
1048
1050
  #range{range=range_sup(R1,R2), other=other_sup(O1,O2)}.
1063
1065
%%== Call Support =============================================================
1064
1066
 
1065
1067
-spec analyse_call_or_enter_fun(fun_name(), [argument()],
1066
 
                                icode_call_type(), call_fun()) -> [#range{}].
 
1068
                                icode_call_type(), call_fun()) -> [range()].
1067
1069
 
1068
1070
analyse_call_or_enter_fun(Fun, Args, CallType, LookupFun) ->
1069
1071
  %%io:format("Fun: ~p~n Args: ~p~n CT: ~p~n LF: ~p~n", [Fun, Args, CallType, LookupFun]),
1105
1107
      [any_type()];
1106
1108
    {hipe_bs_primop, {bs_get_integer, Size, Flags}} ->
1107
1109
      {Min, Max} = analyse_bs_get_integer(Size, Flags, length(Args) =:= 1),
1108
 
      [#range{range={Min, Max}, other=false}, any_type()];
 
1110
      [#range{range = {Min, Max}, other = false}, any_type()];
1109
1111
    {hipe_bs_primop, _} = Primop ->
1110
1112
      Type = hipe_icode_primops:type(Primop),
1111
1113
      range_from_type(Type)
1112
1114
  end.
1113
1115
 
1114
 
-type bin_operation() :: fun((#range{},#range{}) -> #range{}).
1115
 
-type unary_operation() :: fun((#range{}) -> #range{}).
 
1116
-type bin_operation() :: fun((range(), range()) -> range()).
 
1117
-type unary_operation() :: fun((range()) -> range()).
1116
1118
 
1117
1119
-spec basic_type(fun_name()) -> 'not_int' | 'not_analysed'
1118
 
                             | {bin, bin_operation()}
1119
 
                             | {unary, unary_operation()}
1120
 
                             | {fcall, mfa()} | {hipe_bs_primop, _}.
 
1120
                             | {'bin', bin_operation()}
 
1121
                             | {'unary', unary_operation()}
 
1122
                             | {'fcall', mfa()} | {'hipe_bs_primop', _}.
1121
1123
 
1122
1124
%% Arithmetic operations
1123
1125
basic_type('+') -> {bin, fun(R1, R2) -> range_add(R1, R2) end};
1214
1216
 
1215
1217
%% Arithmetic
1216
1218
 
1217
 
-spec range_add(#range{}, #range{}) -> #range{}.
 
1219
-spec range_add(range(), range()) -> range().
1218
1220
 
1219
1221
range_add(Range1, Range2) ->
1220
1222
  NewMin = inf_add(range__min(Range1), range__min(Range2)),
1222
1224
  Other = other(Range1) orelse other(Range2),
1223
1225
  range_init({NewMin, NewMax}, Other).
1224
1226
 
1225
 
-spec range_sub(#range{}, #range{}) -> #range{}.
 
1227
-spec range_sub(range(), range()) -> range().
1226
1228
 
1227
1229
range_sub(Range1, Range2) ->
1228
1230
  Min_sub = inf_min([inf_inv(range__max(Range2)), 
1234
1236
  Other = other(Range1) orelse other(Range2),
1235
1237
  range_init({NewMin, NewMax}, Other).
1236
1238
 
1237
 
-spec range_mult(#range{}, #range{}) -> #range{}.
 
1239
-spec range_mult(range(), range()) -> range().
1238
1240
 
1239
1241
range_mult(#range{range=empty, other=true}, _Range2) ->
1240
1242
  range_init(empty, true);
1274
1276
  Other = other(Range1) orelse other(Range2),
1275
1277
  range_init(Range, Other).
1276
1278
 
1277
 
-spec extreme_divisors(#range{}) -> range_tuple().
 
1279
-spec extreme_divisors(range()) -> range_tuple().
1278
1280
 
1279
1281
extreme_divisors(#range{range={0,0}}) -> {0,0};
1280
1282
extreme_divisors(#range{range={0,Max}}) -> {1,Max};
1289
1291
      end
1290
1292
  end.
1291
1293
 
1292
 
-spec range_div(#range{}, #range{}) -> #range{}.
 
1294
-spec range_div(range(), range()) -> range().
1293
1295
 
1294
1296
%% this is div, not /.
1295
1297
range_div(_, #range{range={0,0}}) ->
1306
1308
                  inf_div(Max1, Min2), inf_div(Max1, Max2)],
1307
1309
  range_init({inf_min(Min_max_list), inf_max(Min_max_list)}, false).
1308
1310
 
1309
 
-spec range_rem(#range{}, #range{}) -> #range{}.
 
1311
-spec range_rem(range(), range()) -> range().
1310
1312
 
1311
1313
range_rem(Range1, Range2) ->
1312
1314
  %% Range1 desides the sign of the answer.
1332
1334
 
1333
1335
%%--- Bit operations ----------------------------
1334
1336
 
1335
 
-spec range_bsr(#range{}, #range{}) -> #range{}.
 
1337
-spec range_bsr(range(), range()) -> range().
1336
1338
 
1337
1339
range_bsr(Range1, Range2=#range{range={Min, Max}}) -> 
1338
1340
  New_Range2 = range_init({inf_inv(Max), inf_inv(Min)}, other(Range2)), 
1340
1342
  %% io:format("bsr res:~w~nInput:= ~w~n", [Ans, {Range1,Range2}]),
1341
1343
  Ans.
1342
1344
 
1343
 
-spec range_bsl(#range{}, #range{}) -> #range{}.
 
1345
-spec range_bsl(range(), range()) -> range().
1344
1346
 
1345
1347
range_bsl(Range1, Range2) ->
1346
1348
  Min1 = range__min(Range1),
1359
1361
    end,
1360
1362
  range_init(MinMax, false).
1361
1363
 
1362
 
-spec range_bnot(#range{}) -> #range{}.
 
1364
-spec range_bnot(range()) -> range().
1363
1365
 
1364
1366
range_bnot(Range) ->
1365
1367
  Minus_one = range_init({-1,-1}, false),
1366
1368
  range_add(range_mult(Range, Minus_one), Minus_one).
1367
1369
 
1368
 
-spec width(range_rep() | integer()) -> 'pos_inf' | non_neg_integer().
 
1370
-spec width(range_rep() | inf_integer()) -> 'pos_inf' | non_neg_integer().
1369
1371
 
1370
1372
width({Min, Max}) -> inf_max([width(Min), width(Max)]);
1371
1373
width(pos_inf) -> pos_inf;
1389
1391
    false -> negwidth(X, N+1)
1390
1392
  end.
1391
1393
 
1392
 
-spec range_band(#range{}, #range{}) -> #range{}.
 
1394
-spec range_band(range(), range()) -> range().
1393
1395
 
1394
1396
range_band(R1, R2) ->
1395
1397
  {_Min1, Max1} = MM1 = range(R1),
1423
1425
    end,
1424
1426
  range_init(Range, false).  
1425
1427
 
1426
 
-spec range_bor(#range{}, #range{}) -> #range{}.
 
1428
-spec range_bor(range(), range()) -> range().
1427
1429
 
1428
1430
range_bor(R1, R2) ->
1429
1431
  {Min1, _Max1} = MM1 = range(R1),
1457
1459
    end,
1458
1460
  range_init(Range, false).  
1459
1461
 
1460
 
-spec classify_range(#range{}) -> 'minus_minus' | 'minus_plus' | 'plus_plus'.
 
1462
-spec classify_range(range()) -> 'minus_minus' | 'minus_plus' | 'plus_plus'.
1461
1463
 
1462
1464
classify_range(Range) ->
1463
1465
  case range(Range) of
1480
1482
classify_int_range(_Number1, _Number2) ->
1481
1483
  minus_plus.
1482
1484
      
1483
 
-spec range_bxor(#range{}, #range{}) -> #range{}.
 
1485
-spec range_bxor(range(), range()) -> range().
1484
1486
 
1485
1487
range_bxor(R1, R2) ->
1486
1488
  {Min1, Max1} = MM1 = range(R1),
1895
1897
%% Icode Coordinator Callbacks
1896
1898
%%=====================================================================
1897
1899
 
1898
 
-spec replace_nones([#range{}]) -> [#range{}].
 
1900
-spec replace_nones([range()]) -> [range()].
1899
1901
replace_nones(Args) ->
1900
1902
  [replace_none(Arg) || Arg <- Args].
1901
1903
 
1905
1907
    false -> Arg
1906
1908
  end.
1907
1909
 
1908
 
-spec update__info([#range{}], [#range{}]) -> {boolean(), [#ann{}]}.
 
1910
-spec update__info([range()], [range()]) -> {boolean(), [ann()]}.
1909
1911
update__info(NewRanges, OldRanges) ->
1910
1912
  SupFun = fun (Ann, Range) -> 
1911
1913
               join_info(Ann, Range, fun safe_widen/3)
1915
1917
  Change = lists:zipwith(EqFun, ResRanges, OldRanges),
1916
1918
  {lists:all(fun (X) -> X end, Change), ResRanges}.
1917
1919
 
1918
 
-spec new__info/1 :: ([#range{}]) -> [#ann{}].
 
1920
-spec new__info([range()]) -> [ann()].
1919
1921
new__info(NewRanges) ->
1920
1922
  [#ann{range=Range,count=1,type=t_any()} || Range <- NewRanges].
1921
1923
 
1922
 
-spec return__info/1 :: ([#ann{}]) -> [#range{}].
 
1924
-spec return__info([ann()]) -> [range()].
1923
1925
return__info(Ranges) ->
1924
1926
  [Range || #ann{range=Range} <- Ranges].
1925
1927
 
1926
 
-spec return_none/0 :: () -> [#range{},...].
 
1928
-spec return_none() -> [range(),...].
1927
1929
return_none() ->
1928
1930
  [none_type()].
1929
1931
 
1930
 
-spec return_none_args/2 :: (#cfg{}, mfa()) -> [#range{}].
 
1932
-spec return_none_args(cfg(), mfa()) -> [range()].
1931
1933
return_none_args(Cfg, {_M,_F,A}) ->
1932
1934
  NoArgs =
1933
1935
    case hipe_icode_cfg:is_closure(Cfg) of
1936
1938
    end,
1937
1939
  lists:duplicate(NoArgs, none_type()).
1938
1940
 
1939
 
-spec return_any_args/2 :: (#cfg{}, mfa()) -> [#range{}].
 
1941
-spec return_any_args(cfg(), mfa()) -> [range()].
1940
1942
return_any_args(Cfg, {_M,_F,A}) ->
1941
1943
  NoArgs = 
1942
1944
    case hipe_icode_cfg:is_closure(Cfg) of