From patchwork Fri Aug 2 16:14:42 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mariam Arutunian X-Patchwork-Id: 1968422 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=XttsHLha; 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 4Wb9sj2Wsdz1yZv for ; Sat, 3 Aug 2024 02:15:21 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 95577385B50B for ; Fri, 2 Aug 2024 16:15:19 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-lj1-x235.google.com (mail-lj1-x235.google.com [IPv6:2a00:1450:4864:20::235]) by sourceware.org (Postfix) with ESMTPS id 1EB9A3858428 for ; Fri, 2 Aug 2024 16:14:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1EB9A3858428 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1EB9A3858428 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::235 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722615299; cv=none; b=HR5pZmmwV6HjB4PETOGpCETEegUuSFvBDJKOWRh++kdn8WTpxxN01jFkR0COGAJMY+s8GcQsYk6as00J3KmfCfqCX3AzzEc2ywV2O69fuYf7h6knGkDQ6Tmie0nQI64PEVKdyQtiafWV4JxknC8bNe9o9NmJPwnW9th+CakQyWQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722615299; c=relaxed/simple; bh=v1O31c1NfMYmm7FlTqCVhViM8cB4o0Q6T14amfr07DU=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=XV0dtuV2YBxTTDX/urbGzaTz6S7bUn9LdAH72tLuMh5ymAR4qz+7MNX9vNc/XvObZGFQ5cMLjZvGHgNUSs9sjWCp4anm9ENwqzTwOyKHIZ+K5sGZVZ1ROOrbje5k2zuryWiIpu3hEQ3/KQ2dePsXOKD2wlsZmh2FaQlAohWg1RE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-lj1-x235.google.com with SMTP id 38308e7fff4ca-2f15790b472so26328331fa.0 for ; Fri, 02 Aug 2024 09:14:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722615295; x=1723220095; darn=gcc.gnu.org; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=kFB+TJ/g5sHvJzzz0oQN+0HYKrJuj+KyPRhsMIQonGU=; b=XttsHLhaBeUVynpVZv2flqyVJMf9tcb1C5Jh05zewFiPPDxLVOx036fRdSGpiS5enn ABrXu8tJLF1eG+ToVKbzbb1V/52vOnZ4mA8GKLTOByapUVI279MWmZ2Ndh7e1eBuz19U fvNk6+BWO03bYcRSJ8RPWSWN91iunq8y36xMc9qcaGms5K3aCs0Qwu+07LCS9FT5vS+n nowSg/Jd3VY1ttAeu/TYqb7oew4v/uWaDXL41pjiN4rqmNpmbT82fWNtACC8f+ARYWz0 Dzj22SZnT2EdOuU1SADn2dJm3KmEqSnqqG19/K7t27heDvaEff0Q1fea0VxcWArl1LV3 ndPw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722615295; x=1723220095; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=kFB+TJ/g5sHvJzzz0oQN+0HYKrJuj+KyPRhsMIQonGU=; b=wlSZyC+yvY7OrxihnOiYgqOr4pfHDqkBMKwcxVtPawKAR6qsqOvMuX7xBRSWEGFbZc mH2+VExGkaEv+8w406UH64AzxgM49UZz5INyc0cX+0MRSg8ZV8nK800kEjru5UAJwI/S 8H7fQHRTQlZC/opO4lHXFCMaPkL9xQBuNa3gI5Y83b2E9O0eHV8FCdWSx3vU3CnTEbB1 9ojOUsylM61XKo9UHnasO9ZYfsDkl8BvTzgTnb6+aunERT93sruIqXF6fW8lViS3Rafl Tw+yt/9+1FLam8shCmXwPn7cKubx7fT011Kkftm0asythRYIAyl4oo+ICBubzO4l9dlV XCEg== X-Gm-Message-State: AOJu0YzYMCyqmChN+LDEzuv1DuGC+Xp6EqRR8WaNJV8TilVszhFNy4DF 3IiuYCcNoCoJUDWEdlw3lcdPFnBDnTtIn9j2NkhXv1DlHJf6c+AZp6w9lixkb4BBE5WYRDiKUXw PXD9TsF6+guvjPLBceqcbGGZDjE3z0Q== X-Google-Smtp-Source: AGHT+IG8tcRNW6MOG9XcVdDeQhN3yr0+5S5Eg8v9DsuZbhwxS53NYh29Al00nFcK9bknt8Nvzv4oGimk1VKlQp+UuMw= X-Received: by 2002:a2e:968b:0:b0:2ec:56b9:259b with SMTP id 38308e7fff4ca-2f15ab5db15mr27580101fa.49.1722615294885; Fri, 02 Aug 2024 09:14:54 -0700 (PDT) MIME-Version: 1.0 From: Mariam Arutunian Date: Fri, 2 Aug 2024 20:14:42 +0400 Message-ID: Subject: [RFC/RFA] [PATCH v2 11/12] Replace the original CRC loops with a faster CRC calculation. To: GCC Patches X-Spam-Status: No, score=-7.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP 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 After the loop exit an internal function call (CRC, CRC_REV) is added, and its result is assigned to the output CRC variable (the variable where the calculated CRC is stored after the loop execution). The removal of the loop is left to CFG cleanup and DCE. gcc/ * gimple-crc-optimization.cc (get_data): New function. (optimize_crc_loop): Likewise. (build_polynomial_without_1): Likewise. (execute): Add optimize_crc_loop function call. Signed-off-by: Mariam Arutunian diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc index bd84d553a60..4de383419a0 100644 --- a/gcc/gimple-crc-optimization.cc +++ b/gcc/gimple-crc-optimization.cc @@ -216,6 +216,24 @@ class crc_optimization { /* Returns phi statement which may hold the calculated CRC. */ gphi *get_output_phi (); + /* Returns data argument to pass to the CRC IFN. + If there is data from the code - use it (this is the case, + when data isn't xor-ed with CRC before the loop). + Otherwise, generate a new variable for the data with 0 value + (the case, when data is xor-ed with CRC before the loop). + For the CRC calculation, it doesn't matter CRC is calculated for the + (CRC^data, 0) or (CRC, data). */ + tree get_data (); + + /* Attempts to optimize a CRC calculation loop by replacing it with a call to + an internal function (IFN_CRC or IFN_CRC_REV). + Returns true if replacement is succeeded, otherwise false. */ + bool optimize_crc_loop (value *polynomial, gphi *output_crc); + + /* Build tree for the POLYNOMIAL (from its binary representation) + without the leading 1. */ + tree build_polynomial_without_1 (tree crc_arg, value *polynomial); + public: unsigned int execute (function *fun); }; @@ -1094,6 +1112,142 @@ crc_optimization::get_output_phi () return nullptr; } +/* Build tree for the POLYNOMIAL (from its binary representation) + without the leading 1. */ + +tree +crc_optimization::build_polynomial_without_1 (tree crc_arg, value *polynomial) +{ + unsigned HOST_WIDE_INT cst_polynomial = 0; + for (unsigned i = 0; i < (*polynomial).length (); i++) + { + value_bit *const_bit; + if (m_is_bit_forward) + const_bit = (*polynomial)[(*polynomial).length () - 1 - i]; + else + const_bit = (*polynomial)[i]; + cst_polynomial <<= 1; + cst_polynomial ^= (as_a (const_bit))->get_val () ? 1 : 0; + } + return build_int_cstu (TREE_TYPE (crc_arg), cst_polynomial); +} + +/* Returns data argument to pass to the CRC IFN. + If there is data from the code - use it (this is the case, + when data isn't xor-ed with CRC before the loop). + Otherwise, generate a new variable for the data with 0 value + (the case, when data is xor-ed with CRC before the loop). + For the CRC calculation, it doesn't matter CRC is calculated for the + (CRC^data, 0) or (CRC, data). */ + +tree +crc_optimization::get_data () +{ + unsigned HOST_WIDE_INT + data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1; + + /* If we have the data, use it. */ + if (m_phi_for_data) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Data and CRC are xor-ed in the for loop. Initializing data " + "with its value.\n"); + tree data_arg = PHI_ARG_DEF (m_phi_for_data, 1); + if (TYPE_PRECISION (TREE_TYPE (data_arg)) == data_size) + return data_arg; + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Loop iteration number and data's size differ.\n"); + return nullptr; + } + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Data and CRC are xor-ed before for loop. Initializing data " + "with 0.\n"); + /* Create a new variable for the data. + Determine the data's size with the loop iteration count. */ + tree type = build_nonstandard_integer_type (data_size, 1); + return build_int_cstu (type, 0); +} + +/* Attempts to optimize a CRC calculation loop by replacing it with a call to + an internal function (IFN_CRC or IFN_CRC_REV). + Returns true if replacement is succeeded, otherwise false. */ + +bool +crc_optimization::optimize_crc_loop (value *polynomial, gphi *output_crc) +{ + if (!output_crc) + { + if (dump_file) + fprintf (dump_file, "Couldn't determine output CRC.\n"); + return false; + } + + gcc_assert (m_phi_for_crc); + + tree crc_arg = PHI_ARG_DEF (m_phi_for_crc, 1); + if (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (crc_arg))).to_constant () + > GET_MODE_SIZE (word_mode)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "word_mode is less than CRC mode.\n"); + return false; + } + + tree data_arg = get_data (); + tree polynomial_arg = build_polynomial_without_1 (crc_arg, polynomial); + + if (!crc_arg || !data_arg || !polynomial_arg) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "crc_arg, data_arg or polynomial_arg is null.\n"); + return false; + } + + /* We don't support the case where data is larger than the CRC. */ + if (TYPE_PRECISION (TREE_TYPE (crc_arg)) + < TYPE_PRECISION (TREE_TYPE (data_arg))) + return false; + + internal_fn ifn; + if (m_is_bit_forward) + ifn = IFN_CRC; + else + ifn = IFN_CRC_REV; + + tree phi_result = gimple_phi_result (output_crc); + location_t loc; + loc = EXPR_LOCATION (phi_result); + + /* Add IFN call and write the return value in the phi_result. */ + gcall *call + = gimple_build_call_internal (ifn, 3, + crc_arg, + data_arg, + polynomial_arg); + + gimple_call_set_lhs (call, phi_result); + gimple_set_location (call, loc); + gimple_stmt_iterator si = gsi_start_bb (output_crc->bb); + gsi_insert_before (&si, call, GSI_SAME_STMT); + + /* Remove phi statement, which was holding CRC result. */ + gimple_stmt_iterator tmp_gsi = gsi_for_stmt (output_crc); + gsi_remove (&tmp_gsi, true); + + /* Alter the exit condition of the loop to always exit. */ + gcond* loop_exit_cond = get_loop_exit_condition (m_crc_loop); + gimple_cond_make_false (loop_exit_cond); + update_stmt (loop_exit_cond); + return true; +} + unsigned int crc_optimization::execute (function *fun) { @@ -1139,6 +1293,12 @@ crc_optimization::execute (function *fun) if (dump_file) fprintf (dump_file, "The loop with %d header BB index " "calculates CRC!\n", m_crc_loop->header->index); + + if (!optimize_crc_loop (polynom_value, output_crc)) + { + if (dump_file) + fprintf (dump_file, "Couldn't generate faster CRC code.\n"); + } } } return 0; -- 2.25.1