From patchwork Fri Oct 18 15:01:51 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mariam Arutunian X-Patchwork-Id: 1999256 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=In8GWW71; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; 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 [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 ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XVSfS21dpz1xth for ; Sat, 19 Oct 2024 02:04:32 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7843A3858294 for ; Fri, 18 Oct 2024 15:04:30 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-lj1-x22f.google.com (mail-lj1-x22f.google.com [IPv6:2a00:1450:4864:20::22f]) by sourceware.org (Postfix) with ESMTPS id C711A385840C for ; Fri, 18 Oct 2024 15:02:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C711A385840C 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 C711A385840C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::22f ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729263729; cv=none; b=WrL87h1d8mxmH/z4eE4wvEZeb7HWGL5CP+uSOxibuIW2Meprvc6D2LHwJWmM/T/jDQYBOOqA4AZ4IPFqagZiYWY12Q0/0scqm6LWTHwkESNBh5L9DThXufY4gdw3ZUncUkTVMSNDg40BPJFcGa+8cx3yA6btGz6dR1DoAUxnOQo= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729263729; c=relaxed/simple; bh=GmLmh/m3kfm7YYghBV32ND7xGy4oYMEqQSIYcB1CRy8=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=TM9lb5EpLEVammv7U7tup7EjL6K43hDd88rkHWhf6ZA0hVF/yODEnaIZDi6raLoGB7ZONR1Orc1govqSvnh3p7LJqpFYg4j62ChkyHvPScR5YR8gWr66Z8NQ653XPxUSyPTrX+U02vktf+RI9jJoYu5SQWNZPQZ4jxZfS56ULKg= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-lj1-x22f.google.com with SMTP id 38308e7fff4ca-2fb443746b8so26346301fa.0 for ; Fri, 18 Oct 2024 08:02:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729263723; x=1729868523; darn=gcc.gnu.org; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=Myb00K/nUuAORjwZrUQawZdA2vzuPT67ho1OaL8j4Po=; b=In8GWW71/H4EOUZonKyflSsxocLH1Av3e3EwzsJSWBz+NJK59hMRAMZaQQZUhBa8TF I5W5FSd4rYkHBQbJR+gwpwSiF4DdO7v4yacVs9WIRKNQoBXkFFhnwyEJvoa1wM/QD724 tGOAX2rIxZgopZsbVuN7aAyg4W5dXa9k+IQZXUCfqZC8IG6FMmdVFy1H+mmTFYP7Uq0T lGz5HEfxMlX44Lyz22hHYcRoH9EuEoA4O9NXV+vv4MQobAm3D47+RHajercoAKLk3ndf w43AVQOPDViiMejQkHAF/PQmIiXzH/+V5jUKe8ZmzEVXnV4ECbhdlk5lBtFJqejNIWIK 4c4w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729263723; x=1729868523; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=Myb00K/nUuAORjwZrUQawZdA2vzuPT67ho1OaL8j4Po=; b=mZs0g2LysZ3FYj/YB53JRRg0XnjIg7tOhCH1ah6deqM2DnMQS1/h8Up0WE7nWRdj6L vmwHVsbpnRL2avcF/Sdzv1ayqtWSVGnOO57+PnO66SzNmjiV9VtEMoD7j8GqwQ11hIgW Nfv77yU7LMMrBijhOtZ8r1gcxRtwuz52CmqSZ8pdGxM2z244Q0Gi9KYxgGB1g1F49VtS sKcIMmGN0QLjSjlPustaclAJsi1XFEZndQR5SSuZuPYZeCT5eH0L4nfALAye9Kgct08i jKRbdBPqqqMXDt1lax/EgB6h3iBZI8ZoZQ7F2I4erzKohGYT5UmWmRKLquKGvu6fdvkT aszw== X-Gm-Message-State: AOJu0Ywagy+i40wRrOI2SVNnXy6ZxpKwbN9MsTeFdJzYzxw14Yi2OGf1 my2WVAd5DaUU7mDoWqw9Xb5tjz8kkyV7atTlhG+EoDpJf6pswT0Upc3Q5puddZNlighY7OyCiOy 4TDxebPfwT7HKQjF20tUvKjicNHDWC3U8xas= X-Google-Smtp-Source: AGHT+IFPL8keNKMmbk45s784JOVxv6o38medss28DQaZhn8Pa4+iPfH3XIrOuFfZtHn/h53WnVvmw8QbdQ++MVOMm4o= X-Received: by 2002:a05:651c:2115:b0:2fb:5f9d:c284 with SMTP id 38308e7fff4ca-2fb82ea2827mr16695281fa.16.1729263722537; Fri, 18 Oct 2024 08:02:02 -0700 (PDT) MIME-Version: 1.0 From: Mariam Arutunian Date: Fri, 18 Oct 2024 19:01:51 +0400 Message-ID: Subject: [RFC/RFA] [PATCH v5 11/12] Replace the original CRC loops with a faster CRC calculation. To: GCC Patches , Jeff Law X-Spam-Status: No, score=-7.7 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 (optimize_crc_loop): New function. (execute): Add optimize_crc_loop function call. Signed-off-by: Mariam Arutunian Mentored-by: Jeff Law --- gcc/gimple-crc-optimization.cc | 78 ++++++++++++++++++++++++++++++++++ 1 file changed, 78 insertions(+) diff --git a/gcc/gimple-crc-optimization.cc b/gcc/gimple-crc-optimization.cc index a05aaf9f217..9dee9be85d0 100644 --- a/gcc/gimple-crc-optimization.cc +++ b/gcc/gimple-crc-optimization.cc @@ -225,6 +225,11 @@ class crc_optimization { /* Returns phi statement which may hold the calculated CRC. */ gphi *get_output_phi (); + /* 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 (gphi *output_crc); + public: crc_optimization () : m_visited_stmts (BITMAP_ALLOC (NULL)), m_crc_loop (nullptr), m_polynomial (0) @@ -1215,6 +1220,73 @@ crc_optimization::get_output_phi () return nullptr; } +/* 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 (gphi *output_crc) +{ + if (!output_crc) + { + if (dump_file) + fprintf (dump_file, "Couldn't determine output CRC.\n"); + return false; + } + + if (!m_data_arg) + { + 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. */ + unsigned HOST_WIDE_INT + data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1; + tree type = build_nonstandard_integer_type (data_size, 1); + /* For the CRC calculation, it doesn't matter CRC is calculated for the + (CRC^data, 0) or (CRC, data). */ + m_data_arg = build_int_cstu (type, 0); + } + + /* Build tree node for the polynomial from its constant value. */ + tree polynomial_arg = build_int_cstu (TREE_TYPE (m_crc_arg), m_polynomial); + gcc_assert (polynomial_arg); + + 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, + m_crc_arg, + m_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); + remove_phi_node (&tmp_gsi, false); + + /* 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) { @@ -1271,6 +1343,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 (output_crc)) + { + if (dump_file) + fprintf (dump_file, "Couldn't generate faster CRC code.\n"); + } } } return 0; -- 2.25.1