From patchwork Sun Apr 15 15:11:21 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 152629 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 CF766B6FFE for ; Mon, 16 Apr 2012 01:11:50 +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=1335107511; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:From:To:Mail-Followup-To:Subject:Date:Message-ID: User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence: List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=Q511mx1olLi6Q05sEPf+uHweGrI=; b=yhoxW+8v7pqZIKx rVCIr3XoNjMgYQfOqAaFCM3YhAh8c+vEMhEtnLOhBpligrjXUpJjzdpfuWUIrLGH 9iMO/ONCxM+LSyNvaNsW0brYlP5Dar4dpLMIOHEQPpNC8T9hyw5oFSWCbQqoC5iO SmmFmOZa0Hr5jHZqSC7NQh2QTA2w= 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:Received:From:To:Mail-Followup-To:Subject:Date:Message-ID:User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=gnuz4gYEKBRtnyQPaBAtHw6GEqYQXzwlFz9DCYi1XPemqEm74JmE1FmVlyz7D/ knYXCsIaDOiX2Eb5Is9sa7sf9ugtuMOu0MnsyghwYLpr13C0SjhfrzhL/iu9arxJ /5fBHXofslHGh4SWfxzQImfIbwQpg48SRuIZxZGfdO2SM=; Received: (qmail 23649 invoked by alias); 15 Apr 2012 15:11:44 -0000 Received: (qmail 23639 invoked by uid 22791); 15 Apr 2012 15:11:40 -0000 X-SWARE-Spam-Status: No, hits=-4.1 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_TX X-Spam-Check-By: sourceware.org Received: from mail-we0-f175.google.com (HELO mail-we0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 15 Apr 2012 15:11:25 +0000 Received: by wera1 with SMTP id a1so3224235wer.20 for ; Sun, 15 Apr 2012 08:11:23 -0700 (PDT) Received: by 10.216.137.30 with SMTP id x30mr4637374wei.34.1334502683601; Sun, 15 Apr 2012 08:11:23 -0700 (PDT) Received: from localhost (rsandifo.gotadsl.co.uk. [82.133.89.107]) by mx.google.com with ESMTPS id h8sm20695777wix.4.2012.04.15.08.11.22 (version=TLSv1/SSLv3 cipher=OTHER); Sun, 15 Apr 2012 08:11:22 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, rdsandiford@googlemail.com Subject: RFA: Clean up ADDRESS handling in alias.c Date: Sun, 15 Apr 2012 16:11:21 +0100 Message-ID: <87y5pxxc6e.fsf@talisman.home> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) MIME-Version: 1.0 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 The comment in alias.c says: The contents of an ADDRESS is not normally used, the mode of the ADDRESS determines whether the ADDRESS is a function argument or some other special value. Pointer equality, not rtx_equal_p, determines whether two ADDRESS expressions refer to the same base address. The only use of the contents of an ADDRESS is for determining if the current function performs nonlocal memory memory references for the purposes of marking the function as a constant function. */ The first paragraph is a bit misleading IMO. AFAICT, rtx_equal_p has always given ADDRESS the full recursive treatment, rather than saying that pointer equality determines ADDRESS equality. (This is in contrast to something like VALUE, where pointer equality is used.) And AFAICT we've always had: static int base_alias_check (rtx x, rtx y, enum machine_mode x_mode, enum machine_mode y_mode) { ... /* If the base addresses are equal nothing is known about aliasing. */ if (rtx_equal_p (x_base, y_base)) return 1; ... } So I think the contents of an ADDRESS _are_ used to distinguish between different bases. The second paragraph ceased to be true in 2005 when the pure/const analysis moved to its own IPA pass. Nothing now looks at the contents beyond rtx_equal_p. Also, base_alias_check effectively treats all arguments as a single base. That makes conceptual sense, because this analysis isn't strong enough to determine whether arguments are base values at all, never mind whether accesses based on different arguments conflict. But the fact that we have a single base isn't obvious from the way the code is written, because we create several separate, non-rtx_equal_p, ADDRESSes to represent arguments. See: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) /* Check whether this register can hold an incoming pointer argument. FUNCTION_ARG_REGNO_P tests outgoing register numbers, so translate if necessary due to register windows. */ if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) && HARD_REGNO_MODE_OK (i, Pmode)) static_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i)); and: /* Check for an argument passed in memory. Only record in the copying-arguments block; it is too hard to track changes otherwise. */ if (copying_arguments && (XEXP (src, 0) == arg_pointer_rtx || (GET_CODE (XEXP (src, 0)) == PLUS && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) return gen_rtx_ADDRESS (VOIDmode, src); I think it would be cleaner and less wasteful to use a single rtx for the single "base" (really "potential base"). So if we wanted to, we could now remove the operand from ADDRESS and simply rely on pointer equality. I'm a bit reluctant to do that though. It would make debugging harder, and it would mean either adding knowledge of this alias-specific code to other files (specifically rtl.c:rtx_equal_p), or adding special ADDRESS shortcuts to alias.c. But I think the code would be more obvious if we replaced the rtx operand with a unique id, which is what we already use for the REG_NOALIAS case: new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode, GEN_INT (unique_id++)); And if we do that, we can make the id a direct operand of the ADDRESS, rather than a CONST_INT subrtx[*]. That should make rtx_equal_p cheaper too. [*] I'm trying to get rid of CONST_INTs like these that have no obvious mode. All of which led to the patch below. I checked that it didn't change the code generated at -O2 for a recent set of cc1 .ii files. Also bootstrapped & regression-tested on x86_64-linux-gnu. OK to install? To cover my back: I'm just trying to rewrite the current code according to its current assumptions. Whether those assumptions are correct or not is always open to debate... Richard gcc/ * rtl.def (ADDRESS): Turn operand into a HOST_WIDE_INT. * alias.c (reg_base_value): Expand and update comment. (arg_base_value): New variable. (unique_id): Move up file. (unique_base_value, unique_base_value_p, known_base_value_p): New. (find_base_value): Use arg_base_value and known_base_value_p. (record_set): Document REG_NOALIAS handling. Use unique_base_value. (find_base_term): Use known_base_value_p. (base_alias_check): Use unique_base_value_p. (init_alias_target): Initialize arg_base_value. Use unique_base_value. (init_alias_analysis): Use 1 as the first id for REG_NOALIAS bases. Index: gcc/rtl.def =================================================================== --- gcc/rtl.def 2012-04-15 15:23:52.747632394 +0100 +++ gcc/rtl.def 2012-04-15 15:58:48.234515667 +0100 @@ -109,8 +109,8 @@ DEF_RTL_EXPR(INSN_LIST, "insn_list", "ue `emit_insn' takes the SEQUENCE apart and makes separate insns. */ DEF_RTL_EXPR(SEQUENCE, "sequence", "E", RTX_EXTRA) -/* Refers to the address of its argument. This is only used in alias.c. */ -DEF_RTL_EXPR(ADDRESS, "address", "e", RTX_MATCH) +/* Represents a non-global base address. This is only used in alias.c. */ +DEF_RTL_EXPR(ADDRESS, "address", "w", RTX_EXTRA) /* ---------------------------------------------------------------------- Expression types used for things in the instruction chain. Index: gcc/alias.c =================================================================== --- gcc/alias.c 2012-04-15 15:23:52.748632394 +0100 +++ gcc/alias.c 2012-04-15 15:59:45.073512500 +0100 @@ -187,21 +187,42 @@ #define MAX_ALIAS_LOOP_PASSES 10 of the first set. A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS - expressions represent certain special values: function arguments and - the stack, frame, and argument pointers. + expressions represent three types of base: - The contents of an ADDRESS is not normally used, the mode of the - ADDRESS determines whether the ADDRESS is a function argument or some - other special value. Pointer equality, not rtx_equal_p, determines whether - two ADDRESS expressions refer to the same base address. - - The only use of the contents of an ADDRESS is for determining if the - current function performs nonlocal memory memory references for the - purposes of marking the function as a constant function. */ + 1. incoming arguments. There is just one ADDRESS to represent all + arguments, since we do not know at this level whether accesses + based on different arguments can alias. The ADDRESS has id 0. + + 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx + (if distinct from frame_pointer_rtx) and arg_pointer_rtx. + Each of these rtxes has a separate ADDRESS associated with it, + each with a negative id. + + GCC is (and is required to be) precise in which register it + chooses to access a particular region of stack. We can therefore + assume that accesses based on one of these rtxes do not alias + accesses based on another of these rtxes. + + 3. bases that are derived from malloc()ed memory (REG_NOALIAS). + Each such piece of memory has a separate ADDRESS associated + with it, each with an id greater than 0. + + Accesses based on one ADDRESS do not alias accesses based on other + ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not + alias globals either; the ADDRESSes have Pmode to indicate this. + The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to + indicate this. */ static GTY(()) VEC(rtx,gc) *reg_base_value; static rtx *new_reg_base_value; +/* The single VOIDmode ADDRESS that represents all argument bases. + It has id 0. */ +static GTY(()) rtx arg_base_value; + +/* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */ +static int unique_id; + /* We preserve the copy of old array around to avoid amount of garbage produced. About 8% of garbage produced were attributed to this array. */ @@ -993,6 +1014,43 @@ get_frame_alias_set (void) return frame_set; } +/* Create a new, unique base with id ID. */ + +static rtx +unique_base_value (HOST_WIDE_INT id) +{ + return gen_rtx_ADDRESS (Pmode, id); +} + +/* Return true if accesses based on any other base value cannot access + those based on X. */ + +static bool +unique_base_value_p (rtx x) +{ + return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode; +} + +/* Return true if X is known to be a base value. */ + +static bool +known_base_value_p (rtx x) +{ + switch (GET_CODE (x)) + { + case LABEL_REF: + case SYMBOL_REF: + return true; + + case ADDRESS: + /* Arguments may or may not be bases; we don't know for sure. */ + return GET_MODE (x) != VOIDmode; + + default: + return false; + } +} + /* Inside SRC, the source of a SET, find a base address. */ static rtx @@ -1049,7 +1107,7 @@ find_base_value (rtx src) && (XEXP (src, 0) == arg_pointer_rtx || (GET_CODE (XEXP (src, 0)) == PLUS && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) - return gen_rtx_ADDRESS (VOIDmode, src); + return arg_base_value; return 0; case CONST: @@ -1090,18 +1148,10 @@ find_base_value (rtx src) /* If either base is named object or a special address (like an argument or stack reference), then use it for the base term. */ - if (src_0 != 0 - && (GET_CODE (src_0) == SYMBOL_REF - || GET_CODE (src_0) == LABEL_REF - || (GET_CODE (src_0) == ADDRESS - && GET_MODE (src_0) != VOIDmode))) + if (src_0 != 0 && known_base_value_p (src_0)) return src_0; - if (src_1 != 0 - && (GET_CODE (src_1) == SYMBOL_REF - || GET_CODE (src_1) == LABEL_REF - || (GET_CODE (src_1) == ADDRESS - && GET_MODE (src_1) != VOIDmode))) + if (src_1 != 0 && known_base_value_p (src_1)) return src_1; /* Guess which operand is the base address: @@ -1169,16 +1219,14 @@ find_base_value (rtx src) return 0; } -/* Called from init_alias_analysis indirectly through note_stores. */ +/* Called from init_alias_analysis indirectly through note_stores, + or directly if DEST is a register with a REG_NOALIAS note attached. + SET is null in the latter case. */ /* While scanning insns to find base values, reg_seen[N] is nonzero if register N has been set in this function. */ static char *reg_seen; -/* Addresses which are known not to alias anything else are identified - by a unique integer. */ -static int unique_id; - static void record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED) { @@ -1223,14 +1271,14 @@ record_set (rtx dest, const_rtx set, voi } else { + /* There's a REG_NOALIAS note against DEST. */ if (reg_seen[regno]) { new_reg_base_value[regno] = 0; return; } reg_seen[regno] = 1; - new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode, - GEN_INT (unique_id++)); + new_reg_base_value[regno] = unique_base_value (unique_id++); return; } @@ -1666,18 +1714,10 @@ find_base_term (rtx x) /* If either base term is named object or a special address (like an argument or stack reference), then use it for the base term. */ - if (tmp1 != 0 - && (GET_CODE (tmp1) == SYMBOL_REF - || GET_CODE (tmp1) == LABEL_REF - || (GET_CODE (tmp1) == ADDRESS - && GET_MODE (tmp1) != VOIDmode))) + if (tmp1 != 0 && known_base_value_p (tmp1)) return tmp1; - if (tmp2 != 0 - && (GET_CODE (tmp2) == SYMBOL_REF - || GET_CODE (tmp2) == LABEL_REF - || (GET_CODE (tmp2) == ADDRESS - && GET_MODE (tmp2) != VOIDmode))) + if (tmp2 != 0 && known_base_value_p (tmp2)) return tmp2; /* We could not determine which of the two operands was the @@ -1762,12 +1802,7 @@ base_alias_check (rtx x, rtx y, enum mac if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS) return 0; - /* If one address is a stack reference there can be no alias: - stack references using different base registers do not alias, - a stack reference can not alias a parameter, and a stack reference - can not alias a global. */ - if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode) - || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode)) + if (unique_base_value_p (x_base) || unique_base_value_p (y_base)) return 0; return 1; @@ -2686,6 +2721,9 @@ init_alias_target (void) { int i; + if (!arg_base_value) + arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0); + memset (static_reg_base_value, 0, sizeof static_reg_base_value); for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) @@ -2694,18 +2732,13 @@ init_alias_target (void) numbers, so translate if necessary due to register windows. */ if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) && HARD_REGNO_MODE_OK (i, Pmode)) - static_reg_base_value[i] - = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i)); + static_reg_base_value[i] = arg_base_value; - static_reg_base_value[STACK_POINTER_REGNUM] - = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx); - static_reg_base_value[ARG_POINTER_REGNUM] - = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx); - static_reg_base_value[FRAME_POINTER_REGNUM] - = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx); + static_reg_base_value[STACK_POINTER_REGNUM] = unique_base_value (-1); + static_reg_base_value[ARG_POINTER_REGNUM] = unique_base_value (-2); + static_reg_base_value[FRAME_POINTER_REGNUM] = unique_base_value (-3); #if !HARD_FRAME_POINTER_IS_FRAME_POINTER - static_reg_base_value[HARD_FRAME_POINTER_REGNUM] - = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx); + static_reg_base_value[HARD_FRAME_POINTER_REGNUM] = unique_base_value (-4); #endif } @@ -2791,8 +2824,8 @@ init_alias_analysis (void) changed = 0; /* We want to assign the same IDs each iteration of this loop, so - start counting from zero each iteration of the loop. */ - unique_id = 0; + start counting from one each iteration of the loop. */ + unique_id = 1; /* We're at the start of the function each iteration through the loop, so we're copying arguments. */