1-module(hipe_llvm_liveness). 2 3-export([analyze/1]). 4 5%% @doc Find gc roots and explicitly mark when they go out of scope, based 6%% on the liveness analyzis performed by the hipe_rtl_liveness:analyze/1. 7analyze(RtlCfg) -> 8 Liveness = hipe_rtl_liveness:analyze(RtlCfg), 9 Roots = find_roots(RtlCfg, Liveness), 10 %% erlang:display(Roots), 11 NewRtlCfg = mark_dead_roots(RtlCfg, Liveness, Roots), 12 {NewRtlCfg, Roots}. 13 14%% @doc Determine which are the GC Roots.Possible roots are all 15%% RTL variables (rtl_var). However, since safe points are function calls, we 16%% consider as possible GC roots only RTL variables that are live around 17%% function calls. 18find_roots(Cfg, Liveness) -> 19 Labels = hipe_rtl_cfg:postorder(Cfg), 20 Roots = find_roots_bb(Labels, Cfg, Liveness, []), 21 lists:usort(lists:flatten(Roots)). 22 23find_roots_bb([], _Cfg, _Liveness, RootAcc) -> 24 RootAcc; 25find_roots_bb([L|Ls], Cfg, Liveness, RootAcc) -> 26 Block = hipe_rtl_cfg:bb(Cfg, L), 27 BlockCode = hipe_bb:code(Block), 28 LiveIn = ordsets:from_list(strip(hipe_rtl_liveness:livein(Liveness, L))), 29 LiveOut = ordsets:from_list(strip(hipe_rtl_liveness:liveout(Liveness, L))), 30 Roots = do_find_roots_bb(BlockCode, L, LiveOut, LiveIn, []), 31 find_roots_bb(Ls, Cfg, Liveness, Roots++RootAcc). 32 33%% For each call inside a BB the GC roots are those RTL variables that 34%% are live before and after the call. 35%% --> Live Before Call: These are the RTL variables that belong to the 36%% LiveIn list or are initialized inside the BB before the call 37%% --> Live After Call: These are the RTL variables that belong to the 38%% LiveOut list or are used after the call inside the BB (they die 39%% inside the BB and so do not belong to the LiveOut list) 40do_find_roots_bb([], _Label, _LiveOut, _LiveBefore, RootAcc) -> 41 RootAcc; 42do_find_roots_bb([I|Is], L, LiveOut, LiveBefore, RootAcc) -> 43 case hipe_rtl:is_call(I) of 44 true -> 45 %% Used inside the BB after the call 46 UsedAfterCall_ = strip(lists:flatten([hipe_rtl:uses(V) || V <- Is])), 47 UsedAfterCall = ordsets:from_list(UsedAfterCall_), 48 LiveAfter = ordsets:union(UsedAfterCall, LiveOut), 49 %% The Actual Roots 50 Roots = ordsets:intersection(LiveBefore, LiveAfter), 51 %% The result of the instruction 52 Defines = ordsets:from_list(strip(hipe_rtl:defines(I))), 53 LiveBefore1 = ordsets:union(LiveBefore, Defines), 54 do_find_roots_bb(Is, L, LiveOut, LiveBefore1, [Roots|RootAcc]); 55 false -> 56 %% The result of the instruction 57 Defines = ordsets:from_list(strip(hipe_rtl:defines(I))), 58 LiveBefore1 = ordsets:union(LiveBefore, Defines), 59 do_find_roots_bb(Is, L, LiveOut, LiveBefore1, RootAcc) 60 end. 61 62%% @doc This function is responsible for marking when GC Roots, which can be 63%% only RTL variables go out of scope (dead). This pass is needed for the LLVM 64%% back end because the LLVM framework forces us to explicit mark when gc roots 65%% are no longer live. 66mark_dead_roots(CFG, Liveness, Roots) -> 67 Labels = hipe_rtl_cfg:postorder(CFG), 68 mark_dead_bb(Labels, CFG, Liveness, Roots). 69 70mark_dead_bb([], Cfg, _Liveness, _Roots) -> 71 Cfg; 72mark_dead_bb([L|Ls], Cfg, Liveness, Roots) -> 73 Block = hipe_rtl_cfg:bb(Cfg, L), 74 BlockCode = hipe_bb:code(Block), 75 LiveOut = ordsets:from_list(strip(hipe_rtl_liveness:liveout(Liveness, L))), 76 NewBlockCode = do_mark_dead_bb(BlockCode, LiveOut, Roots, []), 77 %% Update the CFG 78 NewBB = hipe_bb:code_update(Block, NewBlockCode), 79 NewCFG = hipe_rtl_cfg:bb_add(Cfg, L, NewBB), 80 mark_dead_bb(Ls, NewCFG, Liveness, Roots). 81 82do_mark_dead_bb([], _LiveOut, _Roots, NewBlockCode) -> 83 lists:reverse(NewBlockCode); 84do_mark_dead_bb([I|Is], LiveOut ,Roots, NewBlockCode) -> 85 Uses = ordsets:from_list(strip(hipe_rtl:uses(I))), 86 %% GC roots that are used in this instruction 87 RootsUsed = ordsets:intersection(Roots, Uses), 88 UsedAfter_ = strip(lists:flatten([hipe_rtl:uses(V) || V <- Is])), 89 UsedAfter = ordsets:from_list(UsedAfter_), 90 %% GC roots that are live after this instruction 91 LiveAfter = ordsets:union(LiveOut, UsedAfter), 92 %% GC roots that their last use is in this instruction 93 DeadRoots = ordsets:subtract(RootsUsed, LiveAfter), 94 %% Recreate the RTL variable from the corresponding Index 95 OldVars = [hipe_rtl:mk_var(V1) || V1 <- DeadRoots], 96 %% Mark the RTL variable as DEAD (last use) 97 NewVars = [kill_var(V2) || V2 <- OldVars], 98 %% Create a list with the substitution of the old vars with the new 99 %% ones which are marked with the dead keyword 100 Subtitution = lists:zip(OldVars, NewVars), 101 NewI = case Subtitution of 102 [] -> I; 103 _ -> hipe_rtl:subst_uses_llvm(Subtitution, I) 104 end, 105 do_mark_dead_bb(Is, LiveOut, Roots, [NewI|NewBlockCode]). 106 107%% Update the liveness of a var,in order to mark that this is the last use. 108kill_var(Var) -> hipe_rtl:var_liveness_update(Var, dead). 109 110%% We are only interested for rtl_vars, since only rtl_vars are possible gc 111%% roots. 112strip(L) -> [Y || {rtl_var, Y, _} <- L]. 113