1%% -*- Erlang -*- 2%% -*- erlang-indent-level: 2 -*- 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 4%% 5%% Licensed under the Apache License, Version 2.0 (the "License"); 6%% you may not use this file except in compliance with the License. 7%% You may obtain a copy of the License at 8%% 9%% http://www.apache.org/licenses/LICENSE-2.0 10%% 11%% Unless required by applicable law or agreed to in writing, software 12%% distributed under the License is distributed on an "AS IS" BASIS, 13%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14%% See the License for the specific language governing permissions and 15%% limitations under the License. 16%% 17%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 18%% 19%% CONTROL FLOW GRAPHS 20%% 21%% Construct and manipulate the control flow graph of a function (program?). 22%% 23%% Exports: 24%% ~~~~~~~~ 25%% init(Code) - makes a CFG out of code. 26%% bb(CFG, Label) - returns the basic block named 'Label' from the CFG. 27%% bb_add(CFG, Label, NewBB) - makes NewBB the basic block associated 28%% with Label. 29%% map_bbs(Fun, CFG) - map over all code without changing control flow. 30%% fold_bbs(Fun, Acc, CFG) - fold over the basic blocks in a CFG. 31%% succ(Map, Label) - returns a list of successors of basic block 'Label'. 32%% pred(Map, Label) - returns the predecessors of basic block 'Label'. 33%% fallthrough(CFG, Label) - returns fall-through successor of basic 34%% block 'Label' (or 'none'). 35%% conditional(CFG, Label) - returns conditional successor (or 'none') 36%% start_label(CFG) - returns the label of the entry basic block. 37%% params(CFG) - returns the list of parameters to the CFG. 38%% labels(CFG) - returns a list of labels of all basic blocks in the CFG. 39%% postorder(CFG) - returns a list of labels in postorder. 40%% reverse_postorder(CFG) - returns a list of labels in reverse postorder. 41%% cfg_to_linear(CFG) - converts CFG to linearized code. 42%% remove_trivial_bbs(CFG) - removes empty BBs or BBs with only a goto. 43%% remove_unreachable_code(CFG) - removes unreachable BBs. 44%% 45%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 46%% 47%% TODO: 48%% 49%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 50 51%%===================================================================== 52%% The following are ugly as hell, but what else can I do??? 53%%===================================================================== 54 55-ifdef(GEN_CFG). 56-define(PRED_NEEDED,true). 57-endif. 58 59-ifdef(ICODE_CFG). 60-define(CLOSURE_ARITY_NEEDED,true). 61-define(INFO_NEEDED,true). 62-define(PARAMS_NEEDED,true). 63-define(PARAMS_UPDATE_NEEDED,true). 64-define(PRED_NEEDED,true). 65-define(REMOVE_TRIVIAL_BBS_NEEDED,true). 66-define(REMOVE_UNREACHABLE_CODE,true). 67-define(START_LABEL_UPDATE_NEEDED,true). 68-define(CFG_CAN_HAVE_PHI_NODES,true). 69-endif. 70 71-ifdef(RTL_CFG). 72-define(PREORDER,true). 73-define(FIND_NEW_LABEL_NEEDED,true). 74-define(INFO_NEEDED,true). 75-define(PARAMS_NEEDED,true). 76-define(PARAMS_UPDATE_NEEDED,true). 77-define(PRED_NEEDED,true). 78-define(REMOVE_TRIVIAL_BBS_NEEDED,true). 79-define(REMOVE_UNREACHABLE_CODE,true). 80-define(START_LABEL_UPDATE_NEEDED,true). 81-define(CFG_CAN_HAVE_PHI_NODES,true). 82-endif. 83 84-ifdef(SPARC_CFG). 85-define(BREADTH_ORDER,true). % for linear scan 86-define(PARAMS_NEEDED,true). 87-define(START_LABEL_UPDATE_NEEDED,true). 88-define(MAP_FOLD_NEEDED,true). 89-endif. 90 91%%===================================================================== 92 93-ifdef(START_LABEL_UPDATE_NEEDED). 94-export([start_label_update/2]). 95-endif. 96 97-ifdef(BREADTH_ORDER). 98-export([breadthorder/1]). 99-endif. 100 101-compile(inline). 102 103%%===================================================================== 104%% 105%% Interface functions that MUST be implemented in the including file: 106%% 107%% linear_to_cfg(LinearCode) -> CFG, constructs the cfg. 108%% is_label(Instr) -> boolean(), true if instruction is a label. 109%% label_name(Instr) -> term(), the name of a label. 110%% branch_successors(Instr) -> [term()], the successors of a branch. 111%% fails_to(Instr) -> [term()], the fail-successors of an instruction. 112%% is_branch(Instr) -> boolean(), true if instruction is a branch. 113%% is_comment(Instr) -> boolean(), 114%% true if instruction is a comment, used by remove dead code. 115%% is_goto(Instr) -> boolean(), 116%% true if instruction is a pure goto, used by remove dead code. 117%% redirect_jmp(Jmp, ToOld, ToNew) -> NewJmp, 118%% redirect_ops(Labels, CFG, Map) -> CFG. 119%% Rewrite instructions with labels in operands to use 120%% the new label as given by map. 121%% Use find_new_label(OldLab,Map) to get the new label. 122%% (See hipe_sparc_cfg for example) 123%% pp(CFG) -> ok, do some nifty output. 124%% cfg_to_linear(CFG) -> LinearCode, linearizes the code of CFG 125%% mk_goto(Label) -> instruction 126%% is_phi(Instr) -> boolean(), true if the instruction is a phi-instruction. 127%% phi_remove_pred(PhiInstr, Pred) -> NewPhi, 128%% Removes the predecessor Pred from the phi instruction. 129%% highest_var(Code) -> term(), 130%% Returns the highest variable used or defined in the code. 131%% 132%%===================================================================== 133 134%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 135%% 136%% Primitives (not all of these are exported) 137%% 138 139-spec start_label(cfg()) -> cfg_lbl(). 140start_label(CFG) -> (CFG#cfg.info)#cfg_info.start_label. 141 142-ifndef(GEN_CFG). 143-spec start_label_update(cfg(), cfg_lbl()) -> cfg(). 144start_label_update(CFG, NewStartLabel) -> 145 Info = CFG#cfg.info, 146 CFG#cfg{info = Info#cfg_info{start_label = NewStartLabel}}. 147 148-spec function(cfg()) -> mfa(). 149function(CFG) -> (CFG#cfg.info)#cfg_info.'fun'. 150 151-spec is_closure(cfg()) -> boolean(). 152is_closure(CFG) -> (CFG#cfg.info)#cfg_info.is_closure. 153 154-spec is_leaf(cfg()) -> boolean(). 155is_leaf(CFG) -> (CFG#cfg.info)#cfg_info.is_leaf. 156 157mk_empty_cfg(Fun, StartLbl, Data, Closure, Leaf, Params) -> 158 Info = #cfg_info{'fun' = Fun, 159 start_label = StartLbl, 160 is_closure = Closure, 161 is_leaf = Leaf, 162 params = Params}, 163 #cfg{table = gb_trees:empty(), data = Data, info = Info}. 164 165data(CFG) -> CFG#cfg.data. 166-endif. % GEN_CFG 167 168-ifdef(REMOVE_TRIVIAL_BBS_NEEDED). 169-spec update_data(cfg(), cfg_data()) -> cfg(). 170update_data(CFG, D) -> 171 CFG#cfg{data = D}. 172-endif. 173 174-ifdef(PARAMS_NEEDED). 175params(CFG) -> (CFG#cfg.info)#cfg_info.params. 176-endif. 177 178-ifdef(PARAMS_UPDATE_NEEDED). 179params_update(CFG, NewParams) -> 180 Info = CFG#cfg.info, 181 CFG#cfg{info = Info#cfg_info{params = NewParams}}. 182-endif. 183 184-ifdef(CLOSURE_ARITY_NEEDED). 185-spec closure_arity(cfg()) -> arity(). 186closure_arity(CFG) -> 187 Info = CFG#cfg.info, 188 Info#cfg_info.closure_arity. 189 190-spec closure_arity_update(cfg(), arity()) -> cfg(). 191closure_arity_update(CFG, Arity) -> 192 Info = CFG#cfg.info, 193 CFG#cfg{info = Info#cfg_info{closure_arity = Arity}}. 194-endif. 195 196%% %% Don't forget to do a start_label_update if necessary. 197%% update_code(CFG, NewCode) -> 198%% take_bbs(NewCode, CFG). 199 200-ifdef(INFO_NEEDED). 201info(CFG) -> (CFG#cfg.info)#cfg_info.info. 202%% info_add(CFG, A) -> 203%% As = info(CFG), 204%% Info = CFG#cfg.info, 205%% CFG#cfg{info = Info#cfg_info{info = [A|As]}}. 206info_update(CFG, I) -> 207 Info = CFG#cfg.info, 208 CFG#cfg{info = Info#cfg_info{info = I}}. 209-endif. 210 211%%===================================================================== 212-ifndef(GEN_CFG). 213 214-spec other_entrypoints(cfg()) -> [cfg_lbl()]. 215%% @doc Returns a list of labels that are referred to from the data section. 216 217other_entrypoints(CFG) -> 218 hipe_consttab:referred_labels(data(CFG)). 219 220%% is_entry(Lbl, CFG) -> 221%% Lbl =:= start_label(CFG) orelse 222%% lists:member(Lbl, other_entrypoints(CFG)). 223 224%% @spec bb(CFG::cfg(), Label::cfg_lbl()) -> basic_block() 225%% @doc Returns the basic block of the CFG which begins at the Label. 226bb(CFG, Label) -> 227 HT = CFG#cfg.table, 228 case gb_trees:lookup(Label, HT) of 229 {value, {Block,_Succ,_Pred}} -> 230 Block; 231 none -> 232 not_found 233 end. 234 235%% Remove duplicates from a list. The first instance (in left-to-right 236%% order) of an element is kept, remaining instances are removed. 237-spec remove_duplicates([cfg_lbl()]) -> [cfg_lbl()]. 238remove_duplicates(List) -> 239 remove_duplicates(List, []). 240 241-spec remove_duplicates([cfg_lbl()], [cfg_lbl()]) -> [cfg_lbl()]. 242remove_duplicates([H|T], Acc) -> 243 NewAcc = 244 case lists:member(H, Acc) of 245 false -> [H|Acc]; 246 true -> Acc 247 end, 248 remove_duplicates(T, NewAcc); 249remove_duplicates([], Acc) -> 250 lists:reverse(Acc). 251 252 253-ifdef(RTL_CFG). %% this could be CFG_CAN_HAVE_PHI_NODES 254 %% if Icode also starts using this function 255 256%% @spec bb_insert_between(CFG::cfg(), 257%% Label::cfg_lbl(), NewBB::basic_block(), 258%% Pred::cfg_lbl(), Succ::cfg_lbl()) -> cfg() 259%% 260%% @doc Insert the new basic block with label Label in the edge from 261%% Pred to Succ 262 263bb_insert_between(CFG, Label, NewBB, Pred, Succ) -> 264 Last = hipe_bb:last(NewBB), 265 %% Asserts that NewBB ends in a label 266 true = is_branch(Last), 267 %% Asserts that the only Successor of NewBB is Succ 268 [Succ] = remove_duplicates(branch_successors(Last)), 269 HT = CFG#cfg.table, 270 %% Asserts that Label does not exist in the CFG 271 none = gb_trees:lookup(Label, HT), 272 %% Updates the predecessor of NewBB 273 {value, {PBB, PSucc, PPred}} = gb_trees:lookup(Pred, HT), 274 NewPSucc = [Label|lists:delete(Succ, PSucc)], 275 PLast = hipe_bb:last(PBB), 276 PButLast = hipe_bb:butlast(PBB), 277 NewPBB = hipe_bb:code_update(PBB, PButLast++[redirect_jmp(PLast, Succ, Label)]), 278 HT1 = gb_trees:update(Pred, {NewPBB,NewPSucc,PPred}, HT), 279 %% Updates the successor of NewBB 280 {value, {SBB, SSucc, SPred}} = gb_trees:lookup(Succ, HT1), 281 NewSPred = [Label|lists:delete(Pred, SPred)], 282 SCode = hipe_bb:code(SBB), 283 NewSCode = redirect_phis(SCode, Pred, Label, []), 284 NewSBB = hipe_bb:code_update(SBB, NewSCode), 285 HT2 = gb_trees:update(Succ, {NewSBB,SSucc,NewSPred}, HT1), 286 %% Enters NewBB into the CFG 287 HT3 = gb_trees:insert(Label, {NewBB,[Succ],[Pred]}, HT2), 288 CFG#cfg{table = HT3}. 289 290redirect_phis([], _OldPred, _NewPred, Acc) -> 291 lists:reverse(Acc); 292redirect_phis([I|Rest], OldPred, NewPred, Acc) -> 293 case is_phi(I) of 294 true -> 295 Phi = phi_redirect_pred(I, OldPred, NewPred), 296 redirect_phis(Rest, OldPred, NewPred, [Phi|Acc]); 297 false -> 298 redirect_phis(Rest, OldPred, NewPred, [I|Acc]) 299 end. 300 301-endif. 302 303%% @spec bb_add(CFG::cfg(), Label::cfg_lbl(), NewBB::basic_block()) -> cfg() 304%% @doc Adds a new basic block to a CFG (or updates an existing block). 305bb_add(CFG, Label, NewBB) -> 306 %% Asserting that the NewBB is a legal basic block 307 Last = assert_bb(NewBB), 308 %% The order of the elements from branch_successors/1 is 309 %% significant. It determines the basic block order when the CFG is 310 %% converted to linear form. That order may have been tuned for 311 %% branch prediction purposes. 312 Succ = remove_duplicates(branch_successors(Last)), 313 HT = CFG#cfg.table, 314 {OldSucc, OldPred} = case gb_trees:lookup(Label, HT) of 315 {value, {_Block, OSucc, OPred}} -> 316 {OSucc, OPred}; 317 none -> 318 {[], []} 319 end, 320 %% Change this block to contain new BB and new successors, but keep 321 %% the old predecessors which will be updated in the following steps 322 HT1 = gb_trees:enter(Label, {NewBB, Succ, OldPred}, HT), 323 %% Add this block as predecessor to its new successors 324 HT2 = lists:foldl(fun (P, HTAcc) -> 325 add_pred(HTAcc, P, Label) 326 end, 327 HT1, Succ -- OldSucc), 328 %% Remove this block as predecessor of its former successors 329 HT3 = lists:foldl(fun (S, HTAcc) -> 330 remove_pred(HTAcc, S, Label) 331 end, 332 HT2, OldSucc -- Succ), 333 CFG#cfg{table = HT3}. 334 335-ifdef(MAP_FOLD_NEEDED). 336-spec map_bbs(fun((cfg_lbl(), hipe_bb:bb()) -> hipe_bb:bb()), cfg()) -> cfg(). 337%% @doc Map over the code in a CFG without changing any control flow. 338map_bbs(Fun, CFG = #cfg{table=HT0}) -> 339 HT = gb_trees:map( 340 fun(Lbl, {OldBB, OldSucc, OldPred}) -> 341 NewBB = Fun(Lbl, OldBB), 342 %% Assert preconditions 343 NewLast = assert_bb(NewBB), 344 OldSucc = remove_duplicates(branch_successors(NewLast)), 345 {NewBB, OldSucc, OldPred} 346 end, HT0), 347 CFG#cfg{table=HT}. 348 349-spec fold_bbs(fun((cfg_lbl(), hipe_bb:bb(), Acc) -> Acc), Acc, cfg()) -> Acc. 350%% @doc Fold over the basic blocks in a CFG in unspecified order. 351fold_bbs(Fun, InitAcc, #cfg{table=HT}) -> 352 gb_trees_fold(fun(Lbl, {BB, _, _}, Acc) -> Fun(Lbl, BB, Acc) end, 353 InitAcc, HT). 354 355gb_trees_fold(Fun, InitAcc, Tree) -> 356 gb_trees_fold_1(Fun, InitAcc, gb_trees:iterator(Tree)). 357 358gb_trees_fold_1(Fun, InitAcc, Iter0) -> 359 case gb_trees:next(Iter0) of 360 none -> InitAcc; 361 {Key, Value, Iter} -> 362 gb_trees_fold_1(Fun, Fun(Key, Value, InitAcc), Iter) 363 end. 364-endif. % MAP_FOLD_NEEDED 365 366assert_bb(BB) -> 367 assert_bb_is(hipe_bb:code(BB)). 368 369assert_bb_is([Last]) -> 370 true = is_branch(Last), 371 Last; 372assert_bb_is([I|Is]) -> 373 false = is_branch(I), 374 false = is_label(I), 375 assert_bb_is(Is). 376 377remove_pred(HT, FromL, PredL) -> 378 case gb_trees:lookup(FromL, HT) of 379 {value, {Block, Succ, Preds}} -> 380 Code = hipe_bb:code(Block), 381 NewCode = remove_pred_from_phis(PredL, Code), 382 NewBlock = hipe_bb:code_update(Block, NewCode), 383 gb_trees:update(FromL, {NewBlock,Succ,lists:delete(PredL,Preds)}, HT); 384 none -> 385 HT 386 end. 387 388add_pred(HT, ToL, PredL) -> 389 case gb_trees:lookup(ToL, HT) of 390 {value,{Block,Succ,Preds}} -> 391 gb_trees:update(ToL, {Block,Succ,[PredL|lists:delete(PredL,Preds)]}, HT); 392 none -> 393 gb_trees:insert(ToL, {[],[],[PredL]}, HT) 394 end. 395 396%% find_highest_label(CFG) -> 397%% Labels = labels(CFG), 398%% lists:foldl(fun(X, Acc) -> erlang:max(X, Acc) end, 0, Labels). 399%% 400%% find_highest_var(CFG) -> 401%% Labels = labels(CFG), 402%% Fun = fun(X, Max) -> 403%% Code = hipe_bb:code(bb(CFG, X)), 404%% NewMax = highest_var(Code), 405%% erlang:max(Max, NewMax) 406%% end, 407%% lists:foldl(Fun, 0, Labels). 408 409-ifdef(CFG_CAN_HAVE_PHI_NODES). 410%% phi-instructions in a removed block's successors must be aware of 411%% the change. 412remove_pred_from_phis(Label, List = [I|Left]) -> 413 case is_phi(I) of 414 true -> 415 NewI = phi_remove_pred(I, Label), 416 [NewI | remove_pred_from_phis(Label, Left)]; 417 false -> 418 List 419 end; 420remove_pred_from_phis(_Label, []) -> 421 []. 422-else. 423%% this is used for code representations like those of back-ends which 424%% do not have phi-nodes. 425remove_pred_from_phis(_Label, Code) -> 426 Code. 427-endif. 428 429 430%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 431%% 432%% Constructs a CFG from a list of instructions. 433%% 434 435take_bbs([], CFG) -> 436 CFG; 437take_bbs(Xs, CFG) -> 438 Lbl = hd(Xs), 439 case is_label(Lbl) of 440 true -> 441 case take_bb(tl(Xs), []) of 442 {Code, Rest} -> 443 NewCFG = bb_add(CFG, label_name(Lbl), hipe_bb:mk_bb(Code)), 444 take_bbs(Rest, NewCFG) 445 end; 446 false -> 447 erlang:error({?MODULE,"basic block doesn't start with a label",Xs}) 448 end. 449 450%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 451%% 452%% Take_bb returns: 453%% - {Code, Rest}. 454%% * Code is a list of all the instructions. 455%% * Rest is the remainder of the instructions 456 457take_bb([], Code) -> 458 {lists:reverse(Code), []}; 459take_bb([X, Y|Xs], Code) -> 460 case is_label(X) of 461 true -> %% Empty block fallthrough 462 {[mk_goto(label_name(X))], [X,Y|Xs]}; 463 false -> 464 case is_branch(X) of 465 true -> 466 case is_label(Y) of 467 true -> 468 {lists:reverse([X|Code]), [Y|Xs]}; 469 false -> 470 %% This should not happen... 471 %% move the problem to the next BB. 472 {lists:reverse([X|Code]), [Y|Xs]} 473 end; 474 false -> %% X not branch 475 case is_label(Y) of 476 true -> 477 {lists:reverse([mk_goto(label_name(Y)),X|Code]), [Y|Xs]}; 478 false -> 479 take_bb([Y|Xs], [X|Code]) 480 end 481 end 482 end; 483take_bb([X], []) -> 484 case is_label(X) of 485 true -> 486 %% We don't want the CFG to just end with a label... 487 %% We loop forever instead... 488 {[X,mk_goto(label_name(X))],[]}; 489 false -> 490 {[X],[]} 491 end; 492take_bb([X], Code) -> 493 case is_label(X) of 494 true -> 495 %% We don't want the CFG to just end with a label... 496 %% We loop for ever instead... 497 {lists:reverse(Code),[X,mk_goto(label_name(X))]}; 498 false -> 499 {lists:reverse([X|Code]),[]} 500 end. 501 502%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 503%% 504%% Functions for extracting the names of the basic blocks in various 505%% orders. 506%% 507 508labels(CFG) -> 509 HT = CFG#cfg.table, 510 gb_trees:keys(HT). 511 512postorder(CFG) -> 513 lists:reverse(reverse_postorder(CFG)). 514 515reverse_postorder(CFG) -> 516 Start = start_label(CFG), 517 {Ordering, _Visited} = 518 depth_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []), 519 Ordering. 520 521depth_search([N|Ns], Visited, CFG, Acc) -> 522 case is_visited(N, Visited) of 523 true -> 524 depth_search(Ns, Visited, CFG, Acc); 525 false -> 526 {Order, Vis} = depth_search(succ(CFG, N), visit(N, Visited), CFG, Acc), 527 depth_search(Ns, Vis, CFG, [N|Order]) 528 end; 529depth_search([], Visited, _, Ordering) -> 530 {Ordering, Visited}. 531 532-ifdef(PREORDER). 533preorder(CFG) -> 534 Start = start_label(CFG), 535 {Ordering, _Visited} = 536 preorder_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []), 537 lists:reverse(Ordering). 538 539preorder_search([N|Ns], Visited, CFG, Acc) -> 540 case is_visited(N, Visited) of 541 true -> 542 preorder_search(Ns, Visited, CFG, Acc); 543 false -> 544 {Order, Vis} = 545 preorder_search(succ(CFG, N), visit(N, Visited), CFG, [N|Acc]), 546 preorder_search(Ns, Vis, CFG, Order) 547 end; 548preorder_search([], Visited, _, Ordering) -> 549 {Ordering,Visited}. 550-endif. % PREORDER 551 552-ifdef(BREADTH_ORDER). 553breadthorder(CFG) -> 554 lists:reverse(reverse_breadthorder(CFG)). 555 556reverse_breadthorder(CFG) -> 557 Start = start_label(CFG), 558 {Vis, RBO1} = breadth_list([Start], none_visited(), CFG, []), 559 {_Vis1, RBO2} = breadth_list(other_entrypoints(CFG), Vis, CFG, RBO1), 560 RBO2. 561 562breadth_list([X|Xs], Vis, CFG, BO) -> 563 case is_visited(X, Vis) of 564 true -> 565 breadth_list(Xs, Vis, CFG, BO); 566 false -> 567 breadth_list(Xs ++ succ(CFG, X), visit(X, Vis), CFG, [X|BO]) 568 end; 569breadth_list([], Vis, _CFG, BO) -> 570 {Vis, BO}. 571-endif. 572 573-spec none_visited() -> gb_sets:set(). 574none_visited() -> 575 gb_sets:empty(). 576 577visit(X, Vis) -> 578 gb_sets:add(X, Vis). 579 580is_visited(X, Vis) -> 581 gb_sets:is_member(X, Vis). 582 583-endif. % GEN_CFG 584 585%%--------------------------------------------------------------------- 586 587succ(SuccMap, Label) -> 588 HT = SuccMap#cfg.table, 589 case gb_trees:lookup(Label, HT) of 590 {value, {_Block,Succ,_Pred}} -> 591 Succ; 592 none -> 593 erlang:error({"successor not found", Label, SuccMap}) 594 end. 595 596-ifdef(PRED_NEEDED). 597pred(Map, Label) -> 598 HT = Map#cfg.table, 599 case gb_trees:lookup(Label, HT) of 600 {value, {_Block,_Succ,Pred}} -> 601 Pred; 602 none -> 603 erlang:error({"predecessor not found", Label, Map}) 604 end. 605-endif. % PRED_NEEDED 606 607-ifndef(GEN_CFG). 608fallthrough(CFG, Label) -> 609 HT = CFG#cfg.table, 610 case gb_trees:lookup(Label, HT) of 611 {value, {_Block, Succ, _}} -> 612 case Succ of 613 [X|_] -> X; 614 _ -> none 615 end; 616 none -> 617 erlang:error({"fallthrough label not found", Label}) 618 end. 619 620conditional(CFG, Label) -> 621 HT = CFG#cfg.table, 622 {value,{_Block,Succ,_}} = gb_trees:lookup(Label, HT), 623 case Succ of 624 [] -> none; 625 [_] -> none; 626 [_|Labels] -> Labels 627 end. 628-endif. % GEN_CFG 629 630%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 631%% 632%% Linearize the code in a CFG. Returns a list of instructions. 633%% 634 635-ifdef(GEN_CFG). 636-else. 637linearize_cfg(CFG) -> 638 Start = start_label(CFG), 639 Vis = none_visited(), 640 {Vis0, NestedCode} = lin_succ(Start, CFG, Vis), 641 BlocksInData = hipe_consttab:referred_labels(data(CFG)), 642 AllCode = lin_other_entries(NestedCode, CFG, BlocksInData, Vis0), 643 lists:flatten(AllCode). 644 645lin_succ(none, _CFG, Vis) -> 646 {Vis, []}; 647lin_succ([Label|Labels], CFG, Vis) -> 648 {Vis1, Code1} = lin_succ(Label, CFG, Vis), 649 {Vis2, Code2} = lin_succ(Labels, CFG, Vis1), 650 {Vis2, [Code1,Code2]}; 651lin_succ([], _CFG, Vis) -> 652 {Vis, []}; 653lin_succ(Label, CFG, Vis) -> 654 case is_visited(Label, Vis) of 655 true -> 656 {Vis, []}; % already visited 657 false -> 658 Vis0 = visit(Label, Vis), 659 case bb(CFG, Label) of 660 not_found -> 661 erlang:error({?MODULE, "No basic block with label", Label}); 662 BB -> 663 Fallthrough = fallthrough(CFG, Label), 664 Cond = conditional(CFG, Label), 665 LblInstr = mk_label(Label), 666 {Vis1, Code1} = lin_succ(Fallthrough, CFG, Vis0), 667 {Vis2, Code2} = lin_succ(Cond, CFG, Vis1), 668 {Vis2, [[LblInstr|hipe_bb:code(BB)], Code1, Code2]} 669 end 670 end. 671 672lin_other_entries(Code, _CFG, [], _Vis) -> 673 Code; 674lin_other_entries(Code, CFG, [E|Es], Vis) -> 675 {Vis0, MoreCode} = lin_succ(E, CFG, Vis), 676 lin_other_entries([Code, MoreCode], CFG, Es, Vis0). 677-endif. 678 679-ifdef(FIND_NEW_LABEL_NEEDED). 680find_new_label(Old, Map) -> 681 forward(Old, Map). 682-endif. 683 684%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 685%% 686%% Remove empty BBs. 687%% 688%% Removes basic blocks containing only a goto to another BB. 689%% Branches to removed blocks are updated to the successor of the 690%% removed block. 691%% Loads (or other operations) on the label of the BB are also 692%% updated. So are any references from the data section. 693%% 694 695-ifdef(REMOVE_TRIVIAL_BBS_NEEDED). 696 697-spec remove_trivial_bbs(cfg()) -> cfg(). 698remove_trivial_bbs(CFG) -> 699 ?opt_start_timer("Merge BBs"), 700 CFG0 = merge_bbs(rewrite_trivial_branches(CFG)), 701 ?opt_stop_timer("Merge BBs"), 702 %% pp(CFG0), 703 ?opt_start_timer("FindDead"), 704 {NewMap, CFG1} = remap(labels(CFG0), rd_map_new(), CFG0), 705 ?opt_stop_timer("FindDead"), 706 ?opt_start_timer("Labels"), 707 Labels = labels(CFG1), 708 ?opt_stop_timer("Labels"), 709 ?opt_start_timer("RedirectBranches"), 710 CFG2 = redirect_branches(NewMap, CFG1), 711 ?opt_stop_timer("RedirectBranches"), 712 ?opt_start_timer("RedirectOps"), 713 CFG3 = redirect_ops(Labels, CFG2, NewMap), 714 ?opt_stop_timer("RedirectOps"), 715 ?opt_start_timer("RedirectData"), 716 CFG4 = redirect_data(CFG3, NewMap), 717 ?opt_stop_timer("RedirectData"), 718 ?opt_start_timer("RedirectStart"), 719 CFG5 = redirect_start(CFG4, NewMap), 720 ?opt_stop_timer("RedirectStart"), 721 %% pp(CFG5), 722 CFG5. 723 724redirect_start(CFG, Map) -> 725 Start = start_label(CFG), 726 case forward(Start, Map) of 727 Start -> CFG; 728 NewStart -> 729 start_label_update(CFG, NewStart) 730 end. 731 732redirect_data(CFG, Map) -> 733 Data = data(CFG), 734 NewData = hipe_consttab:update_referred_labels(Data, rd_succs(Map)), 735 update_data(CFG, NewData). 736 737redirect_branches(Map, CFG) -> 738 lists:foldl(fun ({From,{newsuccs,Redirects}}, CFGAcc) -> 739 lists:foldl( 740 fun({ToOld,ToNew}, CFG1) -> 741 case bb(CFG1, From) of 742 not_found -> 743 CFG1; 744 _ -> 745 To = forward(ToNew, Map), 746 redirect(CFG1, From, ToOld, To) 747 end 748 end, 749 CFGAcc, 750 Redirects); 751 (_, CFGAcc) -> CFGAcc 752 end, 753 CFG, 754 gb_trees:to_list(Map)). 755 756redirect(CFG, From, ToOld, ToNew) -> 757 BB = bb(CFG, From), 758 LastInstr = hipe_bb:last(BB), 759 NewLastInstr = redirect_jmp(LastInstr, ToOld, ToNew), 760 NewBB = hipe_bb:mk_bb(hipe_bb:butlast(BB) ++ [NewLastInstr]), 761 bb_add(CFG, From, NewBB). 762 763bb_remove(CFG, Label) -> 764 HT = CFG#cfg.table, 765 case gb_trees:lookup(Label, HT) of 766 {value, {_Block, Succ, _Preds}} -> 767 %% Remove this block as a pred from all successors. 768 HT1 = lists:foldl(fun (S,HTAcc) -> 769 remove_pred(HTAcc, S, Label) 770 end, 771 HT, Succ), 772 CFG#cfg{table = gb_trees:delete(Label, HT1)}; 773 none -> 774 CFG 775 end. 776 777remap([L|Rest], Map, CFG) -> 778 case is_empty(bb(CFG, L)) of 779 true -> 780 case succ(CFG, L) of 781 [L] -> %% This is an empty (infinite) self loop. Leave it. 782 remap(Rest, Map, CFG); 783 [SuccL] -> 784 CFG1 = bb_remove(CFG, L), 785 NewMap = remap_to_succ(L, SuccL, Map, CFG), 786 remap(Rest, NewMap, CFG1) 787 end; 788 false -> 789 remap(Rest, Map, CFG) 790 end; 791remap([], Map, CFG) -> 792 {Map, CFG}. 793 794remap_to_succ(L, SuccL, Map, PredMap) -> 795 insert_remap(L, forward(SuccL,Map), pred(PredMap,L), Map). 796 797%% Find the proxy for a BB 798forward(L, Map) -> 799 case gb_trees:lookup(L, Map) of 800 {value, {dead, To}} -> 801 forward(To, Map); %% Hope this terminates. 802 _ -> L 803 end. 804 805%% A redirection map contains mappings from labels to 806%% none -> this BB is not affected by the remapping. 807%% {dead,To} -> this BB is dead, To is the new proxy. 808%% {newsuccs,[{X,Y}|...]} -> The successor X is redirected to Y. 809 810rd_map_new() -> gb_trees:empty(). 811 812rd_succs(M) -> 813 lists:foldl(fun ({From,{dead,To}}, Acc) -> [{From,forward(To,M)}|Acc]; 814 (_, Acc) -> Acc 815 end, 816 [], 817 gb_trees:to_list(M)). 818 819add_redirectedto(L, From, To, Map) -> 820 case gb_trees:lookup(L, Map) of 821 {value, {newsuccs, NS}} -> 822 gb_trees:update(L,{newsuccs,[{From,To}|lists:keydelete(From,1,NS)]},Map); 823 {value, {dead, _}} -> Map; 824 none -> 825 gb_trees:insert(L, {newsuccs, [{From, To}]}, Map) 826 end. 827 828insert_remap(L, ToL, Preds, Map) -> 829 Map2 = gb_trees:enter(L, {dead, ToL}, Map), 830 lists:foldl(fun (Pred, AccMap) -> 831 add_redirectedto(Pred, L, ToL, AccMap) 832 end, 833 Map2, 834 Preds). 835 836is_empty(BB) -> 837 is_empty_bb(hipe_bb:code(BB)). 838 839is_empty_bb([I]) -> 840 is_goto(I); %% A BB with just a 'goto' is empty. 841is_empty_bb([I|Is]) -> 842 case is_comment(I) of 843 true -> 844 is_empty_bb(Is); 845 false -> 846 false 847 end; 848is_empty_bb([]) -> 849 true. 850 851 852%% Rewrite all pure branches with one successor to goto:s 853 854-spec rewrite_trivial_branches(cfg()) -> cfg(). 855rewrite_trivial_branches(CFG) -> 856 rewrite_trivial_branches(postorder(CFG), CFG). 857 858rewrite_trivial_branches([L|Left], CFG) -> 859 BB = bb(CFG, L), 860 Last = hipe_bb:last(BB), 861 case is_goto(Last) of 862 true -> 863 rewrite_trivial_branches(Left, CFG); 864 false -> 865 case is_pure_branch(Last) of 866 false -> 867 rewrite_trivial_branches(Left, CFG); 868 true -> 869 case succ(CFG, L) of 870 [Successor] -> 871 Head = hipe_bb:butlast(BB), 872 NewBB = hipe_bb:mk_bb(Head ++ [mk_goto(Successor)]), 873 NewCFG = bb_add(CFG, L, NewBB), 874 rewrite_trivial_branches(Left, NewCFG); 875 _ -> 876 rewrite_trivial_branches(Left, CFG) 877 end 878 end 879 end; 880rewrite_trivial_branches([], CFG) -> 881 CFG. 882 883 884%% Go through the CFG and find pairs of BBs that can be merged to one BB. 885%% They are of the form: 886%% 887%% L 888%% | 889%% Successor 890%% 891%% That is, the block L has only one successor (Successor) and that 892%% successor has no other predecessors than L. 893%% 894%% Note: calls might end a basic block 895 896merge_bbs(CFG) -> 897 lists:foldl(fun merge_successor/2, CFG, postorder(CFG)). 898 899%% If L fulfills the requirements, merge it with its successor. 900merge_successor(L, CFG) -> 901 %% Get the BB L (If it still exists). 902 case bb(CFG, L) of 903 not_found -> CFG; 904 BB -> 905 StartLabel = start_label(CFG), 906 Last = hipe_bb:last(BB), 907 %% Note: Cannot use succ/2 since the instruction can have more than 908 %% one successor that are the same label. 909 case {branch_successors(Last), fails_to(Last)} of 910 {[Successor],[Successor]} -> 911 %% The single successor is the fail-label; don't merge. 912 CFG; 913 {[Successor],_} when Successor =/= StartLabel -> 914 %% Make sure the succesor only have this block as predecessor. 915 case [L] =:= pred(CFG, Successor) of 916 true -> 917 %% Remove the goto or remap fall-through in BB and merge the BBs 918 NewCode = merge(BB, bb(CFG, Successor), Successor), 919 NewBB = hipe_bb:mk_bb(NewCode), 920 bb_add(bb_remove(CFG, Successor), L, NewBB); 921 false -> 922 CFG 923 end; 924 _ -> 925 %% Not exactly one successor or tried to merge with the 926 %% entry point 927 CFG 928 end 929 end. 930 931%% Merge BB and BB2 932merge(BB, BB2, BB2_Label) -> 933 Head = hipe_bb:butlast(BB), 934 Last = hipe_bb:last(BB), 935 Tail = hipe_bb:code(BB2), 936 case is_goto(Last) of 937 true -> 938 %% Just ignore the goto. 939 Head ++ Tail; 940 false -> 941 %% The last instr is not a goto, 942 %% e.g. a call with only fall-through 943 %% Remove the fall-through with the []-label. 944 Head ++ [redirect_jmp(Last, BB2_Label, [])|Tail] 945 end. 946 947-endif. % REMOVE_TRIVIAL_BBS_NEEDED 948 949 950%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 951%% 952%% Remove unreachable BBs. 953%% 954%% A BB is unreachable if it cannot be reached by any path from the 955%% start label of the function. 956%% 957%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 958 959-ifdef(REMOVE_UNREACHABLE_CODE). 960 961-spec remove_unreachable_code(cfg()) -> cfg(). 962 963remove_unreachable_code(CFG) -> 964 Start = start_label(CFG), 965 %% No unreachable block will make another block reachable, so no fixpoint 966 %% looping is required 967 Reachable = find_reachable([], [Start], CFG, #{Start=>[]}), 968 case [L || L <- labels(CFG), not maps:is_key(L, Reachable)] of 969 [] -> CFG; 970 Remove -> 971 HT0 = CFG#cfg.table, 972 HT1 = lists:foldl(fun gb_trees:delete/2, HT0, Remove), 973 ReachableP = fun(Lbl) -> maps:is_key(Lbl, Reachable) end, 974 HT = gb_trees:map(fun(_,B)->prune_preds(B, ReachableP)end, HT1), 975 CFG#cfg{table=HT} 976 end. 977 978find_reachable([], [], _CFG, Acc) -> Acc; 979find_reachable([Succ|Succs], Left, CFG, Acc) -> 980 case Acc of 981 #{Succ := _} -> find_reachable(Succs, Left, CFG, Acc); 982 #{} -> find_reachable(Succs, [Succ|Left], CFG, Acc#{Succ => []}) 983 end; 984find_reachable([], [Label|Left], CFG, Acc) -> 985 find_reachable(succ(CFG, Label), Left, CFG, Acc). 986 987%% Batch prune unreachable predecessors. Asymptotically faster than deleting 988%% unreachable blocks one at a time with bb_remove, at least when 989%% CFG_CAN_HAVE_PHI_NODES is undefined. Otherwise a phi_remove_preds might be 990%% needed to achieve that. 991prune_preds(B={Block, Succ, Preds}, ReachableP) -> 992 case lists:partition(ReachableP, Preds) of 993 {_, []} -> B; 994 {NewPreds, Unreach} -> 995 NewCode = remove_preds_from_phis(Unreach, hipe_bb:code(Block)), 996 {hipe_bb:code_update(Block, NewCode), Succ, NewPreds} 997 end. 998 999-ifdef(CFG_CAN_HAVE_PHI_NODES). 1000remove_preds_from_phis(_, []) -> []; 1001remove_preds_from_phis(Preds, List=[I|Left]) -> 1002 case is_phi(I) of 1003 false -> List; 1004 true -> 1005 NewI = lists:foldl(fun(L,IA)->phi_remove_pred(IA,L)end, 1006 I, Preds), 1007 [NewI | remove_preds_from_phis(Preds, Left)] 1008 end. 1009-else. 1010remove_preds_from_phis(_, Code) -> Code. 1011-endif. 1012 1013-endif. %% -ifdef(REMOVE_UNREACHABLE_CODE) 1014