190075Sobrien/* Generic partial redundancy elimination with lazy code motion support. 2169689Skan Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 3132718Skan Free Software Foundation, Inc. 452284Sobrien 590075SobrienThis file is part of GCC. 652284Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1152284Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1652284Sobrien 1752284SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2152284Sobrien 2252284Sobrien/* These routines are meant to be used by various optimization 2390075Sobrien passes which can be modeled as lazy code motion problems. 2452284Sobrien Including, but not limited to: 2552284Sobrien 2652284Sobrien * Traditional partial redundancy elimination. 2752284Sobrien 2852284Sobrien * Placement of caller/caller register save/restores. 2952284Sobrien 3052284Sobrien * Load/store motion. 3152284Sobrien 3252284Sobrien * Copy motion. 3352284Sobrien 3452284Sobrien * Conversion of flat register files to a stacked register 3552284Sobrien model. 3652284Sobrien 3752284Sobrien * Dead load/store elimination. 3852284Sobrien 3952284Sobrien These routines accept as input: 4052284Sobrien 4152284Sobrien * Basic block information (number of blocks, lists of 4252284Sobrien predecessors and successors). Note the granularity 4352284Sobrien does not need to be basic block, they could be statements 4452284Sobrien or functions. 4552284Sobrien 4652284Sobrien * Bitmaps of local properties (computed, transparent and 4752284Sobrien anticipatable expressions). 4852284Sobrien 4952284Sobrien The output of these routines is bitmap of redundant computations 5052284Sobrien and a bitmap of optimal placement points. */ 5152284Sobrien 5252284Sobrien 5352284Sobrien#include "config.h" 5452284Sobrien#include "system.h" 55132718Skan#include "coretypes.h" 56132718Skan#include "tm.h" 5752284Sobrien#include "rtl.h" 5852284Sobrien#include "regs.h" 5952284Sobrien#include "hard-reg-set.h" 6052284Sobrien#include "flags.h" 6152284Sobrien#include "real.h" 6252284Sobrien#include "insn-config.h" 6352284Sobrien#include "recog.h" 6452284Sobrien#include "basic-block.h" 65117395Skan#include "output.h" 6690075Sobrien#include "tm_p.h" 67132718Skan#include "function.h" 6852284Sobrien 6990075Sobrien/* We want target macros for the mode switching code to be able to refer 7090075Sobrien to instruction attribute values. */ 7190075Sobrien#include "insn-attr.h" 7252284Sobrien 7390075Sobrien/* Edge based LCM routines. */ 74132718Skanstatic void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *); 75132718Skanstatic void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *, 76132718Skan sbitmap *, sbitmap *, sbitmap *); 77132718Skanstatic void compute_laterin (struct edge_list *, sbitmap *, sbitmap *, 78132718Skan sbitmap *, sbitmap *); 79132718Skanstatic void compute_insert_delete (struct edge_list *edge_list, sbitmap *, 80132718Skan sbitmap *, sbitmap *, sbitmap *, sbitmap *); 8152284Sobrien 8290075Sobrien/* Edge based LCM routines on a reverse flowgraph. */ 83132718Skanstatic void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *, 84132718Skan sbitmap*, sbitmap *, sbitmap *); 85132718Skanstatic void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *, 86132718Skan sbitmap *, sbitmap *); 87132718Skanstatic void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *, 88132718Skan sbitmap *, sbitmap *, sbitmap *, 89132718Skan sbitmap *); 9090075Sobrien 9190075Sobrien/* Edge based lcm routines. */ 9252284Sobrien 9390075Sobrien/* Compute expression anticipatability at entrance and exit of each block. 9490075Sobrien This is done based on the flow graph, and not on the pred-succ lists. 9590075Sobrien Other than that, its pretty much identical to compute_antinout. */ 9690075Sobrien 9790075Sobrienstatic void 98132718Skancompute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin, 99132718Skan sbitmap *antout) 10052284Sobrien{ 101117395Skan basic_block bb; 10290075Sobrien edge e; 10390075Sobrien basic_block *worklist, *qin, *qout, *qend; 10490075Sobrien unsigned int qlen; 105169689Skan edge_iterator ei; 10652284Sobrien 10790075Sobrien /* Allocate a worklist array/queue. Entries are only added to the 10890075Sobrien list if they were not already on the list. So the size is 10990075Sobrien bounded by the number of basic blocks. */ 110169689Skan qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks); 11152284Sobrien 11290075Sobrien /* We want a maximal solution, so make an optimistic initialization of 11390075Sobrien ANTIN. */ 114117395Skan sbitmap_vector_ones (antin, last_basic_block); 11552284Sobrien 11690075Sobrien /* Put every block on the worklist; this is necessary because of the 11790075Sobrien optimistic initialization of ANTIN above. */ 118117395Skan FOR_EACH_BB_REVERSE (bb) 11990075Sobrien { 120132718Skan *qin++ = bb; 121117395Skan bb->aux = bb; 12290075Sobrien } 12352284Sobrien 12490075Sobrien qin = worklist; 125169689Skan qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; 126169689Skan qlen = n_basic_blocks - NUM_FIXED_BLOCKS; 12752284Sobrien 12890075Sobrien /* Mark blocks which are predecessors of the exit block so that we 12990075Sobrien can easily identify them below. */ 130169689Skan FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 13190075Sobrien e->src->aux = EXIT_BLOCK_PTR; 13252284Sobrien 13390075Sobrien /* Iterate until the worklist is empty. */ 13490075Sobrien while (qlen) 13590075Sobrien { 13690075Sobrien /* Take the first entry off the worklist. */ 137117395Skan bb = *qout++; 13890075Sobrien qlen--; 13990075Sobrien 14090075Sobrien if (qout >= qend) 141117395Skan qout = worklist; 14290075Sobrien 143117395Skan if (bb->aux == EXIT_BLOCK_PTR) 14490075Sobrien /* Do not clear the aux field for blocks which are predecessors of 14590075Sobrien the EXIT block. That way we never add then to the worklist 14690075Sobrien again. */ 147117395Skan sbitmap_zero (antout[bb->index]); 14890075Sobrien else 14990075Sobrien { 15090075Sobrien /* Clear the aux field of this block so that it can be added to 15190075Sobrien the worklist again if necessary. */ 152117395Skan bb->aux = NULL; 153117395Skan sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index); 15490075Sobrien } 15590075Sobrien 156117395Skan if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index], 157117395Skan transp[bb->index], antout[bb->index])) 15890075Sobrien /* If the in state of this block changed, then we need 15990075Sobrien to add the predecessors of this block to the worklist 16090075Sobrien if they are not already on the worklist. */ 161169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 16290075Sobrien if (!e->src->aux && e->src != ENTRY_BLOCK_PTR) 16390075Sobrien { 16490075Sobrien *qin++ = e->src; 16590075Sobrien e->src->aux = e; 16690075Sobrien qlen++; 16790075Sobrien if (qin >= qend) 168117395Skan qin = worklist; 16990075Sobrien } 17090075Sobrien } 17190075Sobrien 17290075Sobrien clear_aux_for_edges (); 17390075Sobrien clear_aux_for_blocks (); 17490075Sobrien free (worklist); 17552284Sobrien} 17652284Sobrien 17790075Sobrien/* Compute the earliest vector for edge based lcm. */ 17852284Sobrien 17990075Sobrienstatic void 180132718Skancompute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin, 181132718Skan sbitmap *antout, sbitmap *avout, sbitmap *kill, 182132718Skan sbitmap *earliest) 18352284Sobrien{ 18490075Sobrien sbitmap difference, temp_bitmap; 18590075Sobrien int x, num_edges; 18690075Sobrien basic_block pred, succ; 18752284Sobrien 18890075Sobrien num_edges = NUM_EDGES (edge_list); 18952284Sobrien 19090075Sobrien difference = sbitmap_alloc (n_exprs); 19190075Sobrien temp_bitmap = sbitmap_alloc (n_exprs); 19252284Sobrien 19390075Sobrien for (x = 0; x < num_edges; x++) 19490075Sobrien { 19590075Sobrien pred = INDEX_EDGE_PRED_BB (edge_list, x); 19690075Sobrien succ = INDEX_EDGE_SUCC_BB (edge_list, x); 19790075Sobrien if (pred == ENTRY_BLOCK_PTR) 19890075Sobrien sbitmap_copy (earliest[x], antin[succ->index]); 19990075Sobrien else 200117395Skan { 201117395Skan if (succ == EXIT_BLOCK_PTR) 20290075Sobrien sbitmap_zero (earliest[x]); 20390075Sobrien else 20490075Sobrien { 20590075Sobrien sbitmap_difference (difference, antin[succ->index], 20690075Sobrien avout[pred->index]); 20790075Sobrien sbitmap_not (temp_bitmap, antout[pred->index]); 20890075Sobrien sbitmap_a_and_b_or_c (earliest[x], difference, 20990075Sobrien kill[pred->index], temp_bitmap); 21090075Sobrien } 21190075Sobrien } 21290075Sobrien } 21352284Sobrien 21490075Sobrien sbitmap_free (temp_bitmap); 21590075Sobrien sbitmap_free (difference); 21690075Sobrien} 21752284Sobrien 21890075Sobrien/* later(p,s) is dependent on the calculation of laterin(p). 21990075Sobrien laterin(p) is dependent on the calculation of later(p2,p). 22052284Sobrien 22190075Sobrien laterin(ENTRY) is defined as all 0's 22290075Sobrien later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY) 22390075Sobrien laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)). 22452284Sobrien 22590075Sobrien If we progress in this manner, starting with all basic blocks 22690075Sobrien in the work list, anytime we change later(bb), we need to add 22790075Sobrien succs(bb) to the worklist if they are not already on the worklist. 22852284Sobrien 22990075Sobrien Boundary conditions: 23090075Sobrien 23190075Sobrien We prime the worklist all the normal basic blocks. The ENTRY block can 23290075Sobrien never be added to the worklist since it is never the successor of any 23390075Sobrien block. We explicitly prevent the EXIT block from being added to the 23490075Sobrien worklist. 23590075Sobrien 23690075Sobrien We optimistically initialize LATER. That is the only time this routine 23790075Sobrien will compute LATER for an edge out of the entry block since the entry 23890075Sobrien block is never on the worklist. Thus, LATERIN is neither used nor 23990075Sobrien computed for the ENTRY block. 24090075Sobrien 24190075Sobrien Since the EXIT block is never added to the worklist, we will neither 24290075Sobrien use nor compute LATERIN for the exit block. Edges which reach the 24390075Sobrien EXIT block are handled in the normal fashion inside the loop. However, 24490075Sobrien the insertion/deletion computation needs LATERIN(EXIT), so we have 24590075Sobrien to compute it. */ 24690075Sobrien 24752284Sobrienstatic void 248132718Skancompute_laterin (struct edge_list *edge_list, sbitmap *earliest, 249132718Skan sbitmap *antloc, sbitmap *later, sbitmap *laterin) 25052284Sobrien{ 251117395Skan int num_edges, i; 25290075Sobrien edge e; 253117395Skan basic_block *worklist, *qin, *qout, *qend, bb; 25490075Sobrien unsigned int qlen; 255169689Skan edge_iterator ei; 25652284Sobrien 25790075Sobrien num_edges = NUM_EDGES (edge_list); 25852284Sobrien 25990075Sobrien /* Allocate a worklist array/queue. Entries are only added to the 26090075Sobrien list if they were not already on the list. So the size is 26190075Sobrien bounded by the number of basic blocks. */ 26290075Sobrien qin = qout = worklist 263169689Skan = XNEWVEC (basic_block, n_basic_blocks); 26452284Sobrien 26590075Sobrien /* Initialize a mapping from each edge to its index. */ 26690075Sobrien for (i = 0; i < num_edges; i++) 26790075Sobrien INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; 26890075Sobrien 26990075Sobrien /* We want a maximal solution, so initially consider LATER true for 27090075Sobrien all edges. This allows propagation through a loop since the incoming 27190075Sobrien loop edge will have LATER set, so if all the other incoming edges 27290075Sobrien to the loop are set, then LATERIN will be set for the head of the 27390075Sobrien loop. 27490075Sobrien 27590075Sobrien If the optimistic setting of LATER on that edge was incorrect (for 27690075Sobrien example the expression is ANTLOC in a block within the loop) then 27790075Sobrien this algorithm will detect it when we process the block at the head 27890075Sobrien of the optimistic edge. That will requeue the affected blocks. */ 27990075Sobrien sbitmap_vector_ones (later, num_edges); 28090075Sobrien 28190075Sobrien /* Note that even though we want an optimistic setting of LATER, we 28290075Sobrien do not want to be overly optimistic. Consider an outgoing edge from 28390075Sobrien the entry block. That edge should always have a LATER value the 28490075Sobrien same as EARLIEST for that edge. */ 285169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 28690075Sobrien sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]); 28790075Sobrien 28890075Sobrien /* Add all the blocks to the worklist. This prevents an early exit from 28990075Sobrien the loop given our optimistic initialization of LATER above. */ 290117395Skan FOR_EACH_BB (bb) 29152284Sobrien { 292117395Skan *qin++ = bb; 293117395Skan bb->aux = bb; 29490075Sobrien } 295169689Skan 296169689Skan /* Note that we do not use the last allocated element for our queue, 297169689Skan as EXIT_BLOCK is never inserted into it. */ 29890075Sobrien qin = worklist; 299169689Skan qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; 300169689Skan qlen = n_basic_blocks - NUM_FIXED_BLOCKS; 30152284Sobrien 30290075Sobrien /* Iterate until the worklist is empty. */ 30390075Sobrien while (qlen) 30490075Sobrien { 30590075Sobrien /* Take the first entry off the worklist. */ 306117395Skan bb = *qout++; 307117395Skan bb->aux = NULL; 30890075Sobrien qlen--; 30990075Sobrien if (qout >= qend) 310117395Skan qout = worklist; 31152284Sobrien 31290075Sobrien /* Compute the intersection of LATERIN for each incoming edge to B. */ 313117395Skan sbitmap_ones (laterin[bb->index]); 314169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 315169689Skan sbitmap_a_and_b (laterin[bb->index], laterin[bb->index], 316169689Skan later[(size_t)e->aux]); 31752284Sobrien 31890075Sobrien /* Calculate LATER for all outgoing edges. */ 319169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 320117395Skan if (sbitmap_union_of_diff_cg (later[(size_t) e->aux], 321117395Skan earliest[(size_t) e->aux], 322117395Skan laterin[e->src->index], 323117395Skan antloc[e->src->index]) 32490075Sobrien /* If LATER for an outgoing edge was changed, then we need 32590075Sobrien to add the target of the outgoing edge to the worklist. */ 32690075Sobrien && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0) 32790075Sobrien { 32890075Sobrien *qin++ = e->dest; 32990075Sobrien e->dest->aux = e; 33090075Sobrien qlen++; 33190075Sobrien if (qin >= qend) 33290075Sobrien qin = worklist; 33390075Sobrien } 33490075Sobrien } 33552284Sobrien 33690075Sobrien /* Computation of insertion and deletion points requires computing LATERIN 33790075Sobrien for the EXIT block. We allocated an extra entry in the LATERIN array 33890075Sobrien for just this purpose. */ 339117395Skan sbitmap_ones (laterin[last_basic_block]); 340169689Skan FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 341117395Skan sbitmap_a_and_b (laterin[last_basic_block], 342117395Skan laterin[last_basic_block], 34390075Sobrien later[(size_t) e->aux]); 34490075Sobrien 34590075Sobrien clear_aux_for_edges (); 34690075Sobrien free (worklist); 34752284Sobrien} 34852284Sobrien 34990075Sobrien/* Compute the insertion and deletion points for edge based LCM. */ 35052284Sobrien 35190075Sobrienstatic void 352132718Skancompute_insert_delete (struct edge_list *edge_list, sbitmap *antloc, 353132718Skan sbitmap *later, sbitmap *laterin, sbitmap *insert, 354132718Skan sbitmap *delete) 35590075Sobrien{ 35690075Sobrien int x; 357117395Skan basic_block bb; 35852284Sobrien 359117395Skan FOR_EACH_BB (bb) 360169689Skan sbitmap_difference (delete[bb->index], antloc[bb->index], 361169689Skan laterin[bb->index]); 36252284Sobrien 36390075Sobrien for (x = 0; x < NUM_EDGES (edge_list); x++) 36490075Sobrien { 36590075Sobrien basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x); 36690075Sobrien 36790075Sobrien if (b == EXIT_BLOCK_PTR) 368117395Skan sbitmap_difference (insert[x], later[x], laterin[last_basic_block]); 36990075Sobrien else 37090075Sobrien sbitmap_difference (insert[x], later[x], laterin[b->index]); 37190075Sobrien } 37290075Sobrien} 37390075Sobrien 37490075Sobrien/* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and 37590075Sobrien delete vectors for edge based LCM. Returns an edgelist which is used to 37690075Sobrien map the insert vector to what edge an expression should be inserted on. */ 37790075Sobrien 37890075Sobrienstruct edge_list * 379169689Skanpre_edge_lcm (int n_exprs, sbitmap *transp, 380132718Skan sbitmap *avloc, sbitmap *antloc, sbitmap *kill, 381132718Skan sbitmap **insert, sbitmap **delete) 38252284Sobrien{ 38390075Sobrien sbitmap *antin, *antout, *earliest; 38490075Sobrien sbitmap *avin, *avout; 38590075Sobrien sbitmap *later, *laterin; 38690075Sobrien struct edge_list *edge_list; 38790075Sobrien int num_edges; 38852284Sobrien 38990075Sobrien edge_list = create_edge_list (); 39090075Sobrien num_edges = NUM_EDGES (edge_list); 39152284Sobrien 39290075Sobrien#ifdef LCM_DEBUG_INFO 393169689Skan if (dump_file) 39490075Sobrien { 395169689Skan fprintf (dump_file, "Edge List:\n"); 396169689Skan verify_edge_list (dump_file, edge_list); 397169689Skan print_edge_list (dump_file, edge_list); 398169689Skan dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); 399169689Skan dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block); 400169689Skan dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block); 401169689Skan dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block); 40290075Sobrien } 40390075Sobrien#endif 40452284Sobrien 40590075Sobrien /* Compute global availability. */ 406117395Skan avin = sbitmap_vector_alloc (last_basic_block, n_exprs); 407117395Skan avout = sbitmap_vector_alloc (last_basic_block, n_exprs); 40890075Sobrien compute_available (avloc, kill, avout, avin); 40990075Sobrien sbitmap_vector_free (avin); 41052284Sobrien 41190075Sobrien /* Compute global anticipatability. */ 412117395Skan antin = sbitmap_vector_alloc (last_basic_block, n_exprs); 413117395Skan antout = sbitmap_vector_alloc (last_basic_block, n_exprs); 41490075Sobrien compute_antinout_edge (antloc, transp, antin, antout); 41590075Sobrien 41690075Sobrien#ifdef LCM_DEBUG_INFO 417169689Skan if (dump_file) 41852284Sobrien { 419169689Skan dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block); 420169689Skan dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block); 42190075Sobrien } 42290075Sobrien#endif 42352284Sobrien 42490075Sobrien /* Compute earliestness. */ 42590075Sobrien earliest = sbitmap_vector_alloc (num_edges, n_exprs); 42690075Sobrien compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest); 42752284Sobrien 42890075Sobrien#ifdef LCM_DEBUG_INFO 429169689Skan if (dump_file) 430169689Skan dump_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges); 43190075Sobrien#endif 43252284Sobrien 43390075Sobrien sbitmap_vector_free (antout); 43490075Sobrien sbitmap_vector_free (antin); 43590075Sobrien sbitmap_vector_free (avout); 43652284Sobrien 43790075Sobrien later = sbitmap_vector_alloc (num_edges, n_exprs); 43890075Sobrien 43990075Sobrien /* Allocate an extra element for the exit block in the laterin vector. */ 440117395Skan laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); 44190075Sobrien compute_laterin (edge_list, earliest, antloc, later, laterin); 44290075Sobrien 44390075Sobrien#ifdef LCM_DEBUG_INFO 444169689Skan if (dump_file) 44590075Sobrien { 446169689Skan dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1); 447169689Skan dump_sbitmap_vector (dump_file, "later", "", later, num_edges); 44852284Sobrien } 44990075Sobrien#endif 45052284Sobrien 45190075Sobrien sbitmap_vector_free (earliest); 45252284Sobrien 45390075Sobrien *insert = sbitmap_vector_alloc (num_edges, n_exprs); 454117395Skan *delete = sbitmap_vector_alloc (last_basic_block, n_exprs); 45590075Sobrien compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete); 45652284Sobrien 45790075Sobrien sbitmap_vector_free (laterin); 45890075Sobrien sbitmap_vector_free (later); 45952284Sobrien 46090075Sobrien#ifdef LCM_DEBUG_INFO 461169689Skan if (dump_file) 46290075Sobrien { 463169689Skan dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); 464169689Skan dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete, 465117395Skan last_basic_block); 46690075Sobrien } 46790075Sobrien#endif 46890075Sobrien 46990075Sobrien return edge_list; 47090075Sobrien} 47190075Sobrien 47290075Sobrien/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. 47390075Sobrien Return the number of passes we performed to iterate to a solution. */ 47490075Sobrien 47590075Sobrienvoid 476132718Skancompute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout, 477132718Skan sbitmap *avin) 47852284Sobrien{ 47990075Sobrien edge e; 480117395Skan basic_block *worklist, *qin, *qout, *qend, bb; 48190075Sobrien unsigned int qlen; 482169689Skan edge_iterator ei; 48352284Sobrien 48490075Sobrien /* Allocate a worklist array/queue. Entries are only added to the 48590075Sobrien list if they were not already on the list. So the size is 48690075Sobrien bounded by the number of basic blocks. */ 487169689Skan qin = qout = worklist = 488169689Skan XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS); 48952284Sobrien 49090075Sobrien /* We want a maximal solution. */ 491117395Skan sbitmap_vector_ones (avout, last_basic_block); 49252284Sobrien 49390075Sobrien /* Put every block on the worklist; this is necessary because of the 49490075Sobrien optimistic initialization of AVOUT above. */ 495117395Skan FOR_EACH_BB (bb) 49652284Sobrien { 497117395Skan *qin++ = bb; 498117395Skan bb->aux = bb; 49990075Sobrien } 50090075Sobrien 50190075Sobrien qin = worklist; 502169689Skan qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS]; 503169689Skan qlen = n_basic_blocks - NUM_FIXED_BLOCKS; 50490075Sobrien 50590075Sobrien /* Mark blocks which are successors of the entry block so that we 50690075Sobrien can easily identify them below. */ 507169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 50890075Sobrien e->dest->aux = ENTRY_BLOCK_PTR; 50990075Sobrien 51090075Sobrien /* Iterate until the worklist is empty. */ 51190075Sobrien while (qlen) 51290075Sobrien { 51390075Sobrien /* Take the first entry off the worklist. */ 514117395Skan bb = *qout++; 51590075Sobrien qlen--; 51690075Sobrien 51790075Sobrien if (qout >= qend) 518117395Skan qout = worklist; 51990075Sobrien 52090075Sobrien /* If one of the predecessor blocks is the ENTRY block, then the 52190075Sobrien intersection of avouts is the null set. We can identify such blocks 52290075Sobrien by the special value in the AUX field in the block structure. */ 523117395Skan if (bb->aux == ENTRY_BLOCK_PTR) 52490075Sobrien /* Do not clear the aux field for blocks which are successors of the 52590075Sobrien ENTRY block. That way we never add then to the worklist again. */ 526117395Skan sbitmap_zero (avin[bb->index]); 52790075Sobrien else 52852284Sobrien { 52990075Sobrien /* Clear the aux field of this block so that it can be added to 53090075Sobrien the worklist again if necessary. */ 531117395Skan bb->aux = NULL; 532117395Skan sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index); 53390075Sobrien } 53490075Sobrien 535169689Skan if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index], 536169689Skan avin[bb->index], kill[bb->index])) 53790075Sobrien /* If the out state of this block changed, then we need 53890075Sobrien to add the successors of this block to the worklist 53990075Sobrien if they are not already on the worklist. */ 540169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 54190075Sobrien if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR) 54252284Sobrien { 54390075Sobrien *qin++ = e->dest; 54490075Sobrien e->dest->aux = e; 54590075Sobrien qlen++; 54690075Sobrien 54790075Sobrien if (qin >= qend) 548117395Skan qin = worklist; 54952284Sobrien } 55052284Sobrien } 55152284Sobrien 55290075Sobrien clear_aux_for_edges (); 55390075Sobrien clear_aux_for_blocks (); 55490075Sobrien free (worklist); 55552284Sobrien} 55652284Sobrien 55790075Sobrien/* Compute the farthest vector for edge based lcm. */ 55852284Sobrien 55952284Sobrienstatic void 560132718Skancompute_farthest (struct edge_list *edge_list, int n_exprs, 561132718Skan sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin, 562132718Skan sbitmap *kill, sbitmap *farthest) 56352284Sobrien{ 56490075Sobrien sbitmap difference, temp_bitmap; 56590075Sobrien int x, num_edges; 56690075Sobrien basic_block pred, succ; 56752284Sobrien 56890075Sobrien num_edges = NUM_EDGES (edge_list); 56990075Sobrien 57090075Sobrien difference = sbitmap_alloc (n_exprs); 57152284Sobrien temp_bitmap = sbitmap_alloc (n_exprs); 57252284Sobrien 57390075Sobrien for (x = 0; x < num_edges; x++) 57452284Sobrien { 57590075Sobrien pred = INDEX_EDGE_PRED_BB (edge_list, x); 57690075Sobrien succ = INDEX_EDGE_SUCC_BB (edge_list, x); 57790075Sobrien if (succ == EXIT_BLOCK_PTR) 57890075Sobrien sbitmap_copy (farthest[x], st_avout[pred->index]); 57990075Sobrien else 58052284Sobrien { 58190075Sobrien if (pred == ENTRY_BLOCK_PTR) 58290075Sobrien sbitmap_zero (farthest[x]); 58390075Sobrien else 58490075Sobrien { 58590075Sobrien sbitmap_difference (difference, st_avout[pred->index], 58690075Sobrien st_antin[succ->index]); 58790075Sobrien sbitmap_not (temp_bitmap, st_avin[succ->index]); 58890075Sobrien sbitmap_a_and_b_or_c (farthest[x], difference, 58990075Sobrien kill[succ->index], temp_bitmap); 59090075Sobrien } 59152284Sobrien } 59252284Sobrien } 59390075Sobrien 59490075Sobrien sbitmap_free (temp_bitmap); 59590075Sobrien sbitmap_free (difference); 59652284Sobrien} 59752284Sobrien 59890075Sobrien/* Compute nearer and nearerout vectors for edge based lcm. 59952284Sobrien 60090075Sobrien This is the mirror of compute_laterin, additional comments on the 60190075Sobrien implementation can be found before compute_laterin. */ 60252284Sobrien 60352284Sobrienstatic void 604132718Skancompute_nearerout (struct edge_list *edge_list, sbitmap *farthest, 605132718Skan sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout) 60652284Sobrien{ 607117395Skan int num_edges, i; 60890075Sobrien edge e; 609117395Skan basic_block *worklist, *tos, bb; 610169689Skan edge_iterator ei; 61152284Sobrien 61290075Sobrien num_edges = NUM_EDGES (edge_list); 61352284Sobrien 61490075Sobrien /* Allocate a worklist array/queue. Entries are only added to the 61590075Sobrien list if they were not already on the list. So the size is 61690075Sobrien bounded by the number of basic blocks. */ 617169689Skan tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1); 61890075Sobrien 61990075Sobrien /* Initialize NEARER for each edge and build a mapping from an edge to 62090075Sobrien its index. */ 62190075Sobrien for (i = 0; i < num_edges; i++) 62290075Sobrien INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; 62390075Sobrien 62490075Sobrien /* We want a maximal solution. */ 62590075Sobrien sbitmap_vector_ones (nearer, num_edges); 62690075Sobrien 62790075Sobrien /* Note that even though we want an optimistic setting of NEARER, we 62890075Sobrien do not want to be overly optimistic. Consider an incoming edge to 62990075Sobrien the exit block. That edge should always have a NEARER value the 63090075Sobrien same as FARTHEST for that edge. */ 631169689Skan FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 63290075Sobrien sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]); 63390075Sobrien 63490075Sobrien /* Add all the blocks to the worklist. This prevents an early exit 63590075Sobrien from the loop given our optimistic initialization of NEARER. */ 636117395Skan FOR_EACH_BB (bb) 63752284Sobrien { 638117395Skan *tos++ = bb; 639117395Skan bb->aux = bb; 64052284Sobrien } 64190075Sobrien 64290075Sobrien /* Iterate until the worklist is empty. */ 64390075Sobrien while (tos != worklist) 64490075Sobrien { 64590075Sobrien /* Take the first entry off the worklist. */ 646117395Skan bb = *--tos; 647117395Skan bb->aux = NULL; 64890075Sobrien 64990075Sobrien /* Compute the intersection of NEARER for each outgoing edge from B. */ 650117395Skan sbitmap_ones (nearerout[bb->index]); 651169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 652117395Skan sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index], 65390075Sobrien nearer[(size_t) e->aux]); 65490075Sobrien 65590075Sobrien /* Calculate NEARER for all incoming edges. */ 656169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 657117395Skan if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux], 658117395Skan farthest[(size_t) e->aux], 659117395Skan nearerout[e->dest->index], 660117395Skan st_avloc[e->dest->index]) 66190075Sobrien /* If NEARER for an incoming edge was changed, then we need 66290075Sobrien to add the source of the incoming edge to the worklist. */ 66390075Sobrien && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0) 66490075Sobrien { 66590075Sobrien *tos++ = e->src; 66690075Sobrien e->src->aux = e; 66790075Sobrien } 66890075Sobrien } 66990075Sobrien 67090075Sobrien /* Computation of insertion and deletion points requires computing NEAREROUT 67190075Sobrien for the ENTRY block. We allocated an extra entry in the NEAREROUT array 67290075Sobrien for just this purpose. */ 673117395Skan sbitmap_ones (nearerout[last_basic_block]); 674169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 675117395Skan sbitmap_a_and_b (nearerout[last_basic_block], 676117395Skan nearerout[last_basic_block], 67790075Sobrien nearer[(size_t) e->aux]); 67890075Sobrien 67990075Sobrien clear_aux_for_edges (); 68090075Sobrien free (tos); 68152284Sobrien} 68252284Sobrien 68390075Sobrien/* Compute the insertion and deletion points for edge based LCM. */ 68452284Sobrien 68552284Sobrienstatic void 686132718Skancompute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc, 687132718Skan sbitmap *nearer, sbitmap *nearerout, 688132718Skan sbitmap *insert, sbitmap *delete) 68952284Sobrien{ 69090075Sobrien int x; 691117395Skan basic_block bb; 69252284Sobrien 693117395Skan FOR_EACH_BB (bb) 694169689Skan sbitmap_difference (delete[bb->index], st_avloc[bb->index], 695169689Skan nearerout[bb->index]); 69690075Sobrien 69790075Sobrien for (x = 0; x < NUM_EDGES (edge_list); x++) 69890075Sobrien { 69990075Sobrien basic_block b = INDEX_EDGE_PRED_BB (edge_list, x); 70090075Sobrien if (b == ENTRY_BLOCK_PTR) 701117395Skan sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]); 70290075Sobrien else 70390075Sobrien sbitmap_difference (insert[x], nearer[x], nearerout[b->index]); 70490075Sobrien } 70552284Sobrien} 70652284Sobrien 70790075Sobrien/* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the 70890075Sobrien insert and delete vectors for edge based reverse LCM. Returns an 70990075Sobrien edgelist which is used to map the insert vector to what edge 71090075Sobrien an expression should be inserted on. */ 71152284Sobrien 71290075Sobrienstruct edge_list * 713169689Skanpre_edge_rev_lcm (int n_exprs, sbitmap *transp, 714132718Skan sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill, 715132718Skan sbitmap **insert, sbitmap **delete) 71652284Sobrien{ 71790075Sobrien sbitmap *st_antin, *st_antout; 71890075Sobrien sbitmap *st_avout, *st_avin, *farthest; 71990075Sobrien sbitmap *nearer, *nearerout; 72090075Sobrien struct edge_list *edge_list; 72190075Sobrien int num_edges; 72252284Sobrien 72390075Sobrien edge_list = create_edge_list (); 72490075Sobrien num_edges = NUM_EDGES (edge_list); 72552284Sobrien 726132718Skan st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs); 727132718Skan st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs); 728117395Skan sbitmap_vector_zero (st_antin, last_basic_block); 729117395Skan sbitmap_vector_zero (st_antout, last_basic_block); 73090075Sobrien compute_antinout_edge (st_antloc, transp, st_antin, st_antout); 73190075Sobrien 73290075Sobrien /* Compute global anticipatability. */ 733117395Skan st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs); 734117395Skan st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs); 73590075Sobrien compute_available (st_avloc, kill, st_avout, st_avin); 73690075Sobrien 73790075Sobrien#ifdef LCM_DEBUG_INFO 738169689Skan if (dump_file) 73952284Sobrien { 740169689Skan fprintf (dump_file, "Edge List:\n"); 741169689Skan verify_edge_list (dump_file, edge_list); 742169689Skan print_edge_list (dump_file, edge_list); 743169689Skan dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block); 744169689Skan dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block); 745169689Skan dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block); 746169689Skan dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block); 747169689Skan dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block); 748169689Skan dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block); 74952284Sobrien } 75090075Sobrien#endif 75190075Sobrien 75290075Sobrien#ifdef LCM_DEBUG_INFO 753169689Skan if (dump_file) 75490075Sobrien { 755169689Skan dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block); 756169689Skan dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block); 75790075Sobrien } 75890075Sobrien#endif 75990075Sobrien 76090075Sobrien /* Compute farthestness. */ 76190075Sobrien farthest = sbitmap_vector_alloc (num_edges, n_exprs); 76290075Sobrien compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin, 76390075Sobrien kill, farthest); 76490075Sobrien 76590075Sobrien#ifdef LCM_DEBUG_INFO 766169689Skan if (dump_file) 767169689Skan dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges); 76890075Sobrien#endif 76990075Sobrien 77090075Sobrien sbitmap_vector_free (st_antin); 77190075Sobrien sbitmap_vector_free (st_antout); 77290075Sobrien 77390075Sobrien sbitmap_vector_free (st_avin); 77490075Sobrien sbitmap_vector_free (st_avout); 77590075Sobrien 77690075Sobrien nearer = sbitmap_vector_alloc (num_edges, n_exprs); 77790075Sobrien 77890075Sobrien /* Allocate an extra element for the entry block. */ 779117395Skan nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); 78090075Sobrien compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout); 78190075Sobrien 78290075Sobrien#ifdef LCM_DEBUG_INFO 783169689Skan if (dump_file) 78490075Sobrien { 785169689Skan dump_sbitmap_vector (dump_file, "nearerout", "", nearerout, 786117395Skan last_basic_block + 1); 787169689Skan dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges); 78890075Sobrien } 78990075Sobrien#endif 79090075Sobrien 79190075Sobrien sbitmap_vector_free (farthest); 79290075Sobrien 79390075Sobrien *insert = sbitmap_vector_alloc (num_edges, n_exprs); 794117395Skan *delete = sbitmap_vector_alloc (last_basic_block, n_exprs); 79590075Sobrien compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, 79690075Sobrien *insert, *delete); 79790075Sobrien 79890075Sobrien sbitmap_vector_free (nearerout); 79990075Sobrien sbitmap_vector_free (nearer); 80090075Sobrien 80190075Sobrien#ifdef LCM_DEBUG_INFO 802169689Skan if (dump_file) 80390075Sobrien { 804169689Skan dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); 805169689Skan dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete, 806117395Skan last_basic_block); 80790075Sobrien } 80890075Sobrien#endif 80990075Sobrien return edge_list; 81052284Sobrien} 81152284Sobrien 812