Re: [llvm-dev] Register Allocation Graph Coloring algorithm and Others

[Bruce Hoult]

So, both AVR and RISC-V are fairly register-rich with usually 32. RV32E
only has 16, but that's still a lot better than i386. If you use a lot of
16 bit integers then AVR also only has effectively 16 registers (or a more
with a mix of 8 and 16 bit variables). 32 bit integers should be rare in
AVR code, but soft float/double variables are common in Arduino code (both
are implemented as 32 bits), so you only have room for 8 of those.

RISC-V doesn't have any hard constraints on something that *must* go in a
certain register, except the usual argument passing/return convention.
There is a an advantage to allocating both the data src/dst register and
the pointer base register for a load or store from x8-x15 (s0-1,a0-5) as
much as possible as this allows the assembler to use a two byte instruction
instead of a four byte instruction.

I haven't look at AVR in detail for a while, but I seem to recall the top
six registers make up three 16 bit pointer registers X,Y,Z. Any of them can
be used for (C language) *p, *--p, *p++, only Y&Z can be used for p->foo,
and only Z can be used for computed jumps (including function link
register) or loading constants from program memory. Also the various
multiply instructions take their 8 bit operands from any registers but
always produce the 16 bit result in r1:r0. Annoying but nowhere near as bad
as i386 as r0 and r1 are not used for anything else. The usual ABI makes r0
a clobber-at-will temp. r1 is supposed to be "always zero", so you need to
CLR it after retrieving (or ignoring) the high bits of a multiply result.

On Thu, Dec 21, 2017 at 3:44 AM, Leslie Zhai via llvm-dev <
llvm-...@lists.llvm.org> wrote:

> Hi Jakob,
>
> Thanks for your kind response!
>
> My usecase is for AVR and RISCV targets, and I just want to learn and
> practice HEA in RA, thanks for your sharing.
>
>
> 在 2017年12月21日 01:25, Jakob Stoklund Olesen 写道:
>
>>
>> On Dec 18, 2017, at 19:03, Leslie Zhai >> lesliez...@llvm.org.cn>> wrote:
>>>
>>
>> Hi Leslie,
>>
>> As others have pointed out, the notion that register allocation is
>> isomorphic to graph coloring is poppycock. There are other important
>> aspects, in particular the placement of spill/fill/copy instructions. The
>> importance of graph coloring relative to spill code placement depends on
>> how many registers you have available. If you are generating code for
>> 32-bit x86 which has only 6-7 general purpose registers, you will have so
>> much spill code and short live ranges that graph coloring doesn’t matter
>> much at all. On the other hand, if you have 32 registers like Chaitin did,
>> you have much less spilling in typical code, and the graph coloring aspect
>> becomes important.
>>
>> Early compilers would keep each local variable in a stack slot, and the
>> register allocation optimization would literally allocate a whole local
>> variable to a register. The C “register” keyword makes sense in that
>> context. Later improvements like copy coalescing and live range splitting
>> meant that multiple local variables could use the same register and a
>> variable could live in different places at different times. It is sometimes
>> useful to take this development to its logical extreme and look at register
>> allocation as a caching problem: The register allocator’s job is to make
>> sure that values are available to the instructions the need them, using the
>> registers as a cache to get the values there in the most efficient way
>> possible.
>>
>> Guo, J., Garzarán, M. J., & Padua, D. (2004). The Power of
>> Belady’s Algorithm in Register Allocation for Long Basic Blocks.
>> In Languages and Compilers for Parallel Computing (Vol. 2958, pp.
>> 374–389). Berlin, Heidelberg: Springer Berlin Heidelberg.
>> http://doi.org/10.1007/978-3-540-24644-2_24
>>
>> Braun, M., & Hack, S. (2009). Register spilling and live-range
>> splitting for SSA-form programs. International Conference on
>> Compiler Construction.
>>
>>
>> When you look at register allocation that way, the graph coloring aspect
>> almost disappears. The optimum approach is probably somewhere in the middle.
>>
>> A third important aspect is register constraints on individual
>> instructions. Sometimes you almost need a little constraint solver just to
>> figure out a valid register assignment for a single instruction. Preston
>> Briggs dealt with this in his thesis, but it hasn’t gotten as much
>> attention as graph coloring since.
>>
>> Pereira, F. Q., & Palsberg, J. (2008). Register allocation by
>> puzzle solving.
>>
>>
>> Regards,
>> /jakob
>>
>>
> --
> Regards,
> Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/
>
>
>
>
> ___
> LLVM Developers mailing list
> llvm-...@lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

Re: Who generate .rela.debug_info?

[Nancy]

> It's not clear to my why you want this level of detail -- curiosity?
I need to enable this feature on open64.

Thank you all for your great infos.

-- 
Best Regards,
Yu Rong Tan

Re: typeid name of non-throwing function type

[Stephan Bergmann]

On 12/21/2017 07:52 AM, Stephan Bergmann wrote:

Thinking a bit more about it, I think that's rather a bug in GCC, right?


~ cat test72.cc
#include 
#include 
void f1();
void f2() noexcept;
int main() { std::cout << (typeid(f1) == typeid(f2)) << '\n'; }

~ g++ -std=c++17 test72.cc
~ ./a.out
1


should print "0" instead of "1" (like the version does that compares

   (typeid(&f1) == typeid(&f2))

instead).


filed  "C++17: 
typeinfo for noexcept function lacks noexcept information"

Re: [llvm-dev] Register Allocation Graph Coloring algorithm and Others

[Leslie Zhai]

Hi Bruce,

Thanks for your sharing!

I am porting GlobalISel to RISCV target[1], the highest priority in the 
TODO list[2], welcome to contribute to lowRISC, if fixed all the issues, 
then I could try to implement RegAllocGraphColoring in HEA and write 
great Machine Schedulers.


[1] https://github.com/lowRISC/riscv-llvm/issues/19
[2] https://github.com/lowRISC/riscv-llvm/issues

在 2017年12月21日 19:09, Bruce Hoult 写道:
So, both AVR and RISC-V are fairly register-rich with usually 32. 
RV32E only has 16, but that's still a lot better than i386. If you use 
a lot of 16 bit integers then AVR also only has effectively 16 
registers (or a more with a mix of 8 and 16 bit variables). 32 bit 
integers should be rare in AVR code, but soft float/double variables 
are common in Arduino code (both are implemented as 32 bits), so you 
only have room for 8 of those.


RISC-V doesn't have any hard constraints on something that *must* go 
in a certain register, except the usual argument passing/return 
convention. There is a an advantage to allocating both the data 
src/dst register and the pointer base register for a load or store 
from x8-x15 (s0-1,a0-5) as much as possible as this allows the 
assembler to use a two byte instruction instead of a four byte 
instruction.


I haven't look at AVR in detail for a while, but I seem to recall the 
top six registers make up three 16 bit pointer registers X,Y,Z. Any of 
them can be used for (C language) *p, *--p, *p++, only Y&Z can be used 
for p->foo, and only Z can be used for computed jumps (including 
function link register) or loading constants from program memory. Also 
the various multiply instructions take their 8 bit operands from any 
registers but always produce the 16 bit result in r1:r0. Annoying but 
nowhere near as bad as i386 as r0 and r1 are not used for anything 
else. The usual ABI makes r0 a clobber-at-will temp. r1 is supposed to 
be "always zero", so you need to CLR it after retrieving (or ignoring) 
the high bits of a multiply result.


On Thu, Dec 21, 2017 at 3:44 AM, Leslie Zhai via llvm-dev 
mailto:llvm-...@lists.llvm.org>> wrote:


Hi Jakob,

Thanks for your kind response!

My usecase is for AVR and RISCV targets, and I just want to learn
and practice HEA in RA, thanks for your sharing.


在 2017年12月21日 01:25, Jakob Stoklund Olesen 写道:


On Dec 18, 2017, at 19:03, Leslie Zhai
mailto:lesliez...@llvm.org.cn>
>> wrote:


Hi Leslie,

As others have pointed out, the notion that register
allocation is isomorphic to graph coloring is poppycock. There
are other important aspects, in particular the placement of
spill/fill/copy instructions. The importance of graph coloring
relative to spill code placement depends on how many registers
you have available. If you are generating code for 32-bit x86
which has only 6-7 general purpose registers, you will have so
much spill code and short live ranges that graph coloring
doesn’t matter much at all. On the other hand, if you have 32
registers like Chaitin did, you have much less spilling in
typical code, and the graph coloring aspect becomes important.

Early compilers would keep each local variable in a stack
slot, and the register allocation optimization would literally
allocate a whole local variable to a register. The C
“register” keyword makes sense in that context. Later
improvements like copy coalescing and live range splitting
meant that multiple local variables could use the same
register and a variable could live in different places at
different times. It is sometimes useful to take this
development to its logical extreme and look at register
allocation as a caching problem: The register allocator’s job
is to make sure that values are available to the instructions
the need them, using the registers as a cache to get the
values there in the most efficient way possible.

    Guo, J., Garzarán, M. J., & Padua, D. (2004). The Power of
    Belady’s Algorithm in Register Allocation for Long Basic
Blocks.
    In Languages and Compilers for Parallel Computing (Vol.
2958, pp.
    374–389). Berlin, Heidelberg: Springer Berlin Heidelberg.
http://doi.org/10.1007/978-3-540-24644-2_24


    Braun, M., & Hack, S. (2009). Register spilling and live-range
    splitting for SSA-form programs. International Conference on
    Compiler Construction.


When you look at register allocation that way, the graph
coloring aspect almost disappears. The optimum approach is
probably somewhere in the middle.

A third important aspect is register constraint

Today's conversion feature

[Eric S. Raymond]

I have implemented the ability for an email address to be declared as
an alias in an author map file.  When this is done, that alias will be 
recognized
in ChangeLog attributions and mapped back to the base address for
which it is an alias when filling inm Author attributions.  However,
the timezone on the alias 

This covers contributors who have had multiple addresses in the past
(possibly in different timezones), aggergating all their authorship
attributions to their preferred addresses.  (This will become
especially relevant if the policy dcision to attribute to gnu.org
addresses when possible is made.)

Several contributors had sent me past aliases.  Now they're used.

Note: if you have not yet reported a timezone, please try to send me
an IANA zone designation - e.g. "Europe/Berlin" rather than "CET".
This decreases the odds that my date-resolution logic will do
something not quite right on dates with daylight saving time in
effect.
-- 
http://www.catb.org/~esr/";>Eric S. Raymond

The kind of charity you can force out of people nourishes about as much as
the kind of love you can buy --- and spreads even nastier diseases.

Today's conversion feature - correction

[Eric S. Raymond]

I wrote:
>I have implemented the ability for an email address to be declared as
>Lan alias in an author map file.  When this is done, that alias will be 
>recognized
>in ChangeLog attributions and mapped back to the base address for
>which it is an alias when filling inm Author attributions.  However,
>the timezone on the alias 

Truncated sentence.  The timezone will be used as is.
-- 
http://www.catb.org/~esr/";>Eric S. Raymond

The kind of charity you can force out of people nourishes about as much as
the kind of love you can buy --- and spreads even nastier diseases.

How far should we trust ChangeLog attribution dates?

[Eric S. Raymond]

The 'changelogs' command of reposugeon attempts to fill in author
attributions (author and authorship date) by mining Changelogs.  It
makes use of the fact that changesets often contain a change band for
a Changelog and that change band normally contains or can be referred
to exactly one attribution line.

This is a recent feature - I developed it while doing the lift of
GNUPLOT from CVS in early September, a trivial and tiny affair
compared to *this* conversion. The code is pretty adaptable and pulls
sense out of a larger percentage of attribution situations than you
might expect, but it has some significant limitations.

It can reliably pull email addresses for authors - the error (false
attribution) rate on this is pretty low.  Authorship dates are a
different matter.

One limitation is that dates are normally given only as YMD; we don't
get time of day, though as Joseph Myers pointed out we will from some
older GCC commits.  Since there's no right way to complete a YMD, we
complete with the committer's time of day and timezone.

# Rationale: If the author is the committer and
# the attribution date is the same day as the
# commit, this is probably wthin seconds or minutes
# of right.  On a different day with the same
# committer this gets the timezone right. If
# committer is different and day is different we're
# making up data out of thin air, but it at least
# is no worse than any other random choice and
# has the following good properties: (1) no
# later than the committer date, and (2) has same
# mm:ss, making it possible to match the
# committer date in a display even if we don't
# know whether it's local or UTC.

Another problem, as Joseph has pointed out, is that the YMD we get is no
better than the manually-entered information in the Changelog; humans
sometimes garble these, for example by swapping month with day.

Joseph's reaction when hearing about this feature was to suggest ignoring
the authorship date and simply filling in the committer date.  I could
write a policy switch to do that easily enough.

However, another effect of having done GNUPLOT recently is that I
audited for dates that were obviously bogus (it was small enough for
that to be practical, about as old as GCC but only 10K commits) and
only found a tiny number - 2 or 3 - of bogons.  What I did, therefore,
is trust the dates but include in the conversion commentary a description
of the limitations and uncertainty in the data.

We really have three possible policies here, and the choice among them
is partly a philosophical:

(i) Don't trust the authorship dates.  Clobber them with commit dates.
Has the advantage that all dates are of consistent quality, and the
disadvantage that if the author and committer aren't the same person
the quality is "always wrong, and by an unbounded amount of time".

(ii) Always trust the authorship dates.  Most will be right to within
24 hours.  A few percent will be garbage. (This is what reposurgeon
did last week.)

(iii) Trust after filtering for obvious bogons like (a) author date in
the future of the commit date, (b) impossible month or year number. If
the filter fails use the committer YMD. (This is what reposurgeon does now.)

I think (iii) wins here, if the figure of merit is "lowest cumulative
authorship-time error over the whole history".

But this is a decision for the customer(s) to make.
-- 
http://www.catb.org/~esr/";>Eric S. Raymond

gcc-7-20171221 is now available

[gccadmin]

Snapshot gcc-7-20171221 is now available on
  ftp://gcc.gnu.org/pub/gcc/snapshots/7-20171221/
and on various mirrors, see http://gcc.gnu.org/mirrors.html for details.

This snapshot has been generated from the GCC 7 SVN branch
with the following options: svn://gcc.gnu.org/svn/gcc/branches/gcc-7-branch 
revision 255959

You'll find:

 gcc-7-20171221.tar.xzComplete GCC

  SHA256=19333063d5b8449ab4363df09d7e3dd23f9d7b5dd620608cdf560a779409c071
  SHA1=ce14b31f7b1a68b755f6a97398da79c6204b075a

Diffs from 7-20171214 are available in the diffs/ subdirectory.

When a particular snapshot is ready for public consumption the LATEST-7
link is updated and a message is sent to the gcc list.  Please do not use
a snapshot before it has been announced that way.

Re: How far should we trust ChangeLog attribution dates?

[Jason Merrill]

On Thu, Dec 21, 2017 at 4:19 PM, Eric S. Raymond  wrote:
> The 'changelogs' command of reposugeon attempts to fill in author
> attributions (author and authorship date) by mining Changelogs.  It
> makes use of the fact that changesets often contain a change band for
> a Changelog and that change band normally contains or can be referred
> to exactly one attribution line.
>
> This is a recent feature - I developed it while doing the lift of
> GNUPLOT from CVS in early September, a trivial and tiny affair
> compared to *this* conversion. The code is pretty adaptable and pulls
> sense out of a larger percentage of attribution situations than you
> might expect, but it has some significant limitations.
>
> It can reliably pull email addresses for authors - the error (false
> attribution) rate on this is pretty low.  Authorship dates are a
> different matter.
>
> One limitation is that dates are normally given only as YMD; we don't
> get time of day, though as Joseph Myers pointed out we will from some
> older GCC commits.  Since there's no right way to complete a YMD, we
> complete with the committer's time of day and timezone.
>
> # Rationale: If the author is the committer and
> # the attribution date is the same day as the
> # commit, this is probably wthin seconds or minutes
> # of right.  On a different day with the same
> # committer this gets the timezone right. If
> # committer is different and day is different we're
> # making up data out of thin air, but it at least
> # is no worse than any other random choice and
> # has the following good properties: (1) no
> # later than the committer date, and (2) has same
> # mm:ss, making it possible to match the
> # committer date in a display even if we don't
> # know whether it's local or UTC.
>
> Another problem, as Joseph has pointed out, is that the YMD we get is no
> better than the manually-entered information in the Changelog; humans
> sometimes garble these, for example by swapping month with day.
>
> Joseph's reaction when hearing about this feature was to suggest ignoring
> the authorship date and simply filling in the committer date.  I could
> write a policy switch to do that easily enough.
>
> However, another effect of having done GNUPLOT recently is that I
> audited for dates that were obviously bogus (it was small enough for
> that to be practical, about as old as GCC but only 10K commits) and
> only found a tiny number - 2 or 3 - of bogons.  What I did, therefore,
> is trust the dates but include in the conversion commentary a description
> of the limitations and uncertainty in the data.
>
> We really have three possible policies here, and the choice among them
> is partly a philosophical:
>
> (i) Don't trust the authorship dates.  Clobber them with commit dates.
> Has the advantage that all dates are of consistent quality, and the
> disadvantage that if the author and committer aren't the same person
> the quality is "always wrong, and by an unbounded amount of time".
>
> (ii) Always trust the authorship dates.  Most will be right to within
> 24 hours.  A few percent will be garbage. (This is what reposurgeon
> did last week.)
>
> (iii) Trust after filtering for obvious bogons like (a) author date in
> the future of the commit date, (b) impossible month or year number. If
> the filter fails use the committer YMD. (This is what reposurgeon does now.)
>
> I think (iii) wins here, if the figure of merit is "lowest cumulative
> authorship-time error over the whole history".

YMD in the ChangeLog is typically commit date rather than authorship
date anyway, so (i) and (iii) shouldn't differ much at all, and (i)
seems simpler.

Jason

Re: How far should we trust ChangeLog attribution dates?

[Eric S. Raymond]

Jason Merrill :
> YMD in the ChangeLog is typically commit date rather than authorship
> date anyway, so (i) and (iii) shouldn't differ much at all, and (i)
> seems simpler.

I have not generally observed this to be true. Maybe it's a GCC-local thing?

When I was an active Emacs contributor but did not have commit access
yet, it was strongly expected that if you shipped a patch to be merged
it would include a ChangeLog entry.  The attribution line would be
therefore have to be the date you made your patch - you couldn't know
the commit date in advance.

Is this not general practice on FSF projects?
-- 
http://www.catb.org/~esr/";>Eric S. Raymond

My work is funded by the Internet Civil Engineering Institute: https://icei.org
Please visit their site and donate: the civilization you save might be your own.

Re: How far should we trust ChangeLog attribution dates?

[Jeff Law]

On 12/21/2017 03:55 PM, Eric S. Raymond wrote:
> Jason Merrill :
>> YMD in the ChangeLog is typically commit date rather than authorship
>> date anyway, so (i) and (iii) shouldn't differ much at all, and (i)
>> seems simpler.
> 
> I have not generally observed this to be true. Maybe it's a GCC-local thing?
I think we've routinely made the ChangeLog date the commit date.


> Is this not general practice on FSF projects?
Unsure.

jeff

Re: How far should we trust ChangeLog attribution dates?

[Eric S. Raymond]

Jeff Law :
> I think we've routinely made the ChangeLog date the commit date.

Ah, so you modify patches as they come in?

I guess I'd better add that policy switch.
-- 
http://www.catb.org/~esr/";>Eric S. Raymond

My work is funded by the Internet Civil Engineering Institute: https://icei.org
Please visit their site and donate: the civilization you save might be your own.

Re: How far should we trust ChangeLog attribution dates?

[Jeff Law]

On 12/21/2017 04:13 PM, Eric S. Raymond wrote:
> Jeff Law :
>> I think we've routinely made the ChangeLog date the commit date.
> 
> Ah, so you modify patches as they come in?
Yes we routinely twiddle the ChangeLog dates.  In fact we tried to
discourage folks from including the date/author line in their patch
submissions in tthe past (with marginal success).

I think glibc does the same.

jeff

Re: How far should we trust ChangeLog attribution dates?

[Eric S. Raymond]

Jeff Law :
> On 12/21/2017 04:13 PM, Eric S. Raymond wrote:
> > Jeff Law :
> >> I think we've routinely made the ChangeLog date the commit date.
> > 
> > Ah, so you modify patches as they come in?
> Yes we routinely twiddle the ChangeLog dates.  In fact we tried to
> discourage folks from including the date/author line in their patch
> submissions in tthe past (with marginal success).
> 
> I think glibc does the same.

I was unaware of this. But I have just implemented and am now smoke-testing
a --use-committer-date policy switch for the changeLogs command.  I will
add it to the lift file.
-- 
http://www.catb.org/~esr/";>Eric S. Raymond

My work is funded by the Internet Civil Engineering Institute: https://icei.org
Please visit their site and donate: the civilization you save might be your own.

Re: How far should we trust ChangeLog attribution dates?

[Joseph Myers]

On Thu, 21 Dec 2017, Eric S. Raymond wrote:

> Jeff Law :
> > I think we've routinely made the ChangeLog date the commit date.
> 
> Ah, so you modify patches as they come in?

Yes.  It's explicitly documented at 
https://gcc.gnu.org/svnwrite.html#checkin - "Use the current date/time for 
the ChangeLog entry, not the time that the patch was submitted.".

(Personally I find author dates generally unhelpful when they differ 
significantly from commit dates - author dates on a patch or patch series 
that was many times revised and rebased tend to relate to an old version 
of the patch and provide no clue to when one might find discussions 
relating to anything similar to the final committed version - they also 
mean you need to explicitly query with "git tag --contains" to see what 
releases had a fix, or look at commit dates, rather than knowing it at a 
glance from the date displayed by default which is the author date.)

-- 
Joseph S. Myers
jos...@codesourcery.com

Re: How far should we trust ChangeLog attribution dates?

[Eric S. Raymond]

Joseph Myers :
> On Thu, 21 Dec 2017, Eric S. Raymond wrote:
> 
> > Jeff Law :
> > > I think we've routinely made the ChangeLog date the commit date.
> > 
> > Ah, so you modify patches as they come in?
> 
> Yes.  It's explicitly documented at 
> https://gcc.gnu.org/svnwrite.html#checkin - "Use the current date/time for 
> the ChangeLog entry, not the time that the patch was submitted.".

OK.  Your desired policy is now selected in the lift file.
-- 
http://www.catb.org/~esr/";>Eric S. Raymond

My work is funded by the Internet Civil Engineering Institute: https://icei.org
Please visit their site and donate: the civilization you save might be your own.