1%% 2%% %CopyrightBegin% 3%% 4%% Copyright Ericsson AB 2018-2020. 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%% This pass infers types from expressions and attempts to simplify or remove 21%% subsequent instructions based on that information. 22%% 23%% This is divided into two subpasses; the first figures out function type 24%% signatures for the whole module without optimizing anything, and the second 25%% optimizes based on that information, further refining the type signatures as 26%% it goes. 27%% 28 29-module(beam_ssa_type). 30-export([opt_start/2, opt_continue/4, opt_finish/3]). 31 32-include("beam_ssa_opt.hrl"). 33-include("beam_types.hrl"). 34 35-import(lists, [all/2,any/2,duplicate/2,foldl/3,member/2, 36 keyfind/3,reverse/1,split/2,zip/2]). 37 38%% The maximum number of #b_ret{} terminators a function can have before 39%% collapsing success types into a single entry. Consider the following code: 40%% 41%% f(0) -> 1; 42%% f(...) -> ...; 43%% f(500000) -> 500000. 44%% 45%% Since success types are grouped by return type and each clause returns a 46%% distinct type (singleton #t_integer{}s), we'll add 500000 entries which 47%% makes progress glacial since every call needs to examine them all to 48%% determine the return type. 49%% 50%% The entries are collapsed unconditionally if the number of returns in a 51%% function exceeds this threshold. This is necessary because collapsing as we 52%% go might widen a type; if we're at (?RETURN_LIMIT - 1) entries and suddenly 53%% narrow a type down, it could push us over the edge and collapse all entries, 54%% possibly widening the return type and breaking optimizations that were based 55%% on the earlier (narrower) types. 56-define(RETURN_LIMIT, 30). 57 58%% Constants common to all subpasses. 59-record(metadata, 60 { func_id :: func_id(), 61 limit_return :: boolean(), 62 params :: [beam_ssa:b_var()], 63 used_once :: sets:set(beam_ssa:b_var()) }). 64 65-type type_db() :: #{ beam_ssa:var_name() := type() }. 66 67%% 68 69-spec opt_start(term(), term()) -> term(). 70opt_start(StMap, FuncDb0) when FuncDb0 =/= #{} -> 71 {ArgDb, FuncDb} = signatures(StMap, FuncDb0), 72 73 opt_start_1(maps:keys(StMap), ArgDb, StMap, FuncDb); 74opt_start(StMap, FuncDb) -> 75 %% Module-level analysis is disabled, likely because of a call to 76 %% load_nif/2 or similar. opt_continue/4 will assume that all arguments and 77 %% return types are 'any'. 78 {StMap, FuncDb}. 79 80opt_start_1([Id | Ids], ArgDb, StMap0, FuncDb0) -> 81 case ArgDb of 82 #{ Id := ArgTypes } -> 83 #opt_st{ssa=Linear0,args=Args} = St0 = map_get(Id, StMap0), 84 85 Ts = maps:from_list(zip(Args, ArgTypes)), 86 {Linear, FuncDb} = opt_function(Linear0, Args, Id, Ts, FuncDb0), 87 88 St = St0#opt_st{ssa=Linear}, 89 StMap = StMap0#{ Id := St }, 90 91 opt_start_1(Ids, ArgDb, StMap, FuncDb); 92 #{} -> 93 %% Unreachable functions must be removed so that opt_continue/4 94 %% won't process them and potentially taint the argument types of 95 %% other functions. 96 StMap = maps:remove(Id, StMap0), 97 FuncDb = maps:remove(Id, FuncDb0), 98 99 opt_start_1(Ids, ArgDb, StMap, FuncDb) 100 end; 101opt_start_1([], _CommittedArgs, StMap, FuncDb) -> 102 {StMap, FuncDb}. 103 104%% 105%% The initial signature analysis is based on the paper "Practical Type 106%% Inference Based on Success Typings" [1] by `Tobias Lindahl` and 107%% `Konstantinos Sagonas`, mainly section 6.1 and onwards. 108%% 109%% The general idea is to start out at the module's entry points and propagate 110%% types to the functions we call. The argument types of all exported functions 111%% start out a 'any', whereas local functions start at 'none'. Every time a 112%% function call widens the argument types, we analyze the callee again and 113%% propagate its return types to the callers, analyzing them again, and 114%% continuing this process until all arguments and return types have been 115%% widened as far as they can be. 116%% 117%% Note that we do not "jump-start the analysis" by first determining success 118%% types as in the paper because we need to know all possible inputs including 119%% those that will not return. 120%% 121%% [1] http://www.it.uu.se/research/group/hipe/papers/succ_types.pdf 122%% 123 124-record(sig_st, 125 { wl = wl_new() :: worklist(), 126 committed = #{} :: #{ func_id() => [type()] }, 127 updates = #{} :: #{ func_id() => [type()] }}). 128 129signatures(StMap, FuncDb0) -> 130 State0 = init_sig_st(StMap, FuncDb0), 131 {State, FuncDb} = signatures_1(StMap, FuncDb0, State0), 132 {State#sig_st.committed, FuncDb}. 133 134signatures_1(StMap, FuncDb0, State0) -> 135 case wl_next(State0#sig_st.wl) of 136 {ok, FuncId} -> 137 {State, FuncDb} = sig_function(FuncId, StMap, State0, FuncDb0), 138 signatures_1(StMap, FuncDb, State); 139 empty -> 140 %% No more work to do, assert that we don't have any outstanding 141 %% updates. 142 #sig_st{updates=Same,committed=Same} = State0, %Assertion. 143 144 {State0, FuncDb0} 145 end. 146 147sig_function(Id, StMap, State, FuncDb) -> 148 try 149 do_sig_function(Id, StMap, State, FuncDb) 150 catch 151 Class:Error:Stack -> 152 #b_local{name=#b_literal{val=Name},arity=Arity} = Id, 153 io:fwrite("Function: ~w/~w\n", [Name,Arity]), 154 erlang:raise(Class, Error, Stack) 155 end. 156 157do_sig_function(Id, StMap, State0, FuncDb0) -> 158 case sig_function_1(Id, StMap, State0, FuncDb0) of 159 {false, false, State, FuncDb} -> 160 %% No added work and the types are identical. Pop ourselves from 161 %% the work list and move on to the next function. 162 Wl = wl_pop(Id, State#sig_st.wl), 163 {State#sig_st{wl=Wl}, FuncDb}; 164 {false, true, State, FuncDb} -> 165 %% We've added some work and our return type is unchanged. Keep 166 %% following the work list without popping ourselves; we're very 167 %% likely to need to return here later and can avoid a lot of 168 %% redundant work by keeping our place in line. 169 {State, FuncDb}; 170 {true, WlChanged, State, FuncDb} -> 171 %% Our return type has changed so all of our (previously analyzed) 172 %% callers need to be analyzed again. 173 %% 174 %% If our worklist is unchanged we'll pop ourselves since our 175 %% callers will add us back if we need to analyzed again, and 176 %% it's wasteful to stay in the worklist when we don't. 177 Wl0 = case WlChanged of 178 true -> State#sig_st.wl; 179 false -> wl_pop(Id, State#sig_st.wl) 180 end, 181 182 #func_info{in=Cs0} = map_get(Id, FuncDb0), 183 Updates = State#sig_st.updates, 184 Callers = [C || C <- Cs0, is_map_key(C, Updates)], 185 Wl = wl_defer_list(Callers, Wl0), 186 187 {State#sig_st{wl=Wl}, FuncDb} 188 end. 189 190sig_function_1(Id, StMap, State0, FuncDb) -> 191 #opt_st{ssa=Linear,args=Args} = map_get(Id, StMap), 192 193 {ArgTypes, State1} = sig_commit_args(Id, State0), 194 Ts = maps:from_list(zip(Args, ArgTypes)), 195 196 FakeCall = #b_set{op=call,args=[#b_remote{mod=#b_literal{val=unknown}, 197 name=#b_literal{val=unknown}, 198 arity=0}]}, 199 200 Ds = maps:from_list([{Var, FakeCall#b_set{dst=Var}} || 201 #b_var{}=Var <- Args]), 202 203 Ls = #{ ?EXCEPTION_BLOCK => {incoming, Ts}, 204 0 => {incoming, Ts} }, 205 206 Meta = init_metadata(Id, Linear, Args), 207 208 Wl0 = State1#sig_st.wl, 209 210 {State, SuccTypes} = sig_bs(Linear, Ds, Ls, FuncDb, #{}, [], Meta, State1), 211 212 WlChanged = wl_changed(Wl0, State#sig_st.wl), 213 #{ Id := #func_info{succ_types=SuccTypes0}=Entry0 } = FuncDb, 214 215 if 216 SuccTypes0 =:= SuccTypes -> 217 {false, WlChanged, State, FuncDb}; 218 SuccTypes0 =/= SuccTypes -> 219 Entry = Entry0#func_info{succ_types=SuccTypes}, 220 {true, WlChanged, State, FuncDb#{ Id := Entry }} 221 end. 222 223sig_bs([{L, #b_blk{is=Is,last=Last0}} | Bs], 224 Ds0, Ls0, Fdb, Sub0, SuccTypes0, Meta, State0) -> 225 case Ls0 of 226 #{ L := Incoming } -> 227 {incoming, Ts0} = Incoming, %Assertion. 228 229 {Ts, Ds, Sub, State} = 230 sig_is(Is, Ts0, Ds0, Ls0, Fdb, Sub0, State0), 231 232 Last = simplify_terminator(Last0, Ts, Ds, Sub), 233 SuccTypes = update_success_types(Last, Ts, Ds, Meta, SuccTypes0), 234 235 UsedOnce = Meta#metadata.used_once, 236 {_, Ls1} = update_successors(Last, Ts, Ds, Ls0, UsedOnce), 237 238 %% In the future there may be a point to storing outgoing types on 239 %% a per-edge basis as it would give us more precision in phi 240 %% nodes, but there's nothing to gain from that at the moment so 241 %% we'll store the current Ts to save memory. 242 Ls = Ls1#{ L := {outgoing, Ts} }, 243 sig_bs(Bs, Ds, Ls, Fdb, Sub, SuccTypes, Meta, State); 244 #{} -> 245 %% This block is never reached. Ignore it. 246 sig_bs(Bs, Ds0, Ls0, Fdb, Sub0, SuccTypes0, Meta, State0) 247 end; 248sig_bs([], _Ds, _Ls, _Fdb, _Sub, SuccTypes, _Meta, State) -> 249 {State, SuccTypes}. 250 251sig_is([#b_set{op=call, 252 args=[#b_local{}=Callee | _]=Args0, 253 dst=Dst}=I0 | Is], 254 Ts0, Ds0, Ls, Fdb, Sub, State0) -> 255 Args = simplify_args(Args0, Ts0, Sub), 256 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 257 258 [_ | CallArgs] = Args, 259 {I, State} = sig_local_call(I1, Callee, CallArgs, Ts0, Fdb, State0), 260 261 Ts = update_types(I, Ts0, Ds0), 262 Ds = Ds0#{ Dst => I }, 263 sig_is(Is, Ts, Ds, Ls, Fdb, Sub, State); 264sig_is([#b_set{op=call, 265 args=[#b_var{} | _]=Args0, 266 dst=Dst}=I0 | Is], 267 Ts0, Ds0, Ls, Fdb, Sub, State) -> 268 Args = simplify_args(Args0, Ts0, Sub), 269 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 270 271 [Fun | _] = Args, 272 I = case normalized_type(Fun, Ts0) of 273 #t_fun{type=Type} -> beam_ssa:add_anno(result_type, Type, I1); 274 _ -> I1 275 end, 276 277 Ts = update_types(I, Ts0, Ds0), 278 Ds = Ds0#{ Dst => I }, 279 sig_is(Is, Ts, Ds, Ls, Fdb, Sub, State); 280sig_is([#b_set{op=MakeFun,args=Args0,dst=Dst}=I0|Is], 281 Ts0, Ds0, Ls, Fdb, Sub0, State0) when MakeFun =:= make_fun; 282 MakeFun =:= old_make_fun -> 283 Args = simplify_args(Args0, Ts0, Sub0), 284 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 285 286 {I, State} = sig_make_fun(I1, Ts0, Fdb, State0), 287 288 Ts = update_types(I, Ts0, Ds0), 289 Ds = Ds0#{ Dst => I }, 290 sig_is(Is, Ts, Ds, Ls, Fdb, Sub0, State); 291sig_is([I0 | Is], Ts0, Ds0, Ls, Fdb, Sub0, State) -> 292 case simplify(I0, Ts0, Ds0, Ls, Sub0) of 293 {#b_set{}, Ts, Ds} -> 294 sig_is(Is, Ts, Ds, Ls, Fdb, Sub0, State); 295 Sub when is_map(Sub) -> 296 sig_is(Is, Ts0, Ds0, Ls, Fdb, Sub, State) 297 end; 298sig_is([], Ts, Ds, _Ls, _Fdb, Sub, State) -> 299 {Ts, Ds, Sub, State}. 300 301sig_local_call(I0, Callee, Args, Ts, Fdb, State) -> 302 ArgTypes = argument_types(Args, Ts), 303 I = sig_local_return(I0, Callee, ArgTypes, Fdb), 304 {I, sig_update_args(Callee, ArgTypes, State)}. 305 306%% While it's impossible to tell which arguments a fun will be called with 307%% (someone could steal it through tracing and call it), we do know its free 308%% variables and can update their types as if this were a local call. 309sig_make_fun(#b_set{op=MakeFun, 310 args=[#b_local{}=Callee | FreeVars]}=I0, 311 Ts, Fdb, State) when MakeFun =:= make_fun; 312 MakeFun =:= old_make_fun -> 313 ArgCount = Callee#b_local.arity - length(FreeVars), 314 315 FVTypes = [raw_type(FreeVar, Ts) || FreeVar <- FreeVars], 316 ArgTypes = duplicate(ArgCount, any) ++ FVTypes, 317 318 I = sig_local_return(I0, Callee, ArgTypes, Fdb), 319 {I, sig_update_args(Callee, ArgTypes, State)}. 320 321sig_local_return(I, Callee, ArgTypes, Fdb) -> 322 #func_info{succ_types=SuccTypes} = map_get(Callee, Fdb), 323 case return_type(SuccTypes, ArgTypes) of 324 any -> I; 325 Type -> beam_ssa:add_anno(result_type, Type, I) 326 end. 327 328init_sig_st(StMap, FuncDb) -> 329 %% Start out as if all the roots have been called with 'any' for all 330 %% arguments. 331 Roots = init_sig_roots(FuncDb), 332 #sig_st{ committed=#{}, 333 updates=init_sig_args(Roots, StMap, #{}), 334 wl=wl_defer_list(Roots, wl_new()) }. 335 336init_sig_roots(FuncDb) -> 337 maps:fold(fun(Id, #func_info{exported=true}, Acc) -> 338 [Id | Acc]; 339 (_, _, Acc) -> 340 Acc 341 end, [], FuncDb). 342 343init_sig_args([Root | Roots], StMap, Acc) -> 344 #opt_st{args=Args0} = map_get(Root, StMap), 345 ArgTypes = lists:duplicate(length(Args0), any), 346 init_sig_args(Roots, StMap, Acc#{ Root => ArgTypes }); 347init_sig_args([], _StMap, Acc) -> 348 Acc. 349 350sig_commit_args(Id, #sig_st{updates=Us,committed=Committed0}=State0) -> 351 Types = map_get(Id, Us), 352 Committed = Committed0#{ Id => Types }, 353 State = State0#sig_st{committed=Committed}, 354 {Types, State}. 355 356sig_update_args(Callee, Types, #sig_st{committed=Committed}=State) -> 357 case Committed of 358 #{ Callee := Current } -> 359 case parallel_join(Current, Types) of 360 Current -> 361 %% We've already processed this function with these 362 %% arguments, so there's no need to visit it again. 363 State; 364 Widened -> 365 sig_update_args_1(Callee, Widened, State) 366 end; 367 #{} -> 368 sig_update_args_1(Callee, Types, State) 369 end. 370 371sig_update_args_1(Callee, Types, #sig_st{updates=Us0,wl=Wl0}=State) -> 372 Us = case Us0 of 373 #{ Callee := Current } -> 374 Us0#{ Callee => parallel_join(Current, Types) }; 375 #{} -> 376 Us0#{ Callee => Types } 377 end, 378 State#sig_st{updates=Us,wl=wl_add(Callee, Wl0)}. 379 380-spec opt_continue(Linear, Args, Anno, FuncDb) -> {Linear, FuncDb} when 381 Linear :: [{non_neg_integer(), beam_ssa:b_blk()}], 382 Args :: [beam_ssa:b_var()], 383 Anno :: beam_ssa:anno(), 384 FuncDb :: func_info_db(). 385opt_continue(Linear0, Args, Anno, FuncDb) when FuncDb =/= #{} -> 386 Id = get_func_id(Anno), 387 case FuncDb of 388 #{ Id := #func_info{exported=false,arg_types=ArgTypes} } -> 389 %% This is a local function and we're guaranteed to have visited 390 %% every call site at least once, so we know that the parameter 391 %% types are at least as narrow as the join of all argument types. 392 Ts = join_arg_types(Args, ArgTypes, #{}), 393 opt_function(Linear0, Args, Id, Ts, FuncDb); 394 #{ Id := #func_info{exported=true} } -> 395 %% We can't infer the parameter types of exported functions, but 396 %% running the pass again could still help other functions. 397 Ts = maps:from_list([{V,any} || #b_var{}=V <- Args]), 398 opt_function(Linear0, Args, Id, Ts, FuncDb) 399 end; 400opt_continue(Linear0, Args, Anno, _FuncDb) -> 401 %% Module-level optimization is disabled, pass an empty function database 402 %% so we only perform local optimizations. 403 Id = get_func_id(Anno), 404 Ts = maps:from_list([{V,any} || #b_var{}=V <- Args]), 405 {Linear, _} = opt_function(Linear0, Args, Id, Ts, #{}), 406 {Linear, #{}}. 407 408join_arg_types([Arg | Args], [TypeMap | TMs], Ts) -> 409 Type = beam_types:join(maps:values(TypeMap)), 410 join_arg_types(Args, TMs, Ts#{ Arg => Type }); 411join_arg_types([], [], Ts) -> 412 Ts. 413 414%% 415%% Optimizes a function based on the type information inferred by signatures/2 416%% and earlier runs of opt_function/5. 417%% 418%% This is pretty straightforward as it only walks through each function once, 419%% and because it only makes types narrower it's safe to optimize the functions 420%% in any order or not at all. 421%% 422 423-spec opt_function(Linear, Args, Id, Ts, FuncDb) -> Result when 424 Linear :: [{non_neg_integer(), beam_ssa:b_blk()}], 425 Args :: [beam_ssa:b_var()], 426 Id :: func_id(), 427 Ts :: type_db(), 428 FuncDb :: func_info_db(), 429 Result :: {Linear, FuncDb}. 430opt_function(Linear, Args, Id, Ts, FuncDb) -> 431 try 432 do_opt_function(Linear, Args, Id, Ts, FuncDb) 433 catch 434 Class:Error:Stack -> 435 #b_local{name=#b_literal{val=Name},arity=Arity} = Id, 436 io:fwrite("Function: ~w/~w\n", [Name,Arity]), 437 erlang:raise(Class, Error, Stack) 438 end. 439 440do_opt_function(Linear0, Args, Id, Ts, FuncDb0) -> 441 FakeCall = #b_set{op=call,args=[#b_remote{mod=#b_literal{val=unknown}, 442 name=#b_literal{val=unknown}, 443 arity=0}]}, 444 445 Ds = maps:from_list([{Var, FakeCall#b_set{dst=Var}} || 446 #b_var{}=Var <- Args]), 447 448 Ls = #{ ?EXCEPTION_BLOCK => {incoming, Ts}, 449 0 => {incoming, Ts} }, 450 451 Meta = init_metadata(Id, Linear0, Args), 452 453 {Linear, FuncDb, SuccTypes} = 454 opt_bs(Linear0, Ds, Ls, FuncDb0, #{}, [], Meta, []), 455 456 case FuncDb of 457 #{ Id := Entry0 } -> 458 Entry = Entry0#func_info{succ_types=SuccTypes}, 459 {Linear, FuncDb#{ Id := Entry }}; 460 #{} -> 461 %% Module-level optimizations have been turned off. 462 {Linear, FuncDb} 463 end. 464 465get_func_id(Anno) -> 466 #{func_info:={_Mod, Name, Arity}} = Anno, 467 #b_local{name=#b_literal{val=Name}, arity=Arity}. 468 469opt_bs([{L, #b_blk{is=Is0,last=Last0}=Blk0} | Bs], 470 Ds0, Ls0, Fdb0, Sub0, SuccTypes0, Meta, Acc) -> 471 case Ls0 of 472 #{ L := Incoming } -> 473 {incoming, Ts0} = Incoming, %Assertion. 474 475 {Is, Ts, Ds, Fdb, Sub} = 476 opt_is(Is0, Ts0, Ds0, Ls0, Fdb0, Sub0, Meta, []), 477 478 Last1 = simplify_terminator(Last0, Ts, Ds, Sub), 479 SuccTypes = update_success_types(Last1, Ts, Ds, Meta, SuccTypes0), 480 481 UsedOnce = Meta#metadata.used_once, 482 {Last, Ls1} = update_successors(Last1, Ts, Ds, Ls0, UsedOnce), 483 484 Ls = Ls1#{ L := {outgoing, Ts} }, %Assertion. 485 486 Blk = Blk0#b_blk{is=Is,last=Last}, 487 opt_bs(Bs, Ds, Ls, Fdb, Sub, SuccTypes, Meta, [{L,Blk} | Acc]); 488 #{} -> 489 %% This block is never reached. Discard it. 490 opt_bs(Bs, Ds0, Ls0, Fdb0, Sub0, SuccTypes0, Meta, Acc) 491 end; 492opt_bs([], _Ds, _Ls, Fdb, _Sub, SuccTypes, _Meta, Acc) -> 493 {reverse(Acc), Fdb, SuccTypes}. 494 495opt_is([#b_set{op=call, 496 args=[#b_local{}=Callee | _]=Args0, 497 dst=Dst}=I0 | Is], 498 Ts0, Ds0, Ls, Fdb0, Sub, Meta, Acc) -> 499 Args = simplify_args(Args0, Ts0, Sub), 500 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 501 502 [_ | CallArgs] = Args, 503 {I, Fdb} = opt_local_call(I1, Callee, CallArgs, Dst, Ts0, Fdb0, Meta), 504 505 Ts = update_types(I, Ts0, Ds0), 506 Ds = Ds0#{ Dst => I }, 507 opt_is(Is, Ts, Ds, Ls, Fdb, Sub, Meta, [I | Acc]); 508opt_is([#b_set{op=call, 509 args=[#b_var{} | _]=Args0, 510 dst=Dst}=I0 | Is], 511 Ts0, Ds0, Ls, Fdb, Sub, Meta, Acc) -> 512 Args = simplify_args(Args0, Ts0, Sub), 513 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 514 515 [Fun | _] = Args, 516 I = case normalized_type(Fun, Ts0) of 517 #t_fun{type=Type} when Type =/= any -> 518 beam_ssa:add_anno(result_type, Type, I1); 519 _ -> 520 I1 521 end, 522 523 Ts = update_types(I, Ts0, Ds0), 524 Ds = Ds0#{ Dst => I }, 525 opt_is(Is, Ts, Ds, Ls, Fdb, Sub, Meta, [I | Acc]); 526opt_is([#b_set{op=MakeFun,args=Args0,dst=Dst}=I0|Is], 527 Ts0, Ds0, Ls, Fdb0, Sub0, Meta, Acc) when MakeFun =:= make_fun; 528 MakeFun =:= old_make_fun -> 529 Args = simplify_args(Args0, Ts0, Sub0), 530 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 531 532 {I, Fdb} = opt_make_fun(I1, Ts0, Fdb0, Meta), 533 534 Ts = update_types(I, Ts0, Ds0), 535 Ds = Ds0#{ Dst => I }, 536 opt_is(Is, Ts, Ds, Ls, Fdb, Sub0, Meta, [I|Acc]); 537opt_is([I0 | Is], Ts0, Ds0, Ls, Fdb, Sub0, Meta, Acc) -> 538 case simplify(I0, Ts0, Ds0, Ls, Sub0) of 539 {#b_set{}=I, Ts, Ds} -> 540 opt_is(Is, Ts, Ds, Ls, Fdb, Sub0, Meta, [I | Acc]); 541 Sub when is_map(Sub) -> 542 opt_is(Is, Ts0, Ds0, Ls, Fdb, Sub, Meta, Acc) 543 end; 544opt_is([], Ts, Ds, _Ls, Fdb, Sub, _Meta, Acc) -> 545 {reverse(Acc), Ts, Ds, Fdb, Sub}. 546 547opt_local_call(I0, Callee, Args, Dst, Ts, Fdb, Meta) -> 548 ArgTypes = argument_types(Args, Ts), 549 I = opt_local_return(I0, Callee, ArgTypes, Fdb), 550 case Fdb of 551 #{ Callee := #func_info{exported=false,arg_types=AT0}=Info0 } -> 552 %% Update the argument types of *this exact call*, the types 553 %% will be joined later when the callee is optimized. 554 CallId = {Meta#metadata.func_id, Dst}, 555 556 AT = update_arg_types(ArgTypes, AT0, CallId), 557 Info = Info0#func_info{arg_types=AT}, 558 559 {I, Fdb#{ Callee := Info }}; 560 #{} -> 561 %% We can't narrow the argument types of exported functions as they 562 %% can receive anything as part of an external call. We can still 563 %% rely on their return types however. 564 {I, Fdb} 565 end. 566 567%% See sig_make_fun/4 568opt_make_fun(#b_set{op=MakeFun, 569 dst=Dst, 570 args=[#b_local{}=Callee | FreeVars]}=I0, 571 Ts, Fdb, Meta) when MakeFun =:= make_fun; 572 MakeFun =:= old_make_fun -> 573 ArgCount = Callee#b_local.arity - length(FreeVars), 574 FVTypes = [raw_type(FreeVar, Ts) || FreeVar <- FreeVars], 575 ArgTypes = duplicate(ArgCount, any) ++ FVTypes, 576 577 I = opt_local_return(I0, Callee, ArgTypes, Fdb), 578 579 case Fdb of 580 #{ Callee := #func_info{exported=false,arg_types=AT0}=Info0 } -> 581 CallId = {Meta#metadata.func_id, Dst}, 582 583 AT = update_arg_types(ArgTypes, AT0, CallId), 584 Info = Info0#func_info{arg_types=AT}, 585 586 {I, Fdb#{ Callee := Info }}; 587 #{} -> 588 %% We can't narrow the argument types of exported functions as they 589 %% can receive anything as part of an external call. 590 {I, Fdb} 591 end. 592 593opt_local_return(I, Callee, ArgTypes, Fdb) when Fdb =/= #{} -> 594 #func_info{succ_types=SuccTypes} = map_get(Callee, Fdb), 595 case return_type(SuccTypes, ArgTypes) of 596 any -> I; 597 Type -> beam_ssa:add_anno(result_type, Type, I) 598 end; 599opt_local_return(I, _Callee, _ArgTyps, _Fdb) -> 600 %% Module-level optimization is disabled, assume it returns anything. 601 I. 602 603update_arg_types([ArgType | ArgTypes], [TypeMap0 | TypeMaps], CallId) -> 604 TypeMap = TypeMap0#{ CallId => ArgType }, 605 [TypeMap | update_arg_types(ArgTypes, TypeMaps, CallId)]; 606update_arg_types([], [], _CallId) -> 607 []. 608 609%% 610 611-spec opt_finish(Args, Anno, FuncDb) -> {Anno, FuncDb} when 612 Args :: [beam_ssa:b_var()], 613 Anno :: beam_ssa:anno(), 614 FuncDb :: func_info_db(). 615opt_finish(Args, Anno, FuncDb) -> 616 Id = get_func_id(Anno), 617 case FuncDb of 618 #{ Id := #func_info{exported=false,arg_types=ArgTypes} } -> 619 ParamInfo0 = maps:get(parameter_info, Anno, #{}), 620 ParamInfo = opt_finish_1(Args, ArgTypes, ParamInfo0), 621 {Anno#{ parameter_info => ParamInfo }, FuncDb}; 622 #{} -> 623 {Anno, FuncDb} 624 end. 625 626opt_finish_1([Arg | Args], [TypeMap | TypeMaps], Acc0) -> 627 case beam_types:join(maps:values(TypeMap)) of 628 any -> 629 opt_finish_1(Args, TypeMaps, Acc0); 630 JoinedType -> 631 Info = maps:get(Arg, Acc0, []), 632 Acc = Acc0#{ Arg => [{type, JoinedType} | Info] }, 633 opt_finish_1(Args, TypeMaps, Acc) 634 end; 635opt_finish_1([], [], Acc) -> 636 Acc. 637 638%%% 639%%% Optimization helpers 640%%% 641 642simplify_terminator(#b_br{bool=Bool}=Br0, Ts, Ds, Sub) -> 643 Br = beam_ssa:normalize(Br0#b_br{bool=simplify_arg(Bool, Ts, Sub)}), 644 simplify_not(Br, Ts, Ds, Sub); 645simplify_terminator(#b_switch{arg=Arg0,fail=Fail,list=List0}=Sw0, 646 Ts, Ds, Sub) -> 647 Arg = simplify_arg(Arg0, Ts, Sub), 648 %% Ensure that no label in the switch list is the same as the 649 %% failure label. 650 List = [{Val,Lbl} || {Val,Lbl} <- List0, Lbl =/= Fail], 651 case beam_ssa:normalize(Sw0#b_switch{arg=Arg,list=List}) of 652 #b_switch{}=Sw -> 653 case beam_types:is_boolean_type(raw_type(Arg, Ts)) of 654 true -> simplify_switch_bool(Sw, Ts, Ds, Sub); 655 false -> Sw 656 end; 657 #b_br{}=Br -> 658 simplify_terminator(Br, Ts, Ds, Sub) 659 end; 660simplify_terminator(#b_ret{arg=Arg}=Ret, Ts, Ds, Sub) -> 661 %% Reducing the result of a call to a literal (fairly common for 'ok') 662 %% breaks tail call optimization. 663 case Ds of 664 #{ Arg := #b_set{op=call}} -> Ret; 665 #{} -> Ret#b_ret{arg=simplify_arg(Arg, Ts, Sub)} 666 end. 667 668%% 669%% Simplifies an instruction, returning either a new instruction (with updated 670%% type and definition maps), or an updated substitution map if the instruction 671%% was redundant. 672%% 673 674simplify(#b_set{op=phi,dst=Dst,args=Args0}=I0, Ts0, Ds0, Ls, Sub) -> 675 %% Simplify the phi node by removing all predecessor blocks that no 676 %% longer exists or no longer branches to this block. 677 {Type, Args} = simplify_phi_args(Args0, Ls, Sub, none, []), 678 case phi_all_same(Args) of 679 true -> 680 %% Eliminate the phi node if there is just one source 681 %% value or if the values are identical. 682 [{Val, _} | _] = Args, 683 Sub#{ Dst => Val }; 684 false -> 685 I = I0#b_set{args=Args}, 686 687 Ts = Ts0#{ Dst => Type }, 688 Ds = Ds0#{ Dst => I }, 689 {I, Ts, Ds} 690 end; 691simplify(#b_set{op={succeeded,Kind},args=[Arg],dst=Dst}=I0, 692 Ts0, Ds0, _Ls, Sub) -> 693 Type = case will_succeed(I0, Ts0, Ds0, Sub) of 694 yes -> beam_types:make_atom(true); 695 no -> beam_types:make_atom(false); 696 maybe -> beam_types:make_boolean() 697 end, 698 case Type of 699 #t_atom{elements=[true]} -> 700 %% The checked operation always succeeds, so it's safe to remove 701 %% this instruction regardless of whether we're in a guard or not. 702 Lit = #b_literal{val=true}, 703 Sub#{ Dst => Lit }; 704 #t_atom{elements=[false]} when Kind =:= guard -> 705 %% Failing operations are only safe to remove in guards. 706 Lit = #b_literal{val=false}, 707 Sub#{ Dst => Lit }; 708 _ -> 709 true = is_map_key(Arg, Ds0), %Assertion. 710 711 %% Note that we never simplify args; this instruction is specific 712 %% to the operation being checked, and simplifying could break that 713 %% connection. 714 I = beam_ssa:normalize(I0), 715 Ts = Ts0#{ Dst => Type }, 716 Ds = Ds0#{ Dst => I }, 717 {I, Ts, Ds} 718 end; 719simplify(#b_set{op=bs_match,dst=Dst,args=Args0}=I0, Ts0, Ds0, _Ls, Sub) -> 720 Args = simplify_args(Args0, Ts0, Sub), 721 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 722 I2 = case {Args0,Args} of 723 {[_,_,_,#b_var{},_],[Type,Val,Flags,#b_literal{val=all},Unit]} -> 724 %% The size `all` is used for the size of the final binary 725 %% segment in a pattern. Using `all` explicitly is not allowed, 726 %% so we convert it to an obvious invalid size. 727 I1#b_set{args=[Type,Val,Flags,#b_literal{val=bad_size},Unit]}; 728 {_,_} -> 729 I1 730 end, 731 %% We KNOW that simplify/2 will return a #b_set{} record when called with 732 %% a bs_match instruction. 733 #b_set{} = I3 = simplify(I2, Ts0), 734 I = beam_ssa:normalize(I3), 735 Ts = update_types(I, Ts0, Ds0), 736 Ds = Ds0#{ Dst => I }, 737 {I, Ts, Ds}; 738simplify(#b_set{dst=Dst,args=Args0}=I0, Ts0, Ds0, _Ls, Sub) -> 739 Args = simplify_args(Args0, Ts0, Sub), 740 I1 = beam_ssa:normalize(I0#b_set{args=Args}), 741 case simplify(I1, Ts0) of 742 #b_set{}=I2 -> 743 I = beam_ssa:normalize(I2), 744 Ts = update_types(I, Ts0, Ds0), 745 Ds = Ds0#{ Dst => I }, 746 {I, Ts, Ds}; 747 #b_literal{}=Lit -> 748 Sub#{ Dst => Lit }; 749 #b_var{}=Var -> 750 Sub#{ Dst => Var } 751 end. 752 753simplify(#b_set{op={bif,'and'},args=Args}=I, Ts) -> 754 case is_safe_bool_op(Args, Ts) of 755 true -> 756 case Args of 757 [_,#b_literal{val=false}=Res] -> Res; 758 [Res,#b_literal{val=true}] -> Res; 759 _ -> eval_bif(I, Ts) 760 end; 761 false -> 762 I 763 end; 764simplify(#b_set{op={bif,'or'},args=Args}=I, Ts) -> 765 case is_safe_bool_op(Args, Ts) of 766 true -> 767 case Args of 768 [Res,#b_literal{val=false}] -> Res; 769 [_,#b_literal{val=true}=Res] -> Res; 770 _ -> eval_bif(I, Ts) 771 end; 772 false -> 773 I 774 end; 775simplify(#b_set{op={bif,element},args=[#b_literal{val=Index},Tuple]}=I0, Ts) -> 776 case normalized_type(Tuple, Ts) of 777 #t_tuple{size=Size} when is_integer(Index), 778 1 =< Index, 779 Index =< Size -> 780 I = I0#b_set{op=get_tuple_element, 781 args=[Tuple,#b_literal{val=Index-1}]}, 782 simplify(I, Ts); 783 _ -> 784 eval_bif(I0, Ts) 785 end; 786simplify(#b_set{op={bif,hd},args=[List]}=I, Ts) -> 787 case normalized_type(List, Ts) of 788 #t_cons{} -> 789 I#b_set{op=get_hd}; 790 _ -> 791 eval_bif(I, Ts) 792 end; 793simplify(#b_set{op={bif,tl},args=[List]}=I, Ts) -> 794 case normalized_type(List, Ts) of 795 #t_cons{} -> 796 I#b_set{op=get_tl}; 797 _ -> 798 eval_bif(I, Ts) 799 end; 800simplify(#b_set{op={bif,size},args=[Term]}=I, Ts) -> 801 case normalized_type(Term, Ts) of 802 #t_tuple{} -> 803 simplify(I#b_set{op={bif,tuple_size}}, Ts); 804 #t_bitstring{size_unit=U} when U rem 8 =:= 0 -> 805 %% If the bitstring is a binary (the size in bits is 806 %% evenly divisibly by 8), byte_size/1 gives 807 %% the same result as size/1. 808 simplify(I#b_set{op={bif,byte_size}}, Ts); 809 _ -> 810 eval_bif(I, Ts) 811 end; 812simplify(#b_set{op={bif,tuple_size},args=[Term]}=I, Ts) -> 813 case normalized_type(Term, Ts) of 814 #t_tuple{size=Size,exact=true} -> 815 #b_literal{val=Size}; 816 _ -> 817 I 818 end; 819simplify(#b_set{op={bif,is_function},args=[Fun,#b_literal{val=Arity}]}=I, Ts) 820 when is_integer(Arity), Arity >= 0 -> 821 case normalized_type(Fun, Ts) of 822 #t_fun{arity=any} -> 823 I; 824 #t_fun{arity=Arity} -> 825 #b_literal{val=true}; 826 any -> 827 I; 828 _ -> 829 #b_literal{val=false} 830 end; 831simplify(#b_set{op={bif,is_map_key},args=[Key,Map]}=I, Ts) -> 832 case normalized_type(Map, Ts) of 833 #t_map{} -> 834 I#b_set{op=has_map_field,args=[Map,Key]}; 835 _ -> 836 I 837 end; 838simplify(#b_set{op={bif,Op0},args=Args}=I, Ts) when Op0 =:= '=='; 839 Op0 =:= '/=' -> 840 Types = normalized_types(Args, Ts), 841 EqEq0 = case {beam_types:meet(Types),beam_types:join(Types)} of 842 {none,any} -> true; 843 {#t_integer{},#t_integer{}} -> true; 844 {#t_float{},#t_float{}} -> true; 845 {#t_bitstring{},_} -> true; 846 {#t_atom{},_} -> true; 847 {_,_} -> false 848 end, 849 EqEq = EqEq0 orelse any_non_numeric_argument(Args, Ts), 850 case EqEq of 851 true -> 852 Op = case Op0 of 853 '==' -> '=:='; 854 '/=' -> '=/=' 855 end, 856 simplify(I#b_set{op={bif,Op}}, Ts); 857 false -> 858 eval_bif(I, Ts) 859 end; 860simplify(#b_set{op={bif,'=:='},args=[Same,Same]}, _Ts) -> 861 #b_literal{val=true}; 862simplify(#b_set{op={bif,'=:='},args=[LHS,RHS]}=I, Ts) -> 863 LType = raw_type(LHS, Ts), 864 RType = raw_type(RHS, Ts), 865 case beam_types:meet(LType, RType) of 866 none -> 867 #b_literal{val=false}; 868 _ -> 869 case {beam_types:is_boolean_type(LType), 870 beam_types:normalize(RType)} of 871 {true,#t_atom{elements=[true]}} -> 872 %% Bool =:= true ==> Bool 873 LHS; 874 {true,#t_atom{elements=[false]}} -> 875 %% Bool =:= false ==> not Bool 876 %% 877 %% This will be further optimized to eliminate the 878 %% 'not', swapping the success and failure 879 %% branches in the br instruction. If LHS comes 880 %% from a type test (such as is_atom/1) or a 881 %% comparison operator (such as >=) that can be 882 %% translated to test instruction, this 883 %% optimization will eliminate one instruction. 884 simplify(I#b_set{op={bif,'not'},args=[LHS]}, Ts); 885 {_,_} -> 886 eval_bif(I, Ts) 887 end 888 end; 889simplify(#b_set{op={bif,Op},args=Args}=I, Ts) -> 890 Types = normalized_types(Args, Ts), 891 case is_float_op(Op, Types) of 892 false -> 893 eval_bif(I, Ts); 894 true -> 895 AnnoArgs = [anno_float_arg(A) || A <- Types], 896 eval_bif(beam_ssa:add_anno(float_op, AnnoArgs, I), Ts) 897 end; 898simplify(#b_set{op=bs_extract,args=[Ctx]}=I, Ts) -> 899 case raw_type(Ctx, Ts) of 900 #t_bitstring{} -> 901 %% This is a bs_match that has been rewritten as a bs_get_tail; 902 %% just return the input as-is. 903 Ctx; 904 #t_bs_context{} -> 905 I 906 end; 907simplify(#b_set{op=bs_match, 908 args=[#b_literal{val=binary}, Ctx, _Flags, 909 #b_literal{val=all}, 910 #b_literal{val=OpUnit}]}=I, Ts) -> 911 %% <<..., Foo/binary>> can be rewritten as <<..., Foo/bits>> if we know the 912 %% unit is correct. 913 #t_bs_context{tail_unit=CtxUnit} = raw_type(Ctx, Ts), 914 if 915 CtxUnit rem OpUnit =:= 0 -> 916 I#b_set{op=bs_get_tail,args=[Ctx]}; 917 CtxUnit rem OpUnit =/= 0 -> 918 I 919 end; 920simplify(#b_set{op=bs_start_match,args=[#b_literal{val=new}, Src]}=I, Ts) -> 921 case raw_type(Src, Ts) of 922 #t_bs_context{} -> 923 I#b_set{op=bs_start_match,args=[#b_literal{val=resume}, Src]}; 924 _ -> 925 I 926 end; 927simplify(#b_set{op=get_tuple_element,args=[Tuple,#b_literal{val=N}]}=I, Ts) -> 928 #t_tuple{size=Size,elements=Es} = normalized_type(Tuple, Ts), 929 true = Size > N, %Assertion. 930 ElemType = beam_types:get_tuple_element(N + 1, Es), 931 case beam_types:get_singleton_value(ElemType) of 932 {ok, Val} -> #b_literal{val=Val}; 933 error -> I 934 end; 935simplify(#b_set{op=is_nonempty_list,args=[Src]}=I, Ts) -> 936 case normalized_type(Src, Ts) of 937 any -> 938 I; 939 #t_list{} -> 940 I; 941 #t_cons{} -> 942 #b_literal{val=true}; 943 _ -> 944 #b_literal{val=false} 945 end; 946simplify(#b_set{op=is_tagged_tuple, 947 args=[Src,#b_literal{val=Size},#b_literal{}=Tag]}=I, Ts) -> 948 simplify_is_record(I, normalized_type(Src, Ts), Size, Tag, Ts); 949simplify(#b_set{op=put_list,args=[#b_literal{val=H}, 950 #b_literal{val=T}]}, _Ts) -> 951 #b_literal{val=[H|T]}; 952simplify(#b_set{op=put_tuple,args=Args}=I, _Ts) -> 953 case make_literal_list(Args) of 954 none -> I; 955 List -> #b_literal{val=list_to_tuple(List)} 956 end; 957simplify(#b_set{op=call,args=[#b_remote{}=Rem|Args]}=I, Ts) -> 958 case Rem of 959 #b_remote{mod=#b_literal{val=Mod}, 960 name=#b_literal{val=Name}} -> 961 simplify_remote_call(Mod, Name, Args, Ts, I); 962 #b_remote{} -> 963 I 964 end; 965simplify(#b_set{op=call,args=[#b_literal{val=Fun}|Args]}=I, _Ts) 966 when is_function(Fun, length(Args)) -> 967 FI = erlang:fun_info(Fun), 968 {module,M} = keyfind(module, 1, FI), 969 {name,F} = keyfind(name, 1, FI), 970 {arity,A} = keyfind(arity, 1, FI), 971 Rem = #b_remote{mod=#b_literal{val=M}, 972 name=#b_literal{val=F}, 973 arity=A}, 974 I#b_set{args=[Rem|Args]}; 975simplify(#b_set{op=peek_message,args=[#b_literal{val=Val}]}=I, _Ts) -> 976 case Val of 977 none -> 978 I; 979 _ -> 980 %% A potential receive marker has been substituted with a literal, 981 %% which means it can't actually be a marker on this path. Replace 982 %% it with a normal receive. 983 I#b_set{args=[#b_literal{val=none}]} 984 end; 985simplify(#b_set{op=recv_marker_clear,args=[#b_literal{}]}, _Ts) -> 986 %% Not a receive marker: see the 'peek_message' case. 987 #b_literal{val=none}; 988simplify(I, _Ts) -> 989 I. 990 991will_succeed(#b_set{args=[Src]}, Ts, Ds, Sub) -> 992 case {Ds, Ts} of 993 {#{}, #{ Src := none }} -> 994 %% Checked operation never returns. 995 no; 996 {#{ Src := I }, #{}} -> 997 %% There can't be any substitution because the instruction 998 %% is still there. 999 false = is_map_key(Src, Sub), %Assertion. 1000 will_succeed_1(I, Src, Ts, Sub); 1001 {#{}, #{}} -> 1002 %% The checked instruction has been removed and substituted, so we 1003 %% can assume it always succeeds. 1004 true = is_map_key(Src, Sub), %Assertion. 1005 yes 1006 end. 1007 1008will_succeed_1(#b_set{op=bs_get_tail}, _Src, _Ts, _Sub) -> 1009 yes; 1010will_succeed_1(#b_set{op=bs_start_match,args=[_, Arg]}, _Src, Ts, _Sub) -> 1011 ArgType = raw_type(Arg, Ts), 1012 case beam_types:is_bs_matchable_type(ArgType) of 1013 true -> 1014 %% In the future we may be able to remove this instruction 1015 %% altogether when we have a #t_bs_context{}, but for now we need 1016 %% to keep it for compatibility with older releases of OTP. 1017 yes; 1018 false -> 1019 %% Is it at all possible to match? 1020 case beam_types:meet(ArgType, #t_bs_matchable{}) of 1021 none -> no; 1022 _ -> maybe 1023 end 1024 end; 1025 1026will_succeed_1(#b_set{op={bif,Bif},args=BifArgs}, _Src, Ts, _Sub) -> 1027 ArgTypes = normalized_types(BifArgs, Ts), 1028 beam_call_types:will_succeed(erlang, Bif, ArgTypes); 1029will_succeed_1(#b_set{op=call, 1030 args=[#b_remote{mod=#b_literal{val=Mod}, 1031 name=#b_literal{val=Func}} | 1032 CallArgs]}, 1033 _Src, Ts, _Sub) -> 1034 ArgTypes = normalized_types(CallArgs, Ts), 1035 beam_call_types:will_succeed(Mod, Func, ArgTypes); 1036 1037will_succeed_1(#b_set{op=get_hd}, _Src, _Ts, _Sub) -> 1038 yes; 1039will_succeed_1(#b_set{op=get_tl}, _Src, _Ts, _Sub) -> 1040 yes; 1041will_succeed_1(#b_set{op=has_map_field}, _Src, _Ts, _Sub) -> 1042 yes; 1043will_succeed_1(#b_set{op=get_tuple_element}, _Src, _Ts, _Sub) -> 1044 yes; 1045will_succeed_1(#b_set{op=put_tuple}, _Src, _Ts, _Sub) -> 1046 yes; 1047 1048%% Remove the success branch from binary operations with invalid 1049%% sizes. That will remove subsequent bs_put and bs_match instructions, 1050%% which are probably not loadable. 1051will_succeed_1(#b_set{op=bs_add,args=[Arg1,Arg2,_]}, 1052 _Src, _Ts, _Sub) -> 1053 case all(fun(#b_literal{val=Size}) -> is_integer(Size) andalso Size >= 0; 1054 (#b_var{}) -> true 1055 end, [Arg1,Arg2]) of 1056 true -> maybe; 1057 false -> no 1058 end; 1059will_succeed_1(#b_set{op=bs_init, 1060 args=[#b_literal{val=new},#b_literal{val=Size},_Unit]}, 1061 _Src, _Ts, _Sub) -> 1062 if 1063 is_integer(Size), Size >= 0 -> 1064 maybe; 1065 true -> 1066 no 1067 end; 1068will_succeed_1(#b_set{op=bs_init, 1069 args=[#b_literal{},_,#b_literal{val=Size},_Unit]}, 1070 _Src, _Ts, _Sub) -> 1071 if 1072 is_integer(Size), Size >= 0 -> 1073 maybe; 1074 true -> 1075 no 1076 end; 1077will_succeed_1(#b_set{op=bs_match, 1078 args=[#b_literal{val=Type},_,_,#b_literal{val=Size},_]}, 1079 _Src, _Ts, _Sub) -> 1080 if 1081 is_integer(Size), Size >= 0 -> 1082 maybe; 1083 Type =:= binary, Size =:= all -> 1084 %% `all` is a legal size for binary segments at the end of 1085 %% a binary pattern. 1086 maybe; 1087 true -> 1088 %% Invalid size. Matching will fail. 1089 no 1090 end; 1091 1092%% These operations may fail even though we know their return value on success. 1093will_succeed_1(#b_set{op=call}, _Src, _Ts, _Sub) -> 1094 maybe; 1095will_succeed_1(#b_set{op=get_map_element}, _Src, _Ts, _Sub) -> 1096 maybe; 1097will_succeed_1(#b_set{op=wait_timeout}, _Src, _Ts, _Sub) -> 1098 %% It is essential to keep the {succeeded,body} instruction to 1099 %% ensure that the failure edge, which potentially leads to a 1100 %% landingpad, is preserved. If the failure edge is removed, a Y 1101 %% register holding a `try` tag could be reused prematurely. 1102 maybe; 1103 1104will_succeed_1(#b_set{}, _Src, _Ts, _Sub) -> 1105 maybe. 1106 1107simplify_is_record(I, #t_tuple{exact=Exact, 1108 size=Size, 1109 elements=Es}, 1110 RecSize, #b_literal{val=TagVal}=RecTag, Ts) -> 1111 TagType = maps:get(1, Es, any), 1112 TagMatch = case beam_types:get_singleton_value(TagType) of 1113 {ok, TagVal} -> yes; 1114 {ok, _} -> no; 1115 error -> 1116 %% Is it at all possible for the tag to match? 1117 case beam_types:meet(raw_type(RecTag, Ts), TagType) of 1118 none -> no; 1119 _ -> maybe 1120 end 1121 end, 1122 if 1123 Size =/= RecSize, Exact; Size > RecSize; TagMatch =:= no -> 1124 #b_literal{val=false}; 1125 Size =:= RecSize, Exact, TagMatch =:= yes -> 1126 #b_literal{val=true}; 1127 true -> 1128 I 1129 end; 1130simplify_is_record(I, any, _Size, _Tag, _Ts) -> 1131 I; 1132simplify_is_record(_I, _Type, _Size, _Tag, _Ts) -> 1133 #b_literal{val=false}. 1134 1135simplify_switch_bool(#b_switch{arg=B,fail=Fail,list=List0}, Ts, Ds, Sub) -> 1136 FalseVal = #b_literal{val=false}, 1137 TrueVal = #b_literal{val=true}, 1138 List1 = List0 ++ [{FalseVal,Fail},{TrueVal,Fail}], 1139 {_,FalseLbl} = keyfind(FalseVal, 1, List1), 1140 {_,TrueLbl} = keyfind(TrueVal, 1, List1), 1141 Br = #b_br{bool=B,succ=TrueLbl,fail=FalseLbl}, 1142 simplify_terminator(Br, Ts, Ds, Sub). 1143 1144simplify_not(#b_br{bool=#b_var{}=V,succ=Succ,fail=Fail}=Br0, Ts, Ds, Sub) -> 1145 case Ds of 1146 #{V:=#b_set{op={bif,'not'},args=[Bool]}} -> 1147 case beam_types:is_boolean_type(raw_type(Bool, Ts)) of 1148 true -> 1149 Br = Br0#b_br{bool=Bool,succ=Fail,fail=Succ}, 1150 simplify_terminator(Br, Ts, Ds, Sub); 1151 false -> 1152 Br0 1153 end; 1154 #{} -> 1155 Br0 1156 end; 1157simplify_not(#b_br{bool=#b_literal{}}=Br, _Sub, _Ts, _Ds) -> 1158 Br. 1159 1160simplify_phi_args([{Arg0, From} | Rest], Ls, Sub, Type0, Args) -> 1161 case Ls of 1162 #{ From := Outgoing } -> 1163 {outgoing, Ts} = Outgoing, %Assertion. 1164 1165 Arg = simplify_arg(Arg0, Ts, Sub), 1166 Type = beam_types:join(raw_type(Arg, Ts), Type0), 1167 Phi = {Arg, From}, 1168 1169 simplify_phi_args(Rest, Ls, Sub, Type, [Phi | Args]); 1170 #{} -> 1171 simplify_phi_args(Rest, Ls, Sub, Type0, Args) 1172 end; 1173simplify_phi_args([], _Ls, _Sub, Type, Args) -> 1174 %% We return the arguments in their incoming order so that they won't 1175 %% change back and forth and ruin fixpoint iteration in beam_ssa_opt. 1176 {Type, reverse(Args)}. 1177 1178phi_all_same([{Arg, _From} | Phis]) -> 1179 phi_all_same_1(Phis, Arg). 1180 1181phi_all_same_1([{Arg, _From} | Phis], Arg) -> 1182 phi_all_same_1(Phis, Arg); 1183phi_all_same_1([], _Arg) -> 1184 true; 1185phi_all_same_1(_Phis, _Arg) -> 1186 false. 1187 1188simplify_remote_call(erlang, throw, [Term], Ts, I) -> 1189 %% Annotate `throw` instructions with the type of their thrown term, 1190 %% helping `beam_ssa_throw` optimize non-local returns. 1191 Type = normalized_type(Term, Ts), 1192 beam_ssa:add_anno(thrown_type, Type, I); 1193simplify_remote_call(erlang, '++', [#b_literal{val=[]},Tl], _Ts, _I) -> 1194 Tl; 1195simplify_remote_call(erlang, setelement, 1196 [#b_literal{val=Pos}, 1197 #b_literal{val=Tuple}, 1198 #b_var{}=Value], _Ts, I) 1199 when is_integer(Pos), 1 =< Pos, Pos =< tuple_size(Tuple) -> 1200 %% Position is a literal integer and the shape of the 1201 %% tuple is known. 1202 Els0 = [#b_literal{val=El} || El <- tuple_to_list(Tuple)], 1203 {Bef,[_|Aft]} = split(Pos - 1, Els0), 1204 Els = Bef ++ [Value|Aft], 1205 I#b_set{op=put_tuple,args=Els}; 1206simplify_remote_call(Mod, Name, Args, _Ts, I) -> 1207 case erl_bifs:is_pure(Mod, Name, length(Args)) of 1208 true -> 1209 simplify_pure_call(Mod, Name, Args, I); 1210 false -> 1211 I 1212 end. 1213 1214%% Simplify a remote call to a pure BIF. 1215simplify_pure_call(Mod, Name, Args0, I) -> 1216 case make_literal_list(Args0) of 1217 none -> 1218 I; 1219 Args -> 1220 %% The arguments are literals. Try to evaluate the BIF. 1221 try apply(Mod, Name, Args) of 1222 Val -> 1223 case cerl:is_literal_term(Val) of 1224 true -> 1225 #b_literal{val=Val}; 1226 false -> 1227 %% The value can't be expressed as a literal 1228 %% (e.g. a pid). 1229 I 1230 end 1231 catch 1232 _:_ -> 1233 %% Failed. Don't bother trying to optimize 1234 %% the call. 1235 I 1236 end 1237 end. 1238 1239any_non_numeric_argument([#b_literal{val=Lit}|_], _Ts) -> 1240 is_non_numeric(Lit); 1241any_non_numeric_argument([#b_var{}=V|T], Ts) -> 1242 is_non_numeric_type(raw_type(V, Ts)) orelse any_non_numeric_argument(T, Ts); 1243any_non_numeric_argument([], _Ts) -> false. 1244 1245is_non_numeric([H|T]) -> 1246 is_non_numeric(H) andalso is_non_numeric(T); 1247is_non_numeric(Tuple) when is_tuple(Tuple) -> 1248 is_non_numeric_tuple(Tuple, tuple_size(Tuple)); 1249is_non_numeric(Map) when is_map(Map) -> 1250 %% Starting from OTP 18, map keys are compared using `=:=`. 1251 %% Therefore, we only need to check that the values in the map are 1252 %% non-numeric. (Support for compiling BEAM files for OTP releases 1253 %% older than OTP 18 has been dropped.) 1254 is_non_numeric(maps:values(Map)); 1255is_non_numeric(Num) when is_number(Num) -> 1256 false; 1257is_non_numeric(_) -> true. 1258 1259is_non_numeric_tuple(Tuple, El) when El >= 1 -> 1260 is_non_numeric(element(El, Tuple)) andalso 1261 is_non_numeric_tuple(Tuple, El-1); 1262is_non_numeric_tuple(_Tuple, 0) -> true. 1263 1264is_non_numeric_type(#t_atom{}) -> true; 1265is_non_numeric_type(#t_bitstring{}) -> true; 1266is_non_numeric_type(#t_cons{type=Type,terminator=Terminator}) -> 1267 is_non_numeric_type(Type) andalso is_non_numeric_type(Terminator); 1268is_non_numeric_type(#t_list{type=Type,terminator=Terminator}) -> 1269 is_non_numeric_type(Type) andalso is_non_numeric_type(Terminator); 1270is_non_numeric_type(#t_map{super_value=Value}) -> 1271 is_non_numeric_type(Value); 1272is_non_numeric_type(nil) -> true; 1273is_non_numeric_type(#t_tuple{size=Size,exact=true,elements=Types}) 1274 when map_size(Types) =:= Size -> 1275 is_non_numeric_tuple_type(Size, Types); 1276is_non_numeric_type(_) -> false. 1277 1278is_non_numeric_tuple_type(0, _Types) -> 1279 true; 1280is_non_numeric_tuple_type(Pos, Types) -> 1281 is_non_numeric_type(map_get(Pos, Types)) andalso 1282 is_non_numeric_tuple_type(Pos - 1, Types). 1283 1284make_literal_list(Args) -> 1285 make_literal_list(Args, []). 1286 1287make_literal_list([#b_literal{val=H}|T], Acc) -> 1288 make_literal_list(T, [H|Acc]); 1289make_literal_list([_|_], _) -> 1290 none; 1291make_literal_list([], Acc) -> 1292 reverse(Acc). 1293 1294is_safe_bool_op([LHS, RHS], Ts) -> 1295 LType = raw_type(LHS, Ts), 1296 RType = raw_type(RHS, Ts), 1297 beam_types:is_boolean_type(LType) andalso 1298 beam_types:is_boolean_type(RType). 1299 1300eval_bif(#b_set{op={bif,Bif},args=Args}=I, Ts) -> 1301 Arity = length(Args), 1302 case erl_bifs:is_pure(erlang, Bif, Arity) of 1303 false -> 1304 I; 1305 true -> 1306 case make_literal_list(Args) of 1307 none -> 1308 eval_type_test_bif(I, Bif, raw_types(Args, Ts)); 1309 LitArgs -> 1310 try apply(erlang, Bif, LitArgs) of 1311 Val -> #b_literal{val=Val} 1312 catch 1313 error:_ -> I 1314 end 1315 1316 end 1317 end. 1318 1319eval_type_test_bif(I, is_atom, [Type]) -> 1320 eval_type_test_bif_1(I, Type, #t_atom{}); 1321eval_type_test_bif(I, is_binary, [Type]) -> 1322 eval_type_test_bif_1(I, Type, #t_bs_matchable{tail_unit=8}); 1323eval_type_test_bif(I, is_bitstring, [Type]) -> 1324 eval_type_test_bif_1(I, Type, #t_bs_matchable{}); 1325eval_type_test_bif(I, is_boolean, [Type]) -> 1326 case beam_types:is_boolean_type(Type) of 1327 true -> 1328 #b_literal{val=true}; 1329 false -> 1330 case beam_types:meet(Type, #t_atom{}) of 1331 #t_atom{elements=[_|_]=Es} -> 1332 case any(fun is_boolean/1, Es) of 1333 true -> I; 1334 false -> #b_literal{val=false} 1335 end; 1336 #t_atom{} -> 1337 I; 1338 none -> 1339 #b_literal{val=false} 1340 end 1341 end; 1342eval_type_test_bif(I, is_float, [Type]) -> 1343 eval_type_test_bif_1(I, Type, #t_float{}); 1344eval_type_test_bif(I, is_function, [Type]) -> 1345 eval_type_test_bif_1(I, Type, #t_fun{}); 1346eval_type_test_bif(I, is_integer, [Type]) -> 1347 eval_type_test_bif_1(I, Type, #t_integer{}); 1348eval_type_test_bif(I, is_list, [Type]) -> 1349 eval_type_test_bif_1(I, Type, #t_list{}); 1350eval_type_test_bif(I, is_map, [Type]) -> 1351 eval_type_test_bif_1(I, Type, #t_map{}); 1352eval_type_test_bif(I, is_number, [Type]) -> 1353 eval_type_test_bif_1(I, Type, number); 1354eval_type_test_bif(I, is_tuple, [Type]) -> 1355 eval_type_test_bif_1(I, Type, #t_tuple{}); 1356eval_type_test_bif(I, Op, Types) -> 1357 case Types of 1358 [#t_integer{},#t_integer{elements={0,0}}] when Op =:= 'bor'; Op =:= 'bxor' -> 1359 #b_set{args=[Result,_]} = I, 1360 Result; 1361 [#t_integer{},#t_integer{elements={0,0}}] when Op =:= '*'; Op =:= 'band' -> 1362 #b_literal{val=0}; 1363 [T,#t_integer{elements={0,0}}] when Op =:= '+'; Op =:= '-' -> 1364 case beam_types:is_numerical_type(T) of 1365 true -> 1366 #b_set{args=[Result,_]} = I, 1367 Result; 1368 false -> 1369 I 1370 end; 1371 [T,#t_integer{elements={1,1}}] when Op =:= '*'; Op =:= 'div' -> 1372 case beam_types:is_numerical_type(T) of 1373 true -> 1374 #b_set{args=[Result,_]} = I, 1375 Result; 1376 false -> 1377 I 1378 end; 1379 [#t_integer{elements={LMin,LMax}},#t_integer{elements={RMin,RMax}}] -> 1380 case is_inequality_op(Op) of 1381 true -> 1382 case {erlang:Op(LMin, RMin),erlang:Op(LMax, RMin), 1383 erlang:Op(LMin, RMax),erlang:Op(LMax, RMax)} of 1384 {Bool,Bool,Bool,Bool} -> 1385 #b_literal{val=Bool}; 1386 _ -> 1387 I 1388 end; 1389 false -> 1390 I 1391 end; 1392 _ -> 1393 I 1394 end. 1395 1396is_inequality_op('<') -> true; 1397is_inequality_op('=<') -> true; 1398is_inequality_op('>') -> true; 1399is_inequality_op('>=') -> true; 1400is_inequality_op(_) -> false. 1401 1402eval_type_test_bif_1(I, ArgType, Required) -> 1403 case beam_types:meet(ArgType, Required) of 1404 ArgType -> #b_literal{val=true}; 1405 none -> #b_literal{val=false}; 1406 _ -> I 1407 end. 1408 1409simplify_args(Args, Ts, Sub) -> 1410 [simplify_arg(Arg, Ts, Sub) || Arg <- Args]. 1411 1412simplify_arg(#b_var{}=Arg0, Ts, Sub) -> 1413 case sub_arg(Arg0, Sub) of 1414 #b_literal{}=LitArg -> 1415 LitArg; 1416 #b_var{}=Arg -> 1417 case beam_types:get_singleton_value(raw_type(Arg, Ts)) of 1418 {ok, Val} -> #b_literal{val=Val}; 1419 error -> Arg 1420 end 1421 end; 1422simplify_arg(#b_remote{mod=Mod,name=Name}=Rem, Ts, Sub) -> 1423 Rem#b_remote{mod=simplify_arg(Mod, Ts, Sub), 1424 name=simplify_arg(Name, Ts, Sub)}; 1425simplify_arg(Arg, _Ts, _Sub) -> Arg. 1426 1427sub_arg(#b_var{}=Old, Sub) -> 1428 case Sub of 1429 #{Old:=New} -> New; 1430 #{} -> Old 1431 end. 1432 1433is_float_op('-', [#t_float{}]) -> 1434 true; 1435is_float_op('/', [_,_]) -> 1436 true; 1437is_float_op(Op, [#t_float{},_Other]) -> 1438 is_float_op_1(Op); 1439is_float_op(Op, [_Other,#t_float{}]) -> 1440 is_float_op_1(Op); 1441is_float_op(_, _) -> false. 1442 1443is_float_op_1('+') -> true; 1444is_float_op_1('-') -> true; 1445is_float_op_1('*') -> true; 1446is_float_op_1(_) -> false. 1447 1448anno_float_arg(#t_float{}) -> float; 1449anno_float_arg(_) -> convert. 1450 1451%%% 1452%%% Type helpers 1453%%% 1454 1455%% Returns the narrowest possible return type for the given success types and 1456%% arguments. 1457return_type(SuccTypes0, CallArgs0) -> 1458 SuccTypes = st_filter_reachable(SuccTypes0, CallArgs0, [], []), 1459 st_join_return_types(SuccTypes, none). 1460 1461st_filter_reachable([{SuccArgs, {call_self, SelfArgs}}=SuccType | Rest], 1462 CallArgs0, Deferred, Acc) -> 1463 case st_is_reachable(SuccArgs, CallArgs0) of 1464 true -> 1465 %% If we return a call to ourselves, we need to join our current 1466 %% argument types with that of the call to ensure all possible 1467 %% return paths are covered. 1468 CallArgs = parallel_join(SelfArgs, CallArgs0), 1469 st_filter_reachable(Rest, CallArgs, Deferred, Acc); 1470 false -> 1471 %% This may be reachable after we've joined another self-call, so 1472 %% we defer it until we've gone through all other self-calls. 1473 st_filter_reachable(Rest, CallArgs0, [SuccType | Deferred], Acc) 1474 end; 1475st_filter_reachable([SuccType | Rest], CallArgs, Deferred, Acc) -> 1476 st_filter_reachable(Rest, CallArgs, Deferred, [SuccType | Acc]); 1477st_filter_reachable([], CallArgs, Deferred, Acc) -> 1478 case st_any_reachable(Deferred, CallArgs) of 1479 true -> 1480 %% Handle all deferred self calls that may be reachable now that 1481 %% we've expanded our argument types. 1482 st_filter_reachable(Deferred, CallArgs, [], Acc); 1483 false -> 1484 %% We have no reachable self calls, so we know our argument types 1485 %% can't expand any further. Filter out our reachable sites and 1486 %% return. 1487 [ST || {SuccArgs, _}=ST <- Acc, st_is_reachable(SuccArgs, CallArgs)] 1488 end. 1489 1490st_join_return_types([{_SuccArgs, SuccRet} | Rest], Acc0) -> 1491 st_join_return_types(Rest, beam_types:join(SuccRet, Acc0)); 1492st_join_return_types([], Acc) -> 1493 Acc. 1494 1495st_any_reachable([{SuccArgs, _} | SuccType], CallArgs) -> 1496 case st_is_reachable(SuccArgs, CallArgs) of 1497 true -> true; 1498 false -> st_any_reachable(SuccType, CallArgs) 1499 end; 1500st_any_reachable([], _CallArgs) -> 1501 false. 1502 1503st_is_reachable([A | SuccArgs], [B | CallArgs]) -> 1504 case beam_types:meet(A, B) of 1505 none -> false; 1506 _Other -> st_is_reachable(SuccArgs, CallArgs) 1507 end; 1508st_is_reachable([], []) -> 1509 true. 1510 1511update_success_types(#b_ret{arg=Arg}, Ts, Ds, Meta, SuccTypes) -> 1512 #metadata{ func_id=FuncId, 1513 limit_return=Limited, 1514 params=Params } = Meta, 1515 1516 RetType = case Ds of 1517 #{ Arg := #b_set{op=call,args=[FuncId | Args]} } -> 1518 {call_self, argument_types(Args, Ts)}; 1519 #{} -> 1520 argument_type(Arg, Ts) 1521 end, 1522 ArgTypes = argument_types(Params, Ts), 1523 1524 case Limited of 1525 true -> ust_limited(SuccTypes, ArgTypes, RetType); 1526 false -> ust_unlimited(SuccTypes, ArgTypes, RetType) 1527 end; 1528update_success_types(_Last, _Ts, _Ds, _Meta, SuccTypes) -> 1529 SuccTypes. 1530 1531%% See ?RETURN_LIMIT for details. 1532ust_limited(SuccTypes, CallArgs, {call_self, SelfArgs}) -> 1533 NewArgs = parallel_join(CallArgs, SelfArgs), 1534 ust_limited_1(SuccTypes, NewArgs, none); 1535ust_limited(SuccTypes, CallArgs, CallRet) -> 1536 ust_limited_1(SuccTypes, CallArgs, CallRet). 1537 1538ust_limited_1([], ArgTypes, RetType) -> 1539 [{ArgTypes, RetType}]; 1540ust_limited_1([{SuccArgs, SuccRet}], CallArgs, CallRet) -> 1541 NewTypes = parallel_join(SuccArgs, CallArgs), 1542 NewType = beam_types:join(SuccRet, CallRet), 1543 [{NewTypes, NewType}]. 1544 1545%% Adds a new success type. Note that we no longer try to keep the list short 1546%% by combining entries with the same return type, as that can make effective 1547%% return types less specific as analysis goes on, which may cause endless 1548%% loops or render previous optimizations unsafe. 1549%% 1550%% See beam_type_SUITE:success_type_oscillation/1 for more details. 1551ust_unlimited(SuccTypes, _CallArgs, none) -> 1552 %% 'none' is implied since functions can always fail. 1553 SuccTypes; 1554ust_unlimited([{SameArgs, SameType} | _]=SuccTypes, SameArgs, SameType) -> 1555 %% Already covered, return as-is. 1556 SuccTypes; 1557ust_unlimited([SuccType | SuccTypes], CallArgs, CallRet) -> 1558 [SuccType | ust_unlimited(SuccTypes, CallArgs, CallRet)]; 1559ust_unlimited([], CallArgs, CallRet) -> 1560 [{CallArgs, CallRet}]. 1561 1562update_successors(#b_br{bool=#b_literal{val=true},succ=Succ}=Last, 1563 Ts, _Ds, Ls, _UsedOnce) -> 1564 {Last, update_successor(Succ, Ts, Ls)}; 1565update_successors(#b_br{bool=#b_var{}=Bool,succ=Succ,fail=Fail}=Last0, 1566 Ts, Ds, Ls0, UsedOnce) -> 1567 IsTempVar = sets:is_element(Bool, UsedOnce), 1568 case infer_types_br(Bool, Ts, IsTempVar, Ds) of 1569 {#{}=SuccTs, #{}=FailTs} -> 1570 Ls1 = update_successor(Succ, SuccTs, Ls0), 1571 Ls = update_successor(Fail, FailTs, Ls1), 1572 {Last0, Ls}; 1573 {#{}=SuccTs, none} -> 1574 Last = Last0#b_br{bool=#b_literal{val=true},fail=Succ}, 1575 {Last, update_successor(Succ, SuccTs, Ls0)}; 1576 {none, #{}=FailTs} -> 1577 Last = Last0#b_br{bool=#b_literal{val=true},succ=Fail}, 1578 {Last, update_successor(Fail, FailTs, Ls0)} 1579 end; 1580update_successors(#b_switch{arg=#b_var{}=V,fail=Fail0,list=List0}=Last0, 1581 Ts, Ds, Ls0, UsedOnce) -> 1582 IsTempVar = sets:is_element(V, UsedOnce), 1583 1584 {List1, FailTs, Ls1} = 1585 update_switch(List0, V, raw_type(V, Ts), Ts, Ds, Ls0, IsTempVar, []), 1586 1587 case FailTs of 1588 none -> 1589 %% The fail block is unreachable; swap it with one of the choices. 1590 case List1 of 1591 [{#b_literal{val=0},_}|_] -> 1592 %% Swap with the last choice in order to keep the zero the 1593 %% first choice. If the loader can substitute a jump table 1594 %% instruction, then a shorter version of the jump table 1595 %% instruction can be used if the first value is zero. 1596 {List, [{_,Fail}]} = split(length(List1)-1, List1), 1597 Last = Last0#b_switch{fail=Fail,list=List}, 1598 {Last, Ls1}; 1599 [{_,Fail}|List] -> 1600 %% Swap with the first choice in the list. 1601 Last = Last0#b_switch{fail=Fail,list=List}, 1602 {Last, Ls1} 1603 end; 1604 #{} -> 1605 Ls = update_successor(Fail0, FailTs, Ls1), 1606 Last = Last0#b_switch{list=List1}, 1607 {Last, Ls} 1608 end; 1609update_successors(#b_ret{}=Last, _Ts, _Ds, Ls, _UsedOnce) -> 1610 {Last, Ls}. 1611 1612update_switch([{Val, Lbl}=Sw | List], 1613 V, FailType0, Ts, Ds, Ls0, IsTempVar, Acc) -> 1614 FailType = beam_types:subtract(FailType0, raw_type(Val, Ts)), 1615 case infer_types_switch(V, Val, Ts, IsTempVar, Ds) of 1616 none -> 1617 update_switch(List, V, FailType, Ts, Ds, Ls0, IsTempVar, Acc); 1618 SwTs -> 1619 Ls = update_successor(Lbl, SwTs, Ls0), 1620 update_switch(List, V, FailType, Ts, Ds, Ls, IsTempVar, [Sw | Acc]) 1621 end; 1622update_switch([], _V, none, _Ts, _Ds, Ls, _IsTempVar, Acc) -> 1623 %% Fail label is unreachable. 1624 {reverse(Acc), none, Ls}; 1625update_switch([], V, FailType, Ts, Ds, Ls, IsTempVar, Acc) -> 1626 %% Fail label is reachable, see if we can narrow the type down further. 1627 FailTs = case beam_types:get_singleton_value(FailType) of 1628 {ok, Value} -> 1629 %% This is the only possible value at the fail label, so 1630 %% we can infer types as if we matched it directly. 1631 Lit = #b_literal{val=Value}, 1632 infer_types_switch(V, Lit, Ts, IsTempVar, Ds); 1633 error when IsTempVar -> 1634 ts_remove_var(V, Ts); 1635 error -> 1636 Ts#{ V := FailType } 1637 end, 1638 {reverse(Acc), FailTs, Ls}. 1639 1640update_successor(?EXCEPTION_BLOCK, _Ts, Ls) -> 1641 %% We KNOW that no variables are used in the ?EXCEPTION_BLOCK, 1642 %% so there is no need to update the type information. That 1643 %% can be a huge timesaver for huge functions. 1644 Ls; 1645update_successor(S, Ts0, Ls) -> 1646 case Ls of 1647 #{ S := {outgoing, _} } -> 1648 %% We're in a receive loop or similar; the target block will not be 1649 %% revisited. 1650 Ls; 1651 #{ S := {incoming, InTs} } -> 1652 Ts = join_types(Ts0, InTs), 1653 Ls#{ S := {incoming, Ts} }; 1654 #{} -> 1655 Ls#{ S => {incoming, Ts0} } 1656 end. 1657 1658update_types(#b_set{op=Op,dst=Dst,anno=Anno,args=Args}, Ts, Ds) -> 1659 T = type(Op, Args, Anno, Ts, Ds), 1660 Ts#{Dst=>T}. 1661 1662type({bif,Bif}, Args, _Anno, Ts, _Ds) -> 1663 ArgTypes = normalized_types(Args, Ts), 1664 {RetType, _, _} = beam_call_types:types(erlang, Bif, ArgTypes), 1665 RetType; 1666type(bs_init, _Args, _Anno, _Ts, _Ds) -> 1667 #t_bitstring{}; 1668type(bs_extract, [Ctx], _Anno, _Ts, Ds) -> 1669 #b_set{op=bs_match,args=Args} = map_get(Ctx, Ds), 1670 bs_match_type(Args); 1671type(bs_start_match, [_, Src], _Anno, Ts, _Ds) -> 1672 case beam_types:meet(#t_bs_matchable{}, raw_type(Src, Ts)) of 1673 none -> 1674 none; 1675 T -> 1676 Unit = beam_types:get_bs_matchable_unit(T), 1677 #t_bs_context{tail_unit=Unit} 1678 end; 1679type(bs_match, [#b_literal{val=binary}, Ctx, _Flags, 1680 #b_literal{val=all}, #b_literal{val=OpUnit}], 1681 _Anno, Ts, _Ds) -> 1682 1683 %% This is an explicit tail unit test which does not advance the match 1684 %% position. 1685 CtxType = raw_type(Ctx, Ts), 1686 OpType = #t_bs_context{tail_unit=OpUnit}, 1687 1688 beam_types:meet(CtxType, OpType); 1689type(bs_match, Args, _Anno, Ts, _Ds) -> 1690 [_, Ctx | _] = Args, 1691 1692 %% Matches advance the current position without testing the tail unit. We 1693 %% try to retain unit information by taking the GCD of our current unit and 1694 %% the increments we know the match will advance by. 1695 #t_bs_context{tail_unit=CtxUnit} = raw_type(Ctx, Ts), 1696 OpUnit = bs_match_stride(Args, Ts), 1697 1698 #t_bs_context{tail_unit=gcd(OpUnit, CtxUnit)}; 1699type(bs_get_tail, [Ctx], _Anno, Ts, _Ds) -> 1700 #t_bs_context{tail_unit=Unit} = raw_type(Ctx, Ts), 1701 #t_bitstring{size_unit=Unit}; 1702type(call, [#b_remote{mod=#b_literal{val=Mod}, 1703 name=#b_literal{val=Name}}|Args], _Anno, Ts, _Ds) -> 1704 ArgTypes = normalized_types(Args, Ts), 1705 {RetType, _, _} = beam_call_types:types(Mod, Name, ArgTypes), 1706 RetType; 1707type(call, [#b_remote{} | _Args], _Anno, _Ts, _Ds) -> 1708 %% Remote call with variable Module and/or Function. 1709 any; 1710type(call, [#b_local{} | _Args], Anno, _Ts, _Ds) -> 1711 case Anno of 1712 #{ result_type := Type } -> Type; 1713 #{} -> any 1714 end; 1715type(call, [#b_var{} | _Args], Anno, _Ts, _Ds) -> 1716 case Anno of 1717 #{ result_type := Type } -> Type; 1718 #{} -> any 1719 end; 1720type(call, [#b_literal{val=Fun} | Args], _Anno, _Ts, _Ds) -> 1721 case is_function(Fun, length(Args)) of 1722 true -> 1723 %% This is an external fun literal (fun M:F/A). 1724 any; 1725 false -> 1726 %% This is either not a fun literal or the number of 1727 %% arguments is wrong. 1728 none 1729 end; 1730type(extract, [V, #b_literal{val=Idx}], _Anno, _Ts, Ds) -> 1731 case map_get(V, Ds) of 1732 #b_set{op=landingpad} when Idx =:= 0 -> 1733 %% Class 1734 #t_atom{elements=[error,exit,throw]}; 1735 #b_set{op=landingpad} when Idx =:= 1 -> 1736 %% Reason 1737 any; 1738 #b_set{op=landingpad} when Idx =:= 2 -> 1739 %% Stack trace 1740 any 1741 end; 1742type(get_hd, [Src], _Anno, Ts, _Ds) -> 1743 SrcType = #t_cons{} = normalized_type(Src, Ts), %Assertion. 1744 {RetType, _, _} = beam_call_types:types(erlang, hd, [SrcType]), 1745 RetType; 1746type(get_tl, [Src], _Anno, Ts, _Ds) -> 1747 SrcType = #t_cons{} = normalized_type(Src, Ts), %Assertion. 1748 {RetType, _, _} = beam_call_types:types(erlang, tl, [SrcType]), 1749 RetType; 1750type(get_map_element, [_, _]=Args0, _Anno, Ts, _Ds) -> 1751 [#t_map{}=Map, Key] = normalized_types(Args0, Ts), %Assertion. 1752 {RetType, _, _} = beam_call_types:types(erlang, map_get, [Key, Map]), 1753 RetType; 1754type(get_tuple_element, [Tuple, Offset], _Anno, Ts, _Ds) -> 1755 #t_tuple{size=Size,elements=Es} = normalized_type(Tuple, Ts), 1756 #b_literal{val=N} = Offset, 1757 true = Size > N, %Assertion. 1758 beam_types:get_tuple_element(N + 1, Es); 1759type(has_map_field, [_, _]=Args0, _Anno, Ts, _Ds) -> 1760 [#t_map{}=Map, Key] = normalized_types(Args0, Ts), %Assertion. 1761 {RetType, _, _} = beam_call_types:types(erlang, is_map_key, [Key, Map]), 1762 RetType; 1763type(is_nonempty_list, [_], _Anno, _Ts, _Ds) -> 1764 beam_types:make_boolean(); 1765type(is_tagged_tuple, [_,#b_literal{},#b_literal{}], _Anno, _Ts, _Ds) -> 1766 beam_types:make_boolean(); 1767type(MakeFun, [#b_local{arity=TotalArity} | Env], Anno, _Ts, _Ds) 1768 when MakeFun =:= make_fun; 1769 MakeFun =:= old_make_fun -> 1770 RetType = case Anno of 1771 #{ result_type := Type } -> Type; 1772 #{} -> any 1773 end, 1774 #t_fun{arity=TotalArity - length(Env), type=RetType}; 1775type(put_map, [_Kind, Map | Ss], _Anno, Ts, _Ds) -> 1776 put_map_type(Map, Ss, Ts); 1777type(put_list, [Head, Tail], _Anno, Ts, _Ds) -> 1778 HeadType = raw_type(Head, Ts), 1779 TailType = raw_type(Tail, Ts), 1780 beam_types:make_cons(HeadType, TailType); 1781type(put_tuple, Args, _Anno, Ts, _Ds) -> 1782 {Es, _} = foldl(fun(Arg, {Es0, Index}) -> 1783 Type = raw_type(Arg, Ts), 1784 Es = beam_types:set_tuple_element(Index, Type, Es0), 1785 {Es, Index + 1} 1786 end, {#{}, 1}, Args), 1787 #t_tuple{exact=true,size=length(Args),elements=Es}; 1788type(resume, [_, _], _Anno, _Ts, _Ds) -> 1789 none; 1790type(wait_timeout, [#b_literal{val=infinity}], _Anno, _Ts, _Ds) -> 1791 %% Waits forever, never reaching the 'after' block. 1792 beam_types:make_atom(false); 1793type(_, _, _, _, _) -> 1794 any. 1795 1796put_map_type(Map, Ss, Ts) -> 1797 pmt_1(Ss, Ts, normalized_type(Map, Ts)). 1798 1799pmt_1([Key0, Value0 | Ss], Ts, Acc0) -> 1800 Key = normalized_type(Key0, Ts), 1801 Value = normalized_type(Value0, Ts), 1802 {Acc, _, _} = beam_call_types:types(maps, put, [Key, Value, Acc0]), 1803 pmt_1(Ss, Ts, Acc); 1804pmt_1([], _Ts, Acc) -> 1805 Acc. 1806 1807%% We seldom know how far a match operation may advance, but we can often tell 1808%% which increment it will advance by. 1809bs_match_stride([#b_literal{val=Type} | Args], Ts) -> 1810 bs_match_stride(Type, Args, Ts). 1811 1812bs_match_stride(_, [_,_,Size,#b_literal{val=Unit}], Ts) -> 1813 case raw_type(Size, Ts) of 1814 #t_integer{elements={Sz, Sz}} when is_integer(Sz) -> 1815 Sz * Unit; 1816 _ -> 1817 Unit 1818 end; 1819bs_match_stride(string, [_,#b_literal{val=String}], _) -> 1820 bit_size(String); 1821bs_match_stride(utf8, _, _) -> 1822 8; 1823bs_match_stride(utf16, _, _) -> 1824 16; 1825bs_match_stride(utf32, _, _) -> 1826 32; 1827bs_match_stride(_, _, _) -> 1828 1. 1829 1830-define(UNICODE_MAX, (16#10FFFF)). 1831 1832bs_match_type([#b_literal{val=Type}|Args]) -> 1833 bs_match_type(Type, Args). 1834 1835bs_match_type(binary, Args) -> 1836 [_,_,_,#b_literal{val=U}] = Args, 1837 #t_bitstring{size_unit=U}; 1838bs_match_type(float, _) -> 1839 #t_float{}; 1840bs_match_type(integer, Args) -> 1841 case Args of 1842 [_, 1843 #b_literal{val=Flags}, 1844 #b_literal{val=Size}, 1845 #b_literal{val=Unit}] when Size * Unit < 64 -> 1846 NumBits = Size * Unit, 1847 case member(unsigned, Flags) of 1848 true -> 1849 beam_types:make_integer(0, (1 bsl NumBits)-1); 1850 false -> 1851 %% Signed integer. Don't bother. 1852 #t_integer{} 1853 end; 1854 [_|_] -> 1855 #t_integer{} 1856 end; 1857bs_match_type(skip, _) -> 1858 any; 1859bs_match_type(string, _) -> 1860 any; 1861bs_match_type(utf8, _) -> 1862 beam_types:make_integer(0, ?UNICODE_MAX); 1863bs_match_type(utf16, _) -> 1864 beam_types:make_integer(0, ?UNICODE_MAX); 1865bs_match_type(utf32, _) -> 1866 beam_types:make_integer(0, ?UNICODE_MAX). 1867 1868normalized_types(Values, Ts) -> 1869 [normalized_type(Val, Ts) || Val <- Values]. 1870 1871normalized_type(V, Ts) -> 1872 beam_types:normalize(raw_type(V, Ts)). 1873 1874argument_types(Values, Ts) -> 1875 [argument_type(Val, Ts) || Val <- Values]. 1876 1877-spec argument_type(beam_ssa:value(), type_db()) -> type(). 1878 1879argument_type(V, Ts) -> 1880 beam_types:limit_depth(raw_type(V, Ts)). 1881 1882raw_types(Values, Ts) -> 1883 [raw_type(Val, Ts) || Val <- Values]. 1884 1885-spec raw_type(beam_ssa:value(), type_db()) -> type(). 1886 1887raw_type(#b_literal{val=Value}, _Ts) -> 1888 beam_types:make_type_from_value(Value); 1889raw_type(V, Ts) -> 1890 map_get(V, Ts). 1891 1892%% infer_types(Var, Types, #d{}) -> {SuccTypes,FailTypes} 1893%% Looking at the expression that defines the variable Var, infer 1894%% the types for the variables in the arguments. Return the updated 1895%% type database for the case that the expression evaluates to 1896%% true, and and for the case that it evaluates to false. 1897%% 1898%% Here is an example. The variable being asked about is 1899%% the variable Bool, which is defined like this: 1900%% 1901%% Bool = is_nonempty_list L 1902%% 1903%% If 'is_nonempty_list L' evaluates to 'true', L must 1904%% must be cons. The meet of the previously known type of L and 'cons' 1905%% will be added to SuccTypes. 1906%% 1907%% On the other hand, if 'is_nonempty_list L' evaluates to false, L 1908%% is not cons and cons can be subtracted from the previously known 1909%% type for L. For example, if L was known to be 'list', subtracting 1910%% 'cons' would give 'nil' as the only possible type. The result of the 1911%% subtraction for L will be added to FailTypes. 1912 1913infer_types_br(#b_var{}=V, Ts, IsTempVar, Ds) -> 1914 #{V:=#b_set{op=Op,args=Args}} = Ds, 1915 1916 {PosTypes, NegTypes} = infer_type(Op, Args, Ts, Ds), 1917 1918 SuccTs0 = meet_types(PosTypes, Ts), 1919 FailTs0 = subtract_types(NegTypes, Ts), 1920 1921 case IsTempVar of 1922 true -> 1923 %% The branch variable is defined in this block and is only 1924 %% referenced by this terminator. Therefore, there is no need to 1925 %% include it in the type database passed on to the successors of 1926 %% of this block. 1927 SuccTs = ts_remove_var(V, SuccTs0), 1928 FailTs = ts_remove_var(V, FailTs0), 1929 {SuccTs, FailTs}; 1930 false -> 1931 SuccTs = infer_br_value(V, true, SuccTs0), 1932 FailTs = infer_br_value(V, false, FailTs0), 1933 {SuccTs, FailTs} 1934 end. 1935 1936infer_br_value(_V, _Bool, none) -> 1937 none; 1938infer_br_value(V, Bool, NewTs) -> 1939 #{ V := T } = NewTs, 1940 case beam_types:is_boolean_type(T) of 1941 true -> 1942 NewTs#{ V := beam_types:make_atom(Bool) }; 1943 false -> 1944 %% V is a try/catch tag or similar, leave it alone. 1945 NewTs 1946 end. 1947 1948infer_types_switch(V, Lit, Ts0, IsTempVar, Ds) -> 1949 {PosTypes, _} = infer_type({bif,'=:='}, [V, Lit], Ts0, Ds), 1950 Ts = meet_types(PosTypes, Ts0), 1951 case IsTempVar of 1952 true -> ts_remove_var(V, Ts); 1953 false -> Ts 1954 end. 1955 1956ts_remove_var(_V, none) -> none; 1957ts_remove_var(V, Ts) -> maps:remove(V, Ts). 1958 1959infer_type({succeeded,_}, [#b_var{}=Src], Ts, Ds) -> 1960 #b_set{op=Op,args=Args} = maps:get(Src, Ds), 1961 infer_success_type(Op, Args, Ts, Ds); 1962 1963%% Type tests are handled separately from other BIFs as we're inferring types 1964%% based on their result, so we know that subtraction is safe even if we're 1965%% not branching on 'succeeded'. 1966infer_type(is_tagged_tuple, [#b_var{}=Src,#b_literal{val=Size}, 1967 #b_literal{}=Tag], _Ts, _Ds) -> 1968 Es = beam_types:set_tuple_element(1, raw_type(Tag, #{}), #{}), 1969 T = {Src,#t_tuple{exact=true,size=Size,elements=Es}}, 1970 {[T], [T]}; 1971infer_type(is_nonempty_list, [#b_var{}=Src], _Ts, _Ds) -> 1972 T = {Src,#t_cons{}}, 1973 {[T], [T]}; 1974infer_type({bif,is_atom}, [Arg], _Ts, _Ds) -> 1975 T = {Arg, #t_atom{}}, 1976 {[T], [T]}; 1977infer_type({bif,is_binary}, [Arg], _Ts, _Ds) -> 1978 T = {Arg, #t_bitstring{size_unit=8}}, 1979 {[T], [T]}; 1980infer_type({bif,is_bitstring}, [Arg], _Ts, _Ds) -> 1981 T = {Arg, #t_bitstring{}}, 1982 {[T], [T]}; 1983infer_type({bif,is_boolean}, [Arg], _Ts, _Ds) -> 1984 T = {Arg, beam_types:make_boolean()}, 1985 {[T], [T]}; 1986infer_type({bif,is_float}, [Arg], _Ts, _Ds) -> 1987 T = {Arg, #t_float{}}, 1988 {[T], [T]}; 1989infer_type({bif,is_integer}, [Arg], _Ts, _Ds) -> 1990 T = {Arg, #t_integer{}}, 1991 {[T], [T]}; 1992infer_type({bif,is_list}, [Arg], _Ts, _Ds) -> 1993 T = {Arg, #t_list{}}, 1994 {[T], [T]}; 1995infer_type({bif,is_map}, [Arg], _Ts, _Ds) -> 1996 T = {Arg, #t_map{}}, 1997 {[T], [T]}; 1998infer_type({bif,is_number}, [Arg], _Ts, _Ds) -> 1999 T = {Arg, number}, 2000 {[T], [T]}; 2001infer_type({bif,is_tuple}, [Arg], _Ts, _Ds) -> 2002 T = {Arg, #t_tuple{}}, 2003 {[T], [T]}; 2004infer_type({bif,'=:='}, [#b_var{}=LHS,#b_var{}=RHS], Ts, _Ds) -> 2005 %% As an example, assume that L1 is known to be 'list', and L2 is 2006 %% known to be 'cons'. Then if 'L1 =:= L2' evaluates to 'true', it can 2007 %% be inferred that L1 is 'cons' (the meet of 'cons' and 'list'). 2008 LType = raw_type(LHS, Ts), 2009 RType = raw_type(RHS, Ts), 2010 Type = beam_types:meet(LType, RType), 2011 2012 PosTypes = [{V,Type} || {V, OrigType} <- [{LHS, LType}, {RHS, RType}], 2013 OrigType =/= Type], 2014 2015 %% We must be careful with types inferred from '=:='. 2016 %% 2017 %% If we have seen L =:= [a], we know that L is 'cons' if the 2018 %% comparison succeeds. However, if the comparison fails, L could 2019 %% still be 'cons'. Therefore, we must not subtract 'cons' from the 2020 %% previous type of L. 2021 %% 2022 %% However, it is safe to subtract a type inferred from '=:=' if 2023 %% it is single-valued, e.g. if it is [] or the atom 'true'. 2024 %% 2025 %% Note that we subtract the left-hand type from the right-hand 2026 %% value and vice versa. We must not subtract the meet of the two 2027 %% as it may be too specific. See beam_type_SUITE:type_subtraction/1 2028 %% for details. 2029 NegTypes = [T || {_, OtherType}=T <- [{RHS, LType}, {LHS, RType}], 2030 beam_types:is_singleton_type(OtherType)], 2031 2032 {PosTypes, NegTypes}; 2033infer_type({bif,'=:='}, [#b_var{}=Src,#b_literal{}=Lit], Ts, Ds) -> 2034 Def = maps:get(Src, Ds), 2035 LitType = raw_type(Lit, Ts), 2036 PosTypes = [{Src, LitType} | infer_eq_lit(Def, LitType)], 2037 2038 %% Subtraction is only safe if LitType is single-valued. 2039 NegTypes = case beam_types:is_singleton_type(LitType) of 2040 true -> PosTypes; 2041 false -> [] 2042 end, 2043 2044 {PosTypes, NegTypes}; 2045infer_type(_Op, _Args, _Ts, _Ds) -> 2046 {[], []}. 2047 2048infer_success_type({bif,Op}, Args, Ts, _Ds) -> 2049 ArgTypes = normalized_types(Args, Ts), 2050 2051 {_, PosTypes0, CanSubtract} = beam_call_types:types(erlang, Op, ArgTypes), 2052 PosTypes = [T || {#b_var{},_}=T <- zip(Args, PosTypes0)], 2053 2054 case CanSubtract of 2055 true -> {PosTypes, PosTypes}; 2056 false -> {PosTypes, []} 2057 end; 2058infer_success_type(call, [#b_var{}=Fun|Args], _Ts, _Ds) -> 2059 T = {Fun, #t_fun{arity=length(Args)}}, 2060 {[T], []}; 2061infer_success_type(bs_start_match, [_, #b_var{}=Src], _Ts, _Ds) -> 2062 T = {Src,#t_bs_matchable{}}, 2063 {[T], [T]}; 2064infer_success_type(bs_match, [#b_literal{val=binary}, 2065 Ctx, _Flags, 2066 #b_literal{val=all}, 2067 #b_literal{val=OpUnit}], 2068 _Ts, _Ds) -> 2069 %% This is an explicit tail unit test which does not advance the match 2070 %% position, so we know that Ctx has the same unit. 2071 T = {Ctx, #t_bs_context{tail_unit=OpUnit}}, 2072 {[T], [T]}; 2073infer_success_type(_Op, _Args, _Ts, _Ds) -> 2074 {[], []}. 2075 2076infer_eq_lit(#b_set{op={bif,tuple_size},args=[#b_var{}=Tuple]}, 2077 #t_integer{elements={Size,Size}}) -> 2078 [{Tuple,#t_tuple{exact=true,size=Size}}]; 2079infer_eq_lit(#b_set{op=get_tuple_element, 2080 args=[#b_var{}=Tuple,#b_literal{val=N}]}, 2081 LitType) -> 2082 Index = N + 1, 2083 case beam_types:set_tuple_element(Index, LitType, #{}) of 2084 #{ Index := _ }=Es -> 2085 [{Tuple,#t_tuple{size=Index,elements=Es}}]; 2086 #{} -> 2087 %% Index was above the element limit; subtraction is not safe. 2088 [] 2089 end; 2090infer_eq_lit(_, _) -> 2091 []. 2092 2093join_types(Ts, Ts) -> 2094 Ts; 2095join_types(LHS, RHS) -> 2096 if 2097 map_size(LHS) < map_size(RHS) -> 2098 join_types_1(maps:keys(LHS), RHS, LHS); 2099 true -> 2100 join_types_1(maps:keys(RHS), LHS, RHS) 2101 end. 2102 2103%% Joins two type maps, keeping the variables that are common to both maps. 2104join_types_1([V | Vs], Bigger, Smaller) -> 2105 case {Bigger, Smaller} of 2106 {#{ V := Same }, #{ V := Same }} -> 2107 join_types_1(Vs, Bigger, Smaller); 2108 {#{ V := LHS }, #{ V := RHS }} -> 2109 T = beam_types:join(LHS, RHS), 2110 join_types_1(Vs, Bigger, Smaller#{ V := T }); 2111 {#{}, #{ V := _ }} -> 2112 join_types_1(Vs, Bigger, maps:remove(V, Smaller)) 2113 end; 2114join_types_1([], _Bigger, Smaller) -> 2115 Smaller. 2116 2117meet_types([{V,T0}|Vs], Ts) -> 2118 #{V:=T1} = Ts, 2119 case beam_types:meet(T0, T1) of 2120 none -> none; 2121 T1 -> meet_types(Vs, Ts); 2122 T -> meet_types(Vs, Ts#{V:=T}) 2123 end; 2124meet_types([], Ts) -> Ts. 2125 2126subtract_types([{V,T0}|Vs], Ts) -> 2127 #{V:=T1} = Ts, 2128 case beam_types:subtract(T1, T0) of 2129 none -> none; 2130 T1 -> subtract_types(Vs, Ts); 2131 T -> subtract_types(Vs, Ts#{V:=T}) 2132 end; 2133subtract_types([], Ts) -> Ts. 2134 2135parallel_join([A | As], [B | Bs]) -> 2136 [beam_types:join(A, B) | parallel_join(As, Bs)]; 2137parallel_join([], []) -> 2138 []. 2139 2140gcd(A, B) -> 2141 case A rem B of 2142 0 -> B; 2143 X -> gcd(B, X) 2144 end. 2145 2146%%% 2147%%% Helpers 2148%%% 2149 2150init_metadata(FuncId, Linear, Params) -> 2151 {RetCounter, Map0} = init_metadata_1(reverse(Linear), 0, #{}), 2152 Map = maps:without(Params, Map0), 2153 UsedOnce = sets:from_list(maps:keys(Map), [{version, 2}]), 2154 2155 #metadata{ func_id = FuncId, 2156 limit_return = (RetCounter >= ?RETURN_LIMIT), 2157 params = Params, 2158 used_once = UsedOnce }. 2159 2160init_metadata_1([{L,#b_blk{is=Is,last=Last}} | Bs], RetCounter0, Uses0) -> 2161 %% Track the number of return terminators in use. See ?RETURN_LIMIT for 2162 %% details. 2163 RetCounter = case Last of 2164 #b_ret{} -> RetCounter0 + 1; 2165 _ -> RetCounter0 2166 end, 2167 2168 %% Calculate the set of variables that are only used once in the terminator 2169 %% of the block that defines them. That will allow us to discard type 2170 %% information discard type information for variables that will never be 2171 %% referenced by the successor blocks, potentially improving compilation 2172 %% times. 2173 2174 Uses1 = used_once_last_uses(beam_ssa:used(Last), L, Uses0), 2175 Uses = used_once_2(reverse(Is), L, Uses1), 2176 init_metadata_1(Bs, RetCounter, Uses); 2177init_metadata_1([], RetCounter, Uses) -> 2178 {RetCounter, Uses}. 2179 2180used_once_2([#b_set{dst=Dst}=I|Is], L, Uses0) -> 2181 Uses = used_once_uses(beam_ssa:used(I), L, Uses0), 2182 case Uses of 2183 #{Dst:=[L]} -> 2184 used_once_2(Is, L, Uses); 2185 #{} -> 2186 %% Used more than once or used once in 2187 %% in another block. 2188 used_once_2(Is, L, maps:remove(Dst, Uses)) 2189 end; 2190used_once_2([], _, Uses) -> Uses. 2191 2192used_once_uses([V|Vs], L, Uses) -> 2193 case Uses of 2194 #{V:=more_than_once} -> 2195 used_once_uses(Vs, L, Uses); 2196 #{} -> 2197 %% Already used or first use is not in 2198 %% a terminator. 2199 used_once_uses(Vs, L, Uses#{V=>more_than_once}) 2200 end; 2201used_once_uses([], _, Uses) -> Uses. 2202 2203used_once_last_uses([V|Vs], L, Uses) -> 2204 case Uses of 2205 #{V:=[_]} -> 2206 %% Second time this variable is used. 2207 used_once_last_uses(Vs, L, Uses#{V:=more_than_once}); 2208 #{V:=more_than_once} -> 2209 %% Used at least twice before. 2210 used_once_last_uses(Vs, L, Uses); 2211 #{} -> 2212 %% First time this variable is used. 2213 used_once_last_uses(Vs, L, Uses#{V=>[L]}) 2214 end; 2215used_once_last_uses([], _, Uses) -> Uses. 2216 2217%% 2218%% Ordered worklist used in signatures/2. 2219%% 2220%% This is equivalent to consing (wl_add) and appending (wl_defer_list) 2221%% to a regular list, but avoids uneccessary work by reordering elements. 2222%% 2223%% We can do this since a function only needs to be visited *once* for all 2224%% prior updates to take effect, so if an element is added to the front, then 2225%% all earlier instances of the same element are redundant. 2226%% 2227 2228-record(worklist, 2229 { counter = 0 :: integer(), 2230 elements = gb_trees:empty() :: gb_trees:tree(integer(), term()), 2231 indexes = #{} :: #{ term() => integer() } }). 2232 2233-type worklist() :: #worklist{}. 2234 2235wl_new() -> #worklist{}. 2236 2237%% Adds an element to the worklist, or moves it to the front if it's already 2238%% present. 2239wl_add(Element, #worklist{counter=Counter,elements=Es,indexes=Is}) -> 2240 case Is of 2241 #{ Element := Index } -> 2242 wl_add_1(Element, Counter, gb_trees:delete(Index, Es), Is); 2243 #{} -> 2244 wl_add_1(Element, Counter, Es, Is) 2245 end. 2246 2247wl_add_1(Element, Counter0, Es0, Is0) -> 2248 Counter = Counter0 + 1, 2249 Es = gb_trees:insert(Counter, Element, Es0), 2250 Is = Is0#{ Element => Counter }, 2251 #worklist{counter=Counter,elements=Es,indexes=Is}. 2252 2253%% All mutations bump the counter, so we can check for changes without a deep 2254%% comparison. 2255wl_changed(#worklist{counter=Same}, #worklist{counter=Same}) -> false; 2256wl_changed(#worklist{}, #worklist{}) -> true. 2257 2258%% Adds the given elements to the back of the worklist, skipping the elements 2259%% that are already present. This lets us append elements arbitrarly after the 2260%% current front without changing the work order. 2261wl_defer_list(Elements, #worklist{counter=Counter,elements=Es,indexes=Is}) -> 2262 wl_defer_list_1(Elements, Counter, Es, Is). 2263 2264wl_defer_list_1([Element | Elements], Counter0, Es0, Is0) -> 2265 case Is0 of 2266 #{ Element := _ } -> 2267 wl_defer_list_1(Elements, Counter0, Es0, Is0); 2268 #{} -> 2269 Counter = Counter0 + 1, 2270 Es = gb_trees:insert(-Counter, Element, Es0), 2271 Is = Is0#{ Element => -Counter }, 2272 wl_defer_list_1(Elements, Counter, Es, Is) 2273 end; 2274wl_defer_list_1([], Counter, Es, Is) -> 2275 #worklist{counter=Counter,elements=Es,indexes=Is}. 2276 2277wl_next(#worklist{indexes=Is}) when Is =:= #{} -> 2278 empty; 2279wl_next(#worklist{elements=Es,indexes=Is}) when Is =/= #{} -> 2280 {_Key, Element} = gb_trees:largest(Es), 2281 {ok, Element}. 2282 2283%% Removes the front of the worklist. 2284wl_pop(Element, #worklist{counter=Counter0,elements=Es0,indexes=Is0}=Wl) -> 2285 Counter = Counter0 + 1, 2286 {_Key, Element, Es} = gb_trees:take_largest(Es0), %Assertion. 2287 Is = maps:remove(Element, Is0), 2288 Wl#worklist{counter=Counter,elements=Es,indexes=Is}. 2289