1%% 2%% %CopyrightBegin% 3%% 4%% Copyright Ericsson AB 2007-2018. All Rights Reserved. 5%% 6%% Licensed under the Apache License, Version 2.0 (the "License"); 7%% you may not use this file except in compliance with the License. 8%% You may obtain a copy of the License at 9%% 10%% http://www.apache.org/licenses/LICENSE-2.0 11%% 12%% Unless required by applicable law or agreed to in writing, software 13%% distributed under the License is distributed on an "AS IS" BASIS, 14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15%% See the License for the specific language governing permissions and 16%% limitations under the License. 17%% 18%% %CopyrightEnd% 19%% 20 21-module(beam_bsm). 22-export([module/2,format_error/1]). 23 24-import(lists, [member/2,foldl/3,reverse/1,sort/1,all/2]). 25 26%%% 27%%% We optimize bit syntax matching where the tail end of a binary is 28%%% matched out and immediately passed on to a bs_start_match2 instruction, 29%%% such as in this code sequence: 30%%% 31%%% func_info ... 32%%% L1 test bs_start_match2 {f,...} {x,0} Live SavePositions {x,0} 33%%% . . . 34%%% test bs_get_binary2 {f,...} {x,0} all 1 Flags {x,0} 35%%% . . . 36%%% call_only 2 L1 37%%% 38%%% The sequence can be optimized simply by removing the bs_get_binary2 39%%% instruction. Another example: 40%%% 41%%% func_info ... 42%%% L1 test bs_start_match2 {f,...} {x,0} Live SavePositions {x,0} 43%%% . . . 44%%% test bs_get_binary2 {f,...} {x,0} all 8 Flags {x,1} 45%%% . . . 46%%% move {x,1} {x,0} 47%%% call_only 2 L1 48%%% 49%%% In this case, the bs_get_binary2 instruction must be replaced by 50%%% 51%%% test bs_unit {x,1} 8 52%%% 53%%% to ensure that the match fail if the length of the binary in bits 54%%% is not evenly divisible by 8. 55%%% 56%%% Note that the bs_start_match2 instruction doesn't need to be in the same 57%%% function as the caller. It can be in the beginning of any function, or 58%%% follow the bs_get_binary2 instruction in the same function. The important 59%%% thing is that the match context register is not copied or built into 60%%% data structures or passed to BIFs. 61%%% 62 63-type label() :: beam_asm:label(). 64-type func_info() :: {beam_asm:reg(),boolean()}. 65 66-record(btb, 67 {f :: gb_trees:tree(label(), func_info()), 68 index :: beam_utils:code_index(), %{Label,Code} index (for liveness). 69 ok_br=gb_sets:empty() :: gb_sets:set(label()), %Labels that are OK. 70 must_not_save=false :: boolean(), %Must not save position when 71 % optimizing (reaches 72 % bs_context_to_binary). 73 must_save=false :: boolean() %Must save position when optimizing. 74 }). 75 76 77-spec module(beam_utils:module_code(), [compile:option()]) -> 78 {'ok',beam_utils:module_code()}. 79 80module({Mod,Exp,Attr,Fs0,Lc}, Opts) -> 81 FIndex = btb_index(Fs0), 82 Fs = [function(F, FIndex) || F <- Fs0], 83 Code = {Mod,Exp,Attr,Fs,Lc}, 84 case proplists:get_bool(bin_opt_info, Opts) of 85 true -> 86 {ok,Code,collect_warnings(Fs)}; 87 false -> 88 {ok,Code} 89 end. 90 91-spec format_error('bin_opt' | {'no_bin_opt', term()}) -> nonempty_string(). 92 93format_error(bin_opt) -> 94 "OPTIMIZED: creation of sub binary delayed"; 95format_error({no_bin_opt,Reason}) -> 96 lists:flatten(["NOT OPTIMIZED: "|format_error_1(Reason)]). 97 98%%% 99%%% Local functions. 100%%% 101 102function({function,Name,Arity,Entry,Is}, FIndex) -> 103 try 104 Index = beam_utils:index_labels(Is), 105 D = #btb{f=FIndex,index=Index}, 106 {function,Name,Arity,Entry,btb_opt_1(Is, D, [])} 107 catch 108 Class:Error:Stack -> 109 io:fwrite("Function: ~w/~w\n", [Name,Arity]), 110 erlang:raise(Class, Error, Stack) 111 end. 112 113btb_opt_1([{test,bs_get_binary2,F,_,[Reg,{atom,all},U,Fs],Reg}=I0|Is], D, Acc0) -> 114 case btb_reaches_match(Is, [Reg], D) of 115 {error,Reason} -> 116 Comment = btb_comment_no_opt(Reason, Fs), 117 btb_opt_1(Is, D, [Comment,I0|Acc0]); 118 {ok,MustSave} -> 119 Comment = btb_comment_opt(Fs), 120 Acc1 = btb_gen_save(MustSave, Reg, [Comment|Acc0]), 121 Acc = case U of 122 1 -> Acc1; 123 _ -> [{test,bs_test_unit,F,[Reg,U]}|Acc1] 124 end, 125 btb_opt_1(Is, D, Acc) 126 end; 127btb_opt_1([{test,bs_get_binary2,F,_,[Ctx,{atom,all},U,Fs],Dst}=I0|Is0], D, Acc0) -> 128 case btb_reaches_match(Is0, [Ctx,Dst], D) of 129 {error,Reason} -> 130 Comment = btb_comment_no_opt(Reason, Fs), 131 btb_opt_1(Is0, D, [Comment,I0|Acc0]); 132 {ok,MustSave} when U =:= 1 -> 133 Comment = btb_comment_opt(Fs), 134 Acc = btb_gen_save(MustSave, Ctx, [Comment|Acc0]), 135 Is = prepend_move(Ctx, Dst, Is0), 136 btb_opt_1(Is, D, Acc); 137 {ok,MustSave} -> 138 Comment = btb_comment_opt(Fs), 139 Acc1 = btb_gen_save(MustSave, Ctx, [Comment|Acc0]), 140 Acc = [{test,bs_test_unit,F,[Ctx,U]}|Acc1], 141 Is = prepend_move(Ctx, Dst, Is0), 142 btb_opt_1(Is, D, Acc) 143 end; 144btb_opt_1([I|Is], D, Acc) -> 145 %%io:format("~p\n", [I]), 146 btb_opt_1(Is, D, [I|Acc]); 147btb_opt_1([], _, Acc) -> 148 reverse(Acc). 149 150btb_gen_save(true, Reg, Acc) -> 151 [{bs_save2,Reg,{atom,start}}|Acc]; 152btb_gen_save(false, _, Acc) -> Acc. 153 154prepend_move(Ctx, Dst, [{block,Bl0}|Is]) -> 155 Bl = [{set,[Dst],[Ctx],move}|Bl0], 156 [{block,Bl}|Is]; 157prepend_move(Ctx, Dst, Is) -> 158 [{move,Ctx,Dst}|Is]. 159 160%% btb_reaches_match([Instruction], [Register], D) -> 161%% {ok,MustSave}|{error,Reason} 162%% 163%% The list of Registers should be a list of registers referencing a 164%% match context. The Register may contain one element if the 165%% bs_get_binary2 instruction looks like 166%% 167%% test bs_get_binary2 {f,...} Ctx all _ _ Ctx 168%% 169%% or two elements if the instruction looks like 170%% 171%% test bs_get_binary2 {f,...} Ctx all _ _ Dst 172%% 173%% This function determines whether the bs_get_binary2 instruction 174%% can be omitted (retaining the match context instead of creating 175%% a sub binary). 176%% 177%% The rule is that the match context ultimately must end up at a 178%% bs_start_match2 instruction and nowhere else. That it, it must not 179%% be passed to BIFs, or copied or put into data structures. There 180%% must only be one copy alive when the match context reaches the 181%% bs_start_match2 instruction. 182%% 183%% At a branch, we must follow all branches and make sure that the above 184%% rule is followed (or that the branch kills the match context). 185%% 186%% The MustSave return value will be true if control may end up at 187%% bs_context_to_binary instruction. Since that instruction uses the 188%% saved start position, we must use "bs_save2 Ctx start" to 189%% update the saved start position. An additional complication is that 190%% "bs_save2 Ctx start" must not be used if Dst and Ctx are 191%% different registers and both registers may be passed to 192%% a bs_context_to_binary instruction. 193%% 194 195btb_reaches_match(Is, RegList, D) -> 196 try 197 Regs = btb_regs_from_list(RegList), 198 #btb{must_not_save=MustNotSave,must_save=MustSave} = 199 btb_reaches_match_1(Is, Regs, D), 200 case MustNotSave andalso MustSave of 201 true -> btb_error(must_and_must_not_save); 202 false -> {ok,MustSave} 203 end 204 catch 205 throw:{error,_}=Error -> Error 206 end. 207 208btb_reaches_match_1(Is, Regs, D) -> 209 case btb_are_registers_empty(Regs) of 210 false -> 211 btb_reaches_match_2(Is, Regs, D); 212 true -> 213 %% The context was killed, which is OK. 214 D 215 end. 216 217btb_reaches_match_2([{block,Bl}|Is], Regs0, D) -> 218 Regs = btb_reaches_match_block(Bl, Regs0), 219 btb_reaches_match_1(Is, Regs, D); 220btb_reaches_match_2([{call,Arity,{f,Lbl}}|Is], Regs0, D) -> 221 case is_tail_call(Is) of 222 true -> 223 Regs1 = btb_kill_not_live(Arity, Regs0), 224 Regs = btb_kill_yregs(Regs1), 225 btb_tail_call(Lbl, Regs, D); 226 false -> 227 btb_call(Arity, Lbl, Regs0, Is, D) 228 end; 229btb_reaches_match_2([{apply,Arity}|Is], Regs, D) -> 230 btb_call(Arity+2, apply, Regs, Is, D); 231btb_reaches_match_2([{call_fun,Live}=I|Is], Regs, D) -> 232 btb_ensure_not_used([{x,Live}], I, Regs), 233 btb_call(Live, I, Regs, Is, D); 234btb_reaches_match_2([{make_fun2,_,_,_,Live}|Is], Regs, D) -> 235 btb_call(Live, make_fun2, Regs, Is, D); 236btb_reaches_match_2([{call_ext,Arity,Func}=I|Is], Regs0, D) -> 237 %% Allow us scanning beyond the call in case the match 238 %% context is saved on the stack. 239 case beam_jump:is_exit_instruction(I) of 240 false -> 241 btb_call(Arity, Func, Regs0, Is, D); 242 true -> 243 Regs = btb_kill_not_live(Arity, Regs0), 244 btb_tail_call(Func, Regs, D) 245 end; 246btb_reaches_match_2([{kill,Y}|Is], Regs, D) -> 247 btb_reaches_match_1(Is, btb_kill([Y], Regs), D); 248btb_reaches_match_2([{deallocate,_}|Is], Regs0, D) -> 249 Regs = btb_kill_yregs(Regs0), 250 btb_reaches_match_1(Is, Regs, D); 251btb_reaches_match_2([return=I|_], Regs0, D) -> 252 btb_ensure_not_used([{x,0}], I, Regs0), 253 D; 254btb_reaches_match_2([{gc_bif,_,{f,F},Live,Ss,Dst}=I|Is], Regs0, D0) -> 255 btb_ensure_not_used(Ss, I, Regs0), 256 Regs1 = btb_kill_not_live(Live, Regs0), 257 Regs = btb_kill([Dst], Regs1), 258 D = btb_follow_branch(F, Regs, D0), 259 btb_reaches_match_1(Is, Regs, D); 260btb_reaches_match_2([{bif,_,{f,F},Ss,Dst}=I|Is], Regs0, D0) -> 261 btb_ensure_not_used(Ss, I, Regs0), 262 Regs = btb_kill([Dst], Regs0), 263 D = btb_follow_branch(F, Regs, D0), 264 btb_reaches_match_1(Is, Regs, D); 265btb_reaches_match_2([{get_map_elements,{f,F},Src,{list,Ls}}=I|Is], Regs0, D0) -> 266 {Ss,Ds} = beam_utils:split_even(Ls), 267 btb_ensure_not_used([Src|Ss], I, Regs0), 268 Regs = btb_kill(Ds, Regs0), 269 D = btb_follow_branch(F, Regs, D0), 270 btb_reaches_match_1(Is, Regs, D); 271btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Ctx,_],Ctx}=I|Is], 272 Regs0, D0) -> 273 CtxRegs = btb_context_regs(Regs0), 274 case member(Ctx, CtxRegs) of 275 false -> 276 %% This bs_start_match2 instruction does not use "our" 277 %% match state. Therefore we can continue the search 278 %% for another bs_start_match2 instruction. 279 D = btb_follow_branch(F, Regs0, D0), 280 Regs = btb_kill_not_live(Live, Regs0), 281 btb_reaches_match_2(Is, Regs, D); 282 true -> 283 %% OK. This instruction will use "our" match state, 284 %% but we must make sure that all other copies of the 285 %% match state are killed in the code that follows 286 %% the instruction. (We know that the fail branch cannot 287 %% be taken in this case.) 288 OtherCtxRegs = CtxRegs -- [Ctx], 289 case btb_are_all_unused(OtherCtxRegs, Is, D0) of 290 false -> btb_error({OtherCtxRegs,not_all_unused_after,I}); 291 true -> D0 292 end 293 end; 294btb_reaches_match_2([{test,bs_start_match2,{f,F},Live,[Bin,_],Ctx}|Is], 295 Regs0, D0) -> 296 CtxRegs = btb_context_regs(Regs0), 297 case member(Bin, CtxRegs) orelse member(Ctx, CtxRegs) of 298 false -> 299 %% This bs_start_match2 does not reference any copy of the 300 %% match state. Therefore it can safely be passed on the 301 %% way to another (perhaps more suitable) bs_start_match2 302 %% instruction. 303 D = btb_follow_branch(F, Regs0, D0), 304 Regs = btb_kill_not_live(Live, Regs0), 305 btb_reaches_match_2(Is, Regs, D); 306 true -> 307 %% This variant of the bs_start_match2 instruction does 308 %% not accept a match state as source. 309 btb_error(unsuitable_bs_start_match) 310 end; 311btb_reaches_match_2([{test,_,{f,F},Ss}=I|Is], Regs, D0) -> 312 btb_ensure_not_used(Ss, I, Regs), 313 D = btb_follow_branch(F, Regs, D0), 314 btb_reaches_match_1(Is, Regs, D); 315btb_reaches_match_2([{test,_,{f,F},_,Ss,_}=I|Is], Regs, D0) -> 316 btb_ensure_not_used(Ss, I, Regs), 317 D = btb_follow_branch(F, Regs, D0), 318 btb_reaches_match_1(Is, Regs, D); 319btb_reaches_match_2([{select,_,Src,{f,F},Conds}=I|Is], Regs, D0) -> 320 btb_ensure_not_used([Src], I, Regs), 321 D1 = btb_follow_branch(F, Regs, D0), 322 D = btb_follow_branches(Conds, Regs, D1), 323 btb_reaches_match_1(Is, Regs, D); 324btb_reaches_match_2([{jump,{f,Lbl}}|_], Regs, #btb{index=Li}=D) -> 325 Is = fetch_code_at(Lbl, Li), 326 btb_reaches_match_2(Is, Regs, D); 327btb_reaches_match_2([{label,_}|Is], Regs, D) -> 328 btb_reaches_match_2(Is, Regs, D); 329btb_reaches_match_2([{bs_init,{f,0},_,_,Ss,Dst}=I|Is], Regs, D) -> 330 btb_ensure_not_used(Ss, I, Regs), 331 btb_reaches_match_1(Is, btb_kill([Dst], Regs), D); 332btb_reaches_match_2([{bs_put,{f,0},_,Ss}=I|Is], Regs, D) -> 333 btb_ensure_not_used(Ss, I, Regs), 334 btb_reaches_match_1(Is, Regs, D); 335btb_reaches_match_2([{bs_restore2,Src,_}=I|Is], Regs0, D) -> 336 case btb_contains_context(Src, Regs0) of 337 false -> 338 btb_reaches_match_1(Is, Regs0, D); 339 true -> 340 %% Check that all other copies of the context registers 341 %% are unused by the following instructions. 342 Regs = btb_kill([Src], Regs0), 343 CtxRegs = btb_context_regs(Regs), 344 case btb_are_all_unused(CtxRegs, Is, D) of 345 false -> btb_error({CtxRegs,not_all_unused_after,I}); 346 true -> D#btb{must_not_save=true} 347 end 348 end; 349btb_reaches_match_2([{bs_context_to_binary,Src}=I|Is], Regs0, D) -> 350 case btb_contains_context(Src, Regs0) of 351 false -> 352 btb_reaches_match_1(Is, Regs0, D); 353 true -> 354 %% Check that all other copies of the context registers 355 %% are unused by the following instructions. 356 Regs = btb_kill([Src], Regs0), 357 CtxRegs = btb_context_regs(Regs), 358 case btb_are_all_unused(CtxRegs, Is, D) of 359 false -> btb_error({CtxRegs,not_all_unused_after,I}); 360 true -> D#btb{must_not_save=true} 361 end 362 end; 363btb_reaches_match_2([{badmatch,Src}=I|_], Regs, D) -> 364 btb_ensure_not_used([Src], I, Regs), 365 D; 366btb_reaches_match_2([{case_end,Src}=I|_], Regs, D) -> 367 btb_ensure_not_used([Src], I, Regs), 368 D; 369btb_reaches_match_2([if_end|_], _Regs, D) -> 370 D; 371btb_reaches_match_2([{func_info,_,_,Arity}=I|_], Regs0, D) -> 372 Regs = btb_kill_yregs(btb_kill_not_live(Arity, Regs0)), 373 case btb_context_regs(Regs) of 374 [] -> D; 375 _ -> {binary_used_in,I} 376 end; 377btb_reaches_match_2([{line,_}|Is], Regs, D) -> 378 btb_reaches_match_1(Is, Regs, D); 379btb_reaches_match_2([I|_], Regs, _) -> 380 btb_error({btb_context_regs(Regs),I,not_handled}). 381 382is_tail_call([{deallocate,_}|_]) -> true; 383is_tail_call([return|_]) -> true; 384is_tail_call(_) -> false. 385 386btb_call(Arity, Lbl, Regs0, Is, D0) -> 387 Regs = btb_kill_not_live(Arity, Regs0), 388 case btb_are_x_registers_empty(Regs) of 389 false -> 390 %% There is a match context in one of the x registers. 391 %% First handle the call as if it were a tail call. 392 D = btb_tail_call(Lbl, Regs, D0), 393 394 %% No problem so far (the called function can handle a 395 %% match context). Now we must make sure that we don't 396 %% have any copies of the match context tucked away in an 397 %% y register. 398 RegList = btb_context_regs(Regs), 399 case [R || {y,_}=R <- RegList] of 400 [] -> 401 D; 402 [_|_] -> 403 btb_error({multiple_uses,RegList}) 404 end; 405 true -> 406 %% No match context in any x register. It could have been 407 %% saved to an y register, so continue to scan the code following 408 %% the call. 409 btb_reaches_match_1(Is, Regs, D0) 410 end. 411 412btb_tail_call(Lbl, Regs, #btb{f=Ftree,must_save=MustSave0}=D) -> 413 %% Ignore any y registers here. 414 case [R || {x,_}=R <- btb_context_regs(Regs)] of 415 [] -> 416 D; 417 [{x,_}=Reg] -> 418 case gb_trees:lookup(Lbl, Ftree) of 419 {value,{Reg,MustSave}} -> 420 D#btb{must_save=MustSave0 or MustSave}; 421 _ when is_integer(Lbl) -> 422 btb_error({{label,Lbl},no_suitable_bs_start_match}); 423 _ -> 424 btb_error({binary_used_in,Lbl}) 425 end; 426 [_|_] when not is_integer(Lbl) -> 427 btb_error({binary_used_in,Lbl}); 428 [_|_]=RegList -> 429 btb_error({multiple_uses,RegList}) 430 end. 431 432%% btb_follow_branches([Cond], Regs, D) -> D' 433%% Recursively follow all the branches. 434 435btb_follow_branches([{f,Lbl}|T], Regs, D0) -> 436 D = btb_follow_branch(Lbl, Regs, D0), 437 btb_follow_branches(T, Regs, D); 438btb_follow_branches([_|T], Regs, D) -> 439 btb_follow_branches(T, Regs, D); 440btb_follow_branches([], _, D) -> D. 441 442%% btb_follow_branch(Lbl, Regs, D) -> D' 443%% Recursively follow the branch. 444 445btb_follow_branch(0, _Regs, D) -> D; 446btb_follow_branch(Lbl, Regs, #btb{ok_br=Br0,index=Li}=D) -> 447 Key = {Lbl,Regs}, 448 case gb_sets:is_member(Key, Br0) of 449 true -> 450 %% We have already followed this branch and it was OK. 451 D; 452 false -> 453 %% New branch. Try it. 454 Is = fetch_code_at(Lbl, Li), 455 #btb{ok_br=Br,must_not_save=MustNotSave,must_save=MustSave} = 456 btb_reaches_match_1(Is, Regs, D), 457 458 %% Since we got back, this branch is OK. 459 D#btb{ok_br=gb_sets:insert(Key, Br),must_not_save=MustNotSave, 460 must_save=MustSave} 461 end. 462 463btb_reaches_match_block([{set,Ds,Ss,{alloc,Live,_}}=I|Is], Regs0) -> 464 %% An allocation instruction or a GC bif. We'll kill all registers 465 %% if any copy of the context is used as the source to the BIF. 466 btb_ensure_not_used(Ss, I, Regs0), 467 Regs1 = btb_kill_not_live(Live, Regs0), 468 Regs = btb_kill(Ds, Regs1), 469 btb_reaches_match_block(Is, Regs); 470btb_reaches_match_block([{set,[Dst]=Ds,[Src],move}|Is], Regs0) -> 471 Regs1 = btb_kill(Ds, Regs0), 472 Regs = case btb_contains_context(Src, Regs1) of 473 false -> Regs1; 474 true -> btb_set_context(Dst, Regs1) 475 end, 476 btb_reaches_match_block(Is, Regs); 477btb_reaches_match_block([{set,Ds,Ss,_}=I|Is], Regs0) -> 478 btb_ensure_not_used(Ss, I, Regs0), 479 Regs = btb_kill(Ds, Regs0), 480 btb_reaches_match_block(Is, Regs); 481btb_reaches_match_block([], Regs) -> 482 Regs. 483 484%% btb_are_all_killed([Register], [Instruction], D) -> true|false 485%% Test whether all of the register are unused in the instruction stream. 486 487btb_are_all_unused(RegList, Is, #btb{index=Li}) -> 488 all(fun(R) -> 489 beam_utils:is_not_used(R, Is, Li) 490 end, RegList). 491 492%% btp_regs_from_list([Register]) -> RegisterSet. 493%% Create a register set from a list of registers. 494 495btb_regs_from_list(L) -> 496 foldl(fun(R, Regs) -> 497 btb_set_context(R, Regs) 498 end, {0,0}, L). 499 500%% btb_set_context(Register, RegisterSet) -> RegisterSet' 501%% Update RegisterSet to indicate that Register contains the matching context. 502 503btb_set_context({x,N}, {Xregs,Yregs}) -> 504 {Xregs bor (1 bsl N),Yregs}; 505btb_set_context({y,N}, {Xregs,Yregs}) -> 506 {Xregs,Yregs bor (1 bsl N)}. 507 508%% btb_ensure_not_used([Register], Instruction, RegisterSet) -> ok 509%% If any register in RegisterSet (the register(s) known to contain 510%% the match context) is used in the list of registers, generate an error. 511 512btb_ensure_not_used(Rs, I, Regs) -> 513 case lists:any(fun(R) -> btb_contains_context(R, Regs) end, Rs) of 514 true -> btb_error({binary_used_in,I}); 515 false -> ok 516 end. 517 518%% btb_kill([Register], RegisterSet) -> RegisterSet' 519%% Kill all registers mentioned in the list of registers. 520 521btb_kill([{x,N}|Rs], {Xregs,Yregs}) -> 522 btb_kill(Rs, {Xregs band (bnot (1 bsl N)),Yregs}); 523btb_kill([{y,N}|Rs], {Xregs,Yregs}) -> 524 btb_kill(Rs, {Xregs,Yregs band (bnot (1 bsl N))}); 525btb_kill([{fr,_}|Rs], Regs) -> 526 btb_kill(Rs, Regs); 527btb_kill([], Regs) -> Regs. 528 529%% btb_kill_not_live(Live, RegisterSet) -> RegisterSet' 530%% Kill all registers indicated not live by Live. 531 532btb_kill_not_live(Live, {Xregs,Yregs}) -> 533 {Xregs band ((1 bsl Live)-1),Yregs}. 534 535%% btb_kill(Regs0) -> Regs 536%% Kill all y registers. 537 538btb_kill_yregs({Xregs,_}) -> {Xregs,0}. 539 540%% btb_are_registers_empty(RegisterSet) -> true|false 541%% Test whether the register set is empty. 542 543btb_are_registers_empty({0,0}) -> true; 544btb_are_registers_empty({_,_}) -> false. 545 546%% btb_are_x_registers_empty(Regs) -> true|false 547%% Test whether the x registers are empty. 548 549btb_are_x_registers_empty({0,_}) -> true; 550btb_are_x_registers_empty({_,_}) -> false. 551 552%% btb_contains_context(Register, RegisterSet) -> true|false 553%% Test whether Register contains the context. 554 555btb_contains_context({x,N}, {Regs,_}) -> Regs band (1 bsl N) =/= 0; 556btb_contains_context({y,N}, {_,Regs}) -> Regs band (1 bsl N) =/= 0; 557btb_contains_context(_, _) -> false. 558 559%% btb_context_regs(RegisterSet) -> [Register] 560%% Convert the register set to an explicit list of registers. 561btb_context_regs({Xregs,Yregs}) -> 562 btb_context_regs_1(Xregs, 0, x, btb_context_regs_1(Yregs, 0, y, [])). 563 564btb_context_regs_1(0, _, _, Acc) -> 565 Acc; 566btb_context_regs_1(Regs, N, Tag, Acc) when (Regs band 1) =:= 1 -> 567 btb_context_regs_1(Regs bsr 1, N+1, Tag, [{Tag,N}|Acc]); 568btb_context_regs_1(Regs, N, Tag, Acc) -> 569 btb_context_regs_1(Regs bsr 1, N+1, Tag, Acc). 570 571%% btb_index([Function]) -> GbTree({EntryLabel,{Register,MustSave}}) 572%% Build an index of functions that accept a match context instead of 573%% a binary. MustSave is true if the function may pass the match 574%% context to the bs_context_to_binary instruction (in which case 575%% the current position in the binary must have saved into the 576%% start position using "bs_save_2 Ctx start"). 577 578btb_index(Fs) -> 579 btb_index_1(Fs, []). 580 581btb_index_1([{function,_,_,Entry,Is0}|Fs], Acc0) -> 582 Is = drop_to_label(Is0, Entry), 583 Acc = btb_index_2(Is, Entry, false, Acc0), 584 btb_index_1(Fs, Acc); 585btb_index_1([], Acc) -> gb_trees:from_orddict(sort(Acc)). 586 587btb_index_2([{test,bs_start_match2,{f,_},_,[Reg,_],Reg}|_], 588 Entry, MustSave, Acc) -> 589 [{Entry,{Reg,MustSave}}|Acc]; 590btb_index_2(Is0, Entry, _, Acc) -> 591 try btb_index_find_start_match(Is0) of 592 Is -> btb_index_2(Is, Entry, true, Acc) 593 catch 594 throw:none -> Acc 595 end. 596 597drop_to_label([{label,L}|Is], L) -> Is; 598drop_to_label([_|Is], L) -> drop_to_label(Is, L). 599 600btb_index_find_start_match([{test,_,{f,F},_},{bs_context_to_binary,_}|Is]) -> 601 btb_index_find_label(Is, F); 602btb_index_find_start_match(_) -> 603 throw(none). 604 605btb_index_find_label([{label,L}|Is], L) -> Is; 606btb_index_find_label([_|Is], L) -> btb_index_find_label(Is, L). 607 608btb_error(Error) -> 609 throw({error,Error}). 610 611fetch_code_at(Lbl, Li) -> 612 case beam_utils:code_at(Lbl, Li) of 613 Is when is_list(Is) -> Is 614 end. 615 616%%% 617%%% Compilation information warnings. 618%%% 619 620btb_comment_opt({field_flags,[{anno,A}|_]}) -> 621 {'%',{bin_opt,A}}; 622btb_comment_opt(_) -> 623 {'%',{bin_opt,[]}}. 624 625btb_comment_no_opt(Reason, {field_flags,[{anno,A}|_]}) -> 626 {'%',{no_bin_opt,Reason,A}}; 627btb_comment_no_opt(Reason, _) -> 628 {'%',{no_bin_opt,Reason,[]}}. 629 630collect_warnings(Fs) -> 631 D = warning_index_functions(Fs), 632 foldl(fun(F, A) -> collect_warnings_fun(F, D, A) end, [], Fs). 633 634collect_warnings_fun({function,_,_,_,Is}, D, A) -> 635 collect_warnings_instr(Is, D, A). 636 637collect_warnings_instr([{'%',{bin_opt,Where}}|Is], D, Acc0) -> 638 Acc = add_warning(bin_opt, Where, Acc0), 639 collect_warnings_instr(Is, D, Acc); 640collect_warnings_instr([{'%',{no_bin_opt,Reason0,Where}}|Is], D, Acc0) -> 641 Reason = warning_translate_label(Reason0, D), 642 Acc = add_warning({no_bin_opt,Reason}, Where, Acc0), 643 collect_warnings_instr(Is, D, Acc); 644collect_warnings_instr([_|Is], D, Acc) -> 645 collect_warnings_instr(Is, D, Acc); 646collect_warnings_instr([], _, Acc) -> Acc. 647 648add_warning(Term, Anno, Ws) -> 649 Line = get_line(Anno), 650 File = get_file(Anno), 651 [{File,[{Line,?MODULE,Term}]}|Ws]. 652 653warning_translate_label(Term, D) when is_tuple(Term) -> 654 case element(1, Term) of 655 {label,F} -> 656 FA = gb_trees:get(F, D), 657 setelement(1, Term, FA); 658 _ -> Term 659 end; 660warning_translate_label(Term, _) -> Term. 661 662get_line([Line|_]) when is_integer(Line) -> Line; 663get_line([_|T]) -> get_line(T); 664get_line([]) -> none. 665 666get_file([{file,File}|_]) -> File; 667get_file([_|T]) -> get_file(T); 668get_file([]) -> "no_file". % should not happen 669 670warning_index_functions(Fs) -> 671 D = [{Entry,{F,A}} || {function,F,A,Entry,_} <- Fs], 672 gb_trees:from_orddict(sort(D)). 673 674format_error_1({binary_used_in,{extfunc,M,F,A}}) -> 675 [io_lib:format("sub binary used by ~p:~p/~p", [M,F,A])| 676 case {M,F,A} of 677 {erlang,split_binary,2} -> 678 "; SUGGEST using binary matching instead of split_binary/2"; 679 _ -> 680 "" 681 end]; 682format_error_1({binary_used_in,_}) -> 683 "sub binary is used or returned"; 684format_error_1({multiple_uses,_}) -> 685 "sub binary is matched or used in more than one place"; 686format_error_1(unsuitable_bs_start_match) -> 687 "the binary matching instruction that follows in the same function " 688 "have problems that prevent delayed sub binary optimization " 689 "(probably indicated by INFO warnings)"; 690format_error_1({{F,A},no_suitable_bs_start_match}) -> 691 io_lib:format("called function ~p/~p does not begin with a suitable " 692 "binary matching instruction", [F,A]); 693format_error_1(must_and_must_not_save) -> 694 "different control paths use different positions in the binary"; 695format_error_1({_,I,not_handled}) -> 696 case I of 697 {'catch',_,_} -> 698 "the compiler currently does not attempt the delayed sub binary " 699 "optimization when catch is used"; 700 {'try',_,_} -> 701 "the compiler currently does not attempt the delayed sub binary " 702 "optimization when try/catch is used"; 703 _ -> 704 io_lib:format("compiler limitation: instruction ~p prevents " 705 "delayed sub binary optimization", [I]) 706 end; 707format_error_1(Term) -> 708 io_lib:format("~w", [Term]). 709