svn commit: r327354 - head/sys/vm

[Bruce Evans]

On Fri, 19 Jan 2018, Conrad Meyer wrote:

> On Fri, Jan 19, 2018 at 9:04 AM, Rodney W. Grimes
> <freebsd at pdx.rh.cn85.dnsmgr.net> wrote:
>> BUT I do not believe this bit of "style" has anything to do with
>> readability of code, and has more to do with how code runs on a
>> processor and stack frames.   If you defer the declaration of
>> "int i" in the above code does that compiler emmit code to allocate
>> a new stack frame, or does it just add space to the function stack
>> frame for this?
>>
>> What happens if you do
>>         for (int i = 0; i < pages;) { }
>>
>>         for (int i = 1; i < pages;) { }
>> as 2 seperate loops, do we allocate 2 i's on the stack at
>> function startup, or do we defer and allacte each one
>> only when that basic block runs, or do we allocate 1 i
>> and reuse it, I know that the compiler makes functional
>> code but how is that functionality done?  The current
>> style leaves no doubt about how things are done from
>> that perspective.
>
> Modern (and I'm using that word very loosely here — think GCC did this
> 10+ years ago) optimizing compilers do something called liveness

gcc-1 did this 25 years ago (if not 30 years ago).

> tracking[0] for variables to determine the scope they are used in
> (something like the region between last write and last read).  So in
> that sense, optimizing compilers do not care whether you declare the
> variable at function scope or local scope — they always determine the
> local scope the variable is alive in.  (Other than for shadowing,
> which we strongly discourage and is considered bad style.)

gcc did this more primitively 25 years ago, but it always (except for
alloca(3)) allocated space for all variables in a function on entry
to the function (except for alloca(3)).  -O0 doesn't do much more than
allocate all variables on the stack.  -O moves a few variables to
registers.

Debugging is also easier with all variables on the stack, allocated to
fixed positions with a lifetime extending to the end of the function.
gcc does many minor pessimizations, at least with -O, so that -g mostly
works.  clang does the opposite, so that -O -g mostly doesn't work (it
tends to give "value optimized out" even for args).

Debugging is another reason to declare all variables at the start of
functions.  If you reuse a function-scope loop variable named i, then
you can't see what its value was for previous loops in the function,
but you can at least write "display" and "watch" directives for it
without these breaking by the variable going out of scope before the
end of the function.

> Liveness analysis is part of register allocation[1], which typically
> uses a graph coloring algorithm to determine the minimal number of
> distinct registers needed to hold live values.  If the number of
> registers needed is more than the machine provides, some values must
> be spilled to the stack.  (On modern x86 it doesn't matter too much
> what you spill to the stack, because the top few words of the stack
> region is actually quite fast, but clever compilers targeting other
> platforms may attempt to spill less frequently accessed values.)

Not usually the top.  Variables that can't be kept entirely in registers
are usually allocated at a fixed place in the stack which is not
especially likely to be at the top.  Caching works the same everywhere
on the stack.  Sometimes related variables end up in the same cache line
so that caching works best, but doing this intentionally is much harder
than register allocation.

> I think I recall Clang and other LLVM frontends do something nutty
> when they emit intermediary representation, like using a new register
> for each assignment.  This relies on the register allocater to reduce
> that to something sane for the target machine.

gcc also depends on the register allocator to undo initial intentionally
very stupid allocation.  New (physical) registers should be used whenever
possible to maximize use of CPU resources.

Bruce