From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 52052 invoked by alias); 2 Aug 2015 18:19:01 -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 52043 invoked by uid 89); 2 Aug 2015 18:19:01 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.5 required=5.0 tests=AWL,BAYES_00,KAM_LAZY_DOMAIN_SECURITY,RCVD_IN_DNSWL_LOW autolearn=no version=3.3.2 X-HELO: mail-qk0-f179.google.com Received: from mail-qk0-f179.google.com (HELO mail-qk0-f179.google.com) (209.85.220.179) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Sun, 02 Aug 2015 18:19:00 +0000 Received: by qkdv3 with SMTP id v3so44639464qkd.3 for ; Sun, 02 Aug 2015 11:18:57 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=n7+atdhLRBGYtpc+HfmhXeSnpc/4WxVbfVveuGvUBuo=; b=K+rSxj8O8/rs3rTfBU2XN1GPAlj0YCo6n1NJSmwQJ+0sGog4Mj1JY8blIenZyNqpe+ w/ZGh9X7d+Z/Q9jfQHysUgZVlfk/3taQrhgco/zegQzXZHWrfKKlEqOBOgVFp8WkNfRw F3cZ9c5zQDwQIYVOxsy4p28qGN5FY4Xz2MxDNlpZfRl4DpKiJjzDAB40JYZWRaJuA1CX 4vNCTKLOQ/gRweYTcLe6FWkT1LbDMb7kD+hAU5G7YWtOp4jwYvd6Bidv+pTn+PEhV9VM FpRfJYHHd31TIlNcNY7EpmtdFoqeL6mkmy70s6SziHSTH8GcOR9klwY02YJbLRDK+3C3 v6bA== X-Gm-Message-State: ALoCoQl31yx1oJyFxxNFlO6zK2g3ZNBM293eV0cuZClTSGVM26du5HbWnOfii5r8dETWipOziIXv X-Received: by 10.55.48.11 with SMTP id w11mr19724619qkw.61.1438539537667; Sun, 02 Aug 2015 11:18:57 -0700 (PDT) Received: from localhost.localdomain (ool-4353acd8.dyn.optonline.net. [67.83.172.216]) by smtp.gmail.com with ESMTPSA id b93sm5626053qgb.49.2015.08.02.11.18.56 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sun, 02 Aug 2015 11:18:56 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: Patrick Palka Subject: [PATCH] Avoid recomputing multiple times the defining predicate-chain for the same PHI Date: Sun, 02 Aug 2015 18:19:00 -0000 Message-Id: <1438539531-18244-1-git-send-email-patrick@parcs.ath.cx> X-SW-Source: 2015-08/txt/msg00016.txt.bz2 In the uninit pass, the function is_use_properly_guarded is called consecutively by find_uninit_use, each time being passed the same PHI parameter, and each time we needlessly compute, simplify and normalize the same defining predicate-chain of that PHI. This patch fixes this inefficiency by tweaking is_use_properly_guarded and its callers to memoize the computation of def_preds. This should make the pass less expensive when analyzing a PHI that has multiple uses. Bootstrapped and regtested on x86_64 Linux with no regressions, OK to commit? gcc/ChangeLog: * gcc/tree-ssa-uninit.c (find_uninit_use): Declare and pass to is_use_properly_guarded the variable def_preds. Free its contents before returning. (prune_uninit_phi_opnds_in_unrealizable_paths): Same. (is_use_properly_guarded): Replace local variable def_preds with a parameter. Adjust accordingly. Only update *def_preds if it's empty. --- gcc/tree-ssa-uninit.c | 69 +++++++++++++++++++++++++++++++++------------------ 1 file changed, 45 insertions(+), 24 deletions(-) diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c index 0ed05e1..e2ac902 100644 --- a/gcc/tree-ssa-uninit.c +++ b/gcc/tree-ssa-uninit.c @@ -980,6 +980,7 @@ is_use_properly_guarded (gimple use_stmt, basic_block use_bb, gphi *phi, unsigned uninit_opnds, + pred_chain_union *def_preds, hash_set *visited_phis); /* Returns true if all uninitialized opnds are pruned. Returns false @@ -1098,14 +1099,19 @@ prune_uninit_phi_opnds_in_unrealizable_paths (gphi *phi, edge opnd_edge; unsigned uninit_opnds2 = compute_uninit_opnds_pos (opnd_def_phi); + pred_chain_union def_preds = vNULL; + bool ok; gcc_assert (!MASK_EMPTY (uninit_opnds2)); opnd_edge = gimple_phi_arg_edge (phi, i); - if (!is_use_properly_guarded (phi, - opnd_edge->src, - opnd_def_phi, - uninit_opnds2, - visited_phis)) - return false; + ok = is_use_properly_guarded (phi, + opnd_edge->src, + opnd_def_phi, + uninit_opnds2, + &def_preds, + visited_phis); + destroy_predicate_vecs (def_preds); + if (!ok) + return false; } else return false; @@ -2158,23 +2164,31 @@ normalize_preds (pred_chain_union preds, gimple use_or_def, bool is_use) true if it can be determined that the use of PHI's def in USE_STMT is guarded with a predicate set not overlapping with predicate sets of all runtime paths that do not have a definition. + Returns false if it is not or it can not be determined. USE_BB is the bb of the use (for phi operand use, the bb is not the bb of - the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS - is a bit vector. If an operand of PHI is uninitialized, the + the phi stmt, but the src bb of the operand edge). + + UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the corresponding bit in the vector is 1. VISIED_PHIS is a pointer - set of phis being visted. */ + set of phis being visted. + + *DEF_PREDS contains the (memoized) defining predicate chains of PHI. + If *DEF_PREDS is the empty vector, the defining predicate chains of + PHI will be computed and stored into *DEF_PREDS as needed. + + VISITED_PHIS is a pointer set of phis being visited. */ static bool is_use_properly_guarded (gimple use_stmt, basic_block use_bb, gphi *phi, unsigned uninit_opnds, + pred_chain_union *def_preds, hash_set *visited_phis) { basic_block phi_bb; pred_chain_union preds = vNULL; - pred_chain_union def_preds = vNULL; bool has_valid_preds = false; bool is_properly_guarded = false; @@ -2205,25 +2219,26 @@ is_use_properly_guarded (gimple use_stmt, return true; } - has_valid_preds = find_def_preds (&def_preds, phi); - - if (!has_valid_preds) + if (def_preds->is_empty ()) { - destroy_predicate_vecs (preds); - destroy_predicate_vecs (def_preds); - return false; + has_valid_preds = find_def_preds (def_preds, phi); + + if (!has_valid_preds) + { + destroy_predicate_vecs (preds); + return false; + } + + simplify_preds (def_preds, phi, false); + *def_preds = normalize_preds (*def_preds, phi, false); } simplify_preds (&preds, use_stmt, true); preds = normalize_preds (preds, use_stmt, true); - simplify_preds (&def_preds, phi, false); - def_preds = normalize_preds (def_preds, phi, false); - - is_properly_guarded = is_superset_of (def_preds, preds); + is_properly_guarded = is_superset_of (*def_preds, preds); destroy_predicate_vecs (preds); - destroy_predicate_vecs (def_preds); return is_properly_guarded; } @@ -2245,6 +2260,8 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds, use_operand_p use_p; gimple use_stmt; imm_use_iterator iter; + pred_chain_union def_preds = vNULL; + gimple ret = NULL; phi_result = gimple_phi_result (phi); @@ -2264,7 +2281,7 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds, hash_set visited_phis; if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds, - &visited_phis)) + &def_preds, &visited_phis)) continue; if (dump_file && (dump_flags & TDF_DETAILS)) @@ -2274,7 +2291,10 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds, } /* Found one real use, return. */ if (gimple_code (use_stmt) != GIMPLE_PHI) - return use_stmt; + { + ret = use_stmt; + break; + } /* Found a phi use that is not guarded, add the phi to the worklist. */ @@ -2291,7 +2311,8 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds, } } - return NULL; + destroy_predicate_vecs (def_preds); + return ret; } /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions -- 2.5.0.rc2.22.g69b1679.dirty