From patchwork Tue Aug 27 14:03:39 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Filip Kastl X-Patchwork-Id: 1977333 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.cz header.i=@suse.cz header.a=rsa-sha256 header.s=susede2_rsa header.b=GO7nhPFZ; dkim=pass header.d=suse.cz header.i=@suse.cz header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=9WvBb600; dkim=pass (1024-bit key) header.d=suse.cz header.i=@suse.cz header.a=rsa-sha256 header.s=susede2_rsa header.b=IrIt4Usx; dkim=neutral header.d=suse.cz header.i=@suse.cz header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=B9k+yQ8X; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WtTmv1gMtz1yZd for ; Wed, 28 Aug 2024 00:04:15 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5A8563860770 for ; Tue, 27 Aug 2024 14:04:13 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.223.131]) by sourceware.org (Postfix) with ESMTPS id 3456A3860745 for ; Tue, 27 Aug 2024 14:03:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3456A3860745 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.cz ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 3456A3860745 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.131 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1724767425; cv=none; b=RvBNxjlZg98/g1ZJ8YCEjF5vsy8OthHBI23bLECxWPTRMKLshrWwn3TFS7tN72QZ+sAKJGDAn0AvG+GqdV2+/zT/qvyuzx0noMBTpwHjnJziWx4BUhfRSr/0mLnky68QYSbdsWyLL5iZNbaezKlU1H9wLBaIlQO3mGIK46IJnvw= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1724767425; c=relaxed/simple; bh=/SLmYUo4KYYlrlPJm1uMTVPXwDWIv2ykG5a4LkvzzXE=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:Message-ID:MIME-Version; b=ENCjmb+jj68MtpXlJNmy7Q0uik8MBGVZqOXhmdGYHRVt9oXMH6zbc7WN11BIBQrwz2h6TD1+jjvoJgRXJQMyOR1IsaHFF8X0sXSah+DsjnSMmY5PgTI0P59fqddj18xmCyf4Qn1Z5tvs+2GDZD4kPtDLP0iunDFMvUhQimq0SRQ= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap1.dmz-prg2.suse.org (imap1.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:97]) (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 smtp-out2.suse.de (Postfix) with ESMTPS id E5EE11FB6C; Tue, 27 Aug 2024 14:03:39 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1724767421; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=ReP4eBLhWhzPNlVI5LJipgILmLHArj7rxqxiZVqHheo=; b=GO7nhPFZBQEtuDnAnXs4GWc5XsCzHS9GwueIC1LrO+g8HERMgIF4yetANtxNvrmtE7JKwh o9dewf3KLLtUeZ0geCUO0vPLrwWUxqp4oNipbuuZM6GDcM93Rz46iX7FotVekZB/fCxdLJ 6PfZYHpA/PfMFl6t4aZ/YJYKemAAgI0= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1724767421; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=ReP4eBLhWhzPNlVI5LJipgILmLHArj7rxqxiZVqHheo=; b=9WvBb600jxQKw4q+Ackcpa2+tQHQxzcVigu3RsgJRq9I4y907iP5kEbLG06/wWTkzQamXf H1uc1oh4Vp1bizAA== Authentication-Results: smtp-out2.suse.de; dkim=pass header.d=suse.cz header.s=susede2_rsa header.b=IrIt4Usx; dkim=pass header.d=suse.cz header.s=susede2_ed25519 header.b=B9k+yQ8X DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1724767419; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=ReP4eBLhWhzPNlVI5LJipgILmLHArj7rxqxiZVqHheo=; b=IrIt4UsxTS2k4M3LURJjOY2FjwUweH64pmr3NvQjU2e0OwYEqT53Vbz280RlEMSzMMMu14 RR8j7aVWVRz+y+5pcQYQfU0BMziskLWJomhFAPmRdrrgQuaYfe/BnIZmAGTRlo3h6MqqBj 2gdA+kjAKzAsZwhX3HWpse7MhVIlz/o= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1724767419; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=ReP4eBLhWhzPNlVI5LJipgILmLHArj7rxqxiZVqHheo=; b=B9k+yQ8XHwEKpYYc/orKY2VHFvDIBHMwyhJOYBu7b/RJi5X2EM5DfXox0+Duyd7MR/btun 6+FeDbFYqdYvpAAQ== Received: from imap1.dmz-prg2.suse.org (localhost [127.0.0.1]) (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 imap1.dmz-prg2.suse.org (Postfix) with ESMTPS id D550913A44; Tue, 27 Aug 2024 14:03:39 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap1.dmz-prg2.suse.org with ESMTPSA id f6wMNLvczWaCCAAAD6G6ig (envelope-from ); Tue, 27 Aug 2024 14:03:39 +0000 Date: Tue, 27 Aug 2024 16:03:39 +0200 From: Filip Kastl To: Richard Biener Cc: gcc-patches@gcc.gnu.org, pinskia@gmail.com Subject: [PATCH v2] gimple ssa: switchconv: Use __builtin_popcount and support more types in exp transform [PR116355] Message-ID: References: <814093qp-n1ps-0r81-nooq-544o37796nqs@fhfr.qr> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <814093qp-n1ps-0r81-nooq-544o37796nqs@fhfr.qr> X-Rspamd-Queue-Id: E5EE11FB6C X-Spam-Level: X-Spamd-Result: default: False [-4.51 / 50.00]; BAYES_HAM(-3.00)[100.00%]; NEURAL_HAM_LONG(-1.00)[-1.000]; R_DKIM_ALLOW(-0.20)[suse.cz:s=susede2_rsa,suse.cz:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-1.000]; MIME_GOOD(-0.10)[text/plain]; MX_GOOD(-0.01)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; FREEMAIL_ENVRCPT(0.00)[gmail.com]; FUZZY_BLOCKED(0.00)[rspamd.com]; RBL_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:104:10:150:64:97:from]; DKIM_SIGNED(0.00)[suse.cz:s=susede2_rsa,suse.cz:s=susede2_ed25519]; MIME_TRACE(0.00)[0:+]; ARC_NA(0.00)[]; FREEMAIL_CC(0.00)[gcc.gnu.org,gmail.com]; DKIM_TRACE(0.00)[suse.cz:+]; TO_DN_SOME(0.00)[]; RCVD_COUNT_TWO(0.00)[2]; FROM_EQ_ENVFROM(0.00)[]; FROM_HAS_DN(0.00)[]; RCVD_TLS_ALL(0.00)[]; MID_RHS_MATCH_FROMTLD(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; RECEIVED_SPAMHAUS_BLOCKED_OPENRESOLVER(0.00)[2a07:de40:b281:106:10:150:64:167:received]; RCPT_COUNT_THREE(0.00)[3]; MISSING_XM_UA(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[sourceware.org:url, tree-switch-conversion.cc:url, imap1.dmz-prg2.suse.org:helo, imap1.dmz-prg2.suse.org:rdns, fkdesktop.suse.cz:mid, gcc.target:url, suse.cz:dkim, suse.cz:email] X-Rspamd-Server: rspamd2.dmz-prg2.suse.org X-Rspamd-Action: no action X-Spam-Score: -4.51 X-Spam-Status: No, score=-11.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Hi, this is the second version of this patch. See the mail with the first version here: https://inbox.sourceware.org/gcc-patches/ZsnRLdYErnIWQlCe@localhost.localdomain/ In this version I've made these adjustments: - Added calls direct_internal_fn_supported_p to can_pow2p. Before I just assumed that if the target supports FFS at all it will support it for unsigned, long unsigned and long long unsigned and didn't check this. - Also added a direct_intenal_fn_supported_p check for the type passed to can_pow2p as a small compile time optimization. This is the first check that runs and if it is positive, the function exits early and doesn't bother with any conversions. - can_pow2p and can_log2 now return the type that gen_pow2p and gen_log2 should convert to before generating the respective operation. gen_pow2p and gen_log2 now have this type as one of their parameters. - Using gimple_convert instead of manually building CONVERT_EXPR/NOP_EXPR assignments. - Using gimple_build for building __builtin_popcount. - Adjusted ChangeLog entries. Bootstrapped and regtested on x86_64 linux. Ok to push? Cheers, Filip Kastl -- 8< -- The gen_pow2p function generates (a & -a) == a as a fallback for POPCOUNT (a) == 1. Not only is the bitmagic not equivalent to POPCOUNT (a) == 1 but it also introduces UB (consider signed a = INT_MIN). This patch rewrites gen_pow2p to always use __builtin_popcount instead. This means that what the end result GIMPLE code is gets decided by an already existing machinery in a later pass. That is a cleaner solution I think. This existing machinery also uses a ^ (a - 1) > a - 1 which is the correct bitmagic. While rewriting gen_pow2p I had to add logic for converting the operand's type to a type that __builtin_popcount accepts. I naturally also added this logic to gen_log2. Thanks to this, exponential index transform gains the capability to handle all operand types with precision at most that of long long int. PR tree-optimization/116355 gcc/ChangeLog: * tree-switch-conversion.cc (can_log2): Add capability to suggest converting the operand to a different type. (gen_log2): Add capability to generate a conversion in case the operand is of a type incompatible with the logarithm operation. (can_pow2p): New function. (gen_pow2p): Rewrite to use __builtin_popcount instead of manually inserting an internal fn call or bitmagic. Also add capability to generate a conversion. (switch_conversion::is_exp_index_transform_viable): Call can_pow2p. Store types suggested by can_log2 and gen_log2. (switch_conversion::exp_index_transform): Params of gen_pow2p and gen_log2 changed so update their calls. * tree-switch-conversion.h: Add m_exp_index_transform_log2_type and m_exp_index_transform_pow2p_type to switch_conversion class to track type conversions needed to generate the "is power of 2" and logarithm operations. gcc/testsuite/ChangeLog: * gcc.target/i386/switch-exp-transform-1.c: Don't test for presence of POPCOUNT internal fn after switch conversion. Test for it after __builtin_popcount has had a chance to get expanded. * gcc.target/i386/switch-exp-transform-3.c: Also test char and short. Signed-off-by: Filip Kastl --- .../gcc.target/i386/switch-exp-transform-1.c | 7 +- .../gcc.target/i386/switch-exp-transform-3.c | 98 ++++++++++- gcc/tree-switch-conversion.cc | 152 ++++++++++++++---- gcc/tree-switch-conversion.h | 7 + 4 files changed, 227 insertions(+), 37 deletions(-) diff --git a/gcc/testsuite/gcc.target/i386/switch-exp-transform-1.c b/gcc/testsuite/gcc.target/i386/switch-exp-transform-1.c index 53d31460ba3..a8c9e03e515 100644 --- a/gcc/testsuite/gcc.target/i386/switch-exp-transform-1.c +++ b/gcc/testsuite/gcc.target/i386/switch-exp-transform-1.c @@ -1,9 +1,10 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-switchconv -mpopcnt -mbmi" } */ +/* { dg-options "-O2 -fdump-tree-switchconv -fdump-tree-widening_mul -mpopcnt -mbmi" } */ /* Checks that exponential index transform enables switch conversion to convert this switch into an array lookup. Also checks that the "index variable is a - power of two" check has been generated. */ + power of two" check has been generated and that it has been later expanded + into an internal function. */ int foo(unsigned bar) { @@ -29,4 +30,4 @@ int foo(unsigned bar) } /* { dg-final { scan-tree-dump "CSWTCH" "switchconv" } } */ -/* { dg-final { scan-tree-dump "POPCOUNT" "switchconv" } } */ +/* { dg-final { scan-tree-dump "POPCOUNT" "widening_mul" } } */ diff --git a/gcc/testsuite/gcc.target/i386/switch-exp-transform-3.c b/gcc/testsuite/gcc.target/i386/switch-exp-transform-3.c index 64a7b146172..5011d1ebb0e 100644 --- a/gcc/testsuite/gcc.target/i386/switch-exp-transform-3.c +++ b/gcc/testsuite/gcc.target/i386/switch-exp-transform-3.c @@ -3,10 +3,104 @@ /* Checks that the exponential index transformation is done for all these types of the index variable: + - (unsigned) char + - (unsigned) short - (unsigned) int - (unsigned) long - (unsigned) long long */ +int unopt_char(char bit_position) +{ + switch (bit_position) + { + case (1 << 0): + return 0; + case (1 << 1): + return 1; + case (1 << 2): + return 2; + case (1 << 3): + return 3; + case (1 << 4): + return 4; + case (1 << 5): + return 5; + case (1 << 6): + return 6; + default: + return 0; + } +} + +int unopt_unsigned_char(unsigned char bit_position) +{ + switch (bit_position) + { + case (1 << 0): + return 0; + case (1 << 1): + return 1; + case (1 << 2): + return 2; + case (1 << 3): + return 3; + case (1 << 4): + return 4; + case (1 << 5): + return 5; + case (1 << 6): + return 6; + default: + return 0; + } +} + +int unopt_short(short bit_position) +{ + switch (bit_position) + { + case (1 << 0): + return 0; + case (1 << 1): + return 1; + case (1 << 2): + return 2; + case (1 << 3): + return 3; + case (1 << 4): + return 4; + case (1 << 5): + return 5; + case (1 << 6): + return 6; + default: + return 0; + } +} + +int unopt_unsigned_short(unsigned short bit_position) +{ + switch (bit_position) + { + case (1 << 0): + return 0; + case (1 << 1): + return 1; + case (1 << 2): + return 2; + case (1 << 3): + return 3; + case (1 << 4): + return 4; + case (1 << 5): + return 5; + case (1 << 6): + return 6; + default: + return 0; + } +} + int unopt_int(int bit_position) { switch (bit_position) @@ -149,5 +243,5 @@ int unopt_unsigned_long_long(unsigned long long bit_position) #endif -/* { dg-final { scan-tree-dump-times "Applying exponential index transform" 4 "switchconv" { target ia32 } } } */ -/* { dg-final { scan-tree-dump-times "Applying exponential index transform" 6 "switchconv" { target { ! ia32 } } } } */ +/* { dg-final { scan-tree-dump-times "Applying exponential index transform" 8 "switchconv" { target ia32 } } } */ +/* { dg-final { scan-tree-dump-times "Applying exponential index transform" 10 "switchconv" { target { ! ia32 } } } } */ diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc index 4b11c8d25f4..c1332a26094 100644 --- a/gcc/tree-switch-conversion.cc +++ b/gcc/tree-switch-conversion.cc @@ -64,65 +64,148 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA using namespace tree_switch_conversion; /* Does the target have optabs needed to efficiently compute exact base two - logarithm of a value with type TYPE? + logarithm of a variable with type TYPE? - See gen_log2. */ + If yes, returns TYPE. If no, returns NULL_TREE. May also return another + type. This indicates that logarithm of the variable can be computed but + only after it is converted to this type. -static bool + Also see gen_log2. */ + +static tree can_log2 (tree type, optimization_type opt_type) { - /* Check if target supports FFS. */ - return direct_internal_fn_supported_p (IFN_FFS, type, opt_type); + /* Check if target supports FFS for given type. */ + if (direct_internal_fn_supported_p (IFN_FFS, type, opt_type)) + return type; + + /* Check if target supports FFS for some type we could convert to. */ + int prec = TYPE_PRECISION (type); + int i_prec = TYPE_PRECISION (integer_type_node); + int li_prec = TYPE_PRECISION (long_integer_type_node); + int lli_prec = TYPE_PRECISION (long_long_integer_type_node); + tree new_type; + if (prec <= i_prec + && direct_internal_fn_supported_p (IFN_FFS, integer_type_node, opt_type)) + new_type = integer_type_node; + else if (prec <= li_prec + && direct_internal_fn_supported_p (IFN_FFS, long_integer_type_node, + opt_type)) + new_type = long_integer_type_node; + else if (prec <= lli_prec + && direct_internal_fn_supported_p (IFN_FFS, + long_long_integer_type_node, + opt_type)) + new_type = long_long_integer_type_node; + else + return NULL_TREE; + return new_type; } /* Assume that OP is a power of two. Build a sequence of gimple statements efficiently computing the base two logarithm of OP using special optabs. Return the ssa name represeting the result of the logarithm through RESULT. - Should only be used if target supports the needed optabs. See can_log2. */ + Before computing the logarithm, OP may have to be converted to another type. + This should be specified in TYPE. Use can_log2 to decide what this type + should be. + + Should only be used if can_log2 doesn't reject the type of OP. */ static gimple_seq -gen_log2 (tree op, location_t loc, tree *result) +gen_log2 (tree op, location_t loc, tree *result, tree type) { - tree type = TREE_TYPE (op); gimple_seq stmts = NULL; gimple_stmt_iterator gsi = gsi_last (stmts); - tree tmp1 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, IFN_FFS, type, op); - tree tmp2 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, MINUS_EXPR, type, - tmp1, build_one_cst (type)); - *result = tmp2; + + tree orig_type = TREE_TYPE (op); + tree tmp1; + if (type != orig_type) + tmp1 = gimple_convert (&gsi, false, GSI_NEW_STMT, loc, type, op); + else + tmp1 = op; + /* Build FFS (op) - 1. */ + tree tmp2 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, IFN_FFS, orig_type, + tmp1); + tree tmp3 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, MINUS_EXPR, + orig_type, tmp2, build_one_cst (orig_type)); + *result = tmp3; return stmts; } +/* Is it possible to efficiently check that a value of TYPE is a power of 2? + + If yes, returns TYPE. If no, returns NULL_TREE. May also return another + type. This indicates that logarithm of the variable can be computed but + only after it is converted to this type. + + Also see gen_pow2p. */ + +static tree +can_pow2p (tree type) +{ + /* __builtin_popcount supports the unsigned type or its long and long long + variants. Choose the smallest out of those that can still fit TYPE. */ + int prec = TYPE_PRECISION (type); + int i_prec = TYPE_PRECISION (unsigned_type_node); + int li_prec = TYPE_PRECISION (long_unsigned_type_node); + int lli_prec = TYPE_PRECISION (long_long_unsigned_type_node); + + if (prec <= i_prec) + return unsigned_type_node; + else if (prec <= li_prec) + return long_unsigned_type_node; + else if (prec <= lli_prec) + return long_long_unsigned_type_node; + else + return NULL_TREE; +} + /* Build a sequence of gimple statements checking that OP is a power of 2. Use special optabs if target supports them. Return the result as a - boolen_type_node ssa name through RESULT. */ + boolean_type_node ssa name through RESULT. Assumes that OP's value will + be non-negative. The generated check may give arbitrary answer for negative + values. + + Before computing the check, OP may have to be converted to another type. + This should be specified in TYPE. Use can_pow2p to decide what this type + should be. + + Should only be used if can_pow2p returns true for type of OP. */ static gimple_seq -gen_pow2p (tree op, location_t loc, optimization_type opt_type, tree *result) +gen_pow2p (tree op, location_t loc, tree *result, tree type) { - tree type = TREE_TYPE (op); gimple_seq stmts = NULL; gimple_stmt_iterator gsi = gsi_last (stmts); - if (direct_internal_fn_supported_p (IFN_POPCOUNT, type, opt_type)) - { - tree tmp = gimple_build (&gsi, false, GSI_NEW_STMT, loc, IFN_POPCOUNT, - type, op); - *result = gimple_build (&gsi, false, GSI_NEW_STMT, loc, EQ_EXPR, - boolean_type_node, tmp, build_one_cst (type)); - } + + built_in_function fn; + if (type == unsigned_type_node) + fn = BUILT_IN_POPCOUNT; + else if (type == long_unsigned_type_node) + fn = BUILT_IN_POPCOUNTL; else { - tree tmp1 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, NEGATE_EXPR, - type, op); - tree tmp2 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, BIT_AND_EXPR, - type, op, tmp1); - *result = gimple_build (&gsi, false, GSI_NEW_STMT, loc, EQ_EXPR, - boolean_type_node, tmp2, op); + fn = BUILT_IN_POPCOUNTLL; + gcc_checking_assert (type == long_long_unsigned_type_node); } + + tree orig_type = TREE_TYPE (op); + tree tmp1; + if (type != orig_type) + tmp1 = gimple_convert (&gsi, false, GSI_NEW_STMT, loc, type, op); + else + tmp1 = op; + /* Build __builtin_popcount{l,ll} (op) == 1. */ + tree tmp2 = gimple_build (&gsi, false, GSI_NEW_STMT, loc, + as_combined_fn (fn), integer_type_node, tmp1); + *result = gimple_build (&gsi, false, GSI_NEW_STMT, loc, EQ_EXPR, + boolean_type_node, tmp2, + build_one_cst (integer_type_node)); return stmts; } + /* Constructor. */ switch_conversion::switch_conversion (): m_final_bb (NULL), @@ -285,7 +368,11 @@ switch_conversion::is_exp_index_transform_viable (gswitch *swtch) unsigned num_labels = gimple_switch_num_labels (swtch); optimization_type opt_type = bb_optimization_type (swtch_bb); - if (!can_log2 (index_type, opt_type)) + m_exp_index_transform_log2_type = can_log2 (index_type, opt_type); + if (!m_exp_index_transform_log2_type) + return false; + m_exp_index_transform_pow2p_type = can_pow2p (index_type); + if (!m_exp_index_transform_pow2p_type) return false; /* Check that each case label corresponds only to one value @@ -380,8 +467,8 @@ switch_conversion::exp_index_transform (gswitch *swtch) new_edge2->probability = profile_probability::even (); tree tmp; - optimization_type opt_type = bb_optimization_type (cond_bb); - gimple_seq stmts = gen_pow2p (index, UNKNOWN_LOCATION, opt_type, &tmp); + gimple_seq stmts = gen_pow2p (index, UNKNOWN_LOCATION, &tmp, + m_exp_index_transform_pow2p_type); gsi = gsi_last_bb (cond_bb); gsi_insert_seq_after (&gsi, stmts, GSI_LAST_NEW_STMT); gcond *stmt_cond = gimple_build_cond (NE_EXPR, tmp, boolean_false_node, @@ -402,7 +489,8 @@ switch_conversion::exp_index_transform (gswitch *swtch) } /* Insert a sequence of stmts that takes the log of the index variable. */ - stmts = gen_log2 (index, UNKNOWN_LOCATION, &tmp); + stmts = gen_log2 (index, UNKNOWN_LOCATION, &tmp, + m_exp_index_transform_log2_type); gsi = gsi_after_labels (swtch_bb); gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index 1a865f85f3a..14610499e5f 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -918,6 +918,13 @@ public: the definition of exp_index_transform for details about the transformation. */ bool m_exp_index_transform_applied; + + /* If switch conversion decided exponential index transform is viable, here + will be stored the types to which index variable has to be converted + before the logarithm and the "is power of 2" operations which are part of + the transform. */ + tree m_exp_index_transform_log2_type; + tree m_exp_index_transform_pow2p_type; }; void