Refactor string operands

There are two instructions that take string operands:

     {bs_put_string,Fail,NumberOfBytes,{string,String}}
     {bs_match_string,Fail,Register,NumberOfBits,{string,String}}

In the canonical BEAM code that is passed to beam_asm, string String
is currently represented as a list. (The string in bs_match_string is
a bitstring before the beam_z compiler pass.) That is wasteful,
because there will be unnecessary conversions between lists and
binaries.

Change the representation of String to be a binary.

Furthermore, bs_put_string is an optimization of a bs_put_binary
instruction with a literal binary operand. Currently, the
bs_put_string instruction is introduced in beam_bs. Delay the
introduction of bs_put_string to the beam_z pass. That will simplify
optimizations and allow us to do the optimization currently done
in beam_bs in a SSA pass in a future commit.

5 files changed, 56 insertions, 24 deletions

diff --git a/lib/compiler/src/beam_a.erl b/lib/compiler/src/beam_a.erl
index dd2537a699..1ac892a8f1 100644
--- a/lib/compiler/src/beam_a.erl
+++ b/lib/compiler/src/beam_a.erl
@@ -100,8 +100,12 @@ rename_instr({bs_put_utf16=I,F,Fl,Src}) ->
     {bs_put,F,{I,Fl},[Src]};
 rename_instr({bs_put_utf32=I,F,Fl,Src}) ->
     {bs_put,F,{I,Fl},[Src]};
-rename_instr({bs_put_string,_,_}=I) ->
-    {bs_put,{f,0},I,[]};
+rename_instr({bs_put_string,_,{string,String}}) ->
+    %% Only happens when compiling from .S files. In old
+    %% .S files, String is a list. In .S in OTP 22 and later,
+    %% String is a binary.
+    {bs_put,{f,0},{bs_put_binary,8,{field_flags,[unsigned,big]}},
+     [{atom,all},{literal,iolist_to_binary([String])}]};
 rename_instr({bs_add=I,F,[Src1,Src2,U],Dst}) when is_integer(U) ->
     {bif,I,F,[Src1,Src2,{integer,U}],Dst};
 rename_instr({bs_utf8_size=I,F,Src,Dst}) ->
@@ -118,8 +122,8 @@ rename_instr({bs_private_append=I,F,Sz,U,Src,Flags,Dst}) ->
     {bs_init,F,{I,U,Flags},none,[Sz,Src],Dst};
 rename_instr(bs_init_writable=I) ->
     {bs_init,{f,0},I,1,[{x,0}],{x,0}};
-rename_instr({test,Op,F,[Ctx,Bits,{string,Str}]}) ->
-    %% When compiling from a .S file.
+rename_instr({test,bs_match_string=Op,F,[Ctx,Bits,{string,Str}]}) when is_list(Str) ->
+    %% When compiling from an old .S file. Starting from OTP 22, Str is a binary.
     <<Bs:Bits/bits,_/bits>> = list_to_binary(Str),
     {test,Op,F,[Ctx,Bs]};
 rename_instr({put_map_assoc,Fail,S,D,R,L}) ->
diff --git a/lib/compiler/src/beam_asm.erl b/lib/compiler/src/beam_asm.erl
index df0321e85a..bc1290f6fd 100644
--- a/lib/compiler/src/beam_asm.erl
+++ b/lib/compiler/src/beam_asm.erl
@@ -424,8 +424,8 @@ encode_arg({f, W}, Dict) ->
     {encode(?tag_f, W), Dict};
 %% encode_arg({'char', C}, Dict) ->
 %%     {encode(?tag_h, C), Dict};
-encode_arg({string, String}, Dict0) ->
-    {Offset, Dict} = beam_dict:string(String, Dict0),
+encode_arg({string, BinString}, Dict0) when is_binary(BinString) ->
+    {Offset, Dict} = beam_dict:string(BinString, Dict0),
     {encode(?tag_u, Offset), Dict};
 encode_arg({extfunc, M, F, A}, Dict0) ->
     {Index, Dict} = beam_dict:import(M, F, A, Dict0),
diff --git a/lib/compiler/src/beam_bs.erl b/lib/compiler/src/beam_bs.erl
index eea0cfcd02..9cf12be1b6 100644
--- a/lib/compiler/src/beam_bs.erl
+++ b/lib/compiler/src/beam_bs.erl
@@ -117,17 +117,23 @@ eval_put_float(Src, Sz, Flags) when Sz =< 256 ->
 value({integer,I}) -> I;
 value({float,F}) -> F.
 
-bs_collect_string(Is, [{bs_put,_,{bs_put_string,Len,{string,Str}},[]}|Acc]) ->
-    bs_coll_str_1(Is, Len, reverse(Str), Acc);
+bs_collect_string(Is, [{bs_put,_,{bs_put_binary,1,_},
+                        [{atom,all},{literal,BinString}]}|Acc]) ->
+    bs_coll_str_1(Is, BinString, Acc);
 bs_collect_string(Is, Acc) ->
-    bs_coll_str_1(Is, 0, [], Acc).
+    bs_coll_str_1(Is, <<>>, Acc).
 
+bs_coll_str_1([{bs_put,_,{bs_put_binary,1,_},
+                [{atom,all},{literal,BinString}]}|Is],
+              StrAcc, IsAcc) when is_binary(BinString) ->
+    bs_coll_str_1(Is, <<StrAcc/binary,BinString/binary>>, IsAcc);
 bs_coll_str_1([{bs_put,_,{bs_put_integer,U,_},[{integer,Sz},{integer,V}]}|Is],
-	      Len, StrAcc, IsAcc) when U*Sz =:= 8 ->
+	      StrAcc, IsAcc) when U*Sz =:= 8 ->
     Byte = V band 16#FF,
-    bs_coll_str_1(Is, Len+1, [Byte|StrAcc], IsAcc);
-bs_coll_str_1(Is, Len, StrAcc, IsAcc) ->
-    {Is,[{bs_put,{f,0},{bs_put_string,Len,{string,reverse(StrAcc)}},[]}|IsAcc]}.
+    bs_coll_str_1(Is, <<StrAcc/binary,Byte>>, IsAcc);
+bs_coll_str_1(Is, StrAcc, IsAcc) ->
+    {Is,[{bs_put,{f,0},{bs_put_binary,1,{field_flags,[unsigned,big]}},
+          [{atom,all},{literal,StrAcc}]}|IsAcc]}.
 
 field_endian({field_flags,F}) -> field_endian_1(F).
 
diff --git a/lib/compiler/src/beam_dict.erl b/lib/compiler/src/beam_dict.erl
index 990e86062a..b2056332e6 100644
--- a/lib/compiler/src/beam_dict.erl
+++ b/lib/compiler/src/beam_dict.erl
@@ -126,18 +126,17 @@ import(Mod0, Name0, Arity, #asm{imports=Imp0,next_import=NextIndex}=D0)
 	    {NextIndex,D2#asm{imports=Imp,next_import=NextIndex+1}}
     end.
 
-%% Returns the index for a string in the string table (adding the string to the
-%% table if necessary).
+%% Returns the index for a binary string in the string table (adding
+%% the string to the table if necessary).
 %%    string(String, Dict) -> {Offset, Dict'}
--spec string(string(), bdict()) -> {non_neg_integer(), bdict()}.
+-spec string(binary(), bdict()) -> {non_neg_integer(), bdict()}.
 
-string(Str, Dict) when is_list(Str) ->
+string(BinString, Dict) when is_binary(BinString) ->
     #asm{strings=Strings,string_offset=NextOffset} = Dict,
-    StrBin = list_to_binary(Str),
-    case old_string(StrBin, Strings) of
+    case old_string(BinString, Strings) of
 	none ->
-	    NewDict = Dict#asm{strings = <<Strings/binary,StrBin/binary>>,
-			       string_offset=NextOffset+byte_size(StrBin)},
+	    NewDict = Dict#asm{strings = <<Strings/binary,BinString/binary>>,
+			       string_offset=NextOffset+byte_size(BinString)},
 	    {NextOffset,NewDict};
 	Offset when is_integer(Offset) ->
 	    {NextOffset-Offset,Dict}
diff --git a/lib/compiler/src/beam_z.erl b/lib/compiler/src/beam_z.erl
index 677094b3cd..415b579240 100644
--- a/lib/compiler/src/beam_z.erl
+++ b/lib/compiler/src/beam_z.erl
@@ -71,6 +71,31 @@ undo_renames([{get_hd,Src,Dst1},{get_tl,Src,Dst2}|Is]) ->
     [{get_list,Src,Dst1,Dst2}|undo_renames(Is)];
 undo_renames([{get_tl,Src,Dst2},{get_hd,Src,Dst1}|Is]) ->
     [{get_list,Src,Dst1,Dst2}|undo_renames(Is)];
+undo_renames([{bs_put,_,{bs_put_binary,1,_},
+               [{atom,all},{literal,<<>>}]}|Is]) ->
+    undo_renames(Is);
+undo_renames([{bs_put,Fail,{bs_put_binary,1,_Flags},
+               [{atom,all},{literal,BinString}]}|Is0]) ->
+    Bits = bit_size(BinString),
+    Bytes = Bits div 8,
+    case Bits rem 8 of
+        0 ->
+            I = {bs_put_string,byte_size(BinString),
+                 {string,BinString}},
+            [undo_rename(I)|undo_renames(Is0)];
+        Rem ->
+            <<Binary:Bytes/bytes,Int:Rem>> = BinString,
+            PutInt = {bs_put_integer,Fail,{integer,Rem},1,
+                      {field_flags,[unsigned,big]},{integer,Int}},
+            Is = [PutInt|undo_renames(Is0)],
+            case Binary of
+                <<>> ->
+                    Is;
+                _ ->
+                    [{bs_put_string,byte_size(Binary),
+                      {string,Binary}}|Is]
+            end
+    end;
 undo_renames([I|Is]) ->
     [undo_rename(I)|undo_renames(Is)];
 undo_renames([]) -> [].
@@ -79,8 +104,6 @@ undo_rename({bs_put,F,{I,U,Fl},[Sz,Src]}) ->
     {I,F,Sz,U,Fl,Src};
 undo_rename({bs_put,F,{I,Fl},[Src]}) ->
     {I,F,Fl,Src};
-undo_rename({bs_put,{f,0},{bs_put_string,_,_}=I,[]}) ->
-    I;
 undo_rename({bif,bs_add=I,F,[Src1,Src2,{integer,U}],Dst}) ->
     {I,F,[Src1,Src2,U],Dst};
 undo_rename({bif,bs_utf8_size=I,F,[Src],Dst}) ->
@@ -101,7 +124,7 @@ undo_rename({test,bs_match_string=Op,F,[Ctx,Bin0]}) ->
 	      0 -> Bin0;
 	      Rem -> <<Bin0/bitstring,0:(8-Rem)>>
 	  end,
-    {test,Op,F,[Ctx,Bits,{string,binary_to_list(Bin)}]};
+    {test,Op,F,[Ctx,Bits,{string,Bin}]};
 undo_rename({put_map,Fail,assoc,S,D,R,L}) ->
     {put_map_assoc,Fail,S,D,R,L};
 undo_rename({put_map,Fail,exact,S,D,R,L}) ->