From patchwork Fri Jun 18 14:08:04 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bernd Schmidt X-Patchwork-Id: 56187 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 749031007D4 for ; Sat, 19 Jun 2010 00:08:27 +1000 (EST) Received: (qmail 12304 invoked by alias); 18 Jun 2010 14:08:25 -0000 Received: (qmail 12264 invoked by uid 22791); 18 Jun 2010 14:08:22 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 18 Jun 2010 14:08:14 +0000 Received: (qmail 32245 invoked from network); 18 Jun 2010 14:08:10 -0000 Received: from unknown (HELO ?84.152.216.85?) (bernds@127.0.0.2) by mail.codesourcery.com with ESMTPA; 18 Jun 2010 14:08:10 -0000 Message-ID: <4C1B7DC4.5000603@codesourcery.com> Date: Fri, 18 Jun 2010 14:08:04 +0000 From: Bernd Schmidt User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.9) Gecko/20100604 Thunderbird/3.0.4 MIME-Version: 1.0 To: GCC Patches Subject: Patch 5/9: rename allocno_set to minmax_set References: <4C1B7BC0.7010803@codesourcery.com> In-Reply-To: <4C1B7BC0.7010803@codesourcery.com> 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 This renames the bitset implementation in ira-int.h so that it no longer has ALLOCNO in its name. I've called this type of set a MINMAX_SET, which seems like a good description to me. Keeping track of min/max values to reduce the size of the bit vector is what separates this from an sbitmap. We could move this to sbitmap.h later IMO. Currently these sets are still all used to keep track of allocnos, but subsequent patches will change this. * ira-int.h (SET_MINMAX_SET_BIT, CLEAR_MINMAX_SET_BIT, TEST_MINMAX_SET_BIT, minmax_set_iterator, minmax_set_iter_init, minmax_set_iter_cond, minmax_set_iter_next, FOR_EACH_BIT_IN_MINMAX_SET): Renamed from SET_ALLOCNO_SET_BIT, CLEAR_ALLOCNO_SET_BIT, TEST_ALLOCNO_SET_BIT, ira_allocno_set_iterator, ira_allocno_set_iter_init, ira_allocno_set_iter_cond, ira_allocno_set_iter_Next and FOR_EACH_ALLOCNO_IN_ALLOCNO_SET. All uses changed. Index: gcc/ira-conflicts.c =================================================================== --- gcc.orig/ira-conflicts.c +++ gcc/ira-conflicts.c @@ -54,10 +54,10 @@ static IRA_INT_TYPE **conflicts; #define CONFLICT_ALLOCNO_P(A1, A2) \ (ALLOCNO_MIN (A1) <= ALLOCNO_CONFLICT_ID (A2) \ && ALLOCNO_CONFLICT_ID (A2) <= ALLOCNO_MAX (A1) \ - && TEST_ALLOCNO_SET_BIT (conflicts[ALLOCNO_NUM (A1)], \ - ALLOCNO_CONFLICT_ID (A2), \ - ALLOCNO_MIN (A1), \ - ALLOCNO_MAX (A1))) + && TEST_MINMAX_SET_BIT (conflicts[ALLOCNO_NUM (A1)], \ + ALLOCNO_CONFLICT_ID (A2), \ + ALLOCNO_MIN (A1), \ + ALLOCNO_MAX (A1))) @@ -142,13 +142,13 @@ build_conflict_bit_table (void) /* Don't set up conflict for the allocno with itself. */ && num != (int) j) { - SET_ALLOCNO_SET_BIT (conflicts[num], - ALLOCNO_CONFLICT_ID (live_a), - ALLOCNO_MIN (allocno), - ALLOCNO_MAX (allocno)); - SET_ALLOCNO_SET_BIT (conflicts[j], id, - ALLOCNO_MIN (live_a), - ALLOCNO_MAX (live_a)); + SET_MINMAX_SET_BIT (conflicts[num], + ALLOCNO_CONFLICT_ID (live_a), + ALLOCNO_MIN (allocno), + ALLOCNO_MAX (allocno)); + SET_MINMAX_SET_BIT (conflicts[j], id, + ALLOCNO_MIN (live_a), + ALLOCNO_MAX (live_a)); } } } @@ -569,12 +569,12 @@ build_allocno_conflicts (ira_allocno_t a ira_allocno_t parent_a, another_a, another_parent_a; ira_allocno_t *vec; IRA_INT_TYPE *allocno_conflicts; - ira_allocno_set_iterator asi; + minmax_set_iterator asi; allocno_conflicts = conflicts[ALLOCNO_NUM (a)]; px = 0; - FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts, - ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi) + FOR_EACH_BIT_IN_MINMAX_SET (allocno_conflicts, + ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi) { another_a = ira_conflict_id_allocno_map[i]; ira_assert (ira_reg_classes_intersect_p @@ -610,8 +610,8 @@ build_allocno_conflicts (ira_allocno_t a ira_assert (parent != NULL); ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a)); parent_num = ALLOCNO_NUM (parent_a); - FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts, - ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi) + FOR_EACH_BIT_IN_MINMAX_SET (allocno_conflicts, + ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi) { another_a = ira_conflict_id_allocno_map[i]; ira_assert (ira_reg_classes_intersect_p @@ -623,10 +623,10 @@ build_allocno_conflicts (ira_allocno_t a ira_assert (ALLOCNO_NUM (another_parent_a) >= 0); ira_assert (ALLOCNO_COVER_CLASS (another_a) == ALLOCNO_COVER_CLASS (another_parent_a)); - SET_ALLOCNO_SET_BIT (conflicts[parent_num], - ALLOCNO_CONFLICT_ID (another_parent_a), - ALLOCNO_MIN (parent_a), - ALLOCNO_MAX (parent_a)); + SET_MINMAX_SET_BIT (conflicts[parent_num], + ALLOCNO_CONFLICT_ID (another_parent_a), + ALLOCNO_MIN (parent_a), + ALLOCNO_MAX (parent_a)); } } Index: gcc/ira-int.h =================================================================== --- gcc.orig/ira-int.h +++ gcc/ira-int.h @@ -567,10 +567,16 @@ extern int ira_move_loops_num, ira_addit /* Maximal value of element of array ira_reg_class_nregs. */ extern int ira_max_nregs; + +/* This page contains a bitset implementation called 'min/max sets' used to + record conflicts in IRA. + They are named min/maxs set since we keep track of a minimum and a maximum + bit number for each set representing the bounds of valid elements. Otherwise, + the implementation resembles sbitmaps in that we store an array of integers + whose bits directly represent the members of the set. */ -/* The number of bits in each element of array used to implement a bit - vector of allocnos and what type that element has. We use the - largest integer format on the host machine. */ +/* The type used as elements in the array, and the number of bits in + this type. */ #define IRA_INT_BITS HOST_BITS_PER_WIDE_INT #define IRA_INT_TYPE HOST_WIDE_INT @@ -579,7 +585,7 @@ extern int ira_max_nregs; MAX. */ #if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007) -#define SET_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \ +#define SET_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \ (({ int _min = (MIN), _max = (MAX), _i = (I); \ if (_i < _min || _i > _max) \ { \ @@ -592,7 +598,7 @@ extern int ira_max_nregs; |= ((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); })) -#define CLEAR_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \ +#define CLEAR_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \ (({ int _min = (MIN), _max = (MAX), _i = (I); \ if (_i < _min || _i > _max) \ { \ @@ -604,7 +610,7 @@ extern int ira_max_nregs; ((R)[(unsigned) (_i - _min) / IRA_INT_BITS] \ &= ~((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); })) -#define TEST_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \ +#define TEST_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \ (({ int _min = (MIN), _max = (MAX), _i = (I); \ if (_i < _min || _i > _max) \ { \ @@ -618,25 +624,24 @@ extern int ira_max_nregs; #else -#define SET_ALLOCNO_SET_BIT(R, I, MIN, MAX) \ +#define SET_MINMAX_SET_BIT(R, I, MIN, MAX) \ ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS] \ |= ((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS))) -#define CLEAR_ALLOCNO_SET_BIT(R, I, MIN, MAX) \ +#define CLEAR_MINMAX_SET_BIT(R, I, MIN, MAX) \ ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS] \ &= ~((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS))) -#define TEST_ALLOCNO_SET_BIT(R, I, MIN, MAX) \ +#define TEST_MINMAX_SET_BIT(R, I, MIN, MAX) \ ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS] \ & ((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS))) #endif -/* The iterator for allocno set implemented ed as allocno bit - vector. */ +/* The iterator for min/max sets. */ typedef struct { - /* Array containing the allocno bit vector. */ + /* Array containing the bit vector. */ IRA_INT_TYPE *vec; /* The number of the current element in the vector. */ @@ -653,13 +658,13 @@ typedef struct { /* The word of the bit vector currently visited. */ unsigned IRA_INT_TYPE word; -} ira_allocno_set_iterator; +} minmax_set_iterator; -/* Initialize the iterator I for allocnos bit vector VEC containing - minimal and maximal values MIN and MAX. */ +/* Initialize the iterator I for bit vector VEC containing minimal and + maximal values MIN and MAX. */ static inline void -ira_allocno_set_iter_init (ira_allocno_set_iterator *i, - IRA_INT_TYPE *vec, int min, int max) +minmax_set_iter_init (minmax_set_iterator *i, IRA_INT_TYPE *vec, int min, + int max) { i->vec = vec; i->word_num = 0; @@ -669,11 +674,11 @@ ira_allocno_set_iter_init (ira_allocno_s i->word = i->nel == 0 ? 0 : vec[0]; } -/* Return TRUE if we have more allocnos to visit, in which case *N is - set to the allocno number to be visited. Otherwise, return +/* Return TRUE if we have more elements to visit, in which case *N is + set to the number of the element to be visited. Otherwise, return FALSE. */ static inline bool -ira_allocno_set_iter_cond (ira_allocno_set_iterator *i, int *n) +minmax_set_iter_cond (minmax_set_iterator *i, int *n) { /* Skip words that are zeros. */ for (; i->word == 0; i->word = i->vec[i->word_num]) @@ -695,23 +700,23 @@ ira_allocno_set_iter_cond (ira_allocno_s return true; } -/* Advance to the next allocno in the set. */ +/* Advance to the next element in the set. */ static inline void -ira_allocno_set_iter_next (ira_allocno_set_iterator *i) +minmax_set_iter_next (minmax_set_iterator *i) { i->word >>= 1; i->bit_num++; } -/* Loop over all elements of allocno set given by bit vector VEC and +/* Loop over all elements of a min/max set given by bit vector VEC and their minimal and maximal values MIN and MAX. In each iteration, N is set to the number of next allocno. ITER is an instance of - ira_allocno_set_iterator used to iterate the allocnos in the set. */ -#define FOR_EACH_ALLOCNO_IN_SET(VEC, MIN, MAX, N, ITER) \ - for (ira_allocno_set_iter_init (&(ITER), (VEC), (MIN), (MAX)); \ - ira_allocno_set_iter_cond (&(ITER), &(N)); \ - ira_allocno_set_iter_next (&(ITER))) - + minmax_set_iterator used to iterate over the set. */ +#define FOR_EACH_BIT_IN_MINMAX_SET(VEC, MIN, MAX, N, ITER) \ + for (minmax_set_iter_init (&(ITER), (VEC), (MIN), (MAX)); \ + minmax_set_iter_cond (&(ITER), &(N)); \ + minmax_set_iter_next (&(ITER))) + /* ira.c: */ /* Map: hard regs X modes -> set of hard registers for storing value Index: gcc/ira-build.c =================================================================== --- gcc.orig/ira-build.c +++ gcc/ira-build.c @@ -670,7 +670,7 @@ add_to_allocno_conflicts (ira_allocno_t } ALLOCNO_MAX (a1) = id; } - SET_ALLOCNO_SET_BIT (vec, id, ALLOCNO_MIN (a1), ALLOCNO_MAX (a1)); + SET_MINMAX_SET_BIT (vec, id, ALLOCNO_MIN (a1), ALLOCNO_MAX (a1)); } }