llvm dev - Jul 2016 - grouping global variables by alignment: safe to do at LLVM level, or only at Clang level?

Dear all,

Howdy! ;-)  This is Abe of the Samsung Austin R&D Center`s compilers team.

As an early part of a project that should help performance on some CPUs, I would
like to cause
global variables [at least from C and C++ programs] to be grouped together
according to their
alignment needs, which should help to slightly reduce RAM requirements in some
cases.  IMO this
should be done at "-O3" and higher levels of optimization [maybe
"-O2" and higher?] and at
"-Oz" [and maybe also at "-Os"].  This change is likely to
break some poorly-written programs
which rely on undefined behavior by assuming that
consecutively-{declared/defined} global
variables are allocated consecutively in RAM, so I propose to allow those
programs to go on
compiling to code that works as the author expected when there is no strong
optimization
imperative for either RAM savings or performance.

My question this time is this: is re-ordering globals at the LLVM level both
possible [without
massive rewriting of LLVM] and safe?  I don`t know whether or not it`s safe
because perhaps
some languages -- unlike C and C++ -- _explicitly_ allow programmers to make the
assumption
that consecutively-written globals at the source-code level map to
consecutively-allocated
globals at run-time.  If so, and if any such language is using LLVM as a
back-end, then
changing that behavior at the LLVM level with _any_ optimization flag may break
programs that
_are_ well-formed according to the rules of their respective source language[s].

Regards,

Abe

Hi Abe,

I don't see why you couldn't make a frontend query in the pass-manager
to
selectively enable such globals reordering/aligning pass. If this is a
discouraged practice noted in docs somewhere and LLVM's goal is to be truly
frontend/platform agnostic, please do correct me. AFAIK, Pass Manager
selects some optimizations based on Optimization Levels (-O2,-O3,etc), so
extending this shouldn't be a challenge.

Regards,
Kevin

Intel WOS

On 25 July 2016 at 15:36, Abe Skolnik via llvm-dev <llvm-dev at
lists.llvm.org>
wrote:
> Dear all,
>
> Howdy! ;-)  This is Abe of the Samsung Austin R&D Center`s compilers
team.
>
> As an early part of a project that should help performance on some CPUs, I
> would like to cause global variables [at least from C and C++ programs] to
> be grouped together according to their alignment needs, which should help
> to slightly reduce RAM requirements in some cases.  IMO this should be done
> at "-O3" and higher levels of optimization [maybe "-O2"
and higher?] and at
> "-Oz" [and maybe also at "-Os"].  This change is likely
to break some
> poorly-written programs which rely on undefined behavior by assuming that
> consecutively-{declared/defined} global variables are allocated
> consecutively in RAM, so I propose to allow those programs to go on
> compiling to code that works as the author expected when there is no strong
> optimization imperative for either RAM savings or performance.
>
> My question this time is this: is re-ordering globals at the LLVM level
> both possible [without massive rewriting of LLVM] and safe?  I don`t know
> whether or not it`s safe because perhaps some languages -- unlike C and C++
> -- _explicitly_ allow programmers to make the assumption that
> consecutively-written globals at the source-code level map to
> consecutively-allocated globals at run-time.  If so, and if any such
> language is using LLVM as a back-end, then changing that behavior at the
> LLVM level with _any_ optimization flag may break programs that _are_
> well-formed according to the rules of their respective source language[s].
>
> Regards,
>
> Abe
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160725/32e9709c/attachment.html>

Dear Kevin,

Thanks for your quick and thoughtful reply.

Please tell me whether or not I have understood you correctly: I think what you
are saying is
that it might be possible to do what I`m talking about at the LLVM level, have
it turned off by
default so it`s safe, have Clang turn it on when the optimization level says to
do so [since
AFAIK all Clang-supported languages allow compilers to re-order globals], and
let other front
ends turn it on if their respective language specifications also allow compilers
to re-order
globals.

If that`s a correct understanding, then I think that`s a great idea.  Thanks
either way, i.e.
even if I _have_ misunderstood. ;-)

Regards,

Abe






On 07/25/2016 06:52 PM, Kevin Choi wrote:
> Hi Abe,
> I don't see why you couldn't make a frontend query in the
pass-manager to
> selectively enable such globals reordering/aligning pass. If this is a
> discouraged practice noted in docs somewhere and LLVM's goal is to be
truly
> frontend/platform agnostic, please do correct me. AFAIK, Pass Manager
> selects some optimizations based on Optimization Levels (-O2,-O3,etc), so
> extending this shouldn't be a challenge.
> Regards,
> Kevin

I do not believe that we guarantee any order of globals.  Unless someone else
points out a case where we do, we should not intro extra complexity to provide a
choice here.

You may want to take a look an unnamed_addr flag on globals.  It may be relevant
here.  (*may*)

Philip


> On Jul 25, 2016, at 3:36 PM, Abe Skolnik via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Dear all,
> 
> Howdy! ;-)  This is Abe of the Samsung Austin R&D Center`s compilers
team.
> 
> As an early part of a project that should help performance on some CPUs, I
would like to cause global variables [at least from C and C++ programs] to be
grouped together according to their alignment needs, which should help to
slightly reduce RAM requirements in some cases.  IMO this should be done at
"-O3" and higher levels of optimization [maybe "-O2" and
higher?] and at "-Oz" [and maybe also at "-Os"].  This
change is likely to break some poorly-written programs which rely on undefined
behavior by assuming that consecutively-{declared/defined} global variables are
allocated consecutively in RAM, so I propose to allow those programs to go on
compiling to code that works as the author expected when there is no strong
optimization imperative for either RAM savings or performance.
> 
> My question this time is this: is re-ordering globals at the LLVM level
both possible [without massive rewriting of LLVM] and safe?  I don`t know
whether or not it`s safe because perhaps some languages -- unlike C and C++ --
_explicitly_ allow programmers to make the assumption that consecutively-written
globals at the source-code level map to consecutively-allocated globals at
run-time.  If so, and if any such language is using LLVM as a back-end, then
changing that behavior at the LLVM level with _any_ optimization flag may break
programs that _are_ well-formed according to the rules of their respective
source language[s].
> 
> Regards,
> 
> Abe
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 25 July 2016 at 15:36, Abe Skolnik via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> My question this time is this: is re-ordering globals at the LLVM level
both
> possible [without massive rewriting of LLVM] and safe?
First, I think it's completely safe as far as LLVM is concerned (and
have no sympathy for any C or C++ developers who might claim to rely
on the order either). In fact it looks like GCC and Clang already do
it differently so the risk is pretty tiny too.

For LTO it's probably fairly simple to do (sort by alignment during MC
emission would be my first stab). In the general case, it's really an
issue for the linker to resolve though (as the only program that
actually gets to see all globals). Probably with the help of
"-fdata-sections" on ELF targets. But it doesn't look like either
of
the GNU linkers do support it.

Cheers.

Tim.

> On Jul 25, 2016, at 3:36 PM, Abe Skolnik via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Dear all,
> 
> Howdy! ;-)  This is Abe of the Samsung Austin R&D Center`s compilers
team.
> 
> As an early part of a project that should help performance on some CPUs, I
would like to cause global variables [at least from C and C++ programs] to be
grouped together according to their alignment needs, which should help to
slightly reduce RAM requirements in some cases.  IMO this should be done at
"-O3" and higher levels of optimization [maybe "-O2" and
higher?] and at "-Oz" [and maybe also at "-Os"].  This
change is likely to break some poorly-written programs which rely on undefined
behavior by assuming that consecutively-{declared/defined} global variables are
allocated consecutively in RAM, so I propose to allow those programs to go on
compiling to code that works as the author expected when there is no strong
optimization imperative for either RAM savings or performance.
> 
> My question this time is this: is re-ordering globals at the LLVM level
both possible
Isn’t something a linker could/should do?
> [without massive rewriting of LLVM] and safe?  I don`t know whether or not
it`s safe because perhaps some languages -- unlike C and C++ -- _explicitly_
allow programmers to make the assumption that consecutively-written globals at
the source-code level map to consecutively-allocated globals at run-time.  If
so, and if any such language is using LLVM as a back-end, then changing that
behavior at the LLVM level with _any_ optimization flag may break programs that
_are_ well-formed according to the rules of their respective source language[s].
Such programming language should not use LLVM global variables if they need to
provide such guarantee, but probably use instead something more like a global
array when lowering to LLVM IR.

— 
Mehdi

>> My question this time is this: is re-ordering globals at the LLVM level
both possible [...]
On 07/25/2016 10:53 PM, Mehdi Amini wrote:
> Isn’t something a linker could/should do?
AFAIK & TTBOMK, a compiler should do it [if allowed by the language] and a
linker should not
mess it up.  I don`t know that a linker is allowed to make assumptions about
code not
traversing labels in its data accesses.  After all, a compiler may have assigned
labels to e.g.
the start of a "struct" instance and to a specific part of that same
struct.  That doesn`t mean
the linker is free to move the middle of the struct somewhere else far from the
start of the
struct.

IOW, a linker is required to handle the code no matter what the source language
was and what
its specification says about implementations being allowed to re-order things
and whether or
not the language allows the programmer to _validly_ assume that when two arrays
of identical
element type are created back-to-back, the second array immediately follows the
first, thus
effectively creating a single array with its element count being the sum of the
two element
counts of the as-written arrays.



On 07/25/2016 10:53 PM, Mehdi Amini wrote:
> Such programming language should not use LLVM global variables if they need
to provide such guarantee,
>  but probably use instead something more like a global array when lowering
to LLVM IR.
Agreed, but I can`t [en]force that.  That would need to be decided by the LLVM
steering
committee or something like that, then documented publicly.

Thanks for your reply.

Regards,

Abe

> On Jul 25, 2016, at 20:53, Mehdi Amini via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
> Isn’t something a linker could/should do?
We have a problem where some globals are lowered to an immediate address in the
DAG. It would be nice if we had some fixed order for the globals before then.
Right now the total allocated size at the end depends on the use order, block by
block, inverse within the block

-Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160726/32ca04ce/attachment.html>