RE: How to detect whether we're inside of a loop??

RE: How to detect whether we're inside of a loop??

[S. Bosscher]

Jan Hubicka wrote:
> > Daniel Berlin wrote:
> > > On Wednesday, April 9, 2003, at 02:25  PM, Geoff Keating wrote:
> > > > Why don't you just use the support that GCC already has for
> > > > detecting the probability that a block will be executed?
> > > 
> > > Because it's at the tree level he's talking about, not the RTL
> > > level.
> > 
> > FWIW, once tree-ssa-vrp is implemented, you get branch
> > prediction with it for free.  Would that help?
> Definitly :)
> We already do have branch prediction algorithm at RTL level.  I
> would like to port it to tree-ssa as soon as we realize how to
> maintain the profile over RTL expansion....

Yes that would be nice.  Already when I first posted the pointer to the
SSA-VRP paper to Diego, it was discussed that we should figure out a way to
bring branch predictions from trees to RTL.  Diego said that he expected it
to be quite hard to do because RTL is so different from trees.  He also
suggested that we could maybe use RTL NOTEs for it...

Greetz
Steven

Re: How to detect whether we're inside of a loop??

[Jan Hubicka]

> Jan Hubicka wrote:
> > > Daniel Berlin wrote:
> > > > On Wednesday, April 9, 2003, at 02:25  PM, Geoff Keating wrote:
> > > > > Why don't you just use the support that GCC already has for
> > > > > detecting the probability that a block will be executed?
> > > > 
> > > > Because it's at the tree level he's talking about, not the RTL
> > > > level.
> > > 
> > > FWIW, once tree-ssa-vrp is implemented, you get branch
> > > prediction with it for free.  Would that help?
> > Definitly :)
> > We already do have branch prediction algorithm at RTL level.  I
> > would like to port it to tree-ssa as soon as we realize how to
> > maintain the profile over RTL expansion....
> 
> Yes that would be nice.  Already when I first posted the pointer to the
> SSA-VRP paper to Diego, it was discussed that we should figure out a way to

How expansive the SSA-VRP is?  All ways of doing VRP seems to be very
expensive and/or dificult and the value of having accurate VRP
information is not too well understood (at least by me), so I am not
sure it is wortwhile to do in the production compiler.  On the other
hand it is so cool toy so I would like to see it happen in any case
and I guess we will find use for it later.

Note that VRP does not completely replace the existing branch prediction
algorithm.  Only when combined together it leads to beter prediction.
Also the paper on VRP based branch prediction is doing stronger form of
it - it propagates onot only intervals but each value range is
subdivided into multiple intervals each having different probability, so
the overall analysis are even more tricky.

> bring branch predictions from trees to RTL.  Diego said that he expected it
> to be quite hard to do because RTL is so different from trees.  He also
> suggested that we could maybe use RTL NOTEs for it...

Yes, I think everyone wonders about how this can be done.

It can be great if we were able to do expansion preserving the CFG
structure (ie take expresion of each basic block in tree CFG and expand
them into RTL and modify the expanders for expresion doing the control
flow to inject code into proper basic block).

This will introduce new basic blocks, but we can call
find_sub_basic_blocks as we do after instruction splitting - in fact RTL
expansion should be as easy as instruction splitting from this point of
view if done properly.

There are other showstoppers waiting - we need to replace all the passes
destroying CFG first - loop optimizer, sibcall, EH expansion.
We are working on that.

Honza

> 
> Greetz
> Steven
> 

Re: How to detect whether we're inside of a loop??

[Steven Bosscher]

Op wo 09-04-2003, om 21:39 schreef Jan Hubicka:
> > > We already do have branch prediction algorithm at RTL level.  I
> > > would like to port it to tree-ssa as soon as we realize how to
> > > maintain the profile over RTL expansion....
> > 
> > Yes that would be nice.  Already when I first posted the pointer to the
> > SSA-VRP paper to Diego, it was discussed that we should figure out a way to
> 
> How expansive the SSA-VRP is?  All ways of doing VRP seems to be very
> expensive and/or dificult and the value of having accurate VRP
> information is not too well understood (at least by me), so I am not
> sure it is wortwhile to do in the production compiler.  On the other
> hand it is so cool toy so I would like to see it happen in any case
> and I guess we will find use for it later.

SSA-VRP is basically an extension to SSA constant propagation, so it
should be linear in time.  There is a link to the paper describing the
algorithm from the tree-ssa project page.
It's always possible to only enable it at some high optimization level
if it turns out that it is not very useful and too slow for a production
compiler.

> Note that VRP does not completely replace the existing branch prediction
> algorithm.  Only when combined together it leads to beter prediction.

Yup.  The existing algorithm is based on heuristics, right?  VRP
actually computes branch probabilities.

> There are other showstoppers waiting - we need to replace all the passes
> destroying CFG first - loop optimizer, sibcall, EH expansion.
> We are working on that.

Cool.

Greetz
Steven

Re: How to detect whether we're inside of a loop??

[Jan Hubicka]

> Op wo 09-04-2003, om 21:39 schreef Jan Hubicka:
> > > > We already do have branch prediction algorithm at RTL level.  I
> > > > would like to port it to tree-ssa as soon as we realize how to
> > > > maintain the profile over RTL expansion....
> > > 
> > > Yes that would be nice.  Already when I first posted the pointer to the
> > > SSA-VRP paper to Diego, it was discussed that we should figure out a way to
> > 
> > How expansive the SSA-VRP is?  All ways of doing VRP seems to be very
> > expensive and/or dificult and the value of having accurate VRP
> > information is not too well understood (at least by me), so I am not
> > sure it is wortwhile to do in the production compiler.  On the other
> > hand it is so cool toy so I would like to see it happen in any case
> > and I guess we will find use for it later.
> 
> SSA-VRP is basically an extension to SSA constant propagation, so it
> should be linear in time.  There is a link to the paper describing the
> algorithm from the tree-ssa project page.
> It's always possible to only enable it at some high optimization level
> if it turns out that it is not very useful and too slow for a production
> compiler.

Have to take a look at it!  Thinking about it it should be pretty
straighforward to do VRP on SSA...
> 
> > Note that VRP does not completely replace the existing branch prediction
> > algorithm.  Only when combined together it leads to beter prediction.
> 
> Yup.  The existing algorithm is based on heuristics, right?  VRP
> actually computes branch probabilities.

It does compute just for small percentage of the branches so it don't
get better overall hitrate.  Many of the heuristics covers branches VRP
usually does not so they seem to cooperate nicely.

Honza
> 
> > There are other showstoppers waiting - we need to replace all the passes
> > destroying CFG first - loop optimizer, sibcall, EH expansion.
> > We are working on that.
> 
> Cool.
> 
> Greetz
> Steven
> 
> 

Re: How to detect whether we're inside of a loop??

[Kaveh R. Ghazi]

Thanks to all who replied to my original question.  I came up with a
function to do what I wanted.  I've not yet applied it to do anything
useful, so this patch is merely for informational purposes on this
thread for now.  I.e. it's not intended for inclusion in the gcc tree.

The function get_loop_depth() returns how many levels of loop nesting
you're in at the time you call it.  It ignores "do {...} while(0)" loops
to avoid false positives.  (Thanks to Bruce Korb for suggesting that
to me.)

It was tested by calling it from inside an expand_builtin_foo function
in builtins.c and it works correctly used from there.  I don't know if
this code needs a certain state in the compiler to be reached for it
to work, so I can't say if calling it from somewhere else
(i.e. earlier or later in compilation) will still behave correctly.

Comments welcome.

		--Kaveh

PS: now I can play with heuristics which attempt to use it.


2003-04-08  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>

	* rtl.h (get_loop_depth): Prototype.
	* stmt.c (get_loop_depth): New function.
	
diff -rup orig/egcc-CVS20030407/gcc/rtl.h egcc-CVS20030407/gcc/rtl.h
--- orig/egcc-CVS20030407/gcc/rtl.h	2003-04-06 21:01:05.000000000 -0400
+++ egcc-CVS20030407/gcc/rtl.h	2003-04-08 20:18:47.947896418 -0400
@@ -2084,6 +2084,7 @@ extern void set_file_and_line_for_stmt	P
 extern void expand_null_return		PARAMS ((void));
 extern void emit_jump			PARAMS ((rtx));
 extern int preserve_subexpressions_p	PARAMS ((void));
+extern int get_loop_depth		PARAMS ((void));
 
 /* In expr.c */
 extern void move_by_pieces		PARAMS ((rtx, rtx,
diff -rup orig/egcc-CVS20030407/gcc/stmt.c egcc-CVS20030407/gcc/stmt.c
--- orig/egcc-CVS20030407/gcc/stmt.c	2003-03-24 21:01:13.000000000 -0500
+++ egcc-CVS20030407/gcc/stmt.c	2003-04-08 22:50:16.055405217 -0400
@@ -435,6 +435,25 @@ static void emit_jump_if_reachable	PARAM
 static void emit_case_nodes		PARAMS ((rtx, case_node_ptr, rtx, tree));
 static struct case_node *case_tree2list	PARAMS ((case_node *, case_node *));
 \f
+/* Determine the number of nested loops at the current location in the
+   source code GCC is compiling.  Ignore "do {...} while(0)" loops.  */
+
+int
+get_loop_depth (void)
+{
+  int depth = 0;
+  struct nesting *ptr = loop_stack;
+
+  while (ptr)
+    {
+      /* Loops whose start_label is a NOTE are "do {...} while(0)".  */
+      if (! NOTE_P (ptr->data.loop.start_label))
+	depth++;
+      ptr = ptr->next;
+    }
+  return depth;
+}
+
 void
 using_eh_for_cleanups ()
 {

Re: How to detect whether we're inside of a loop??

[Diego Novillo]

On Wed, 2003-04-09 at 17:10, Kaveh R. Ghazi wrote:

> The function get_loop_depth() returns how many levels of loop nesting
> you're in at the time you call it.  It ignores "do {...} while(0)" loops
> to avoid false positives.  (Thanks to Bruce Korb for suggesting that
> to me.)
> 
If you are interested in loop analysis/transformations at the tree
level, I suggest you take a look at tree-ssa.  After we build the
flowgraph for the function tree you can use the generic loop
infrastructure in cfgloop.c (flow_loops_find and friends).


Diego.

Re: How to detect whether we're inside of a loop??

[Robert Dewar]

> The average you cite above for loops means that the loop-body is still
> executed more often than code which is not in a loop, just not by as
> much as I'd hoped.  And if-then clauses have execution probability of
> less than one for each clause so code in there is even less likely to
> be executed than loop bodies.

Normal assumptions are that inner loops are executed more often than
outer loops. The figure of 1.5 is wildly wrong for inner loops

Re: How to detect whether we're inside of a loop??

[Kaveh R. Ghazi]

 > From: dewar@gnat.com (Robert Dewar)
 > 
 > > The average you cite above for loops means that the loop-body is still
 > > executed more often than code which is not in a loop, just not by as
 > > much as I'd hoped.  And if-then clauses have execution probability of
 > > less than one for each clause so code in there is even less likely to
 > > be executed than loop bodies.
 > 
 > Normal assumptions are that inner loops are executed more often than
 > outer loops. The figure of 1.5 is wildly wrong for inner loops

Yup, the function I posted here:
http://gcc.gnu.org/ml/gcc/2003-04/msg00392.html
allows you to check how deep your loop nesting is.

		--Kaveh
--
Kaveh R. Ghazi			ghazi@caip.rutgers.edu

Re: How to detect whether we're inside of a loop??

[Kaveh R. Ghazi]

 > From: Geoff Keating <geoffk@geoffk.org>
 > 
 > > Date: Wed, 9 Apr 2003 16:56:55 -0400 (EDT)
 > > From: "Kaveh R. Ghazi" <ghazi@caip.rutgers.edu>
 > 
 > > I think your approach would be suited for finding which of the if-else
 > > branches to choose.  Finding the looping spots is what I'm looking
 > > for because I think it has more impact.
 > > 
 > > Do you agree with this line of reasoning?
 > 
 > No, not really.  For instance, a little-known fact is that the
 > average number of iterations for a loop is about 1.5; someone did
 > some analysis on some huge collection of programs and this is the
 > number they came up with.

Interesting, do you have a URL article with the research?  I'd like to
read it.

By the way, 1.5 > 1. :-)

The average you cite above for loops means that the loop-body is still
executed more often than code which is not in a loop, just not by as
much as I'd hoped.  And if-then clauses have execution probability of
less than one for each clause so code in there is even less likely to
be executed than loop bodies.

You've proved my point, simply with a smaller margin.

		Thanks, ;-)
		--Kaveh
--
Kaveh R. Ghazi			ghazi@caip.rutgers.edu

Re: How to detect whether we're inside of a loop??

[Joe Buck]

On Wed, Apr 09, 2003 at 04:30:00PM -0700, Geoff Keating wrote:
> No, not really.  For instance, a little-known fact is that the average
> number of iterations for a loop is about 1.5; someone did some
> analysis on some huge collection of programs and this is the number
> they came up with.  So it's important to know *which* loops to look
> at.

Well, this depends: the number is substantially higher for scientific
codes, and is a good deal higher (for example) in SPECfp (for various
years) than SPECint.

Re: How to detect whether we're inside of a loop??

[Geoff Keating]

> Date: Wed, 9 Apr 2003 16:56:55 -0400 (EDT)
> From: "Kaveh R. Ghazi" <ghazi@caip.rutgers.edu>

> I think your approach would be suited for finding which of the if-else
> branches to choose.  Finding the looping spots is what I'm looking
> for because I think it has more impact.
> 
> Do you agree with this line of reasoning?

No, not really.  For instance, a little-known fact is that the average
number of iterations for a loop is about 1.5; someone did some
analysis on some huge collection of programs and this is the number
they came up with.  So it's important to know *which* loops to look
at.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: How to detect whether we're inside of a loop??

[Kaveh R. Ghazi]

 > From: Geoff Keating <geoffk@geoffk.org>
 > 
 > "Kaveh R. Ghazi" <ghazi@caip.rutgers.edu> writes:
 > 
 > > I was interested in experimenting with heuristics which might expand a
 > > builtin depending on whether at the point of expansion we're in a loop
 > > or not.  E.g. It might make sense to expand something which might
 > > create slightly larger code only if we think it's likely that it'll be
 > > executed a number of times.  I'm guessing that being inside a loop is
 > > one way to increase that probability.  Thus I was curious if there's a
 > > way to detect this.
 > 
 > Why don't you just use the support that GCC already has for detecting
 > the probability that a block will be executed?

Well first, I don't know how to do that. :-)

But secondly, my limited understanding of probability detection leads
me to believe that using it would answer a different question than the
one I'm posing.  E.g. given this code fragment:

{
  <code1>
  if (foo)
    <code2>
  else
    {
      <code3>
      exit(1);
    }
 for (i=0; i<x; i++)
    <code4>
}

we know that <code1> is executed once.  And we can say that <code2>
has a higher probability of being executed that <code3>, but again it
would be once.  It's <code4> that is likely to be executed many times
(on average) for each pass through the fragment and therefore it is
most suitable for an expensive optimization.

I think your approach would be suited for finding which of the if-else
branches to choose.  Finding the looping spots is what I'm looking
for because I think it has more impact.

Do you agree with this line of reasoning?

		--Kaveh
--
Kaveh R. Ghazi			ghazi@caip.rutgers.edu

Re: How to detect whether we're inside of a loop??

[Jan Hubicka]

> Daniel Berlin wrote:
> > On Wednesday, April 9, 2003, at 02:25  PM, Geoff Keating wrote:
> > > Why don't you just use the support that GCC already has for
> > > detecting the probability that a block will be executed?
> > 
> > Because it's at the tree level he's talking about, not the RTL
> > level.
> 
> FWIW, once tree-ssa-vrp is implemented, you get branch
> prediction with it for free.  Would that help?
Definitly :)
We already do have branch prediction algorithm at RTL level.  I would
like to port it to tree-ssa as soon as we realize how to maintain the
profile over RTL expansion....

Honza
> 
> Greetz
> Steven

RE: How to detect whether we're inside of a loop??

[S. Bosscher]

Daniel Berlin wrote:
> On Wednesday, April 9, 2003, at 02:25  PM, Geoff Keating wrote:
> > Why don't you just use the support that GCC already has for
> > detecting the probability that a block will be executed?
> 
> Because it's at the tree level he's talking about, not the RTL
> level.

FWIW, once tree-ssa-vrp is implemented, you get branch
prediction with it for free.  Would that help?

Greetz
Steven

Re: How to detect whether we're inside of a loop??

[Daniel Berlin]

On Wednesday, April 9, 2003, at 02:25  PM, Geoff Keating wrote:

> "Kaveh R. Ghazi" <ghazi@caip.rutgers.edu> writes:
>
>> I was interested in experimenting with heuristics which might expand a
>> builtin depending on whether at the point of expansion we're in a loop
>> or not.  E.g. It might make sense to expand something which might
>> create slightly larger code only if we think it's likely that it'll be
>> executed a number of times.  I'm guessing that being inside a loop is
>> one way to increase that probability.  Thus I was curious if there's a
>> way to detect this.
>
> Why don't you just use the support that GCC already has for detecting
> the probability that a block will be executed?

Because it's at the tree level he's talking about, not the RTL level.
--Dan

Re: How to detect whether we're inside of a loop??

[Geoff Keating]

"Kaveh R. Ghazi" <ghazi@caip.rutgers.edu> writes:

> I was interested in experimenting with heuristics which might expand a
> builtin depending on whether at the point of expansion we're in a loop
> or not.  E.g. It might make sense to expand something which might
> create slightly larger code only if we think it's likely that it'll be
> executed a number of times.  I'm guessing that being inside a loop is
> one way to increase that probability.  Thus I was curious if there's a
> way to detect this.

Why don't you just use the support that GCC already has for detecting
the probability that a block will be executed?

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: How to detect whether we're inside of a loop??

[Richard Earnshaw]

> I was interested in experimenting with heuristics which might expand a
> builtin depending on whether at the point of expansion we're in a loop
> or not.  E.g. It might make sense to expand something which might
> create slightly larger code only if we think it's likely that it'll be
> executed a number of times.  I'm guessing that being inside a loop is
> one way to increase that probability.  Thus I was curious if there's a
> way to detect this.  So my questions are:
> 
> 1.  Can we detect this?  (C'mon there's gotta be a way.)
> 
> 2.  Is it cheap to detect or a heavy calculation?  Ie. I don't want to
>     have to do an expensive optimization pass just to figure this out.
>     I'm hoping that I can just access a bit somewhere that tells me
>     yes or no.
> 
> 3.  Is it practical to detect this at the point I'm interested in,
>     ie. inside an expand_builtin_foo function?
> 
> 4.  Is there another way to conceptually do what I want, ie. detect
>     that the code in question is likely to be executed more than once?
> 
> 5.  Can you explain it all simply enough for me to understand? :-)
> 
> 		Thanks,
> 		--Kaveh

What would it mean if the loop had been unwound or an iteration peeled off?

What would it mean if the loop were inside an inline function which was 
itself called from a loop?

R.

Re: How to detect whether we're inside of a loop??

[Kaveh R. Ghazi]

 > From: Jan Hubicka <hubicka@ucw.cz>
 > 
 > > I was interested in experimenting with heuristics which might expand a
 > > builtin depending on whether at the point of expansion we're in a loop
 > > or not.  E.g. It might make sense to expand something which might
 > > create slightly larger code only if we think it's likely that it'll be
 > > executed a number of times.  I'm guessing that being inside a loop is
 > > one way to increase that probability.  Thus I was curious if there's a
 > > way to detect this.  So my questions are:
 > > 
 > > 1.  Can we detect this?  (C'mon there's gotta be a way.)
 > 
 > I guess cfun->stmt->x_nesting_depth is what you are looking for.
 > Honza

Not quite.  Following your lead I read through stmt.c a bit and if I
understand it correctly, x_nesting_depth records all scopes not just
loops.  E.g. if-then, switches, etc.  Luckily, I quickly found
x_loop_stack which does exactly what I want.  So thanks for putting me
in the right ballpark.

		--Kaveh
--
Kaveh R. Ghazi			ghazi@caip.rutgers.edu

Re: How to detect whether we're inside of a loop??

[Jan Hubicka]

> I was interested in experimenting with heuristics which might expand a
> builtin depending on whether at the point of expansion we're in a loop
> or not.  E.g. It might make sense to expand something which might
> create slightly larger code only if we think it's likely that it'll be
> executed a number of times.  I'm guessing that being inside a loop is
> one way to increase that probability.  Thus I was curious if there's a
> way to detect this.  So my questions are:
> 
> 1.  Can we detect this?  (C'mon there's gotta be a way.)

I guess cfun->stmt->x_nesting_depth is what you are looking for.
Of course I would preffer this to be done using the profile but it is
not available at that point... uhm

Honza
> 
> 2.  Is it cheap to detect or a heavy calculation?  Ie. I don't want to
>     have to do an expensive optimization pass just to figure this out.
>     I'm hoping that I can just access a bit somewhere that tells me
>     yes or no.
> 
> 3.  Is it practical to detect this at the point I'm interested in,
>     ie. inside an expand_builtin_foo function?
> 
> 4.  Is there another way to conceptually do what I want, ie. detect
>     that the code in question is likely to be executed more than once?
> 
> 5.  Can you explain it all simply enough for me to understand? :-)
> 
> 		Thanks,
> 		--Kaveh
> --
> Kaveh R. Ghazi			ghazi@caip.rutgers.edu

How to detect whether we're inside of a loop??

[Kaveh R. Ghazi]

I was interested in experimenting with heuristics which might expand a
builtin depending on whether at the point of expansion we're in a loop
or not.  E.g. It might make sense to expand something which might
create slightly larger code only if we think it's likely that it'll be
executed a number of times.  I'm guessing that being inside a loop is
one way to increase that probability.  Thus I was curious if there's a
way to detect this.  So my questions are:

1.  Can we detect this?  (C'mon there's gotta be a way.)

2.  Is it cheap to detect or a heavy calculation?  Ie. I don't want to
    have to do an expensive optimization pass just to figure this out.
    I'm hoping that I can just access a bit somewhere that tells me
    yes or no.

3.  Is it practical to detect this at the point I'm interested in,
    ie. inside an expand_builtin_foo function?

4.  Is there another way to conceptually do what I want, ie. detect
    that the code in question is likely to be executed more than once?

5.  Can you explain it all simply enough for me to understand? :-)

		Thanks,
		--Kaveh
--
Kaveh R. Ghazi			ghazi@caip.rutgers.edu