Extend RTL API to support the LLVM backend

Extend the 'rtl_var' definition to host liveness information needed for
a simple liveness analysis performed by the LLVM backend.

Also, uncomment some function definitions (mostly simple accessors) that
are already there and are useful for the translation of RTL code to LLVM
assembly.

Finally, extend the RTL 'call' instruction with the 'normalcontinuation'
field which is required for translating calls that are in the scope of
an exception handler. This extra field is required in order to point to
a new basic block which will hold the 'unwind label' of LLVM's invoke
instruction. While the 'unwind label' is semantically equivalent with
the 'failcontinuation', in LLVM this block must have a 'landingpad'
instruction. The problem arises by the fact that an RTL 'continuation'
block can also be accessible by other paths in the RTL CFG, and so
cannot be marked as a landing pad. To overcome this issue we create a
new block (the 'normalcontinuation') which is used as the 'unwind label'
of LLVM's invoke instruction and which will eventually transfer control
to the 'continuation' block.

3 files changed, 170 insertions, 10 deletions

diff --git a/lib/hipe/rtl/hipe_rtl.erl b/lib/hipe/rtl/hipe_rtl.erl
index 4bf4eb6bd7..bc61bec0bd 100644
--- a/lib/hipe/rtl/hipe_rtl.erl
+++ b/lib/hipe/rtl/hipe_rtl.erl
@@ -29,7 +29,7 @@
 %%   <li> {alu, Dst, Src1, Op, Src2} </li>
 %%   <li> {alub, Dst, Src1, Op, Src2, RelOp, TrueLabel, FalseLabel, P} </li>
 %%   <li> {branch, Src1, Src2, RelOp, TrueLabel, FalseLabel, P} </li>
-%%   <li> {call, DsListt, Fun, ArgList, Type, Continuation, FailContinuation}
+%%   <li> {call, DsListt, Fun, ArgList, Type, Continuation, FailContinuation, NormalContinuation}
 %%           Type is one of {local, remote, primop, closure} </li>
 %%   <li> {comment, Text} </li>
 %%   <li> {enter, Fun, ArgList, Type}
@@ -106,7 +106,7 @@
 	 %% rtl_data_update/2,
 	 %% rtl_var_range/1,
 	 %% rtl_var_range_update/2,
-	 %% rtl_label_range/1,
+	 rtl_label_range/1,
 	 %% rtl_label_range_update/2,
 	 rtl_info/1,
 	 rtl_info_update/2]).
@@ -226,6 +226,7 @@
 	 %% goto_label_update/2,
 
 	 mk_call/6,
+	 mk_call/7,
 	 call_fun/1,
 	 call_dstlist/1,
 	 call_dstlist_update/2,
@@ -233,8 +234,10 @@
 	 call_continuation/1,
 	 call_fail/1,
 	 call_type/1,
+	 call_normal/1,
+	 call_normal_update/2,
 	 %% call_continuation_update/2,
-	 %% call_fail_update/2,
+	 call_fail_update/2,
 	 is_call/1,
 
 	 mk_enter/3,
@@ -290,10 +293,13 @@
 	 %% fconv_src_update/2,
 	 %% is_fconv/1,
 
-	 %% mk_var/1,
+	 mk_var/1,
+	 mk_var/2,
 	 mk_new_var/0,
 	 is_var/1,
 	 var_index/1,
+	 var_liveness/1,
+	 var_liveness_update/2,
 
 	 %% change_vars_to_regs/1,
 	 
@@ -350,10 +356,15 @@
 	 %% move_dst_update/2,
 	 fixnumop_dst_update/2,
 	 pp_instr/2,
-         %% pp_arg/2,
+	 %% Uber hack!
+	 pp_var/2,
+	 pp_reg/2,
+	 pp_arg/2,
          phi_arglist_update/2,
          phi_redirect_pred/3]).
 
+-export([subst_uses_llvm/2]).
+
 -export_type([alub_cond/0]).
 
 %%
@@ -387,7 +398,7 @@ rtl_data(#rtl{data=Data}) -> Data.
 %% rtl_data_update(Rtl, Data) -> Rtl#rtl{data=Data}.
 %% rtl_var_range(#rtl{var_range=VarRange}) -> VarRange.
 %% rtl_var_range_update(Rtl, VarRange) -> Rtl#rtl{var_range=VarRange}.
-%% rtl_label_range(#rtl{label_range=LabelRange}) -> LabelRange.
+rtl_label_range(#rtl{label_range=LabelRange}) -> LabelRange.
 %% rtl_label_range_update(Rtl, LabelRange) -> Rtl#rtl{label_range=LabelRange}.
 rtl_info(#rtl{info=Info}) -> Info.
 rtl_info_update(Rtl, Info) -> Rtl#rtl{info=Info}.
@@ -643,6 +654,17 @@ is_goto(_) -> false.
 %% call
 %%
 
+%% LLVM: Call with normal continuation
+mk_call(DstList, Fun, ArgList, Continuation, FailContinuation,
+    NormalContinuation, Type) ->
+  case Type of
+    remote -> ok;
+    not_remote -> ok
+  end,
+  #call{dstlist=DstList, 'fun'=Fun, arglist=ArgList, type=Type,
+    continuation=Continuation, failcontinuation=FailContinuation,
+    normalcontinuation=NormalContinuation}.
+
 mk_call(DstList, Fun, ArgList, Continuation, FailContinuation, Type) ->
   case Type of
     remote -> ok;
@@ -651,6 +673,10 @@ mk_call(DstList, Fun, ArgList, Continuation, FailContinuation, Type) ->
   #call{dstlist=DstList, 'fun'=Fun, arglist=ArgList, type=Type,
 	continuation=Continuation,
 	failcontinuation=FailContinuation}.
+
+call_normal(#call{normalcontinuation=NormalContinuation}) -> NormalContinuation.
+call_normal_update(C, NewNormalContinuation) ->
+  C#call{normalcontinuation=NewNormalContinuation}.
 call_dstlist(#call{dstlist=DstList}) -> DstList.
 call_dstlist_update(C, NewDstList) -> C#call{dstlist=NewDstList}.
 call_fun(#call{'fun'=Fun}) -> Fun.
@@ -853,11 +879,14 @@ reg_is_gcsafe(#rtl_reg{is_gc_safe=IsGcSafe}) -> IsGcSafe.
 is_reg(#rtl_reg{}) -> true;
 is_reg(_) -> false.
 
--record(rtl_var, {index :: non_neg_integer()}).
+-record(rtl_var, {index :: non_neg_integer(), liveness=live :: dead | live}).
 
 mk_var(Num) when is_integer(Num), Num >= 0 -> #rtl_var{index=Num}.
+mk_var(Num, Liveness) when is_integer(Num), Num>=0 -> #rtl_var{index=Num, liveness=Liveness}.
 mk_new_var() -> mk_var(hipe_gensym:get_next_var(rtl)).
 var_index(#rtl_var{index=Index}) -> Index.
+var_liveness(#rtl_var{liveness=Liveness}) -> Liveness.
+var_liveness_update(RtlVar, Liveness) -> RtlVar#rtl_var{liveness=Liveness}.
 is_var(#rtl_var{}) -> true;
 is_var(_) -> false.
 
@@ -1077,6 +1106,131 @@ subst_uses(Subst, I) ->
       switch_src_update(I, subst1(Subst, switch_src(I)))
   end.
 
+subst_uses_llvm(Subst, I) ->
+  case I of
+    #alu{} ->
+      {NewSrc2, Subst1} = subst1_llvm(Subst, alu_src2(I)),
+      {NewSrc1, _ } = subst1_llvm(Subst1, alu_src1(I)),
+      I0 =  alu_src1_update(I, NewSrc1),
+      alu_src2_update(I0, NewSrc2);
+    #alub{} ->
+      {NewSrc2, Subst1} = subst1_llvm(Subst, alub_src2(I)),
+      {NewSrc1, _ } = subst1_llvm(Subst1, alub_src1(I)),
+      I0 =  alub_src1_update(I, NewSrc1),
+      alub_src2_update(I0, NewSrc2);
+    #branch{} ->
+      {NewSrc2, Subst1} = subst1_llvm(Subst, branch_src2(I)),
+      {NewSrc1, _ } = subst1_llvm(Subst1, branch_src1(I)),
+      I0 = branch_src1_update(I, NewSrc1),
+      branch_src2_update(I0, NewSrc2);
+    #call{} ->
+      case call_is_known(I) of
+        false ->
+          {NewFun, Subst1} = subst1_llvm(Subst, call_fun(I)),
+          {NewArgList, _} = subst_list_llvm(Subst1, call_arglist(I)),
+          I0 = call_fun_update(I, NewFun),
+          call_arglist_update(I0, NewArgList);
+        true ->
+          {NewArgList, _} = subst_list_llvm(Subst, call_arglist(I)),
+          call_arglist_update(I, NewArgList)
+      end;
+    #comment{} ->
+      I;
+    #enter{} ->
+      case enter_is_known(I) of
+        false ->
+          {NewFun, Subst1} = subst1_llvm(Subst, enter_fun(I)),
+          {NewArgList, _} = subst_list_llvm(Subst1, enter_arglist(I)),
+          I0 = enter_fun_update(I, NewFun),
+          enter_arglist_update(I0, NewArgList);
+        true ->
+          {NewArgList, _} = subst_list_llvm(Subst, enter_arglist(I)),
+          enter_arglist_update(I, NewArgList)
+      end;
+    #fconv{} ->
+      {NewSrc, _ } = subst1_llvm(Subst, fconv_src(I)),
+      fconv_src_update(I, NewSrc);
+    #fixnumop{} ->
+      {NewSrc, _ } = subst1_llvm(Subst, fixnumop_src(I)),
+      fixnumop_src_update(I, NewSrc);
+    #fload{} ->
+      {NewSrc, Subst1} = subst1_llvm(Subst, fload_src(I)),
+      {NewOffset, _ } = subst1_llvm(Subst1, fload_offset(I)),
+      I0 = fload_src_update(I, NewSrc),
+      fload_offset_update(I0, NewOffset);
+    #fmove{} ->
+      {NewSrc, _ } = subst1_llvm(Subst, fmove_src(I)),
+      fmove_src_update(I, NewSrc);
+    #fp{} ->
+      {NewSrc2, Subst1} = subst1_llvm(Subst, fp_src2(I)),
+      {NewSrc1, _ } = subst1_llvm(Subst1, fp_src1(I)),
+      I0 = fp_src1_update(I, NewSrc1),
+      fp_src2_update(I0, NewSrc2);
+    #fp_unop{} ->
+      {NewSrc, _ } = subst1_llvm(Subst, fp_unop_src(I)),
+      fp_unop_src_update(I, NewSrc);
+    #fstore{} ->
+      {NewSrc, Subst1} = subst1_llvm(Subst, fstore_src(I)),
+      {NewBase, Subst2} = subst1_llvm(Subst1, fstore_base(I)),
+      {NewOffset, _ } = subst1_llvm(Subst2, fstore_offset(I)),
+      I0 = fstore_src_update(I, NewSrc),
+      I1 = fstore_base_update(I0, NewBase),
+      fstore_offset_update(I1, NewOffset);
+    #goto{} ->
+      I;
+    #goto_index{} ->
+      I;
+    #gctest{} ->
+      {NewWords, _ } = subst1_llvm(Subst, gctest_words(I)),
+      gctest_words_update(I, NewWords);
+    #label{} ->
+      I;
+    #load{} ->
+      {NewSrc, Subst1} = subst1_llvm(Subst, load_src(I)),
+      {NewOffset, _ } = subst1_llvm(Subst1, load_offset(I)),
+      I0 = load_src_update(I, NewSrc),
+      load_offset_update(I0, NewOffset);
+    #load_address{} ->
+      I;
+    #load_atom{} ->
+      I;
+    #load_word_index{} ->
+      I;
+    #move{} ->
+      {NewSrc, _ } = subst1_llvm(Subst, move_src(I)),
+      move_src_update(I, NewSrc);
+    #multimove{} ->
+      {NewSrcList, _} = subst_list_llvm(Subst, multimove_srclist(I)),
+      multimove_srclist_update(I, NewSrcList);
+    #phi{} ->
+      phi_argvar_subst(I, Subst);
+    #return{} ->
+      {NewVarList, _} = subst_list_llvm(Subst, return_varlist(I)),
+      return_varlist_update(I, NewVarList);
+    #store{} ->
+      {NewSrc, Subst1} = subst1_llvm(Subst, store_src(I)),
+      {NewBase, Subst2} = subst1_llvm(Subst1, store_base(I)),
+      {NewOffset, _ } = subst1_llvm(Subst2, store_offset(I)),
+      I0 = store_src_update(I, NewSrc),
+      I1 = store_base_update(I0, NewBase),
+      store_offset_update(I1, NewOffset);
+    #switch{} ->
+      {NewSrc, _ } = subst1_llvm(Subst, switch_src(I)),
+      switch_src_update(I, NewSrc)
+  end.
+
+subst_list_llvm(S,X) -> subst_list_llvm(S, lists:reverse(X), []).
+subst_list_llvm(S, [], Acc) -> {Acc, S};
+subst_list_llvm(S, [X|Xs], Acc) ->
+  {NewX, RestS} = subst1_llvm(S, X),
+  subst_list_llvm(RestS, Xs, [NewX|Acc]).
+
+subst1_llvm(A,B) -> subst1_llvm(A,B,[]).
+
+subst1_llvm([], X, Acc) -> {X, Acc};
+subst1_llvm([{X,Y}|Rs], X, Acc) -> {Y, Acc++Rs};
+subst1_llvm([R|Xs], X, Acc) -> subst1_llvm(Xs,X,[R|Acc]).
+
 subst_defines(Subst, I)->
   case I of
     #alu{} ->
@@ -1614,7 +1768,11 @@ pp_var(Dev, Arg) ->
     true ->
       pp_hard_reg(Dev, var_index(Arg));
     false ->
-      io:format(Dev, "v~w", [var_index(Arg)])
+      io:format(Dev, "v~w", [var_index(Arg)]),
+      case var_liveness(Arg) of
+        dead -> io:format(Dev, "(dead)", []);
+        _ -> ok
+      end
   end.
 
 pp_arg(Dev, A) ->
diff --git a/lib/hipe/rtl/hipe_rtl.hrl b/lib/hipe/rtl/hipe_rtl.hrl
index 974e40f830..fbdf9ac524 100644
--- a/lib/hipe/rtl/hipe_rtl.hrl
+++ b/lib/hipe/rtl/hipe_rtl.hrl
@@ -28,7 +28,8 @@
 -record(alu, {dst, src1, op, src2}).
 -record(alub, {dst, src1, op, src2, 'cond', true_label, false_label, p}).
 -record(branch, {src1, src2, 'cond', true_label, false_label, p}).
--record(call, {dstlist, 'fun', arglist, type, continuation, failcontinuation}).
+-record(call, {dstlist, 'fun', arglist, type, continuation,
+    failcontinuation, normalcontinuation = []}).
 -record(comment, {text}).
 -record(enter, {'fun', arglist, type}).
 -record(fconv, {dst, src}).
diff --git a/lib/hipe/rtl/hipe_rtl_liveness.erl b/lib/hipe/rtl/hipe_rtl_liveness.erl
index 3cfada9d6c..0c4b6b2e11 100644
--- a/lib/hipe/rtl/hipe_rtl_liveness.erl
+++ b/lib/hipe/rtl/hipe_rtl_liveness.erl
@@ -34,7 +34,8 @@
 
 -module(hipe_rtl_liveness).
 
-%% -define(LIVEOUT_NEEDED,true).	% needed for liveness.inc below.
+%% -define(DEBUG_LIVENESS,true).
+-define(LIVEOUT_NEEDED,true).	% needed for liveness.inc below.
 -define(PRETTY_PRINT,false).
 
 -include("hipe_rtl.hrl").