From patchwork Tue Jan 5 09:08:02 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 1422389 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=SfW7NKcF; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4D969F5rr5z9sVs for ; Tue, 5 Jan 2021 20:08:15 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E3349393C85E; Tue, 5 Jan 2021 09:08:12 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E3349393C85E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1609837692; bh=tuY97qp8fo9bxAOHzQKQt/iDTYLmLCjwK/6g5cZ9bLE=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=SfW7NKcFuDEgk2fNPOcpElbGHFJo3ycA58/ScuN3zT+N+wTTdjTheRudM/5RZYhF5 nhqIXYbpATdE4/Nq8CEwObwKVzM9zO5EZx2NU3uS0Mui5VOvwjrdT7gCYa4HR9T7n/ AbQF+R5V+EptXNtUAky1ilE6YDhIRIbk28v2UZDY= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 9B823385780E for ; Tue, 5 Jan 2021 09:08:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 9B823385780E Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-443-dseFdhdLONeMxxDlW1mx6g-1; Tue, 05 Jan 2021 04:08:07 -0500 X-MC-Unique: dseFdhdLONeMxxDlW1mx6g-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 470CF801817; Tue, 5 Jan 2021 09:08:06 +0000 (UTC) Received: from tucnak.zalov.cz (ovpn-112-11.ams2.redhat.com [10.36.112.11]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 7AC8F5D9C6; Tue, 5 Jan 2021 09:08:05 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.16.1/8.16.1) with ESMTPS id 105983WI1731270 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 5 Jan 2021 10:08:03 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.16.1/8.16.1/Submit) id 105982261731269; Tue, 5 Jan 2021 10:08:02 +0100 Date: Tue, 5 Jan 2021 10:08:02 +0100 To: Richard Biener Subject: [PATCH] reassoc: Fix reassociation on 32-bit hosts with > 32767 bbs [PR98514] Message-ID: <20210105090802.GM725145@tucnak> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-6.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: Jakub Jelinek via Gcc-patches From: Jakub Jelinek Reply-To: Jakub Jelinek Cc: gcc-patches@gcc.gnu.org Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Hi! Apparently reassoc ICEs on large functions (more than 32767 basic blocks with something to reassociate in those). The problem is that the pass uses long type to store the ranks, and the bb ranks are (number of SSA_NAMEs with default defs + 2 + bb->index) << 16, so with many basic blocks we overflow the ranks and we then have assertions rank is not negative. The following patch just uses HOST_WIDE_INT instead of long in the pass, yes, it means slightly higher memory consumption (one array indexed by bb->index is twice as large, and one hash_map from trees to the ranks will grow by 50%, but I think it is better than punting on large functions the reassociation on 32-bit hosts and making it inconsistent e.g. when cross-compiling. Given vec.h uses unsigned for vect element counts, we don't really support more than 4G of SSA_NAMEs or more than 2G of basic blocks in a function, so even with the << 16 we can't really overflow the HOST_WIDE_INT rank counters. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2021-01-05 Jakub Jelinek PR tree-optimization/98514 * tree-ssa-reassoc.c (bb_rank): Change type from long * to HOST_WIDE_INT *. (operand_rank): Change type from hash_map to hash_map. (phi_rank): Change return type from long to HOST_WIDE_INT. (loop_carried_phi): Change block_rank variable type from long to HOST_WIDE_INT. (propagate_rank): Change return type, rank parameter type and op_rank variable type from long to HOST_WIDE_INT. (find_operand_rank): Change return type from long to HOST_WIDE_INT and change slot variable type from long * to HOST_WIDE_INT *. (insert_operand_rank): Change rank parameter type from long to HOST_WIDE_INT. (get_rank): Change return type and rank variable type from long to HOST_WIDE_INT. Use HOST_WIDE_INT_PRINT_DEC instead of %ld to print the rank. (init_reassoc): Change rank variable type from long to HOST_WIDE_INT and adjust correspondingly bb_rank and operand_rank initialization. Jakub --- gcc/tree-ssa-reassoc.c.jj 2021-01-04 10:25:37.153252851 +0100 +++ gcc/tree-ssa-reassoc.c 2021-01-04 17:01:15.211112328 +0100 @@ -200,10 +200,10 @@ static unsigned int next_operand_entry_i /* Starting rank number for a given basic block, so that we can rank operations using unmovable instructions in that BB based on the bb depth. */ -static long *bb_rank; +static HOST_WIDE_INT *bb_rank; /* Operand->rank hashtable. */ -static hash_map *operand_rank; +static hash_map *operand_rank; /* Vector of SSA_NAMEs on which after reassociate_bb is done with all basic blocks the CFG should be adjusted - basic blocks @@ -212,7 +212,7 @@ static hash_map *operand_ran static vec reassoc_branch_fixups; /* Forward decls. */ -static long get_rank (tree); +static HOST_WIDE_INT get_rank (tree); static bool reassoc_stmt_dominates_stmt_p (gimple *, gimple *); /* Wrapper around gsi_remove, which adjusts gimple_uid of debug stmts @@ -257,7 +257,7 @@ reassoc_remove_stmt (gimple_stmt_iterato calculated into an accumulator variable to be independent for each iteration of the loop. If STMT is some other phi, the rank is the block rank of its containing block. */ -static long +static HOST_WIDE_INT phi_rank (gimple *stmt) { basic_block bb = gimple_bb (stmt); @@ -311,7 +311,7 @@ static bool loop_carried_phi (tree exp) { gimple *phi_stmt; - long block_rank; + HOST_WIDE_INT block_rank; if (TREE_CODE (exp) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (exp)) @@ -337,10 +337,10 @@ loop_carried_phi (tree exp) from expression OP. For most operands, this is just the rank of OP. For loop-carried phis, the value is zero to avoid undoing the bias in favor of the phi. */ -static long -propagate_rank (long rank, tree op) +static HOST_WIDE_INT +propagate_rank (HOST_WIDE_INT rank, tree op) { - long op_rank; + HOST_WIDE_INT op_rank; if (loop_carried_phi (op)) return rank; @@ -352,17 +352,17 @@ propagate_rank (long rank, tree op) /* Look up the operand rank structure for expression E. */ -static inline long +static inline HOST_WIDE_INT find_operand_rank (tree e) { - long *slot = operand_rank->get (e); + HOST_WIDE_INT *slot = operand_rank->get (e); return slot ? *slot : -1; } /* Insert {E,RANK} into the operand rank hashtable. */ static inline void -insert_operand_rank (tree e, long rank) +insert_operand_rank (tree e, HOST_WIDE_INT rank) { gcc_assert (rank > 0); gcc_assert (!operand_rank->put (e, rank)); @@ -370,7 +370,7 @@ insert_operand_rank (tree e, long rank) /* Given an expression E, return the rank of the expression. */ -static long +static HOST_WIDE_INT get_rank (tree e) { /* SSA_NAME's have the rank of the expression they are the result @@ -414,7 +414,7 @@ get_rank (tree e) { ssa_op_iter iter; gimple *stmt; - long rank; + HOST_WIDE_INT rank; tree op; /* If we already have a rank for this expression, use that. */ @@ -448,7 +448,7 @@ get_rank (tree e) { fprintf (dump_file, "Rank for "); print_generic_expr (dump_file, e); - fprintf (dump_file, " is %ld\n", rank); + fprintf (dump_file, " is " HOST_WIDE_INT_PRINT_DEC "\n", rank); } /* Note the rank in the hashtable so we don't recompute it. */ @@ -6774,7 +6774,7 @@ static void init_reassoc (void) { int i; - long rank = 2; + HOST_WIDE_INT rank = 2; int *bbs = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS); /* Find the loops, so that we can prevent moving calculations in @@ -6788,8 +6788,8 @@ init_reassoc (void) /* Reverse RPO (Reverse Post Order) will give us something where deeper loops come later. */ pre_and_rev_post_order_compute (NULL, bbs, false); - bb_rank = XCNEWVEC (long, last_basic_block_for_fn (cfun)); - operand_rank = new hash_map; + bb_rank = XCNEWVEC (HOST_WIDE_INT, last_basic_block_for_fn (cfun)); + operand_rank = new hash_map; /* Give each default definition a distinct rank. This includes parameters and the static chain. Walk backwards over all