From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 76482 invoked by alias); 2 Oct 2015 09:18:45 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 76461 invoked by uid 89); 2 Oct 2015 09:18:45 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.4 required=5.0 tests=AWL,BAYES_40,KAM_ASCII_DIVIDERS,KAM_LAZY_DOMAIN_SECURITY,RCVD_IN_DNSWL_LOW autolearn=no version=3.3.2 X-HELO: smtp.eu.adacore.com Received: from mel.act-europe.fr (HELO smtp.eu.adacore.com) (194.98.77.210) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 02 Oct 2015 09:18:43 +0000 Received: from localhost (localhost [127.0.0.1]) by filtered-smtp.eu.adacore.com (Postfix) with ESMTP id 81A6F2F9BC32 for ; Fri, 2 Oct 2015 11:18:40 +0200 (CEST) Received: from smtp.eu.adacore.com ([127.0.0.1]) by localhost (smtp.eu.adacore.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id gmFiZ1CmBRaX for ; Fri, 2 Oct 2015 11:18:40 +0200 (CEST) Received: from polaris.localnet (bon31-6-88-161-99-133.fbx.proxad.net [88.161.99.133]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by smtp.eu.adacore.com (Postfix) with ESMTPSA id 3F7592F9BC20 for ; Fri, 2 Oct 2015 11:18:40 +0200 (CEST) From: Eric Botcazou To: gcc-patches@gcc.gnu.org Subject: [Ada] Implement restricted aliasing for parameters Date: Fri, 02 Oct 2015 09:18:00 -0000 Message-ID: <84932960.2kzfNaknKQ@polaris> User-Agent: KMail/4.7.2 (Linux/3.1.10-1.29-desktop; KDE/4.7.2; x86_64; ; ) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="nextPart7047705.yHJvfIbFn4" Content-Transfer-Encoding: 7Bit X-SW-Source: 2015-10/txt/msg00177.txt.bz2 --nextPart7047705.yHJvfIbFn4 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Content-length: 1632 In Ada, parameters can be passed by reference or by copy and, for some types, the mechanism is specified by the language whereas, for other types, it's up to the implementation. In the former case, if the mechanism is by reference, full aliasing is allowed between parameters but, in the latter case, if the mechanism is by reference, only a limited form of aliasing is allowed (it's equivalent to what the language would allow if the mechanism was by copy). So it's a weaker than 'restrict', in particular WAR (aka anti-) dependence must be honored between parameters, but it nevertheless makes it possible to vectorize certain classes of loops by making the iterations independent. The patch implements minimal support for this by means of pragma ivdep. Tested on x86_64-suse-linux, applied on the mainline. 2015-10-02 Eric Botcazou * gcc-interface/ada-tree.h (DECL_RESTRICTED_ALIASING_P): New flag. * gcc-interface/decl.c (gnat_to_gnu_param): For parameters passed by reference but whose type isn't by-ref and whose mechanism hasn't been forced to by-ref, set the DECL_RESTRICTED_ALIASING_P flag directly on them instead of changing their type. * gcc-interface/trans.c (scan_rhs_r): New helper function. (independent_iterations_p): New predicate. (Loop_Statement_to_gnu): For a loop with an iteration scheme, set an ivdep pragma if the iterations are independent. 2015-10-02 Eric Botcazou * gnat.dg/vect15.ad[sb]: New test. * gnat.dg/vect16.ad[sb]: Likewise. * gnat.dg/vect17.ad[sb]: Likewise. * gnat.dg/vect18.ad[sb]: Likewise. -- Eric Botcazou --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="p.diff" Content-Transfer-Encoding: 7Bit Content-Type: text/x-patch; charset="UTF-8"; name="p.diff" Content-length: 6412 Index: gcc-interface/decl.c =================================================================== --- gcc-interface/decl.c (revision 228315) +++ gcc-interface/decl.c (working copy) @@ -5585,6 +5585,7 @@ gnat_to_gnu_param (Entity_Id gnat_param, bool ro_param = in_param && !Address_Taken (gnat_param); bool by_return = false, by_component_ptr = false; bool by_ref = false; + bool restricted_aliasing_p = false; tree gnu_param; /* Copy-return is used only for the first parameter of a valued procedure. @@ -5675,15 +5676,12 @@ gnat_to_gnu_param (Entity_Id gnat_param, || (!foreign && default_pass_by_ref (gnu_param_type))))) { + gnu_param_type = build_reference_type (gnu_param_type); /* We take advantage of 6.2(12) by considering that references built for parameters whose type isn't by-ref and for which the mechanism hasn't - been forced to by-ref are restrict-qualified in the C sense. */ - bool restrict_p + been forced to by-ref allow only a restricted form of aliasing. */ + restricted_aliasing_p = !TYPE_IS_BY_REFERENCE_P (gnu_param_type) && mech != By_Reference; - gnu_param_type = build_reference_type (gnu_param_type); - if (restrict_p) - gnu_param_type - = change_qualified_type (gnu_param_type, TYPE_QUAL_RESTRICT); by_ref = true; } @@ -5731,6 +5729,7 @@ gnat_to_gnu_param (Entity_Id gnat_param, DECL_POINTS_TO_READONLY_P (gnu_param) = (ro_param && (by_ref || by_component_ptr)); DECL_CAN_NEVER_BE_NULL_P (gnu_param) = Can_Never_Be_Null (gnat_param); + DECL_RESTRICTED_ALIASING_P (gnu_param) = restricted_aliasing_p; /* If no Mechanism was specified, indicate what we're using, then back-annotate it. */ Index: gcc-interface/trans.c =================================================================== --- gcc-interface/trans.c (revision 228373) +++ gcc-interface/trans.c (working copy) @@ -2714,6 +2714,89 @@ can_be_lower_p (tree val1, tree val2) return tree_int_cst_lt (val1, val2); } +/* Helper function for walk_tree, used by independent_iterations_p below. */ + +static tree +scan_rhs_r (tree *tp, int *walk_subtrees, void *data) +{ + bitmap *params = (bitmap *)data; + tree t = *tp; + + /* No need to walk into types or decls. */ + if (IS_TYPE_OR_DECL_P (t)) + *walk_subtrees = 0; + + if (TREE_CODE (t) == PARM_DECL && bitmap_bit_p (*params, DECL_UID (t))) + return t; + + return NULL_TREE; +} + +/* Return true if STMT_LIST generates independent iterations in a loop. */ + +static bool +independent_iterations_p (tree stmt_list) +{ + tree_stmt_iterator tsi; + bitmap params = BITMAP_GGC_ALLOC(); + auto_vec rhs; + tree iter; + int i; + + if (TREE_CODE (stmt_list) == BIND_EXPR) + stmt_list = BIND_EXPR_BODY (stmt_list); + + /* Scan the list and return false on anything that is not either a check + or an assignment to a parameter with restricted aliasing. */ + for (tsi = tsi_start (stmt_list); !tsi_end_p (tsi); tsi_next (&tsi)) + { + tree stmt = tsi_stmt (tsi); + + switch (TREE_CODE (stmt)) + { + case COND_EXPR: + { + if (COND_EXPR_ELSE (stmt)) + return false; + if (TREE_CODE (COND_EXPR_THEN (stmt)) != CALL_EXPR) + return false; + tree func = get_callee_fndecl (COND_EXPR_THEN (stmt)); + if (!(func && TREE_THIS_VOLATILE (func))) + return false; + break; + } + + case MODIFY_EXPR: + { + tree lhs = TREE_OPERAND (stmt, 0); + while (handled_component_p (lhs)) + lhs = TREE_OPERAND (lhs, 0); + if (TREE_CODE (lhs) != INDIRECT_REF) + return false; + lhs = TREE_OPERAND (lhs, 0); + if (!(TREE_CODE (lhs) == PARM_DECL + && DECL_RESTRICTED_ALIASING_P (lhs))) + return false; + bitmap_set_bit (params, DECL_UID (lhs)); + rhs.safe_push (TREE_OPERAND (stmt, 1)); + break; + } + + default: + return false; + } + } + + /* At this point we know that the list contains only statements that will + modify parameters with restricted aliasing. Check that the statements + don't at the time read from these parameters. */ + FOR_EACH_VEC_ELT (rhs, i, iter) + if (walk_tree_without_duplicates (&iter, scan_rhs_r, ¶ms)) + return false; + + return true; +} + /* Subroutine of gnat_to_gnu to translate gnat_node, an N_Loop_Statement, to a GCC tree, which is returned. */ @@ -3038,6 +3121,13 @@ Loop_Statement_to_gnu (Node_Id gnat_node add_stmt_with_node_force (rci->invariant_cond, gnat_node); } + /* Second, if loop vectorization is enabled and the iterations of the + loop can easily be proved as independent, mark the loop. */ + if (optimize + && flag_tree_loop_vectorize + && independent_iterations_p (LOOP_STMT_BODY (gnu_loop_stmt))) + LOOP_STMT_IVDEP (gnu_loop_stmt) = 1; + add_stmt (gnu_loop_stmt); gnat_poplevel (); gnu_loop_stmt = end_stmt_group (); Index: gcc-interface/ada-tree.h =================================================================== --- gcc-interface/ada-tree.h (revision 228315) +++ gcc-interface/ada-tree.h (working copy) @@ -369,6 +369,21 @@ do { \ in the main unit, i.e. the full declaration is available. */ #define DECL_TAFT_TYPE_P(NODE) DECL_LANG_FLAG_0 (TYPE_DECL_CHECK (NODE)) +/* Nonzero in a PARM_DECL passed by reference but for which only a restricted + form of aliasing is allowed. The first restriction comes explicitly from + the RM 6.2(12) clause: there is no read-after-write dependency between a + store based on such a PARM_DECL and a load not based on this PARM_DECL, + so stores based on such PARM_DECLs can be sunk past all loads based on + a distinct object. The second restriction can be inferred from the same + clause: there is no write-after-write dependency between a store based + on such a PARM_DECL and a store based on a distinct such PARM_DECL, as + the compiler would be allowed to pass the parameters by copy and the + order of assignment to actual parameters after a call is arbitrary as + per the RM 6.4.1(17) clause, so stores based on distinct such PARM_DECLs + can be swapped. */ +#define DECL_RESTRICTED_ALIASING_P(NODE) \ + DECL_LANG_FLAG_0 (PARM_DECL_CHECK (NODE)) + /* Nonzero in a DECL if it is always used by reference, i.e. an INDIRECT_REF is needed to access the object. */ #define DECL_BY_REF_P(NODE) DECL_LANG_FLAG_1 (NODE) --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect15.ads" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect15.ads" Content-length: 163 package Vect15 is type Sarray is array (1 .. 4) of Long_Float; for Sarray'Alignment use 16; procedure Add (X, Y : Sarray; R : out Sarray); end Vect15; --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect15.adb" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect15.adb" Content-length: 362 -- { dg-do compile { target i?86-*-* x86_64-*-* } } -- { dg-options "-O3 -msse2 -fdump-tree-vect-details" } package body Vect15 is procedure Add (X, Y : Sarray; R : out Sarray) is begin for I in Sarray'Range loop R(I) := X(I) + Y(I); end loop; end; end Vect15; -- { dg-final { scan-tree-dump-not "possible aliasing" "vect" } } --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect17.ads" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect17.ads" Content-length: 179 package Vect17 is type Sarray is array (1 .. 4) of Long_Float; for Sarray'Alignment use 16; procedure Add (X, Y : aliased Sarray; R : aliased out Sarray); end Vect17; --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect16.adb" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect16.adb" Content-length: 398 -- { dg-do compile { target i?86-*-* x86_64-*-* } } -- { dg-options "-O3 -msse2 -fdump-tree-vect-details" } package body Vect16 is procedure Add_Sub (X, Y : Sarray; R,S : out Sarray) is begin for I in Sarray'Range loop R(I) := X(I) + Y(I); S(I) := X(I) - Y(I); end loop; end; end Vect16; -- { dg-final { scan-tree-dump-not "possible aliasing" "vect" } } --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect16.ads" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect16.ads" Content-length: 169 package Vect16 is type Sarray is array (1 .. 4) of Long_Float; for Sarray'Alignment use 16; procedure Add_Sub (X, Y : Sarray; R,S : out Sarray); end Vect16; --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect17.adb" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect17.adb" Content-length: 374 -- { dg-do compile { target i?86-*-* x86_64-*-* } } -- { dg-options "-O3 -msse2 -fdump-tree-vect-details" } package body Vect17 is procedure Add (X, Y : aliased Sarray; R : aliased out Sarray) is begin for I in Sarray'Range loop R(I) := X(I) + Y(I); end loop; end; end Vect17; -- { dg-final { scan-tree-dump "possible aliasing" "vect" } } --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect18.adb" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect18.adb" Content-length: 432 -- { dg-do compile { target i?86-*-* x86_64-*-* } } -- { dg-options "-O3 -msse2 -fdump-tree-vect-details" } package body Vect18 is procedure Comp (X, Y : Sarray; R : in out Sarray) is Tmp : Long_Float := R(4); begin for I in 1 .. 3 loop R(I+1) := R(I) + X(I) + Y(I); end loop; R(1) := Tmp + X(4) + Y(4); end; end Vect18; -- { dg-final { scan-tree-dump "bad data dependence" "vect" } } --nextPart7047705.yHJvfIbFn4 Content-Disposition: attachment; filename="vect18.ads" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="vect18.ads" Content-length: 167 package Vect18 is type Sarray is array (1 .. 4) of Long_Float; for Sarray'Alignment use 16; procedure Comp (X, Y : Sarray; R : in out Sarray); end Vect18; --nextPart7047705.yHJvfIbFn4--