tree-ssa-threadupdate.c revision 285830
118334Speter/* Thread edges through blocks and update the control flow and SSA graphs. 218334Speter Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. 318334Speter 4169689SkanThis file is part of GCC. 5169689Skan 690075SobrienGCC is free software; you can redistribute it and/or modify 718334Speterit under the terms of the GNU General Public License as published by 890075Sobrienthe Free Software Foundation; either version 2, or (at your option) 918334Speterany later version. 1090075Sobrien 1190075SobrienGCC is distributed in the hope that it will be useful, 1290075Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1390075SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1418334SpeterGNU General Public License for more details. 1590075Sobrien 1690075SobrienYou should have received a copy of the GNU General Public License 1790075Sobrienalong with GCC; see the file COPYING. If not, write to 1890075Sobrienthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 1918334SpeterBoston, MA 02110-1301, USA. */ 2018334Speter 2190075Sobrien#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 2418334Speter#include "tm.h" 2518334Speter#include "tree.h" 2618334Speter#include "flags.h" 2718334Speter#include "rtl.h" 2818334Speter#include "tm_p.h" 2918334Speter#include "ggc.h" 3018334Speter#include "basic-block.h" 3118334Speter#include "output.h" 3218334Speter#include "expr.h" 3318334Speter#include "function.h" 3418334Speter#include "diagnostic.h" 3518334Speter#include "tree-flow.h" 3618334Speter#include "tree-dump.h" 3718334Speter#include "tree-pass.h" 3818334Speter#include "cfgloop.h" 3918334Speter 4018334Speter/* Given a block B, update the CFG and SSA graph to reflect redirecting 4118334Speter one or more in-edges to B to instead reach the destination of an 4218334Speter out-edge from B while preserving any side effects in B. 43132718Skan 4418334Speter i.e., given A->B and B->C, change A->B to be A->C yet still preserve the 4518334Speter side effects of executing B. 4618334Speter 4718334Speter 1. Make a copy of B (including its outgoing edges and statements). Call 4818334Speter the copy B'. Note B' has no incoming edges or PHIs at this time. 4918334Speter 50169689Skan 2. Remove the control statement at the end of B' and all outgoing edges 51169689Skan except B'->C. 52169689Skan 53169689Skan 3. Add a new argument to each PHI in C with the same value as the existing 54169689Skan argument associated with edge B->C. Associate the new PHI arguments 55169689Skan with the edge B'->C. 56169689Skan 57169689Skan 4. For each PHI in B, find or create a PHI in B' with an identical 58169689Skan PHI_RESULT. Add an argument to the PHI in B' which has the same 59169689Skan value as the PHI in B associated with the edge A->B. Associate 60169689Skan the new argument in the PHI in B' with the edge A->B. 61169689Skan 62169689Skan 5. Change the edge A->B to A->B'. 63169689Skan 64169689Skan 5a. This automatically deletes any PHI arguments associated with the 65169689Skan edge A->B in B. 66169689Skan 67169689Skan 5b. This automatically associates each new argument added in step 4 68169689Skan with the edge A->B'. 69169689Skan 70169689Skan 6. Repeat for other incoming edges into B. 71169689Skan 72169689Skan 7. Put the duplicated resources in B and all the B' blocks into SSA form. 73169689Skan 74169689Skan Note that block duplication can be minimized by first collecting the 75169689Skan the set of unique destination blocks that the incoming edges should 76169689Skan be threaded to. Block duplication can be further minimized by using 7718334Speter B instead of creating B' for one destination if all edges into B are 78169689Skan going to be threaded to a successor of B. 79169689Skan 8018334Speter We further reduce the number of edges and statements we create by 81169689Skan not copying all the outgoing edges and the control statement in 82169689Skan step #1. We instead create a template block without the outgoing 83169689Skan edges and duplicate the template. */ 8418334Speter 8518334Speter 8618334Speter/* Steps #5 and #6 of the above algorithm are best implemented by walking 8718334Speter all the incoming edges which thread to the same destination edge at 8818334Speter the same time. That avoids lots of table lookups to get information 8918334Speter for the destination edge. 90169689Skan 9118334Speter To realize that implementation we create a list of incoming edges 9218334Speter which thread to the same outgoing edge. Thus to implement steps 9318334Speter #5 and #6 we traverse our hash table of outgoing edge information. 94169689Skan For each entry we walk the list of incoming edges which thread to 9518334Speter the current outgoing edge. */ 96169689Skan 97169689Skanstruct el 98169689Skan{ 99169689Skan edge e; 10018334Speter struct el *next; 10118334Speter}; 10218334Speter 10318334Speter/* Main data structure recording information regarding B's duplicate 10418334Speter blocks. */ 105169689Skan 10618334Speter/* We need to efficiently record the unique thread destinations of this 10790075Sobrien block and specific information associated with those destinations. We 108169689Skan may have many incoming edges threaded to the same outgoing edge. This 10918334Speter can be naturally implemented with a hash table. */ 11018334Speter 11118334Speterstruct redirection_data 11218334Speter{ 11318334Speter /* A duplicate of B with the trailing control statement removed and which 11418334Speter targets a single successor of B. */ 11518334Speter basic_block dup_block; 116132718Skan 11718334Speter /* An outgoing edge from B. DUP_BLOCK will have OUTGOING_EDGE->dest as 11818334Speter its single successor. */ 11918334Speter edge outgoing_edge; 12018334Speter 121169689Skan /* A list of incoming edges which we want to thread to 12218334Speter OUTGOING_EDGE->dest. */ 12318334Speter struct el *incoming_edges; 124132718Skan 125169689Skan /* Flag indicating whether or not we should create a duplicate block 12618334Speter for this thread destination. This is only true if we are threading 12718334Speter all incoming edges and thus are using BB itself as a duplicate block. */ 12818334Speter bool do_not_duplicate; 12918334Speter}; 130132718Skan 131132718Skan/* Main data structure to hold information for duplicates of BB. */ 132169689Skanstatic htab_t redirection_data; 13318334Speter 13418334Speter/* Data structure of information to pass to hash table traversal routines. */ 135169689Skanstruct local_info 13618334Speter{ 13718334Speter /* The current block we are working on. */ 13818334Speter basic_block bb; 139132718Skan 140132718Skan /* A template copy of BB with no outgoing edges or control statement that 141132718Skan we use for creating copies. */ 142260918Spfg basic_block template_block; 143260918Spfg 144260918Spfg /* TRUE if we thread one or more jumps, FALSE otherwise. */ 145260918Spfg bool jumps_threaded; 146260918Spfg}; 147117395Skan 148260918Spfg/* Passes which use the jump threading code register jump threading 149169689Skan opportunities as they are discovered. We keep the registered 15018334Speter jump threading opportunities in this vector as edge pairs 15190075Sobrien (original_edge, target_edge). */ 152169689SkanDEF_VEC_ALLOC_P(edge,heap); 153169689Skanstatic VEC(edge,heap) *threaded_edges; 154169689Skan 155169689Skan 156169689Skan/* Jump threading statistics. */ 157169689Skan 158132718Skanstruct thread_stats_d 159132718Skan{ 160132718Skan unsigned long num_threaded_edges; 161169689Skan}; 162169689Skan 16318334Speterstruct thread_stats_d thread_stats; 16418334Speter 16518334Speter 16618334Speter/* Remove the last statement in block BB if it is a control statement 16718334Speter Also remove all outgoing edges except the edge which reaches DEST_BB. 16890075Sobrien If DEST_BB is NULL, then remove all outgoing edges. */ 16990075Sobrien 17090075Sobrienstatic void 17190075Sobrienremove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb) 17290075Sobrien{ 17390075Sobrien block_stmt_iterator bsi; 17490075Sobrien edge e; 175169689Skan edge_iterator ei; 17690075Sobrien 17790075Sobrien bsi = bsi_last (bb); 178169689Skan 17918334Speter /* If the duplicate ends with a control statement, then remove it. 18018334Speter 18118334Speter Note that if we are duplicating the template block rather than the 18218334Speter original basic block, then the duplicate might not have any real 18318334Speter statements in it. */ 18418334Speter if (!bsi_end_p (bsi) 18518334Speter && bsi_stmt (bsi) 186169689Skan && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR 18718334Speter || TREE_CODE (bsi_stmt (bsi)) == GOTO_EXPR 188169689Skan || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR)) 18918334Speter bsi_remove (&bsi, true); 19018334Speter 19118334Speter for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 19218334Speter { 19318334Speter if (e->dest != dest_bb) 19418334Speter remove_edge (e); 19518334Speter else 19618334Speter ei_next (&ei); 19718334Speter } 19818334Speter} 199169689Skan 200169689Skan/* Create a duplicate of BB which only reaches the destination of the edge 201169689Skan stored in RD. Record the duplicate block in RD. */ 202169689Skan 203169689Skanstatic void 204169689Skancreate_block_for_threading (basic_block bb, struct redirection_data *rd) 205169689Skan{ 206169689Skan /* We can use the generic block duplication code and simply remove 207169689Skan the stuff we do not need. */ 208169689Skan rd->dup_block = duplicate_block (bb, NULL, NULL); 209169689Skan 210169689Skan /* Zero out the profile, since the block is unreachable for now. */ 211169689Skan rd->dup_block->frequency = 0; 21218334Speter rd->dup_block->count = 0; 21318334Speter 214169689Skan /* The call to duplicate_block will copy everything, including the 215169689Skan useless COND_EXPR or SWITCH_EXPR at the end of BB. We just remove 21618334Speter the useless COND_EXPR or SWITCH_EXPR here rather than having a 21718334Speter specialized block copier. We also remove all outgoing edges 21818334Speter from the duplicate block. The appropriate edge will be created 21918334Speter later. */ 22018334Speter remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL); 22118334Speter} 22218334Speter 22318334Speter/* Hashing and equality routines for our hash table. */ 22418334Speterstatic hashval_t 22518334Speterredirection_data_hash (const void *p) 226169689Skan{ 22718334Speter edge e = ((struct redirection_data *)p)->outgoing_edge; 22818334Speter return e->dest->index; 229169689Skan} 23018334Speter 23118334Speterstatic int 23218334Speterredirection_data_eq (const void *p1, const void *p2) 233169689Skan{ 23418334Speter edge e1 = ((struct redirection_data *)p1)->outgoing_edge; 23518334Speter edge e2 = ((struct redirection_data *)p2)->outgoing_edge; 23618334Speter 23718334Speter return e1 == e2; 23850397Sobrien} 23950397Sobrien 24050397Sobrien/* Given an outgoing edge E lookup and return its entry in our hash table. 24150397Sobrien 24250397Sobrien If INSERT is true, then we insert the entry into the hash table if 24350397Sobrien it is not already present. INCOMING_EDGE is added to the list of incoming 24450397Sobrien edges associated with E in the hash table. */ 24550397Sobrien 24650397Sobrienstatic struct redirection_data * 24750397Sobrienlookup_redirection_data (edge e, edge incoming_edge, enum insert_option insert) 24850397Sobrien{ 24950397Sobrien void **slot; 25050397Sobrien struct redirection_data *elt; 25150397Sobrien 25250397Sobrien /* Build a hash table element so we can see if E is already 25318334Speter in the table. */ 25450397Sobrien elt = XNEW (struct redirection_data); 25550397Sobrien elt->outgoing_edge = e; 25650397Sobrien elt->dup_block = NULL; 25750397Sobrien elt->do_not_duplicate = false; 258169689Skan elt->incoming_edges = NULL; 25950397Sobrien 26090075Sobrien slot = htab_find_slot (redirection_data, elt, insert); 26190075Sobrien 26290075Sobrien /* This will only happen if INSERT is false and the entry is not 26390075Sobrien in the hash table. */ 26490075Sobrien if (slot == NULL) 26590075Sobrien { 26690075Sobrien free (elt); 26790075Sobrien return NULL; 26890075Sobrien } 269169689Skan 27090075Sobrien /* This will only happen if E was not in the hash table and 27118334Speter INSERT is true. */ 27218334Speter if (*slot == NULL) 27318334Speter { 27418334Speter *slot = (void *)elt; 27518334Speter elt->incoming_edges = XNEW (struct el); 27618334Speter elt->incoming_edges->e = incoming_edge; 27718334Speter elt->incoming_edges->next = NULL; 27818334Speter return elt; 27918334Speter } 28018334Speter /* E was in the hash table. */ 281169689Skan else 28218334Speter { 28318334Speter /* Free ELT as we do not need it anymore, we will extract the 28418334Speter relevant entry from the hash table itself. */ 28518334Speter free (elt); 286169689Skan 28718334Speter /* Get the entry stored in the hash table. */ 28818334Speter elt = (struct redirection_data *) *slot; 28918334Speter 29018334Speter /* If insertion was requested, then we need to add INCOMING_EDGE 291169689Skan to the list of incoming edges associated with E. */ 29218334Speter if (insert) 29318334Speter { 29418334Speter struct el *el = XNEW (struct el); 29518334Speter el->next = elt->incoming_edges; 29618334Speter el->e = incoming_edge; 297169689Skan elt->incoming_edges = el; 29818334Speter } 29918334Speter 30018334Speter return elt; 301169689Skan } 30218334Speter} 30318334Speter 30418334Speter/* Given a duplicate block and its single destination (both stored 30518334Speter in RD). Create an edge between the duplicate and its single 30618334Speter destination. 307169689Skan 30818334Speter Add an additional argument to any PHI nodes at the single 30990075Sobrien destination. */ 31090075Sobrien 31190075Sobrienstatic void 312169689Skancreate_edge_and_update_destination_phis (struct redirection_data *rd) 31390075Sobrien{ 31418334Speter edge e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU); 31518334Speter tree phi; 31618334Speter 31718334Speter e->probability = REG_BR_PROB_BASE; 31818334Speter e->count = rd->dup_block->count; 319169689Skan 32018334Speter /* If there are any PHI nodes at the destination of the outgoing edge 32190075Sobrien from the duplicate block, then we will need to add a new argument 322117395Skan to them. The argument should have the same value as the argument 323117395Skan associated with the outgoing edge stored in RD. */ 324169689Skan for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 32518334Speter { 32696263Sobrien int indx = rd->outgoing_edge->dest_idx; 327169689Skan add_phi_arg (phi, PHI_ARG_DEF (phi, indx), e); 32896263Sobrien } 329169689Skan} 330169689Skan 331169689Skan/* Hash table traversal callback routine to create duplicate blocks. */ 332169689Skan 33318334Speterstatic int 33418334Spetercreate_duplicates (void **slot, void *data) 33518334Speter{ 33618334Speter struct redirection_data *rd = (struct redirection_data *) *slot; 33718334Speter struct local_info *local_info = (struct local_info *)data; 338169689Skan 33918334Speter /* If this entry should not have a duplicate created, then there's 34018334Speter nothing to do. */ 34118334Speter if (rd->do_not_duplicate) 342169689Skan return 1; 34318334Speter 344169689Skan /* Create a template block if we have not done so already. Otherwise 345169689Skan use the template to create a new block. */ 346169689Skan if (local_info->template_block == NULL) 347169689Skan { 34890075Sobrien create_block_for_threading (local_info->bb, rd); 34950397Sobrien local_info->template_block = rd->dup_block; 35050397Sobrien 35150397Sobrien /* We do not create any outgoing edges for the template. We will 35290075Sobrien take care of that in a later traversal. That way we do not 353169689Skan create edges that are going to just be deleted. */ 354169689Skan } 35590075Sobrien else 35690075Sobrien { 357169689Skan create_block_for_threading (local_info->template_block, rd); 35818334Speter 35918334Speter /* Go ahead and wire up outgoing edges and update PHIs for the duplicate 36018334Speter block. */ 36118334Speter create_edge_and_update_destination_phis (rd); 36218334Speter } 36318334Speter 364169689Skan /* Keep walking the hash table. */ 36518334Speter return 1; 36618334Speter} 36718334Speter 36818334Speter/* We did not create any outgoing edges for the template block during 36918334Speter block creation. This hash table traversal callback creates the 37018334Speter outgoing edge for the template block. */ 37118334Speter 37218334Speterstatic int 37318334Speterfixup_template_block (void **slot, void *data) 374169689Skan{ 37518334Speter struct redirection_data *rd = (struct redirection_data *) *slot; 37618334Speter struct local_info *local_info = (struct local_info *)data; 37718334Speter 37818334Speter /* If this is the template block, then create its outgoing edges 37918334Speter and halt the hash table traversal. */ 38018334Speter if (rd->dup_block && rd->dup_block == local_info->template_block) 38118334Speter { 38218334Speter create_edge_and_update_destination_phis (rd); 38318334Speter return 0; 38418334Speter } 38518334Speter 38618334Speter return 1; 387169689Skan} 38818334Speter 38918334Speter/* Not all jump threading requests are useful. In particular some 39018334Speter jump threading requests can create irreducible regions which are 39118334Speter undesirable. 39218334Speter 393169689Skan This routine will examine the BB's incoming edges for jump threading 39418334Speter requests which, if acted upon, would create irreducible regions. Any 39590075Sobrien such jump threading requests found will be pruned away. */ 39690075Sobrien 39790075Sobrienstatic void 398169689Skanprune_undesirable_thread_requests (basic_block bb) 39918334Speter{ 40018334Speter edge e; 401169689Skan edge_iterator ei; 402169689Skan bool may_create_irreducible_region = false; 40318334Speter unsigned int num_outgoing_edges_into_loop = 0; 404132718Skan 405132718Skan /* For the heuristics below, we need to know if BB has more than 406132718Skan one outgoing edge into a loop. */ 407132718Skan FOR_EACH_EDGE (e, ei, bb->succs) 408132718Skan num_outgoing_edges_into_loop += ((e->flags & EDGE_LOOP_EXIT) == 0); 409169689Skan 41018334Speter if (num_outgoing_edges_into_loop > 1) 41118334Speter { 41218334Speter edge backedge = NULL; 41318334Speter 41418334Speter /* Consider the effect of threading the edge (0, 1) to 2 on the left 41518334Speter CFG to produce the right CFG: 416169689Skan 41718334Speter 41818334Speter 0 0 41918334Speter | | 42018334Speter 1<--+ 2<--------+ 42118334Speter / \ | | | 42218334Speter 2 3 | 4<----+ | 42318334Speter \ / | / \ | | 42418334Speter 4---+ E 1-- | --+ 42518334Speter | | | 42618334Speter E 3---+ 42718334Speter 428169689Skan 42918334Speter Threading the (0, 1) edge to 2 effectively creates two loops 43018334Speter (2, 4, 1) and (4, 1, 3) which are neither disjoint nor nested. 431169689Skan This is not good. 43218334Speter 43318334Speter However, we do need to be able to thread (0, 1) to 2 or 3 434169689Skan in the left CFG below (which creates the middle and right 43518334Speter CFGs with nested loops). 43618334Speter 437169689Skan 0 0 0 43818334Speter | | | 43918334Speter 1<--+ 2<----+ 3<-+<-+ 440169689Skan /| | | | | | | 44118334Speter 2 | | 3<-+ | 1--+ | 442169689Skan \| | | | | | | 44318334Speter 3---+ 1--+--+ 2-----+ 44418334Speter 445169689Skan 44618334Speter A safe heuristic appears to be to only allow threading if BB 447169689Skan has a single incoming backedge from one of its direct successors. */ 44818334Speter 44918334Speter FOR_EACH_EDGE (e, ei, bb->preds) 450169689Skan { 451169689Skan if (e->flags & EDGE_DFS_BACK) 45218334Speter { 45318334Speter if (backedge) 454169689Skan { 455169689Skan backedge = NULL; 456169689Skan break; 457169689Skan } 45818334Speter else 45918334Speter { 46018334Speter backedge = e; 46118334Speter } 462169689Skan } 463169689Skan } 464169689Skan 465169689Skan if (backedge && find_edge (bb, backedge->src)) 466169689Skan ; 46718334Speter else 46818334Speter may_create_irreducible_region = true; 46918334Speter } 470169689Skan else 471169689Skan { 472169689Skan edge dest = NULL; 473169689Skan 47418334Speter /* If we thread across the loop entry block (BB) into the 475169689Skan loop and BB is still reached from outside the loop, then 476169689Skan we would create an irreducible CFG. Consider the effect 477169689Skan of threading the edge (1, 4) to 5 on the left CFG to produce 478169689Skan the right CFG 47918334Speter 48018334Speter 0 0 48118334Speter / \ / \ 48218334Speter 1 2 1 2 48318334Speter \ / | | 48418334Speter 4<----+ 5<->4 48518334Speter / \ | | 48618334Speter E 5---+ E 487169689Skan 488169689Skan 489169689Skan Threading the (1, 4) edge to 5 creates two entry points 490169689Skan into the loop (4, 5) (one from block 1, the other from 49118334Speter block 2). A classic irreducible region. 49252284Sobrien 49352284Sobrien So look at all of BB's incoming edges which are not 49452284Sobrien backedges and which are not threaded to the loop exit. 49590075Sobrien If that subset of incoming edges do not all thread 49690075Sobrien to the same block, then threading any of them will create 49790075Sobrien an irreducible region. */ 49890075Sobrien 49990075Sobrien FOR_EACH_EDGE (e, ei, bb->preds) 50090075Sobrien { 50190075Sobrien edge e2; 50290075Sobrien 50390075Sobrien /* We ignore back edges for now. This may need refinement 504169689Skan as threading a backedge creates an inner loop which 505169689Skan we would need to verify has a single entry point. 50652284Sobrien 50718334Speter If all backedges thread to new locations, then this 50818334Speter block will no longer have incoming backedges and we 509169689Skan need not worry about creating irreducible regions 510169689Skan by threading through BB. I don't think this happens 511169689Skan enough in practice to worry about it. */ 512169689Skan if (e->flags & EDGE_DFS_BACK) 513169689Skan continue; 514169689Skan 515169689Skan /* If the incoming edge threads to the loop exit, then it 516169689Skan is clearly safe. */ 517169689Skan e2 = e->aux; 518169689Skan if (e2 && (e2->flags & EDGE_LOOP_EXIT)) 51918334Speter continue; 520132718Skan 521169689Skan /* E enters the loop header and is not threaded. We can 522169689Skan not allow any other incoming edges to thread into 52390075Sobrien the loop as that would create an irreducible region. */ 524117395Skan if (!e2) 525169689Skan { 526169689Skan may_create_irreducible_region = true; 527169689Skan break; 528169689Skan } 529169689Skan 53090075Sobrien /* We know that this incoming edge threads to a block inside 53190075Sobrien the loop. This edge must thread to the same target in 532169689Skan the loop as any previously seen threaded edges. Otherwise 53390075Sobrien we will create an irreducible region. */ 53418334Speter if (!dest) 53518334Speter dest = e2; 53618334Speter else if (e2 != dest) 537169689Skan { 53818334Speter may_create_irreducible_region = true; 53918334Speter break; 540169689Skan } 54118334Speter } 54218334Speter } 543169689Skan 54418334Speter /* If we might create an irreducible region, then cancel any of 54518334Speter the jump threading requests for incoming edges which are 546169689Skan not backedges and which do not thread to the exit block. */ 547169689Skan if (may_create_irreducible_region) 54818334Speter { 54918334Speter FOR_EACH_EDGE (e, ei, bb->preds) 550169689Skan { 55118334Speter edge e2; 55218334Speter 55318334Speter /* Ignore back edges. */ 55418334Speter if (e->flags & EDGE_DFS_BACK) 55518334Speter continue; 55618334Speter 55718334Speter e2 = e->aux; 558169689Skan 55918334Speter /* If this incoming edge was not threaded, then there is 56018334Speter nothing to do. */ 561169689Skan if (!e2) 56218334Speter continue; 56318334Speter 56418334Speter /* If this incoming edge threaded to the loop exit, 56518334Speter then it can be ignored as it is safe. */ 566169689Skan if (e2->flags & EDGE_LOOP_EXIT) 56718334Speter continue; 56818334Speter 569169689Skan if (e2) 57018334Speter { 57118334Speter /* This edge threaded into the loop and the jump thread 572169689Skan request must be cancelled. */ 57318334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 574259563Spfg fprintf (dump_file, " Not threading jump %d --> %d to %d\n", 575259563Spfg e->src->index, e->dest->index, e2->dest->index); 576259563Spfg e->aux = NULL; 57718334Speter } 57818334Speter } 57918334Speter } 580169689Skan} 58118334Speter 582132718Skan/* Hash table traversal callback to redirect each incoming edge 583169689Skan associated with this hash table element to its new destination. */ 584132718Skan 585132718Skanstatic int 586169689Skanredirect_edges (void **slot, void *data) 587132718Skan{ 588132718Skan struct redirection_data *rd = (struct redirection_data *) *slot; 589169689Skan struct local_info *local_info = (struct local_info *)data; 590132718Skan struct el *next, *el; 591132718Skan 592169689Skan /* Walk over all the incoming edges associated associated with this 593132718Skan hash table entry. */ 59418334Speter for (el = rd->incoming_edges; el; el = next) 59518334Speter { 59618334Speter edge e = el->e; 59718334Speter 59818334Speter /* Go ahead and free this element from the list. Doing this now 59918334Speter avoids the need for another list walk when we destroy the hash 60018334Speter table. */ 60118334Speter next = el->next; 602169689Skan free (el); 603169689Skan 604169689Skan /* Go ahead and clear E->aux. It's not needed anymore and failure 60518334Speter to clear it will cause all kinds of unpleasant problems later. */ 606169689Skan e->aux = NULL; 607169689Skan 608169689Skan thread_stats.num_threaded_edges++; 60918334Speter 61018334Speter if (rd->dup_block) 61118334Speter { 61218334Speter edge e2; 613169689Skan 61418334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 61518334Speter fprintf (dump_file, " Threaded jump %d --> %d to %d\n", 61618334Speter e->src->index, e->dest->index, rd->dup_block->index); 617169689Skan 61818334Speter rd->dup_block->count += e->count; 61990075Sobrien rd->dup_block->frequency += EDGE_FREQUENCY (e); 62090075Sobrien EDGE_SUCC (rd->dup_block, 0)->count += e->count; 62190075Sobrien /* Redirect the incoming edge to the appropriate duplicate 62290075Sobrien block. */ 62390075Sobrien e2 = redirect_edge_and_branch (e, rd->dup_block); 624169689Skan flush_pending_stmts (e2); 62590075Sobrien 62690075Sobrien if ((dump_file && (dump_flags & TDF_DETAILS)) 62790075Sobrien && e->src != e2->src) 62890075Sobrien fprintf (dump_file, " basic block %d created\n", e2->src->index); 62990075Sobrien } 630169689Skan else 63190075Sobrien { 63290075Sobrien if (dump_file && (dump_flags & TDF_DETAILS)) 63390075Sobrien fprintf (dump_file, " Threaded jump %d --> %d to %d\n", 63490075Sobrien e->src->index, e->dest->index, local_info->bb->index); 635169689Skan 63690075Sobrien /* We are using BB as the duplicate. Remove the unnecessary 63790075Sobrien outgoing edges and statements from BB. */ 63890075Sobrien remove_ctrl_stmt_and_useless_edges (local_info->bb, 63990075Sobrien rd->outgoing_edge->dest); 64090075Sobrien 641169689Skan /* And fixup the flags on the single remaining edge. */ 64290075Sobrien single_succ_edge (local_info->bb)->flags 64390075Sobrien &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); 644169689Skan single_succ_edge (local_info->bb)->flags |= EDGE_FALLTHRU; 64590075Sobrien } 64690075Sobrien } 647169689Skan 64890075Sobrien /* Indicate that we actually threaded one or more jumps. */ 64990075Sobrien if (rd->incoming_edges) 650169689Skan local_info->jumps_threaded = true; 65190075Sobrien 652169689Skan return 1; 653169689Skan} 654169689Skan 655169689Skan/* Return true if this block has no executable statements other than 656169689Skan a simple ctrl flow instruction. When the number of outgoing edges 657169689Skan is one, this is equivalent to a "forwarder" block. */ 65890075Sobrien 659169689Skanstatic bool 66090075Sobrienredirection_block_p (basic_block bb) 66190075Sobrien{ 662169689Skan block_stmt_iterator bsi; 66390075Sobrien 66490075Sobrien /* Advance to the first executable statement. */ 665169689Skan bsi = bsi_start (bb); 66690075Sobrien while (!bsi_end_p (bsi) 667169689Skan && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR 668169689Skan || IS_EMPTY_STMT (bsi_stmt (bsi)))) 66990075Sobrien bsi_next (&bsi); 670169689Skan 671169689Skan /* Check if this is an empty block. */ 672169689Skan if (bsi_end_p (bsi)) 673169689Skan return true; 674169689Skan 675169689Skan /* Test that we've reached the terminating control statement. */ 676169689Skan return bsi_stmt (bsi) 677169689Skan && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR 678169689Skan || TREE_CODE (bsi_stmt (bsi)) == GOTO_EXPR 679169689Skan || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR); 680169689Skan} 681169689Skan 682169689Skan/* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB 683169689Skan is reached via one or more specific incoming edges, we know which 684169689Skan outgoing edge from BB will be traversed. 685169689Skan 686169689Skan We want to redirect those incoming edges to the target of the 687169689Skan appropriate outgoing edge. Doing so avoids a conditional branch 688169689Skan and may expose new optimization opportunities. Note that we have 689169689Skan to update dominator tree and SSA graph after such changes. 690169689Skan 691169689Skan The key to keeping the SSA graph update manageable is to duplicate 692169689Skan the side effects occurring in BB so that those side effects still 693169689Skan occur on the paths which bypass BB after redirecting edges. 694169689Skan 695169689Skan We accomplish this by creating duplicates of BB and arranging for 696169689Skan the duplicates to unconditionally pass control to one specific 697169689Skan successor of BB. We then revector the incoming edges into BB to 698169689Skan the appropriate duplicate of BB. 699169689Skan 700169689Skan BB and its duplicates will have assignments to the same set of 701169689Skan SSA_NAMEs. Right now, we just call into update_ssa to update the 702169689Skan SSA graph for those names. 703169689Skan 704169689Skan We are also going to experiment with a true incremental update 705169689Skan scheme for the duplicated resources. One of the interesting 706169689Skan properties we can exploit here is that all the resources set 707169689Skan in BB will have the same IDFS, so we have one IDFS computation 708169689Skan per block with incoming threaded edges, which can lower the 709169689Skan cost of the true incremental update algorithm. */ 710169689Skan 711169689Skanstatic bool 712169689Skanthread_block (basic_block bb) 713169689Skan{ 714169689Skan /* E is an incoming edge into BB that we may or may not want to 715169689Skan redirect to a duplicate of BB. */ 716169689Skan edge e; 717169689Skan edge_iterator ei; 718169689Skan struct local_info local_info; 719169689Skan 720169689Skan /* FOUND_BACKEDGE indicates that we found an incoming backedge 721169689Skan into BB, in which case we may ignore certain jump threads 722169689Skan to avoid creating irreducible regions. */ 723169689Skan bool found_backedge = false; 724169689Skan 725169689Skan /* ALL indicates whether or not all incoming edges into BB should 726169689Skan be threaded to a duplicate of BB. */ 727169689Skan bool all = true; 728169689Skan 729169689Skan /* If optimizing for size, only thread this block if we don't have 730169689Skan to duplicate it or it's an otherwise empty redirection block. */ 731169689Skan if (optimize_size 732169689Skan && EDGE_COUNT (bb->preds) > 1 733169689Skan && !redirection_block_p (bb)) 734169689Skan { 735169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 736169689Skan e->aux = NULL; 737169689Skan return false; 738169689Skan } 739169689Skan 740169689Skan /* To avoid scanning a linear array for the element we need we instead 741169689Skan use a hash table. For normal code there should be no noticeable 742169689Skan difference. However, if we have a block with a large number of 743169689Skan incoming and outgoing edges such linear searches can get expensive. */ 744169689Skan redirection_data = htab_create (EDGE_COUNT (bb->succs), 745169689Skan redirection_data_hash, 746169689Skan redirection_data_eq, 747169689Skan free); 748169689Skan 749169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 750169689Skan found_backedge |= ((e->flags & EDGE_DFS_BACK) != 0); 751169689Skan 752169689Skan /* If BB has incoming backedges, then threading across BB might 753169689Skan introduce an irreducible region, which would be undesirable 754169689Skan as that inhibits various optimizations later. Prune away 755169689Skan any jump threading requests which we know will result in 756169689Skan an irreducible region. */ 757169689Skan if (found_backedge) 758169689Skan prune_undesirable_thread_requests (bb); 759169689Skan 760169689Skan /* Record each unique threaded destination into a hash table for 761169689Skan efficient lookups. */ 762169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 763169689Skan { 764169689Skan if (!e->aux) 765169689Skan { 766169689Skan all = false; 767169689Skan } 768169689Skan else 769169689Skan { 770169689Skan edge e2 = e->aux; 771169689Skan update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e), 772169689Skan e->count, e->aux); 773169689Skan 774169689Skan /* Insert the outgoing edge into the hash table if it is not 775169689Skan already in the hash table. */ 776169689Skan lookup_redirection_data (e2, e, INSERT); 777169689Skan } 778169689Skan } 779169689Skan 780169689Skan /* If we are going to thread all incoming edges to an outgoing edge, then 781169689Skan BB will become unreachable. Rather than just throwing it away, use 782169689Skan it for one of the duplicates. Mark the first incoming edge with the 783169689Skan DO_NOT_DUPLICATE attribute. */ 784169689Skan if (all) 785169689Skan { 786169689Skan edge e = EDGE_PRED (bb, 0)->aux; 787169689Skan lookup_redirection_data (e, NULL, NO_INSERT)->do_not_duplicate = true; 788169689Skan } 789169689Skan 790169689Skan /* Now create duplicates of BB. 791169689Skan 792169689Skan Note that for a block with a high outgoing degree we can waste 793169689Skan a lot of time and memory creating and destroying useless edges. 794169689Skan 795169689Skan So we first duplicate BB and remove the control structure at the 796169689Skan tail of the duplicate as well as all outgoing edges from the 797169689Skan duplicate. We then use that duplicate block as a template for 798169689Skan the rest of the duplicates. */ 799169689Skan local_info.template_block = NULL; 800169689Skan local_info.bb = bb; 801169689Skan local_info.jumps_threaded = false; 802169689Skan htab_traverse (redirection_data, create_duplicates, &local_info); 803169689Skan 804169689Skan /* The template does not have an outgoing edge. Create that outgoing 805169689Skan edge and update PHI nodes as the edge's target as necessary. 806169689Skan 807169689Skan We do this after creating all the duplicates to avoid creating 808169689Skan unnecessary edges. */ 809169689Skan htab_traverse (redirection_data, fixup_template_block, &local_info); 810169689Skan 811169689Skan /* The hash table traversals above created the duplicate blocks (and the 812169689Skan statements within the duplicate blocks). This loop creates PHI nodes for 813169689Skan the duplicated blocks and redirects the incoming edges into BB to reach 814169689Skan the duplicates of BB. */ 815169689Skan htab_traverse (redirection_data, redirect_edges, &local_info); 816169689Skan 817169689Skan /* Done with this block. Clear REDIRECTION_DATA. */ 818169689Skan htab_delete (redirection_data); 819169689Skan redirection_data = NULL; 820169689Skan 821169689Skan /* Indicate to our caller whether or not any jumps were threaded. */ 822169689Skan return local_info.jumps_threaded; 823169689Skan} 824169689Skan 825169689Skan/* Walk through the registered jump threads and convert them into a 826169689Skan form convenient for this pass. 827169689Skan 828169689Skan Any block which has incoming edges threaded to outgoing edges 829169689Skan will have its entry in THREADED_BLOCK set. 830169689Skan 831169689Skan Any threaded edge will have its new outgoing edge stored in the 832169689Skan original edge's AUX field. 833169689Skan 834169689Skan This form avoids the need to walk all the edges in the CFG to 835169689Skan discover blocks which need processing and avoids unnecessary 836169689Skan hash table lookups to map from threaded edge to new target. */ 837169689Skan 838169689Skanstatic void 839169689Skanmark_threaded_blocks (bitmap threaded_blocks) 840169689Skan{ 841169689Skan unsigned int i; 842169689Skan 843169689Skan for (i = 0; i < VEC_length (edge, threaded_edges); i += 2) 844169689Skan { 845169689Skan edge e = VEC_index (edge, threaded_edges, i); 846169689Skan edge e2 = VEC_index (edge, threaded_edges, i + 1); 847169689Skan 848169689Skan e->aux = e2; 849169689Skan bitmap_set_bit (threaded_blocks, e->dest->index); 850169689Skan } 851169689Skan} 852169689Skan 853169689Skan 854169689Skan/* Walk through all blocks and thread incoming edges to the appropriate 855169689Skan outgoing edge for each edge pair recorded in THREADED_EDGES. 856169689Skan 857169689Skan It is the caller's responsibility to fix the dominance information 858169689Skan and rewrite duplicated SSA_NAMEs back into SSA form. 859169689Skan 860169689Skan Returns true if one or more edges were threaded, false otherwise. */ 861169689Skan 862169689Skanbool 863169689Skanthread_through_all_blocks (void) 864169689Skan{ 865169689Skan bool retval = false; 866169689Skan unsigned int i; 867169689Skan bitmap_iterator bi; 868169689Skan bitmap threaded_blocks; 869169689Skan 870169689Skan if (threaded_edges == NULL) 871169689Skan return false; 872169689Skan 873169689Skan threaded_blocks = BITMAP_ALLOC (NULL); 874169689Skan memset (&thread_stats, 0, sizeof (thread_stats)); 875169689Skan 876169689Skan mark_threaded_blocks (threaded_blocks); 877169689Skan 878169689Skan EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi) 879169689Skan { 880169689Skan basic_block bb = BASIC_BLOCK (i); 881169689Skan 882169689Skan if (EDGE_COUNT (bb->preds) > 0) 883169689Skan retval |= thread_block (bb); 884169689Skan } 885169689Skan 886169689Skan if (dump_file && (dump_flags & TDF_STATS)) 887169689Skan fprintf (dump_file, "\nJumps threaded: %lu\n", 888169689Skan thread_stats.num_threaded_edges); 889169689Skan 890169689Skan BITMAP_FREE (threaded_blocks); 891169689Skan threaded_blocks = NULL; 892169689Skan VEC_free (edge, heap, threaded_edges); 893169689Skan threaded_edges = NULL; 894169689Skan return retval; 895169689Skan} 896169689Skan 897169689Skan/* Register a jump threading opportunity. We queue up all the jump 898169689Skan threading opportunities discovered by a pass and update the CFG 899169689Skan and SSA form all at once. 900169689Skan 901169689Skan E is the edge we can thread, E2 is the new target edge. ie, we 902169689Skan are effectively recording that E->dest can be changed to E2->dest 903169689Skan after fixing the SSA graph. */ 904169689Skan 905169689Skanvoid 906169689Skanregister_jump_thread (edge e, edge e2) 907169689Skan{ 908169689Skan if (threaded_edges == NULL) 909169689Skan threaded_edges = VEC_alloc (edge, heap, 10); 910169689Skan 911169689Skan VEC_safe_push (edge, heap, threaded_edges, e); 912169689Skan VEC_safe_push (edge, heap, threaded_edges, e2); 913169689Skan} 914169689Skan