11590Srgrimes/* Generic partial redundancy elimination with lazy code motion support. 21590Srgrimes Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008 31590Srgrimes Free Software Foundation, Inc. 41590Srgrimes 51590SrgrimesThis file is part of GCC. 61590Srgrimes 71590SrgrimesGCC is free software; you can redistribute it and/or modify it under 81590Srgrimesthe terms of the GNU General Public License as published by the Free 91590SrgrimesSoftware Foundation; either version 3, or (at your option) any later 101590Srgrimesversion. 111590Srgrimes 121590SrgrimesGCC is distributed in the hope that it will be useful, but WITHOUT ANY 131590SrgrimesWARRANTY; without even the implied warranty of MERCHANTABILITY or 141590SrgrimesFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 151590Srgrimesfor more details. 161590Srgrimes 171590SrgrimesYou should have received a copy of the GNU General Public License 181590Srgrimesalong with GCC; see the file COPYING3. If not see 191590Srgrimes<http://www.gnu.org/licenses/>. */ 201590Srgrimes 211590Srgrimes/* These routines are meant to be used by various optimization 221590Srgrimes passes which can be modeled as lazy code motion problems. 231590Srgrimes Including, but not limited to: 241590Srgrimes 251590Srgrimes * Traditional partial redundancy elimination. 261590Srgrimes 271590Srgrimes * Placement of caller/caller register save/restores. 281590Srgrimes 291590Srgrimes * Load/store motion. 301590Srgrimes 311590Srgrimes * Copy motion. 321590Srgrimes 331590Srgrimes * Conversion of flat register files to a stacked register 341590Srgrimes model. 3527272Scharnier 361590Srgrimes * Dead load/store elimination. 371590Srgrimes 381590Srgrimes These routines accept as input: 391590Srgrimes 401590Srgrimes * Basic block information (number of blocks, lists of 4127272Scharnier predecessors and successors). Note the granularity 4223693Speter does not need to be basic block, they could be statements 4327272Scharnier or functions. 441590Srgrimes 4599112Sobrien * Bitmaps of local properties (computed, transparent and 4699112Sobrien anticipatable expressions). 471590Srgrimes 481590Srgrimes The output of these routines is bitmap of redundant computations 491590Srgrimes and a bitmap of optimal placement points. */ 501590Srgrimes 511590Srgrimes 521590Srgrimes#include "config.h" 531590Srgrimes#include "system.h" 541590Srgrimes#include "coretypes.h" 551590Srgrimes#include "tm.h" 561590Srgrimes#include "rtl.h" 571590Srgrimes#include "regs.h" 5836110Smarkm#include "hard-reg-set.h" 591590Srgrimes#include "flags.h" 601590Srgrimes#include "real.h" 611590Srgrimes#include "insn-config.h" 627726Sdg#include "recog.h" 63132477Ssilby#include "basic-block.h" 6417808Speter#include "output.h" 6553133Sgreen#include "tm_p.h" 661590Srgrimes#include "function.h" 67101872Sbmilekic 681590Srgrimes/* We want target macros for the mode switching code to be able to refer 691590Srgrimes to instruction attribute values. */ 7088051Sgreen#include "insn-attr.h" 7155206Speter 729336Sdfr/* Edge based LCM routines. */ 731590Srgrimesstatic void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *); 7483653Speterstatic void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *, 7583653Speter sbitmap *, sbitmap *, sbitmap *); 761590Srgrimesstatic void compute_laterin (struct edge_list *, sbitmap *, sbitmap *, 7758125Sgreen sbitmap *, sbitmap *); 7859029Sgreenstatic void compute_insert_delete (struct edge_list *edge_list, sbitmap *, 7959029Sgreen sbitmap *, sbitmap *, sbitmap *, sbitmap *); 8059029Sgreen 8159029Sgreen/* Edge based LCM routines on a reverse flowgraph. */ 821590Srgrimesstatic void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *, 831590Srgrimes sbitmap*, sbitmap *, sbitmap *); 841590Srgrimesstatic void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *, 851590Srgrimes sbitmap *, sbitmap *); 861590Srgrimesstatic void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *, 871590Srgrimes sbitmap *, sbitmap *, sbitmap *, 881590Srgrimes sbitmap *); 8927272Scharnier 9018570Sbde/* Edge based lcm routines. */ 911590Srgrimes 9223693Speter/* Compute expression anticipatability at entrance and exit of each block. 931590Srgrimes This is done based on the flow graph, and not on the pred-succ lists. 941590Srgrimes Other than that, its pretty much identical to compute_antinout. */ 951590Srgrimes 961590Srgrimesstatic void 971590Srgrimescompute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin, 981590Srgrimes sbitmap *antout) 9923693Speter{ 10048463Sru basic_block bb; 1011590Srgrimes edge e; 10258125Sgreen basic_block *worklist, *qin, *qout, *qend; 10358125Sgreen unsigned int qlen; 1041590Srgrimes edge_iterator ei; 1051590Srgrimes 1061590Srgrimes /* Allocate a worklist array/queue. Entries are only added to the 1071590Srgrimes list if they were not already on the list. So the size is 10859029Sgreen bounded by the number of basic blocks. */ 109140958Sphk qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks); 1101590Srgrimes 1111590Srgrimes /* We want a maximal solution, so make an optimistic initialization of 1121590Srgrimes ANTIN. */ 1131590Srgrimes sbitmap_vector_ones (antin, last_basic_block); 1141590Srgrimes 1151590Srgrimes /* Put every block on the worklist; this is necessary because of the 1161590Srgrimes optimistic initialization of ANTIN above. */ 1171590Srgrimes FOR_EACH_BB_REVERSE (bb) 1181590Srgrimes { 1191590Srgrimes *qin++ = bb; 1201590Srgrimes bb->aux = bb; 1211590Srgrimes } 1221590Srgrimes 1231590Srgrimes qin = worklist; 1241590Srgrimes qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; 12559029Sgreen qlen = n_basic_blocks - NUM_FIXED_BLOCKS; 1261590Srgrimes 1271590Srgrimes /* Mark blocks which are predecessors of the exit block so that we 1281590Srgrimes can easily identify them below. */ 1291590Srgrimes FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 1301590Srgrimes e->src->aux = EXIT_BLOCK_PTR; 1311590Srgrimes 1321590Srgrimes /* Iterate until the worklist is empty. */ 1331590Srgrimes while (qlen) 1341590Srgrimes { 13527272Scharnier /* Take the first entry off the worklist. */ 1361590Srgrimes bb = *qout++; 1371590Srgrimes qlen--; 1381590Srgrimes 1391590Srgrimes if (qout >= qend) 14097946Sdes qout = worklist; 1411590Srgrimes 1421590Srgrimes if (bb->aux == EXIT_BLOCK_PTR) 14397946Sdes /* Do not clear the aux field for blocks which are predecessors of 14497946Sdes the EXIT block. That way we never add then to the worklist 14592920Simp again. */ 14692920Simp sbitmap_zero (antout[bb->index]); 14792920Simp else 14892920Simp { 14992920Simp /* Clear the aux field of this block so that it can be added to 15092920Simp the worklist again if necessary. */ 15192920Simp bb->aux = NULL; 15292920Simp sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index); 15392920Simp } 15492920Simp 15593427Sdwmalone if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index], 15692920Simp transp[bb->index], antout[bb->index])) 1571590Srgrimes /* If the in state of this block changed, then we need 15817808Speter to add the predecessors of this block to the worklist 15917808Speter if they are not already on the worklist. */ 160131293Sdwmalone FOR_EACH_EDGE (e, ei, bb->preds) 1611590Srgrimes if (!e->src->aux && e->src != ENTRY_BLOCK_PTR) 16293427Sdwmalone { 1631590Srgrimes *qin++ = e->src; 1641590Srgrimes e->src->aux = e; 1651590Srgrimes qlen++; 1661590Srgrimes if (qin >= qend) 1671590Srgrimes qin = worklist; 16859029Sgreen } 1691590Srgrimes } 1701590Srgrimes 1711590Srgrimes clear_aux_for_edges (); 1721590Srgrimes clear_aux_for_blocks (); 1731590Srgrimes free (worklist); 1741590Srgrimes} 1751590Srgrimes 1761590Srgrimes/* Compute the earliest vector for edge based lcm. */ 1771590Srgrimes 1781590Srgrimesstatic void 17959029Sgreencompute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin, 18059029Sgreen sbitmap *antout, sbitmap *avout, sbitmap *kill, 18159029Sgreen sbitmap *earliest) 1821590Srgrimes{ 1831590Srgrimes sbitmap difference, temp_bitmap; 1841590Srgrimes int x, num_edges; 1851590Srgrimes basic_block pred, succ; 1861590Srgrimes 1871590Srgrimes num_edges = NUM_EDGES (edge_list); 1881590Srgrimes 18927311Scharnier difference = sbitmap_alloc (n_exprs); 1901590Srgrimes temp_bitmap = sbitmap_alloc (n_exprs); 1911590Srgrimes 1921590Srgrimes for (x = 0; x < num_edges; x++) 1931590Srgrimes { 1941590Srgrimes pred = INDEX_EDGE_PRED_BB (edge_list, x); 1951590Srgrimes succ = INDEX_EDGE_SUCC_BB (edge_list, x); 1961590Srgrimes if (pred == ENTRY_BLOCK_PTR) 1971590Srgrimes sbitmap_copy (earliest[x], antin[succ->index]); 19827272Scharnier else 19927272Scharnier { 2001590Srgrimes if (succ == EXIT_BLOCK_PTR) 2011590Srgrimes sbitmap_zero (earliest[x]); 2021590Srgrimes else 2031590Srgrimes { 2041590Srgrimes sbitmap_difference (difference, antin[succ->index], 2051590Srgrimes avout[pred->index]); 2061590Srgrimes sbitmap_not (temp_bitmap, antout[pred->index]); 2071590Srgrimes sbitmap_a_and_b_or_c (earliest[x], difference, 2081590Srgrimes kill[pred->index], temp_bitmap); 2091590Srgrimes } 2101590Srgrimes } 2111590Srgrimes } 2121590Srgrimes 2131590Srgrimes sbitmap_free (temp_bitmap); 2141590Srgrimes sbitmap_free (difference); 2151590Srgrimes} 2161590Srgrimes 2171590Srgrimes/* later(p,s) is dependent on the calculation of laterin(p). 2181590Srgrimes laterin(p) is dependent on the calculation of later(p2,p). 2191590Srgrimes 2208874Srgrimes laterin(ENTRY) is defined as all 0's 2211590Srgrimes later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY) 2221590Srgrimes laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)). 2231590Srgrimes 2241590Srgrimes If we progress in this manner, starting with all basic blocks 2251590Srgrimes in the work list, anytime we change later(bb), we need to add 2261590Srgrimes succs(bb) to the worklist if they are not already on the worklist. 22797946Sdes 22897946Sdes Boundary conditions: 22997946Sdes 23097946Sdes We prime the worklist all the normal basic blocks. The ENTRY block can 23197946Sdes never be added to the worklist since it is never the successor of any 23297946Sdes block. We explicitly prevent the EXIT block from being added to the 23397946Sdes worklist. 23497946Sdes 23597946Sdes We optimistically initialize LATER. That is the only time this routine 23697946Sdes will compute LATER for an edge out of the entry block since the entry 23797946Sdes block is never on the worklist. Thus, LATERIN is neither used nor 23897946Sdes computed for the ENTRY block. 23997946Sdes 24097946Sdes Since the EXIT block is never added to the worklist, we will neither 24197946Sdes use nor compute LATERIN for the exit block. Edges which reach the 24297946Sdes EXIT block are handled in the normal fashion inside the loop. However, 24397946Sdes the insertion/deletion computation needs LATERIN(EXIT), so we have 24497946Sdes to compute it. */ 24597946Sdes 24697946Sdesstatic void 24797946Sdescompute_laterin (struct edge_list *edge_list, sbitmap *earliest, 24897946Sdes sbitmap *antloc, sbitmap *later, sbitmap *laterin) 24997946Sdes{ 25097946Sdes int num_edges, i; 25197946Sdes edge e; 25297946Sdes basic_block *worklist, *qin, *qout, *qend, bb; 25397946Sdes unsigned int qlen; 25497946Sdes edge_iterator ei; 25597946Sdes 25697946Sdes num_edges = NUM_EDGES (edge_list); 25797946Sdes 25897946Sdes /* Allocate a worklist array/queue. Entries are only added to the 2591590Srgrimes list if they were not already on the list. So the size is 2601590Srgrimes bounded by the number of basic blocks. */ 2611590Srgrimes qin = qout = worklist 2621590Srgrimes = XNEWVEC (basic_block, n_basic_blocks); 2631590Srgrimes 2641590Srgrimes /* Initialize a mapping from each edge to its index. */ 2651590Srgrimes for (i = 0; i < num_edges; i++) 26627272Scharnier INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; 26727272Scharnier 26882664Sru /* We want a maximal solution, so initially consider LATER true for 2691590Srgrimes all edges. This allows propagation through a loop since the incoming 27027272Scharnier loop edge will have LATER set, so if all the other incoming edges 27127272Scharnier to the loop are set, then LATERIN will be set for the head of the 2721590Srgrimes loop. 27327272Scharnier 27427272Scharnier If the optimistic setting of LATER on that edge was incorrect (for 275116717Smaxim example the expression is ANTLOC in a block within the loop) then 2761590Srgrimes this algorithm will detect it when we process the block at the head 27769896Smckusick of the optimistic edge. That will requeue the affected blocks. */ 2781590Srgrimes sbitmap_vector_ones (later, num_edges); 2791590Srgrimes 28059029Sgreen /* Note that even though we want an optimistic setting of LATER, we 28159029Sgreen do not want to be overly optimistic. Consider an outgoing edge from 2821590Srgrimes the entry block. That edge should always have a LATER value the 2831590Srgrimes same as EARLIEST for that edge. */ 2841590Srgrimes FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 28597946Sdes sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]); 28697946Sdes 28797946Sdes /* Add all the blocks to the worklist. This prevents an early exit from 28897946Sdes the loop given our optimistic initialization of LATER above. */ 28997946Sdes FOR_EACH_BB (bb) 29097946Sdes { 29197946Sdes *qin++ = bb; 29297946Sdes bb->aux = bb; 29393427Sdwmalone } 2941590Srgrimes 2951590Srgrimes /* Note that we do not use the last allocated element for our queue, 2961590Srgrimes as EXIT_BLOCK is never inserted into it. */ 2971590Srgrimes qin = worklist; 2981590Srgrimes qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; 2991590Srgrimes qlen = n_basic_blocks - NUM_FIXED_BLOCKS; 3001590Srgrimes 3011590Srgrimes /* Iterate until the worklist is empty. */ 3021590Srgrimes while (qlen) 3031590Srgrimes { 3041590Srgrimes /* Take the first entry off the worklist. */ 3051590Srgrimes bb = *qout++; 3061590Srgrimes bb->aux = NULL; 3071590Srgrimes qlen--; 3081590Srgrimes if (qout >= qend) 3091590Srgrimes qout = worklist; 31059029Sgreen 31159029Sgreen /* Compute the intersection of LATERIN for each incoming edge to B. */ 31259029Sgreen sbitmap_ones (laterin[bb->index]); 313140958Sphk FOR_EACH_EDGE (e, ei, bb->preds) 314140958Sphk sbitmap_a_and_b (laterin[bb->index], laterin[bb->index], 315140958Sphk later[(size_t)e->aux]); 3161590Srgrimes 3171590Srgrimes /* Calculate LATER for all outgoing edges. */ 3181590Srgrimes FOR_EACH_EDGE (e, ei, bb->succs) 3191590Srgrimes if (sbitmap_union_of_diff_cg (later[(size_t) e->aux], 3201590Srgrimes earliest[(size_t) e->aux], 3211590Srgrimes laterin[e->src->index], 3221590Srgrimes antloc[e->src->index]) 3231590Srgrimes /* If LATER for an outgoing edge was changed, then we need 3241590Srgrimes to add the target of the outgoing edge to the worklist. */ 325131293Sdwmalone && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0) 3261590Srgrimes { 32727272Scharnier *qin++ = e->dest; 3281590Srgrimes e->dest->aux = e; 329137352Sphk qlen++; 3301590Srgrimes if (qin >= qend) 33169896Smckusick qin = worklist; 33269896Smckusick } 33369896Smckusick } 3341590Srgrimes 33569896Smckusick /* Computation of insertion and deletion points requires computing LATERIN 3361590Srgrimes for the EXIT block. We allocated an extra entry in the LATERIN array 337137352Sphk for just this purpose. */ 33837453Sbde sbitmap_ones (laterin[last_basic_block]); 33969896Smckusick FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 3401590Srgrimes sbitmap_a_and_b (laterin[last_basic_block], 3411590Srgrimes laterin[last_basic_block], 3421590Srgrimes later[(size_t) e->aux]); 3431590Srgrimes 3441590Srgrimes clear_aux_for_edges (); 3451590Srgrimes free (worklist); 3461590Srgrimes} 3471590Srgrimes 3481590Srgrimes/* Compute the insertion and deletion points for edge based LCM. */ 3491590Srgrimes 3501590Srgrimesstatic void 3511590Srgrimescompute_insert_delete (struct edge_list *edge_list, sbitmap *antloc, 352140958Sphk sbitmap *later, sbitmap *laterin, sbitmap *insert, 353140958Sphk sbitmap *del) 354140958Sphk{ 355140958Sphk int x; 356140958Sphk basic_block bb; 3571590Srgrimes 3581590Srgrimes FOR_EACH_BB (bb) 35969896Smckusick sbitmap_difference (del[bb->index], antloc[bb->index], 36069896Smckusick laterin[bb->index]); 3611590Srgrimes 36217813Speter for (x = 0; x < NUM_EDGES (edge_list); x++) 36317813Speter { 36469896Smckusick basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x); 36569896Smckusick 36617813Speter if (b == EXIT_BLOCK_PTR) 3671590Srgrimes sbitmap_difference (insert[x], later[x], laterin[last_basic_block]); 3681590Srgrimes else 3691590Srgrimes sbitmap_difference (insert[x], later[x], laterin[b->index]); 370140958Sphk } 371140958Sphk} 372140958Sphk 373140958Sphk/* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and 374140958Sphk delete vectors for edge based LCM. Returns an edgelist which is used to 375140958Sphk map the insert vector to what edge an expression should be inserted on. */ 3761590Srgrimes 377137352Sphkstruct edge_list * 378137352Sphkpre_edge_lcm (int n_exprs, sbitmap *transp, 379137352Sphk sbitmap *avloc, sbitmap *antloc, sbitmap *kill, 380137352Sphk sbitmap **insert, sbitmap **del) 381137352Sphk{ 382137352Sphk sbitmap *antin, *antout, *earliest; 383137352Sphk sbitmap *avin, *avout; 3841590Srgrimes sbitmap *later, *laterin; 3851590Srgrimes struct edge_list *edge_list; 3861590Srgrimes int num_edges; 3871590Srgrimes 38837453Sbde edge_list = create_edge_list (); 38937453Sbde num_edges = NUM_EDGES (edge_list); 3901590Srgrimes 3911590Srgrimes#ifdef LCM_DEBUG_INFO 3921590Srgrimes if (dump_file) 393140078Sssouhlal { 3941590Srgrimes fprintf (dump_file, "Edge List:\n"); 3951590Srgrimes verify_edge_list (dump_file, edge_list); 396109153Sdillon print_edge_list (dump_file, edge_list); 3971590Srgrimes dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); 39817808Speter dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block); 39917808Speter dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block); 40017808Speter dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block); 401109153Sdillon } 40217808Speter#endif 40317808Speter 40478401Sroam /* Compute global availability. */ 40578401Sroam avin = sbitmap_vector_alloc (last_basic_block, n_exprs); 40678401Sroam avout = sbitmap_vector_alloc (last_basic_block, n_exprs); 407140078Sssouhlal compute_available (avloc, kill, avout, avin); 40878401Sroam sbitmap_vector_free (avin); 40978401Sroam 4101590Srgrimes /* Compute global anticipatability. */ 4118874Srgrimes antin = sbitmap_vector_alloc (last_basic_block, n_exprs); 41278401Sroam antout = sbitmap_vector_alloc (last_basic_block, n_exprs); 41378401Sroam compute_antinout_edge (antloc, transp, antin, antout); 4141590Srgrimes 4151590Srgrimes#ifdef LCM_DEBUG_INFO 4161590Srgrimes if (dump_file) 4171590Srgrimes { 4181590Srgrimes dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block); 419131293Sdwmalone dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block); 42059029Sgreen } 42169896Smckusick#endif 42259029Sgreen 42359029Sgreen /* Compute earliestness. */ 42459029Sgreen earliest = sbitmap_vector_alloc (num_edges, n_exprs); 42559029Sgreen compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest); 42659029Sgreen 42759029Sgreen#ifdef LCM_DEBUG_INFO 42859029Sgreen if (dump_file) 42969896Smckusick dump_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges); 43069896Smckusick#endif 43169896Smckusick 43269896Smckusick sbitmap_vector_free (antout); 43359029Sgreen sbitmap_vector_free (antin); 43459029Sgreen sbitmap_vector_free (avout); 43559029Sgreen 43659029Sgreen later = sbitmap_vector_alloc (num_edges, n_exprs); 43772527Siedowse 43872527Siedowse /* Allocate an extra element for the exit block in the laterin vector. */ 43959029Sgreen laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); 44059029Sgreen compute_laterin (edge_list, earliest, antloc, later, laterin); 44159029Sgreen 44259029Sgreen#ifdef LCM_DEBUG_INFO 44359029Sgreen if (dump_file) 44459029Sgreen { 44559029Sgreen dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1); 44659029Sgreen dump_sbitmap_vector (dump_file, "later", "", later, num_edges); 44759029Sgreen } 44859029Sgreen#endif 44959029Sgreen 45059029Sgreen sbitmap_vector_free (earliest); 45159029Sgreen 45259029Sgreen *insert = sbitmap_vector_alloc (num_edges, n_exprs); 45359029Sgreen *del = sbitmap_vector_alloc (last_basic_block, n_exprs); 45459029Sgreen compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del); 45559029Sgreen 45659029Sgreen sbitmap_vector_free (laterin); 45759029Sgreen sbitmap_vector_free (later); 45859029Sgreen 45959029Sgreen#ifdef LCM_DEBUG_INFO 46059029Sgreen if (dump_file) 46159029Sgreen { 46259029Sgreen dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); 46359029Sgreen dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del, 46459029Sgreen last_basic_block); 46559029Sgreen } 46659029Sgreen#endif 46759029Sgreen 46859029Sgreen return edge_list; 46959029Sgreen} 47059029Sgreen 47159029Sgreen/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. 47259029Sgreen Return the number of passes we performed to iterate to a solution. */ 47359029Sgreen 47459029Sgreenvoid 47559029Sgreencompute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout, 476131293Sdwmalone sbitmap *avin) 4771590Srgrimes{ 4781590Srgrimes edge e; 4791590Srgrimes basic_block *worklist, *qin, *qout, *qend, bb; 480103325Snjl unsigned int qlen; 48193427Sdwmalone edge_iterator ei; 4821590Srgrimes 4831590Srgrimes /* Allocate a worklist array/queue. Entries are only added to the 4841590Srgrimes list if they were not already on the list. So the size is 48537453Sbde bounded by the number of basic blocks. */ 48637453Sbde qin = qout = worklist = 4871590Srgrimes XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS); 4881590Srgrimes 489103325Snjl /* We want a maximal solution. */ 490103325Snjl sbitmap_vector_ones (avout, last_basic_block); 491103325Snjl 492103325Snjl /* Put every block on the worklist; this is necessary because of the 493103325Snjl optimistic initialization of AVOUT above. */ 494103325Snjl FOR_EACH_BB (bb) 495103325Snjl { 496103325Snjl *qin++ = bb; 4971590Srgrimes bb->aux = bb; 4981590Srgrimes } 4991590Srgrimes 500103325Snjl qin = worklist; 501103325Snjl qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; 5021590Srgrimes qlen = n_basic_blocks - NUM_FIXED_BLOCKS; 5031590Srgrimes 504103325Snjl /* Mark blocks which are successors of the entry block so that we 50588051Sgreen can easily identify them below. */ 50688051Sgreen FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 507103325Snjl e->dest->aux = ENTRY_BLOCK_PTR; 5081590Srgrimes 5091590Srgrimes /* Iterate until the worklist is empty. */ 510103325Snjl while (qlen) 51158125Sgreen { 51258125Sgreen /* Take the first entry off the worklist. */ 513103325Snjl bb = *qout++; 51458125Sgreen qlen--; 51558125Sgreen 516103325Snjl if (qout >= qend) 517103325Snjl qout = worklist; 518103325Snjl 51993427Sdwmalone /* If one of the predecessor blocks is the ENTRY block, then the 5201590Srgrimes intersection of avouts is the null set. We can identify such blocks 5211590Srgrimes by the special value in the AUX field in the block structure. */ 5221590Srgrimes if (bb->aux == ENTRY_BLOCK_PTR) 5231590Srgrimes /* Do not clear the aux field for blocks which are successors of the 52493427Sdwmalone ENTRY block. That way we never add then to the worklist again. */ 5251590Srgrimes sbitmap_zero (avin[bb->index]); 5261590Srgrimes else 5271590Srgrimes { 5281590Srgrimes /* Clear the aux field of this block so that it can be added to 5291590Srgrimes the worklist again if necessary. */ 5301590Srgrimes bb->aux = NULL; 5311590Srgrimes sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index); 5321590Srgrimes } 5331590Srgrimes 5341590Srgrimes if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index], 5351590Srgrimes avin[bb->index], kill[bb->index])) 5361590Srgrimes /* If the out state of this block changed, then we need 5371590Srgrimes to add the successors of this block to the worklist 5381590Srgrimes if they are not already on the worklist. */ 5391590Srgrimes FOR_EACH_EDGE (e, ei, bb->succs) 5401590Srgrimes if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR) 5411590Srgrimes { 5421590Srgrimes *qin++ = e->dest; 5431590Srgrimes e->dest->aux = e; 5441590Srgrimes qlen++; 5451590Srgrimes 5461590Srgrimes if (qin >= qend) 5471590Srgrimes qin = worklist; 5481590Srgrimes } 5491590Srgrimes } 5501590Srgrimes 5511590Srgrimes clear_aux_for_edges (); 55237453Sbde clear_aux_for_blocks (); 5531590Srgrimes free (worklist); 5541590Srgrimes} 5551590Srgrimes 5561590Srgrimes/* Compute the farthest vector for edge based lcm. */ 5571590Srgrimes 5588874Srgrimesstatic void 5591590Srgrimescompute_farthest (struct edge_list *edge_list, int n_exprs, 5601590Srgrimes sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin, 5611590Srgrimes sbitmap *kill, sbitmap *farthest) 5621590Srgrimes{ 5631590Srgrimes sbitmap difference, temp_bitmap; 5641590Srgrimes int x, num_edges; 5651590Srgrimes basic_block pred, succ; 56628948Salex 5671590Srgrimes num_edges = NUM_EDGES (edge_list); 5681590Srgrimes 5691590Srgrimes difference = sbitmap_alloc (n_exprs); 5701590Srgrimes temp_bitmap = sbitmap_alloc (n_exprs); 5711590Srgrimes 5721590Srgrimes for (x = 0; x < num_edges; x++) 5731590Srgrimes { 5741590Srgrimes pred = INDEX_EDGE_PRED_BB (edge_list, x); 5751590Srgrimes succ = INDEX_EDGE_SUCC_BB (edge_list, x); 5761590Srgrimes if (succ == EXIT_BLOCK_PTR) 5771590Srgrimes sbitmap_copy (farthest[x], st_avout[pred->index]); 5781590Srgrimes else 5791590Srgrimes { 580131293Sdwmalone if (pred == ENTRY_BLOCK_PTR) 5811590Srgrimes sbitmap_zero (farthest[x]); 5821590Srgrimes else 5831590Srgrimes { 5841590Srgrimes sbitmap_difference (difference, st_avout[pred->index], 58537453Sbde st_antin[succ->index]); 58637453Sbde sbitmap_not (temp_bitmap, st_avin[succ->index]); 5871590Srgrimes sbitmap_a_and_b_or_c (farthest[x], difference, 5881590Srgrimes kill[succ->index], temp_bitmap); 58953133Sgreen } 590130640Sphk } 591130640Sphk } 59253133Sgreen 59353133Sgreen sbitmap_free (temp_bitmap); 59486100Sdwmalone sbitmap_free (difference); 5951590Srgrimes} 5961590Srgrimes 5971590Srgrimes/* Compute nearer and nearerout vectors for edge based lcm. 59898542Smckusick 599116780Sjmg This is the mirror of compute_laterin, additional comments on the 600116780Sjmg implementation can be found before compute_laterin. */ 601116780Sjmg 602116780Sjmgstatic void 603116780Sjmgcompute_nearerout (struct edge_list *edge_list, sbitmap *farthest, 60498542Smckusick sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout) 60598542Smckusick{ 60698542Smckusick int num_edges, i; 6071590Srgrimes edge e; 6081590Srgrimes basic_block *worklist, *tos, bb; 6091590Srgrimes edge_iterator ei; 6101590Srgrimes 6111590Srgrimes num_edges = NUM_EDGES (edge_list); 612131293Sdwmalone 61388051Sgreen /* Allocate a worklist array/queue. Entries are only added to the 61488051Sgreen list if they were not already on the list. So the size is 61588051Sgreen bounded by the number of basic blocks. */ 61688051Sgreen tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1); 61788051Sgreen 61888051Sgreen /* Initialize NEARER for each edge and build a mapping from an edge to 61988051Sgreen its index. */ 62088051Sgreen for (i = 0; i < num_edges; i++) 62188051Sgreen INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; 62288051Sgreen 62388051Sgreen /* We want a maximal solution. */ 62488051Sgreen sbitmap_vector_ones (nearer, num_edges); 62588051Sgreen 62688051Sgreen /* Note that even though we want an optimistic setting of NEARER, we 62788051Sgreen do not want to be overly optimistic. Consider an incoming edge to 62888051Sgreen the exit block. That edge should always have a NEARER value the 62988051Sgreen same as FARTHEST for that edge. */ 63088051Sgreen FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 63188051Sgreen sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]); 63288051Sgreen 63388051Sgreen /* Add all the blocks to the worklist. This prevents an early exit 63488051Sgreen from the loop given our optimistic initialization of NEARER. */ 63588051Sgreen FOR_EACH_BB (bb) 63688051Sgreen { 637116556Sjmg *tos++ = bb; 63888051Sgreen bb->aux = bb; 63988051Sgreen } 64088051Sgreen 64188051Sgreen /* Iterate until the worklist is empty. */ 64288051Sgreen while (tos != worklist) 643131293Sdwmalone { 6441590Srgrimes /* Take the first entry off the worklist. */ 6451590Srgrimes bb = *--tos; 64693427Sdwmalone bb->aux = NULL; 6471590Srgrimes 6481590Srgrimes /* Compute the intersection of NEARER for each outgoing edge from B. */ 64937453Sbde sbitmap_ones (nearerout[bb->index]); 65037453Sbde FOR_EACH_EDGE (e, ei, bb->succs) 6511590Srgrimes sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index], 6521590Srgrimes nearer[(size_t) e->aux]); 6531590Srgrimes 6541590Srgrimes /* Calculate NEARER for all incoming edges. */ 6551590Srgrimes FOR_EACH_EDGE (e, ei, bb->preds) 6561590Srgrimes if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux], 6571590Srgrimes farthest[(size_t) e->aux], 6581590Srgrimes nearerout[e->dest->index], 6591590Srgrimes st_avloc[e->dest->index]) 6601590Srgrimes /* If NEARER for an incoming edge was changed, then we need 6611590Srgrimes to add the source of the incoming edge to the worklist. */ 6621590Srgrimes && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0) 6631590Srgrimes { 6641590Srgrimes *tos++ = e->src; 6651590Srgrimes e->src->aux = e; 6661590Srgrimes } 6671590Srgrimes } 6681590Srgrimes 6691590Srgrimes /* Computation of insertion and deletion points requires computing NEAREROUT 6701590Srgrimes for the ENTRY block. We allocated an extra entry in the NEAREROUT array 6711590Srgrimes for just this purpose. */ 6721590Srgrimes sbitmap_ones (nearerout[last_basic_block]); 6731590Srgrimes FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 6741590Srgrimes sbitmap_a_and_b (nearerout[last_basic_block], 6751590Srgrimes nearerout[last_basic_block], 6761590Srgrimes nearer[(size_t) e->aux]); 6771590Srgrimes 6781590Srgrimes clear_aux_for_edges (); 6791590Srgrimes free (tos); 68048463Sru} 68148463Sru 68248463Sru/* Compute the insertion and deletion points for edge based LCM. */ 6831590Srgrimes 6841590Srgrimesstatic void 6851590Srgrimescompute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc, 6861590Srgrimes sbitmap *nearer, sbitmap *nearerout, 6871590Srgrimes sbitmap *insert, sbitmap *del) 6881590Srgrimes{ 6891590Srgrimes int x; 6901590Srgrimes basic_block bb; 691131293Sdwmalone 6921590Srgrimes FOR_EACH_BB (bb) 6931590Srgrimes sbitmap_difference (del[bb->index], st_avloc[bb->index], 6941590Srgrimes nearerout[bb->index]); 6951590Srgrimes 6961590Srgrimes for (x = 0; x < NUM_EDGES (edge_list); x++) 6971590Srgrimes { 6981590Srgrimes basic_block b = INDEX_EDGE_PRED_BB (edge_list, x); 69993427Sdwmalone if (b == ENTRY_BLOCK_PTR) 7001590Srgrimes sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]); 7011590Srgrimes else 7021590Srgrimes sbitmap_difference (insert[x], nearer[x], nearerout[b->index]); 7031590Srgrimes } 7041590Srgrimes} 70537453Sbde 7061590Srgrimes/* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the 7071590Srgrimes insert and delete vectors for edge based reverse LCM. Returns an 70827272Scharnier edgelist which is used to map the insert vector to what edge 70927272Scharnier an expression should be inserted on. */ 7101590Srgrimes 7111590Srgrimesstruct edge_list * 7121590Srgrimespre_edge_rev_lcm (int n_exprs, sbitmap *transp, 7131590Srgrimes sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill, 7141590Srgrimes sbitmap **insert, sbitmap **del) 7151590Srgrimes{ 7161590Srgrimes sbitmap *st_antin, *st_antout; 7171590Srgrimes sbitmap *st_avout, *st_avin, *farthest; 718131293Sdwmalone sbitmap *nearer, *nearerout; 71917808Speter struct edge_list *edge_list; 72017808Speter int num_edges; 72117808Speter 72217808Speter edge_list = create_edge_list (); 72317808Speter num_edges = NUM_EDGES (edge_list); 72417808Speter 72517808Speter st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs); 72617808Speter st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs); 72737453Sbde sbitmap_vector_zero (st_antin, last_basic_block); 72817808Speter sbitmap_vector_zero (st_antout, last_basic_block); 72917808Speter compute_antinout_edge (st_antloc, transp, st_antin, st_antout); 73017808Speter 73180355Smjacob /* Compute global anticipatability. */ 73217808Speter st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs); 73317808Speter st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs); 73417808Speter compute_available (st_avloc, kill, st_avout, st_avin); 73517808Speter 73617808Speter#ifdef LCM_DEBUG_INFO 73717808Speter if (dump_file) 73817808Speter { 73917808Speter fprintf (dump_file, "Edge List:\n"); 74017808Speter verify_edge_list (dump_file, edge_list); 74117808Speter print_edge_list (dump_file, edge_list); 74217808Speter dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); 74317808Speter dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block); 74417808Speter dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block); 74517808Speter dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block); 74617808Speter dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block); 747131293Sdwmalone dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block); 7481590Srgrimes } 74993427Sdwmalone#endif 7501590Srgrimes 7511590Srgrimes#ifdef LCM_DEBUG_INFO 7521590Srgrimes if (dump_file) 7531590Srgrimes { 7541590Srgrimes dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block); 7551590Srgrimes dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block); 7561590Srgrimes } 7571590Srgrimes#endif 7581590Srgrimes 7591590Srgrimes /* Compute farthestness. */ 7601590Srgrimes farthest = sbitmap_vector_alloc (num_edges, n_exprs); 7611590Srgrimes compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin, 7621590Srgrimes kill, farthest); 7631590Srgrimes 76493427Sdwmalone#ifdef LCM_DEBUG_INFO 7651590Srgrimes if (dump_file) 7661590Srgrimes dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges); 7671590Srgrimes#endif 7681590Srgrimes 7691590Srgrimes sbitmap_vector_free (st_antin); 77037453Sbde sbitmap_vector_free (st_antout); 7711590Srgrimes 7721590Srgrimes sbitmap_vector_free (st_avin); 7731590Srgrimes sbitmap_vector_free (st_avout); 7741590Srgrimes 7751590Srgrimes nearer = sbitmap_vector_alloc (num_edges, n_exprs); 77637453Sbde 77737453Sbde /* Allocate an extra element for the entry block. */ 7781590Srgrimes nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); 7791590Srgrimes compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout); 7801590Srgrimes 7811590Srgrimes#ifdef LCM_DEBUG_INFO 7821590Srgrimes if (dump_file) 78337453Sbde { 78437453Sbde dump_sbitmap_vector (dump_file, "nearerout", "", nearerout, 7851590Srgrimes last_basic_block + 1); 7861590Srgrimes dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges); 7871590Srgrimes } 7881590Srgrimes#endif 7891590Srgrimes 79037453Sbde sbitmap_vector_free (farthest); 79137453Sbde 7921590Srgrimes *insert = sbitmap_vector_alloc (num_edges, n_exprs); 7931590Srgrimes *del = sbitmap_vector_alloc (last_basic_block, n_exprs); 7941590Srgrimes compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, 7951590Srgrimes *insert, *del); 7961590Srgrimes 7971590Srgrimes sbitmap_vector_free (nearerout); 7981590Srgrimes sbitmap_vector_free (nearer); 7991590Srgrimes 8001590Srgrimes#ifdef LCM_DEBUG_INFO 8011590Srgrimes if (dump_file) 8028874Srgrimes { 8031590Srgrimes dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); 8041590Srgrimes dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del, 8051590Srgrimes last_basic_block); 8061590Srgrimes } 8071590Srgrimes#endif 8081590Srgrimes return edge_list; 8091590Srgrimes} 8101590Srgrimes 8111590Srgrimes