1%% 2%% %CopyrightBegin% 3%% 4%% Copyright Ericsson AB 1999-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%% Purpose : Code generator for Beam. 21 22-module(v3_codegen). 23 24%% The main interface. 25-export([module/2]). 26 27-import(lists, [member/2,keymember/3,keysort/2,keydelete/3, 28 append/1,flatmap/2,filter/2,foldl/3,foldr/3,mapfoldl/3, 29 sort/1,reverse/1,reverse/2,map/2]). 30-import(ordsets, [add_element/2,intersection/2,union/2]). 31 32-include("v3_kernel.hrl"). 33 34%% These are not defined in v3_kernel.hrl. 35get_kanno(Kthing) -> element(2, Kthing). 36set_kanno(Kthing, Anno) -> setelement(2, Kthing, Anno). 37 38%% Main codegen structure. 39-record(cg, {lcount=1, %Label counter 40 bfail, %Fail label for BIFs 41 break, %Break label 42 recv, %Receive label 43 is_top_block, %Boolean: top block or not 44 functable=#{}, %Map of local functions: {Name,Arity}=>Label 45 in_catch=false, %Inside a catch or not. 46 need_frame, %Need a stack frame. 47 ultimate_failure, %Label for ultimate match failure. 48 ctx %Match context. 49 }). 50 51%% Stack/register state record. 52-record(sr, {reg=[], %Register table 53 stk=[], %Stack table 54 res=[]}). %Registers to reserve 55 56%% Internal records. 57-record(cg_need_heap, {anno=[] :: term(), 58 h=0 :: integer()}). 59-record(cg_block, {anno=[] :: term(), 60 es=[] :: [term()]}). 61 62-type vdb_entry() :: {atom(),non_neg_integer(),non_neg_integer()}. 63 64-record(l, {i=0 :: non_neg_integer(), %Op number 65 vdb=[] :: [vdb_entry()], %Variable database 66 a=[] :: [term()]}). %Core annotation 67 68-spec module(#k_mdef{}, [compile:option()]) -> {'ok',beam_asm:module_code()}. 69 70module(#k_mdef{name=Mod,exports=Es,attributes=Attr,body=Forms}, _Opts) -> 71 {Asm,St} = functions(Forms, {atom,Mod}), 72 {ok,{Mod,Es,Attr,Asm,St#cg.lcount}}. 73 74functions(Forms, AtomMod) -> 75 mapfoldl(fun (F, St) -> function(F, AtomMod, St) end, #cg{lcount=1}, Forms). 76 77function(#k_fdef{anno=#k{a=Anno},func=Name,arity=Arity, 78 vars=As,body=Kb}, AtomMod, St0) -> 79 try 80 #k_match{} = Kb, %Assertion. 81 82 %% Annotate kernel records with variable usage. 83 Vdb0 = init_vars(As), 84 {Body,_,Vdb} = body(Kb, 1, Vdb0), 85 86 %% Generate the BEAM assembly code. 87 {Asm,EntryLabel,St} = cg_fun(Body, As, Vdb, AtomMod, 88 {Name,Arity}, Anno, St0), 89 Func = {function,Name,Arity,EntryLabel,Asm}, 90 {Func,St} 91 catch 92 Class:Error:Stack -> 93 io:fwrite("Function: ~w/~w\n", [Name,Arity]), 94 erlang:raise(Class, Error, Stack) 95 end. 96 97%% This pass creates beam format annotated with variable lifetime 98%% information. Each thing is given an index and for each variable we 99%% store the first and last index for its occurrence. The variable 100%% database, VDB, attached to each thing is only relevant internally 101%% for that thing. 102%% 103%% For nested things like matches the numbering continues locally and 104%% the VDB for that thing refers to the variable usage within that 105%% thing. Variables which live through a such a thing are internally 106%% given a very large last index. Internally the indexes continue 107%% after the index of that thing. This creates no problems as the 108%% internal variable info never escapes and externally we only see 109%% variable which are alive both before or after. 110%% 111%% This means that variables never "escape" from a thing and the only 112%% way to get values from a thing is to "return" them, with 'break' or 113%% 'return'. Externally these values become the return values of the 114%% thing. This is no real limitation as most nested things have 115%% multiple threads so working out a common best variable usage is 116%% difficult. 117 118%% body(Kbody, I, Vdb) -> {[Expr],MaxI,Vdb}. 119%% Handle a body. 120 121body(#k_seq{arg=Ke,body=Kb}, I, Vdb0) -> 122 %%ok = io:fwrite("life ~w:~p~n", [?LINE,{Ke,I,Vdb0}]), 123 A = get_kanno(Ke), 124 Vdb1 = use_vars(union(A#k.us, A#k.ns), I, Vdb0), 125 {Es,MaxI,Vdb2} = body(Kb, I+1, Vdb1), 126 E = expr(Ke, I, Vdb2), 127 {[E|Es],MaxI,Vdb2}; 128body(Ke, I, Vdb0) -> 129 %%ok = io:fwrite("life ~w:~p~n", [?LINE,{Ke,I,Vdb0}]), 130 A = get_kanno(Ke), 131 Vdb1 = use_vars(union(A#k.us, A#k.ns), I, Vdb0), 132 E = expr(Ke, I, Vdb1), 133 {[E],I,Vdb1}. 134 135%% expr(Kexpr, I, Vdb) -> Expr. 136 137expr(#k_test{anno=A}=Test, I, _Vdb) -> 138 Test#k_test{anno=#l{i=I,a=A#k.a}}; 139expr(#k_call{anno=A}=Call, I, _Vdb) -> 140 Call#k_call{anno=#l{i=I,a=A#k.a}}; 141expr(#k_enter{anno=A}=Enter, I, _Vdb) -> 142 Enter#k_enter{anno=#l{i=I,a=A#k.a}}; 143expr(#k_bif{anno=A}=Bif, I, _Vdb) -> 144 Bif#k_bif{anno=#l{i=I,a=A#k.a}}; 145expr(#k_match{anno=A,body=Kb,ret=Rs}, I, Vdb) -> 146 %% Work out imported variables which need to be locked. 147 Mdb = vdb_sub(I, I+1, Vdb), 148 M = match(Kb, A#k.us, I+1, Mdb), 149 L = #l{i=I,vdb=use_vars(A#k.us, I+1, Mdb),a=A#k.a}, 150 #k_match{anno=L,body=M,ret=Rs}; 151expr(#k_guard_match{anno=A,body=Kb,ret=Rs}, I, Vdb) -> 152 %% Work out imported variables which need to be locked. 153 Mdb = vdb_sub(I, I+1, Vdb), 154 M = match(Kb, A#k.us, I+1, Mdb), 155 L = #l{i=I,vdb=use_vars(A#k.us, I+1, Mdb),a=A#k.a}, 156 #k_guard_match{anno=L,body=M,ret=Rs}; 157expr(#k_protected{}=Protected, I, Vdb) -> 158 protected(Protected, I, Vdb); 159expr(#k_try{anno=A,arg=Ka,vars=Vs,body=Kb,evars=Evs,handler=Kh}=Try, I, Vdb) -> 160 %% Lock variables that are alive before the catch and used afterwards. 161 %% Don't lock variables that are only used inside the try. 162 Tdb0 = vdb_sub(I, I+1, Vdb), 163 %% This is the tricky bit. Lock variables in Arg that are used in 164 %% the body and handler. Add try tag 'variable'. 165 Ab = get_kanno(Kb), 166 Ah = get_kanno(Kh), 167 Tdb1 = use_vars(union(Ab#k.us, Ah#k.us), I+3, Tdb0), 168 Tdb2 = vdb_sub(I, I+2, Tdb1), 169 Vnames = fun (Kvar) -> Kvar#k_var.name end, %Get the variable names 170 {Aes,_,Adb} = body(Ka, I+2, add_var({catch_tag,I+1}, I+1, locked, Tdb2)), 171 {Bes,_,Bdb} = body(Kb, I+4, new_vars(sort(map(Vnames, Vs)), I+3, Tdb2)), 172 {Hes,_,Hdb} = body(Kh, I+4, new_vars(sort(map(Vnames, Evs)), I+3, Tdb2)), 173 L = #l{i=I,vdb=Tdb1,a=A#k.a}, 174 Try#k_try{anno=L, 175 arg=#cg_block{es=Aes,anno=#l{i=I+1,vdb=Adb,a=[]}}, 176 vars=Vs,body=#cg_block{es=Bes,anno=#l{i=I+3,vdb=Bdb,a=[]}}, 177 evars=Evs,handler=#cg_block{es=Hes,anno=#l{i=I+3,vdb=Hdb,a=[]}}}; 178expr(#k_try_enter{anno=A,arg=Ka,vars=Vs,body=Kb,evars=Evs,handler=Kh}, I, Vdb) -> 179 %% Lock variables that are alive before the catch and used afterwards. 180 %% Don't lock variables that are only used inside the try. 181 Tdb0 = vdb_sub(I, I+1, Vdb), 182 %% This is the tricky bit. Lock variables in Arg that are used in 183 %% the body and handler. Add try tag 'variable'. 184 Ab = get_kanno(Kb), 185 Ah = get_kanno(Kh), 186 Tdb1 = use_vars(union(Ab#k.us, Ah#k.us), I+3, Tdb0), 187 Tdb2 = vdb_sub(I, I+2, Tdb1), 188 Vnames = fun (Kvar) -> Kvar#k_var.name end, %Get the variable names 189 {Aes,_,Adb} = body(Ka, I+2, add_var({catch_tag,I+1}, I+1, 1000000, Tdb2)), 190 {Bes,_,Bdb} = body(Kb, I+4, new_vars(sort(map(Vnames, Vs)), I+3, Tdb2)), 191 {Hes,_,Hdb} = body(Kh, I+4, new_vars(sort(map(Vnames, Evs)), I+3, Tdb2)), 192 L = #l{i=I,vdb=Tdb1,a=A#k.a}, 193 #k_try_enter{anno=L, 194 arg=#cg_block{es=Aes,anno=#l{i=I+1,vdb=Adb,a=[]}}, 195 vars=Vs,body=#cg_block{es=Bes,anno=#l{i=I+3,vdb=Bdb,a=[]}}, 196 evars=Evs,handler=#cg_block{es=Hes,anno=#l{i=I+3,vdb=Hdb,a=[]}}}; 197expr(#k_catch{anno=A,body=Kb}=Catch, I, Vdb) -> 198 %% Lock variables that are alive before the catch and used afterwards. 199 %% Don't lock variables that are only used inside the catch. 200 %% Add catch tag 'variable'. 201 Cdb0 = vdb_sub(I, I+1, Vdb), 202 {Es,_,Cdb1} = body(Kb, I+1, add_var({catch_tag,I}, I, locked, Cdb0)), 203 L = #l{i=I,vdb=Cdb1,a=A#k.a}, 204 Catch#k_catch{anno=L,body=#cg_block{es=Es}}; 205expr(#k_receive{anno=A,var=V,body=Kb,action=Ka}=Recv, I, Vdb) -> 206 %% Work out imported variables which need to be locked. 207 Rdb = vdb_sub(I, I+1, Vdb), 208 M = match(Kb, add_element(V#k_var.name, A#k.us), I+1, 209 new_vars([V#k_var.name], I, Rdb)), 210 {Tes,_,Adb} = body(Ka, I+1, Rdb), 211 Le = #l{i=I,vdb=use_vars(A#k.us, I+1, Vdb),a=A#k.a}, 212 Recv#k_receive{anno=Le,body=M, 213 action=#cg_block{anno=#l{i=I+1,vdb=Adb,a=[]},es=Tes}}; 214expr(#k_receive_accept{anno=A}, I, _Vdb) -> 215 #k_receive_accept{anno=#l{i=I,a=A#k.a}}; 216expr(#k_receive_next{anno=A}, I, _Vdb) -> 217 #k_receive_next{anno=#l{i=I,a=A#k.a}}; 218expr(#k_put{anno=A}=Put, I, _Vdb) -> 219 Put#k_put{anno=#l{i=I,a=A#k.a}}; 220expr(#k_break{anno=A}=Break, I, _Vdb) -> 221 Break#k_break{anno=#l{i=I,a=A#k.a}}; 222expr(#k_guard_break{anno=A}=Break, I, _Vdb) -> 223 Break#k_guard_break{anno=#l{i=I,a=A#k.a}}; 224expr(#k_return{anno=A}=Ret, I, _Vdb) -> 225 Ret#k_return{anno=#l{i=I,a=A#k.a}}. 226 227%% protected(Kprotected, I, Vdb) -> Protected. 228%% Only used in guards. 229 230protected(#k_protected{anno=A,arg=Ts}=Prot, I, Vdb) -> 231 %% Lock variables that are alive before try and used afterwards. 232 %% Don't lock variables that are only used inside the protected 233 %% expression. 234 Pdb0 = vdb_sub(I, I+1, Vdb), 235 {T,MaxI,Pdb1} = body(Ts, I+1, Pdb0), 236 Pdb2 = use_vars(A#k.ns, MaxI+1, Pdb1), %Save "return" values 237 Prot#k_protected{arg=T,anno=#l{i=I,a=A#k.a,vdb=Pdb2}}. 238 239%% match(Kexpr, [LockVar], I, Vdb) -> Expr. 240%% Convert match tree to old format. 241 242match(#k_alt{anno=A,first=Kf,then=Kt}, Ls, I, Vdb0) -> 243 Vdb1 = use_vars(union(A#k.us, Ls), I, Vdb0), 244 F = match(Kf, Ls, I+1, Vdb1), 245 T = match(Kt, Ls, I+1, Vdb1), 246 #k_alt{anno=[],first=F,then=T}; 247match(#k_select{anno=A,types=Kts}=Select, Ls, I, Vdb0) -> 248 Vdb1 = use_vars(union(A#k.us, Ls), I, Vdb0), 249 Ts = [type_clause(Tc, Ls, I+1, Vdb1) || Tc <- Kts], 250 Select#k_select{anno=[],types=Ts}; 251match(#k_guard{anno=A,clauses=Kcs}, Ls, I, Vdb0) -> 252 Vdb1 = use_vars(union(A#k.us, Ls), I, Vdb0), 253 Cs = [guard_clause(G, Ls, I+1, Vdb1) || G <- Kcs], 254 #k_guard{anno=[],clauses=Cs}; 255match(Other, Ls, I, Vdb0) -> 256 Vdb1 = use_vars(Ls, I, Vdb0), 257 {B,_,Vdb2} = body(Other, I+1, Vdb1), 258 Le = #l{i=I,vdb=Vdb2,a=[]}, 259 #cg_block{anno=Le,es=B}. 260 261type_clause(#k_type_clause{anno=A,type=T,values=Kvs}, Ls, I, Vdb0) -> 262 %%ok = io:format("life ~w: ~p~n", [?LINE,{T,Kvs}]), 263 Vdb1 = use_vars(union(A#k.us, Ls), I+1, Vdb0), 264 Vs = [val_clause(Vc, Ls, I+1, Vdb1) || Vc <- Kvs], 265 #k_type_clause{anno=[],type=T,values=Vs}. 266 267val_clause(#k_val_clause{anno=A,val=V,body=Kb}, Ls0, I, Vdb0) -> 268 New = (get_kanno(V))#k.ns, 269 Bus = (get_kanno(Kb))#k.us, 270 %%ok = io:format("Ls0 = ~p, Used=~p\n New=~p, Bus=~p\n", [Ls0,Used,New,Bus]), 271 Ls1 = union(intersection(New, Bus), Ls0), %Lock for safety 272 Vdb1 = use_vars(union(A#k.us, Ls1), I+1, new_vars(New, I, Vdb0)), 273 B = match(Kb, Ls1, I+1, Vdb1), 274 Le = #l{i=I,vdb=use_vars(Bus, I+1, Vdb1),a=A#k.a}, 275 #k_val_clause{anno=Le,val=V,body=B}. 276 277guard_clause(#k_guard_clause{anno=A,guard=Kg,body=Kb}, Ls, I, Vdb0) -> 278 Vdb1 = use_vars(union(A#k.us, Ls), I+2, Vdb0), 279 Gdb = vdb_sub(I+1, I+2, Vdb1), 280 G = protected(Kg, I+1, Gdb), 281 B = match(Kb, Ls, I+2, Vdb1), 282 Le = #l{i=I,vdb=use_vars((get_kanno(Kg))#k.us, I+2, Vdb1),a=A#k.a}, 283 #k_guard_clause{anno=Le,guard=G,body=B}. 284 285 286%% Here follows the code generator pass. 287%% 288%% The following assumptions have been made: 289%% 290%% 1. Matches, i.e. things with {match,M,Ret} wrappers, only return 291%% values; no variables are exported. If the match would have returned 292%% extra variables then these have been transformed to multiple return 293%% values. 294%% 295%% 2. All BIF's called in guards are gc-safe so there is no need to 296%% put thing on the stack in the guard. While this would in principle 297%% work it would be difficult to keep track of the stack depth when 298%% trimming. 299%% 300%% The code generation uses variable lifetime information added by 301%% the previous pass to save variables, allocate registers and 302%% move registers to the stack when necessary. 303%% 304%% We try to use a consistent variable name scheme throughout. The 305%% StackReg record is always called Bef,Int<n>,Aft. 306 307%% cg_fun([Lkexpr], [HeadVar], Vdb, State) -> {[Ainstr],State} 308 309cg_fun(Les, Hvs, Vdb, AtomMod, NameArity, Anno, St0) -> 310 {Fi,St1} = new_label(St0), %FuncInfo label 311 {Fl,St2} = local_func_label(NameArity, St1), 312 313 %% 314 %% The pattern matching compiler (in v3_kernel) no longer 315 %% provides its own catch-all clause, because the 316 %% call to erlang:exit/1 caused problem when cases were 317 %% used in guards. Therefore, there may be tests that 318 %% cannot fail (providing that there is not a bug in a 319 %% previous optimzation pass), but still need to provide 320 %% a label (there are instructions, such as is_tuple/2, 321 %% that do not allow {f,0}). 322 %% 323 %% We will generate an ultimate failure label and put it 324 %% at the end of function, followed by an 'if_end' instruction. 325 %% Note that and 'if_end' instruction does not need any 326 %% live x registers, so it will always be safe to jump to 327 %% it. (We never ever expect the jump to be taken, and in 328 %% most functions there will never be any references to 329 %% the label in the first place.) 330 %% 331 332 {UltimateMatchFail,St3} = new_label(St2), 333 334 %% Create initial stack/register state, clear unused arguments. 335 Bef = clear_dead(#sr{reg=foldl(fun (#k_var{name=V}, Reg) -> 336 put_reg(V, Reg) 337 end, [], Hvs), 338 stk=[]}, 0, Vdb), 339 {B,_Aft,St} = cg_list(Les, Vdb, Bef, 340 St3#cg{bfail=0, 341 ultimate_failure=UltimateMatchFail, 342 is_top_block=true}), 343 {Name,Arity} = NameArity, 344 Asm = [{label,Fi},line(Anno),{func_info,AtomMod,{atom,Name},Arity}, 345 {label,Fl}|B++[{label,UltimateMatchFail},if_end]], 346 {Asm,Fl,St}. 347 348%% cg(Lkexpr, Vdb, StackReg, State) -> {[Ainstr],StackReg,State}. 349%% Generate code for a kexpr. 350 351cg(#cg_block{anno=Le,es=Es}, Vdb, Bef, St) -> 352 block_cg(Es, Le, Vdb, Bef, St); 353cg(#k_match{anno=Le,body=M,ret=Rs}, Vdb, Bef, St) -> 354 match_cg(M, Rs, Le, Vdb, Bef, St); 355cg(#k_guard_match{anno=Le,body=M,ret=Rs}, Vdb, Bef, St) -> 356 guard_match_cg(M, Rs, Le, Vdb, Bef, St); 357cg(#k_call{anno=Le,op=Func,args=As,ret=Rs}, Vdb, Bef, St) -> 358 call_cg(Func, As, Rs, Le, Vdb, Bef, St); 359cg(#k_enter{anno=Le,op=Func,args=As}, Vdb, Bef, St) -> 360 enter_cg(Func, As, Le, Vdb, Bef, St); 361cg(#k_bif{anno=Le}=Bif, Vdb, Bef, St) -> 362 bif_cg(Bif, Le, Vdb, Bef, St); 363cg(#k_receive{anno=Le,timeout=Te,var=Rvar,body=Rm,action=Tes,ret=Rs}, 364 Vdb, Bef, St) -> 365 recv_loop_cg(Te, Rvar, Rm, Tes, Rs, Le, Vdb, Bef, St); 366cg(#k_receive_next{anno=Le}, Vdb, Bef, St) -> 367 recv_next_cg(Le, Vdb, Bef, St); 368cg(#k_receive_accept{}, _Vdb, Bef, St) -> 369 {[remove_message],Bef,St}; 370cg(#k_try{anno=Le,arg=Ta,vars=Vs,body=Tb,evars=Evs,handler=Th,ret=Rs}, 371 Vdb, Bef, St) -> 372 try_cg(Ta, Vs, Tb, Evs, Th, Rs, Le, Vdb, Bef, St); 373cg(#k_try_enter{anno=Le,arg=Ta,vars=Vs,body=Tb,evars=Evs,handler=Th}, 374 Vdb, Bef, St) -> 375 try_enter_cg(Ta, Vs, Tb, Evs, Th, Le, Vdb, Bef, St); 376cg(#k_catch{anno=Le,body=Cb,ret=[R]}, Vdb, Bef, St) -> 377 catch_cg(Cb, R, Le, Vdb, Bef, St); 378cg(#k_put{anno=Le,arg=Con,ret=Var}, Vdb, Bef, St) -> 379 put_cg(Var, Con, Le, Vdb, Bef, St); 380cg(#k_return{anno=Le,args=Rs}, Vdb, Bef, St) -> 381 return_cg(Rs, Le, Vdb, Bef, St); 382cg(#k_break{anno=Le,args=Bs}, Vdb, Bef, St) -> 383 break_cg(Bs, Le, Vdb, Bef, St); 384cg(#k_guard_break{anno=Le,args=Bs}, Vdb, Bef, St) -> 385 guard_break_cg(Bs, Le, Vdb, Bef, St); 386cg(#cg_need_heap{h=H}, _Vdb, Bef, St) -> 387 {[{test_heap,H,max_reg(Bef#sr.reg)}],Bef,St}. 388 389%% cg_list([Kexpr], FirstI, Vdb, StackReg, St) -> {[Ainstr],StackReg,St}. 390 391cg_list(Kes, Vdb, Bef, St0) -> 392 {Keis,{Aft,St1}} = 393 flatmapfoldl(fun (Ke, {Inta,Sta}) -> 394 {Keis,Intb,Stb} = cg(Ke, Vdb, Inta, Sta), 395 {Keis,{Intb,Stb}} 396 end, {Bef,St0}, need_heap(Kes)), 397 {Keis,Aft,St1}. 398 399%% need_heap([Lkexpr], I, St) -> [Lkexpr]. 400%% Insert need_heap instructions in Kexpr list. Try to be smart and 401%% collect them together as much as possible. 402 403need_heap(Kes0) -> 404 {Kes,H} = need_heap_0(reverse(Kes0), 0, []), 405 406 %% Prepend need_heap if necessary. 407 need_heap_need(H) ++ Kes. 408 409need_heap_0([Ke|Kes], H0, Acc) -> 410 {Ns,H} = need_heap_1(Ke, H0), 411 need_heap_0(Kes, H, [Ke|Ns]++Acc); 412need_heap_0([], H, Acc) -> 413 {Acc,H}. 414 415need_heap_1(#k_put{arg=#k_binary{}}, H) -> 416 {need_heap_need(H),0}; 417need_heap_1(#k_put{arg=#k_map{}}, H) -> 418 {need_heap_need(H),0}; 419need_heap_1(#k_put{arg=Val}, H) -> 420 %% Just pass through adding to needed heap. 421 {[],H + case Val of 422 #k_cons{} -> 2; 423 #k_tuple{es=Es} -> 1 + length(Es); 424 _Other -> 0 425 end}; 426need_heap_1(#k_bif{}=Bif, H) -> 427 case is_gc_bif(Bif) of 428 false -> 429 {[],H}; 430 true -> 431 {need_heap_need(H),0} 432 end; 433need_heap_1(_Ke, H) -> 434 %% Call or call-like instruction such as set_tuple_element/3. 435 {need_heap_need(H),0}. 436 437need_heap_need(0) -> []; 438need_heap_need(H) -> [#cg_need_heap{h=H}]. 439 440%% is_gc_bif(#k_bif{}) -> true|false. 441%% is_gc_bif(Name, Arity) -> true|false. 442%% Determines whether the BIF Name/Arity might do a GC. 443 444is_gc_bif(#k_bif{op=#k_remote{name=#k_atom{val=Name}},args=Args}) -> 445 is_gc_bif(Name, length(Args)); 446is_gc_bif(#k_bif{op=#k_internal{}}) -> 447 true. 448 449is_gc_bif(hd, 1) -> false; 450is_gc_bif(tl, 1) -> false; 451is_gc_bif(self, 0) -> false; 452is_gc_bif(node, 0) -> false; 453is_gc_bif(node, 1) -> false; 454is_gc_bif(element, 2) -> false; 455is_gc_bif(get, 1) -> false; 456is_gc_bif(tuple_size, 1) -> false; 457is_gc_bif(map_get, 2) -> false; 458is_gc_bif(is_map_key, 2) -> false; 459is_gc_bif(Bif, Arity) -> 460 not (erl_internal:bool_op(Bif, Arity) orelse 461 erl_internal:new_type_test(Bif, Arity) orelse 462 erl_internal:comp_op(Bif, Arity)). 463 464%% match_cg(Matc, [Ret], Le, Vdb, StackReg, State) -> 465%% {[Ainstr],StackReg,State}. 466%% Generate code for a match. First save all variables on the stack 467%% that are to survive after the match. We leave saved variables in 468%% their registers as they might actually be in the right place. 469 470match_cg(M, Rs, Le, Vdb, Bef, St0) -> 471 I = Le#l.i, 472 {Sis,Int0} = adjust_stack(Bef, I, I+1, Vdb), 473 {B,St1} = new_label(St0), 474 {Mis,Int1,St2} = match_cg(M, St1#cg.ultimate_failure, 475 Int0, St1#cg{break=B}), 476 %% Put return values in registers. 477 Reg = load_vars(Rs, Int1#sr.reg), 478 {Sis ++ Mis ++ [{label,B}], 479 clear_dead(Int1#sr{reg=Reg}, I, Vdb), 480 St2#cg{break=St1#cg.break}}. 481 482guard_match_cg(M, Rs, Le, Vdb, Bef, St0) -> 483 I = Le#l.i, 484 {B,St1} = new_label(St0), 485 Fail = case St0 of 486 #cg{bfail=0,ultimate_failure=Fail0} -> Fail0; 487 #cg{bfail=Fail0} -> Fail0 488 end, 489 {Mis,Aft,St2} = match_cg(M, Fail, Bef, St1#cg{break=B}), 490 %% Update the register descriptors for the return registers. 491 Reg = guard_match_regs(Aft#sr.reg, Rs), 492 {Mis ++ [{label,B}], 493 clear_dead(Aft#sr{reg=Reg}, I, Vdb), 494 St2#cg{break=St1#cg.break}}. 495 496guard_match_regs([{I,gbreakvar}|Rs], [#k_var{name=V}|Vs]) -> 497 [{I,V}|guard_match_regs(Rs, Vs)]; 498guard_match_regs([R|Rs], Vs) -> 499 [R|guard_match_regs(Rs, Vs)]; 500guard_match_regs([], []) -> []. 501 502 503%% match_cg(Match, Fail, StackReg, State) -> {[Ainstr],StackReg,State}. 504%% Generate code for a match tree. N.B. there is no need pass Vdb 505%% down as each level which uses this takes its own internal Vdb not 506%% the outer one. 507 508match_cg(#k_alt{first=F,then=S}, Fail, Bef, St0) -> 509 {Tf,St1} = new_label(St0), 510 {Fis,Faft,St2} = match_cg(F, Tf, Bef, St1), 511 {Sis,Saft,St3} = match_cg(S, Fail, Bef, St2), 512 Aft = sr_merge(Faft, Saft), 513 {Fis ++ [{label,Tf}] ++ Sis,Aft,St3}; 514match_cg(#k_select{var=#k_var{anno=Vanno,name=Vname}=V,types=Scs0}, Fail, Bef, St) -> 515 ReuseForContext = member(reuse_for_context, Vanno) andalso 516 find_reg(Vname, Bef#sr.reg) =/= error, 517 Scs = case ReuseForContext of 518 false -> Scs0; 519 true -> bsm_rename_ctx(Scs0, Vname) 520 end, 521 match_fmf(fun (S, F, Sta) -> 522 select_cg(S, V, F, Fail, Bef, Sta) end, 523 Fail, St, Scs); 524match_cg(#k_guard{clauses=Gcs}, Fail, Bef, St) -> 525 match_fmf(fun (G, F, Sta) -> guard_clause_cg(G, F, Bef, Sta) end, 526 Fail, St, Gcs); 527match_cg(#cg_block{anno=Le,es=Es}, _Fail, Bef, St) -> 528 %% Must clear registers and stack of dead variables. 529 Int = clear_dead(Bef, Le#l.i, Le#l.vdb), 530 block_cg(Es, Le, Int, St). 531 532%% bsm_rename_ctx([Clause], Var) -> [Clause] 533%% We know from an annotation that the register for a binary can 534%% be reused for the match context because the two are not truly 535%% alive at the same time (even though the life time information 536%% says so). 537%% 538%% The easiest way to have those variables share the same register is 539%% to rename the variable with the shortest life-span (the match 540%% context) to the variable for the binary (which can have a very 541%% long life-time because it is locked during matching). We KNOW that 542%% the match state variable will only be alive during the matching. 543%% 544%% We must also remove all information about the match context 545%% variable from all life-time information databases (Vdb). 546 547bsm_rename_ctx([#k_type_clause{type=k_binary,values=Vcs}=TC|Cs], New) -> 548 [#k_val_clause{val=#k_binary{segs=#k_var{name=Old}}=Bin, 549 body=Ke0}=VC0] = Vcs, 550 Ke = bsm_rename_ctx(Ke0, Old, New, false), 551 VC = VC0#k_val_clause{val=Bin#k_binary{segs=#k_var{name=New}}, 552 body=Ke}, 553 [TC#k_type_clause{values=[VC]}|bsm_rename_ctx(Cs, New)]; 554bsm_rename_ctx([C|Cs], New) -> 555 [C|bsm_rename_ctx(Cs, New)]; 556bsm_rename_ctx([], _) -> []. 557 558%% bsm_rename_ctx(Ke, OldName, NewName, InProt) -> Ke' 559%% Rename and clear OldName from life-time information. We must 560%% recurse into any block contained in a protected, but it would 561%% only complicatate things to recurse into blocks not in a protected 562%% (the match context variable is not live inside them). 563 564bsm_rename_ctx(#k_select{var=#k_var{name=V},types=Cs0}=Sel, 565 Old, New, InProt) -> 566 Cs = bsm_rename_ctx_list(Cs0, Old, New, InProt), 567 Sel#k_select{var=#k_var{name=bsm_rename_var(V, Old, New)},types=Cs}; 568bsm_rename_ctx(#k_type_clause{values=Cs0}=TC, Old, New, InProt) -> 569 Cs = bsm_rename_ctx_list(Cs0, Old, New, InProt), 570 TC#k_type_clause{values=Cs}; 571bsm_rename_ctx(#k_val_clause{body=Ke0}=VC, Old, New, InProt) -> 572 Ke = bsm_rename_ctx(Ke0, Old, New, InProt), 573 VC#k_val_clause{body=Ke}; 574bsm_rename_ctx(#k_alt{first=F0,then=S0}=Alt, Old, New, InProt) -> 575 F = bsm_rename_ctx(F0, Old, New, InProt), 576 S = bsm_rename_ctx(S0, Old, New, InProt), 577 Alt#k_alt{first=F,then=S}; 578bsm_rename_ctx(#k_guard{clauses=Gcs0}=Guard, Old, New, InProt) -> 579 Gcs = bsm_rename_ctx_list(Gcs0, Old, New, InProt), 580 Guard#k_guard{clauses=Gcs}; 581bsm_rename_ctx(#k_guard_clause{guard=G0,body=B0}=GC, Old, New, InProt) -> 582 G = bsm_rename_ctx(G0, Old, New, InProt), 583 B = bsm_rename_ctx(B0, Old, New, InProt), 584 %% A guard clause may cause unsaved variables to be saved on the stack. 585 %% Since the match state variable Old is an alias for New (uses the 586 %% same register), it is neither in the stack nor register descriptor 587 %% lists and we would crash when we didn't find it unless we remove 588 %% it from the database. 589 bsm_forget_var(GC#k_guard_clause{guard=G,body=B}, Old); 590bsm_rename_ctx(#k_protected{arg=Ts0}=Prot, Old, New, _InProt) -> 591 InProt = true, 592 Ts = bsm_rename_ctx_list(Ts0, Old, New, InProt), 593 bsm_forget_var(Prot#k_protected{arg=Ts}, Old); 594bsm_rename_ctx(#k_guard_match{body=Ms0}=Match, Old, New, InProt) -> 595 Ms = bsm_rename_ctx(Ms0, Old, New, InProt), 596 Match#k_guard_match{body=Ms}; 597bsm_rename_ctx(#k_test{}=Test, _, _, _) -> Test; 598bsm_rename_ctx(#k_bif{}=Bif, _, _, _) -> Bif; 599bsm_rename_ctx(#k_put{}=Put, _, _, _) -> Put; 600bsm_rename_ctx(#k_call{}=Call, _, _, _) -> Call; 601bsm_rename_ctx(#cg_block{}=Block, Old, _, false) -> 602 %% This block is not inside a protected. The match context variable cannot 603 %% possibly be live inside the block. 604 bsm_forget_var(Block, Old); 605bsm_rename_ctx(#cg_block{es=Es0}=Block, Old, New, true) -> 606 %% A block in a protected. We must recursively rename the variable 607 %% inside the block. 608 Es = bsm_rename_ctx_list(Es0, Old, New, true), 609 bsm_forget_var(Block#cg_block{es=Es}, Old); 610bsm_rename_ctx(#k_guard_break{}=Break, Old, _New, _InProt) -> 611 bsm_forget_var(Break, Old). 612 613bsm_rename_ctx_list([C|Cs], Old, New, InProt) -> 614 [bsm_rename_ctx(C, Old, New, InProt)| 615 bsm_rename_ctx_list(Cs, Old, New, InProt)]; 616bsm_rename_ctx_list([], _, _, _) -> []. 617 618bsm_rename_var(Old, Old, New) -> New; 619bsm_rename_var(V, _, _) -> V. 620 621%% bsm_forget_var(#l{}, Variable) -> #l{} 622%% Remove a variable from the variable life-time database. 623 624bsm_forget_var(Ke, V) -> 625 #l{vdb=Vdb} = L0 = get_kanno(Ke), 626 L = L0#l{vdb=keydelete(V, 1, Vdb)}, 627 set_kanno(Ke, L). 628 629%% block_cg([Kexpr], Le, Vdb, StackReg, St) -> {[Ainstr],StackReg,St}. 630%% block_cg([Kexpr], Le, StackReg, St) -> {[Ainstr],StackReg,St}. 631 632block_cg(Es, Le, _Vdb, Bef, St) -> 633 block_cg(Es, Le, Bef, St). 634 635block_cg(Es, Le, Bef, #cg{is_top_block=false}=St) -> 636 cg_block(Es, Le#l.vdb, Bef, St); 637block_cg(Es, Le, Bef, #cg{is_top_block=true}=St0) -> 638 %% No stack frame has been established yet. Do we need one? 639 case need_stackframe(Es) of 640 true -> 641 %% We need a stack frame. Generate the code and add the 642 %% code for creating and deallocating the stack frame. 643 {Is0,Aft,St} = cg_block(Es, Le#l.vdb, Bef, 644 St0#cg{is_top_block=false,need_frame=false}), 645 Is = top_level_block(Is0, Aft, max_reg(Bef#sr.reg), St), 646 {Is,Aft,St#cg{is_top_block=true}}; 647 false -> 648 %% This sequence of instructions ending in a #k_match{} (a 649 %% 'case' or 'if') in the Erlang code does not need a 650 %% stack frame yet. Delay the creation (if a stack frame 651 %% is needed at all, it will be created inside the 652 %% #k_match{}). 653 cg_list(Es, Le#l.vdb, Bef, St0) 654 end. 655 656%% need_stackframe([Kexpr]) -> true|false. 657%% Does this list of instructions need a stack frame? 658%% 659%% A sequence of instructions that don't clobber the X registers 660%% followed by a single #k_match{} doesn't need a stack frame. 661 662need_stackframe([H|T]) -> 663 case H of 664 #k_bif{op=#k_internal{}} -> true; 665 #k_put{arg=#k_binary{}} -> true; 666 #k_bif{} -> need_stackframe(T); 667 #k_put{} -> need_stackframe(T); 668 #k_guard_match{} -> need_stackframe(T); 669 #k_match{} when T =:= [] -> false; 670 _ -> true 671 end; 672need_stackframe([]) -> false. 673 674cg_block([], _Vdb, Bef, St0) -> 675 {[],Bef,St0}; 676cg_block(Kes0, Vdb, Bef, St0) -> 677 {Kes2,Int1,St1} = 678 case basic_block(Kes0) of 679 {Kes1,LastI,Args,Rest} -> 680 cg_basic_block(Kes1, LastI, Args, Vdb, Bef, St0); 681 {Kes1,Rest} -> 682 cg_list(Kes1, Vdb, Bef, St0) 683 end, 684 {Kes3,Int2,St2} = cg_block(Rest, Vdb, Int1, St1), 685 {Kes2 ++ Kes3,Int2,St2}. 686 687basic_block(Kes) -> basic_block(Kes, []). 688 689basic_block([Ke|Kes], Acc) -> 690 case collect_block(Ke) of 691 include -> basic_block(Kes, [Ke|Acc]); 692 {block_end,As} -> 693 case Acc of 694 [] -> 695 %% If the basic block does not contain any #k_put{} instructions, 696 %% it serves no useful purpose to do basic block optimizations. 697 {[Ke],Kes}; 698 _ -> 699 #l{i=I} = get_kanno(Ke), 700 {reverse(Acc, [Ke]),I,As,Kes} 701 end; 702 no_block -> {reverse(Acc, [Ke]),Kes} 703 end. 704 705collect_block(#k_put{arg=Arg}) -> 706 %% #k_put{} instructions that may garbage collect are not allowed 707 %% in basic blocks. 708 case Arg of 709 #k_binary{} -> no_block; 710 #k_map{} -> no_block; 711 _ -> include 712 end; 713collect_block(#k_call{op=Func,args=As}) -> 714 {block_end,As++func_vars(Func)}; 715collect_block(#k_enter{op=Func,args=As}) -> 716 {block_end,As++func_vars(Func)}; 717collect_block(#k_return{args=Rs}) -> 718 {block_end,Rs}; 719collect_block(#k_break{args=Bs}) -> 720 {block_end,Bs}; 721collect_block(_) -> no_block. 722 723func_vars(#k_var{}=Var) -> 724 [Var]; 725func_vars(#k_remote{mod=M,name=F}) 726 when is_record(M, k_var); is_record(F, k_var) -> 727 [M,F]; 728func_vars(_) -> []. 729 730%% cg_basic_block([Kexpr], FirstI, LastI, Arguments, Vdb, StackReg, State) -> 731%% {[Ainstr],StackReg,State}. 732%% 733%% Do a specialized code generation for a basic block of #put{} 734%% instructions (that don't do any garbage collection) followed by a 735%% call, break, or return. 736%% 737%% 'Arguments' is a list of the variables that must be loaded into 738%% consecutive X registers before the last instruction in the block. 739%% The point of this specialized code generation is to try put the 740%% all of the variables in 'Arguments' into the correct X register 741%% to begin with, instead of putting them into the first available 742%% X register and having to move them to the correct X register 743%% later. 744%% 745%% To achieve that, we attempt to reserve the X registers that the 746%% variables in 'Arguments' will need to be in when the block ends. 747%% 748%% To make it more likely that reservations will be successful, we 749%% will try to save variables that need to be saved to the stack as 750%% early as possible (if an X register needed by a variable in 751%% Arguments is occupied by another variable, the value in the 752%% X register can be evicted if it is saved on the stack). 753%% 754%% We will take care not to increase the size of stack frame compared 755%% to what the standard code generator would have done (that is, to 756%% save all X registers at the last possible moment). We will do that 757%% by extending the stack frame to the minimal size needed to save 758%% all that needs to be saved using extend_stack/4, and use 759%% save_carefully/4 during code generation to only save the variables 760%% that can be saved without growing the stack frame. 761 762cg_basic_block(Kes, Lf, As, Vdb, Bef, St0) -> 763 Int0 = reserve_arg_regs(As, Bef), 764 Int = extend_stack(Int0, Lf, Lf+1, Vdb), 765 {Keis,{Aft,St1}} = 766 flatmapfoldl(fun(Ke, St) -> cg_basic_block(Ke, St, Lf, Vdb) end, 767 {Int,St0}, need_heap(Kes)), 768 {Keis,Aft,St1}. 769 770cg_basic_block(#cg_need_heap{}=Ke, {Bef,St0}, _Lf, Vdb) -> 771 {Keis,Aft,St1} = cg(Ke, Vdb, Bef, St0), 772 {Keis,{Aft,St1}}; 773cg_basic_block(Ke, {Bef,St0}, Lf, Vdb) -> 774 #l{i=I} = get_kanno(Ke), 775 776 %% Save all we can to increase the possibility that reserving 777 %% registers will succeed. 778 {Sis,Int0} = save_carefully(Bef, I, Lf+1, Vdb), 779 Int1 = reserve(Int0), 780 {Keis,Aft,St1} = cg(Ke, Vdb, Int1, St0), 781 {Sis ++ Keis,{Aft,St1}}. 782 783%% reserve_arg_regs([Argument], Bef) -> Aft. 784%% Try to reserve the X registers for all arguments. All registers 785%% that we wish to reserve will be saved in Bef#sr.res. 786 787reserve_arg_regs(As, Bef) -> 788 Res = reserve_arg_regs_1(As, 0), 789 reserve(Bef#sr{res=Res}). 790 791reserve_arg_regs_1([#k_var{name=V}|As], I) -> 792 [{I,V}|reserve_arg_regs_1(As, I+1)]; 793reserve_arg_regs_1([A|As], I) -> 794 [{I,A}|reserve_arg_regs_1(As, I+1)]; 795reserve_arg_regs_1([], _) -> []. 796 797%% reserve(Bef) -> Aft. 798%% Try to reserve more registers. The registers we wish to reserve 799%% are found in Bef#sr.res. 800 801reserve(#sr{reg=Regs,stk=Stk,res=Res}=Sr) -> 802 Sr#sr{reg=reserve_1(Res, Regs, Stk)}. 803 804reserve_1([{I,V}|Rs], [free|Regs], Stk) -> 805 [{reserved,I,V}|reserve_1(Rs, Regs, Stk)]; 806reserve_1([{I,V}|Rs], [{I,V}|Regs], Stk) -> 807 [{I,V}|reserve_1(Rs, Regs, Stk)]; 808reserve_1([{I,V}|Rs], [{I,Var}|Regs], Stk) -> 809 case on_stack(Var, Stk) of 810 true -> [{reserved,I,V}|reserve_1(Rs, Regs, Stk)]; 811 false -> [{I,Var}|reserve_1(Rs, Regs, Stk)] 812 end; 813reserve_1([{I,V}|Rs], [{reserved,I,_}|Regs], Stk) -> 814 [{reserved,I,V}|reserve_1(Rs, Regs, Stk)]; 815reserve_1([{I,V}|Rs], [], Stk) -> 816 [{reserved,I,V}|reserve_1(Rs, [], Stk)]; 817reserve_1([], Regs, _) -> Regs. 818 819%% extend_stack(Bef, FirstBefore, LastFrom, Vdb) -> Aft. 820%% Extend the stack enough to fit all variables alive past LastFrom 821%% and not already on the stack. 822 823extend_stack(#sr{stk=Stk0}=Bef, Fb, Lf, Vdb) -> 824 Stk1 = clear_dead_stk(Stk0, Fb, Vdb), 825 New = new_not_on_stack(Stk1, Fb, Lf, Vdb), 826 Stk2 = foldl(fun ({V,_,_}, Stk) -> put_stack(V, Stk) end, Stk1, New), 827 Stk = Stk0 ++ lists:duplicate(length(Stk2) - length(Stk0), free), 828 Bef#sr{stk=Stk}. 829 830%% save_carefully(Bef, FirstBefore, LastFrom, Vdb) -> {[SaveVar],Aft}. 831%% Save variables which are used past current point and which are not 832%% already on the stack, but only if the variables can be saved without 833%% growing the stack frame. 834 835save_carefully(#sr{stk=Stk}=Bef, Fb, Lf, Vdb) -> 836 New0 = new_not_on_stack(Stk, Fb, Lf, Vdb), 837 New = keysort(2, New0), 838 save_carefully_1(New, Bef, []). 839 840save_carefully_1([{V,_,_}|Vs], #sr{reg=Regs,stk=Stk0}=Bef, Acc) -> 841 case put_stack_carefully(V, Stk0) of 842 error -> 843 {reverse(Acc),Bef}; 844 Stk1 -> 845 SrcReg = fetch_reg(V, Regs), 846 Move = {move,SrcReg,fetch_stack(V, Stk1)}, 847 {x,_} = SrcReg, %Assertion - must be X register. 848 save_carefully_1(Vs, Bef#sr{stk=Stk1}, [Move|Acc]) 849 end; 850save_carefully_1([], Bef, Acc) -> 851 {reverse(Acc),Bef}. 852 853%% top_level_block([Instruction], Bef, MaxRegs, St) -> [Instruction]. 854%% For the top-level block, allocate a stack frame a necessary, 855%% adjust Y register numbering and instructions that return 856%% from the function. 857 858top_level_block(Keis, #sr{stk=[]}, _MaxRegs, #cg{need_frame=false}) -> 859 Keis; 860top_level_block(Keis, Bef, MaxRegs, _St) -> 861 %% This top block needs an allocate instruction before it, and a 862 %% deallocate instruction before each return. 863 FrameSz = length(Bef#sr.stk), 864 MaxY = FrameSz-1, 865 Keis1 = flatmap(fun ({call_only,Arity,Func}) -> 866 [{call_last,Arity,Func,FrameSz}]; 867 ({call_ext_only,Arity,Func}) -> 868 [{call_ext_last,Arity,Func,FrameSz}]; 869 ({apply_only,Arity}) -> 870 [{apply_last,Arity,FrameSz}]; 871 (return) -> 872 [{deallocate,FrameSz},return]; 873 (Tuple) when is_tuple(Tuple) -> 874 [turn_yregs(Tuple, MaxY)]; 875 (Other) -> 876 [Other] 877 end, Keis), 878 [{allocate_zero,FrameSz,MaxRegs}|Keis1]. 879 880%% turn_yregs(Size, Tuple, MaxY) -> Tuple' 881%% Renumber y register so that {y,0} becomes {y,FrameSize-1}, 882%% {y,FrameSize-1} becomes {y,0} and so on. This is to make nested 883%% catches work. The code generation algorithm gives a lower register 884%% number to the outer catch, which is wrong. 885 886turn_yregs({call,_,_}=I, _MaxY) -> I; 887turn_yregs({call_ext,_,_}=I, _MaxY) -> I; 888turn_yregs({jump,_}=I, _MaxY) -> I; 889turn_yregs({label,_}=I, _MaxY) -> I; 890turn_yregs({line,_}=I, _MaxY) -> I; 891turn_yregs({test_heap,_,_}=I, _MaxY) -> I; 892turn_yregs({bif,Op,F,A,B}, MaxY) -> 893 {bif,Op,F,turn_yreg(A, MaxY),turn_yreg(B, MaxY)}; 894turn_yregs({gc_bif,Op,F,Live,A,B}, MaxY) when is_integer(Live) -> 895 {gc_bif,Op,F,Live,turn_yreg(A, MaxY),turn_yreg(B, MaxY)}; 896turn_yregs({get_tuple_element,S,N,D}, MaxY) -> 897 {get_tuple_element,turn_yreg(S, MaxY),N,turn_yreg(D, MaxY)}; 898turn_yregs({put_tuple,Arity,D}, MaxY) -> 899 {put_tuple,Arity,turn_yreg(D, MaxY)}; 900turn_yregs({select_val,R,F,L}, MaxY) -> 901 {select_val,turn_yreg(R, MaxY),F,L}; 902turn_yregs({test,Op,F,L}, MaxY) -> 903 {test,Op,F,turn_yreg(L, MaxY)}; 904turn_yregs({test,Op,F,Live,A,B}, MaxY) when is_integer(Live) -> 905 {test,Op,F,Live,turn_yreg(A, MaxY),turn_yreg(B, MaxY)}; 906turn_yregs({Op,A}, MaxY) -> 907 {Op,turn_yreg(A, MaxY)}; 908turn_yregs({Op,A,B}, MaxY) -> 909 {Op,turn_yreg(A, MaxY),turn_yreg(B, MaxY)}; 910turn_yregs({Op,A,B,C}, MaxY) -> 911 {Op,turn_yreg(A, MaxY),turn_yreg(B, MaxY),turn_yreg(C, MaxY)}; 912turn_yregs(Tuple, MaxY) -> 913 turn_yregs(tuple_size(Tuple), Tuple, MaxY). 914 915turn_yregs(1, Tp, _) -> 916 Tp; 917turn_yregs(N, Tp, MaxY) -> 918 E = turn_yreg(element(N, Tp), MaxY), 919 turn_yregs(N-1, setelement(N, Tp, E), MaxY). 920 921turn_yreg({yy,YY}, MaxY) -> 922 {y,MaxY-YY}; 923turn_yreg({list,Ls},MaxY) -> 924 {list,turn_yreg(Ls, MaxY)}; 925turn_yreg([_|_]=Ts, MaxY) -> 926 [turn_yreg(T, MaxY) || T <- Ts]; 927turn_yreg(Other, _MaxY) -> 928 Other. 929 930%% select_cg(Sclause, V, TypeFail, ValueFail, StackReg, State) -> 931%% {Is,StackReg,State}. 932%% Selecting type and value needs two failure labels, TypeFail is the 933%% label to jump to of the next type test when this type fails, and 934%% ValueFail is the label when this type is correct but the value is 935%% wrong. These are different as in the second case there is no need 936%% to try the next type, it will always fail. 937 938select_cg(#k_type_clause{type=Type,values=Vs}, Var, Tf, Vf, Bef, St) -> 939 #k_var{name=V} = Var, 940 select_cg(Type, Vs, V, Tf, Vf, Bef, St). 941 942select_cg(k_cons, [S], V, Tf, Vf, Bef, St) -> 943 select_cons(S, V, Tf, Vf, Bef, St); 944select_cg(k_nil, [S], V, Tf, Vf, Bef, St) -> 945 select_nil(S, V, Tf, Vf, Bef, St); 946select_cg(k_binary, [S], V, Tf, Vf, Bef, St) -> 947 select_binary(S, V, Tf, Vf, Bef, St); 948select_cg(k_bin_seg, S, V, Tf, _Vf, Bef, St) -> 949 select_bin_segs(S, V, Tf, Bef, St); 950select_cg(k_bin_int, S, V, Tf, _Vf, Bef, St) -> 951 select_bin_segs(S, V, Tf, Bef, St); 952select_cg(k_bin_end, [S], V, Tf, _Vf, Bef, St) -> 953 select_bin_end(S, V, Tf, Bef, St); 954select_cg(k_map, S, V, Tf, Vf, Bef, St) -> 955 select_map(S, V, Tf, Vf, Bef, St); 956select_cg(k_literal, S, V, Tf, Vf, Bef, St) -> 957 select_literal(S, V, Tf, Vf, Bef, St); 958select_cg(Type, Scs, V, Tf, Vf, Bef, St0) -> 959 {Vis,{Aft,St1}} = 960 mapfoldl(fun (S, {Int,Sta}) -> 961 {Val,Is,Inta,Stb} = select_val(S, V, Vf, Bef, Sta), 962 {{Is,[Val]},{sr_merge(Int, Inta),Stb}} 963 end, {void,St0}, Scs), 964 OptVls = combine(lists:sort(combine(Vis))), 965 {Vls,Sis,St2} = select_labels(OptVls, St1, [], []), 966 {select_val_cg(Type, fetch_var(V, Bef), Vls, Tf, Vf, Sis), Aft, St2}. 967 968select_val_cg(k_tuple, R, [Arity,{f,Lbl}], Tf, Vf, [{label,Lbl}|Sis]) -> 969 [{test,is_tuple,{f,Tf},[R]},{test,test_arity,{f,Vf},[R,Arity]}|Sis]; 970select_val_cg(k_tuple, R, Vls, Tf, Vf, Sis) -> 971 [{test,is_tuple,{f,Tf},[R]},{select_tuple_arity,R,{f,Vf},{list,Vls}}|Sis]; 972select_val_cg(Type, R, [Val, {f,Lbl}], Fail, Fail, [{label,Lbl}|Sis]) -> 973 [{test,is_eq_exact,{f,Fail},[R,{type(Type),Val}]}|Sis]; 974select_val_cg(Type, R, [Val, {f,Lbl}], Tf, Vf, [{label,Lbl}|Sis]) -> 975 [{test,select_type_test(Type),{f,Tf},[R]}, 976 {test,is_eq_exact,{f,Vf},[R,{type(Type),Val}]}|Sis]; 977select_val_cg(Type, R, Vls0, Tf, Vf, Sis) -> 978 Vls1 = [case Value of 979 {f,_Lbl} -> Value; 980 _ -> {type(Type),Value} 981 end || Value <- Vls0], 982 [{test,select_type_test(Type),{f,Tf},[R]}, {select_val,R,{f,Vf},{list,Vls1}}|Sis]. 983 984type(k_atom) -> atom; 985type(k_float) -> float; 986type(k_int) -> integer. 987 988select_type_test(k_int) -> is_integer; 989select_type_test(k_atom) -> is_atom; 990select_type_test(k_float) -> is_float. 991 992combine([{Is,Vs1}, {Is,Vs2}|Vis]) -> combine([{Is,Vs1 ++ Vs2}|Vis]); 993combine([V|Vis]) -> [V|combine(Vis)]; 994combine([]) -> []. 995 996select_labels([{Is,Vs}|Vis], St0, Vls, Sis) -> 997 {Lbl,St1} = new_label(St0), 998 select_labels(Vis, St1, add_vls(Vs, Lbl, Vls), [[{label,Lbl}|Is]|Sis]); 999select_labels([], St, Vls, Sis) -> 1000 {Vls,append(Sis),St}. 1001 1002add_vls([V|Vs], Lbl, Acc) -> 1003 add_vls(Vs, Lbl, [V, {f,Lbl}|Acc]); 1004add_vls([], _, Acc) -> Acc. 1005 1006select_literal(S, V, Tf, Vf, Bef, St) -> 1007 Reg = fetch_var(V, Bef), 1008 F = fun(ValClause, Fail, St0) -> 1009 {Val,Is,Aft,St1} = select_val(ValClause, V, Vf, Bef, St0), 1010 Test = {test,is_eq_exact,{f,Fail},[Reg,{literal,Val}]}, 1011 {[Test|Is],Aft,St1} 1012 end, 1013 match_fmf(F, Tf, St, S). 1014 1015select_cons(#k_val_clause{val=#k_cons{hd=Hd,tl=Tl},body=B,anno=#l{i=I,vdb=Vdb}}, 1016 V, Tf, Vf, Bef, St0) -> 1017 Es = [Hd,Tl], 1018 {Eis,Int,St1} = select_extract_cons(V, Es, I, Vdb, Bef, St0), 1019 {Bis,Aft,St2} = match_cg(B, Vf, Int, St1), 1020 {[{test,is_nonempty_list,{f,Tf},[fetch_var(V, Bef)]}] ++ Eis ++ Bis,Aft,St2}. 1021 1022select_nil(#k_val_clause{val=#k_nil{},body=B}, V, Tf, Vf, Bef, St0) -> 1023 {Bis,Aft,St1} = match_cg(B, Vf, Bef, St0), 1024 {[{test,is_nil,{f,Tf},[fetch_var(V, Bef)]}] ++ Bis,Aft,St1}. 1025 1026select_binary(#k_val_clause{val=#k_binary{segs=#k_var{name=V}},body=B, 1027 anno=#l{i=I,vdb=Vdb}}, V, Tf, Vf, Bef, St0) -> 1028 #cg{ctx=OldCtx} = St0, 1029 Int0 = clear_dead(Bef#sr{reg=Bef#sr.reg}, I, Vdb), 1030 {Bis0,Aft,St1} = match_cg(B, Vf, Int0, St0#cg{ctx=V}), 1031 CtxReg = fetch_var(V, Int0), 1032 Live = max_reg(Bef#sr.reg), 1033 Bis1 = [{test,bs_start_match2,{f,Tf},Live,[CtxReg,{context,V}],CtxReg}, 1034 {bs_save2,CtxReg,{V,V}}|Bis0], 1035 Bis = finish_select_binary(Bis1), 1036 {Bis,Aft,St1#cg{ctx=OldCtx}}; 1037select_binary(#k_val_clause{val=#k_binary{segs=#k_var{name=Ivar}},body=B, 1038 anno=#l{i=I,vdb=Vdb}}, V, Tf, Vf, Bef, St0) -> 1039 #cg{ctx=OldCtx} = St0, 1040 Regs = put_reg(Ivar, Bef#sr.reg), 1041 Int0 = clear_dead(Bef#sr{reg=Regs}, I, Vdb), 1042 {Bis0,Aft,St1} = match_cg(B, Vf, Int0, St0#cg{ctx=Ivar}), 1043 CtxReg = fetch_var(Ivar, Int0), 1044 Live = max_reg(Bef#sr.reg), 1045 Bis1 = [{test,bs_start_match2,{f,Tf},Live, 1046 [fetch_var(V, Bef),{context,Ivar}],CtxReg}, 1047 {bs_save2,CtxReg,{Ivar,Ivar}}|Bis0], 1048 Bis = finish_select_binary(Bis1), 1049 {Bis,Aft,St1#cg{ctx=OldCtx}}. 1050 1051finish_select_binary([{bs_save2,R,Point}=I,{bs_restore2,R,Point}|Is]) -> 1052 [I|finish_select_binary(Is)]; 1053finish_select_binary([{bs_save2,R,Point}=I,{test,is_eq_exact,_,_}=Test, 1054 {bs_restore2,R,Point}|Is]) -> 1055 [I,Test|finish_select_binary(Is)]; 1056finish_select_binary([{test,bs_match_string,F,[Ctx,BinList]}|Is]) 1057 when is_list(BinList) -> 1058 I = {test,bs_match_string,F,[Ctx,list_to_bitstring(BinList)]}, 1059 [I|finish_select_binary(Is)]; 1060finish_select_binary([I|Is]) -> 1061 [I|finish_select_binary(Is)]; 1062finish_select_binary([]) -> []. 1063 1064%% New instructions for selection of binary segments. 1065 1066select_bin_segs(Scs, Ivar, Tf, Bef, St) -> 1067 match_fmf(fun(S, Fail, Sta) -> 1068 select_bin_seg(S, Ivar, Fail, Bef, Sta) end, 1069 Tf, St, Scs). 1070 1071select_bin_seg(#k_val_clause{val=#k_bin_seg{size=Size,unit=U,type=T, 1072 seg=Seg,flags=Fs0,next=Next}, 1073 body=B, 1074 anno=#l{i=I,vdb=Vdb,a=A}}, Ivar, Fail, Bef, St0) -> 1075 Ctx = St0#cg.ctx, 1076 Fs = [{anno,A}|Fs0], 1077 Es = case Next of 1078 [] -> [Seg]; 1079 _ -> [Seg,Next] 1080 end, 1081 {Mis,Int,St1} = select_extract_bin(Es, Size, U, T, Fs, Fail, 1082 I, Vdb, Bef, Ctx, B, St0), 1083 {Bis,Aft,St2} = match_cg(B, Fail, Int, St1), 1084 CtxReg = fetch_var(Ctx, Bef), 1085 Is = if 1086 Mis =:= [] -> 1087 %% No bs_restore2 instruction needed if no match instructions. 1088 Bis; 1089 true -> 1090 [{bs_restore2,CtxReg,{Ctx,Ivar}}|Mis++Bis] 1091 end, 1092 {Is,Aft,St2}; 1093select_bin_seg(#k_val_clause{val=#k_bin_int{size=Sz,unit=U,flags=Fs, 1094 val=Val,next=Next}, 1095 body=B, 1096 anno=#l{i=I,vdb=Vdb}}, Ivar, Fail, Bef, St0) -> 1097 Ctx = St0#cg.ctx, 1098 {Mis,Int,St1} = select_extract_int(Next, Val, Sz, U, Fs, Fail, 1099 I, Vdb, Bef, Ctx, St0), 1100 {Bis,Aft,St2} = match_cg(B, Fail, Int, St1), 1101 CtxReg = fetch_var(Ctx, Bef), 1102 Is = case Mis ++ Bis of 1103 [{test,bs_match_string,F,[OtherCtx,Bin1]}, 1104 {bs_save2,OtherCtx,_}, 1105 {bs_restore2,OtherCtx,_}, 1106 {test,bs_match_string,F,[OtherCtx,Bin2]}|Is0] -> 1107 %% We used to do this optimization later, but it 1108 %% turns out that in huge functions with many 1109 %% bs_match_string instructions, it's a big win 1110 %% to do the combination now. To avoid copying the 1111 %% binary data again and again, we'll combine bitstrings 1112 %% in a list and convert all of it to a bitstring later. 1113 [{test,bs_match_string,F,[OtherCtx,[Bin1,Bin2]]}|Is0]; 1114 Is0 -> 1115 Is0 1116 end, 1117 {[{bs_restore2,CtxReg,{Ctx,Ivar}}|Is],Aft,St2}. 1118 1119select_extract_int(#k_var{name=Tl}, Val, #k_int{val=Sz}, U, Fs, Vf, 1120 I, Vdb, Bef, Ctx, St) -> 1121 Bits = U*Sz, 1122 Bin = case member(big, Fs) of 1123 true -> 1124 <<Val:Bits>>; 1125 false -> 1126 true = member(little, Fs), %Assertion. 1127 <<Val:Bits/little>> 1128 end, 1129 Bits = bit_size(Bin), %Assertion. 1130 CtxReg = fetch_var(Ctx, Bef), 1131 Is = if 1132 Bits =:= 0 -> 1133 [{bs_save2,CtxReg,{Ctx,Tl}}]; 1134 true -> 1135 [{test,bs_match_string,{f,Vf},[CtxReg,Bin]}, 1136 {bs_save2,CtxReg,{Ctx,Tl}}] 1137 end, 1138 {Is,clear_dead(Bef, I, Vdb),St}. 1139 1140select_extract_bin([#k_var{name=Hd},#k_var{name=Tl}], Size0, Unit, Type, Flags, Vf, 1141 I, Vdb, Bef, Ctx, _Body, St) -> 1142 SizeReg = get_bin_size_reg(Size0, Bef), 1143 {Es,Aft} = 1144 case vdb_find(Hd, Vdb) of 1145 {_,_,Lhd} when Lhd =< I -> 1146 %% The extracted value will not be used. 1147 CtxReg = fetch_var(Ctx, Bef), 1148 Live = max_reg(Bef#sr.reg), 1149 Skip = build_skip_instr(Type, Vf, CtxReg, Live, 1150 SizeReg, Unit, Flags), 1151 {[Skip,{bs_save2,CtxReg,{Ctx,Tl}}],Bef}; 1152 {_,_,_} -> 1153 Reg = put_reg(Hd, Bef#sr.reg), 1154 Int1 = Bef#sr{reg=Reg}, 1155 Rhd = fetch_reg(Hd, Reg), 1156 CtxReg = fetch_reg(Ctx, Reg), 1157 Live = max_reg(Bef#sr.reg), 1158 {[build_bs_instr(Type, Vf, CtxReg, Live, SizeReg, 1159 Unit, Flags, Rhd), 1160 {bs_save2,CtxReg,{Ctx,Tl}}],Int1} 1161 end, 1162 {Es,clear_dead(Aft, I, Vdb),St}; 1163select_extract_bin([#k_var{name=Hd}], Size, Unit, binary, Flags, Vf, 1164 I, Vdb, Bef, Ctx, Body, St) -> 1165 %% Match the last segment of a binary. We KNOW that the size 1166 %% must be 'all'. 1167 #k_atom{val=all} = Size, %Assertion. 1168 {Es,Aft} = 1169 case vdb_find(Hd, Vdb) of 1170 {_,_,Lhd} when Lhd =< I -> 1171 %% The result will not be used. Furthermore, since we 1172 %% we are at the end of the binary, the position will 1173 %% not be used again; thus, it is safe to do a cheaper 1174 %% test of the unit. 1175 CtxReg = fetch_var(Ctx, Bef), 1176 {case Unit of 1177 1 -> 1178 []; 1179 _ -> 1180 [{test,bs_test_unit,{f,Vf},[CtxReg,Unit]}] 1181 end,Bef}; 1182 {_,_,_} -> 1183 case is_context_unused(Body) of 1184 false -> 1185 Reg = put_reg(Hd, Bef#sr.reg), 1186 Int1 = Bef#sr{reg=Reg}, 1187 Rhd = fetch_reg(Hd, Reg), 1188 CtxReg = fetch_reg(Ctx, Reg), 1189 Name = bs_get_binary2, 1190 Live = max_reg(Bef#sr.reg), 1191 {[{test,Name,{f,Vf},Live, 1192 [CtxReg,atomic(Size),Unit,{field_flags,Flags}],Rhd}], 1193 Int1}; 1194 true -> 1195 %% Since the matching context will not be used again, 1196 %% we can reuse its register. Reusing the register 1197 %% opens some interesting optimizations in the 1198 %% run-time system. 1199 1200 Reg0 = Bef#sr.reg, 1201 CtxReg = fetch_reg(Ctx, Reg0), 1202 Reg = replace_reg_contents(Ctx, Hd, Reg0), 1203 Int1 = Bef#sr{reg=Reg}, 1204 Name = bs_get_binary2, 1205 Live = max_reg(Int1#sr.reg), 1206 {[{test,Name,{f,Vf},Live, 1207 [CtxReg,atomic(Size),Unit,{field_flags,Flags}],CtxReg}], 1208 Int1} 1209 end 1210 end, 1211 {Es,clear_dead(Aft, I, Vdb),St}. 1212 1213%% is_context_unused(Ke) -> true | false 1214%% Simple heurististic to determine whether the code that follows 1215%% will use the current matching context again. (The liveness 1216%% information is too conservative to be useful for this purpose.) 1217%% 'true' means that the code that follows will definitely not use 1218%% the context again (because it is a block, not guard or matching 1219%% code); 'false' that we are not sure (there could be more 1220%% matching). 1221 1222is_context_unused(#k_alt{then=Then}) -> 1223 %% #k_alt{} can be used for different purposes. If the Then part 1224 %% is a block, it means that matching has finished and is used for a guard 1225 %% to choose between the matched clauses. 1226 is_context_unused(Then); 1227is_context_unused(#cg_block{}) -> 1228 true; 1229is_context_unused(_) -> 1230 false. 1231 1232select_bin_end(#k_val_clause{val=#k_bin_end{},body=B}, Ivar, Tf, Bef, St0) -> 1233 Ctx = St0#cg.ctx, 1234 {Bis,Aft,St2} = match_cg(B, Tf, Bef, St0), 1235 CtxReg = fetch_var(Ctx, Bef), 1236 {[{bs_restore2,CtxReg,{Ctx,Ivar}}, 1237 {test,bs_test_tail2,{f,Tf},[CtxReg,0]}|Bis],Aft,St2}. 1238 1239get_bin_size_reg(#k_var{name=V}, Bef) -> 1240 fetch_var(V, Bef); 1241get_bin_size_reg(Literal, _Bef) -> 1242 atomic(Literal). 1243 1244build_bs_instr(Type, Vf, CtxReg, Live, SizeReg, Unit, Flags, Rhd) -> 1245 {Format,Name} = case Type of 1246 integer -> {plain,bs_get_integer2}; 1247 float -> {plain,bs_get_float2}; 1248 binary -> {plain,bs_get_binary2}; 1249 utf8 -> {utf,bs_get_utf8}; 1250 utf16 -> {utf,bs_get_utf16}; 1251 utf32 -> {utf,bs_get_utf32} 1252 end, 1253 case Format of 1254 plain -> 1255 {test,Name,{f,Vf},Live, 1256 [CtxReg,SizeReg,Unit,{field_flags,Flags}],Rhd}; 1257 utf -> 1258 {test,Name,{f,Vf},Live, 1259 [CtxReg,{field_flags,Flags}],Rhd} 1260 end. 1261 1262build_skip_instr(Type, Vf, CtxReg, Live, SizeReg, Unit, Flags) -> 1263 {Format,Name} = case Type of 1264 utf8 -> {utf,bs_skip_utf8}; 1265 utf16 -> {utf,bs_skip_utf16}; 1266 utf32 -> {utf,bs_skip_utf32}; 1267 _ -> {plain,bs_skip_bits2} 1268 end, 1269 case Format of 1270 plain -> 1271 {test,Name,{f,Vf},[CtxReg,SizeReg,Unit,{field_flags,Flags}]}; 1272 utf -> 1273 {test,Name,{f,Vf},[CtxReg,Live,{field_flags,Flags}]} 1274 end. 1275 1276select_val(#k_val_clause{val=#k_tuple{es=Es},body=B,anno=#l{i=I,vdb=Vdb}}, 1277 V, Vf, Bef, St0) -> 1278 {Eis,Int,St1} = select_extract_tuple(V, Es, I, Vdb, Bef, St0), 1279 {Bis,Aft,St2} = match_cg(B, Vf, Int, St1), 1280 {length(Es),Eis ++ Bis,Aft,St2}; 1281select_val(#k_val_clause{val=Val0,body=B}, _V, Vf, Bef, St0) -> 1282 Val = case Val0 of 1283 #k_atom{val=Lit} -> Lit; 1284 #k_float{val=Lit} -> Lit; 1285 #k_int{val=Lit} -> Lit; 1286 #k_literal{val=Lit} -> Lit 1287 end, 1288 {Bis,Aft,St1} = match_cg(B, Vf, Bef, St0), 1289 {Val,Bis,Aft,St1}. 1290 1291%% select_extract_tuple(Src, [V], I, Vdb, StackReg, State) -> 1292%% {[E],StackReg,State}. 1293%% Extract tuple elements, but only if they do not immediately die. 1294 1295select_extract_tuple(Src, Vs, I, Vdb, Bef, St) -> 1296 F = fun (#k_var{name=V}, {Int0,Elem}) -> 1297 case vdb_find(V, Vdb) of 1298 {V,_,L} when L =< I -> {[], {Int0,Elem+1}}; 1299 _Other -> 1300 Reg1 = put_reg(V, Int0#sr.reg), 1301 Int1 = Int0#sr{reg=Reg1}, 1302 Rsrc = fetch_var(Src, Int1), 1303 {[{get_tuple_element,Rsrc,Elem,fetch_reg(V, Reg1)}], 1304 {Int1,Elem+1}} 1305 end 1306 end, 1307 {Es,{Aft,_}} = flatmapfoldl(F, {Bef,0}, Vs), 1308 {Es,Aft,St}. 1309 1310select_map(Scs, V, Tf, Vf, Bef, St0) -> 1311 Reg = fetch_var(V, Bef), 1312 {Is,Aft,St1} = 1313 match_fmf(fun(#k_val_clause{val=#k_map{op=exact,es=Es}, 1314 body=B,anno=#l{i=I,vdb=Vdb}}, Fail, St1) -> 1315 select_map_val(V, Es, B, Fail, I, Vdb, Bef, St1) 1316 end, Vf, St0, Scs), 1317 {[{test,is_map,{f,Tf},[Reg]}|Is],Aft,St1}. 1318 1319select_map_val(V, Es, B, Fail, I, Vdb, Bef, St0) -> 1320 {Eis,Int,St1} = select_extract_map(V, Es, Fail, I, Vdb, Bef, St0), 1321 {Bis,Aft,St2} = match_cg(B, Fail, Int, St1), 1322 {Eis++Bis,Aft,St2}. 1323 1324select_extract_map(_, [], _, _, _, Bef, St) -> {[],Bef,St}; 1325select_extract_map(Src, Vs, Fail, I, Vdb, Bef, St) -> 1326 %% First split the instruction flow 1327 %% We want one set of each 1328 %% 1) has_map_fields (no target registers) 1329 %% 2) get_map_elements (with target registers) 1330 %% Assume keys are term-sorted 1331 Rsrc = fetch_var(Src, Bef), 1332 1333 {{HasKs,GetVs,HasVarKs,GetVarVs},Aft} = 1334 foldr(fun(#k_map_pair{key=#k_var{name=K},val=#k_var{name=V}}, 1335 {{HasKsi,GetVsi,HasVarVsi,GetVarVsi},Int0}) -> 1336 case vdb_find(V, Vdb) of 1337 {V,_,L} when L =< I -> 1338 RK = fetch_var(K,Int0), 1339 {{HasKsi,GetVsi,[RK|HasVarVsi],GetVarVsi},Int0}; 1340 _Other -> 1341 Reg1 = put_reg(V, Int0#sr.reg), 1342 Int1 = Int0#sr{reg=Reg1}, 1343 RK = fetch_var(K,Int0), 1344 RV = fetch_reg(V,Reg1), 1345 {{HasKsi,GetVsi,HasVarVsi,[[RK,RV]|GetVarVsi]},Int1} 1346 end; 1347 (#k_map_pair{key=Key,val=#k_var{name=V}}, 1348 {{HasKsi,GetVsi,HasVarVsi,GetVarVsi},Int0}) -> 1349 case vdb_find(V, Vdb) of 1350 {V,_,L} when L =< I -> 1351 {{[atomic(Key)|HasKsi],GetVsi,HasVarVsi,GetVarVsi},Int0}; 1352 _Other -> 1353 Reg1 = put_reg(V, Int0#sr.reg), 1354 Int1 = Int0#sr{reg=Reg1}, 1355 {{HasKsi,[atomic(Key),fetch_reg(V, Reg1)|GetVsi], 1356 HasVarVsi,GetVarVsi},Int1} 1357 end 1358 end, {{[],[],[],[]},Bef}, Vs), 1359 1360 Code = [{test,has_map_fields,{f,Fail},Rsrc,{list,HasKs}} || HasKs =/= []] ++ 1361 [{test,has_map_fields,{f,Fail},Rsrc,{list,[K]}} || K <- HasVarKs] ++ 1362 [{get_map_elements, {f,Fail},Rsrc,{list,GetVs}} || GetVs =/= []] ++ 1363 [{get_map_elements, {f,Fail},Rsrc,{list,[K,V]}} || [K,V] <- GetVarVs], 1364 {Code, Aft, St}. 1365 1366 1367select_extract_cons(Src, [#k_var{name=Hd},#k_var{name=Tl}], I, Vdb, Bef, St) -> 1368 Rsrc = fetch_var(Src, Bef), 1369 Int = clear_dead(Bef, I, Vdb), 1370 {{_,_,Lhd},{_,_,Ltl}} = {vdb_find(Hd, Vdb),vdb_find(Tl, Vdb)}, 1371 case {Lhd =< I, Ltl =< I} of 1372 {true,true} -> 1373 %% Both dead. 1374 {[],Bef,St}; 1375 {true,false} -> 1376 %% Head dead. 1377 Reg0 = put_reg(Tl, Bef#sr.reg), 1378 Aft = Int#sr{reg=Reg0}, 1379 Rtl = fetch_reg(Tl, Reg0), 1380 {[{get_tl,Rsrc,Rtl}],Aft,St}; 1381 {false,true} -> 1382 %% Tail dead. 1383 Reg0 = put_reg(Hd, Bef#sr.reg), 1384 Aft = Int#sr{reg=Reg0}, 1385 Rhd = fetch_reg(Hd, Reg0), 1386 {[{get_hd,Rsrc,Rhd}],Aft,St}; 1387 {false,false} -> 1388 %% Both used. 1389 Reg0 = put_reg(Tl, put_reg(Hd, Bef#sr.reg)), 1390 Aft = Bef#sr{reg=Reg0}, 1391 Rhd = fetch_reg(Hd, Reg0), 1392 Rtl = fetch_reg(Tl, Reg0), 1393 {[{get_hd,Rsrc,Rhd},{get_tl,Rsrc,Rtl}],Aft,St} 1394 end. 1395 1396guard_clause_cg(#k_guard_clause{anno=#l{vdb=Vdb},guard=G,body=B}, Fail, Bef, St0) -> 1397 {Gis,Int,St1} = guard_cg(G, Fail, Vdb, Bef, St0), 1398 {Bis,Aft,St} = match_cg(B, Fail, Int, St1), 1399 {Gis ++ Bis,Aft,St}. 1400 1401%% guard_cg(Guard, Fail, Vdb, StackReg, State) -> 1402%% {[Ainstr],StackReg,State}. 1403%% A guard is a boolean expression of tests. Tests return true or 1404%% false. A fault in a test causes the test to return false. Tests 1405%% never return the boolean, instead we generate jump code to go to 1406%% the correct exit point. Primops and tests all go to the next 1407%% instruction on success or jump to a failure label. 1408 1409guard_cg(#k_protected{arg=Ts,ret=Rs,anno=#l{vdb=Pdb}}, Fail, _Vdb, Bef, St) -> 1410 protected_cg(Ts, Rs, Fail, Pdb, Bef, St); 1411guard_cg(#k_test{anno=#l{i=I},op=Test0,args=As,inverted=Inverted}, 1412 Fail, Vdb, Bef, St0) -> 1413 #k_remote{mod=#k_atom{val=erlang},name=#k_atom{val=Test}} = Test0, 1414 case Inverted of 1415 false -> 1416 test_cg(Test, As, Fail, I, Vdb, Bef, St0); 1417 true -> 1418 {Psucc,St1} = new_label(St0), 1419 {Is,Aft,St2} = test_cg(Test, As, Psucc, I, Vdb, Bef, St1), 1420 {Is++[{jump,{f,Fail}},{label,Psucc}],Aft,St2} 1421 end; 1422guard_cg(G, _Fail, Vdb, Bef, St) -> 1423 %%ok = io:fwrite("cg ~w: ~p~n", [?LINE,{G,Fail,Vdb,Bef}]), 1424 {Gis,Aft,St1} = cg(G, Vdb, Bef, St), 1425 %%ok = io:fwrite("cg ~w: ~p~n", [?LINE,{Aft}]), 1426 {Gis,Aft,St1}. 1427 1428%% guard_cg_list([Kexpr], Fail, I, Vdb, StackReg, St) -> 1429%% {[Ainstr],StackReg,St}. 1430 1431guard_cg_list(Kes, Fail, Vdb, Bef, St0) -> 1432 {Keis,{Aft,St1}} = 1433 flatmapfoldl(fun (Ke, {Inta,Sta}) -> 1434 {Keis,Intb,Stb} = 1435 guard_cg(Ke, Fail, Vdb, Inta, Sta), 1436 {Keis,{Intb,Stb}} 1437 end, {Bef,St0}, need_heap(Kes)), 1438 {Keis,Aft,St1}. 1439 1440%% protected_cg([Kexpr], [Ret], Fail, I, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 1441%% Do a protected. Protecteds without return values are just done 1442%% for effect, the return value is not checked, success passes on to 1443%% the next instruction and failure jumps to Fail. If there are 1444%% return values then these must be set to 'false' on failure, 1445%% control always passes to the next instruction. 1446 1447protected_cg(Ts, [], Fail, Vdb, Bef, St0) -> 1448 %% Protect these calls, revert when done. 1449 {Tis,Aft,St1} = guard_cg_list(Ts, Fail, Vdb, Bef, St0#cg{bfail=Fail}), 1450 {Tis,Aft,St1#cg{bfail=St0#cg.bfail}}; 1451protected_cg(Ts, Rs, _Fail, Vdb, Bef, St0) -> 1452 {Pfail,St1} = new_label(St0), 1453 {Psucc,St2} = new_label(St1), 1454 {Tis,Aft,St3} = guard_cg_list(Ts, Pfail, Vdb, Bef, 1455 St2#cg{bfail=Pfail}), 1456 %%ok = io:fwrite("cg ~w: ~p~n", [?LINE,{Rs,I,Vdb,Aft}]), 1457 %% Set return values to false. 1458 Mis = [{move,{atom,false},fetch_var(V,Aft)}||#k_var{name=V} <- Rs], 1459 {Tis ++ [{jump,{f,Psucc}}, 1460 {label,Pfail}] ++ Mis ++ [{label,Psucc}], 1461 Aft,St3#cg{bfail=St0#cg.bfail}}. 1462 1463%% test_cg(TestName, Args, Fail, I, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 1464%% Generate test instruction. Use explicit fail label here. 1465 1466test_cg(is_map, [A], Fail, I, Vdb, Bef, St) -> 1467 %% We must avoid creating code like this: 1468 %% 1469 %% move x(0) y(0) 1470 %% is_map Fail [x(0)] 1471 %% make_fun => x(0) %% Overwrite x(0) 1472 %% put_map_assoc y(0) ... 1473 %% 1474 %% The code is safe, but beam_validator does not understand that. 1475 %% Extending beam_validator to handle such (rare) code as the 1476 %% above would make it slower for all programs. Instead, change 1477 %% the code generator to always prefer the Y register for is_map() 1478 %% and put_map_assoc() instructions, ensuring that they use the 1479 %% same register. 1480 Arg = cg_reg_arg_prefer_y(A, Bef), 1481 Aft = clear_dead(Bef, I, Vdb), 1482 {[{test,is_map,{f,Fail},[Arg]}],Aft,St}; 1483test_cg(is_boolean, [#k_atom{val=Val}], Fail, I, Vdb, Bef, St) -> 1484 Aft = clear_dead(Bef, I, Vdb), 1485 Is = case is_boolean(Val) of 1486 true -> []; 1487 false -> [{jump,{f,Fail}}] 1488 end, 1489 {Is,Aft,St}; 1490test_cg(Test, As, Fail, I, Vdb, Bef, St) -> 1491 Args = cg_reg_args(As, Bef), 1492 Aft = clear_dead(Bef, I, Vdb), 1493 {[beam_utils:bif_to_test(Test, Args, {f,Fail})],Aft,St}. 1494 1495%% match_fmf(Fun, LastFail, State, [Clause]) -> {Is,Aft,State}. 1496%% This is a special flatmapfoldl for match code gen where we 1497%% generate a "failure" label for each clause. The last clause uses 1498%% an externally generated failure label, LastFail. N.B. We do not 1499%% know or care how the failure labels are used. 1500 1501match_fmf(F, LastFail, St, [H]) -> 1502 F(H, LastFail, St); 1503match_fmf(F, LastFail, St0, [H|T]) -> 1504 {Fail,St1} = new_label(St0), 1505 {R,Aft1,St2} = F(H, Fail, St1), 1506 {Rs,Aft2,St3} = match_fmf(F, LastFail, St2, T), 1507 {R ++ [{label,Fail}] ++ Rs,sr_merge(Aft1, Aft2),St3}. 1508 1509%% call_cg(Func, [Arg], [Ret], Le, Vdb, StackReg, State) -> 1510%% {[Ainstr],StackReg,State}. 1511%% enter_cg(Func, [Arg], Le, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 1512%% Call and enter first put the arguments into registers and save any 1513%% other registers, then clean up and compress the stack and set the 1514%% frame size. Finally the actual call is made. Call then needs the 1515%% return values filled in. 1516 1517call_cg(#k_var{}=Var, As, Rs, Le, Vdb, Bef, St0) -> 1518 {Sis,Int} = cg_setup_call(As++[Var], Bef, Le#l.i, Vdb), 1519 %% Put return values in registers. 1520 Reg = load_vars(Rs, clear_regs(Int#sr.reg)), 1521 %% Build complete code and final stack/register state. 1522 Arity = length(As), 1523 {Frees,Aft} = free_dead(clear_dead(Int#sr{reg=Reg}, Le#l.i, Vdb)), 1524 {Sis ++ Frees ++ [line(Le),{call_fun,Arity}],Aft, 1525 need_stack_frame(St0)}; 1526call_cg(#k_remote{mod=Mod,name=Name}, As, Rs, Le, Vdb, Bef, St0) 1527 when is_record(Mod, k_var); is_record(Name, k_var) -> 1528 {Sis,Int} = cg_setup_call(As++[Mod,Name], Bef, Le#l.i, Vdb), 1529 %% Put return values in registers. 1530 Reg = load_vars(Rs, clear_regs(Int#sr.reg)), 1531 %% Build complete code and final stack/register state. 1532 Arity = length(As), 1533 St = need_stack_frame(St0), 1534 %%{Call,St1} = build_call(Func, Arity, St0), 1535 {Frees,Aft} = free_dead(clear_dead(Int#sr{reg=Reg}, Le#l.i, Vdb)), 1536 {Sis ++ Frees ++ [line(Le),{apply,Arity}],Aft,St}; 1537call_cg(Func, As, Rs, Le, Vdb, Bef, St0) -> 1538 case St0 of 1539 #cg{bfail=Fail} when Fail =/= 0 -> 1540 %% Inside a guard. The only allowed function call is to 1541 %% erlang:error/1,2. We will generate the following code: 1542 %% 1543 %% move {atom,ok} DestReg 1544 %% jump FailureLabel 1545 #k_remote{mod=#k_atom{val=erlang}, 1546 name=#k_atom{val=error}} = Func, %Assertion. 1547 [#k_var{name=DestVar}] = Rs, 1548 Int0 = clear_dead(Bef, Le#l.i, Vdb), 1549 Reg = put_reg(DestVar, Int0#sr.reg), 1550 Int = Int0#sr{reg=Reg}, 1551 Dst = fetch_reg(DestVar, Reg), 1552 {[{move,{atom,ok},Dst},{jump,{f,Fail}}], 1553 clear_dead(Int, Le#l.i, Vdb),St0}; 1554 #cg{} -> 1555 %% Ordinary function call in a function body. 1556 {Sis,Int} = cg_setup_call(As, Bef, Le#l.i, Vdb), 1557 %% Put return values in registers. 1558 Reg = load_vars(Rs, clear_regs(Int#sr.reg)), 1559 %% Build complete code and final stack/register state. 1560 Arity = length(As), 1561 {Call,St1} = build_call(Func, Arity, St0), 1562 {Frees,Aft} = free_dead(clear_dead(Int#sr{reg=Reg}, Le#l.i, Vdb)), 1563 {Sis ++ Frees ++ [line(Le)|Call],Aft,St1} 1564 end. 1565 1566build_call(#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val='!'}}, 2, St0) -> 1567 {[send],need_stack_frame(St0)}; 1568build_call(#k_remote{mod=#k_atom{val=Mod},name=#k_atom{val=Name}}, Arity, St0) -> 1569 {[{call_ext,Arity,{extfunc,Mod,Name,Arity}}],need_stack_frame(St0)}; 1570build_call(#k_local{name=Name}, Arity, St0) when is_atom(Name) -> 1571 {Lbl,St1} = local_func_label(Name, Arity, need_stack_frame(St0)), 1572 {[{call,Arity,{f,Lbl}}],St1}. 1573 1574free_dead(#sr{stk=Stk0}=Aft) -> 1575 {Instr,Stk} = free_dead(Stk0, 0, [], []), 1576 {Instr,Aft#sr{stk=Stk}}. 1577 1578free_dead([dead|Stk], Y, Instr, StkAcc) -> 1579 %% Note: kill/1 is equivalent to init/1 (translated by beam_asm). 1580 %% We use kill/1 to help further optimisation passes. 1581 free_dead(Stk, Y+1, [{kill,{yy,Y}}|Instr], [free|StkAcc]); 1582free_dead([Any|Stk], Y, Instr, StkAcc) -> 1583 free_dead(Stk, Y+1, Instr, [Any|StkAcc]); 1584free_dead([], _, Instr, StkAcc) -> {Instr,reverse(StkAcc)}. 1585 1586enter_cg(#k_var{} = Var, As, Le, Vdb, Bef, St0) -> 1587 {Sis,Int} = cg_setup_call(As++[Var], Bef, Le#l.i, Vdb), 1588 %% Build complete code and final stack/register state. 1589 Arity = length(As), 1590 {Sis ++ [line(Le),{call_fun,Arity},return], 1591 clear_dead(Int#sr{reg=clear_regs(Int#sr.reg)}, Le#l.i, Vdb), 1592 need_stack_frame(St0)}; 1593enter_cg(#k_remote{mod=Mod,name=Name}, As, Le, Vdb, Bef, St0) 1594 when is_record(Mod, k_var); is_record(Name, k_var) -> 1595 {Sis,Int} = cg_setup_call(As++[Mod,Name], Bef, Le#l.i, Vdb), 1596 %% Build complete code and final stack/register state. 1597 Arity = length(As), 1598 St = need_stack_frame(St0), 1599 {Sis ++ [line(Le),{apply_only,Arity}], 1600 clear_dead(Int#sr{reg=clear_regs(Int#sr.reg)}, Le#l.i, Vdb), 1601 St}; 1602enter_cg(Func, As, Le, Vdb, Bef, St0) -> 1603 {Sis,Int} = cg_setup_call(As, Bef, Le#l.i, Vdb), 1604 %% Build complete code and final stack/register state. 1605 Arity = length(As), 1606 {Call,St1} = build_enter(Func, Arity, St0), 1607 Line = enter_line(Func, Arity, Le), 1608 {Sis ++ Line ++ Call, 1609 clear_dead(Int#sr{reg=clear_regs(Int#sr.reg)}, Le#l.i, Vdb), 1610 St1}. 1611 1612build_enter(#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val='!'}}, 2, St0) -> 1613 {[send,return],need_stack_frame(St0)}; 1614build_enter(#k_remote{mod=#k_atom{val=Mod},name=#k_atom{val=Name}}, Arity, St0) -> 1615 St1 = case trap_bif(Mod, Name, Arity) of 1616 true -> need_stack_frame(St0); 1617 false -> St0 1618 end, 1619 {[{call_ext_only,Arity,{extfunc,Mod,Name,Arity}}],St1}; 1620build_enter(#k_local{name=Name}, Arity, St0) when is_atom(Name) -> 1621 {Lbl,St1} = local_func_label(Name, Arity, St0), 1622 {[{call_only,Arity,{f,Lbl}}],St1}. 1623 1624enter_line(#k_remote{mod=#k_atom{val=Mod},name=#k_atom{val=Name}}, Arity, Le) -> 1625 case erl_bifs:is_safe(Mod, Name, Arity) of 1626 false -> 1627 %% Tail-recursive call, possibly to a BIF. 1628 %% We'll need a line instruction in case the 1629 %% BIF call fails. 1630 [line(Le)]; 1631 true -> 1632 %% Call to a safe BIF. Since it cannot fail, 1633 %% we don't need any line instruction here. 1634 [] 1635 end; 1636enter_line(_, _, _) -> 1637 %% Tail-recursive call to a local function. A line 1638 %% instruction will not be useful. 1639 []. 1640 1641%% local_func_label(Name, Arity, State) -> {Label,State'} 1642%% local_func_label({Name,Arity}, State) -> {Label,State'} 1643%% Get the function entry label for a local function. 1644 1645local_func_label(Name, Arity, St) -> 1646 local_func_label({Name,Arity}, St). 1647 1648local_func_label(Key, #cg{functable=Map}=St0) -> 1649 case Map of 1650 #{Key := Label} -> {Label,St0}; 1651 _ -> 1652 {Label,St} = new_label(St0), 1653 {Label,St#cg{functable=Map#{Key => Label}}} 1654 end. 1655 1656%% need_stack_frame(State) -> State' 1657%% Make a note in the state that this function will need a stack frame. 1658 1659need_stack_frame(#cg{need_frame=true}=St) -> St; 1660need_stack_frame(St) -> St#cg{need_frame=true}. 1661 1662%% trap_bif(Mod, Name, Arity) -> true|false 1663%% Trap bifs that need a stack frame. 1664 1665trap_bif(erlang, link, 1) -> true; 1666trap_bif(erlang, unlink, 1) -> true; 1667trap_bif(erlang, monitor_node, 2) -> true; 1668trap_bif(erlang, group_leader, 2) -> true; 1669trap_bif(erlang, exit, 2) -> true; 1670trap_bif(_, _, _) -> false. 1671 1672%% bif_cg(#k_bif{}, Le, Vdb, StackReg, State) -> 1673%% {[Ainstr],StackReg,State}. 1674%% Generate code a BIF. 1675 1676bif_cg(#k_bif{op=#k_internal{name=Name},args=As,ret=Rs}, Le, Vdb, Bef, St) -> 1677 internal_cg(Name, As, Rs, Le, Vdb, Bef, St); 1678bif_cg(#k_bif{op=#k_remote{mod=#k_atom{val=erlang},name=#k_atom{val=Name}}, 1679 args=As,ret=Rs}, Le, Vdb, Bef, St) -> 1680 Ar = length(As), 1681 case is_gc_bif(Name, Ar) of 1682 false -> 1683 bif_cg(Name, As, Rs, Le, Vdb, Bef, St); 1684 true -> 1685 gc_bif_cg(Name, As, Rs, Le, Vdb, Bef, St) 1686 end. 1687 1688%% internal_cg(Bif, [Arg], [Ret], Le, Vdb, StackReg, State) -> 1689%% {[Ainstr],StackReg,State}. 1690 1691internal_cg(bs_context_to_binary=Instr, [Src0], [], Le, Vdb, Bef, St0) -> 1692 [Src] = cg_reg_args([Src0], Bef), 1693 {[{Instr,Src}],clear_dead(Bef, Le#l.i, Vdb), St0}; 1694internal_cg(dsetelement, [Index0,Tuple0,New0], _Rs, Le, Vdb, Bef, St0) -> 1695 [New,Tuple,{integer,Index1}] = cg_reg_args([New0,Tuple0,Index0], Bef), 1696 Index = Index1-1, 1697 {[{set_tuple_element,New,Tuple,Index}], 1698 clear_dead(Bef, Le#l.i, Vdb), St0}; 1699internal_cg(make_fun, [Func0,Arity0|As], Rs, Le, Vdb, Bef, St0) -> 1700 %% This behaves more like a function call. 1701 #k_atom{val=Func} = Func0, 1702 #k_int{val=Arity} = Arity0, 1703 {Sis,Int} = cg_setup_call(As, Bef, Le#l.i, Vdb), 1704 Reg = load_vars(Rs, clear_regs(Int#sr.reg)), 1705 {FuncLbl,St1} = local_func_label(Func, Arity, St0), 1706 MakeFun = {make_fun2,{f,FuncLbl},0,0,length(As)}, 1707 {Sis ++ [MakeFun], 1708 clear_dead(Int#sr{reg=Reg}, Le#l.i, Vdb), 1709 St1}; 1710internal_cg(bs_init_writable=I, As, Rs, Le, Vdb, Bef, St) -> 1711 %% This behaves like a function call. 1712 {Sis,Int} = cg_setup_call(As, Bef, Le#l.i, Vdb), 1713 Reg = load_vars(Rs, clear_regs(Int#sr.reg)), 1714 {Sis++[I],clear_dead(Int#sr{reg=Reg}, Le#l.i, Vdb),St}; 1715internal_cg(build_stacktrace=I, As, Rs, Le, Vdb, Bef, St) -> 1716 %% This behaves like a function call. 1717 {Sis,Int} = cg_setup_call(As, Bef, Le#l.i, Vdb), 1718 Reg = load_vars(Rs, clear_regs(Int#sr.reg)), 1719 {Sis++[I],clear_dead(Int#sr{reg=Reg}, Le#l.i, Vdb),St}; 1720internal_cg(raise, As, Rs, Le, Vdb, Bef, St) -> 1721 %% raise can be treated like a guard BIF. 1722 bif_cg(raise, As, Rs, Le, Vdb, Bef, St); 1723internal_cg(guard_error, [ExitCall], _Rs, Le, Vdb, Bef, St) -> 1724 %% A call an exit BIF from inside a #k_guard_match{}. 1725 %% Generate a standard call, but leave the register descriptors 1726 %% alone, effectively pretending that there was no call. 1727 #k_call{op=#k_remote{mod=#k_atom{val=Mod},name=#k_atom{val=Name}}, 1728 args=As} = ExitCall, 1729 Arity = length(As), 1730 {Ms,_} = cg_call_args(As, Bef, Le#l.i, Vdb), 1731 Call = {call_ext,Arity,{extfunc,Mod,Name,Arity}}, 1732 Is = Ms++[line(Le),Call], 1733 {Is,Bef,St}; 1734internal_cg(raw_raise=I, As, Rs, Le, Vdb, Bef, St) -> 1735 %% This behaves like a function call. 1736 {Sis,Int} = cg_setup_call(As, Bef, Le#l.i, Vdb), 1737 Reg = load_vars(Rs, clear_regs(Int#sr.reg)), 1738 {Sis++[I],clear_dead(Int#sr{reg=Reg}, Le#l.i, Vdb),St}. 1739 1740%% bif_cg(Bif, [Arg], [Ret], Le, Vdb, StackReg, State) -> 1741%% {[Ainstr],StackReg,State}. 1742 1743bif_cg(Bif, As, [#k_var{name=V}], Le, Vdb, Bef, St0) -> 1744 Ars = cg_reg_args(As, Bef), 1745 1746 %% If we are inside a catch and in a body (not in guard) and the 1747 %% BIF may fail, we must save everything that will be alive after 1748 %% the catch (because the code after the code assumes that all 1749 %% variables that are live are stored on the stack). 1750 %% 1751 %% Currently, we are somewhat pessimistic in 1752 %% that we save any variable that will be live after this BIF call. 1753 1754 MayFail = not erl_bifs:is_safe(erlang, Bif, length(As)), 1755 {Sis,Int0} = 1756 case MayFail of 1757 true -> 1758 maybe_adjust_stack(Bef, Le#l.i, Le#l.i+1, Vdb, St0); 1759 false -> 1760 {[],Bef} 1761 end, 1762 Int1 = clear_dead(Int0, Le#l.i, Vdb), 1763 Reg = put_reg(V, Int1#sr.reg), 1764 Int = Int1#sr{reg=Reg}, 1765 Dst = fetch_reg(V, Reg), 1766 BifFail = {f,St0#cg.bfail}, 1767 %% We need a line instructions for BIFs that may fail in a body. 1768 Line = case BifFail of 1769 {f,0} when MayFail -> 1770 [line(Le)]; 1771 _ -> 1772 [] 1773 end, 1774 {Sis++Line++[{bif,Bif,BifFail,Ars,Dst}], 1775 clear_dead(Int, Le#l.i, Vdb), St0}. 1776 1777 1778%% gc_bif_cg(Bif, [Arg], [Ret], Le, Vdb, StackReg, State) -> 1779%% {[Ainstr],StackReg,State}. 1780 1781gc_bif_cg(Bif, As, [#k_var{name=V}], Le, Vdb, Bef, St0) -> 1782 Ars = cg_reg_args(As, Bef), 1783 1784 %% If we are inside a catch and in a body (not in guard) and the 1785 %% BIF may fail, we must save everything that will be alive after 1786 %% the catch (because the code after the code assumes that all 1787 %% variables that are live are stored on the stack). 1788 %% 1789 %% Currently, we are somewhat pessimistic in 1790 %% that we save any variable that will be live after this BIF call. 1791 1792 {Sis,Int0} = maybe_adjust_stack(Bef, Le#l.i, Le#l.i+1, Vdb, St0), 1793 1794 Int1 = clear_dead(Int0, Le#l.i, Vdb), 1795 Reg = put_reg(V, Int1#sr.reg), 1796 Int = Int1#sr{reg=Reg}, 1797 Dst = fetch_reg(V, Reg), 1798 BifFail = {f,St0#cg.bfail}, 1799 Line = case BifFail of 1800 {f,0} -> [line(Le)]; 1801 {f,_} -> [] 1802 end, 1803 {Sis++Line++[{gc_bif,Bif,BifFail,max_reg(Bef#sr.reg),Ars,Dst}], 1804 clear_dead(Int, Le#l.i, Vdb), St0}. 1805 1806%% recv_loop_cg(TimeOut, ReceiveVar, ReceiveMatch, TimeOutExprs, 1807%% [Ret], Le, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 1808 1809recv_loop_cg(Te, Rvar, Rm, Tes, Rs, Le, Vdb, Bef, St0) -> 1810 {Sis,Int0} = adjust_stack(Bef, Le#l.i, Le#l.i, Vdb), 1811 Int1 = Int0#sr{reg=clear_regs(Int0#sr.reg)}, 1812 %% Get labels. 1813 {Rl,St1} = new_label(St0), 1814 {Tl,St2} = new_label(St1), 1815 {Bl,St3} = new_label(St2), 1816 St4 = St3#cg{break=Bl,recv=Rl}, %Set correct receive labels 1817 {Ris,Raft,St5} = cg_recv_mesg(Rvar, Rm, Tl, Int1, St4), 1818 {Wis,Taft,St6} = cg_recv_wait(Te, Tes, Le#l.i, Int1, St5), 1819 Int2 = sr_merge(Raft, Taft), %Merge stack/registers 1820 Reg = load_vars(Rs, Int2#sr.reg), 1821 {Sis ++ [line(Le)] ++ Ris ++ [{label,Tl}] ++ Wis ++ [{label,Bl}], 1822 clear_dead(Int2#sr{reg=Reg}, Le#l.i, Vdb), 1823 St6#cg{break=St0#cg.break,recv=St0#cg.recv}}. 1824 1825%% cg_recv_mesg( ) -> {[Ainstr],Aft,St}. 1826 1827cg_recv_mesg(#k_var{name=R}, Rm, Tl, Bef, St0) -> 1828 Int0 = Bef#sr{reg=put_reg(R, Bef#sr.reg)}, 1829 Ret = fetch_reg(R, Int0#sr.reg), 1830 %% Int1 = clear_dead(Int0, I, Rm#l.vdb), 1831 Int1 = Int0, 1832 {Mis,Int2,St1} = match_cg(Rm, none, Int1, St0), 1833 {[{label,St1#cg.recv},{loop_rec,{f,Tl},Ret}|Mis],Int2,St1}. 1834 1835%% cg_recv_wait(Te, Tes, I, Vdb, Int2, St3) -> {[Ainstr],Aft,St}. 1836 1837cg_recv_wait(#k_atom{val=infinity}, #cg_block{anno=Le,es=Tes}, I, Bef, St0) -> 1838 %% We know that the 'after' body will never be executed. 1839 %% But to keep the stack and register information up to date, 1840 %% we will generate the code for the 'after' body, and then discard it. 1841 Int1 = clear_dead(Bef, I, Le#l.vdb), 1842 {_,Int2,St1} = cg_block(Tes, Le#l.vdb, 1843 Int1#sr{reg=clear_regs(Int1#sr.reg)}, St0), 1844 {[{wait,{f,St1#cg.recv}}],Int2,St1}; 1845cg_recv_wait(#k_int{val=0}, #cg_block{anno=Le,es=Tes}, _I, Bef, St0) -> 1846 {Tis,Int,St1} = cg_block(Tes, Le#l.vdb, Bef, St0), 1847 {[timeout|Tis],Int,St1}; 1848cg_recv_wait(Te, #cg_block{anno=Le,es=Tes}, I, Bef, St0) -> 1849 Reg = cg_reg_arg(Te, Bef), 1850 %% Must have empty registers here! Bug if anything in registers. 1851 Int0 = clear_dead(Bef, I, Le#l.vdb), 1852 {Tis,Int,St1} = cg_block(Tes, Le#l.vdb, 1853 Int0#sr{reg=clear_regs(Int0#sr.reg)}, St0), 1854 {[{wait_timeout,{f,St1#cg.recv},Reg},timeout] ++ Tis,Int,St1}. 1855 1856%% recv_next_cg(Le, Vdb, StackReg, St) -> {[Ainstr],StackReg,St}. 1857%% Use adjust stack to clear stack, but only need it for Aft. 1858 1859recv_next_cg(Le, Vdb, Bef, St) -> 1860 {Sis,Aft} = adjust_stack(Bef, Le#l.i, Le#l.i+1, Vdb), 1861 {[{loop_rec_end,{f,St#cg.recv}}] ++ Sis,Aft,St}. %Joke 1862 1863%% try_cg(TryBlock, [BodyVar], TryBody, [ExcpVar], TryHandler, [Ret], 1864%% Le, Vdb, StackReg, St) -> {[Ainstr],StackReg,St}. 1865 1866try_cg(Ta, Vs, Tb, Evs, Th, Rs, Le, Vdb, Bef, St0) -> 1867 {B,St1} = new_label(St0), %Body label 1868 {H,St2} = new_label(St1), %Handler label 1869 {E,St3} = new_label(St2), %End label 1870 #l{i=TryTag} = get_kanno(Ta), 1871 Int1 = Bef#sr{stk=put_catch(TryTag, Bef#sr.stk)}, 1872 TryReg = fetch_stack({catch_tag,TryTag}, Int1#sr.stk), 1873 {Ais,Int2,St4} = cg(Ta, Vdb, Int1, St3#cg{break=B,in_catch=true}), 1874 Int3 = Int2#sr{stk=drop_catch(TryTag, Int2#sr.stk)}, 1875 St5 = St4#cg{break=E,in_catch=St3#cg.in_catch}, 1876 {Bis,Baft,St6} = cg(Tb, Vdb, Int3#sr{reg=load_vars(Vs, Int3#sr.reg)}, St5), 1877 {His,Haft,St7} = cg(Th, Vdb, Int3#sr{reg=load_vars(Evs, Int3#sr.reg)}, St6), 1878 Int4 = sr_merge(Baft, Haft), %Merge stack/registers 1879 Aft = Int4#sr{reg=load_vars(Rs, Int4#sr.reg)}, 1880 {[{'try',TryReg,{f,H}}] ++ Ais ++ 1881 [{label,B},{try_end,TryReg}] ++ Bis ++ 1882 [{label,H},{try_case,TryReg}] ++ His ++ 1883 [{label,E}], 1884 clear_dead(Aft, Le#l.i, Vdb), 1885 St7#cg{break=St0#cg.break}}. 1886 1887try_enter_cg(Ta, Vs, Tb, Evs, Th, Le, Vdb, Bef, St0) -> 1888 {B,St1} = new_label(St0), %Body label 1889 {H,St2} = new_label(St1), %Handler label 1890 #l{i=TryTag} = get_kanno(Ta), 1891 Int1 = Bef#sr{stk=put_catch(TryTag, Bef#sr.stk)}, 1892 TryReg = fetch_stack({catch_tag,TryTag}, Int1#sr.stk), 1893 {Ais,Int2,St3} = cg(Ta, Vdb, Int1, St2#cg{break=B,in_catch=true}), 1894 Int3 = Int2#sr{stk=drop_catch(TryTag, Int2#sr.stk)}, 1895 St4 = St3#cg{in_catch=St2#cg.in_catch}, 1896 {Bis,Baft,St5} = cg(Tb, Vdb, Int3#sr{reg=load_vars(Vs, Int3#sr.reg)}, St4), 1897 {His,Haft,St6} = cg(Th, Vdb, Int3#sr{reg=load_vars(Evs, Int3#sr.reg)}, St5), 1898 Int4 = sr_merge(Baft, Haft), %Merge stack/registers 1899 Aft = Int4, 1900 {[{'try',TryReg,{f,H}}] ++ Ais ++ 1901 [{label,B},{try_end,TryReg}] ++ Bis ++ 1902 [{label,H},{try_case,TryReg}] ++ His, 1903 clear_dead(Aft, Le#l.i, Vdb), 1904 St6#cg{break=St0#cg.break}}. 1905 1906%% catch_cg(CatchBlock, Ret, Le, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 1907 1908catch_cg(#cg_block{es=C}, #k_var{name=R}, Le, Vdb, Bef, St0) -> 1909 {B,St1} = new_label(St0), 1910 CatchTag = Le#l.i, 1911 Int1 = Bef#sr{stk=put_catch(CatchTag, Bef#sr.stk)}, 1912 CatchReg = fetch_stack({catch_tag,CatchTag}, Int1#sr.stk), 1913 {Cis,Int2,St2} = cg_block(C, Le#l.vdb, Int1, 1914 St1#cg{break=B,in_catch=true}), 1915 [] = Int2#sr.reg, %Assertion. 1916 Aft = Int2#sr{reg=[{0,R}],stk=drop_catch(CatchTag, Int2#sr.stk)}, 1917 {[{'catch',CatchReg,{f,B}}] ++ Cis ++ 1918 [{label,B},{catch_end,CatchReg}], 1919 clear_dead(Aft, Le#l.i, Vdb), 1920 St2#cg{break=St1#cg.break,in_catch=St1#cg.in_catch}}. 1921 1922%% put_cg([Var], Constr, Le, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 1923%% We have to be careful how a 'put' works. First the structure is 1924%% built, then it is filled and finally things can be cleared. The 1925%% annotation must reflect this and make sure that the return 1926%% variable is allocated first. 1927%% 1928%% put_list and put_map are atomic instructions, both of 1929%% which can safely resuse one of the source registers as target. 1930 1931put_cg([#k_var{name=R}], #k_cons{hd=Hd,tl=Tl}, Le, Vdb, Bef, St) -> 1932 [S1,S2] = cg_reg_args([Hd,Tl], Bef), 1933 Int0 = clear_dead(Bef, Le#l.i, Vdb), 1934 Int1 = Int0#sr{reg=put_reg(R, Int0#sr.reg)}, 1935 Ret = fetch_reg(R, Int1#sr.reg), 1936 {[{put_list,S1,S2,Ret}], Int1, St}; 1937put_cg([#k_var{name=R}], #k_binary{segs=Segs}, Le, Vdb, Bef, 1938 #cg{bfail=Bfail}=St) -> 1939 %% At run-time, binaries are constructed in three stages: 1940 %% 1) First the size of the binary is calculated. 1941 %% 2) Then the binary is allocated. 1942 %% 3) Then each field in the binary is constructed. 1943 %% For simplicity, we use the target register to also hold the 1944 %% size of the binary. Therefore the target register must *not* 1945 %% be one of the source registers. 1946 1947 %% First allocate the target register. 1948 Int0 = Bef#sr{reg=put_reg(R, Bef#sr.reg)}, 1949 Target = fetch_reg(R, Int0#sr.reg), 1950 1951 %% Also allocate a scratch register for size calculations. 1952 Temp = find_scratch_reg(Int0#sr.reg), 1953 1954 %% First generate the code that constructs each field. 1955 Fail = {f,Bfail}, 1956 PutCode = cg_bin_put(Segs, Fail, Bef), 1957 {Sis,Int1} = maybe_adjust_stack(Int0, Le#l.i, Le#l.i+1, Vdb, St), 1958 MaxRegs = max_reg(Bef#sr.reg), 1959 Aft = clear_dead(Int1, Le#l.i, Vdb), 1960 1961 %% Now generate the complete code for constructing the binary. 1962 Code = cg_binary(PutCode, Target, Temp, Fail, MaxRegs, Le#l.a), 1963 {Sis++Code,Aft,St}; 1964 1965%% Map: single variable key. 1966put_cg([#k_var{name=R}], #k_map{op=Op,var=Map, 1967 es=[#k_map_pair{key=#k_var{}=K,val=V}]}, 1968 Le, Vdb, Bef, St0) -> 1969 {Sis,Int0} = maybe_adjust_stack(Bef, Le#l.i, Le#l.i+1, Vdb, St0), 1970 1971 SrcReg = cg_reg_arg_prefer_y(Map, Int0), 1972 Line = line(Le#l.a), 1973 1974 List = [cg_reg_arg(K,Int0),cg_reg_arg(V,Int0)], 1975 1976 Live = max_reg(Bef#sr.reg), 1977 1978 %% The target register can reuse one of the source registers. 1979 Aft0 = clear_dead(Int0, Le#l.i, Vdb), 1980 Aft = Aft0#sr{reg=put_reg(R, Aft0#sr.reg)}, 1981 Target = fetch_reg(R, Aft#sr.reg), 1982 1983 {Is,St1} = put_cg_map(Line, Op, SrcReg, Target, Live, List, St0), 1984 {Sis++Is,Aft,St1}; 1985 1986%% Map: (possibly) multiple literal keys. 1987put_cg([#k_var{name=R}], #k_map{op=Op,var=Map,es=Es}, Le, Vdb, Bef, St0) -> 1988 1989 %% assert key literals 1990 [] = [Var || #k_map_pair{key=#k_var{}=Var} <- Es], 1991 1992 {Sis,Int0} = maybe_adjust_stack(Bef, Le#l.i, Le#l.i+1, Vdb, St0), 1993 SrcReg = cg_reg_arg_prefer_y(Map, Int0), 1994 Line = line(Le#l.a), 1995 1996 %% fetch registers for values to be put into the map 1997 List = flatmap(fun(#k_map_pair{key=K,val=V}) -> 1998 [atomic(K),cg_reg_arg(V, Int0)] 1999 end, Es), 2000 2001 Live = max_reg(Bef#sr.reg), 2002 2003 %% The target register can reuse one of the source registers. 2004 Aft0 = clear_dead(Int0, Le#l.i, Vdb), 2005 Aft = Aft0#sr{reg=put_reg(R, Aft0#sr.reg)}, 2006 Target = fetch_reg(R, Aft#sr.reg), 2007 2008 {Is,St1} = put_cg_map(Line, Op, SrcReg, Target, Live, List, St0), 2009 {Sis++Is,Aft,St1}; 2010 2011%% Everything else. 2012put_cg([#k_var{name=R}], Con, Le, Vdb, Bef, St) -> 2013 %% Find a place for the return register first. 2014 Int = Bef#sr{reg=put_reg(R, Bef#sr.reg)}, 2015 Ret = fetch_reg(R, Int#sr.reg), 2016 Ais = case Con of 2017 #k_tuple{es=Es} -> 2018 [{put_tuple,length(Es),Ret}] ++ cg_build_args(Es, Bef); 2019 Other -> 2020 [{move,cg_reg_arg(Other, Int),Ret}] 2021 end, 2022 {Ais,clear_dead(Int, Le#l.i, Vdb),St}. 2023 2024 2025put_cg_map(Line, Op0, SrcReg, Target, Live, List, St0) -> 2026 Bfail = St0#cg.bfail, 2027 Fail = {f,St0#cg.bfail}, 2028 Op = case Op0 of 2029 assoc -> put_map_assoc; 2030 exact -> put_map_exact 2031 end, 2032 {OkLbl,St1} = new_label(St0), 2033 {BadLbl,St2} = new_label(St1), 2034 Is = if 2035 Bfail =:= 0 orelse Op =:= put_map_assoc -> 2036 [Line,{Op,{f,0},SrcReg,Target,Live,{list,List}}]; 2037 true -> 2038 %% Ensure that Target is always set, even if 2039 %% the map update operation fails. That is necessary 2040 %% because Target may be included in a test_heap 2041 %% instruction. 2042 [Line, 2043 {Op,{f,BadLbl},SrcReg,Target,Live,{list,List}}, 2044 {jump,{f,OkLbl}}, 2045 {label,BadLbl}, 2046 {move,{atom,ok},Target}, 2047 {jump,Fail}, 2048 {label,OkLbl}] 2049 end, 2050 {Is,St2}. 2051 2052%%% 2053%%% Code generation for constructing binaries. 2054%%% 2055 2056cg_binary([{bs_put_binary,Fail,{atom,all},U,_Flags,Src}|PutCode], 2057 Target, Temp, Fail, MaxRegs, Anno) -> 2058 Line = line(Anno), 2059 Live = cg_live(Target, MaxRegs), 2060 SzCode = cg_bitstr_size(PutCode, Target, Temp, Fail, Live), 2061 BinFlags = {field_flags,[]}, 2062 Code = [Line|SzCode] ++ 2063 [case member(single_use, Anno) of 2064 true -> 2065 {bs_private_append,Fail,Target,U,Src,BinFlags,Target}; 2066 false -> 2067 {bs_append,Fail,Target,0,MaxRegs,U,Src,BinFlags,Target} 2068 end] ++ PutCode, 2069 cg_bin_opt(Code); 2070cg_binary(PutCode, Target, Temp, Fail, MaxRegs, Anno) -> 2071 Line = line(Anno), 2072 Live = cg_live(Target, MaxRegs), 2073 {InitOp,SzCode} = cg_binary_size(PutCode, Target, Temp, Fail, Live), 2074 2075 Code = [Line|SzCode] ++ [{InitOp,Fail,Target,0,MaxRegs, 2076 {field_flags,[]},Target}|PutCode], 2077 cg_bin_opt(Code). 2078 2079cg_live({x,X}, MaxRegs) when X =:= MaxRegs -> MaxRegs+1; 2080cg_live({x,X}, MaxRegs) when X < MaxRegs -> MaxRegs. 2081 2082%% Generate code that calculate the size of the bitstr to be 2083%% built in BITS. 2084 2085cg_bitstr_size(PutCode, Target, Temp, Fail, Live) -> 2086 {Bits,Es} = cg_bitstr_size_1(PutCode, 0, []), 2087 reverse(cg_gen_binsize(Es, Target, Temp, Fail, Live, 2088 [{move,{integer,Bits},Target}])). 2089 2090cg_bitstr_size_1([{bs_put_utf8,_,_,Src}|Next], Bits, Acc) -> 2091 cg_bitstr_size_1(Next, Bits, [{'*',{bs_utf8_size,Src},8}|Acc]); 2092cg_bitstr_size_1([{bs_put_utf16,_,_,Src}|Next], Bits, Acc) -> 2093 cg_bitstr_size_1(Next, Bits, [{'*',{bs_utf16_size,Src},8}|Acc]); 2094cg_bitstr_size_1([{bs_put_utf32,_,_,_}|Next], Bits, Acc) -> 2095 cg_bitstr_size_1(Next, Bits+32, Acc); 2096cg_bitstr_size_1([{_,_,S,U,_,Src}|Next], Bits, Acc) -> 2097 case S of 2098 {integer,N} -> cg_bitstr_size_1(Next, Bits+N*U, Acc); 2099 {atom,all} -> cg_bitstr_size_1(Next, Bits, [{bit_size,Src}|Acc]); 2100 _ when U =:= 1 -> cg_bitstr_size_1(Next, Bits, [S|Acc]); 2101 _ -> cg_bitstr_size_1(Next, Bits, [{'*',S,U}|Acc]) 2102 end; 2103cg_bitstr_size_1([], Bits, Acc) -> {Bits,Acc}. 2104 2105%% Generate code that calculate the size of the bitstr to be 2106%% built in BYTES or BITS (depending on what is easiest). 2107 2108cg_binary_size(PutCode, Target, Temp, Fail, Live) -> 2109 {InitInstruction,Szs} = cg_binary_size_1(PutCode, 0, []), 2110 SizeExpr = reverse(cg_gen_binsize(Szs, Target, Temp, Fail, Live, [{move,{integer,0},Target}])), 2111 {InitInstruction,SizeExpr}. 2112 2113cg_binary_size_1([{bs_put_utf8,_Fail,_Flags,Src}|T], Bits, Acc) -> 2114 cg_binary_size_1(T, Bits, [{8,{bs_utf8_size,Src}}|Acc]); 2115cg_binary_size_1([{bs_put_utf16,_Fail,_Flags,Src}|T], Bits, Acc) -> 2116 cg_binary_size_1(T, Bits, [{8,{bs_utf16_size,Src}}|Acc]); 2117cg_binary_size_1([{bs_put_utf32,_Fail,_Flags,_Src}|T], Bits, Acc) -> 2118 cg_binary_size_1(T, Bits+32, Acc); 2119cg_binary_size_1([{_Put,_Fail,S,U,_Flags,Src}|T], Bits, Acc) -> 2120 cg_binary_size_2(S, U, Src, T, Bits, Acc); 2121cg_binary_size_1([], Bits, Acc) -> 2122 Bytes = Bits div 8, 2123 RemBits = Bits rem 8, 2124 Sizes0 = sort([{1,{integer,RemBits}},{8,{integer,Bytes}}|Acc]), 2125 Sizes = filter(fun({_,{integer,0}}) -> false; 2126 (_) -> true end, Sizes0), 2127 case Sizes of 2128 [{1,_}|_] -> 2129 {bs_init_bits,cg_binary_bytes_to_bits(Sizes, [])}; 2130 [{8,_}|_] -> 2131 {bs_init2,[E || {8,E} <- Sizes]}; 2132 [] -> 2133 {bs_init_bits,[]} 2134 end. 2135 2136cg_binary_size_2({integer,N}, U, _, Next, Bits, Acc) -> 2137 cg_binary_size_1(Next, Bits+N*U, Acc); 2138cg_binary_size_2({atom,all}, U, E, Next, Bits, Acc) -> 2139 if 2140 U rem 8 =:= 0 -> 2141 cg_binary_size_1(Next, Bits, [{8,{byte_size,E}}|Acc]); 2142 true -> 2143 cg_binary_size_1(Next, Bits, [{1,{bit_size,E}}|Acc]) 2144 end; 2145cg_binary_size_2(Reg, 1, _, Next, Bits, Acc) -> 2146 cg_binary_size_1(Next, Bits, [{1,Reg}|Acc]); 2147cg_binary_size_2(Reg, 8, _, Next, Bits, Acc) -> 2148 cg_binary_size_1(Next, Bits, [{8,Reg}|Acc]); 2149cg_binary_size_2(Reg, U, _, Next, Bits, Acc) -> 2150 cg_binary_size_1(Next, Bits, [{1,{'*',Reg,U}}|Acc]). 2151 2152cg_binary_bytes_to_bits([{8,{integer,N}}|T], Acc) -> 2153 cg_binary_bytes_to_bits(T, [{integer,8*N}|Acc]); 2154cg_binary_bytes_to_bits([{8,{byte_size,Reg}}|T], Acc) -> 2155 cg_binary_bytes_to_bits(T, [{bit_size,Reg}|Acc]); 2156cg_binary_bytes_to_bits([{8,Reg}|T], Acc) -> 2157 cg_binary_bytes_to_bits(T, [{'*',Reg,8}|Acc]); 2158cg_binary_bytes_to_bits([{1,Sz}|T], Acc) -> 2159 cg_binary_bytes_to_bits(T, [Sz|Acc]); 2160cg_binary_bytes_to_bits([], Acc) -> 2161 cg_binary_bytes_to_bits_1(sort(Acc)). 2162 2163cg_binary_bytes_to_bits_1([{integer,I},{integer,J}|T]) -> 2164 cg_binary_bytes_to_bits_1([{integer,I+J}|T]); 2165cg_binary_bytes_to_bits_1([H|T]) -> 2166 [H|cg_binary_bytes_to_bits_1(T)]; 2167cg_binary_bytes_to_bits_1([]) -> []. 2168 2169cg_gen_binsize([{'*',{bs_utf8_size,Src},B}|T], Target, Temp, Fail, Live, Acc) -> 2170 Size = {bs_utf8_size,Fail,Src,Temp}, 2171 Add = {bs_add,Fail,[Target,Temp,B],Target}, 2172 cg_gen_binsize(T, Target, Temp, Fail, Live, 2173 [Add,Size|Acc]); 2174cg_gen_binsize([{'*',{bs_utf16_size,Src},B}|T], Target, Temp, Fail, Live, Acc) -> 2175 Size = {bs_utf16_size,Fail,Src,Temp}, 2176 Add = {bs_add,Fail,[Target,Temp,B],Target}, 2177 cg_gen_binsize(T, Target, Temp, Fail, Live, 2178 [Add,Size|Acc]); 2179cg_gen_binsize([{'*',A,B}|T], Target, Temp, Fail, Live, Acc) -> 2180 cg_gen_binsize(T, Target, Temp, Fail, Live, 2181 [{bs_add,Fail,[Target,A,B],Target}|Acc]); 2182cg_gen_binsize([{bit_size,B}|T], Target, Temp, Fail, Live, Acc) -> 2183 cg_gen_binsize([Temp|T], Target, Temp, Fail, Live, 2184 [{gc_bif,bit_size,Fail,Live,[B],Temp}|Acc]); 2185cg_gen_binsize([{byte_size,B}|T], Target, Temp, Fail, Live, Acc) -> 2186 cg_gen_binsize([Temp|T], Target, Temp, Fail, Live, 2187 [{gc_bif,byte_size,Fail,Live,[B],Temp}|Acc]); 2188cg_gen_binsize([{bs_utf8_size,B}|T], Target, Temp, Fail, Live, Acc) -> 2189 cg_gen_binsize([Temp|T], Target, Temp, Fail, Live, 2190 [{bs_utf8_size,Fail,B,Temp}|Acc]); 2191cg_gen_binsize([{bs_utf16_size,B}|T], Target, Temp, Fail, Live, Acc) -> 2192 cg_gen_binsize([Temp|T], Target, Temp, Fail, Live, 2193 [{bs_utf16_size,Fail,B,Temp}|Acc]); 2194cg_gen_binsize([E0|T], Target, Temp, Fail, Live, Acc) -> 2195 cg_gen_binsize(T, Target, Temp, Fail, Live, 2196 [{bs_add,Fail,[Target,E0,1],Target}|Acc]); 2197cg_gen_binsize([], _, _, _, _, Acc) -> Acc. 2198 2199 2200%% cg_bin_opt(Code0) -> Code 2201%% Optimize the size calculations for binary construction. 2202 2203cg_bin_opt([{move,S1,{x,X}=D},{gc_bif,Op,Fail,Live0,As,Dst}|Is]) -> 2204 Live = if 2205 X + 1 =:= Live0 -> X; 2206 true -> Live0 2207 end, 2208 [{gc_bif,Op,Fail,Live,As,D}|cg_bin_opt([{move,S1,Dst}|Is])]; 2209cg_bin_opt([{move,_,_}=I1,{Op,_,_,_}=I2|Is]) 2210 when Op =:= bs_utf8_size orelse Op =:= bs_utf16_size -> 2211 [I2|cg_bin_opt([I1|Is])]; 2212cg_bin_opt([{bs_add,_,[{integer,0},Src,1],Dst}|Is]) -> 2213 cg_bin_opt_1([{move,Src,Dst}|Is]); 2214cg_bin_opt([{bs_add,_,[Src,{integer,0},_],Dst}|Is]) -> 2215 cg_bin_opt_1([{move,Src,Dst}|Is]); 2216cg_bin_opt(Is) -> 2217 cg_bin_opt_1(Is). 2218 2219cg_bin_opt_1([{move,Size,D},{bs_append,Fail,D,Extra,Regs,U,Bin,Flags,D}|Is]) -> 2220 [{bs_append,Fail,Size,Extra,Regs,U,Bin,Flags,D}|cg_bin_opt(Is)]; 2221cg_bin_opt_1([{move,Size,D},{bs_private_append,Fail,D,U,Bin,Flags,D}|Is]) -> 2222 [{bs_private_append,Fail,Size,U,Bin,Flags,D}|cg_bin_opt(Is)]; 2223cg_bin_opt_1([{move,Size,D},{Op,Fail,D,Extra,Regs,Flags,D}|Is]) 2224 when Op =:= bs_init2; Op =:= bs_init_bits -> 2225 Bytes = case Size of 2226 {integer,Int} -> Int; 2227 _ -> Size 2228 end, 2229 [{Op,Fail,Bytes,Extra,Regs,Flags,D}|cg_bin_opt(Is)]; 2230cg_bin_opt_1([{move,S1,D},{bs_add,Fail,[D,S2,U],Dst}|Is]) -> 2231 cg_bin_opt([{bs_add,Fail,[S1,S2,U],Dst}|Is]); 2232cg_bin_opt_1([{move,S1,D},{bs_add,Fail,[S2,D,U],Dst}|Is]) -> 2233 cg_bin_opt([{bs_add,Fail,[S2,S1,U],Dst}|Is]); 2234cg_bin_opt_1([I|Is]) -> 2235 [I|cg_bin_opt(Is)]; 2236cg_bin_opt_1([]) -> 2237 []. 2238 2239cg_bin_put(#k_bin_seg{size=S0,unit=U,type=T,flags=Fs,seg=E0,next=Next}, 2240 Fail, Bef) -> 2241 S1 = cg_reg_arg(S0, Bef), 2242 E1 = cg_reg_arg(E0, Bef), 2243 {Format,Op} = case T of 2244 integer -> {plain,bs_put_integer}; 2245 utf8 -> {utf,bs_put_utf8}; 2246 utf16 -> {utf,bs_put_utf16}; 2247 utf32 -> {utf,bs_put_utf32}; 2248 binary -> {plain,bs_put_binary}; 2249 float -> {plain,bs_put_float} 2250 end, 2251 case Format of 2252 plain -> 2253 [{Op,Fail,S1,U,{field_flags,Fs},E1}|cg_bin_put(Next, Fail, Bef)]; 2254 utf -> 2255 [{Op,Fail,{field_flags,Fs},E1}|cg_bin_put(Next, Fail, Bef)] 2256 end; 2257cg_bin_put(#k_bin_end{}, _, _) -> []. 2258 2259cg_build_args(As, Bef) -> 2260 [{put,cg_reg_arg(A, Bef)} || A <- As]. 2261 2262%% return_cg([Val], Le, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 2263%% break_cg([Val], Le, Vdb, Bef, St) -> {[Ainstr],Aft,St}. 2264%% These are very simple, just put return/break values in registers 2265%% from 0, then return/break. Use the call setup to clean up stack, 2266%% but must clear registers to ensure sr_merge works correctly. 2267 2268return_cg(Rs, Le, Vdb, Bef, St) -> 2269 {Ms,Int} = cg_setup_call(Rs, Bef, Le#l.i, Vdb), 2270 {Ms ++ [return],Int#sr{reg=clear_regs(Int#sr.reg)},St}. 2271 2272break_cg(Bs, Le, Vdb, Bef, St) -> 2273 {Ms,Int} = cg_setup_call(Bs, Bef, Le#l.i, Vdb), 2274 {Ms ++ [{jump,{f,St#cg.break}}], 2275 Int#sr{reg=clear_regs(Int#sr.reg)},St}. 2276 2277guard_break_cg(Bs, #l{i=I}, Vdb, #sr{reg=Reg0}=Bef, St) -> 2278 #sr{reg=Reg1} = Int = clear_dead(Bef, I, Vdb), 2279 Reg2 = trim_free(Reg1), 2280 NumLocked = length(Reg2), 2281 Moves0 = gen_moves(Bs, Bef, NumLocked, []), 2282 Moves = order_moves(Moves0, find_scratch_reg(Reg0)), 2283 {BreakVars,_} = mapfoldl(fun(_, RegNum) -> 2284 {{RegNum,gbreakvar},RegNum+1} 2285 end, length(Reg2), Bs), 2286 Reg = Reg2 ++ BreakVars, 2287 Aft = Int#sr{reg=Reg}, 2288 {Moves ++ [{jump,{f,St#cg.break}}],Aft,St}. 2289 2290%% cg_reg_arg(Arg0, Info) -> Arg 2291%% cg_reg_args([Arg0], Info) -> [Arg] 2292%% Convert argument[s] into registers. Literal values are returned unchanged. 2293 2294cg_reg_args(As, Bef) -> [cg_reg_arg(A, Bef) || A <- As]. 2295 2296cg_reg_arg(#k_var{name=V}, Bef) -> fetch_var(V, Bef); 2297cg_reg_arg(Literal, _) -> atomic(Literal). 2298 2299cg_reg_arg_prefer_y(#k_var{name=V}, Bef) -> fetch_var_prefer_y(V, Bef); 2300cg_reg_arg_prefer_y(Literal, _) -> atomic(Literal). 2301 2302%% cg_setup_call([Arg], Bef, Cur, Vdb) -> {[Instr],Aft}. 2303%% Do the complete setup for a call/enter. 2304 2305cg_setup_call(As, Bef, I, Vdb) -> 2306 {Ms,Int0} = cg_call_args(As, Bef, I, Vdb), 2307 %% Have set up arguments, can now clean up, compress and save to stack. 2308 Int1 = Int0#sr{stk=clear_dead_stk(Int0#sr.stk, I, Vdb),res=[]}, 2309 {Sis,Int2} = adjust_stack(Int1, I, I+1, Vdb), 2310 {Ms ++ Sis,Int2}. 2311 2312%% cg_call_args([Arg], SrState) -> {[Instr],SrState}. 2313%% Setup the arguments to a call/enter/bif. Put the arguments into 2314%% consecutive registers starting at {x,0} moving any data which 2315%% needs to be saved. Return a modified SrState structure with the 2316%% new register contents. N.B. the resultant register info will 2317%% contain non-variable values when there are non-variable values. 2318%% 2319%% This routine is complicated by unsaved values in x registers. 2320%% We'll move away any unsaved values that are in the registers 2321%% to be overwritten by the arguments. 2322 2323cg_call_args(As, Bef, I, Vdb) -> 2324 Regs0 = load_arg_regs(Bef#sr.reg, As), 2325 Unsaved = unsaved_registers(Regs0, Bef#sr.stk, I, I+1, Vdb), 2326 {UnsavedMoves,Regs} = move_unsaved(Unsaved, Bef#sr.reg, Regs0), 2327 Moves0 = gen_moves(As, Bef), 2328 Moves = order_moves(Moves0, find_scratch_reg(Regs)), 2329 {UnsavedMoves ++ Moves,Bef#sr{reg=Regs}}. 2330 2331%% load_arg_regs([Reg], Arguments) -> [Reg] 2332%% Update the register descriptor to include the arguments (from {x,0} 2333%% and upwards). Values in argument register are overwritten. 2334%% Values in x registers above the arguments are preserved. 2335 2336load_arg_regs(Regs, As) -> load_arg_regs(Regs, As, 0). 2337 2338load_arg_regs([_|Rs], [#k_var{name=V}|As], I) -> [{I,V}|load_arg_regs(Rs, As, I+1)]; 2339load_arg_regs([_|Rs], [A|As], I) -> [{I,A}|load_arg_regs(Rs, As, I+1)]; 2340load_arg_regs([], [#k_var{name=V}|As], I) -> [{I,V}|load_arg_regs([], As, I+1)]; 2341load_arg_regs([], [A|As], I) -> [{I,A}|load_arg_regs([], As, I+1)]; 2342load_arg_regs(Rs, [], _) -> Rs. 2343 2344%% Returns the variables must be saved and are currently in the 2345%% x registers that are about to be overwritten by the arguments. 2346 2347unsaved_registers(Regs, Stk, Fb, Lf, Vdb) -> 2348 [V || {V,F,L} <- Vdb, 2349 F < Fb, 2350 L >= Lf, 2351 not on_stack(V, Stk), 2352 not in_reg(V, Regs)]. 2353 2354in_reg(V, Regs) -> keymember(V, 2, Regs). 2355 2356%% Move away unsaved variables from the registers that are to be 2357%% overwritten by the arguments. 2358move_unsaved(Vs, OrigRegs, NewRegs) -> 2359 move_unsaved(Vs, OrigRegs, NewRegs, []). 2360 2361move_unsaved([V|Vs], OrigRegs, NewRegs0, Acc) -> 2362 NewRegs = put_reg(V, NewRegs0), 2363 Src = fetch_reg(V, OrigRegs), 2364 Dst = fetch_reg(V, NewRegs), 2365 move_unsaved(Vs, OrigRegs, NewRegs, [{move,Src,Dst}|Acc]); 2366move_unsaved([], _, Regs, Acc) -> {Acc,Regs}. 2367 2368%% gen_moves(As, Sr) 2369%% Generate the basic move instruction to move the arguments 2370%% to their proper registers. The list will be sorted on 2371%% destinations. (I.e. the move to {x,0} will be first -- 2372%% see the comment to order_moves/2.) 2373 2374gen_moves(As, Sr) -> gen_moves(As, Sr, 0, []). 2375 2376gen_moves([#k_var{name=V}|As], Sr, I, Acc) -> 2377 case fetch_var(V, Sr) of 2378 {x,I} -> gen_moves(As, Sr, I+1, Acc); 2379 Reg -> gen_moves(As, Sr, I+1, [{move,Reg,{x,I}}|Acc]) 2380 end; 2381gen_moves([A0|As], Sr, I, Acc) -> 2382 A = atomic(A0), 2383 gen_moves(As, Sr, I+1, [{move,A,{x,I}}|Acc]); 2384gen_moves([], _, _, Acc) -> lists:keysort(3, Acc). 2385 2386%% order_moves([Move], ScratchReg) -> [Move] 2387%% Orders move instruction so that source registers are not 2388%% destroyed before they are used. If there are cycles 2389%% (such as {move,{x,0},{x,1}}, {move,{x,1},{x,1}}), 2390%% the scratch register is used to break up the cycle. 2391%% If possible, the first move of the input list is placed 2392%% last in the result list (to make the move to {x,0} occur 2393%% just before the call to allow the Beam loader to coalesce 2394%% the instructions). 2395 2396order_moves(Ms, Scr) -> order_moves(Ms, Scr, []). 2397 2398order_moves([{move,_,_}=M|Ms0], ScrReg, Acc0) -> 2399 {Chain,Ms} = collect_chain(Ms0, [M], ScrReg), 2400 Acc = reverse(Chain, Acc0), 2401 order_moves(Ms, ScrReg, Acc); 2402order_moves([], _, Acc) -> Acc. 2403 2404collect_chain(Ms, Path, ScrReg) -> 2405 collect_chain(Ms, Path, [], ScrReg). 2406 2407collect_chain([{move,Src,Same}=M|Ms0], [{move,Same,_}|_]=Path, Others, ScrReg) -> 2408 case lists:keyfind(Src, 3, Path) of 2409 false -> 2410 collect_chain(reverse(Others, Ms0), [M|Path], [], ScrReg); 2411 _ -> % We have a cycle. 2412 {break_up_cycle(M, Path, ScrReg),reverse(Others, Ms0)} 2413 end; 2414collect_chain([M|Ms], Path, Others, ScrReg) -> 2415 collect_chain(Ms, Path, [M|Others], ScrReg); 2416collect_chain([], Path, Others, _) -> 2417 {Path,Others}. 2418 2419break_up_cycle({move,Src,_}=M, Path, ScrReg) -> 2420 [{move,ScrReg,Src},M|break_up_cycle1(Src, Path, ScrReg)]. 2421 2422break_up_cycle1(Dst, [{move,Src,Dst}|Path], ScrReg) -> 2423 [{move,Src,ScrReg}|Path]; 2424break_up_cycle1(Dst, [M|Path], LastMove) -> 2425 [M|break_up_cycle1(Dst, Path, LastMove)]. 2426 2427%% clear_dead(Sr, Until, Vdb) -> Aft. 2428%% Remove all variables in Sr which have died AT ALL so far. 2429 2430clear_dead(#sr{stk=Stk}=Sr0, Until, Vdb) -> 2431 Sr = Sr0#sr{reg=clear_dead_reg(Sr0, Until, Vdb), 2432 stk=clear_dead_stk(Stk, Until, Vdb)}, 2433 reserve(Sr). 2434 2435clear_dead_reg(Sr, Until, Vdb) -> 2436 [case R of 2437 {_I,V} = IV -> 2438 case vdb_find(V, Vdb) of 2439 {V,_,L} when L > Until -> IV; 2440 _ -> free %Remove anything else 2441 end; 2442 {reserved,_I,_V}=Reserved -> Reserved; 2443 free -> free 2444 end || R <- Sr#sr.reg]. 2445 2446clear_dead_stk(Stk, Until, Vdb) -> 2447 [case S of 2448 {V} = T -> 2449 case vdb_find(V, Vdb) of 2450 {V,_,L} when L > Until -> T; 2451 _ -> dead %Remove anything else 2452 end; 2453 free -> free; 2454 dead -> dead 2455 end || S <- Stk]. 2456 2457 2458%% sr_merge(Sr1, Sr2) -> Sr. 2459%% Merge two stack/register states keeping the longest of both stack 2460%% and register. Perform consistency check on both, elements must be 2461%% the same. Allow frame size 'void' to make easy creation of 2462%% "empty" frame. 2463 2464sr_merge(#sr{reg=R1,stk=S1,res=[]}, #sr{reg=R2,stk=S2,res=[]}) -> 2465 #sr{reg=longest(R1, R2),stk=longest(S1, S2),res=[]}; 2466sr_merge(void, S2) -> S2#sr{res=[]}. 2467 2468longest([H|T1], [H|T2]) -> [H|longest(T1, T2)]; 2469longest([dead|T1], [free|T2]) -> [dead|longest(T1, T2)]; 2470longest([free|T1], [dead|T2]) -> [dead|longest(T1, T2)]; 2471longest([dead|_] = L, []) -> L; 2472longest([], [dead|_] = L) -> L; 2473longest([free|_] = L, []) -> L; 2474longest([], [free|_] = L) -> L; 2475longest([], []) -> []. 2476 2477trim_free([R|Rs0]) -> 2478 case {trim_free(Rs0),R} of 2479 {[],free} -> []; 2480 {Rs,R} -> [R|Rs] 2481 end; 2482trim_free([]) -> []. 2483 2484%% maybe_adjust_stack(Bef, FirstBefore, LastFrom, Vdb, St) -> {[Ainstr],Aft}. 2485%% Adjust the stack, but only if the code is inside a catch and not 2486%% inside a guard. Use this funtion before instructions that may 2487%% cause an exception. 2488 2489maybe_adjust_stack(Bef, Fb, Lf, Vdb, St) -> 2490 case St of 2491 #cg{in_catch=true,bfail=0} -> 2492 adjust_stack(Bef, Fb, Lf, Vdb); 2493 #cg{} -> 2494 {[],Bef} 2495 end. 2496 2497%% adjust_stack(Bef, FirstBefore, LastFrom, Vdb) -> {[Ainstr],Aft}. 2498%% Do complete stack adjustment by compressing stack and adding 2499%% variables to be saved. Try to optimise ordering on stack by 2500%% having reverse order to their lifetimes. 2501%% 2502%% In Beam, there is a fixed stack frame and no need to do stack compression. 2503 2504adjust_stack(Bef, Fb, Lf, Vdb) -> 2505 Stk0 = Bef#sr.stk, 2506 {Stk1,Saves} = save_stack(Stk0, Fb, Lf, Vdb), 2507 {saves(Saves, Bef#sr.reg, Stk1), 2508 Bef#sr{stk=Stk1}}. 2509 2510%% save_stack(Stack, FirstBefore, LastFrom, Vdb) -> {[SaveVar],NewStack}. 2511%% Save variables which are used past current point and which are not 2512%% already on the stack. 2513 2514save_stack(Stk0, Fb, Lf, Vdb) -> 2515 %% New variables that are in use but not on stack. 2516 New = new_not_on_stack(Stk0, Fb, Lf, Vdb), 2517 2518 %% Add new variables that are not just dropped immediately. 2519 %% N.B. foldr works backwards from the end!! 2520 Saves = [V || {V,_,_} <- keysort(3, New)], 2521 Stk1 = foldr(fun (V, Stk) -> put_stack(V, Stk) end, Stk0, Saves), 2522 {Stk1,Saves}. 2523 2524%% new_not_on_stack(Stack, FirstBefore, LastFrom, Vdb) -> 2525%% [{Variable,First,Last}] 2526%% Return information about all variables that are used past current 2527%% point and that are not already on the stack. 2528 2529new_not_on_stack(Stk, Fb, Lf, Vdb) -> 2530 [VFL || {V,F,L} = VFL <- Vdb, 2531 F < Fb, 2532 L >= Lf, 2533 not on_stack(V, Stk)]. 2534 2535%% saves([SaveVar], Reg, Stk) -> [{move,Reg,Stk}]. 2536%% Generate move instructions to save variables onto stack. The 2537%% stack/reg info used is that after the new stack has been made. 2538 2539saves(Ss, Reg, Stk) -> 2540 [{move,fetch_reg(V, Reg),fetch_stack(V, Stk)} || V <- Ss]. 2541 2542%% fetch_var(VarName, StkReg) -> r{R} | sp{Sp}. 2543%% find_var(VarName, StkReg) -> ok{r{R} | sp{Sp}} | error. 2544%% Fetch/find a variable in either the registers or on the 2545%% stack. Fetch KNOWS it's there. 2546 2547fetch_var(V, Sr) -> 2548 case find_reg(V, Sr#sr.reg) of 2549 {ok,R} -> R; 2550 error -> fetch_stack(V, Sr#sr.stk) 2551 end. 2552 2553fetch_var_prefer_y(V, #sr{reg=Reg,stk=Stk}) -> 2554 case find_stack(V, Stk) of 2555 {ok,R} -> R; 2556 error -> fetch_reg(V, Reg) 2557 end. 2558 2559load_vars(Vs, Regs) -> 2560 foldl(fun (#k_var{name=V}, Rs) -> put_reg(V, Rs) end, Regs, Vs). 2561 2562%% put_reg(Val, Regs) -> Regs. 2563%% find_reg(Val, Regs) -> {ok,r{R}} | error. 2564%% fetch_reg(Val, Regs) -> r{R}. 2565%% Functions to interface the registers. 2566 2567% put_regs(Vs, Rs) -> foldl(fun put_reg/2, Rs, Vs). 2568 2569put_reg(V, Rs) -> put_reg_1(V, Rs, 0). 2570 2571put_reg_1(V, [free|Rs], I) -> [{I,V}|Rs]; 2572put_reg_1(V, [{reserved,I,V}|Rs], I) -> [{I,V}|Rs]; 2573put_reg_1(V, [R|Rs], I) -> [R|put_reg_1(V, Rs, I+1)]; 2574put_reg_1(V, [], I) -> [{I,V}]. 2575 2576fetch_reg(V, [{I,V}|_]) -> {x,I}; 2577fetch_reg(V, [_|SRs]) -> fetch_reg(V, SRs). 2578 2579find_reg(V, [{I,V}|_]) -> {ok,{x,I}}; 2580find_reg(V, [_|SRs]) -> find_reg(V, SRs); 2581find_reg(_, []) -> error. 2582 2583%% For the bit syntax, we need a scratch register if we are constructing 2584%% a binary that will not be used. 2585 2586find_scratch_reg(Rs) -> find_scratch_reg(Rs, 0). 2587 2588find_scratch_reg([free|_], I) -> {x,I}; 2589find_scratch_reg([_|Rs], I) -> find_scratch_reg(Rs, I+1); 2590find_scratch_reg([], I) -> {x,I}. 2591 2592replace_reg_contents(Old, New, [{I,Old}|Rs]) -> [{I,New}|Rs]; 2593replace_reg_contents(Old, New, [R|Rs]) -> [R|replace_reg_contents(Old, New, Rs)]. 2594 2595%%clear_regs(Regs) -> map(fun (R) -> free end, Regs). 2596clear_regs(_) -> []. 2597 2598max_reg(Regs) -> 2599 foldl(fun ({I,_}, _) -> I; 2600 (_, Max) -> Max end, 2601 -1, Regs) + 1. 2602 2603%% put_stack(Val, [{Val}]) -> [{Val}]. 2604%% fetch_stack(Var, Stk) -> sp{S}. 2605%% find_stack(Var, Stk) -> ok{sp{S}} | error. 2606%% Functions to interface the stack. 2607 2608put_stack(Val, []) -> [{Val}]; 2609put_stack(Val, [dead|Stk]) -> [{Val}|Stk]; 2610put_stack(Val, [free|Stk]) -> [{Val}|Stk]; 2611put_stack(Val, [NotFree|Stk]) -> [NotFree|put_stack(Val, Stk)]. 2612 2613put_stack_carefully(Val, Stk0) -> 2614 try 2615 put_stack_carefully1(Val, Stk0) 2616 catch 2617 throw:error -> 2618 error 2619 end. 2620 2621put_stack_carefully1(_, []) -> throw(error); 2622put_stack_carefully1(Val, [dead|Stk]) -> [{Val}|Stk]; 2623put_stack_carefully1(Val, [free|Stk]) -> [{Val}|Stk]; 2624put_stack_carefully1(Val, [NotFree|Stk]) -> 2625 [NotFree|put_stack_carefully1(Val, Stk)]. 2626 2627fetch_stack(Var, Stk) -> fetch_stack(Var, Stk, 0). 2628 2629fetch_stack(V, [{V}|_], I) -> {yy,I}; 2630fetch_stack(V, [_|Stk], I) -> fetch_stack(V, Stk, I+1). 2631 2632find_stack(Var, Stk) -> find_stack(Var, Stk, 0). 2633 2634find_stack(V, [{V}|_], I) -> {ok,{yy,I}}; 2635find_stack(V, [_|Stk], I) -> find_stack(V, Stk, I+1); 2636find_stack(_, [], _) -> error. 2637 2638on_stack(V, Stk) -> keymember(V, 1, Stk). 2639 2640%% put_catch(CatchTag, Stack) -> Stack' 2641%% drop_catch(CatchTag, Stack) -> Stack' 2642%% Special interface for putting and removing catch tags, to ensure that 2643%% catches nest properly. Also used for try tags. 2644 2645put_catch(Tag, Stk0) -> put_catch(Tag, reverse(Stk0), []). 2646 2647put_catch(Tag, [], Stk) -> 2648 put_stack({catch_tag,Tag}, Stk); 2649put_catch(Tag, [{{catch_tag,_}}|_]=RevStk, Stk) -> 2650 reverse(RevStk, put_stack({catch_tag,Tag}, Stk)); 2651put_catch(Tag, [Other|Stk], Acc) -> 2652 put_catch(Tag, Stk, [Other|Acc]). 2653 2654drop_catch(Tag, [{{catch_tag,Tag}}|Stk]) -> [free|Stk]; 2655drop_catch(Tag, [Other|Stk]) -> [Other|drop_catch(Tag, Stk)]. 2656 2657%% atomic(Klit) -> Lit. 2658%% atomic_list([Klit]) -> [Lit]. 2659 2660atomic(#k_literal{val=V}) -> {literal,V}; 2661atomic(#k_int{val=I}) -> {integer,I}; 2662atomic(#k_float{val=F}) -> {float,F}; 2663atomic(#k_atom{val=A}) -> {atom,A}; 2664%%atomic(#k_char{val=C}) -> {char,C}; 2665atomic(#k_nil{}) -> nil. 2666 2667%% new_label(St) -> {L,St}. 2668 2669new_label(#cg{lcount=Next}=St) -> 2670 {Next,St#cg{lcount=Next+1}}. 2671 2672%% line(Le) -> {line,[] | {location,File,Line}} 2673%% Create a line instruction, containing information about 2674%% the current filename and line number. A line information 2675%% instruction should be placed before any operation that could 2676%% cause an exception. 2677 2678line(#l{a=Anno}) -> 2679 line(Anno); 2680line([Line,{file,Name}]) when is_integer(Line) -> 2681 line_1(Name, Line); 2682line([_|_]=A) -> 2683 {Name,Line} = find_loc(A, no_file, 0), 2684 line_1(Name, Line); 2685line([]) -> 2686 {line,[]}. 2687 2688line_1(no_file, _) -> 2689 {line,[]}; 2690line_1(_, 0) -> 2691 %% Missing line number or line number 0. 2692 {line,[]}; 2693line_1(Name, Line) -> 2694 {line,[{location,Name,Line}]}. 2695 2696find_loc([Line|T], File, _) when is_integer(Line) -> 2697 find_loc(T, File, Line); 2698find_loc([{file,File}|T], _, Line) -> 2699 find_loc(T, File, Line); 2700find_loc([_|T], File, Line) -> 2701 find_loc(T, File, Line); 2702find_loc([], File, Line) -> {File,Line}. 2703 2704flatmapfoldl(F, Accu0, [Hd|Tail]) -> 2705 {R,Accu1} = F(Hd, Accu0), 2706 {Rs,Accu2} = flatmapfoldl(F, Accu1, Tail), 2707 {R++Rs,Accu2}; 2708flatmapfoldl(_, Accu, []) -> {[],Accu}. 2709 2710%% Keep track of life time for variables. 2711%% 2712%% init_vars([{var,VarName}]) -> Vdb. 2713%% new_vars([VarName], I, Vdb) -> Vdb. 2714%% use_vars([VarName], I, Vdb) -> Vdb. 2715%% add_var(VarName, F, L, Vdb) -> Vdb. 2716%% 2717%% The list of variable names for new_vars/3 and use_vars/3 2718%% must be sorted. 2719 2720init_vars(Vs) -> 2721 vdb_new(Vs). 2722 2723new_vars([], _, Vdb) -> Vdb; 2724new_vars([V], I, Vdb) -> vdb_store_new(V, {V,I,I}, Vdb); 2725new_vars(Vs, I, Vdb) -> vdb_update_vars(Vs, Vdb, I). 2726 2727use_vars([], _, Vdb) -> 2728 Vdb; 2729use_vars([V], I, Vdb) -> 2730 case vdb_find(V, Vdb) of 2731 {V,F,L} when I > L -> vdb_update(V, {V,F,I}, Vdb); 2732 {V,_,_} -> Vdb; 2733 error -> vdb_store_new(V, {V,I,I}, Vdb) 2734 end; 2735use_vars(Vs, I, Vdb) -> vdb_update_vars(Vs, Vdb, I). 2736 2737add_var(V, F, L, Vdb) -> 2738 vdb_store_new(V, {V,F,L}, Vdb). 2739 2740%% vdb 2741 2742vdb_new(Vs) -> 2743 ordsets:from_list([{V,0,0} || #k_var{name=V} <- Vs]). 2744 2745-type var() :: atom(). 2746 2747-spec vdb_find(var(), [vdb_entry()]) -> 'error' | vdb_entry(). 2748 2749vdb_find(V, Vdb) -> 2750 case lists:keyfind(V, 1, Vdb) of 2751 false -> error; 2752 Vd -> Vd 2753 end. 2754 2755vdb_update(V, Update, [{V,_,_}|Vdb]) -> 2756 [Update|Vdb]; 2757vdb_update(V, Update, [Vd|Vdb]) -> 2758 [Vd|vdb_update(V, Update, Vdb)]. 2759 2760vdb_store_new(V, New, [{V1,_,_}=Vd|Vdb]) when V > V1 -> 2761 [Vd|vdb_store_new(V, New, Vdb)]; 2762vdb_store_new(V, New, [{V1,_,_}|_]=Vdb) when V < V1 -> 2763 [New|Vdb]; 2764vdb_store_new(_, New, []) -> [New]. 2765 2766vdb_update_vars([V|_]=Vs, [{V1,_,_}=Vd|Vdb], I) when V > V1 -> 2767 [Vd|vdb_update_vars(Vs, Vdb, I)]; 2768vdb_update_vars([V|Vs], [{V1,_,_}|_]=Vdb, I) when V < V1 -> 2769 %% New variable. 2770 [{V,I,I}|vdb_update_vars(Vs, Vdb, I)]; 2771vdb_update_vars([V|Vs], [{_,F,L}=Vd|Vdb], I) -> 2772 %% Existing variable. 2773 if 2774 I > L -> [{V,F,I}|vdb_update_vars(Vs, Vdb, I)]; 2775 true -> [Vd|vdb_update_vars(Vs, Vdb, I)] 2776 end; 2777vdb_update_vars([V|Vs], [], I) -> 2778 %% New variable. 2779 [{V,I,I}|vdb_update_vars(Vs, [], I)]; 2780vdb_update_vars([], Vdb, _) -> Vdb. 2781 2782%% vdb_sub(Min, Max, Vdb) -> Vdb. 2783%% Extract variables which are used before and after Min. Lock 2784%% variables alive after Max. 2785 2786vdb_sub(Min, Max, Vdb) -> 2787 [ if L >= Max -> {V,F,locked}; 2788 true -> Vd 2789 end || {V,F,L}=Vd <- Vdb, 2790 F < Min, 2791 L >= Min ]. 2792