From patchwork Tue Oct 12 10:24:32 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 46127 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 46D123857C51 for ; Tue, 12 Oct 2021 10:25:04 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 46D123857C51 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1634034304; bh=ZZZsSC2h1S0ajqiTIR4u7bftEOBb1aAsKf6mCFsjvN0=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=oiE8oV6A+Q1UkmczDVXfNeE14lZINk7u+YVMZ3bXTtVqBgt9XR5WZnJzm7ilet9g5 vKqdpHNFUpNqYtY12OFKejvhPHWckEip04YmIgYjPYnrPJ0koDm8poT6TgafO9/icP LaEZD3hHdC4EGY35Zo9jxRBPfr6XyYBfO9lgiBoU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 169C43858D3C for ; Tue, 12 Oct 2021 10:24:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 169C43858D3C Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id DF4DB220BE; Tue, 12 Oct 2021 10:24:32 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id C203C13B2A; Tue, 12 Oct 2021 10:24:32 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id An8iLmBiZWEKBAAAMHmgww (envelope-from ); Tue, 12 Oct 2021 10:24:32 +0000 Date: Tue, 12 Oct 2021 12:24:32 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH][RFC] Introduce TREE_AOREFWRAP to cache ao_ref in the IL Message-ID: <3313269o-5444-9142-o8ro-1s59r67083pq@fhfr.qr> MIME-Version: 1.0 X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Cc: matz@suse.de, hubicka@ucw.cz Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This prototype hack introduces a new tcc_reference TREE_AOREFWRAP which we can use to wrap a reference tree, recording the ao_ref associated with it. That comes in handy when trying to optimize the constant factor involved with alias stmt walking (or alias queries in general) where there's parts that are liner in the reference expression complexity, namely get_ref_base_and_extent, which shows up usually high on profiles. The idea was to make a wrapping TREE_AOREFWRAP mostly transparent to users by making gimple_assign_{lhs,rhs1} strip it and provide special accessors that get at the embedded ao_ref as well as doing the wrapping when it's not already there. The following patch is minimal as to make tree-ssa.exp=ssa-fre-* not ICE and make the testcases from PR28071 and PR39326 compile successfully at -O1 (both testcases show a moderately high load on alias stmt walking around 25%, resp. 34%). With the patch which makes use of the cache only from stmt_may_clobber_ref_p for now the compile-time improves by 7%, resp. 19% which means overall the idea might be worth pursuing. I did run into more "issues" with the extra TREE_AOREFWRAP appearing than anticipated (well, no, not really...). So given it is a kind of hack already I'm now thinking of making it even more transparent by instead of wrapping the refs with another tree to reallocate the outermost handled_component_p (and only those), placing the ao_ref after the tree and indicating its presence by TREE_ASM_WRITTEN (or any other available bit). As with TREE_AOREFWRAP the key is to invalidate the ao_ref (strip TREE_AOREFWRAP or unset TREE_ASM_WRITTEN) when its information becomes stale (for example by unsharing) or invalid (by mangling the reference into sth semantically different) or no longer precise (by propagating constants into the reference). I did consider simply using an (optional) on-the-side hash-map and allocpool to be initialized by passes and queried by the oracle. The downside is that we're optimizing a "constant" factor of the oracle query but a hash-map lookup isn't exactly cache-friendly. Likewise caching across pass boundaries sounded maybe important (OK, we have at most N ao_refs with N linear in the program size - but as said, we're optimizing a constant factor). Existing on-the-side caching includes the SCEV cache for example. So take this as a proof-of-concept showing the possible gain, I do think going either the TREE_ASM_WRITTEN or on-the-side table solution is going to have less issues all around the compiler. Comments? Thanks, Richard. 2021-10-12 Richard Biener * treestruct.def (TS_AOREFWRAP): New. * tree.def (TREE_AOREFWRAP): Likewise. * gimple.h (gimple_assign_lhs): Look through TREE_AOREFWRAP. (gimple_assign_rhs1): Likewise. (gimple_assign_lhs_with_ao_ref): New. (gimple_assign_rhs1_with_ao_ref): Likewise. * tree-ssa-alias.c (stmt_may_clobber_ref_p_1): Use the ao_ref embedded in the stmts LHS if possible. <... and more hacks ...> --- gcc/gimple.c | 62 +++++++++++++++++++++++++++++++++++++- gcc/gimple.h | 12 ++++++-- gcc/tree-core.h | 8 +++++ gcc/tree-inline.c | 4 +++ gcc/tree-ssa-alias.c | 11 +++++-- gcc/tree-ssa-loop-im.c | 5 ++- gcc/tree-ssa-loop-ivopts.c | 3 ++ gcc/tree-ssa-loop.c | 1 + gcc/tree-ssa-operands.c | 1 + gcc/tree-streamer.c | 1 + gcc/tree.c | 15 +++++++-- gcc/tree.def | 4 +++ gcc/treestruct.def | 1 + 13 files changed, 119 insertions(+), 9 deletions(-) diff --git a/gcc/gimple.c b/gcc/gimple.c index cc7a88e822b..070304b64bf 100644 --- a/gcc/gimple.c +++ b/gcc/gimple.c @@ -1758,6 +1758,60 @@ gimple_set_bb (gimple *stmt, basic_block bb) } +/* Return rhs1 of a STMT with GIMPLE_SINGLE_RHS and initialize *REF + to the wrapping TREE_AOREFWRAP ao_ref or if rhs1 is not wrapped, + wrap it. When wrapping is not profitable initialize *REF to NULL. */ + +tree +gimple_assign_rhs1_with_ao_ref (gassign *stmt, ao_ref **ref) +{ + tree rhs1 = stmt->op[1]; + if (!REFERENCE_CLASS_P (rhs1)) + { + *ref = NULL; + return rhs1; + } + if (TREE_CODE (rhs1) != TREE_AOREFWRAP) + { + rhs1 = build1 (TREE_AOREFWRAP, TREE_TYPE (rhs1), rhs1); + static_assert (sizeof (ao_ref) == sizeof (rhs1->aorefwrap.ref_storage), + "wrong aorefwrap storage size"); + *ref = new (&rhs1->aorefwrap.ref_storage) ao_ref; + ao_ref_init (*ref, TREE_OPERAND (rhs1, 0)); + stmt->op[1] = rhs1; + return TREE_OPERAND (rhs1, 0); + } + *ref = reinterpret_cast (&rhs1->aorefwrap.ref_storage); + return TREE_OPERAND (rhs1, 0); +} + +/* Return lhs of a STMT with GIMPLE_SINGLE_RHS and initialize *REF + to the wrapping TREE_AOREFWRAP ao_ref or if rhs1 is not wrapped, + wrap it. When wrapping is not profitable initialize *REF to NULL. */ + +tree +gimple_assign_lhs_with_ao_ref (gassign *stmt, ao_ref **ref) +{ + tree lhs = stmt->op[0]; + if (!REFERENCE_CLASS_P (lhs)) + { + *ref = NULL; + return lhs; + } + if (TREE_CODE (lhs) != TREE_AOREFWRAP) + { + lhs = build1 (TREE_AOREFWRAP, TREE_TYPE (lhs), lhs); + static_assert (sizeof (ao_ref) == sizeof (lhs->aorefwrap.ref_storage), + "wrong aorefwrap storage size"); + *ref = new (&lhs->aorefwrap.ref_storage) ao_ref; + ao_ref_init (*ref, TREE_OPERAND (lhs, 0)); + stmt->op[0] = lhs; + return TREE_OPERAND (lhs, 0); + } + *ref = reinterpret_cast (&lhs->aorefwrap.ref_storage); + return TREE_OPERAND (lhs, 0); +} + /* Modify the RHS of the assignment pointed-to by GSI using the operands in the expression tree EXPR. @@ -2094,7 +2148,13 @@ gimple_copy (gimple *stmt) /* Make copy of operands. */ for (i = 0; i < num_ops; i++) - gimple_set_op (copy, i, unshare_expr (gimple_op (stmt, i))); + { + tree op = gimple_op (stmt, i); + /* When we unshare OP the references in the ao_ref get stale. */ + if (op && TREE_CODE (op) == TREE_AOREFWRAP) + op = TREE_OPERAND (op, 0); + gimple_set_op (copy, i, unshare_expr (op)); + } if (gimple_has_mem_ops (stmt)) { diff --git a/gcc/gimple.h b/gcc/gimple.h index 303623b3ced..e3fcce5ab60 100644 --- a/gcc/gimple.h +++ b/gcc/gimple.h @@ -2593,7 +2593,10 @@ get_gimple_rhs_class (enum tree_code code) static inline tree gimple_assign_lhs (const gassign *gs) { - return gs->op[0]; + tree lhs = gs->op[0]; + if (TREE_CODE (lhs) == TREE_AOREFWRAP) + lhs = TREE_OPERAND (lhs, 0); + return lhs; } static inline tree @@ -2644,7 +2647,10 @@ gimple_assign_set_lhs (gimple *gs, tree lhs) static inline tree gimple_assign_rhs1 (const gassign *gs) { - return gs->op[1]; + tree rhs1 = gs->op[1]; + if (TREE_CODE (rhs1) == TREE_AOREFWRAP) + rhs1 = TREE_OPERAND (rhs1, 0); + return rhs1; } static inline tree @@ -2654,6 +2660,8 @@ gimple_assign_rhs1 (const gimple *gs) return gimple_assign_rhs1 (ass); } +extern tree gimple_assign_lhs_with_ao_ref (gassign *, ao_ref **); +extern tree gimple_assign_rhs1_with_ao_ref (gassign *, ao_ref **); /* Return a pointer to the first operand on the RHS of assignment statement GS. */ diff --git a/gcc/tree-core.h b/gcc/tree-core.h index d3d2a8d812f..437888181a5 100644 --- a/gcc/tree-core.h +++ b/gcc/tree-core.h @@ -1551,6 +1551,13 @@ struct GTY(()) tree_exp { operands[1]; }; +struct GTY(()) tree_aorefwrap { + /* We rely on exp.operands having one declared element. */ + struct tree_exp exp; + /* We could move the definition of ao_ref here or to coretypes.h. */ + unsigned char ref_storage[/* sizeof (ao_ref) */ 2 * sizeof (tree) + 3 * sizeof (poly_int64) + 2 * sizeof (alias_set_type) + sizeof (tree)/*bool*/]; +}; + /* Immediate use linking structure. This structure is used for maintaining a doubly linked list of uses of an SSA_NAME. */ struct GTY(()) ssa_use_operand_t { @@ -2058,6 +2065,7 @@ union GTY ((ptr_alias (union lang_tree_node), struct tree_list GTY ((tag ("TS_LIST"))) list; struct tree_vec GTY ((tag ("TS_VEC"))) vec; struct tree_exp GTY ((tag ("TS_EXP"))) exp; + struct tree_aorefwrap GTY ((tag ("TS_AOREFWRAP"))) aorefwrap; struct tree_ssa_name GTY ((tag ("TS_SSA_NAME"))) ssa_name; struct tree_block GTY ((tag ("TS_BLOCK"))) block; struct tree_binfo GTY ((tag ("TS_BINFO"))) binfo; diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c index e292a144967..7b4e701b2d5 100644 --- a/gcc/tree-inline.c +++ b/gcc/tree-inline.c @@ -1029,6 +1029,10 @@ remap_gimple_op_r (tree *tp, int *walk_subtrees, void *data) bool is_lhs = wi_p->is_lhs; wi_p->is_lhs = false; + /* Instead of possibly re-mapping ao_ref ref/base simply drop the cache. */ + if (TREE_CODE (*tp) == TREE_AOREFWRAP) + *tp = TREE_OPERAND (*tp, 0); + if (TREE_CODE (*tp) == SSA_NAME) { *tp = remap_ssa_name (*tp, id); diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index ce667ff32b9..670d03748a8 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -3144,12 +3144,17 @@ stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref, bool tbaa_p) } else if (gimple_assign_single_p (stmt)) { - tree lhs = gimple_assign_lhs (stmt); + ao_ref *rp; + tree lhs = gimple_assign_lhs_with_ao_ref (as_a (stmt), &rp); if (TREE_CODE (lhs) != SSA_NAME) { ao_ref r; - ao_ref_init (&r, lhs); - return refs_may_alias_p_1 (ref, &r, tbaa_p); + if (!rp) + { + ao_ref_init (&r, lhs); + rp = &r; + } + return refs_may_alias_p_1 (ref, rp, tbaa_p); } } else if (gimple_code (stmt) == GIMPLE_ASM) diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 4b187c2cdaf..ae940576e19 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -1500,6 +1500,9 @@ gather_mem_refs_stmt (class loop *loop, gimple *stmt) make sure we can canonicalize the ref in the hashtable if non-operand_equal_p refs are found. For the lookup we mark the case we want strict equality with aor.max_size == -1. */ + tree *orig_mem = mem; + if (TREE_CODE (*mem) == TREE_AOREFWRAP) + mem = &TREE_OPERAND (*mem, 0); ao_ref aor; ao_ref_init (&aor, *mem); ao_ref_base (&aor); @@ -1603,7 +1606,7 @@ gather_mem_refs_stmt (class loop *loop, gimple *stmt) } } - record_mem_ref_loc (ref, stmt, mem); + record_mem_ref_loc (ref, stmt, orig_mem); } if (is_stored) { diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 4a498abe3b0..579cdce2d23 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -2302,6 +2302,9 @@ find_interesting_uses_address (struct ivopts_data *data, gimple *stmt, if (gimple_has_volatile_ops (stmt)) goto fail; + if (TREE_CODE (base) == TREE_AOREFWRAP) + base = TREE_OPERAND (base, 0); + /* Ignore bitfields for now. Not really something terribly complicated to handle. TODO. */ if (TREE_CODE (base) == BIT_FIELD_REF) diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c index 1bbf2f1fb2c..10ba24c5f07 100644 --- a/gcc/tree-ssa-loop.c +++ b/gcc/tree-ssa-loop.c @@ -600,6 +600,7 @@ for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) case VIEW_CONVERT_EXPR: case REALPART_EXPR: case IMAGPART_EXPR: + case TREE_AOREFWRAP: nxt = &TREE_OPERAND (*addr_p, 0); break; diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index ebf7eea3b04..4c7910518c4 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -826,6 +826,7 @@ operands_scanner::get_expr_operands (tree *expr_p, int flags) case COMPONENT_REF: case REALPART_EXPR: case IMAGPART_EXPR: + case TREE_AOREFWRAP: { if (!(flags & opf_no_vops) && TREE_THIS_VOLATILE (expr)) diff --git a/gcc/tree-streamer.c b/gcc/tree-streamer.c index 5a8406ffb3d..e23844bdfef 100644 --- a/gcc/tree-streamer.c +++ b/gcc/tree-streamer.c @@ -81,6 +81,7 @@ streamer_check_handled_ts_structures (void) handled_p[TS_LIST] = true; handled_p[TS_VEC] = true; handled_p[TS_EXP] = true; + handled_p[TS_AOREFWRAP] = true; handled_p[TS_SSA_NAME] = true; handled_p[TS_BLOCK] = true; handled_p[TS_BINFO] = true; diff --git a/gcc/tree.c b/gcc/tree.c index 7bfd64160f4..c6e82962c5c 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -480,10 +480,13 @@ tree_node_structure_for_code (enum tree_code code) case tcc_type: return TS_TYPE_NON_COMMON; + case tcc_reference: + if (code == TREE_AOREFWRAP) + return TS_AOREFWRAP; + /* Fallthru. */ case tcc_binary: case tcc_comparison: case tcc_expression: - case tcc_reference: case tcc_statement: case tcc_unary: case tcc_vl_exp: return TS_EXP; @@ -624,6 +627,10 @@ initialize_tree_contains_struct (void) MARK_TS_DECL_COMMON (code); break; + case TS_AOREFWRAP: + MARK_TS_EXP (code); + break; + default: gcc_unreachable (); } @@ -998,6 +1005,9 @@ tree_code_size (enum tree_code code) } case tcc_reference: /* a reference */ + if (code == TREE_AOREFWRAP) + return sizeof (struct tree_aorefwrap); + /* Fallthru. */ case tcc_expression: /* an expression */ case tcc_statement: /* an expression with side effects */ case tcc_comparison: /* a comparison expression */ @@ -4887,7 +4897,8 @@ build0 (enum tree_code code, tree tt MEM_STAT_DECL) tree build1 (enum tree_code code, tree type, tree node MEM_STAT_DECL) { - int length = sizeof (struct tree_exp); + /* ??? This was all tree_exp. */ + size_t length = tree_code_size (code); tree t; record_node_allocation_statistics (code, length); diff --git a/gcc/tree.def b/gcc/tree.def index e27bc3e2b1f..d09c77e7e4a 100644 --- a/gcc/tree.def +++ b/gcc/tree.def @@ -461,6 +461,10 @@ DEFTREECODE (IMAGPART_EXPR, "imagpart_expr", tcc_reference, 1) generating insns. */ DEFTREECODE (VIEW_CONVERT_EXPR, "view_convert_expr", tcc_reference, 1) +/* Outermost wrapper around a reference caching an ao_ref for it. The + only operand is the reference itself. */ +DEFTREECODE (TREE_AOREFWRAP, "aoref_wrap", tcc_reference, 1) + /* C unary `*'. One operand, an expression for a pointer. */ DEFTREECODE (INDIRECT_REF, "indirect_ref", tcc_reference, 1) diff --git a/gcc/treestruct.def b/gcc/treestruct.def index 822fba17068..aab962a913b 100644 --- a/gcc/treestruct.def +++ b/gcc/treestruct.def @@ -61,6 +61,7 @@ DEFTREESTRUCT(TS_TYPE_NON_COMMON, "type non-common") DEFTREESTRUCT(TS_LIST, "list") DEFTREESTRUCT(TS_VEC, "vec") DEFTREESTRUCT(TS_EXP, "exp") +DEFTREESTRUCT(TS_AOREFWRAP, "aorefwrap") DEFTREESTRUCT(TS_SSA_NAME, "ssa name") DEFTREESTRUCT(TS_BLOCK, "block") DEFTREESTRUCT(TS_BINFO, "binfo")