Extract SCoP coverage information from GRAPHITE
Simone Pellegrini
I would like to whether is possible to extract from GCC information on
SCoP region covered by GRAPHITE. I saw this kind of work has been done
by several people in publications and I need to compare my tool with
GCC in terms of coverage.
What it would be ideal to have for me is the number of SCoP which have
been found in the input program and the number of statements within
the SCoPs.
Is there any special flag available in GCC which allows me to do that?
I tried to ask the same question on GCC mailing list but I had no luck
so far.
thanks for the help,
cheers, S. Pellegrini
Tobias Grosser
Hi Simone,
sorry for the slow reply. To get the number of SCoPs you may use the
-fdump-tree-graphite-all flag and look into the dumped output. The
number of statements is as far as I remember not available in this file,
but it should be easy to dump it with the number of SCoPs.
Alternatively, Polly [1] has similar support integrated, but in addition
provides more detailed feedback. Also Andreas Simb�rger (CCed) works on
dynamic coverage, which also takes the number of statement executions
into account.
Cheers
Tobi
moton...@gmail.com
in the case other people are wondering, you also have to enable
optimization (use -O1) and use the -fgraphite-identity flag.
cheers, Simone
On Thu, Sep 29, 2011 at 9:56 PM, Tobias Grosser <tob...@grosser.es> wrote:
> On 09/29/2011 01:36 PM, Simone Pellegrini wrote:
>>
>> Dear all,
>> I would like to whether is possible to extract from GCC information on
>> SCoP region covered by GRAPHITE. I saw this kind of work has been done
>> by several people in publications and I need to compare my tool with
>> GCC in terms of coverage.
>>
>> What it would be ideal to have for me is the number of SCoP which have
>> been found in the input program and the number of statements within
>> the SCoPs.
>>
>> Is there any special flag available in GCC which allows me to do that?
>> I tried to ask the same question on GCC mailing list but I had no luck
>> so far.
>
> Hi Simone,
>
> sorry for the slow reply. To get the number of SCoPs you may use the
> -fdump-tree-graphite-all flag and look into the dumped output. The number of
> statements is as far as I remember not available in this file,
> but it should be easy to dump it with the number of SCoPs.
>
> Alternatively, Polly [1] has similar support integrated, but in addition
> provides more detailed feedback. Also Andreas Simbürger (CCed) works on
moton...@gmail.com
I was able to get the information I was looking for from Gcc. I have
to admit the SCoP analysis in Gcc is kind of weak. I would like to
know whether it is possible to get also some timing information, what
I am interested in is how long the SCoP analysis takes (removed the
frontend time of GCC).
I would also like to consider other tools like LLVM/Polly and
PolyRose. How can I get this detailed information from LLVM/Polly? I
guess the "view-scops" is what I am looking for. Another question is
how do I get timing information for the SCoP analysis in Polly? As
before I only want the time which Polly needs to determine SCoPs.
cheers, Simone
Tobias Grosser
> Hi again,
> I was able to get the information I was looking for from Gcc. I have
> to admit the SCoP analysis in Gcc is kind of weak.
One weakness is that the current detection of SCoPs is not very well
structured, that's why we have implemented a new region-based scop
detection. (You may want to also give it a try). This is mainly a
weakness in terms of code quality.
I assume you were referring to the amount of SCoPs Graphite detects and
optimize. Here you should take into account two things. 1) The SCoP
detection only detects code which Graphite can optimize. This means it
will refuse to detect a SCoP that is a SCoP, but were we did not
implement the code to translate it into a polyhedral description or
where we did not implement code generation. 2) Graphite aims to be
correct. Keep in mind that we are working on C code. Stuff like aliasing
or integer wrapping (due to arithmetic operations or casts) may be well
defined and need to be taken into account.
If you have specific test cases where the Graphite SCoP detection fails
and your work is better, I would be glad to look into them. Also in
general I would be interested to see some documentation/description
of what you are working on, in case it is available.
> I would like to
> know whether it is possible to get also some timing information, what
> I am interested in is how long the SCoP analysis takes (removed the
> frontend time of GCC).
No, we did not add this into the source code. However GCC allows to get
these statistics. Have a look at the file gcc/timevar.def and
gcc/graphite-dependences.c. Here we added the timer
TV_GRAPHITE_DATA_DEPS to time the calculation of data dependences. You
could do something similar for the SCoP detection.
> I would also like to consider other tools like LLVM/Polly and
> PolyRose. How can I get this detailed information from LLVM/Polly? I
> guess the "view-scops" is what I am looking for. Another question is
> how do I get timing information for the SCoP analysis in Polly? As
> before I only want the time which Polly needs to determine SCoPs.
In Polly you can get very basic results from running the following
commands on a llvm-ir file.
"opt -basicaa ${PREPARING_OPTS} -polly-detect -stats file.ll"
"opt -basicaa ${PREPARING_OPTS} -polly-detect -time-passes file.ll"
I would try first with "PREPARING_OPTS="". Later you can copy the
options as used in tools/pollycc.
For a in depth analysis you can have a look at the patches Andreas
Simbuerger posted a couple of weeks ago on the Polly mailing list.
When interpreting the results, please take in mind that the above points
1) and 2) also apply for Polly. We do not detect everything that might
be a SCoP, because in some cases we cannot prove something is
a SCoP, but a lot more often, because we did not implement the
translation of a construct into a polyhedral representation or we
miss the corresponding code generation.
Cheers
Tobi
moton...@gmail.com
> On 10/03/2011 12:12 PM, moton...@gmail.com wrote:
>>
>> Hi again,
>> I was able to get the information I was looking for from Gcc. I have
>> to admit the SCoP analysis in Gcc is kind of weak.
>
> What does it mean to be weak?
I mean the number of SCoPs found is very low. I get a 100x factor in
terms of statement covered and I am working at source code level while
Gcc is working on GIMPLE (and 1 source stmt is usually equals to
several GIMPLE statements). Furthermore, I am doing very basic
analysis, my numbers could get even better if I start dealing with
while loops for example.
It is true that at this point I cannot claim my coverage is complete
as I have to implement the code generation mechanism. Probably, as you
said, I will need to reduce my coverage because I cannot produce back
semantically equivalent code. I will start working on this aspect now
and see how far can I go.
>
> One weakness is that the current detection of SCoPs is not very well
> structured, that's why we have implemented a new region-based scop
> detection. (You may want to also give it a try). This is mainly a weakness
> in terms of code quality.
>
> I assume you were referring to the amount of SCoPs Graphite detects and
> optimize. Here you should take into account two things. 1) The SCoP
> detection only detects code which Graphite can optimize. This means it
> will refuse to detect a SCoP that is a SCoP, but were we did not implement
> the code to translate it into a polyhedral description or where we did not
> implement code generation. 2) Graphite aims to be correct. Keep in mind that
> we are working on C code. Stuff like aliasing or integer wrapping (due to
> arithmetic operations or casts) may be well defined and need to be taken
> into account.
>
> If you have specific test cases where the Graphite SCoP detection fails
> and your work is better, I would be glad to look into them. Also in general
> I would be interested to see some documentation/description
> of what you are working on, in case it is available.
The codes I am using are from the NAS parallel benchmarks which are a
set of OpenMP benchmarks. Because most of the loops in the code are
parallel and almost everything is affine, I was expecting a rather
large number of SCoPs... but this is not the case. My guess is that
GCC analysis is limited because global variables are accessed within
those loops. But again, I know nothing about GCC internals so it could
be I am totally wrong here.
Regarding the compiler I am working... at the moment there is nothing
being released, we are starting to get some results now after a year
of implementation, I hope papers/technical reports will follow soon.
for any reference, the main link is: http://www.dps.uibk.ac.at/insieme/
>
>> I would like to
>>
>> know whether it is possible to get also some timing information, what
>> I am interested in is how long the SCoP analysis takes (removed the
>> frontend time of GCC).
>
> No, we did not add this into the source code. However GCC allows to get
> these statistics. Have a look at the file gcc/timevar.def and
> gcc/graphite-dependences.c. Here we added the timer TV_GRAPHITE_DATA_DEPS to
> time the calculation of data dependences. You could do something similar for
> the SCoP detection.
>
thanks a lot.
>> I would also like to consider other tools like LLVM/Polly and
>> PolyRose. How can I get this detailed information from LLVM/Polly? I
>> guess the "view-scops" is what I am looking for. Another question is
>> how do I get timing information for the SCoP analysis in Polly? As
>> before I only want the time which Polly needs to determine SCoPs.
>
> In Polly you can get very basic results from running the following commands
> on a llvm-ir file.
>
> "opt -basicaa ${PREPARING_OPTS} -polly-detect -stats file.ll"
>
> "opt -basicaa ${PREPARING_OPTS} -polly-detect -time-passes file.ll"
>
> I would try first with "PREPARING_OPTS="". Later you can copy the options as
> used in tools/pollycc.
>
> For a in depth analysis you can have a look at the patches Andreas
> Simbuerger posted a couple of weeks ago on the Polly mailing list.
>
> When interpreting the results, please take in mind that the above points 1)
> and 2) also apply for Polly. We do not detect everything that might be a
> SCoP, because in some cases we cannot prove something is
> a SCoP, but a lot more often, because we did not implement the translation
> of a construct into a polyhedral representation or we
> miss the corresponding code generation.
>
> Cheers
> Tobi
>
Thanks again, I will take this in mind.
cheers, Simone
Tobias Grosser
Is there a way to get these benchmarks without signing an NDA? I just
looked at a similar version available here [1]. Looking e.g. at the file
LU/lu.c I see a lot of very affine looking code. However, I am pretty
sure both Polly and Graphite may currently not detect this code, because
the arrays passed as parameters are not marked 'restricted', which means
possible aliasing does not allow us to translate them into a SCoP. We
may handle this, as soon as we implemented a runtime check for aliasing.
How do you handle aliasing in your SCoP detection? Can you post a simple
function where you detect a SCoP and Graphite does not?
> Regarding the compiler I am working... at the moment there is nothing
> being released, we are starting to get some results now after a year
> of implementation, I hope papers/technical reports will follow soon.
>
> for any reference, the main link is: http://www.dps.uibk.ac.at/insieme/
Ah, alright. If you are interested in detected SCoPs you may also look
into pet [2]. This is a C/C++ front end, which extracts SCoPs.
Especially the way it handles unsigned integers is interesting (because
it is more correct than most other front ends).
>>> I would like to
>>>
>>> know whether it is possible to get also some timing information, what
>>> I am interested in is how long the SCoP analysis takes (removed the
>>> frontend time of GCC).
>>
>> No, we did not add this into the source code. However GCC allows to get
>> these statistics. Have a look at the file gcc/timevar.def and
>> gcc/graphite-dependences.c. Here we added the timer TV_GRAPHITE_DATA_DEPS to
>> time the calculation of data dependences. You could do something similar for
>> the SCoP detection.
>>
>
> thanks a lot
You are welcome.
Cheers
Tobi
[1]
http://www.hpcs.cs.tsukuba.ac.jp/omni-openmp/download/download-benchmarks.html
[2] http://repo.or.cz/w/pet.git
Simone Pellegrini
I gave a try at Polly. I get quite large number of SCoPs and my guess is
that nested SCoPs are counted individually. So if A is nested into B,
they are counted as separate SCoPs. I wonder if there is a way to only
get the number of top level SCoPs (which at then end is the number which
is important because usually you want to apply polyhedral
analysis/transformations on the biggest SCoP).
I tried to get to this information using the -polly-export-cloog flag
but no file is being produced... this is very weird because if I enable
the timing info I see that the module was executed, but I see no file
being produced in the folder. Where those files are stored? Do I have to
add a second flag to allow LLVM to print out data?
My line is:
opt -load /lib/LLVMPolly.so -polly-detect -polly-analyze-ir -stats
-polly-scops -polly-export-cloog -time-passes file.ir
===-------------------------------------------------------------------------===
... Statistics Collected ...
===-------------------------------------------------------------------------===
225 polly-detect - Number of bad regions for Scop: Expression not affine
2 polly-detect - Number of bad regions for Scop: Others
22 polly-detect - Number of bad regions for Scop: Region not simple
278 region - The # of regions
225 region - The # of simple regions
===-------------------------------------------------------------------------===
... Pass execution timing report ...
===-------------------------------------------------------------------------===
Total Execution Time: 0.0067 seconds (0.0108 wall clock)
---User Time--- --User+System-- ---Wall Time--- --- Name ---
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0038 ( 35.5%) Module Verifier
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0022 ( 20.6%) Polly - Detect
static control parts (SCoPs)
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0008 ( 7.4%) Dominator Tree
Construction
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0007 ( 6.6%) Natural Loop
Information
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0007 ( 6.4%) Detect single
entry single exit regions
0.0033 ( 50.0%) 0.0033 ( 50.0%) 0.0007 ( 6.3%) Post-Dominator
Tree Construction
0.0033 ( 50.0%) 0.0033 ( 50.0%) 0.0006 ( 5.3%) Dominance
Frontier Construction
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0004 ( 3.5%) Execute Cloog
code generation
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0004 ( 3.4%) Polly - Create
polyhedral description of Scops
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0003 ( 3.1%) Polly - Export
the Cloog input file (Writes a .cloog file for each Scop)
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0001 ( 1.0%) Scalar
Evolution Analysis
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.4%) Polly - Analyse
the LLVM-IR in the detected regions
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.3%) Polly - Create
independent blocks
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.3%) Preliminary
module verification
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) Target Data Layout
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) No Alias
Analysis (always returns 'may' alias)
0.0067 (100.0%) 0.0067 (100.0%) 0.0108 (100.0%) Total
Thanks again.
cheers, Simone