Re: Stack Pointer/Size on GIMPLE?

Re: Stack Pointer/Size on GIMPLE?

[schindew]

Hi Luke,

thank you very much for your answer!

> I don't know anything about GIMPLE, but I can address this issue. It
> sounds like you are proposing to checkpoint (via copying) the entire
> stack eagerly at the time you enter a transaction, in order to avoid
> transactional instrumentation of stack accesses.
That is exactly what I had in mind. May I assume that you are part of
the group working on RochesterSTM?

> This is probably a bad idea, as the overhead of the instrumentation is
> probably much less than the overhead of copying and restoring the
> stack. You're also relying on your ability to detect stack accesses
> statically (in order not to instrument them). If you can do this, then
> you can probably just implement a lightweight lazy checkpoint scheme
> rather than an eager, full copy.
We were not sure about the overhead and do not have any comparisons so  
far, but we thought that there are some cases where it is faster to  
copy the stack. (rarely aborting transactions with frequent accesses  
to stack variables). Do you know any papers comparing the different  
approaches?

Right now,  I am not sure that we are able to detect stack accesses  
statically, but I figured it should be possible inside the GCC. But  
assuming it would be possible to do so, how would a lightweight lazy  
checkpoint scheme look like? Would it be like Intels approach  
mentioned in the paper below?

> I think, based on your first post
> (http://gcc.gnu.org/ml/gcc/2008-06/msg00193.html), that you are
> attempting to interface with TinySTM, which does lazy versioning
> (write-buffering) anyway if I recall correctly, so writes are going to
> be buffered aren't going to be written back on an abort anyway, which
> is what you want.
TinySTM supports write-buffering (called write-back) and undo-log
based versioning (called write-through). The idea of copying the stack
comes from Tanger. This is an LLVM-based compiler environment that
supports code generation for TinySTM. Saving the stack can be switched  
off by specifying a command-line option.
At first sight stack copying seemed a reasonable solution and looked  
straightforward to implement. After experiencing some difficulties  
accessing the necessary data if we want to restrict ourselves to the  
tree representation, maybe we should simply go for the approach of  
instrumenting the stack variables as well.

> If you are thinking about an eager versioning system, then you should
> take a look at how stack access is dealt with in "Code Generation and
> Optimization for Transactional Memory Constructs in an Unmanaged
> Language" (http://portal.acm.org/citation.cfm?id=1251974.1252529), as
> the real issue is trying to "undo" accesses into stack space between
> the setjmp and the longjmp.
We are familiar with the paper, but this approach would  require to go  
to RTL level or maybe even beyond. From my current point of view this  
seemed not tempting.

Regards,
Martin

Re: Stack Pointer/Size on GIMPLE?

[Andrew Haley]

schindew@ira.uka.de wrote:

> my intention is to add a pass at the Gimple (maybe SSA) level. The
> current problem is that I would like to generate code that saves the
> contents of the stack to a different memory location. Is there a way to
> access stack pointer and stack size (and the direction in which the
> stack is growing) on the tree level?
> 
> I already found STACK_SIZE and FRAME_ADDRESS on the RTL level, but would
> like to avoid adding an RTL pass.

The stack doesn't exist yet at Gimple level.  Stack slots are allocated
later.  Much, much later.

> The explanation why I want to save the stack contents is the following:
> Code:
> 
> ... use stack variables
> 
> __tm_atomic { /* begin transaction */
> 
> access shared locations in here
> 
> } /* may rollback */
> 
> In case of a rollback the original context of the thread must be
> restored so that it may execute the transaction again. This will be done
> using setjmp/longjmp. To prevent instrumenting all accesses to stack
> variables inside the transaction with STM runtime calls, the stack
> should be copied back from memory and the previous state of the stack
> variables is restored.
> 
> Any suggestions are helpful, thank you very much.

If this is to be done in the compiler at all, it's going to have to be done
very late.  Also, you'll be violating many of the assumptions the compiler
makes about, for example, the state of registers and volatile variables.

Andrew.

Re: Stack Pointer/Size on GIMPLE?

[Luke Dalessandro]

> Is there a way to 
> access stack pointer and stack size (and the direction in which the 
> stack is growing) on the tree level?
> 
> The explanation why I want to save the stack contents is the following:
> Code:
> 
> ... use stack variables
> 
> __tm_atomic { /* begin transaction */
> 
> access shared locations in here
> 
> } /* may rollback */
> 
> In case of a rollback the original context of the thread must be 
> restored so that it may execute the transaction again. This will be done 
> using setjmp/longjmp. To prevent instrumenting all accesses to stack 
> variables inside the transaction with STM runtime calls, the stack 
> should be copied back from memory and the previous state of the stack 
> variables is restored.
> 
> Any suggestions are helpful, thank you very much.

Hi Martin,

I don't know anything about GIMPLE, but I can address this issue. It sounds 
like you are proposing to checkpoint (via copying) the entire stack eagerly at 
the time you enter a transaction, in order to avoid transactional 
instrumentation of stack accesses.

This is probably a bad idea, as the overhead of the instrumentation is 
probably much less than the overhead of copying and restoring the stack. 
You're also relying on your ability to detect stack accesses statically (in 
order not to instrument them). If you can do this, then you can probably just 
implement a lightweight lazy checkpoint scheme rather than an eager, full copy.

I think, based on your first post 
(http://gcc.gnu.org/ml/gcc/2008-06/msg00193.html), that you are attempting to 
interface with TinySTM, which does lazy versioning (write-buffering) anyway if 
I recall correctly, so writes are going to be buffered aren't going to be 
written back on an abort anyway, which is what you want.

If you are thinking about an eager versioning system, then you should take a 
look at how stack access is dealt with in "Code Generation and Optimization 
for Transactional Memory Constructs in an Unmanaged Language" 
(http://portal.acm.org/citation.cfm?id=1251974.1252529), as the real issue is 
trying to "undo" accesses into stack space between the setjmp and the longjmp.

Hope this helps.

Luke

Stack Pointer/Size on GIMPLE?

[schindew]

Hi all,

my intention is to add a pass at the Gimple (maybe SSA) level. The  
current problem is that I would like to generate code that saves the  
contents of the stack to a different memory location. Is there a way  
to access stack pointer and stack size (and the direction in which the  
stack is growing) on the tree level?

I already found STACK_SIZE and FRAME_ADDRESS on the RTL level, but  
would like to avoid adding an RTL pass.

The explanation why I want to save the stack contents is the following:
Code:

... use stack variables

__tm_atomic { /* begin transaction */

access shared locations in here

} /* may rollback */

In case of a rollback the original context of the thread must be  
restored so that it may execute the transaction again. This will be  
done using setjmp/longjmp. To prevent instrumenting all accesses to  
stack variables inside the transaction with STM runtime calls, the  
stack should be copied back from memory and the previous state of the  
stack variables is restored.

Any suggestions are helpful, thank you very much.

Regards,

Martin