Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

GCC proves an uninitialized variable must be 0 and doesn't warn about it

lkml.org

Post reply on HN
Print view View original

61–67 of 67 posts

Re: GCC proves an uninitialized variable must be 0 and doesn't warn about it

#61

Post by TheAsprngHacker »

DannyBee wrote: post #57
rcdmd wrote: post #9

Explanation here (from 2004): https://gcc.gnu.org/ml/gcc/2004-12/msg00681.html It's not that GCC proves the uninitialized variable must be 0, it's just that CCP sets it to 0 and everything happens to work out in specific cases.

This is not a correct interpretation (I worked on CCP and related optimizations for years :P) It does in fact prove that it is zero, because it is the meet of lattice values (undefined, 0). You can actually solve this particular case by interpreting phi nodes differently than CCP does. CCP does not generally care about what blocks things occur in - it doesn't have to, all definitions dominate all uses, so it is safe…

I had no idea that the meet/join operations are used in compiler analysis, and I'm curious to find out more. Where can I find out how meet and join are defined on C values, in the context of GCC?

Re: GCC proves an uninitialized variable must be 0 and doesn't warn about it

#62

Post by Taniwha »

tux3 wrote: post #56
Taniwha wrote: post #54

Earlier quoted context omitted.

No, it picks 0 because that's required for the code path where the "if (ret) return ret;" doesn't return, for all the other code paths where it reaches the end of the subroutine ret is undefined so 0 is good for all possible paths to that point

Since I'm on a comment spree today: I think we mostly agree, actually, but note that the compiler doesn't have to pick 0 for the undefined value at all. It only does that because that's the most convenient value to pick. (And for the code path where it's deduced to be 0, well it's not really picking, it doesn't have a choice =] ) A compiler with less optimizations could chose to spill the "ret" variable and not pick…

yes I agree, and it's optimised out a stack location for ret so no stack goop to default to

My point really is that there are two interesting paths here, one where it's undefined and one where it's 0 ... I guess my point is that 0 is more than just 'convenient' because it's required for one of those paths

Re: GCC proves an uninitialized variable must be 0 and doesn't warn about it

#63

Post by tux3 »

Taniwha wrote: post #62
tux3 wrote: post #56

Earlier quoted context omitted.

Since I'm on a comment spree today: I think we mostly agree, actually, but note that the compiler doesn't have to pick 0 for the undefined value at all. It only does that because that's the most convenient value to pick. (And for the code path where it's deduced to be 0, well it's not really picking, it doesn't have a choice =] ) A compiler with less optimizations could chose to spill the "ret" variable and not pick…

yes I agree, and it's optimised out a stack location for ret so no stack goop to default to My point really is that there are two interesting paths here, one where it's undefined and one where it's 0 ... I guess my point is that 0 is more than just 'convenient' because it's required for one of those paths

Fair enough, I can see your point =]

Re: GCC proves an uninitialized variable must be 0 and doesn't warn about it

#64

Post by DannyBee »

TheAsprngHacker wrote: post #61
DannyBee wrote: post #57

Earlier quoted context omitted.

This is not a correct interpretation (I worked on CCP and related optimizations for years :P) It does in fact prove that it is zero, because it is the meet of lattice values (undefined, 0). You can actually solve this particular case by interpreting phi nodes differently than CCP does. CCP does not generally care about what blocks things occur in - it doesn't have to, all definitions dominate all uses, so it is safe…

I had no idea that the meet/join operations are used in compiler analysis, and I'm curious to find out more. Where can I find out how meet and join are defined on C values, in the context of GCC?

Compiler dataflow, is at its core, lattice operations. If you read papers from the 70's, you will find it's very direct about it.

For this specific optimization, you want https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-ssa-c...

Re: GCC proves an uninitialized variable must be 0 and doesn't warn about it

#65

Post by chriswarbo »

dope99 wrote: post #60
DannyBee wrote: post #57

Earlier quoted context omitted.

This is not a correct interpretation (I worked on CCP and related optimizations for years :P) It does in fact prove that it is zero, because it is the meet of lattice values (undefined, 0). You can actually solve this particular case by interpreting phi nodes differently than CCP does. CCP does not generally care about what blocks things occur in - it doesn't have to, all definitions dominate all uses, so it is safe…

Just curious. I’m learning about compilers and would be interested in which compilers most make the trade-off in favor of optimal code generation over compilation speed.

I'm not sure about C, but I know of a few for other languages.

Some compilers perform whole program optimisation, rather than separate compilation of components/modules. This takes longer, but can find some extra optimisations (e.g. if a module provides some functionality, but it's not used in the resulting program, it can be deleted as dead code). MLton does this for StandardML ( http://mlton.org ) and Stalin does this for Scheme ( https://en.wikipedia.org/wiki/Stalin_(Scheme_implementation) )

At the very extreme end is the idea of superoptimisation ( https://en.wikipedia.org/wiki/Superoptimization ). Rather than translating the given code in some way, like a compiler, a superoptimiser treats the given code like a specification or test suite. It performs a brute-force search through the space of all possible programs, looking for any that match the specification. This can find truly optimal code, but it's ridiculously slow. So far its only real-world uses are to find small "peephole" (find/replace) optimisations that can be added to real compilers like LLVM.

There's a related idea called supercompilation (which is often confused or conflated with superoptimisation) https://stackoverflow.com/questions/9067545/what-is-supercom...

A supercompiler can be thought of as running the given code at compile-time. If we know the values of all the functions and variables in a given piece of code, we can just run it to find out what the answer is. Interestingly, we can also "run" code involving values we don't know: we just pass those values around as opaque black-boxes. This is really useful for collapsing layers of indirection, resolving dynamically dispatched targets, baking-in configurable parameters, etc. The downside is that it can lead to bloated executables. Roughly speaking, supercompilation replaces a few long paths containing many conditionals, with many short paths containing fewer conditionals. It also specialises general-purpose functions into many single-use functions which have particular arguments baked-in.

Re: GCC proves an uninitialized variable must be 0 and doesn't warn about it

#66

Post by zzo38computer »

tux3 wrote: post #45
kazinator wrote: post #43

Earlier quoted context omitted.

I don't follow. If the branch on the inode link count is taken, then the external function shmem_reserve_inode is called; ret becomes its return value then. The only way the tail of the function runs with ret == 0 is if that external function happens to return zero. What I don't somehow see is the advantage of, or requirement for, preparing a zero value in ret that didn't come from shmem_reserve_inode, for a branch o…

Oh, I see. It's really a behavior of x86 that's causing the confusion then. The gist of it is that ret is not eax. Let me explain. When shmem_reserve_inode is called, under the x86 C ABIs (all of them!), it will place its return value in eax. So after the call, at this precise moment, "ret" is "eax", and we don't know it's value. Then we do "if (ret) return ret", after this line "ret" is still "eax", and this time we…

I agree; that does look indeed a good reason to set it to zero. Once the end of the function code is reached, ret is either zero or undefined, so there is no need to keep track of the value of ret; just assume that it is zero.

Now I can see how x86 C ABIs is working; thank you for explaining because I did not know much about that before, but now I know, and indeed it is making sense. (On a different instruction set, something else might make sense; I don't really know.)

Post reply on HN