From patchwork Mon Jul 23 13:59:34 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Steven Bosscher X-Patchwork-Id: 172692 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 4DC7D2C013E for ; Tue, 24 Jul 2012 00:03:48 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1343657029; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: MIME-Version:Received:From:Date:Message-ID:Subject:To: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=tClZFh1 MxaIHiMmxNC20th+2Em4=; b=TpTf3ecxtotxMykEXlk3tlCp1yohSZfzNlnSnUy WTOp+GNMdtUDxLpGx7icar1K0GCmFWzbb9d+1oIZC3B9w1e+KWxJTB0zlL/wHMIb upmjIaQXzbBZ3T8UyNXZQIL3Lo8Wp47UlYQrjqqedfbZwLMYObeHphHGvbPrtAO7 FCEw= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:MIME-Version:Received:From:Date:Message-ID:Subject:To:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=fOsuCEgabvj7Pw8FVyAJe17xNrJluX5kckHIRWmaZFxxEE1DG2ooBIbI0MHuRB 5ZlHEgmYM0muApzCWDX6g/GnhqMq+Epc2DLpoGwT6KIx/Dwb+n/PNHL+/T4h0M8h hPZ1+lvS6A2RANzZNhweHmJ4w3bgd4MulICj7qSdYaIpE=; Received: (qmail 21580 invoked by alias); 23 Jul 2012 14:03:41 -0000 Received: (qmail 21532 invoked by uid 22791); 23 Jul 2012 14:03:38 -0000 X-SWARE-Spam-Status: No, hits=-4.2 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, KHOP_RCVD_TRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, TW_CF X-Spam-Check-By: sourceware.org Received: from mail-fa0-f47.google.com (HELO mail-fa0-f47.google.com) (209.85.161.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 23 Jul 2012 14:03:17 +0000 Received: by faet1 with SMTP id t1so30586fae.20 for ; Mon, 23 Jul 2012 07:03:16 -0700 (PDT) Received: by 10.152.122.12 with SMTP id lo12mr17026949lab.3.1343051994192; Mon, 23 Jul 2012 06:59:54 -0700 (PDT) MIME-Version: 1.0 Received: by 10.112.4.229 with HTTP; Mon, 23 Jul 2012 06:59:34 -0700 (PDT) From: Steven Bosscher Date: Mon, 23 Jul 2012 15:59:34 +0200 Message-ID: Subject: [patch] Move sbitmap dataflow functions from sbitmap.c to cfganal.c To: GCC Patches X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hello, $SUBJECT because it makes sbitmap.c independent of basic-block.h -- as it should be, given that sbitmap is just a very simple bitmap datatype. Bootstrapped (profiledbootstrapped, actually) and tested on x86_64-unknown-linux-gnu. OK for trunk? Ciao! Steven * sbitmap.h (sbitmap_intersect_of_predsucc, sbitmap_union_of_predsucc): Remove prototypes of non-existing function. (sbitmap_intersect_of_predecessors, sbitmap_intersect_of_successors, sbitmap_union_of_predecessors, sbitmap_union_of_successors): Remove unused defines. (sbitmap_intersection_of_succs, sbitmap_intersection_of_preds, sbitmap_union_of_succs, sbitmap_union_of_preds): Move prototypes to... * basic-block.h: ... here. * sbitmap.c: Do not include basic-block.h. (sbitmap_intersection_of_succs, sbitmap_intersection_of_preds, sbitmap_union_of_succs, sbitmap_union_of_preds): Move functions to... * cfganal.c: ... here. * bt-load.c (compute_out, link_btr_uses): Update for above changes. * gcse.c (compute_code_hoist_vbeinout): Likewise. * lcm.c (compute_antinout_edge, compute_available): Likewise. * Makefile.in: Fix sbitmap.o dependencies. Index: sbitmap.h =================================================================== --- sbitmap.h (revision 189778) +++ sbitmap.h (working copy) @@ -241,24 +241,6 @@ extern bool sbitmap_a_subset_b_p (const_sbitmap, c extern int sbitmap_first_set_bit (const_sbitmap); extern int sbitmap_last_set_bit (const_sbitmap); -extern void sbitmap_intersect_of_predsucc (sbitmap, sbitmap *, int, - struct int_list **); -#define sbitmap_intersect_of_predecessors sbitmap_intersect_of_predsucc -#define sbitmap_intersect_of_successors sbitmap_intersect_of_predsucc - -extern void sbitmap_union_of_predsucc (sbitmap, sbitmap *, int, - struct int_list **); -#define sbitmap_union_of_predecessors sbitmap_union_of_predsucc -#define sbitmap_union_of_successors sbitmap_union_of_predsucc - -/* Intersection and Union of preds/succs using the new flow graph - structure instead of the pred/succ arrays. */ - -extern void sbitmap_intersection_of_succs (sbitmap, sbitmap *, int); -extern void sbitmap_intersection_of_preds (sbitmap, sbitmap *, int); -extern void sbitmap_union_of_succs (sbitmap, sbitmap *, int); -extern void sbitmap_union_of_preds (sbitmap, sbitmap *, int); - extern void debug_sbitmap (const_sbitmap); extern sbitmap sbitmap_realloc (sbitmap, unsigned int); extern unsigned long sbitmap_popcount(const_sbitmap, unsigned long); Index: basic-block.h =================================================================== --- basic-block.h (revision 189778) +++ basic-block.h (working copy) @@ -674,6 +674,12 @@ ei_cond (edge_iterator ei, edge *p) #define CLEANUP_CFGLAYOUT 32 /* Do cleanup in cfglayout mode. */ #define CLEANUP_CFG_CHANGED 64 /* The caller changed the CFG. */ +/* In cfganal.c */ +extern void sbitmap_intersection_of_succs (sbitmap, sbitmap *, basic_block); +extern void sbitmap_intersection_of_preds (sbitmap, sbitmap *, basic_block); +extern void sbitmap_union_of_succs (sbitmap, sbitmap *, basic_block); +extern void sbitmap_union_of_preds (sbitmap, sbitmap *, basic_block); + /* In lcm.c */ extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *, sbitmap *, sbitmap *, sbitmap **, Index: sbitmap.c =================================================================== --- sbitmap.c (revision 189778) +++ sbitmap.c (working copy) @@ -23,15 +23,6 @@ along with GCC; see the file COPYING3. If not see #include "coretypes.h" #include "sbitmap.h" -#ifdef IN_GCC -/* FIXME: sbitmap is just a data structure, but we define dataflow functions - here also. This is conditional on IN_GCC (see second #ifdef IN_GCC - further down). - For now, also only conditionally include basic-block.h, but we should - find a better place for the dataflow functions. Perhaps cfganal.c? */ -#include "basic-block.h" -#endif - #if GCC_VERSION >= 3400 # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG # define do_popcount(x) __builtin_popcountl(x) @@ -744,184 +735,6 @@ sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a *dstp++ = *ap++ & (*bp++ | *cp++); } -#ifdef IN_GCC -/* FIXME: depends on basic-block.h, see comment at start of this file. - - Ironically, the comments before the functions below suggest they do - dataflow using the "new flow graph structures", but that's the *old* - new data structures. The functions receive basic block numbers and - use BASIC_BLOCK(idx) to get the basic block. They should receive - the basic block directly, *sigh*. */ - -/* Set the bitmap DST to the intersection of SRC of successors of - block number BB, using the new flow graph structures. */ - -void -sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb) -{ - basic_block b = BASIC_BLOCK (bb); - unsigned int set_size = dst->size; - edge e; - unsigned ix; - - gcc_assert (!dst->popcount); - - for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) - { - e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) - continue; - - sbitmap_copy (dst, src[e->dest->index]); - break; - } - - if (e == 0) - sbitmap_ones (dst); - else - for (++ix; ix < EDGE_COUNT (b->succs); ix++) - { - unsigned int i; - sbitmap_ptr p, r; - - e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) - continue; - - p = src[e->dest->index]->elms; - r = dst->elms; - for (i = 0; i < set_size; i++) - *r++ &= *p++; - } -} - -/* Set the bitmap DST to the intersection of SRC of predecessors of - block number BB, using the new flow graph structures. */ - -void -sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb) -{ - basic_block b = BASIC_BLOCK (bb); - unsigned int set_size = dst->size; - edge e; - unsigned ix; - - gcc_assert (!dst->popcount); - - for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) - { - e = EDGE_PRED (b, ix); - if (e->src == ENTRY_BLOCK_PTR) - continue; - - sbitmap_copy (dst, src[e->src->index]); - break; - } - - if (e == 0) - sbitmap_ones (dst); - else - for (++ix; ix < EDGE_COUNT (b->preds); ix++) - { - unsigned int i; - sbitmap_ptr p, r; - - e = EDGE_PRED (b, ix); - if (e->src == ENTRY_BLOCK_PTR) - continue; - - p = src[e->src->index]->elms; - r = dst->elms; - for (i = 0; i < set_size; i++) - *r++ &= *p++; - } -} - -/* Set the bitmap DST to the union of SRC of successors of - block number BB, using the new flow graph structures. */ - -void -sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb) -{ - basic_block b = BASIC_BLOCK (bb); - unsigned int set_size = dst->size; - edge e; - unsigned ix; - - gcc_assert (!dst->popcount); - - for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) - { - e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) - continue; - - sbitmap_copy (dst, src[e->dest->index]); - break; - } - - if (ix == EDGE_COUNT (b->succs)) - sbitmap_zero (dst); - else - for (ix++; ix < EDGE_COUNT (b->succs); ix++) - { - unsigned int i; - sbitmap_ptr p, r; - - e = EDGE_SUCC (b, ix); - if (e->dest == EXIT_BLOCK_PTR) - continue; - - p = src[e->dest->index]->elms; - r = dst->elms; - for (i = 0; i < set_size; i++) - *r++ |= *p++; - } -} - -/* Set the bitmap DST to the union of SRC of predecessors of - block number BB, using the new flow graph structures. */ - -void -sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb) -{ - basic_block b = BASIC_BLOCK (bb); - unsigned int set_size = dst->size; - edge e; - unsigned ix; - - gcc_assert (!dst->popcount); - - for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) - { - e = EDGE_PRED (b, ix); - if (e->src== ENTRY_BLOCK_PTR) - continue; - - sbitmap_copy (dst, src[e->src->index]); - break; - } - - if (ix == EDGE_COUNT (b->preds)) - sbitmap_zero (dst); - else - for (ix++; ix < EDGE_COUNT (b->preds); ix++) - { - unsigned int i; - sbitmap_ptr p, r; - - e = EDGE_PRED (b, ix); - if (e->src == ENTRY_BLOCK_PTR) - continue; - - p = src[e->src->index]->elms; - r = dst->elms; - for (i = 0; i < set_size; i++) - *r++ |= *p++; - } -} -#endif - /* Return number of first bit set in the bitmap, -1 if none. */ int @@ -1021,13 +834,13 @@ void dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle, sbitmap *bmaps, int n_maps) { - int bb; + int i; fprintf (file, "%s\n", title); - for (bb = 0; bb < n_maps; bb++) + for (i = 0; i < n_maps; i++) { - fprintf (file, "%s %d\n", subtitle, bb); - dump_sbitmap (file, bmaps[bb]); + fprintf (file, "%s %d\n", subtitle, i); + dump_sbitmap (file, bmaps[i]); } fprintf (file, "\n"); Index: cfganal.c =================================================================== --- cfganal.c (revision 189778) +++ cfganal.c (working copy) @@ -1182,4 +1182,177 @@ compute_idf (bitmap def_blocks, bitmap_head *dfs) return phi_insertion_points; } +/* Intersection and union of preds/succs for sbitmap based data flow + solvers. All four functions defined below take the same arguments: + B is the basic block to perform the operation for. DST is the + target sbitmap, i.e. the result. SRC is an sbitmap vector of size + last_basic_block so that it can be indexed with basic block indices. + DST may be (but does not have to be) SRC[B->index]. */ +/* Set the bitmap DST to the intersection of SRC of successors of + basic block B. */ + +void +sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, + basic_block b) +{ + unsigned int set_size = dst->size; + edge e; + unsigned ix; + + gcc_assert (!dst->popcount); + + for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) + { + e = EDGE_SUCC (b, ix); + if (e->dest == EXIT_BLOCK_PTR) + continue; + + sbitmap_copy (dst, src[e->dest->index]); + break; + } + + if (e == 0) + sbitmap_ones (dst); + else + for (++ix; ix < EDGE_COUNT (b->succs); ix++) + { + unsigned int i; + SBITMAP_ELT_TYPE *p, *r; + + e = EDGE_SUCC (b, ix); + if (e->dest == EXIT_BLOCK_PTR) + continue; + + p = src[e->dest->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ &= *p++; + } +} + +/* Set the bitmap DST to the intersection of SRC of predecessors of + basic block B. */ + +void +sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, + basic_block b) +{ + unsigned int set_size = dst->size; + edge e; + unsigned ix; + + gcc_assert (!dst->popcount); + + for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) + { + e = EDGE_PRED (b, ix); + if (e->src == ENTRY_BLOCK_PTR) + continue; + + sbitmap_copy (dst, src[e->src->index]); + break; + } + + if (e == 0) + sbitmap_ones (dst); + else + for (++ix; ix < EDGE_COUNT (b->preds); ix++) + { + unsigned int i; + SBITMAP_ELT_TYPE *p, *r; + + e = EDGE_PRED (b, ix); + if (e->src == ENTRY_BLOCK_PTR) + continue; + + p = src[e->src->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ &= *p++; + } +} + +/* Set the bitmap DST to the union of SRC of successors of + basic block B. */ + +void +sbitmap_union_of_succs (sbitmap dst, sbitmap *src, + basic_block b) +{ + unsigned int set_size = dst->size; + edge e; + unsigned ix; + + gcc_assert (!dst->popcount); + + for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) + { + e = EDGE_SUCC (b, ix); + if (e->dest == EXIT_BLOCK_PTR) + continue; + + sbitmap_copy (dst, src[e->dest->index]); + break; + } + + if (ix == EDGE_COUNT (b->succs)) + sbitmap_zero (dst); + else + for (ix++; ix < EDGE_COUNT (b->succs); ix++) + { + unsigned int i; + SBITMAP_ELT_TYPE *p, *r; + + e = EDGE_SUCC (b, ix); + if (e->dest == EXIT_BLOCK_PTR) + continue; + + p = src[e->dest->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ |= *p++; + } +} + +/* Set the bitmap DST to the union of SRC of predecessors of + basic block B. */ + +void +sbitmap_union_of_preds (sbitmap dst, sbitmap *src, + basic_block b) +{ + unsigned int set_size = dst->size; + edge e; + unsigned ix; + + gcc_assert (!dst->popcount); + + for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) + { + e = EDGE_PRED (b, ix); + if (e->src== ENTRY_BLOCK_PTR) + continue; + + sbitmap_copy (dst, src[e->src->index]); + break; + } + + if (ix == EDGE_COUNT (b->preds)) + sbitmap_zero (dst); + else + for (ix++; ix < EDGE_COUNT (b->preds); ix++) + { + unsigned int i; + SBITMAP_ELT_TYPE *p, *r; + + e = EDGE_PRED (b, ix); + if (e->src == ENTRY_BLOCK_PTR) + continue; + + p = src[e->src->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ |= *p++; + } +} Index: bt-load.c =================================================================== --- bt-load.c (revision 189778) +++ bt-load.c (working copy) @@ -650,7 +650,7 @@ compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbi changed = 0; for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++) { - sbitmap_union_of_preds (bb_in, bb_out, i); + sbitmap_union_of_preds (bb_in, bb_out, BASIC_BLOCK (i)); changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i], bb_in, bb_kill[i]); } @@ -673,7 +673,7 @@ link_btr_uses (btr_def *def_array, btr_user *use_a rtx insn; rtx last; - sbitmap_union_of_preds (reaching_defs, bb_out, i); + sbitmap_union_of_preds (reaching_defs, bb_out, BASIC_BLOCK (i)); for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last; insn = NEXT_INSN (insn)) Index: gcse.c =================================================================== --- gcse.c (revision 189778) +++ gcse.c (working copy) @@ -2790,7 +2790,7 @@ compute_code_hoist_vbeinout (void) if (bb->next_bb != EXIT_BLOCK_PTR) { sbitmap_intersection_of_succs (hoist_vbeout[bb->index], - hoist_vbein, bb->index); + hoist_vbein, bb); /* Include expressions in VBEout that are calculated in BB and available at its end. */ Index: lcm.c =================================================================== --- lcm.c (revision 189778) +++ lcm.c (working copy) @@ -145,7 +145,7 @@ compute_antinout_edge (sbitmap *antloc, sbitmap *t /* Clear the aux field of this block so that it can be added to the worklist again if necessary. */ bb->aux = NULL; - sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index); + sbitmap_intersection_of_succs (antout[bb->index], antin, bb); } if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index], @@ -526,7 +526,7 @@ compute_available (sbitmap *avloc, sbitmap *kill, /* Clear the aux field of this block so that it can be added to the worklist again if necessary. */ bb->aux = NULL; - sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index); + sbitmap_intersection_of_preds (avin[bb->index], avout, bb); } if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index], Index: Makefile.in =================================================================== --- Makefile.in (revision 189780) +++ Makefile.in (working copy) @@ -1842,7 +1842,7 @@ graph.o: graph.c $(SYSTEM_H) coretypes.h $(RTL_H) $(FUNCTION_H) hard-reg-set.h $(BASIC_BLOCK_H) graph.h $(OBSTACK_H) \ $(CONFIG_H) $(EMIT_RTL_H) -sbitmap.o: sbitmap.c sbitmap.h $(CONFIG_H) $(SYSTEM_H) coretypes.h $(BASIC_BLOCK_H) +sbitmap.o: sbitmap.c sbitmap.h $(CONFIG_H) $(SYSTEM_H) coretypes.h ebitmap.o: ebitmap.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(EBITMAP_H) sparseset.o: sparseset.c $(SYSTEM_H) sparseset.h $(CONFIG_H)