On the redundancy of C99's restrict(blog.frama-c.com)
blog.frama-c.com
On the redundancy of C99's restrict
http://blog.frama-c.com/index.php?post/2012/07/25/On-the-redundancy-of-C99-s-restrict
25 comments
See also Pascal's followup post, "The previous post was written in jest."[1]
"The previous post assumes the reader is familiar with the notion of undefined behavior and how C compilers have started to justify their more aggressive optimizations along the lines of “this program has always been undefined”....
This was not a serious suggestion, but should be understood as an argument in the debate about the exploitation of undefined behavior in compiler optimization.... I was not suggesting to replace the respected restrict keyword with an awkward replacement. All the arguments I put forward were in bad faith."
[1]: http://blog.frama-c.com/index.php?post/2012/07/25/The-previo...
"The previous post assumes the reader is familiar with the notion of undefined behavior and how C compilers have started to justify their more aggressive optimizations along the lines of “this program has always been undefined”....
This was not a serious suggestion, but should be understood as an argument in the debate about the exploitation of undefined behavior in compiler optimization.... I was not suggesting to replace the respected restrict keyword with an awkward replacement. All the arguments I put forward were in bad faith."
[1]: http://blog.frama-c.com/index.php?post/2012/07/25/The-previo...
This technique may work for simple pointers to integers but is very clumsy if you consider real world use cases where you have pointers to arrays of structures. There's no oneliner magic that tell the compiler that they don't alias.
So, no, this hack is not a replacement for "restrict" keyword in C99. If you use C99, use restrict. If you use C89, use __restrict or whatever your compiler provides you with.
So, no, this hack is not a replacement for "restrict" keyword in C99. If you use C99, use restrict. If you use C89, use __restrict or whatever your compiler provides you with.
Having `restrict` in the function declaration allow other tools to know about the aliasing constraint without the need to read and understand the function code. Think of documentation tools, static checkers, code completion functionalities in IDEs...
The proposed replacement doesn't actually have the same semantics as restrict. I believe that Pascal knows this, as he's a smart guy.
Consider memcpy; its arguments are declared restrict. This not only means that the source and destination pointers cannot be the same (which is what Pascal's "replacement" says), but also means that the buffers cannot overlap at all (i.e. the src pointer cannot be anywhere in the range [dst-(length-1), dst+(length-1)]).
restrict also has the virtue of making this contract apparent to your callers, as it's part of the API. People should know that they can't call memcpy with overlapping buffers, and use memmove instead. If the information is instead encoded in a cryptic line in the implementation, then it isn't obvious to a developer who intends to use the function.
Consider memcpy; its arguments are declared restrict. This not only means that the source and destination pointers cannot be the same (which is what Pascal's "replacement" says), but also means that the buffers cannot overlap at all (i.e. the src pointer cannot be anywhere in the range [dst-(length-1), dst+(length-1)]).
restrict also has the virtue of making this contract apparent to your callers, as it's part of the API. People should know that they can't call memcpy with overlapping buffers, and use memmove instead. If the information is instead encoded in a cryptic line in the implementation, then it isn't obvious to a developer who intends to use the function.
I find your explanation about “restrict” being part of the function interface extremely insightful. Just that makes my misguided attempt at humor worth it (for me). The idea was in gioele's comment too but you made me understand it.
I thought subscribers to the blog deserved to see that comment, so I wrote an answer/advertisement:
http://blog.frama-c.com/index.php?post/2012/07/25/The-restri...
http://blog.frama-c.com/index.php?post/2012/07/25/The-restri...
Could someone please explain how this line:
"(* p=* p) & (* q=* q);"
"inform[s] the compiler that f2() will never be called with aliasing arguments."
Thanks
"(* p=* p) & (* q=* q);"
"inform[s] the compiler that f2() will never be called with aliasing arguments."
Thanks
In contrast to &&, & does not introduce a sequence point, which makes the expression illegal (ie it will exhibit undefined behavior) if p and q alias: an object may only be modified once between sequence points.
Undefined behaviour yes, but does that really make it illegal? Sure the compiler is allowed to play some AC/DC at this point or other undefined behaviour, but I am not sure that makes it an assertion per se?
That's true, but in many cases of undefined behavior, compilers take the liberty of interpreting it as an assertion. In this case, for example, it's legal for the compiler to assume that p and q don't alias when it sees this expression, because either: 1) they really don't alias, in which case the assumption and subsequent optimization is correct; or 2) they really do alias, but in that case the behavior is undefined, so the compiler's choice to apply "erroneous" optimizations is not prohibited.
It's a common approach in C compilers for inferring more optimization-relevant semantics than the language constructs explicitly specify.
It's a common approach in C compilers for inferring more optimization-relevant semantics than the language constructs explicitly specify.
How else would you define the legality of a C program? The language specification comes with constraints, and code which violates those will probably fail to compile (eg syntax errors); any other semantic violation (ie when you see 'shall' or 'shall not' outside of a constraint clause) only results in undefined behavior.
See also the C99 rationale:
"Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior."
Undefined behavior only occurs in case of program errors or language extensions, in which case you're not dealing with standard C, but C-with-extensions.
See also the C99 rationale:
"Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior."
Undefined behavior only occurs in case of program errors or language extensions, in which case you're not dealing with standard C, but C-with-extensions.
If p and q are aliased (pointing to the same location), you would assign twice to the same pointer between two consecutive sequence points, which is undefined in C.
[deleted]
Thanks for asking this. I thought it to be a bit smug of OP not to include an explanation. Like everyone here knows the C specs in and out.
Doesn't "undefined behaviour" means that solution might not be portable? Anyway it looks like a mess. I guess the most of C programmers wouldn't have any idea what that first line of function does and why. If one see restricted he just looks on google what does it mean. Looking for meaning of your solution might be troublesome.
> Doesn't "undefined behaviour" means that solution might not be portable?
It is only undefined behavior if you call the function with aliasing arguments, which is exactly what you are committing not to do anyway. It is only similar to writing the function in C99 with restrict and then calling it with aliasing pointers: you get garbage but it is your fault.
> Anyway it looks like a mess.
I actually wrote this blog post in reaction to the ongoing debate about the exploitation of undefined behavior by C compilers for optimization. As Tom Duff noted in other circumstances, “This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.”
It is only undefined behavior if you call the function with aliasing arguments, which is exactly what you are committing not to do anyway. It is only similar to writing the function in C99 with restrict and then calling it with aliasing pointers: you get garbage but it is your fault.
> Anyway it looks like a mess.
I actually wrote this blog post in reaction to the ongoing debate about the exploitation of undefined behavior by C compilers for optimization. As Tom Duff noted in other circumstances, “This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.”
>I actually wrote this blog post in reaction to the ongoing debate about the exploitation of undefined behavior by C compilers for optimization.
So, it looks like they do quite good job. They noticed that there was some feature needed, provided with some workaround. They added it to standard. No workarounds needed anymore. Workaround that uses some compiler features, but in terms of programming language don't make any sense. That's great, makes C better with same, good sanity. In fact, one of best things I like C for. :)
So, it looks like they do quite good job. They noticed that there was some feature needed, provided with some workaround. They added it to standard. No workarounds needed anymore. Workaround that uses some compiler features, but in terms of programming language don't make any sense. That's great, makes C better with same, good sanity. In fact, one of best things I like C for. :)
> ongoing debate about the exploitation of undefined behavior by C compilers for optimization
Can you provide some links to other examples of this?
Can you provide some links to other examples of this?
There was much gnawing of teeth when compilers started to take advantage of the “strict aliasing rule”: http://labs.qt.nokia.com/2011/06/10/type-punning-and-strict-...
Programmers might think that it is okay to use uninitialized variables as a source of additional entropy (xoring with the real source of entropy), but it isn't, because the compiler will treat the uninitialized access as undefined behavior and eliminate code altogether: http://kqueue.org/blog/2012/06/25/more-randomness-or-less/
This 3-part blog post by Chris Lattner has various examples: http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
Programmers might think that it is okay to use uninitialized variables as a source of additional entropy (xoring with the real source of entropy), but it isn't, because the compiler will treat the uninitialized access as undefined behavior and eliminate code altogether: http://kqueue.org/blog/2012/06/25/more-randomness-or-less/
This 3-part blog post by Chris Lattner has various examples: http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
[deleted]
So he wants to replace something informative like restrict by this expression "(* p=* p) & (* q=* q);"?!
Yuck, I would fire the developer with such clever tricks in our code base.
Yuck, I would fire the developer with such clever tricks in our code base.
If only there was a preprocessor in the language that could be used to hide the keyword from older compilers.
It's kind of late to be complaining about a new keyword in a language standard from 1999 in 2012. However, it does reflect an attitude I've seen in a variety of places, that C99 is a corruption of the spirit of C, which was most closely captured in the old ANSI C. Standard C, they called it. To these people, C99 (and its successors) will always be a proposal, a hypothetical, and a foreign idea. Fun to think about and debate, but not really something that really matters.
There's a new keyword in C99, which can be seen as a bad thing. There's also a confusing one-liner which compilers can reduce to a noop and which they can take as the same guarantee as "restrict". One of the most popular compilers sees it as noop but doesn't increase assumptions. Author calls for detection of the one-liner in compilers because he prefers it to the new keyword.
Why doesn't it make sense to me? I'd much rather see restrict than some not googlable magic line. If you're stuck to some old version of a compiler, it's usually (in my experience) because you need some specific architecture support - why not just drop down to asm when you really really need optimised code at that level? Why would you not have C99 support if you're writing for x86_64?
Maybe I'm missing the big idea about specifying pairwise not-aliasing, but can't it be achieved by passing the pointers to another function with restrict attributes instead and ensuring it's inlined?