Forum Menu




 


Log in Problems?
New User? Sign Up!
AVR Freaks Forum Index

Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Author Message
wek
PostPosted: Jun 09, 2010 - 08:18 PM
Raving lunatic


Joined: Dec 16, 2005
Posts: 3217
Location: Bratislava, Slovakia

Programs contain sequences of statements, and a naive compiler would execute them exactly in the order as they are written. But an optimizing compiler is free to reorder the statements - or even parts of them - if the resulting "net effect" is the same. The "measure" of the "net effect" is what the standard calls "side effects", and is accomplished exclusively through accesses (reads and writes) to variables tagged as volatile. So, as long as all volatile reads and writes are to the same addresses and in the same order (and writes write the same values), the program is correct, regardless of other operations in it. (One important point to note here is, that time duration between consecutive volatile accesses is not considered at all.)

Unfortunately, there are also operations which are not covered by volatile accesses. An example of this in avr-gcc/avr-libc are the cli()/sei() macros defined in <avr/interrupt.h>, which convert directly to the respective assembler mnemonics through the __asm__() statement. These don't constitute a variable access at all, not even volatile, so the compiler is free to move them around. Although there is a "volatile" qualifier which can be attached to the __asm__() statement, its effect on (re)ordering is not clear from the documentation (and is more likely only to prevent complete removal by the optimiser), as it (among other) states:
Note that even a volatile asm instruction can be moved relative to other code, including across jump instructions. [...] Similarly, you can't expect a sequence of volatile asm instructions to remain perfectly consecutive.

There is another mechanism which can be used to achieve something similar: memory barriers. This is accomplished through adding a special "memory" clobber to the assembler statement, and ensures that all variables are flushed from registers to memory before the statement, and then re-read after the statement. The purpose of memory barriers is slightly different than to enforce code ordering: it is supposed to ensure that there are no variables "cached" in registers, so that it is safe to change the content of registers e.g. when switching context in a multitasking OS (on "big" processors with out-of-order execution they also imply usage of special instructions which force the processor into "in-order" state (this is not the case of AVRs)).

However, memory barrier works well in ensuring that all volatile accesses before and after the barrier occur in the given order with respect to the barrier. However, it does not ensure the compiler moving non-volatile-related statements across the barrier. Peter Dannegger provided a nice example of this effect:
Code:
#define cli() __asm volatile( "cli" ::: "memory" )
#define sei() __asm volatile( "sei" ::: "memory" )

unsigned int ivar;

void test2( unsigned int val )
{
  val = 65535U / val;

  cli();

  ivar = val;

  sei();
}
compiles with optimisations switched on (-Os) to
Code:
00000112 <test2>:
 112:   bc 01          movw   r22, r24
 114:   f8 94          cli
 116:   8f ef          ldi   r24, 0xFF   ; 255
 118:   9f ef          ldi   r25, 0xFF   ; 255
 11a:   0e 94 96 00    call   0x12c   ; 0x12c <__udivmodhi4>
 11e:   70 93 01 02    sts   0x0201, r23
 122:   60 93 00 02    sts   0x0200, r22
 126:   78 94          sei
 128:   08 95          ret
where the potentially slow multiplication is moved across cli(), resulting in interrupts to be disabled longer than intended. Note, that the volatile access occurs in order with respect to cli()/sei(); so the "net effect" required by the standard is achieved as intended, it is "only" the timing which is off. However, for most of embedded applications, timing is an important, sometimes critical factor.

Unfortunately, at the moment, in avr-gcc (nor in the C standard), there is no mechanism to enforce complete match of written and executed code ordering - except maybe of switching the optimization completely off (-O0), or writing all the critical code in assembly.

To sum it up:
  • memory barriers ensure proper ordering of volatile accesses
  • memory barriers don't ensure statements with no volatile accesses to be reordered across the barrier



[This article was written as a supporting documentation for related items in avr-libc - the sei()/cli() macros in <avr/interrupt.h>, the ATOMIC_BLOCK mechanism in <utils/atomic.h> and the newly being introduced _MemoryBarrier() in <avr/cpufunc.h>. It also drew from http://www.avrfreaks.net/index.php?name ... ighlight=.

Comments please. Thanks.

Jan Waclawek

[edit] fixed the last link


Last edited by wek on Jun 09, 2010 - 09:54 PM; edited 1 time in total
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
theusch
PostPosted: Jun 09, 2010 - 08:34 PM
10k+ Postman


Joined: Feb 19, 2001
Posts: 28927
Location: Wisconsin USA

Quote:

The "measure" of the "net effect" is what the standard calls "side effects", and is accomplished exclusively through accesses (reads and writes) to variables tagged as volatile.

I cannot agree with this, especially the "exclusively" part. The optimization situations that you allude to existed long before microcontrollers and "volatile". You start with basic blocks first, mix well with a portion of sequence points, and add a dash of register lifetime. Volatile is like the sprinkles on the top of the cupcake icing. (generalizations based on past live(s) doing compilers and the like)

However, I can certainly see your point as you expand on the particular situation(s) being addressed.
 
 View user's profile Send private message  
Reply with quote Back to top
Bingo600
PostPosted: Jun 09, 2010 - 09:20 PM
Raving lunatic


Joined: Apr 25, 2004
Posts: 3930
Location: Denmark

@Jan

Tell the poor compiler that you insist on using val "NOW ....."

Code:

#define cli() __asm volatile( "cli" ::: "memory" )
#define sei() __asm volatile( "sei" ::: "memory" )


unsigned int ivar;

void test2( unsigned int val )
{

  val = 65535U / val;

  asm volatile ("" : : "b"(val): "memory");


  cli();

  ivar = val;

  sei();
}


Code:

test2:
/* prologue: function */
/* frame size = 0 */
   movw r22,r24
   ldi r24,lo8(-1)
   ldi r25,hi8(-1)
   rcall __udivmodhi4
   movw r30,r22
/* #APP */
 ;  23 "testw.c" 1
   cli
 ;  0 "" 2
/* #NOAPP */
   sts (ivar)+1,r23
   sts ivar,r22
/* #APP */
 ;  27 "testw.c" 1
   sei
 ;  0 "" 2
/* epilogue start */
/* #NOAPP */
   ret


Some hints here

http://blog.regehr.org/archives/28

http://www.cs.utah.edu/~regehr/papers/e ... eprint.pdf

And i think Dean or Danni also mentioned this trick.


Btw: I'm not 100% sure about the "b" in
Code:
: "b"(val):


I used b to get it to shut up Smile

And you doesnt access the var at all , you just tell the compiler that you want to use/access it.

/Bingo

Ps: If you complain about the
Code:
 movw r30,r22


Then "Put the beast out of it's misery" and go buy an IAR compiler Smile

Wonder where it came from ... Smile
Was it the "b" access ... ?

.
 
 View user's profile Send private message  
Reply with quote Back to top
wek
PostPosted: Jun 09, 2010 - 09:50 PM
Raving lunatic


Joined: Dec 16, 2005
Posts: 3217
Location: Bratislava, Slovakia

Bingo600 wrote:

asm volatile ("" : : "b"(val): "memory");

Well, some form of "volatilisation" should help (btw. "b" is not a particularly good choice in this case, standing for "Base pointer register (r28–r31)", the register allocator might feel pressed in a more convoluted situation and move things around unnecessarily... or not, as it's a pretty unpredictible beast... Smile ). Danni's solution is also a form of "volatilisation", except he did it on the other side of barrier, involving C-ish cast magic, http://www.avrfreaks.net/index.php?name ... 85#672085.

But my point is slightly different: the article is NOT intended to provide a solution, it is intended to WARN about the effect. Once you KNOW this may happen, you will be aware of it when hunting down the subtle bugs it may cause.

Jan
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
Bingo600
PostPosted: Jun 09, 2010 - 09:55 PM
Raving lunatic


Joined: Apr 25, 2004
Posts: 3930
Location: Denmark

@Jan

Well im not an assembler guru , but i take it that you get the hint ...
Tell gcc that you want to use the variable as in the above , but maybe with the right "magic" instead of "b".
Then it will deliver it at that point.

But you are right that it would be optimal if the plain ::: memory , could have done it.
But i do think a volatile would help see below link.

There was a previous issue here
http://www.avrfreaks.net/index.php?name ... mp;t=89378


/Bingo
 
 View user's profile Send private message  
Reply with quote Back to top
Bingo600
PostPosted: Jun 09, 2010 - 10:01 PM
Raving lunatic


Joined: Apr 25, 2004
Posts: 3930
Location: Denmark

Seems like the "r" aka. any register will get rid of the extra code.

Code:
void test2( unsigned int val )
{

  val = 65535U / val;

  asm volatile ("" : : "r"(val): "memory");


  cli();

  ivar = val;

  sei();
}


Code:

test2:
/* prologue: function */
/* frame size = 0 */
   movw r22,r24
   ldi r24,lo8(-1)
   ldi r25,hi8(-1)
   rcall __udivmodhi4
/* #APP */
 ;  23 "testw.c" 1
   cli
 ;  0 "" 2
/* #NOAPP */
   sts (ivar)+1,r23
   sts ivar,r22
/* #APP */
 ;  27 "testw.c" 1
   sei
 ;  0 "" 2
/* epilogue start */
/* #NOAPP */
   ret




Could any of the "C" gurus make a TOUCH(val) macro out of this one : asm volatile ("" : : "r"(val): "memory");

Could come in handy ....

/Bingo
 
 View user's profile Send private message  
Reply with quote Back to top
wek
PostPosted: Jun 09, 2010 - 10:05 PM
Raving lunatic


Joined: Dec 16, 2005
Posts: 3217
Location: Bratislava, Slovakia

theusch wrote:
Quote:

The "measure" of the "net effect" is what the standard calls "side effects", and is accomplished exclusively through accesses (reads and writes) to variables tagged as volatile.

I cannot agree with this, especially the "exclusively" part.

That's just a fancy word... Wink

Lee wrote:
The optimization situations that you allude to existed long before microcontrollers and "volatile". You start with basic blocks first, mix well with a portion of sequence points, and add a dash of register lifetime. Volatile is like the sprinkles on the top of the cupcake icing. (generalizations based on past live(s) doing compilers and the like)

This all comes from C99 5.1.2.3. Sure, I've committed (over)simplification, but I don't think the description of the problem needs to go to further details (which I think the same what you said in the following:)

Lee wrote:
However, I can certainly see your point as you expand on the particular situation(s) being addressed.


You are free to suggest different wording, of course.

Jan
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
Bingo600
PostPosted: Jun 09, 2010 - 10:11 PM
Raving lunatic


Joined: Apr 25, 2004
Posts: 3930
Location: Denmark

wek wrote:

But my point is slightly different: the article is NOT intended to provide a solution, it is intended to WARN about the effect. Once you KNOW this may happen, you will be aware of it when hunting down the subtle bugs it may cause.

Jan


Ahh... I get it (now...)
It was a "warning/info" not a "how to avoid" question ..

Sorry ... But a "TOUCH" macro could come in handy anyways.

Even though one prob still has to check if "the beast" does what "You think/expect you have told it to do" Smile

/Bingo
 
 View user's profile Send private message  
Reply with quote Back to top
ArnoldB
PostPosted: Jun 10, 2010 - 06:54 AM
Raving lunatic


Joined: Nov 29, 2007
Posts: 3219


Do I get it right, you are trying to move an age-old avr-libc discussion to avrfreaks, to build up some pressure on the decision makers there?
 
 View user's profile Send private message  
Reply with quote Back to top
wek
PostPosted: Jun 10, 2010 - 07:48 AM
Raving lunatic


Joined: Dec 16, 2005
Posts: 3217
Location: Bratislava, Slovakia

ArnoldB wrote:
Do I get it right, you are trying to move an age-old avr-libc discussion to avrfreaks, to build up some pressure on the decision makers there?
Well, there are no real decisions made there, as far as substantial issues of gcc are concerned.

I'm just trying to document the status quo.

JW
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
dl8dtl
PostPosted: Jun 10, 2010 - 10:47 AM
Raving lunatic


Joined: Dec 20, 2002
Posts: 7374
Location: Dresden, Germany

I've asked Jan to discuss this here, so his contribution can go into
the avr-libc documentation, as what's currently there might be a
little terse if you never thought about all those details.

_________________
Jörg Wunsch

Please don't send me PMs, use email if you want to approach me personally.
Please read the `General information...' article before.
 
 View user's profile Send private message Send e-mail Visit poster's website 
Reply with quote Back to top
anders_m
PostPosted: Jun 10, 2010 - 01:50 PM
Hangaround


Joined: Dec 18, 2009
Posts: 120


One thing I've though about is a new "reorder_barrier" GCC function attribute. The intended effect would be to prevent the compiler from moving any code across a call to a function with that attribute, ie. from the programmer's point of view basically the same effect as a memory clobber but not quite as expensive.

However, I'm not enough of a language lawyer to judge just how bad an idea this would be.
 
 View user's profile Send private message  
Reply with quote Back to top
theusch
PostPosted: Jun 10, 2010 - 04:10 PM
10k+ Postman


Joined: Feb 19, 2001
Posts: 28927
Location: Wisconsin USA

I haven't dug into the internals, but if the volatile accesses were made a "sequence point"--or the equivalent in the GCC approach--then the code couldn't be moved outside of it's "area". The shortest analogy I can think of is a label in assembler that is the target of a branch/jump/call/... . One must be careful on placing code before/after this destination. This doesn't affect register contents at the "fall though" so may not be as brutal as the memory clobber mentioned.
 
 View user's profile Send private message  
Reply with quote Back to top
ArnoldB
PostPosted: Jun 10, 2010 - 07:33 PM
Raving lunatic


Joined: Nov 29, 2007
Posts: 3219


And what is wrong with first starting to support the build-ins GCC already has? Or, in case they are already reasonably supported for AVRs, spread the news about them?

In particular I am talking about

http://gcc.gnu.org/onlinedocs/gcc-4.3.5 ... ltins.html

anders_m wrote:
One thing I've though about is a new "reorder_barrier" GCC function attribute.

For those asking for just a memory barrier, let me point you to __sync_synchronize() on the above mentioned page.

I really don't see the point of inventing new syntax, new attributes or new semantic. Get the __sync_*() stuff running and you are in business. No point in letting the not invented here syndrome take over.

And if you don't like the function names, wrap them in convenience macros.

And I hate it when things that are named like an assembler opcode (e.g. cli(), sbi(), or nop()) do even a iota more than the corresponding opcodes.
 
 View user's profile Send private message  
Reply with quote Back to top
wek
PostPosted: Jun 10, 2010 - 09:41 PM
Raving lunatic


Joined: Dec 16, 2005
Posts: 3217
Location: Bratislava, Slovakia

ArnoldB wrote:
Get the __sync_*() stuff running and you are in business.
Good point. Do you know of any timeline of when will this appear in avr-gcc, more precisely, in WinAVR/its sucessor?

JW
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
theusch
PostPosted: Jun 10, 2010 - 10:02 PM
10k+ Postman


Joined: Feb 19, 2001
Posts: 28927
Location: Wisconsin USA

Hmmm--my amateur reading of the C standard says to me that if the sei() and cli() are considered volatile (I'd think they should be as it is the same as modifying the SREG volatile sfr, right?), then the following should never get out of order:

Code:

cli();
frog = dog;
sei();


I use this draft for reference:
http://www.open-std.org/jtc1/sc22/wg14/ ... /n1124.pdf

Searching for sequence point, especially as related to volatile, I find:
Quote:
5.1.2.3 Program execution

The semantic descriptions in this International Standard describe the behavior of an abstract machine in which issues of optimization are irrelevant.

Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression may produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place. (A summary of the sequence points is given in annex C.)

As the cli() is an access of a volatile object (at least I'd think that) things look pretty clear as "frog = dog;" is an "expression statement" and Appendix C lists
Quote:
the expression in an expression
statement (6.8.3);
lists 6.8.3 as a sequence point, and 6.8.3 is the expression statement.
 
 View user's profile Send private message  
Reply with quote Back to top
ArnoldB
PostPosted: Jun 10, 2010 - 10:04 PM
Raving lunatic


Joined: Nov 29, 2007
Posts: 3219


The __sync_*() buildins appeared in the GCC around v4.1.

I pointed to 4.3.5 documentation, because that is a current GCC version for Linux avr-gcc, and WinAvr is for sure not much different.

So the buildins are in GCC for some time now. I don't know if they have been implemented for the AVR target. If they have, why not use them? If they haven't avr-libc could implement those that make sense under the corresponding __sync_*_n names.
 
 View user's profile Send private message  
Reply with quote Back to top
ArnoldB
PostPosted: Jun 10, 2010 - 10:27 PM
Raving lunatic


Joined: Nov 29, 2007
Posts: 3219


I just ran
Code:

int a;

void f() {
   a = 1;
   __sync_synchronize();
   a = 2;
}

void g() {
   a = 1;
   a = 2;
}
Through a 4.3.3 avr-gcc with -Os optimization and no other options.
Code:

   .file   "a.c"
__SREG__ = 0x3f
__SP_H__ = 0x3e
__SP_L__ = 0x3d
__tmp_reg__ = 0
__zero_reg__ = 1
   .global __do_copy_data
   .global __do_clear_bss
   .text
.global   g
   .type   g, @function
g:
/* prologue: frame size=0 */
/* prologue end (size=0) */
   ldi r24,lo8(2)
   ldi r25,hi8(2)
   sts (a)+1,r25
   sts a,r24
/* epilogue: frame size=0 */
   ret
/* epilogue end (size=1) */
/* function g size 7 (6) */
   .size   g, .-g
.global   f
   .type   f, @function
f:
/* prologue: frame size=0 */
/* prologue end (size=0) */
   ldi r24,lo8(1)
   ldi r25,hi8(1)
   sts (a)+1,r25
   sts a,r24
   ldi r24,lo8(2)
   ldi r25,hi8(2)
   sts (a)+1,r25
   sts a,r24
/* epilogue: frame size=0 */
   ret
/* epilogue end (size=1) */
/* function f size 15 (14) */
   .size   f, .-f
   .comm a,2,1
/* File "a.c": code   22 = 0x0016 (  20), prologues   0, epilogues   2 */
Looks like __sync_synchronize(); is implemented.
 
 View user's profile Send private message  
Reply with quote Back to top
wek
PostPosted: Jun 10, 2010 - 10:45 PM
Raving lunatic


Joined: Dec 16, 2005
Posts: 3217
Location: Bratislava, Slovakia

Sounds like a good news.
Is that avr-gcc which comes with WinAVR20100110?
Could you please try it also on the example above (I am not at a computer with avr-gcc)?
Are the other __sync_xxx() function also implemented? If yes, how do they achieve atomicity - through cli()/sei()?

Thanks,

JW
 
 View user's profile Send private message Visit poster's website 
Reply with quote Back to top
ArnoldB
PostPosted: Jun 10, 2010 - 11:37 PM
Raving lunatic


Joined: Nov 29, 2007
Posts: 3219


wek wrote:
Sounds like a good news.
Is that avr-gcc which comes with WinAVR20100110?
Could you please try it also on the example above (I am not at a computer with avr-gcc)?
Are the other __sync_xxx() function also implemented? If yes, how do they achieve atomicity - through cli()/sei()?
That is an avr-gcc build with the Bingo scripts on Linux.

Regarding the original example, it doesn't work. I think the reason is the same as for the version without sync, the compiler just doesn't consider cli or sei to be memory operands, so it doesn't care.
Code:

test2:
/* prologue: frame size=0 */
/* prologue end (size=0) */
        mov r22,r24
        mov r23,r25
/* #APP */
        cli
/* #NOAPP */
        ldi r24,lo8(-1)
        ldi r25,hi8(-1)
        rcall __udivmodhi4
        sts (ivar)+1,r23
        sts ivar,r22
/* #APP */
        sei
/* #NOAPP */
/* epilogue: frame size=0 */
        ret
/* epilogue end (size=1) */
/* function test2 size 16 (15) */
        .size   test2, .-test2
        .comm ivar,2,1
/* File "b.c": code   16 = 0x0010 (  15), prologues   0, epilogues   1 */


Lets see what __sync_add_and_fetch() does
Code:

int a;
void f() {
   a = 1;
   __sync_add_and_fetch(&a, 4);
   a = 2;
}

void g() {
   a = 1;
   a += 4;
   a = 2;
}

int main() {
   return 1;
}
Code:

   .file   "c.c"
__SREG__ = 0x3f
__SP_H__ = 0x3e
__SP_L__ = 0x3d
__tmp_reg__ = 0
__zero_reg__ = 1
   .global __do_copy_data
   .global __do_clear_bss
   .text
.global   g
   .type   g, @function
g:
/* prologue: frame size=0 */
/* prologue end (size=0) */
   ldi r24,lo8(2)
   ldi r25,hi8(2)
   sts (a)+1,r25
   sts a,r24
/* epilogue: frame size=0 */
   ret
/* epilogue end (size=1) */
/* function g size 7 (6) */
   .size   g, .-g
.global   main
   .type   main, @function
main:
/* prologue: frame size=0 */
/* prologue end (size=0) */
   ldi r24,lo8(1)
   ldi r25,hi8(1)
/* epilogue: frame size=0 */
   ret
/* epilogue end (size=1) */
/* function main size 3 (2) */
   .size   main, .-main
.global   f
   .type   f, @function
f:
/* prologue: frame size=0 */
/* prologue end (size=0) */
   ldi r24,lo8(1)
   ldi r25,hi8(1)
   sts (a)+1,r25
   sts a,r24
   ldi r22,lo8(4)
   ldi r23,hi8(4)
   ldi r24,lo8(a)
   ldi r25,hi8(a)
   rcall __sync_add_and_fetch_2
   ldi r24,lo8(2)
   ldi r25,hi8(2)
   sts (a)+1,r25
   sts a,r24
/* epilogue: frame size=0 */
   ret
/* epilogue end (size=1) */
/* function f size 18 (17) */
   .size   f, .-f
   .comm a,2,1
/* File "c.c": code   28 = 0x001c (  25), prologues   0, epilogues   3 */

So they aren't implemented in GCC 4.3.3 for the AVR. And the called function is also not in the library:
Code:

c.c:(.text+0x28): undefined reference to `__sync_add_and_fetch_2'

There is some opportunity for avr-libc to provide them. And to convince the GCC programmers to include cli/sei when considering memory operations.
 
 View user's profile Send private message  
Reply with quote Back to top
Display posts from previous:     
Jump to:  
All times are GMT + 1 Hour
Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Powered by PNphpBB2 © 2003-2006 The PNphpBB Group
Credits