aboutsummaryrefslogblamecommitdiffstats
path: root/lib/hipe/icode/hipe_icode_range.erl
blob: 46c5a39f2c96fa4d57f533dbbe0999bb0a155e44 (plain) (tree)
1
2
3
4
5
6
7
8
9
10
11
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901


                                 


                                                        




                                                                      
  



                                                                         
  











































                                                                       
                          
 
                                 

                                              
                      
 



                                                                      






                                                             
                                                                       
                                                                 
                                                           




                                                              
                                                           























                                                                       

                                                       




















































































































                                                                                    
                                                        





































                                                                                 
                                                     
 
                                                            








                                                                                      
                                                       



                         
                                                               



                                              
                                                                                  









                                                                   
                                                                      













                                                                           
                                                 

                    
                                                                                
 
                                             



                                   
                                                         



                            
                                                       


                                                                           


                                                                         


                             

                                                                           


                             
                                              
                 
                                                                           



                         
                                                                             


                         
                           


            
                            
 
                                                  


                                                                      


                                                        


                             
                                       



                                                          
                                    
                 
                                                          







                                                            
                           


            
                            




























                                                                               
                                           







































































                                                                                       
                                                                                  

                                                 
                                                                           

                             

                                                                                   













                                                                 
                                                                           






                                                         
              





                                                         
                                                                                   





















































                                                                                     
                                        
           
                                                     






                                                           
                    



                                                                          
                                                   


                                                            
                                                  






                                                                     
          
                                                          




                                                          
                                                          

                                                     
                                                          



                                                          




                                                                  
            
                                                                  
                                                   

                                                              
      

                                                                 
                                                                     
                 




                                                                 
        

                                                                   
                                                                       
                 




                                                                    
        
                             

                 
                          
                                
               
                             
                                      
                   



















                                       

                                                     



                                                 
                     
















                                                           

                                                       



































































                                                                   

                                           
        
                                                 



                                                 


                                                    

                                     
                                      
        
         

                                      
                                        
        
                             






                                      
                   




                
                           
 
                                                                     

























                                                                              
                                                       
 
                                                         
              
                                                                         
                    
                                                                     
















                                                                   
                                                         



                                                       
                                                              













                                                         
                                                    










                                           
                                    


                              
                                  


                              
                                               


                                      
                                                             
 

                                           
 
                                                             
 

                                           
 
                                           
 
                                                             

                                  
                                            
 

                                                
 
                                                        






                                                              
                                                          
 






                                                                             
    
                                          

    
                            

             
                                        
 
                             

              
                                         
 
                              

               
                                      
 
                             







                                       
                                                     



                                           
                                                






                                          
                                                        
                
                                             




                                                     
                                                   













                                          
                                       








                                                               

                                 










                                                   
                                    





                          
                                       



















                                                                               
                                                                            








































                                                                                          
                                                              




                                             

                                                            

                                                          


                                                                        































































































                                                                               
                                             






                                                           
                                             










                                                   
                                              






































                                                                           
                                                 













                                                    
                                             















                                                                    
                                             
























                                                       
                                             






                                                                        
                                             

















                                                                   
                                     




                                                     
                                                                          






















                                                                          
                                              
































                                                    
                                             
































                                                                
                                                                            





















                                                                         
                                              





























































































































































































































































































































































































































                                                                              
                                            








                                     
                                                                 








                                                          
                                      


                                                                 
                                         


                                         
                                     


                
                                                  







                                                    
                                                 


























                                                                                      
%% -*- erlang-indent-level: 2 -*-
%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2007-2011. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
%%
%%%-------------------------------------------------------------------
%%% File    : hipe_icode_range.erl
%%% Author  : Per Gustafsson <[email protected]>
%%% Description : 
%%%
%%% Created : 12 Mar 2007 by Per Gustafsson <[email protected]>
%%%-------------------------------------------------------------------
-module(hipe_icode_range).

-export([cfg/4]).

%%=====================================================================
%% Icode Coordinator Behaviour Callbacks
%%=====================================================================

-export([replace_nones/1,
	 update__info/2, new__info/1, return__info/1,
	 return_none/0, return_none_args/2, return_any_args/2]).

%%=====================================================================

-import(erl_types, [t_any/0,
		    t_from_range_unsafe/2,
		    t_inf/2, t_integer/0,
		    t_to_string/1, t_to_tlist/1,
		    t_limit/2, t_none/0,
		    number_min/1, number_max/1]).

-include("hipe_icode.hrl").
-include("hipe_icode_primops.hrl").
-include("../main/hipe.hrl").
-include("../flow/cfg.hrl").
-include("../flow/hipe_bb.hrl").
-include("hipe_icode_type.hrl").

-type range_tuple() :: {'neg_inf' | integer(), 'pos_inf' | integer()}.
-type range_rep()   :: range_tuple() | 'empty'.
-type fun_name()    :: atom() | tuple().
-type inf_integer() :: 'neg_inf' | 'pos_inf' | integer().

-record(range, {range :: range_rep(),
		other :: boolean()}).
-type range() :: #range{}.

-record(ann,   {range :: range(),
                type  :: erl_types:erl_type(),
		count :: integer()}).
-type ann() :: #ann{}.

-type range_anno() :: {'range_anno', ann(), fun((ann()) -> string())}.
-type args_fun() :: fun((mfa(), cfg()) -> [range()]).
-type call_fun() :: fun((mfa(), [range()]) -> range()).
-type final_fun() :: fun((mfa(), [range()]) -> 'ok').
-type data() :: {mfa(), args_fun(), call_fun(), final_fun()}.
-type label() :: non_neg_integer().
-type info() :: gb_tree().
-type work_list() :: {[label()], [label()], set()}.
-type variable() :: #icode_variable{}.
-type annotated_variable() :: #icode_variable{}.
-type argument() :: #icode_const{} | variable().
-type three_range_fun()   :: fun((range(),range(),range()) -> range()).
-type instr_split_info()  :: {icode_instr(), [{label(),info()}]}.
-type last_instr_return() :: {instr_split_info(), range()}.

-record(state, {info_map = gb_trees:empty()	:: info(), 
		counter  = dict:new()		:: dict(), 
		cfg				:: cfg(), 
		liveness = gb_trees:empty()	:: gb_tree(), 
		ret_type			:: range(),
		lookup_fun			:: call_fun(),
		result_action			:: final_fun()}).

-define(WIDEN, 1).

-define(TAG_IMMED1_SIZE, 4).

-define(BITS, 64).

%%---------------------------------------------------------------------

-spec cfg(cfg(), mfa(), comp_options(), #comp_servers{}) -> cfg().

cfg(Cfg, MFA, Options, Servers) ->
  case proplists:get_bool(concurrent_comp, Options) of
    true ->
      concurrent_cfg(Cfg, MFA, Servers#comp_servers.range);
    false ->
      ordinary_cfg(Cfg, MFA)
  end.

-spec concurrent_cfg(cfg(), mfa(), pid()) -> cfg().

concurrent_cfg(Cfg, MFA, CompServer) ->
  CompServer ! {ready, {MFA, self()}},
  {ArgsFun, CallFun, FinalFun} = do_analysis(Cfg, MFA),
  Ans = do_rewrite(Cfg, MFA, ArgsFun, CallFun, FinalFun),
  CompServer ! {done_rewrite, MFA},
  Ans.

-spec do_analysis(cfg(), mfa()) -> {args_fun(), call_fun(), final_fun()}.

do_analysis(Cfg, MFA) ->
  receive
    {analyse, {ArgsFun, CallFun, FinalFun}} ->
      analyse(Cfg, {MFA, ArgsFun, CallFun, FinalFun}),
      do_analysis(Cfg, MFA);
    {done, {_NewArgsFun, _NewCallFun, _NewFinalFun} = T} ->
      T
  end.

-spec do_rewrite(cfg(), mfa(), args_fun(), call_fun(), final_fun()) -> cfg().

do_rewrite(Cfg, MFA, ArgsFun, CallFun, FinalFun) ->
  common_rewrite(Cfg, {MFA, ArgsFun, CallFun, FinalFun}).
 
-spec ordinary_cfg(cfg(), mfa()) -> cfg().

ordinary_cfg(Cfg, MFA) ->
  Data = make_data(Cfg,MFA),
  common_rewrite(Cfg, Data).
  
-spec common_rewrite(cfg(), data()) -> cfg().

common_rewrite(Cfg, Data) ->
  State = safe_analyse(Cfg, Data),
  State2 = rewrite_blocks(State),
  Cfg1 = state__cfg(State2),
  Cfg2 = hipe_icode_cfg:remove_unreachable_code(Cfg1),
  Cfg3 = convert_cfg_to_types(Cfg2),
  hipe_icode_type:specialize(Cfg3).

-spec make_data(cfg(), mfa()) -> data().

make_data(Cfg, {_M,_F,A}=MFA) ->
  NoArgs = 
    case hipe_icode_cfg:is_closure(Cfg) of
      true -> hipe_icode_cfg:closure_arity(Cfg)+1;
      false -> A
    end,
  Args = lists:duplicate(NoArgs, any_type()), 
  ArgsFun = fun(_,_) -> Args end,
  CallFun = fun(_,_) -> any_type() end,
  FinalFun = fun(_,_) -> ok end,
  {MFA, ArgsFun, CallFun, FinalFun}.

-spec analyse(cfg(), data()) -> 'ok'.

analyse(Cfg, Data) ->
  try 
    #state{} = safe_analyse(Cfg, Data),
    ok
  catch throw:no_input -> ok
  end.

-spec safe_analyse(cfg(), data()) -> #state{}.

safe_analyse(CFG, Data={MFA,_,_,_}) ->
  State = state__init(CFG, Data),
  Work = init_work(State),
  NewState = analyse_blocks(State, Work),
  (state__result_action(NewState))(MFA, [state__ret_type(NewState)]),
  NewState.

-spec rewrite_blocks(#state{}) -> #state{}.

rewrite_blocks(State) ->
  CFG = state__cfg(State),
  Start = hipe_icode_cfg:start_label(CFG),
  rewrite_blocks([Start], State, [Start]).

-spec rewrite_blocks([label()], #state{}, [label()]) -> #state{}.

rewrite_blocks([Next|Rest], State, Visited) ->
  Info = state__info_in(State, Next),
  {NewState, NewLabels} = analyse_block(Next, Info, State, true),
  NewLabelsSet = ordsets:from_list(NewLabels),
  RealNew = ordsets:subtract(NewLabelsSet, Visited),
  NewVisited = ordsets:union([RealNew, Visited, [Next]]),
  NewWork = ordsets:union([RealNew, Rest]),
  rewrite_blocks(NewWork, NewState, NewVisited);
rewrite_blocks([], State, _) ->
  State.

-spec analyse_blocks(#state{}, work_list()) -> #state{}.

analyse_blocks(State, Work) ->
  case get_work(Work) of
    fixpoint ->
      State;
    {Label, NewWork} ->
      Info = state__info_in(State, Label),
      {NewState, NewLabels}  = 
	try analyse_block(Label, Info, State, false)
	catch throw:none_range ->
	    {State, []}
	end,
      NewWork2 = add_work(NewWork, NewLabels),
      analyse_blocks(NewState, NewWork2)
  end.

-spec analyse_block(label(), info(), #state{}, boolean()) -> {#state{}, [label()]}.

analyse_block(Label, Info, State, Rewrite) ->
  BB = state__bb(State, Label),
  Code = hipe_bb:code(BB),
  {NewCode, InfoList, RetType} = 
    analyse_BB(Code, Info, [], Rewrite, state__lookup_fun(State)),
  State1 = state__bb_add(State, Label, hipe_bb:mk_bb(NewCode)),
  State2 = state__ret_type_update(State1, RetType),
  state__update_info(State2, InfoList, Rewrite).

-spec analyse_BB([icode_instr()], info(), [icode_instr()], boolean(), call_fun()) ->
	 {[icode_instr()], [{label(),info()}], range()}.

analyse_BB([Last], Info, Code, Rewrite, LookupFun) ->
  {{NewI, LabelInfoList}, RetType} =
    analyse_last_insn(Last, Info, Rewrite, LookupFun),
  {lists:reverse([NewI|Code]), LabelInfoList, RetType};
analyse_BB([Insn|InsnList], Info, Code, Rewrite, LookupFun) ->
  {NewInfo, NewI} = analyse_insn(Insn, Info, LookupFun), 
  analyse_BB(InsnList, NewInfo, [NewI|Code], Rewrite, LookupFun).

-spec analyse_insn(icode_instr(), info(), call_fun()) -> {info(), icode_instr()}.

analyse_insn(I, Info, LookupFun) ->
  %% io:format("~w Info: ~p~n", [I, Info]),
  NewI = handle_args(I,Info),
  FinalI = 
    case NewI of 
      #icode_call{} -> analyse_call(NewI, LookupFun);
      #icode_move{} -> analyse_move(NewI);
      #icode_phi{} -> analyse_phi(NewI);
      #icode_begin_handler{} -> analyse_begin_handler(NewI);
      #icode_comment{} -> NewI
    end,
  {enter_vals(FinalI, Info), FinalI}.

-spec handle_args(icode_instr(), info()) -> icode_instr().

handle_args(I, Info) ->
  WidenFun = fun update_three/3,
  handle_args(I, Info, WidenFun).

-spec handle_args(icode_instr(), info(), three_range_fun()) -> icode_instr().

handle_args(I, Info, WidenFun) ->
  Uses = hipe_icode:uses(I),
  PresentRanges = [lookup(V, Info) || V <- Uses],
  %% io:format("Uses: ~p~nRanges: ~p~n", [Uses, PresentRanges]),
  JoinFun = fun(Var, Range) -> update_info(Var, Range, WidenFun) end,
  NewUses = lists:zipwith(JoinFun, Uses, PresentRanges),
  hipe_icode:subst_uses(lists:zip(Uses, NewUses), I).

-spec join_info(ann(), range(), three_range_fun()) -> ann().

join_info(Ann = #ann{range = R1, type = Type, count = ?WIDEN}, R2, Fun) ->
  Ann#ann{range = Fun(R1, R2, range_from_simple_type(Type))};
join_info(Ann = #ann{range = R1, type = Type, count = C}, R2, _Fun) when C < ?WIDEN ->
  case join_three(R1, R2, range_from_simple_type(Type)) of
    R1 -> Ann;
    NewR -> Ann#ann{range = NewR, count = C+1}
  end.

-spec join_three(range(), range(), range()) -> range().

join_three(R1, R2, R3) ->
  inf(sup(R1, R2), R3).

-spec update_info(variable(), range()) -> annotated_variable().

update_info(Var, Range) ->
  update_info(Var, Range, fun update_three/3).

-spec update_info(variable(), range(), three_range_fun()) -> annotated_variable().

update_info(Arg, R, Fun) ->
  case hipe_icode:is_annotated_variable(Arg) of
    true ->
      Ann = hipe_icode:variable_annotation(Arg),
      hipe_icode:annotate_variable(Arg, update_info1(Ann, R, Fun));
    false ->
      Arg
  end.

-spec update_info1(any(), range(), three_range_fun()) -> range_anno().

update_info1({range_anno, Ann, _}, R2, Fun) ->
  make_range_anno(update_ann(Ann,R2,Fun));
update_info1({type_anno, Type, _}, R2, Fun) ->
  make_range_anno(update_ann(type_to_ann(Type), R2, Fun)).

update_ann(Ann = #ann{range = R1, type = Type, count = ?WIDEN}, R2, Fun) ->
  Ann#ann{range = Fun(R1,R2,range_from_simple_type(Type))};
update_ann(Ann = #ann{range = R1, type = Type, count = C}, R2, _Fun) ->
  case update_three(R1, R2, range_from_simple_type(Type)) of
    R1 -> Ann;
    NewR -> Ann#ann{range = NewR, count = C+1}
  end.

-spec type_to_ann(erl_types:erl_type()) -> ann().

type_to_ann(Type) ->
  #ann{range = range_from_simple_type(Type), type = t_limit(Type,1), count = 1}.

-spec make_range_anno(ann()) -> range_anno().

make_range_anno(Ann) ->
  {range_anno, Ann, fun pp_ann/1}. 

-spec update_three(range(), range(), range()) -> range().

update_three(_R1, R2, R3) ->
  inf(R2, R3).

-spec safe_widen(range(), range(), range()) -> range().

safe_widen(#range{range=Old}, #range{range=New}, T = #range{range=Wide}) ->
  ResRange =
    case {Old, New, Wide} of
      {{Min,Max1}, {Min,Max2}, {_,Max}} ->
	case inf_geq(OMax = next_up_limit(inf_max([Max1, Max2])), Max) of
	  true -> {Min,Max};
	  false -> {Min,OMax}
	end;
      {{Min1,Max}, {Min2,Max}, {Min,_}} ->
	case inf_geq(Min, OMin = next_down_limit(inf_min([Min1, Min2]))) of
	  true -> {Min,Max};
	  false -> {OMin,Max}
	end;
      {{Min1,Max1}, {Min2,Max2}, {Min,Max}} ->
	RealMax =
	  case inf_geq(OMax = next_up_limit(inf_max([Max1, Max2])), Max) of
	    true -> Max;
	    false -> OMax
	  end,
	RealMin = 
	  case inf_geq(Min, OMin = next_down_limit(inf_min([Min1, Min2]))) of
	    true -> Min;
	    false -> OMin
	  end,
	{RealMin, RealMax};
      _ ->
	Wide
    end,
  T#range{range = ResRange}.

-spec widen(range(), range(), range()) -> range().

widen(#range{range=Old}, #range{range=New}, T = #range{range=Wide}) ->
  ResRange =
    case {Old, New, Wide} of
      {{Min,_}, {Min,Max2}, {_,Max}} ->
	case inf_geq(OMax = next_up_limit(Max2), Max) of
	  true -> {Min,Max};
	  false -> {Min,OMax}
	end;
      {{_,Max}, {Min2,Max}, {Min,_}} ->
	case inf_geq(Min, OMin = next_down_limit(Min2)) of
	  true -> {Min,Max};
	  false -> {OMin,Max}
	end;
      {_, {Min2,Max2}, {Min,Max}} ->
	RealMax =
	  case inf_geq(OMax = next_up_limit(Max2), Max) of
	    true -> Max;
	    false -> OMax
	  end,
	RealMin = 
	  case inf_geq(Min, OMin = next_down_limit(Min2)) of
	    true -> Min;
	    false -> OMin
	  end,
	{RealMin, RealMax};
      _ ->
	Wide
    end,
  T#range{range = ResRange}.

-spec analyse_call(#icode_call{}, call_fun()) -> #icode_call{}.

analyse_call(Call, LookupFun) ->
  case hipe_icode:call_dstlist(Call) of
    [] ->
      Call;
    Dsts ->
      Args = hipe_icode:args(Call),
      Fun = hipe_icode:call_fun(Call),
      Type = hipe_icode:call_type(Call),
      DstRanges = analyse_call_or_enter_fun(Fun, Args, Type, LookupFun),
      NewDefs = [update_info(Var, R) || {Var,R} <- lists:zip(Dsts, DstRanges)],
      hipe_icode:subst_defines(lists:zip(Dsts, NewDefs), Call)
  end.

-spec analyse_move(#icode_move{}) -> #icode_move{}.

analyse_move(Move) ->
  Src = hipe_icode:move_src(Move),
  Dst = hipe_icode:move_dst(Move),
  Range = get_range_from_arg(Src),
  NewDst = update_info(Dst, Range),  
  hipe_icode:subst_defines([{Dst,NewDst}], Move).

-spec analyse_begin_handler(#icode_begin_handler{}) -> #icode_begin_handler{}.

analyse_begin_handler(Handler) ->
  SubstList =
    [{Dst, update_info(Dst, any_type())} ||
      Dst <- hipe_icode:begin_handler_dstlist(Handler)],
  hipe_icode:subst_defines(SubstList, Handler).

-spec analyse_phi(#icode_phi{}) -> #icode_phi{}.
    
analyse_phi(Phi) ->
  {_, Args} = lists:unzip(hipe_icode:phi_arglist(Phi)),
  Dst = hipe_icode:phi_dst(Phi),
  ArgRanges = get_range_from_args(Args),
  %% io:format("Phi-Arg_ranges: ~p ~n", [Arg_ranges]),
  DstRange = sup(ArgRanges),
  NewDst = update_info(Dst, DstRange, fun widen/3),  
  hipe_icode:subst_defines([{Dst, NewDst}], Phi).

-spec analyse_last_insn(icode_instr(), info(), boolean(), call_fun()) ->
	  last_instr_return().

analyse_last_insn(I, Info, Rewrite, LookupFun) ->
  %% io:format("~w Info: ~p~n",[I,Info]),
  NewI = handle_args(I, Info),
  %% io:format("~w -> ~w~n",[NewI,I]),
  case NewI of 
    #icode_return{} -> analyse_return(NewI, Info);
    #icode_enter{} -> analyse_enter(NewI, Info, LookupFun);
    #icode_switch_val{} ->
      {analyse_switch_val(NewI, Info, Rewrite), none_type()};
    #icode_if{} -> {analyse_if(NewI, Info, Rewrite), none_type()};
    #icode_goto{} -> {analyse_goto(NewI, Info), none_type()};	
    #icode_type{} -> {analyse_type(NewI, Info, Rewrite), none_type()};
    #icode_fail{} -> {analyse_fail(NewI, Info), none_type()};
    #icode_call{} -> {analyse_last_call(NewI, Info, LookupFun), none_type()};
    #icode_switch_tuple_arity{} ->
      {analyse_switch_tuple_arity(NewI, Info), none_type()};
    #icode_begin_try{} -> {analyse_begin_try(NewI, Info), none_type()}
  end.

-spec analyse_return(#icode_return{}, info()) -> last_instr_return().

analyse_return(Insn, _Info) ->
  [RetRange] = get_range_from_args(hipe_icode:return_vars(Insn)),
  {{Insn,[]}, RetRange}.

-spec analyse_enter(#icode_enter{}, info(), call_fun()) -> last_instr_return().
  
analyse_enter(Insn, _Info, LookupFun) ->
  Args = hipe_icode:args(Insn),
  Fun = hipe_icode:enter_fun(Insn),
  CallType = hipe_icode:enter_type(Insn),
  [RetRange] = analyse_call_or_enter_fun(Fun, Args, CallType, LookupFun),
  {{Insn,[]}, RetRange}.

-spec analyse_switch_val(#icode_switch_val{}, info(), boolean()) -> instr_split_info().

analyse_switch_val(Switch, Info, Rewrite) -> 
  Var = hipe_icode:switch_val_term(Switch),
  SwitchRange = get_range_from_arg(Var),
  Cases = hipe_icode:switch_val_cases(Switch),
  {FailRange, LabelRangeList} = get_range_label_list(Cases, SwitchRange, []),
  case range__is_none(FailRange) of
    true -> 
      InfoList = update_infos(Var, Info, LabelRangeList),
      if Rewrite -> {update_switch(Switch, LabelRangeList, false), InfoList};
	 true -> {Switch, InfoList}
      end;
    false ->
      FailLabel = hipe_icode:switch_val_fail_label(Switch),
      InfoList = update_infos(Var, Info, [{FailRange, FailLabel}|LabelRangeList]),
      if Rewrite -> {update_switch(Switch, LabelRangeList, true), InfoList};
	 true -> {Switch, InfoList}
      end
  end.

-spec update_infos(argument(), info(), [{range(),label()}]) -> [{label(),info()}].

update_infos(Arg, Info, [{Range, Label}|Rest]) ->
  [{Label,enter_define({Arg,Range},Info)} | update_infos(Arg, Info, Rest)];
update_infos(_, _, []) -> [].

-spec get_range_label_list([{argument(),label()}], range(), [{range(),label()}]) ->
	 {range(),[{range(),label()}]}.

get_range_label_list([{Val,Label}|Cases], SRange, Acc) ->
  VRange = get_range_from_arg(Val),
  None = none_type(),
  case inf(SRange, VRange) of
    None ->
      get_range_label_list(Cases, SRange, Acc);
    ResRange ->
      get_range_label_list(Cases, SRange, [{ResRange,Label}|Acc])
  end;
get_range_label_list([], SRange, Acc) ->
  {PointTypes, _} = lists:unzip(Acc),
  {remove_point_types(SRange, PointTypes), Acc}.

-spec update_switch(#icode_switch_val{}, [{range(),label()}], boolean()) ->
	 #icode_switch_val{}.

update_switch(Switch, LabelRangeList, KeepFail) ->
  S2 =
    case label_range_list_to_cases(LabelRangeList, []) of
      no_update ->
	Switch;
      Cases ->
	hipe_icode:switch_val_cases_update(Switch, Cases)
    end,
  if KeepFail -> S2;
     true -> S2
  end.

-spec label_range_list_to_cases([{range(),label()}], [{#icode_const{},label()}]) ->
	 'no_update' | [{#icode_const{},label()}].

label_range_list_to_cases([{#range{range={C,C},other=false},Label}|Rest],
			  Acc) when is_integer(C) -> 
  label_range_list_to_cases(Rest, [{hipe_icode:mk_const(C),Label}|Acc]);
label_range_list_to_cases([{_NotAConstantRange,_Label}|_Rest], _Acc) ->
  no_update;
label_range_list_to_cases([], Acc) ->
  lists:reverse(Acc).

-spec analyse_switch_tuple_arity(#icode_switch_tuple_arity{}, info()) ->
	 {#icode_switch_tuple_arity{}, [{label(),info()}]}.
  
analyse_switch_tuple_arity(Switch, Info) -> 
  Var = hipe_icode:switch_tuple_arity_term(Switch),
  NewInfo = enter_define({Var, get_range_from_arg(Var)}, Info),
  Cases = hipe_icode:switch_tuple_arity_cases(Switch),
  Fail = hipe_icode:switch_tuple_arity_fail_label(Switch),
  {_, Case_labels} = lists:unzip(Cases),
  Labels = [Fail|Case_labels],
  {Switch, [{Label,NewInfo} || Label <- Labels]}.

-spec analyse_goto(#icode_goto{}, info()) -> {#icode_goto{}, [{label(),info()},...]}.

analyse_goto(Insn, Info) ->
  GotoLabel = hipe_icode:goto_label(Insn),
  {Insn, [{GotoLabel,Info}]}.

-spec analyse_fail(#icode_fail{}, info()) -> {#icode_fail{}, [{label(),info()}]}.

analyse_fail(Fail, Info) ->
  case hipe_icode:fail_label(Fail) of
    [] -> {Fail, []};
    Label -> {Fail, [{Label,Info}]}
  end.

-spec analyse_begin_try(#icode_begin_try{}, info()) ->
	 {#icode_begin_try{}, [{label(),info()},...]}.

analyse_begin_try(Insn, Info) ->
  Label = hipe_icode:begin_try_label(Insn),
  Successor = hipe_icode:begin_try_successor(Insn),
  {Insn, [{Label,Info},{Successor,Info}]}.

-spec analyse_last_call(#icode_call{}, info(), call_fun()) ->
	 {#icode_call{}, [{label(),info()},...]}.

analyse_last_call(Call, Info, LookupFun) ->
  %% hipe_icode_pp:pp_block([Insn]),
  NewI = analyse_call(Call, LookupFun),
  Continuation = hipe_icode:call_continuation(Call),
  NewInfo = enter_vals(NewI, Info),
  case hipe_icode:call_fail_label(Call) of
    [] -> 
      {NewI, [{Continuation, NewInfo}]};
    Fail ->
      {NewI, [{Continuation, NewInfo}, {Fail, Info}]}
  end.

-spec analyse_if(#icode_if{}, info(), boolean()) ->
	 {#icode_goto{} | #icode_if{}, [{label(),info()}]}.

analyse_if(If, Info, Rewrite) ->
  case hipe_icode:if_args(If) of
    [_, _] = Args ->
      analyse_sane_if(If, Info, Args, get_range_from_args(Args), Rewrite);
    _ ->
      TrueLabel = hipe_icode:if_true_label(If),
      FalseLabel = hipe_icode:if_false_label(If),
      {If, [{TrueLabel, Info}, {FalseLabel, Info}]}
  end.

-spec analyse_sane_if(#icode_if{}, info(), [argument(),...],
		      [range(),...], boolean()) ->
	 {#icode_goto{} | #icode_if{}, [{label(), info()}]}.

analyse_sane_if(If, Info, [Arg1, Arg2], [Range1, Range2], Rewrite) ->
  case normalize_name(hipe_icode:if_op(If)) of
    '>' ->
      {TrueRange2, TrueRange1, FalseRange2, FalseRange1} = 
	range_inequality_propagation(Range2, Range1);
    '<' ->
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2} =
	range_inequality_propagation(Range1, Range2);
    '>=' ->
      {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
	range_inequality_propagation(Range1, Range2);
    '=<' ->
      {FalseRange2, FalseRange1, TrueRange2, TrueRange1} =
	range_inequality_propagation(Range2, Range1);
    '=:=' ->
      {TrueRange1, TrueRange2, FalseRange1, FalseRange2} =
	range_equality_propagation(Range1, Range2);
    '=/=' ->
      {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
	range_equality_propagation(Range1, Range2);
    '==' ->
      {TempTrueRange1, TempTrueRange2, FalseRange1, FalseRange2} =
	range_equality_propagation(Range1, Range2),
      TrueRange1 = set_other(TempTrueRange1, other(Range1)),
      TrueRange2 = set_other(TempTrueRange2, other(Range2));
    '/=' -> 
      {TempFalseRange1, TempFalseRange2, TrueRange1, TrueRange2} =
	range_equality_propagation(Range1, Range2),
      FalseRange1 = set_other(TempFalseRange1, other(Range1)),
      FalseRange2 = set_other(TempFalseRange2, other(Range2))
  end,
  %% io:format("TR1 = ~w\nTR2 = ~w\n", [TrueRange1, TrueRange2]),
  True =
    case lists:all(fun range__is_none/1, [TrueRange1, TrueRange2]) of
      true -> [];
      false ->
	TrueLabel = hipe_icode:if_true_label(If),
	TrueArgRanges = [{Arg1, TrueRange1}, {Arg2, TrueRange2}],
	TrueInfo = enter_defines(TrueArgRanges, Info),
	[{TrueLabel, TrueInfo}]
    end,
  %% io:format("FR1 = ~w\nFR2 = ~w\n", [FalseRange1, FalseRange2]),
  False =
    case lists:all(fun range__is_none/1, [FalseRange1, FalseRange2]) of
      true -> [];
      false ->
	FalseLabel = hipe_icode:if_false_label(If),
	FalseArgRanges = [{Arg1, FalseRange1}, {Arg2, FalseRange2}],
	FalseInfo = enter_defines(FalseArgRanges, Info),
	[{FalseLabel, FalseInfo}]
    end,
  UpdateInfo = True ++ False,
  NewIF =
    if Rewrite ->
	case UpdateInfo of
	  [] -> %% This is weird
	    If;
	  [{Label, _Info}] ->
	    hipe_icode:mk_goto(Label);
	  [_, _] ->
	    If
	end;
       true ->
	If
    end,
  {NewIF, UpdateInfo}.

-spec normalize_name(atom()) -> atom().

normalize_name(Name) ->
  case Name of
    'fixnum_eq'  -> '=:='; 
    'fixnum_neq' -> '=/=';
    'fixnum_gt'  -> '>';
    'fixnum_lt'  -> '<';
    'fixnum_ge'  -> '>=';
    'fixnum_le'  -> '=<';
    Name -> Name
  end.

-spec range_equality_propagation(range(), range()) ->
	  {range(), range(), range(), range()}.

range_equality_propagation(Range_1, Range_2) ->  
  True_range = inf(Range_1, Range_2),
  case {range(Range_1), range(Range_2)} of
    {{N,N}, {N,N}} ->
      False_range_1 = none_range(),
      False_range_2 = none_range();
    {{N1,N1}, {N2,N2}} ->
      False_range_1 = Range_1,
      False_range_2 = Range_2;
    {{N,N}, _} ->
      False_range_1 = Range_1,
      {_,False_range_2} = compare_with_integer(N, Range_2);
    {_, {N,N}} ->
      False_range_2 = Range_2,
      {_,False_range_1} = compare_with_integer(N, Range_1);
    {_, _} ->
      False_range_1 = Range_1,
      False_range_2 = Range_2
  end,
  {True_range, True_range, False_range_1, False_range_2}.

-spec range_inequality_propagation(range(), range()) ->
	  {range(), range(), range(), range()}.

%% Range1 < Range2
range_inequality_propagation(Range1, Range2) ->
  R1_other = other(Range1),
  R2_other = other(Range2),
  {R1_true_range, R1_false_range, R2_true_range, R2_false_range} =
    case {range(Range1), range(Range2)} of
      {{N1,N1}, {N2,N2}} ->
	case inf_geq(N2,inf_add(N1,1)) of
	  true ->
	    {{N1,N1},empty,{N2,N2},empty};
	  false ->
	    {empty,{N1,N1},empty,{N2,N2}}
	  end;
      {{N1,N1}, {Min2,Max2}} ->
	case inf_geq(Min2,inf_add(N1,1)) of
	  true ->
	    {{N1,N1},empty,{inf_add(N1,1),Max2},empty};
	  false ->
	    case inf_geq(N1,Max2) of
	      true ->
		{empty,{N1,N1},empty,{Min2,N1}};
	      false ->
		{{N1,N1},{N1,N1},{inf_add(N1,1),Max2},{Min2,N1}}
	    end
	end;
      {{Min1,Max1}, {N2,N2}} ->
	case inf_geq(N2,inf_add(Max1,1)) of
	  true ->
	  {{Min1,inf_add(N2,-1)},empty,{N2,N2},empty};
	  false ->
	    case inf_geq(Min1,N2) of
	      true ->
		{empty,{N2,Max1},empty,{N2,N2}};
	      false ->
		{{Min1,inf_add(N2,-1)},{N2,Max1},{N2,N2},{N2,N2}}
	    end
	end;
      {empty, {Min2,Max2}} ->
	{empty,empty,{Min2,Max2},{Min2,Max2}};
      {{Min1,Max1}, empty} ->
	{{Min1,Max1},{Min1,Max1},empty,empty};
      {empty, empty} ->
	{empty,empty,empty,empty};
      {{Min1,Max1}, {Min2,Max2}} ->
	{{Min1,inf_min([Max1,inf_add(Max2,-1)])},
	 {inf_max([Min1,Min2]),Max1},
	 {inf_max([inf_add(Min1,1),Min2]),Max2},
	 {Min2,inf_min([Max1,Max2])}}
    end,
  {range_init(R1_true_range, R1_other),
   range_init(R2_true_range, R2_other),
   range_init(R1_false_range, R1_other),
   range_init(R2_false_range, R2_other)}.

-spec analyse_type(#icode_type{}, info(), boolean()) ->
	 {#icode_goto{} | #icode_type{}, [{label(),info()}]}.

analyse_type(Type, Info, Rewrite) ->
  TypeTest = hipe_icode:type_test(Type),
  [Arg|_] = hipe_icode:type_args(Type),
  OldVarRange = get_range_from_arg(Arg),
  case TypeTest of
    {integer, N} ->
      {TrueRange,FalseRange} = compare_with_integer(N,OldVarRange);
    integer ->
      TrueRange = inf(any_range(), OldVarRange),
      FalseRange = inf(none_range(), OldVarRange);
    number ->
      TrueRange = FalseRange = OldVarRange;
    _ ->
      TrueRange = inf(none_range(), OldVarRange),
      FalseRange = OldVarRange
  end,
  TrueLabel = hipe_icode:type_true_label(Type),
  FalseLabel = hipe_icode:type_false_label(Type),
  TrueInfo = enter_define({Arg, TrueRange}, Info),
  FalseInfo = enter_define({Arg, FalseRange}, Info),
  True =
    case range__is_none(TrueRange) of
      true -> [];
      false -> [{TrueLabel, TrueInfo}]
    end,
  False =
    case range__is_none(FalseRange) of
      true -> [];
      false -> [{FalseLabel, FalseInfo}]
    end,
  UpdateInfo = True ++ False,
  NewType =
    if Rewrite ->
	case UpdateInfo of
	  [] -> %% This is weird
	    Type;
	  [{Label,_Info}] ->
	    hipe_icode:mk_goto(Label);
	  [_, _] ->
	    Type
	end;
       true ->
	Type
    end,
  {NewType, True ++ False}.

-spec compare_with_integer(integer(), range()) -> {range(), range()}.

compare_with_integer(N, OldVarRange) ->
  TestRange = range_init({N, N}, false),
  TrueRange = inf(TestRange, OldVarRange),
  %% False range
  TempFalseRange = range__remove_constant(OldVarRange, TestRange),
  BetterRange = 
    case range(TempFalseRange) of
      {Min, Max} = MM ->
	New_small = inf_geq(Min, N),
	New_large = inf_geq(N, Max),
	if New_small and not New_large ->
	    {N + 1, Max};
	   New_large and not New_small ->
	    {Min, N - 1};
	   true -> 
	    MM
	end;
      Not_tuple ->
	Not_tuple
    end,
  FalseRange = range_init(BetterRange, other(TempFalseRange)),
  {TrueRange, FalseRange}.

%%== Ranges ==================================================================

-spec pp_ann(ann() | erl_types:erl_type()) -> string().

pp_ann(#ann{range = #range{range = R, other = false}}) ->
  pp_range(R);
pp_ann(#ann{range = #range{range = empty, other = true}, type = Type}) ->
  t_to_string(Type);
pp_ann(#ann{range = #range{range = R, other = true}, type = Type}) ->
  pp_range(R) ++ " | " ++ t_to_string(Type);
pp_ann(Type) ->
  t_to_string(Type).

-spec pp_range(range_rep()) -> nonempty_string().

pp_range(empty) ->
  "none";
pp_range({Min, Max}) ->
  val_to_string(Min) ++ ".." ++ val_to_string(Max).

-spec val_to_string('pos_inf' | 'neg_inf' | integer()) -> string().

val_to_string(pos_inf) -> "inf";
val_to_string(neg_inf) -> "-inf";
val_to_string(X) when is_integer(X) -> integer_to_list(X).

-spec range_from_type(erl_types:erl_type()) -> [range()].

range_from_type(Type) ->
  [range_from_simple_type(T) || T <- t_to_tlist(Type)].
  
-spec range_from_simple_type(erl_types:erl_type()) -> range().

range_from_simple_type(Type) ->
  None = t_none(),
  case t_inf(t_integer(), Type) of
    None ->
      #range{range = empty, other = true};
    Type ->
      Range = {number_min(Type), number_max(Type)},
      #range{range = Range, other = false};
    NewType ->
      Range = {number_min(NewType), number_max(NewType)},
      #range{range = Range, other = true}
  end.

-spec range_init(range_rep(), boolean()) -> range().

range_init({Min, Max} = Range, Other) ->
  case inf_geq(Max, Min) of
    true ->
      #range{range = Range, other = Other};
    false ->
      #range{range = empty, other = Other}
  end;
range_init(empty, Other) ->
  #range{range = empty, other = Other}.

-spec range(range()) -> range_rep().

range(#range{range = R}) -> R.

-spec other(range()) -> boolean().

other(#range{other = O}) -> O.

-spec set_other(range(), boolean()) -> range().

set_other(R, O) -> R#range{other = O}.

-spec range__min(range()) -> 'empty' | 'neg_inf' | integer().

range__min(#range{range = empty}) -> empty;
range__min(#range{range = {Min,_}}) -> Min.

-spec range__max(range()) -> 'empty' | 'pos_inf' | integer().

range__max(#range{range = empty}) -> empty;
range__max(#range{range = {_,Max}}) -> Max.

-spec range__is_none(range()) -> boolean().

range__is_none(#range{range = empty, other = false}) -> true;
range__is_none(#range{}) -> false.

-spec range__is_empty(range()) -> boolean().

range__is_empty(#range{range = empty}) -> true;
range__is_empty(#range{range = {_,_}}) -> false.

-spec remove_point_types(range(), [range()]) -> range().

remove_point_types(Range, Ranges) ->
  Sorted = lists:sort(Ranges),
  FoldFun = fun (R, Acc) -> range__remove_constant(Acc,R) end,
  Range1 = lists:foldl(FoldFun, Range, Sorted),
  lists:foldl(FoldFun, Range1, lists:reverse(Sorted)).

-spec range__remove_constant(range(), range()) -> range().

range__remove_constant(#range{range = {C, C}} = R, #range{range = {C, C}}) ->
  R#range{range = empty};
range__remove_constant(#range{range = {C, H}} = R, #range{range = {C, C}}) ->
  R#range{range = {C+1, H}};
range__remove_constant(#range{range = {L, C}} = R, #range{range = {C, C}}) ->
  R#range{range = {L, C-1}};
range__remove_constant(#range{} = R, #range{range = {C,C}}) ->
  R;
range__remove_constant(#range{} = R, _) ->
  R.

-spec any_type() -> range().

any_type() ->
  #range{range = any_r(), other = true}.

-spec any_range() -> range().

any_range() ->
  #range{range = any_r(), other = false}.

-spec none_range() -> range().

none_range() ->
  #range{range = empty, other = true}.

-spec none_type() -> range().

none_type() ->
  #range{range = empty, other = false}.

-spec any_r() -> {'neg_inf','pos_inf'}.

any_r() -> {neg_inf, pos_inf}.

-spec get_range_from_args([argument()]) -> [range()].
  
get_range_from_args(Args) ->
  [get_range_from_arg(Arg) || Arg <- Args].

-spec get_range_from_arg(argument()) -> range().

get_range_from_arg(Arg) ->
  case hipe_icode:is_const(Arg) of
    true ->
      Value = hipe_icode:const_value(Arg),
      case is_integer(Value) of
	true ->
	  #range{range = {Value, Value}, other = false};
	false ->
	  #range{range = empty, other = true}
      end;
    false ->
      case hipe_icode:is_annotated_variable(Arg) of
	true ->
	  case hipe_icode:variable_annotation(Arg) of
	    {range_anno, #ann{range = Range}, _} ->
	      Range;
	    {type_anno, Type, _} ->
	      range_from_simple_type(Type)
	  end;
	false ->
	  any_type()
      end
  end.

%% inf([R]) ->
%%   R;
%% inf([R1,R2|Rest]) ->
%%   inf([inf(R1,R2)|Rest]).

-spec inf(range(), range()) -> range().

inf(#range{range=R1, other=O1}, #range{range=R2, other=O2}) -> 
  #range{range=range_inf(R1,R2), other=other_inf(O1,O2)}.

-spec range_inf(range_rep(), range_rep()) -> range_rep().

range_inf(empty, _) -> empty;
range_inf(_, empty) -> empty;
range_inf({Min1,Max1}, {Min2,Max2}) ->
  NewMin = inf_max([Min1, Min2]),
  NewMax = inf_min([Max1, Max2]),
  case inf_geq(NewMax, NewMin) of
    true ->
      {NewMin, NewMax};
    false ->
      empty
  end.

-spec other_inf(boolean(), boolean()) -> boolean().

other_inf(O1, O2) -> O1 and O2.

-spec sup([range(),...]) -> range().

sup([R]) ->
  R;
sup([R1,R2|Rest]) ->
  sup([sup(R1, R2)|Rest]).

-spec sup(range(), range()) -> range().

sup(#range{range=R1,other=O1}, #range{range=R2,other=O2}) -> 
  #range{range=range_sup(R1,R2), other=other_sup(O1,O2)}.

-spec range_sup(range_rep(), range_rep()) -> range_rep().
	 
range_sup(empty, R) -> R;
range_sup(R, empty) -> R;
range_sup({Min1,Max1}, {Min2,Max2}) ->
  NewMin = inf_min([Min1,Min2]),
  NewMax = inf_max([Max1,Max2]),
  {NewMin,NewMax}.

-spec other_sup(boolean(), boolean()) -> boolean().

other_sup(O1, O2) -> O1 or O2.

%%== Call Support =============================================================

-spec analyse_call_or_enter_fun(fun_name(), [argument()],
				icode_call_type(), call_fun()) -> [range()].

analyse_call_or_enter_fun(Fun, Args, CallType, LookupFun) ->
  %%io:format("Fun: ~p~n Args: ~p~n CT: ~p~n LF: ~p~n", [Fun, Args, CallType, LookupFun]),
  case basic_type(Fun) of
    {bin, Operation} ->
      [Arg_range1,Arg_range2] = get_range_from_args(Args),
      A1_is_empty = range__is_empty(Arg_range1),
      A2_is_empty = range__is_empty(Arg_range2),
      case A1_is_empty orelse A2_is_empty of
	true ->
	  [none_type()];
	false ->
	  [Operation(Arg_range1, Arg_range2)]
      end;
    {unary, Operation} ->
      [Arg_range] = get_range_from_args(Args),
      case range__is_empty(Arg_range) of
	true ->
	  [none_type()];
	false ->
	  [Operation(Arg_range)]
      end;
    {fcall, MFA} ->
      case CallType of
	local ->
	  Range = LookupFun(MFA, get_range_from_args(Args)),
	  case range__is_none(Range) of
	    true ->
	      throw(none_range);
	    false ->
	      [Range]
	  end;
	remote ->
	  [any_type()]
      end;
    not_int ->
      [any_type()];
    not_analysed -> 
      [any_type()];
    {hipe_bs_primop, {bs_get_integer, Size, Flags}} ->
      {Min, Max} = analyse_bs_get_integer(Size, Flags, length(Args) =:= 1),
      [#range{range = {Min, Max}, other = false}, any_type()];
    {hipe_bs_primop, _} = Primop ->
      Type = hipe_icode_primops:type(Primop),
      range_from_type(Type)
  end.

-type bin_operation() :: fun((range(), range()) -> range()).
-type unary_operation() :: fun((range()) -> range()).

-spec basic_type(fun_name()) -> 'not_int' | 'not_analysed'
			     | {'bin', bin_operation()}
			     | {'unary', unary_operation()}
			     | {'fcall', mfa()} | {'hipe_bs_primop', _}.

%% Arithmetic operations
basic_type('+') -> {bin, fun(R1, R2) -> range_add(R1, R2) end};
basic_type('-') -> {bin, fun(R1, R2) -> range_sub(R1, R2) end};
basic_type('*') -> {bin, fun(R1, R2) -> range_mult(R1, R2) end};
basic_type('/') -> not_int;
basic_type('div') -> {bin, fun(R1, R2) -> range_div(R1, R2) end};
basic_type('rem') -> {bin, fun(R1, R2) -> range_rem(R1, R2) end};
basic_type('bor') -> {bin, fun(R1, R2) -> range_bor(R1, R2) end};
basic_type('band') -> {bin, fun(R1, R2) -> range_band(R1, R2) end};
basic_type('bxor') -> {bin, fun(R1, R2) -> range_bxor(R1, R2) end};
basic_type('bnot') -> {unary, fun(R1) -> range_bnot(R1) end};
basic_type('bsl') -> {bin, fun(R1, R2) -> range_bsl(R1, R2) end};
basic_type('bsr') -> {bin, fun(R1, R2) -> range_bsr(R1, R2) end};
%% unsafe_*
basic_type('unsafe_bor') ->  
  {bin, fun(R1, R2) -> range_bor(R1, R2) end};
basic_type('unsafe_band') ->
  {bin, fun(R1, R2) -> range_band(R1, R2) end};
basic_type('unsafe_bxor') ->
  {bin, fun(R1, R2) -> range_bxor(R1, R2) end};
basic_type('unsafe_bnot') ->
  {unary, fun(R1) -> range_bnot(R1) end};
basic_type('unsafe_bsl') ->
  {bin, fun(R1, R2) -> range_bsl(R1, R2) end};
basic_type('unsafe_bsr') ->
  {bin, fun(R1, R2) -> range_bsr(R1, R2) end};
basic_type('unsafe_add') ->
  {bin, fun(R1, R2) -> range_add(R1, R2) end};
basic_type('unsafe_sub') ->
  {bin, fun(R1, R2) -> range_sub(R1, R2) end};
basic_type('extra_unsafe_add') ->
  {bin, fun(R1, R2) -> range_add(R1, R2) end};
basic_type('extra_unsafe_sub') ->
  {bin, fun(R1, R2) -> range_sub(R1, R2) end};
%% Binaries
basic_type({hipe_bs_primop, _} = Primop) -> Primop;
%% Unknown, other
basic_type(call_fun) -> not_analysed;
basic_type(clear_timeout) -> not_analysed;
basic_type(redtest) -> not_analysed;
basic_type(set_timeout) -> not_analysed;
basic_type(#apply_N{}) -> not_analysed;
basic_type(#closure_element{}) -> not_analysed;
basic_type(#gc_test{}) -> not_analysed;
%% Message handling
basic_type(check_get_msg) -> not_analysed;
basic_type(next_msg) -> not_analysed;
basic_type(select_msg) -> not_analysed;
basic_type(suspend_msg) -> not_analysed;
%% Functions
basic_type(enter_fun) -> not_analysed;
basic_type(#mkfun{}) -> not_int;
basic_type({_M,_F,_A} = MFA) -> {fcall, MFA}; 
%% Floats
basic_type(conv_to_float) -> not_int;
basic_type(fclearerror) -> not_analysed;
basic_type(fcheckerror) -> not_analysed;
basic_type(fnegate) -> not_int;
basic_type(fp_add) -> not_int;
basic_type(fp_div) -> not_int;
basic_type(fp_mul) -> not_int;
basic_type(fp_sub) -> not_int;
basic_type(unsafe_tag_float) -> not_int;
basic_type(unsafe_untag_float) -> not_int;
%% Lists, tuples, records
basic_type(cons) -> not_int;
basic_type(mktuple) -> not_int;
basic_type(unsafe_hd) -> not_analysed;
basic_type(unsafe_tl) -> not_int;
basic_type(#element{}) -> not_analysed;
basic_type(#unsafe_element{}) -> not_analysed;
basic_type(#unsafe_update_element{}) -> not_analysed.

-spec analyse_bs_get_integer(integer(), integer(), boolean()) -> range_tuple().

analyse_bs_get_integer(Size, Flags, true) ->
  Signed = Flags band 4,
  if Signed =:= 0 ->
      Max = 1 bsl Size - 1,
      Min = 0;
     true ->
      Max = 1 bsl (Size-1) - 1,
      Min = -(1 bsl (Size-1))
  end,
  {Min, Max};
analyse_bs_get_integer(Size, Flags, false) when is_integer(Size),
						is_integer(Flags) ->
  any_r().

%%---------------------------------------------------------------------------
%% Range operations
%%---------------------------------------------------------------------------

%% Arithmetic

-spec range_add(range(), range()) -> range().

range_add(Range1, Range2) ->
  NewMin = inf_add(range__min(Range1), range__min(Range2)),
  NewMax = inf_add(range__max(Range1), range__max(Range2)),
  Other = other(Range1) orelse other(Range2),
  range_init({NewMin, NewMax}, Other).

-spec range_sub(range(), range()) -> range().

range_sub(Range1, Range2) ->
  Min_sub = inf_min([inf_inv(range__max(Range2)), 
		     inf_inv(range__min(Range2))]),
  Max_sub = inf_max([inf_inv(range__max(Range2)), 
		     inf_inv(range__min(Range2))]),
  NewMin = inf_add(range__min(Range1), Min_sub),
  NewMax = inf_add(range__max(Range1), Max_sub),
  Other = other(Range1) orelse other(Range2),
  range_init({NewMin, NewMax}, Other).

-spec range_mult(range(), range()) -> range().

range_mult(#range{range=empty, other=true}, _Range2) ->
  range_init(empty, true);
range_mult(_Range1, #range{range=empty, other=true}) ->
  range_init(empty, true);
range_mult(Range1, Range2) ->
  Min1 = range__min(Range1),
  Min2 = range__min(Range2),
  Max1 = range__max(Range1),
  Max2 = range__max(Range2),
  GreaterMin1 = inf_greater_zero(Min1),
  GreaterMin2 = inf_greater_zero(Min2),
  GreaterMax1 = inf_greater_zero(Max1),
  GreaterMax2 = inf_greater_zero(Max2),
  Range =
    if GreaterMin1 -> 
	if GreaterMin2 -> {inf_mult(Min1, Min2), inf_mult(Max1, Max2)};
	   GreaterMax2 -> {inf_mult(Min2, Max1), inf_mult(Max2, Max1)};
	   true        -> {inf_mult(Min2, Max1), inf_mult(Max2, Min1)}
	end;
       %% Column 1 or 2
       GreaterMin2 -> % Column 1 or 2 row 3
	range(range_mult(Range2, Range1));
       GreaterMax1 -> % Column 2 Row 1 or 2
	if GreaterMax2 -> % Column 2 Row 2
	    NewMin = inf_min([inf_mult(Min2, Max1), inf_mult(Max2, Min1)]),
	    NewMax = inf_max([inf_mult(Min2, Min1), inf_mult(Max2, Max1)]),
	    {NewMin, NewMax};
	   true -> % Column 2 Row 1
	    {inf_mult(Min2, Max1), inf_mult(Min2, Min1)}
	end;
       GreaterMax2 -> % Column 1 Row 2
	range(range_mult(Range2, Range1));
       true -> % Column 1 Row 1
	{inf_mult(Max1, Max2), inf_mult(Min2, Min1)}
    end,
  Other = other(Range1) orelse other(Range2),
  range_init(Range, Other).

-spec extreme_divisors(range()) -> range_tuple().

extreme_divisors(#range{range={0,0}}) -> {0,0};
extreme_divisors(#range{range={0,Max}}) -> {1,Max};
extreme_divisors(#range{range={Min,0}}) -> {Min,-1};
extreme_divisors(#range{range={Min,Max}}) ->
  case inf_geq(Min, 0) of 
    true -> {Min, Max};
    false -> % Min < 0
      case inf_geq(0, Max) of
	true -> {Min,Max}; % Max < 0
	false -> {-1,1} % Max > 0
      end
  end.

-spec range_div(range(), range()) -> range().

%% this is div, not /.
range_div(_, #range{range={0,0}}) ->
  range_init(empty, false);
range_div(#range{range=empty}, _) ->
  range_init(empty, false);
range_div(_, #range{range=empty}) ->
  range_init(empty, false);
range_div(Range1, Den) ->
  Min1 = range__min(Range1),
  Max1 = range__max(Range1),
  {Min2, Max2} = extreme_divisors(Den),
  Min_max_list = [inf_div(Min1, Min2), inf_div(Min1, Max2),
		  inf_div(Max1, Min2), inf_div(Max1, Max2)],
  range_init({inf_min(Min_max_list), inf_max(Min_max_list)}, false).

-spec range_rem(range(), range()) -> range().

range_rem(Range1, Range2) ->
  %% Range1 desides the sign of the answer.
  Min1 = range__min(Range1),
  Max1 = range__max(Range1),
  Min2 = range__min(Range2),
  Max2 = range__max(Range2),
  Min1_geq_zero = inf_geq(Min1, 0),
  Max1_leq_zero = inf_geq(0, Max1),
  Max_range2 = inf_max([inf_abs(Min2), inf_abs(Max2)]),
  Max_range2_leq_zero = inf_geq(0, Max_range2),
  New_min = 
    if Min1_geq_zero ->	0;
       Max_range2_leq_zero -> Max_range2;
       true -> inf_inv(Max_range2)
    end,
  New_max = 
    if Max1_leq_zero -> 0;
       Max_range2_leq_zero -> inf_inv(Max_range2);
       true -> Max_range2
    end,
  range_init({New_min, New_max}, false).

%%--- Bit operations ----------------------------

-spec range_bsr(range(), range()) -> range().

range_bsr(Range1, Range2=#range{range={Min, Max}}) -> 
  New_Range2 = range_init({inf_inv(Max), inf_inv(Min)}, other(Range2)), 
  Ans = range_bsl(Range1, New_Range2),
  %% io:format("bsr res:~w~nInput:= ~w~n", [Ans, {Range1,Range2}]),
  Ans.

-spec range_bsl(range(), range()) -> range().

range_bsl(Range1, Range2) ->
  Min1 = range__min(Range1),
  Min2 = range__min(Range2),
  Max1 = range__max(Range1),
  Max2 = range__max(Range2),
  Min1Geq0 = inf_geq(Min1, 0),
  Max1Less0 = not inf_geq(Max1, 0),
  MinMax =
    if Min1Geq0 ->
	{inf_bsl(Min1, Min2), inf_bsl(Max1, Max2)};
       true ->
	if Max1Less0 -> {inf_bsl(Min1, Max2), inf_bsl(Max1, Min2)};
	   true -> {inf_bsl(Min1, Max2), inf_bsl(Max1, Max2)}
	end
    end,
  range_init(MinMax, false).

-spec range_bnot(range()) -> range().

range_bnot(Range) ->
  Minus_one = range_init({-1,-1}, false),
  range_add(range_mult(Range, Minus_one), Minus_one).

-spec width(range_rep() | inf_integer()) -> 'pos_inf' | non_neg_integer().

width({Min, Max}) -> inf_max([width(Min), width(Max)]);
width(pos_inf) -> pos_inf;
width(neg_inf) -> pos_inf;
width(X) when is_integer(X), X >= 0 -> poswidth(X, 0);
width(X) when is_integer(X), X < 0 -> negwidth(X, 0).

-spec poswidth(non_neg_integer(), non_neg_integer()) -> non_neg_integer().

poswidth(X, N) ->
  case X < (1 bsl N) of
    true  -> N;
    false -> poswidth(X, N+1)
  end.

-spec negwidth(neg_integer(), non_neg_integer()) -> non_neg_integer().

negwidth(X, N) ->
  case X > (-1 bsl N) of
    true  -> N;
    false -> negwidth(X, N+1)
  end.

-spec range_band(range(), range()) -> range().

range_band(R1, R2) ->
  {_Min1, Max1} = MM1 = range(R1),
  {_Min2, Max2} = MM2 = range(R2),
  Width1 = width(MM1),
  Width2 = width(MM2),
  Range = 
    case {classify_range(R1), classify_range(R2)} of
      {minus_minus, minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), -1};
      {minus_minus, minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), Max2};
      {minus_minus, plus_plus} ->
	{0, Max2};
      {minus_plus,  minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), Max1};
      {minus_plus,  minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), inf_max([Max1, Max2])};
      {minus_plus,  plus_plus} ->
	{0, Max2};
      {plus_plus,   minus_minus} ->
	{0, Max1};
      {plus_plus,   minus_plus} ->
	{0, Max1};
      {plus_plus,   plus_plus} ->
	{0, inf_min([Max1, Max2])}
    end,
  range_init(Range, false).  

-spec range_bor(range(), range()) -> range().

range_bor(R1, R2) ->
  {Min1, _Max1} = MM1 = range(R1),
  {Min2, _Max2} = MM2 = range(R2),
  Width1 = width(MM1),
  Width2 = width(MM2),
  Range = 
    case {classify_range(R1), classify_range(R2)} of
      {minus_minus, minus_minus} ->
	{inf_max([Min1, Min2]), -1};
      {minus_minus, minus_plus} ->
	{Min1, -1};
      {minus_minus, plus_plus} ->
	{Min1, -1};
      {minus_plus,  minus_minus} ->
	{Min2, -1};
      {minus_plus,  minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_min([Min1, Min2]), inf_add(-1, inf_bsl(1, Width))};
      {minus_plus,  plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{Min1, inf_add(-1, inf_bsl(1, Width))};
      {plus_plus,   minus_minus} ->
	{Min2, -1};
      {plus_plus,   minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{Min2, inf_add(-1, inf_bsl(1, Width))};
      {plus_plus,   plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{0, inf_add(-1, inf_bsl(1, Width))}
    end,
  range_init(Range, false).  

-spec classify_range(range()) -> 'minus_minus' | 'minus_plus' | 'plus_plus'.

classify_range(Range) ->
  case range(Range) of
    {neg_inf, Number} when is_integer(Number), Number < 0 -> minus_minus;
    {neg_inf, Number} when is_integer(Number), Number >= 0 -> minus_plus;
    {Number, pos_inf} when is_integer(Number), Number < 0 -> minus_plus;
    {Number, pos_inf} when is_integer(Number), Number >= 0 -> plus_plus;
    {neg_inf, pos_inf} -> minus_plus;
    {Number1,Number2} when is_integer(Number1), is_integer(Number2) ->
      classify_int_range(Number1, Number2)
  end.

-spec classify_int_range(integer(), integer()) ->
	  'minus_minus' | 'minus_plus' | 'plus_plus'.

classify_int_range(Number1, _Number2) when Number1 >= 0 ->
  plus_plus;
classify_int_range(_Number1, Number2) when Number2 < 0 ->
  minus_minus;
classify_int_range(_Number1, _Number2) ->
  minus_plus.
      
-spec range_bxor(range(), range()) -> range().

range_bxor(R1, R2) ->
  {Min1, Max1} = MM1 = range(R1),
  {Min2, Max2} = MM2 = range(R2),
  Width1 = width(MM1),
  Width2 = width(MM2),
  Range =
    case {classify_range(R1), classify_range(R2)} of
      {minus_minus, minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{0, inf_add(-1, inf_bsl(1, Width))};
      {minus_minus, minus_plus} ->
	MinWidth = inf_max([Width1, width({0,Max2})]),
	MaxWidth = inf_max([Width1, width({Min2,-1})]),
	{inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
      {minus_minus, plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), -1};
      {minus_plus,  minus_minus} ->
	MinWidth = inf_max([Width2,width({0,Max1})]),
	MaxWidth = inf_max([Width2,width({Min1,-1})]),
	{inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
      {minus_plus,  minus_plus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), inf_add(-1, inf_bsl(1, Width))};
      {minus_plus,  plus_plus} ->
	MinWidth = inf_max([Width2,width({Min1,-1})]),
	MaxWidth = inf_max([Width2,width({0,Max1})]),
	{inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
      {plus_plus,   minus_minus} ->
	Width = inf_max([Width1, Width2]),
	{inf_bsl(-1, Width), -1};
      {plus_plus,   minus_plus} ->
	MinWidth = inf_max([Width1,width({Min2,-1})]),
	MaxWidth = inf_max([Width1,width({0,Max2})]),
	{inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
      {plus_plus,   plus_plus} ->
	Width = inf_max([Width1, Width2]),
	{0, inf_add(-1, inf_bsl(1, Width))}
    end,
  range_init(Range, false).  

%%---------------------------------------------------------------------------
%% Inf operations
%%---------------------------------------------------------------------------

-spec inf_max([inf_integer(),...]) -> inf_integer().

inf_max([H|T]) ->
  lists:foldl(fun (Elem, Max) ->
		  case inf_geq(Elem, Max) of
		    false -> Max;
		    true  -> Elem
		  end
	      end, H, T).

-spec inf_min([inf_integer(),...]) -> inf_integer().

inf_min([H|T]) ->
  lists:foldl(fun (Elem, Min) ->
		  case inf_geq(Elem, Min) of
		    true  -> Min;
		    false -> Elem
		  end
	      end, H, T).

-spec inf_abs(inf_integer()) -> 'pos_inf' | integer().

inf_abs(pos_inf) -> pos_inf;
inf_abs(neg_inf) -> pos_inf;
inf_abs(Number) when is_integer(Number), (Number < 0) -> - Number;
inf_abs(Number) when is_integer(Number) -> Number.

-spec inf_add(inf_integer(), inf_integer()) -> inf_integer().

inf_add(pos_inf, _Number) -> pos_inf;
inf_add(neg_inf, _Number) -> neg_inf;
inf_add(_Number, pos_inf) -> pos_inf;
inf_add(_Number, neg_inf) -> neg_inf;
inf_add(Number1, Number2) when is_integer(Number1), is_integer(Number2) ->
  Number1 + Number2.

-spec inf_inv(inf_integer()) -> inf_integer().

inf_inv(pos_inf) -> neg_inf;
inf_inv(neg_inf) -> pos_inf;
inf_inv(Number) -> -Number.

-spec inf_geq(inf_integer(), inf_integer()) -> boolean().

inf_geq(pos_inf, _) -> true;
inf_geq(_, pos_inf) -> false;
inf_geq(_, neg_inf) -> true;
inf_geq(neg_inf, _) -> false;
inf_geq(A, B) -> A >= B.

-spec inf_greater_zero(inf_integer()) -> boolean().

inf_greater_zero(pos_inf) -> true;
inf_greater_zero(neg_inf) -> false;
inf_greater_zero(Number) when is_integer(Number), Number >= 0 -> true;
inf_greater_zero(Number) when is_integer(Number), Number < 0 -> false.

-spec inf_div(inf_integer(), inf_integer()) -> inf_integer().

inf_div(Number, 0) ->
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_div(pos_inf, Number) ->
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_div(neg_inf, Number) ->
  Greater = inf_greater_zero(Number),
  if Greater -> neg_inf;
     true -> pos_inf
  end;
inf_div(Number, pos_inf) -> 
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_div(Number, neg_inf) ->
  Greater = inf_greater_zero(Number),
  if Greater -> neg_inf;
     true -> pos_inf
  end;
inf_div(Number1, Number2) -> Number1 div Number2.

-spec inf_mult(inf_integer(), inf_integer()) -> inf_integer().

inf_mult(neg_inf, Number) -> 
  Greater = inf_greater_zero(Number), 
  if Greater -> neg_inf;
     true -> pos_inf
  end;
inf_mult(pos_inf, Number) -> 
  Greater = inf_greater_zero(Number),
  if Greater -> pos_inf;
     true -> neg_inf
  end;
inf_mult(Number, pos_inf) -> inf_mult(pos_inf, Number);
inf_mult(Number, neg_inf) -> inf_mult(neg_inf, Number);
inf_mult(Number1, Number2) -> Number1 * Number2.

-spec inf_bsl(inf_integer(), inf_integer()) -> inf_integer().

inf_bsl(pos_inf, _) -> pos_inf;
inf_bsl(neg_inf, _) -> neg_inf;
inf_bsl(Number, pos_inf) when is_integer(Number), Number >= 0 -> pos_inf;
inf_bsl(_, pos_inf) -> neg_inf;
inf_bsl(Number, neg_inf) when is_integer(Number), Number >= 0 -> 0;
inf_bsl(_Number, neg_inf) -> -1;
inf_bsl(Number1, Number2) when is_integer(Number1), is_integer(Number2) ->
  %% We can not shift left with a number which is not a fixnum. We
  %% don't have enough memory.
  Bits = ?BITS,
  if Number2 > (Bits bsl 1) -> inf_bsl(Number1, pos_inf);
     Number2 < (-Bits bsl 1) ->	inf_bsl(Number1, neg_inf);
     true -> Number1 bsl Number2
  end.

%% State

-spec state__init(cfg(), data()) -> #state{}.

state__init(Cfg, {MFA, ArgsFun, CallFun, FinalFun}) ->
  Start = hipe_icode_cfg:start_label(Cfg),  
  Params = hipe_icode_cfg:params(Cfg),
  Ranges = ArgsFun(MFA, Cfg),
  %% io:format("MFA: ~w~nRanges: ~w~n", [MFA, Ranges]),
  Liveness =
    hipe_icode_ssa:ssa_liveness__analyze(hipe_icode_type:unannotate_cfg(Cfg)),
  case lists:any(fun range__is_none/1, Ranges) of
    true -> 
      FinalFun(MFA, [none_type()]),
      throw(no_input);
    false ->
      NewParams = lists:zipwith(fun update_info/2, Params, Ranges),
      NewCfg = hipe_icode_cfg:params_update(Cfg, NewParams),
      Info = enter_defines(NewParams, gb_trees:empty()),
      InfoMap = gb_trees:insert({Start, in}, Info, gb_trees:empty()),
      #state{info_map=InfoMap, cfg=NewCfg, liveness=Liveness,
	     ret_type=none_type(),
	     lookup_fun=CallFun, result_action=FinalFun}
  end.

-spec state__cfg(#state{}) -> cfg().

state__cfg(#state{cfg=Cfg}) ->
  Cfg.

-spec state__bb(#state{}, label()) -> bb().

state__bb(#state{cfg=Cfg}, Label) ->
  BB = hipe_icode_cfg:bb(Cfg, Label),
  true = hipe_bb:is_bb(BB), % Just an assert
  BB.
  
-spec state__bb_add(#state{}, label(), bb()) -> #state{}.

state__bb_add(S=#state{cfg=Cfg}, Label, BB) ->
  NewCfg = hipe_icode_cfg:bb_add(Cfg, Label, BB),
  S#state{cfg=NewCfg}.

state__lookup_fun(#state{lookup_fun=LF}) -> LF.

state__result_action(#state{result_action=RA}) -> RA.

state__ret_type(#state{ret_type=RT}) -> RT.

state__ret_type_update(#state{ret_type=RT} = State, NewType) ->
  TotType = sup(RT, NewType),
  State#state{ret_type=TotType}.

state__info_in(S, Label) ->
  state__info(S, {Label, in}).

state__info(#state{info_map=IM}, Key) ->
  gb_trees:get(Key, IM).

state__update_info(State, LabelInfo, Rewrite) ->
  update_info(LabelInfo, State, [], Rewrite).

update_info([{Label,InfoIn}|Rest], State, LabelAcc, Rewrite) ->
  case state__info_in_update(State, Label, InfoIn) of
    fixpoint ->
      if Rewrite ->
	  update_info(Rest, State, [Label|LabelAcc], Rewrite);
	 true ->
	  update_info(Rest, State, LabelAcc, Rewrite)
      end;
    NewState ->
      update_info(Rest, NewState, [Label|LabelAcc], Rewrite)
  end;
update_info([], State, LabelAcc, _Rewrite) ->
  {State, LabelAcc}.

state__info_in_update(S=#state{info_map=IM,liveness=Liveness}, Label, Info) ->
  LabelIn = {Label, in},
  case gb_trees:lookup(LabelIn, IM) of
    none -> 
      LiveIn = hipe_icode_ssa:ssa_liveness__livein(Liveness, Label),
      NamesLiveIn = [hipe_icode:var_name(Var) || Var <- LiveIn,
						 hipe_icode:is_var(Var)],
      OldInfo = gb_trees:empty(),
      case join_info_in(NamesLiveIn, OldInfo, Info) of
	fixpoint -> 
	  S#state{info_map=gb_trees:insert(LabelIn, OldInfo, IM)};
	NewInfo ->
	  S#state{info_map=gb_trees:enter(LabelIn, NewInfo, IM)}
      end;
    {value, OldInfo} ->
      OldVars = gb_trees:keys(OldInfo),
      case join_info_in(OldVars, OldInfo, Info) of
	fixpoint -> 
	  fixpoint;
	NewInfo ->
	  S#state{info_map=gb_trees:update(LabelIn, NewInfo, IM)}
      end
  end.

join_info_in(Vars, OldInfo, NewInfo) ->
  case join_info_in(Vars, OldInfo, NewInfo, gb_trees:empty(), false) of
    {Res, true} -> Res;
    {_, false} -> fixpoint
  end.
  
join_info_in([Var|Left], Info1, Info2, Acc, Changed) ->
  Type1 = gb_trees:lookup(Var, Info1),
  Type2 = gb_trees:lookup(Var, Info2),
  case {Type1, Type2} of
    {none, none} ->
      NewTree = gb_trees:insert(Var, none_type(), Acc),
      join_info_in(Left, Info1, Info2, NewTree, true);
    {none, {value, Val}} ->
      NewTree = gb_trees:insert(Var, Val, Acc),
      join_info_in(Left, Info1, Info2, NewTree, true);
    {{value, Val}, none} ->
      NewTree = gb_trees:insert(Var, Val, Acc),
      join_info_in(Left, Info1, Info2, NewTree, Changed);
    {{value, Val}, {value, Val}} ->
      NewTree = gb_trees:insert(Var, Val, Acc),
      join_info_in(Left, Info1, Info2, NewTree, Changed);
    {{value, Val1}, {value, Val2}} ->
      NewVal = 
	case sup(Val1, Val2) of
	  Val1 ->
	    NewChanged = Changed,
	    Val1;
	  Val ->
	    NewChanged = true,
	    Val
	end,
      NewTree = gb_trees:insert(Var, NewVal, Acc),
      join_info_in(Left, Info1, Info2, NewTree, NewChanged)
  end;
join_info_in([], _Info1, _Info2, Acc, NewChanged) ->
  {Acc, NewChanged}.

enter_defines([Def|Rest], Info) ->
  enter_defines(Rest, enter_define(Def, Info));
enter_defines([], Info) -> Info.

enter_define({PossibleVar, Range = #range{}}, Info) ->
  case hipe_icode:is_var(PossibleVar) of
    true -> 
      gb_trees:enter(hipe_icode:var_name(PossibleVar), Range, Info);
    false ->
      Info
  end;
enter_define(PossibleVar, Info) ->
  case hipe_icode:is_var(PossibleVar) of
    true -> 
      case hipe_icode:variable_annotation(PossibleVar) of
	{range_anno, #ann{range=Range}, _} ->
	   gb_trees:enter(hipe_icode:var_name(PossibleVar), Range, Info);
	_ ->
	  Info
      end;
    false ->
      Info
  end.

enter_vals(Ins, Info) ->
  NewInfo = enter_defines(hipe_icode:args(Ins), Info),
  enter_defines(hipe_icode:defines(Ins), NewInfo).

lookup(PossibleVar, Info) ->
  case hipe_icode:is_var(PossibleVar) of
    true -> 
      case gb_trees:lookup(hipe_icode:var_name(PossibleVar), Info) of
	none ->
	  none_type();
	{value, Val} ->
	  Val
      end;
    false ->
      none_type()
  end.

%% _________________________________________________________________
%%
%% The worklist.
%%

init_work(State) ->
  %% Labels = hipe_icode_cfg:reverse_postorder(state__cfg(State)),
  Labels = [hipe_icode_cfg:start_label(state__cfg(State))],
  {Labels, [], sets:from_list(Labels)}.

get_work({[Label|Left], List, Set}) ->
  NewWork = {Left, List, sets:del_element(Label, Set)},
  {Label, NewWork};
get_work({[], [], _Set}) ->
  fixpoint;
get_work({[], List, Set}) ->
  get_work({lists:reverse(List), [], Set}).

add_work(Work = {List1, List2, Set}, [Label|Left]) ->
  case sets:is_element(Label, Set) of
    true ->
      add_work(Work, Left);
    false ->
      %% io:format("Adding work: ~w\n", [Label]),
      add_work({List1, [Label|List2], sets:add_element(Label, Set)}, Left)
  end;
add_work(Work, []) ->
  Work.

convert_cfg_to_types(Cfg) ->
  Lbls = hipe_icode_cfg:reverse_postorder(Cfg),
  lists:foldl(fun convert_lbl_to_type/2, Cfg, Lbls).

convert_lbl_to_type(Lbl, Cfg) ->
  BB = hipe_icode_cfg:bb(Cfg, Lbl),
  Code = hipe_bb:code(BB),
  NewCode = [convert_instr_to_type(I) || I <- Code],
  hipe_icode_cfg:bb_add(Cfg, Lbl, hipe_bb:mk_bb(NewCode)).

convert_instr_to_type(I) ->
  Uses = hipe_icode:uses(I),
  UseSubstList = [{Use, convert_to_types(Use)} ||
		   Use <- Uses, hipe_icode:is_annotated_variable(Use)],
  NewI = hipe_icode:subst_uses(UseSubstList, I),
  Defs = hipe_icode:defines(NewI),
  DefSubstList = [{Def, convert_to_types(Def)} ||
		   Def <- Defs, hipe_icode:is_annotated_variable(Def)],
  hipe_icode:subst_defines(DefSubstList, NewI).

convert_to_types(VarOrReg) ->
 Annotation = 
    case hipe_icode:variable_annotation(VarOrReg) of
      {range_anno, Ann, _} ->
	{type_anno, convert_ann_to_types(Ann), fun erl_types:t_to_string/1};
      {type_anno, _, _} = TypeAnn ->
	TypeAnn
    end,
  hipe_icode:annotate_variable(VarOrReg, Annotation).

convert_ann_to_types(#ann{range=#range{range={Min,Max}, other=false}}) ->
  t_from_range_unsafe(Min, Max);
convert_ann_to_types(#ann{range=#range{range=empty, other=false}}) ->
  t_none();
convert_ann_to_types(#ann{range=#range{other=true}, type=Type}) ->
  Type.

%%=====================================================================
%% Icode Coordinator Callbacks
%%=====================================================================

-spec replace_nones([range()]) -> [range()].
replace_nones(Args) ->
  [replace_none(Arg) || Arg <- Args].

replace_none(Arg) ->
  case range__is_none(Arg) of
    true -> any_type();
    false -> Arg
  end.

-spec update__info([range()], [range()]) -> {boolean(), [ann()]}.
update__info(NewRanges, OldRanges) ->
  SupFun = fun (Ann, Range) -> 
	       join_info(Ann, Range, fun safe_widen/3)
	   end,
  EqFun = fun (X, Y) -> X =:= Y end,
  ResRanges = lists:zipwith(SupFun, OldRanges, NewRanges),
  Change = lists:zipwith(EqFun, ResRanges, OldRanges),
  {lists:all(fun (X) -> X end, Change), ResRanges}.

-spec new__info([range()]) -> [ann()].
new__info(NewRanges) ->
  [#ann{range=Range,count=1,type=t_any()} || Range <- NewRanges].

-spec return__info([ann()]) -> [range()].
return__info(Ranges) ->
  [Range || #ann{range=Range} <- Ranges].

-spec return_none() -> [range(),...].
return_none() ->
  [none_type()].

-spec return_none_args(cfg(), mfa()) -> [range()].
return_none_args(Cfg, {_M,_F,A}) ->
  NoArgs =
    case hipe_icode_cfg:is_closure(Cfg) of
      true -> hipe_icode_cfg:closure_arity(Cfg) + 1;
      false -> A
    end,
  lists:duplicate(NoArgs, none_type()).

-spec return_any_args(cfg(), mfa()) -> [range()].
return_any_args(Cfg, {_M,_F,A}) ->
  NoArgs = 
    case hipe_icode_cfg:is_closure(Cfg) of
      true -> hipe_icode_cfg:closure_arity(Cfg) + 1;
      false -> A
    end,
  lists:duplicate(NoArgs, any_type()).

%%=====================================================================

next_up_limit(X) when is_integer(X), X < 0 -> 0;
next_up_limit(X) when is_integer(X), X < 255 -> 255;
next_up_limit(X) when is_integer(X), X < 16#10ffff -> 16#10ffff;
next_up_limit(X) when is_integer(X), X < 16#7ffffff -> 16#7ffffff;
next_up_limit(X) when is_integer(X), X < 16#7fffffff -> 16#7fffffff;
next_up_limit(X) when is_integer(X), X < 16#ffffffff -> 16#ffffffff;
next_up_limit(X) when is_integer(X), X < 16#fffffffffff -> 16#fffffffffff;
next_up_limit(X) when is_integer(X), X < 16#7fffffffffffffff -> 16#7fffffffffffffff;
next_up_limit(_X) -> pos_inf.

next_down_limit(X) when is_integer(X), X > 0 -> 0;
next_down_limit(X) when is_integer(X), X > -256 -> -256;
next_down_limit(X) when is_integer(X), X > -16#10ffff -> -16#10ffff;
next_down_limit(X) when is_integer(X), X > -16#8000000 -> -16#8000000;
next_down_limit(X) when is_integer(X), X > -16#80000000 -> -16#80000000;
next_down_limit(X) when is_integer(X), X > -16#800000000000000 -> -16#800000000000000;
next_down_limit(_X) -> neg_inf.