loop optimization in gcc

loop optimization in gcc

[sandeep soni]

Hi All,

I have been studying the gcc code lately as part of my project.I have
got info from this mailing list about CFG and DFG information.I want
to know how gcc uses this information to perform loop optimization?
Does it Follow any particular algorithm or in particular what are the
different techniques that it uses to parallelize the code by
performing the loop optimizations?(correct me please if this sentence
is not right).

If possible please provide any pointers to any form of literature
available regarding it.

Thanks in advance.



-- 
cheers
sandy

Re: loop optimization in gcc

[Ian Lance Taylor]

sandeep soni <saintiwara@gmail.com> writes:

> I have been studying the gcc code lately as part of my project.I have
> got info from this mailing list about CFG and DFG information.I want
> to know how gcc uses this information to perform loop optimization?
> Does it Follow any particular algorithm or in particular what are the
> different techniques that it uses to parallelize the code by
> performing the loop optimizations?(correct me please if this sentence
> is not right).

I'm not really sure what you are asking.  gcc supports OpenMP for
parallelizing loops.  That is mostly done in the frontends.  I don't
think it has much to do with the CFG or DFG, but I'm not very familiar
with the code.  The other loop optimizations are mostly in
tree-ssa-loop-*.c, q.v.

Ian

Re: loop optimization in gcc

[sandeep soni]

On Mon, Oct 12, 2009 at 12:13 PM, Ian Lance Taylor <iant@google.com> wrote:

> I'm not really sure what you are asking.  gcc supports OpenMP for
> parallelizing loops.  That is mostly done in the frontends.

I have been told that openMP does parallelizing of loops, but these
types of optimizations are generally done for a large clusters of
computers (Is this correct?).Meaning thereby that these optimizations
are not used for low scale systems.

What i aim for in parallelizing, is to improve the speed of execution
of relatively simple tools used for distribution of packages.(for eg:
speed improvements in using dwarf utilities and elf utilities during
distribution of software to test for backward compatibilities and
dependency checks) for modestly multicore (2 or 4 to start out)
processors.A few ideas in this regard are brewing in which i will be
trying out along with my team in the near future.

I will also be happy to know if there are any good ideas to improve
the speed of execution by optimizing the loops with a focus to
parallelize them than the one which are in place in gcc so that i can
try this out with my team.


-- 
cheers
sandy

Re: loop optimization in gcc

[Ian Lance Taylor]

sandeep soni <saintiwara@gmail.com> writes:

> On Mon, Oct 12, 2009 at 12:13 PM, Ian Lance Taylor <iant@google.com> wrote:
>
>> I'm not really sure what you are asking.  gcc supports OpenMP for
>> parallelizing loops.  That is mostly done in the frontends.
>
> I have been told that openMP does parallelizing of loops, but these
> types of optimizations are generally done for a large clusters of
> computers (Is this correct?).Meaning thereby that these optimizations
> are not used for low scale systems.

That is not correct.  OpenMP parallelizes loops within a single
system, using pthreads.  It does not parallelize loops across
different systems.

Ian

Re: loop optimization in gcc

[sandeep soni]

On Mon, Oct 12, 2009 at 11:28 PM, Ian Lance Taylor <iant@google.com> wrote:
> sandeep soni <saintiwara@gmail.com> writes:
>
>> On Mon, Oct 12, 2009 at 12:13 PM, Ian Lance Taylor <iant@google.com> wrote:
>>
>>> I'm not really sure what you are asking.  gcc supports OpenMP for
>>> parallelizing loops.  That is mostly done in the frontends.
>>
>> I have been told that openMP does parallelizing of loops, but these
>> types of optimizations are generally done for a large clusters of
>> computers (Is this correct?).Meaning thereby that these optimizations
>> are not used for low scale systems.
>
> That is not correct.  OpenMP parallelizes loops within a single
> system, using pthreads.  It does not parallelize loops across
> different systems.
>
> Ian
>

Well i was under a misconception then.Thanks for clearing this.


-- 
cheers
sandy

Re: loop optimization in gcc

[Tobias Grosser]

On Sun, 2009-10-11 at 20:20 +0530, sandeep soni wrote:
> Hi All,
> 
> I have been studying the gcc code lately as part of my project.I have
> got info from this mailing list about CFG and DFG information.I want
> to know how gcc uses this information to perform loop optimization?
> Does it Follow any particular algorithm or in particular what are the
> different techniques that it uses to parallelize the code by
> performing the loop optimizations?(correct me please if this sentence
> is not right).
> 
> If possible please provide any pointers to any form of literature
> available regarding it.
> 
> Thanks in advance.

Hi,

you also might want to take a look at the Graphite project.
http://gcc.gnu.org/wiki/Graphite where we do loop optimizations and
automatic parallelization based on the polytop model. If you need any
help feel free to ask.

Tobias

Re: loop optimization in gcc

[sandeep soni]

> Hi,
>
> you also might want to take a look at the Graphite project.
> http://gcc.gnu.org/wiki/Graphite where we do loop optimizations and
> automatic parallelization based on the polytop model. If you need any
> help feel free to ask.
>
> Tobias
>
>

Hi,

This seems to be quite interesting and challenging.Moreover,it is very
close to what we are trying to achieve as well (on a small scale that
is).I have started preliminary reading on the polytope model and the
working of GRAPHITE. I will ask you if i face any doubts.It would be
nice to contribute to this project.


For the starters, can you tell me if GRAPHITE also does source to
source transformations or otherwise to optimize??Coz i had read
somewhere else that the polyhedral model used source to source
transformations.

-- 
cheers
sandy

Re: loop optimization in gcc

[Tobias Grosser]

On Wed, 2009-10-14 at 20:12 +0530, sandeep soni wrote:
> > Hi,
> >
> > you also might want to take a look at the Graphite project.
> > http://gcc.gnu.org/wiki/Graphite where we do loop optimizations and
> > automatic parallelization based on the polytop model. If you need any
> > help feel free to ask.
> >
> > Tobias
> >
> >
> 
> Hi,
> 
> This seems to be quite interesting and challenging.Moreover,it is very
> close to what we are trying to achieve as well (on a small scale that
> is).I have started preliminary reading on the polytope model and the
> working of GRAPHITE. I will ask you if i face any doubts.It would be
> nice to contribute to this project.
> 
> 
> For the starters, can you tell me if GRAPHITE also does source to
> source transformations or otherwise to optimize??Coz i had read
> somewhere else that the polyhedral model used source to source
> transformations.

Hi,

you are right. There are several polytope frameworks that work on the
source code level (LooPo, Cloog/Clan from Cedric Bastoul), however
Graphite works on the intermediate level tree-ssa in gcc. Therefore we
can not do any source to source transformations.
The idea is to not be limited to specific input languages or special
formatting of the code, but to be able to use the powerful analysis in
the gcc middle end.
This allows us to work on any input language and to detect loops that do
not even look like a loop in the input program (goto-loops). Using the
powerful scalar evolution framework in gcc Graphite also handles loops
that do not look like affine linear loops.
This is a powerful approach in its earlier stages. Basic loops and
simple code transformations already work, but there is still a lot left
to be done.

Tobi

Re: loop optimization in gcc

[sandeep soni]

On Wed, Oct 14, 2009 at 9:02 PM, Tobias Grosser
<grosser@fim.uni-passau.de> wrote:
> On Wed, 2009-10-14 at 20:12 +0530, sandeep soni wrote:
>> > Hi,
>> >
>> > you also might want to take a look at the Graphite project.
>> > http://gcc.gnu.org/wiki/Graphite where we do loop optimizations and
>> > automatic parallelization based on the polytop model. If you need any
>> > help feel free to ask.
>> >
>> > Tobias
>> >
>> >
>>
>> Hi,
>>
>> This seems to be quite interesting and challenging.Moreover,it is very
>> close to what we are trying to achieve as well (on a small scale that
>> is).I have started preliminary reading on the polytope model and the
>> working of GRAPHITE. I will ask you if i face any doubts.It would be
>> nice to contribute to this project.
>>
>>
>> For the starters, can you tell me if GRAPHITE also does source to
>> source transformations or otherwise to optimize??Coz i had read
>> somewhere else that the polyhedral model used source to source
>> transformations.
>
> Hi,
>
> you are right. There are several polytope frameworks that work on the
> source code level (LooPo, Cloog/Clan from Cedric Bastoul), however
> Graphite works on the intermediate level tree-ssa in gcc. Therefore we
> can not do any source to source transformations.
> The idea is to not be limited to specific input languages or special
> formatting of the code, but to be able to use the powerful analysis in
> the gcc middle end.
> This allows us to work on any input language and to detect loops that do
> not even look like a loop in the input program (goto-loops). Using the
> powerful scalar evolution framework in gcc Graphite also handles loops
> that do not look like affine linear loops.
> This is a powerful approach in its earlier stages. Basic loops and
> simple code transformations already work, but there is still a lot left
> to be done.
>
> Tobi
>
>

Hi,

 Sounds absolutely convincing to me. I am too keen to contribute in
this in any way possible.I will first try to understand how it works
totally .Would you mind me pressing on with some of issues in the near
future? I am afraid though that they might be a bit more theoretical
to begin with.


-- 
cheers
sandy

Re: loop optimization in gcc

[Tobias Grosser]

On Wed, 2009-10-14 at 23:56 +0530, sandeep soni wrote:
> On Wed, Oct 14, 2009 at 9:02 PM, Tobias Grosser
> <grosser@fim.uni-passau.de> wrote:
> > On Wed, 2009-10-14 at 20:12 +0530, sandeep soni wrote:
> >> > Hi,
> >> >
> >> > you also might want to take a look at the Graphite project.
> >> > http://gcc.gnu.org/wiki/Graphite where we do loop optimizations and
> >> > automatic parallelization based on the polytop model. If you need any
> >> > help feel free to ask.
> >> >
> >> > Tobias
> >> >
> >> >
> >>
> >> Hi,
> >>
> >> This seems to be quite interesting and challenging.Moreover,it is very
> >> close to what we are trying to achieve as well (on a small scale that
> >> is).I have started preliminary reading on the polytope model and the
> >> working of GRAPHITE. I will ask you if i face any doubts.It would be
> >> nice to contribute to this project.
> >>
> >>
> >> For the starters, can you tell me if GRAPHITE also does source to
> >> source transformations or otherwise to optimize??Coz i had read
> >> somewhere else that the polyhedral model used source to source
> >> transformations.
> >
> > Hi,
> >
> > you are right. There are several polytope frameworks that work on the
> > source code level (LooPo, Cloog/Clan from Cedric Bastoul), however
> > Graphite works on the intermediate level tree-ssa in gcc. Therefore we
> > can not do any source to source transformations.
> > The idea is to not be limited to specific input languages or special
> > formatting of the code, but to be able to use the powerful analysis in
> > the gcc middle end.
> > This allows us to work on any input language and to detect loops that do
> > not even look like a loop in the input program (goto-loops). Using the
> > powerful scalar evolution framework in gcc Graphite also handles loops
> > that do not look like affine linear loops.
> > This is a powerful approach in its earlier stages. Basic loops and
> > simple code transformations already work, but there is still a lot left
> > to be done.
> >
> > Tobi
> >
> >
> 
> Hi,
> 
>  Sounds absolutely convincing to me. I am too keen to contribute in
> this in any way possible.I will first try to understand how it works
> totally .Would you mind me pressing on with some of issues in the near
> future? I am afraid though that they might be a bit more theoretical
> to begin with.

Sure. Just drop me a line