Re: [PATCH] Fix loop split incorrect count and probability

[Jan Hubicka <hubicka@kam.mff.cuni.cz>]

> >

> 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.