From patchwork Mon Aug 4 14:23:06 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Roman Gareev X-Patchwork-Id: 376339 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4828A140080 for ; Tue, 5 Aug 2014 00:23:37 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; q=dns; s=default; b=KW+Qf6tRWQB0tegV/m lUTpABZM3lx1tTe0O0Nm12jke5cxAE7qHCR6evUsVXrDw4RWhaEhsSAtc8saYR35 3dynZXErqcGGJK/js1e95anAyZIK/qHRbNCy1hED4mikSjm21ROt6D25gC6CP+W1 YB6MzYS7r94I9ydL7teelALbE= 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 :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; s=default; bh=VDu9veeE//ud8C9NZwx2braN kxo=; b=tozW11kwmmjYM3+T9EyQhnMLTUBvLL2AEiUq8REhZVfaJA7lIcU5Unb3 Z0IqL2oBxQV+Qp6Ja5muSi22niMvAD6xiKbk/7cP88xpC6XRxbXCJpXYjVl4JKmZ pGd8L4IicxFCkaRN/iX9yOas6G1b/IliP86WtOQbFBhj34ngvCE= Received: (qmail 31565 invoked by alias); 4 Aug 2014 14:23:14 -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 31528 invoked by uid 89); 4 Aug 2014 14:23:12 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-yh0-f48.google.com Received: from mail-yh0-f48.google.com (HELO mail-yh0-f48.google.com) (209.85.213.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 04 Aug 2014 14:23:09 +0000 Received: by mail-yh0-f48.google.com with SMTP id i57so4289492yha.35 for ; Mon, 04 Aug 2014 07:23:07 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.236.166.138 with SMTP id g10mr3408094yhl.197.1407162187174; Mon, 04 Aug 2014 07:23:07 -0700 (PDT) Received: by 10.170.85.194 with HTTP; Mon, 4 Aug 2014 07:23:06 -0700 (PDT) In-Reply-To: <53DF2ACD.5050509@grosser.es> References: <53DA5F0C.9070002@grosser.es> <53DCBC2D.4090604@grosser.es> <53DE454C.60008@grosser.es> <53DF2ACD.5050509@grosser.es> Date: Mon, 4 Aug 2014 20:23:06 +0600 Message-ID: Subject: Re: [GSoC] checking for the loop parallelism From: Roman Gareev To: Tobias Grosser Cc: Mircea Namolaru , gcc-patches@gcc.gnu.org > I would expect the to mark the i loop as non-parallel, but the j-loop > as parallel. What is the partial schedule, the set of dependences and > the dimension you check for both the i and the j loop? Yes, you are right. The i loop is non-parallel and j-loop is parallel. I've found that this substraction “ int dimension = isl_space_dim (schedule_space, isl_dim_out) – 1;” was wrong. The attached patch contains the improved version of checking for the loop parallelism, which passes all the tests from libgomp/testsuite/libgomp.graphite except graphite-isl-ast-to-gimple.c. P.S.: I've added checking of the ux's emptiness and of the x's value, because ux is empty for specific test cases and produces the following error: “/home/roman/graphite_stuff/isl-0.12.2/isl_union_map.c:418: union map needs to contain elements in exactly one space” Index: gcc/graphite-dependences.c =================================================================== --- gcc/graphite-dependences.c (revision 213256) +++ gcc/graphite-dependences.c (working copy) @@ -53,6 +53,35 @@ #include "graphite-poly.h" #include "graphite-htab.h" +isl_union_map * +scop_get_dependences (scop_p scop) +{ + isl_union_map *dependences; + + if (!scop->must_raw) + compute_deps (scop, SCOP_BBS (scop), + &scop->must_raw, &scop->may_raw, + &scop->must_raw_no_source, &scop->may_raw_no_source, + &scop->must_war, &scop->may_war, + &scop->must_war_no_source, &scop->may_war_no_source, + &scop->must_waw, &scop->may_waw, + &scop->must_waw_no_source, &scop->may_waw_no_source); + + dependences = isl_union_map_copy (scop->must_raw); + dependences = isl_union_map_union (dependences, + isl_union_map_copy (scop->must_war)); + dependences = isl_union_map_union (dependences, + isl_union_map_copy (scop->must_waw)); + dependences = isl_union_map_union (dependences, + isl_union_map_copy (scop->may_raw)); + dependences = isl_union_map_union (dependences, + isl_union_map_copy (scop->may_war)); + dependences = isl_union_map_union (dependences, + isl_union_map_copy (scop->may_waw)); + + return dependences; +} + /* Add the constraints from the set S to the domain of MAP. */ static isl_map * @@ -263,6 +292,11 @@ ux = isl_union_map_copy (deps); ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans)); ux = isl_union_map_apply_range (ux, trans); + if (isl_union_map_is_empty (ux)) + { + isl_union_map_free (ux); + return NULL; + } x = isl_map_from_union_map (ux); return x; @@ -300,7 +334,7 @@ in which all the inputs before DEPTH occur at the same time as the output, and the input at DEPTH occurs before output. */ -static bool +bool carries_deps (__isl_keep isl_union_map *schedule, __isl_keep isl_union_map *deps, int depth) @@ -315,6 +349,8 @@ return false; x = apply_schedule_on_deps (schedule, deps); + if (x == NULL) + return false; space = isl_map_get_space (x); space = isl_space_range (space); lex = isl_map_lex_le (space); Index: gcc/graphite-isl-ast-to-gimple.c =================================================================== --- gcc/graphite-isl-ast-to-gimple.c (revision 213262) +++ gcc/graphite-isl-ast-to-gimple.c (working copy) @@ -73,6 +73,14 @@ static int graphite_expression_type_precision = 128 <= max_mode_int_precision ? 128 : max_mode_int_precision; +struct ast_build_info +{ + ast_build_info() + : is_parallelizable(false) + { }; + bool is_parallelizable; +}; + /* Converts a GMP constant VAL to a tree and returns it. */ static tree @@ -435,7 +443,15 @@ redirect_edge_succ_nodup (next_e, after); set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); - /* TODO: Add checking for the loop parallelism. */ + if (flag_loop_parallelize_all) + { + isl_id *id = isl_ast_node_get_annotation (node_for); + gcc_assert (id); + ast_build_info *for_info = (ast_build_info *) isl_id_get_user (id); + loop->can_be_parallel = for_info->is_parallelizable; + free (for_info); + isl_id_free (id); + } return last_e; } @@ -834,6 +850,23 @@ return schedule_isl; } +/* This method is executed before the construction of a for node. */ +static __isl_give isl_id * +ast_build_before_for (__isl_keep isl_ast_build *build, void *user) +{ + isl_union_map *dependences = (isl_union_map *) user; + ast_build_info *for_info = XNEW (struct ast_build_info); + isl_union_map *schedule = isl_ast_build_get_schedule (build); + isl_space *schedule_space = isl_ast_build_get_schedule_space (build); + int dimension = isl_space_dim (schedule_space, isl_dim_out); + for_info->is_parallelizable = + !carries_deps (schedule, dependences, dimension); + isl_union_map_free (schedule); + isl_space_free (schedule_space); + isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info); + return id; +} + static __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop, ivs_params &ip) { @@ -846,8 +879,18 @@ add_parameters_to_ivs_params (scop, ip); isl_union_map *schedule_isl = generate_isl_schedule (scop); isl_ast_build *context_isl = generate_isl_context (scop); + isl_union_map *dependences = NULL; + if (flag_loop_parallelize_all) + { + dependences = scop_get_dependences (scop); + context_isl = + isl_ast_build_set_before_each_for (context_isl, ast_build_before_for, + dependences); + } isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl, schedule_isl); + if(dependences) + isl_union_map_free (dependences); isl_ast_build_free (context_isl); return ast_isl; } @@ -908,7 +951,20 @@ ivs_params_clear (ip); isl_ast_node_free (root_node); timevar_pop (TV_GRAPHITE_CODE_GEN); - /* TODO: Add dump */ + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + loop_p loop; + int num_no_dependency = 0; + + FOR_EACH_LOOP (loop, 0) + if (loop->can_be_parallel) + num_no_dependency++; + + fprintf (dump_file, "\n%d loops carried no dependency.\n", + num_no_dependency); + } + return !graphite_regenerate_error; } #endif Index: gcc/graphite-optimize-isl.c =================================================================== --- gcc/graphite-optimize-isl.c (revision 213256) +++ gcc/graphite-optimize-isl.c (working copy) @@ -65,35 +65,6 @@ return res; } -static isl_union_map * -scop_get_dependences (scop_p scop) -{ - isl_union_map *dependences; - - if (!scop->must_raw) - compute_deps (scop, SCOP_BBS (scop), - &scop->must_raw, &scop->may_raw, - &scop->must_raw_no_source, &scop->may_raw_no_source, - &scop->must_war, &scop->may_war, - &scop->must_war_no_source, &scop->may_war_no_source, - &scop->must_waw, &scop->may_waw, - &scop->must_waw_no_source, &scop->may_waw_no_source); - - dependences = isl_union_map_copy (scop->must_raw); - dependences = isl_union_map_union (dependences, - isl_union_map_copy (scop->must_war)); - dependences = isl_union_map_union (dependences, - isl_union_map_copy (scop->must_waw)); - dependences = isl_union_map_union (dependences, - isl_union_map_copy (scop->may_raw)); - dependences = isl_union_map_union (dependences, - isl_union_map_copy (scop->may_war)); - dependences = isl_union_map_union (dependences, - isl_union_map_copy (scop->may_waw)); - - return dependences; -} - /* getTileMap - Create a map that describes a n-dimensonal tiling. getTileMap creates a map from a n-dimensional scattering space into an Index: gcc/graphite-poly.h =================================================================== --- gcc/graphite-poly.h (revision 213256) +++ gcc/graphite-poly.h (working copy) @@ -1551,4 +1551,12 @@ isl_union_map **must_waw_no_source, isl_union_map **may_waw_no_source); +isl_union_map * +scop_get_dependences (scop_p scop); + +bool +carries_deps (__isl_keep isl_union_map *schedule, + __isl_keep isl_union_map *deps, + int depth); + #endif