From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <hubicka@kam.mff.cuni.cz>
Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16])
 by sourceware.org (Postfix) with ESMTPS id 711AE3858034;
 Tue, 26 Oct 2021 13:05:24 +0000 (GMT)
DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 711AE3858034
Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202)
 id 38659281D84; Tue, 26 Oct 2021 15:05:23 +0200 (CEST)
Date: Tue, 26 Oct 2021 15:05:23 +0200
From: Jan Hubicka <hubicka@kam.mff.cuni.cz>
To: Feng Xue OS <fxue@os.amperecomputing.com>
Cc: Richard Biener <rguenther@suse.de>, Xionghu Luo <luoxhu@linux.ibm.com>,
 "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
 "segher@kernel.crashing.org" <segher@kernel.crashing.org>,
 "wschmidt@linux.ibm.com" <wschmidt@linux.ibm.com>,
 "guojiufu@linux.ibm.com" <guojiufu@linux.ibm.com>,
 "linkw@gcc.gnu.org" <linkw@gcc.gnu.org>
Subject: Re: [PATCH] Fix loop split incorrect count and probability
Message-ID: <20211026130523.GA49464@kam.mff.cuni.cz>
References: <20210803085813.2217766-1-luoxhu@linux.ibm.com>
 <nycvar.YFH.7.76.2108061338260.11781@zhemvz.fhfr.qr>
 <58f9e351-fc10-406e-5272-270ece73be71@linux.ibm.com>
 <nycvar.YFH.7.76.2108101634250.11781@zhemvz.fhfr.qr>
 <SN6PR01MB4958F0E90EF1ECED4E66F4E4F7F89@SN6PR01MB4958.prod.exchangelabs.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <SN6PR01MB4958F0E90EF1ECED4E66F4E4F7F89@SN6PR01MB4958.prod.exchangelabs.com>
User-Agent: Mutt/1.10.1 (2018-07-13)
X-Spam-Status: No, score=-6.1 required=5.0 tests=BAYES_00, DKIM_SIGNED,
 DKIM_VALID, DKIM_VALID_AU, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE,
 SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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 <gcc-patches.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>,
 <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/>
List-Post: <mailto:gcc-patches@gcc.gnu.org>
List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>,
 <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Tue, 26 Oct 2021 13:05:26 -0000

> >

> That said, likely the profile update cannot be done uniformly
> for all blocks of a loop?

For the loop:

for (i = 0; i < n; i = inc (i))
    {
      if (ga)
        ga = do_something ();
}

to:

  for (i = 0; i < x; i = inc (i))
{
    if (true)
         ga = do_something ();
        if (!ga)
          break;
}
  for (; i < n; i = inc (i))
{
    if (false)
         ga = do_something ();
}

If probability of if (ga) being true is p, then you indeed can scale the
first loop by p and second loop by 1-p.

Imagine that loop has n iterations and it takes m iterations for ga to
become false, then probability of if(ga) is m/n and you get frequencies
with m=n*(m/n) for first loop and n-m=n*(1-n/m) for second loop.

Because the conditional becomes constant true, one needs to scale up the
basic block guarded by the if (true) up by n/m to compensate for the
change.  With that the udpate should be right.
Ideally one can bypass scaling of basic block(s) containing
 ga = do_something () since the scaling first scales down to m/n
and then scale sup to m/n. Which may not combine to noop.
Perhaps one wants to have a parameter specifying basic blocks on which
the scaling is performed while duplicating for this?

Honza
> 
> Richard.