From patchwork Wed Feb 6 09:24:39 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1037376 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-495366-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="gFYZKjO/"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 43vbd11LDyz9s6w for ; Wed, 6 Feb 2019 20:24:52 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=Nd2/k8bHyZhH7CA+92d721yA1Ee/GT+ZzV1PmEeMqBQisVByVU+Wk CTOnysk7+DMLgu4vOsdKq21j5a9044xxCyN8dtNic150OpnpPlLKJT5VpjBbcUJE jNw7t3EZniN+JBaIRZRtElegdJXPAnN952GJQ0G7tD0do9mztCu3KI= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=lJc/X1luSWPDrZTooQPN7vkkZxw=; b=gFYZKjO/jvsHg1U+HdlS fiNvmtpQPyfB5eZVaUfTE4pz2Izv0TciF/hVjR9grSoJzdO4o2In429dWqOs9K4A bbd2/XHG8CrLfI/O8a1VmT25LHyPiMwX7yffHrhoaVPcHsCpkf/8G8SZK5dOaQ+D jWy9R0/YO7xK6yh4tXFW5wE= Received: (qmail 110292 invoked by alias); 6 Feb 2019 09:24:44 -0000 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 Received: (qmail 110279 invoked by uid 89); 6 Feb 2019 09:24:44 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-10.6 required=5.0 tests=BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, KAM_NUMSUBJECT, SPF_PASS autolearn=ham version=3.3.2 spammy=hole X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 06 Feb 2019 09:24:42 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 0E78EB699 for ; Wed, 6 Feb 2019 09:24:40 +0000 (UTC) Date: Wed, 6 Feb 2019 10:24:39 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix PR89182 Message-ID: User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 This adds a cache around scalar_evolution_in_region avoiding re-analysis during code-generation where out-of-date SSA form can cause minor differences in SCEV analysis (follow_copies_to_constant ...). Bootstrap and regtest running on x86_64-unknown-linux-gnu. It leaves a (tiny) hole via scev_analyzable_p but I refrained from more refactoring at this point w/o a good reason (testcase). Richard. 2019-02-06 Richard Biener PR tree-optimization/89182 * graphite.h (cached_scalar_evolution_in_region): Declare. * graphite.c (struct seir_cache_key): New. (struct sese_scev_hash): Likewise. (seir_cache): New global. (cached_scalar_evolution_in_region): New function. (graphite_transform_loops): Allocate and release seir_cache. * graphite-isl-ast-to-gimple.c (get_rename_from_scev): Use cached_scalar_evolution_in_region. * graphite-scop-detection.c (scop_detection::can_represent_loop): Simplify. (scop_detection::graphite_can_represent_expr: Use cached_scalar_evolution_in_region. (scop_detection::stmt_simple_for_scop_p): Likewise. (find_params_in_bb): Likewise. (gather_bbs::before_dom_children): Likewise. * graphite-sese-to-poly.c (create_pw_aff_from_tree): Likewise. (add_loop_constraints): Likewise. * gfortran.dg/graphite/pr89182.f90: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c =================================================================== --- gcc/graphite-isl-ast-to-gimple.c (revision 268572) +++ gcc/graphite-isl-ast-to-gimple.c (working copy) @@ -1092,7 +1092,8 @@ tree translate_isl_ast_to_gimple:: get_rename_from_scev (tree old_name, gimple_seq *stmts, loop_p loop, vec iv_map) { - tree scev = scalar_evolution_in_region (region->region, loop, old_name); + tree scev = cached_scalar_evolution_in_region (region->region, + loop, old_name); /* At this point we should know the exact scev for each scalar SSA_NAME used in the scop: all the other scalar Index: gcc/graphite-scop-detection.c =================================================================== --- gcc/graphite-scop-detection.c (revision 268572) +++ gcc/graphite-scop-detection.c (working copy) @@ -568,8 +568,6 @@ scop_detection::can_represent_loop (loop && niter_desc.control.no_overflow && (niter = number_of_latch_executions (loop)) && !chrec_contains_undetermined (niter) - && !chrec_contains_undetermined (scalar_evolution_in_region (scop, - loop, niter)) && graphite_can_represent_expr (scop, loop, niter); } @@ -924,7 +922,7 @@ bool scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop, tree expr) { - tree scev = scalar_evolution_in_region (scop, loop, expr); + tree scev = cached_scalar_evolution_in_region (scop, loop, expr); return graphite_can_represent_scev (scop, scev); } @@ -1061,7 +1059,8 @@ scop_detection::stmt_simple_for_scop_p ( FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) if (scev_analyzable_p (op, scop) && chrec_contains_undetermined - (scalar_evolution_in_region (scop, bb->loop_father, op))) + (cached_scalar_evolution_in_region (scop, + bb->loop_father, op))) { DEBUG_PRINT (dp << "[scop-detection-fail] " << "Graphite cannot code-gen stmt:\n"; @@ -1190,10 +1189,10 @@ find_params_in_bb (sese_info_p region, g FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) { loop_p loop = gimple_bb (stmt)->loop_father; - tree lhs = scalar_evolution_in_region (region->region, loop, - gimple_cond_lhs (stmt)); - tree rhs = scalar_evolution_in_region (region->region, loop, - gimple_cond_rhs (stmt)); + tree lhs = cached_scalar_evolution_in_region (region->region, loop, + gimple_cond_lhs (stmt)); + tree rhs = cached_scalar_evolution_in_region (region->region, loop, + gimple_cond_rhs (stmt)); gcc_assert (!chrec_contains_undetermined (lhs) && !chrec_contains_undetermined (rhs)); @@ -1492,8 +1491,8 @@ gather_bbs::before_dom_children (basic_b tree nb_iters = number_of_latch_executions (loop); if (chrec_contains_symbols (nb_iters)) { - nb_iters = scalar_evolution_in_region (region->region, - loop, nb_iters); + nb_iters = cached_scalar_evolution_in_region (region->region, + loop, nb_iters); scan_tree_for_params (region, nb_iters); } } Index: gcc/graphite-sese-to-poly.c =================================================================== --- gcc/graphite-sese-to-poly.c (revision 268572) +++ gcc/graphite-sese-to-poly.c (working copy) @@ -328,7 +328,7 @@ create_pw_aff_from_tree (poly_bb_p pbb, { scop_p scop = PBB_SCOP (pbb); - t = scalar_evolution_in_region (scop->scop_info->region, loop, t); + t = cached_scalar_evolution_in_region (scop->scop_info->region, loop, t); gcc_assert (!chrec_contains_undetermined (t)); gcc_assert (!automatically_generated_chrec_p (t)); @@ -782,7 +782,7 @@ add_loop_constraints (scop_p scop, __isl } /* loop_i <= expr_nb_iters */ gcc_assert (!chrec_contains_undetermined (nb_iters)); - nb_iters = scalar_evolution_in_region (region, loop, nb_iters); + nb_iters = cached_scalar_evolution_in_region (region, loop, nb_iters); gcc_assert (!chrec_contains_undetermined (nb_iters)); isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters, Index: gcc/graphite.c =================================================================== --- gcc/graphite.c (revision 268572) +++ gcc/graphite.c (working copy) @@ -210,6 +210,63 @@ print_graphite_statistics (FILE* file, v print_graphite_scop_statistics (file, scop); } +struct seir_cache_key +{ + hashval_t hash; + int entry_dest; + int exit_src; + int loop_num; + tree expr; +}; + +struct sese_scev_hash : typed_noop_remove +{ + typedef seir_cache_key value_type; + typedef seir_cache_key compare_type; + static hashval_t hash (const seir_cache_key &key) { return key.hash; } + static bool + equal (const seir_cache_key &key1, const seir_cache_key &key2) + { + return (key1.hash == key2.hash + && key1.entry_dest == key2.entry_dest + && key1.exit_src == key2.exit_src + && key1.loop_num == key2.loop_num + && operand_equal_p (key1.expr, key2.expr, 0)); + } + static void mark_deleted (seir_cache_key &key) { key.expr = NULL_TREE; } + static void mark_empty (seir_cache_key &key) { key.entry_dest = 0; } + static bool is_deleted (const seir_cache_key &key) { return !key.expr; } + static bool is_empty (const seir_cache_key &key) { return key.entry_dest == 0; } +}; + +static hash_map *seir_cache; + +/* Same as scalar_evolution_in_region but caches results so we avoid + re-computing evolutions during transform phase. */ + +tree +cached_scalar_evolution_in_region (const sese_l ®ion, loop_p loop, + tree expr) +{ + seir_cache_key key; + key.entry_dest = region.entry->dest->index; + key.exit_src = region.exit->src->index; + key.loop_num = loop->num; + key.expr = expr; + inchash::hash hstate (0); + hstate.add_int (key.entry_dest); + hstate.add_int (key.exit_src); + hstate.add_int (key.loop_num); + inchash::add_expr (key.expr, hstate); + key.hash = hstate.end (); + + bool existed; + tree &chrec = seir_cache->get_or_insert (key, &existed); + if (!existed) + chrec = scalar_evolution_in_region (region, loop, expr); + return chrec; +} + /* Deletes all scops in SCOPS. */ static void @@ -385,6 +442,8 @@ graphite_transform_loops (void) print_loops (dump_file, 3); } + seir_cache = new hash_map; + calculate_dominance_info (CDI_POST_DOMINATORS); build_scops (&scops); free_dominance_info (CDI_POST_DOMINATORS); @@ -420,6 +479,9 @@ graphite_transform_loops (void) } } + delete seir_cache; + seir_cache = NULL; + if (changed) { mark_virtual_operands_for_renaming (cfun); Index: gcc/graphite.h =================================================================== --- gcc/graphite.h (revision 268572) +++ gcc/graphite.h (working copy) @@ -460,6 +460,7 @@ carries_deps (__isl_keep isl_union_map * extern bool build_poly_scop (scop_p); extern bool graphite_regenerate_ast_isl (scop_p); extern void build_scops (vec *); +extern tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree); extern void dot_all_sese (FILE *, vec &); extern void dot_sese (sese_l &); extern void dot_cfg (); Index: gcc/testsuite/gfortran.dg/graphite/pr89182.f90 =================================================================== --- gcc/testsuite/gfortran.dg/graphite/pr89182.f90 (nonexistent) +++ gcc/testsuite/gfortran.dg/graphite/pr89182.f90 (working copy) @@ -0,0 +1,31 @@ +! { dg-do compile } +! { dg-options "-O3 -fgraphite-identity --param max-completely-peeled-insns=8" } + +MODULE hfx_contract_block + INTEGER, PARAMETER :: dp=8 +CONTAINS + SUBROUTINE contract_block(mb_max,mc_max,kbc,ks_bc) + REAL(KIND=dp) :: kbc(mb_max*mc_max), ks_bc + CALL block_1_2_1_2(kbc,ks_bc) + CALL block_1_2_1_3(kbc,ks_bc) + CALL block_1_2_1_3(kbc,ks_bc) + END SUBROUTINE contract_block + SUBROUTINE block_1_2_1_2(kbc,ks_bc) + REAL(KIND=dp) :: kbc(2*1), ks_bc + DO mc = 1,2 + DO mb = 1,2 + kbc((mc-1)*2+mb) = ks_bc + END DO + END DO + END SUBROUTINE block_1_2_1_2 + SUBROUTINE block_1_2_1_3(kbc,ks_bc) + REAL(KIND=dp) :: kbc(2*1), ks_bc + DO md = 1,3 + DO mc = 1,1 + DO mb = 1,2 + kbc((mc-1)*2+mb) = kbc((mc-1)*2+mb) - ks_bc + END DO + END DO + END DO + END SUBROUTINE block_1_2_1_3 +END MODULE hfx_contract_block