From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yb1-xb36.google.com (mail-yb1-xb36.google.com [IPv6:2607:f8b0:4864:20::b36]) by sourceware.org (Postfix) with ESMTPS id 3A71E38582A4 for ; Tue, 14 Feb 2023 16:31:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3A71E38582A4 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-yb1-xb36.google.com with SMTP id s203so13712161ybc.11 for ; Tue, 14 Feb 2023 08:31:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=4Sn/siq5PI0am9hkFt3NwGyXqjR/PDBMalsmdZe9vWI=; b=MUAr1/YHuX962DFDalU4538hfEqSkBctkc3QU5+gXse1mn4z5oHqVC7BE0WR/KR2M9 xo8E1Tm76CIsVtAoxgf4W36HpZO0KgwIbTkgbaZObBscLhih5iI+f8luElorvD/aYmeQ 3PClBO3qF1iZ6mz3S35DFk9h1Ofv80xZA2bowP0WvvxDcyQJeEzR2ryuDPwyGoGThr9R c2qC5OaTj/9SsUD8i0M0TYImhVU8hH56idPU8cJoMp/PDA076JyTOY5bfjxHXxcbezgP i04vPIzlSe3xUaNA8Jz5IWOoBIvRIEk2Vn8JivHXypj5pihQGM3Ob5ZP1ZDNW43fBRtG EcCA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=4Sn/siq5PI0am9hkFt3NwGyXqjR/PDBMalsmdZe9vWI=; b=nQghtDkCGsURnFmkWdT/dbMXs4HcfBxqN7BXH5RStYloDMn/FNumuVFLvMhr163q6m lXn7vNmXNums/cnGv6iTLb2vBAxZwVQ8cTKn5TeDu7w19XcLC3uBZoKpr1PlCeCVqU4h 1974dgjUqDsIg1F2Bra9J9mpuiIBZoN0TwOHdAivCl7Ijp2DDrqwZToWwb71JoIfNI3L KWKPMFnCGWnaFEfSSLSxeu/cuSfMU34kcWQxVR4HRpoK26XgQ8ovfLaGmpVar60arC0y 1zcP5eyt+odM0TF0xrOX8xHOW+dvD+x4KSNczjLcDG9b6tDEnWzO+LBvxVCIaC0xupru IuYQ== X-Gm-Message-State: AO0yUKWdfmdNYXixDx+8GCFQGwvP6SZm4OWv/J55A0TwKY/d8beO2MLP 6aVIazNY6oz9j3NRHfxwO758Bj9+d44tinwg7E86DDpP8Hs= X-Google-Smtp-Source: AK7set/veQiZBXo3RuFULzkSxT0VPokwr9P9pE8jtrYmABuBWR1dwOlzDC8RN8+ZuPDa6hZ6UTiIrbKqYmMmgTY7L/o= X-Received: by 2002:a25:9012:0:b0:874:380b:887e with SMTP id s18-20020a259012000000b00874380b887emr298808ybl.239.1676392260481; Tue, 14 Feb 2023 08:31:00 -0800 (PST) MIME-Version: 1.0 References: <20230209142522.2411B3858413@sourceware.org> In-Reply-To: <20230209142522.2411B3858413@sourceware.org> From: Uros Bizjak Date: Tue, 14 Feb 2023 17:30:49 +0100 Message-ID: Subject: Re: [PATCH] target/108738 - STV bitmap operations compile-time hog To: Richard Biener Cc: gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-7.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,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 List-Id: On Thu, Feb 9, 2023 at 3:25 PM Richard Biener via Gcc-patches wrote: > > When the set of candidates becomes very large then repeated > bit checks on it during the build of an actual chain can become > slow because of the O(n) nature of bitmap tests. The following > switches the candidates bitmaps to the tree representation before > building the chains to get O(log n) amortized behavior. > > For the testcase at hand this improves STV time by 50%. > > Bootstrapped and tested on x86_64-unknown-linux-gnu, OK? > > Thanks, > Richard. > > PR target/108738 > * config/i386/i386-features.cc (convert_scalars_to_vector): > Switch candidates bitmaps to tree view before building the chains. 'git diff -w' shows the true change ;) LGTM. Thanks, Uros. > --- > gcc/config/i386/i386-features.cc | 49 +++++++++++++++++--------------- > 1 file changed, 26 insertions(+), 23 deletions(-) > > diff --git a/gcc/config/i386/i386-features.cc b/gcc/config/i386/i386-features.cc > index ec13d4e7489..9bd6d8677bb 100644 > --- a/gcc/config/i386/i386-features.cc > +++ b/gcc/config/i386/i386-features.cc > @@ -2283,30 +2283,33 @@ convert_scalars_to_vector (bool timode_p) > fprintf (dump_file, "There are no candidates for optimization.\n"); > > for (unsigned i = 0; i <= 2; ++i) > - while (!bitmap_empty_p (&candidates[i])) > - { > - unsigned uid = bitmap_first_set_bit (&candidates[i]); > - scalar_chain *chain; > - > - if (cand_mode[i] == TImode) > - chain = new timode_scalar_chain; > - else > - chain = new general_scalar_chain (cand_mode[i], cand_vmode[i]); > - > - /* Find instructions chain we want to convert to vector mode. > - Check all uses and definitions to estimate all required > - conversions. */ > - chain->build (&candidates[i], uid); > - > - if (chain->compute_convert_gain () > 0) > - converted_insns += chain->convert (); > - else > - if (dump_file) > - fprintf (dump_file, "Chain #%d conversion is not profitable\n", > - chain->chain_id); > + { > + bitmap_tree_view (&candidates[i]); > + while (!bitmap_empty_p (&candidates[i])) > + { > + unsigned uid = bitmap_first_set_bit (&candidates[i]); > + scalar_chain *chain; > > - delete chain; > - } > + if (cand_mode[i] == TImode) > + chain = new timode_scalar_chain; > + else > + chain = new general_scalar_chain (cand_mode[i], cand_vmode[i]); > + > + /* Find instructions chain we want to convert to vector mode. > + Check all uses and definitions to estimate all required > + conversions. */ > + chain->build (&candidates[i], uid); > + > + if (chain->compute_convert_gain () > 0) > + converted_insns += chain->convert (); > + else > + if (dump_file) > + fprintf (dump_file, "Chain #%d conversion is not profitable\n", > + chain->chain_id); > + > + delete chain; > + } > + } > > if (dump_file) > fprintf (dump_file, "Total insns converted: %d\n", converted_insns); > -- > 2.35.3