null@diku.dk (Niels Ull Jacobsen) (04/09/90)
0Q 7# Hello world! I'm having a slight problem. I need to make an expression of the type: "( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s. The expression is supposed to have the value of the right side of the assignment, and to push this on the stack as well. The expression is to be a part of a function argument, and can therefore not contain any local block declarations. I have the traditional problem of order of evaluation. The above construct will only work, if the lval is evaluated before the right side. Unfortunately, this is NOT guaranteed. I can make a construct, which will work, if the right side is evaluated first, and I can even make a construct, which will work, if I know that the order of evaluation for two assignments is always the same. However, even this is not guaranteed by an optimizing compiler. The construct, which would work if the order was homogenous: "(stack[++sp]=exp, stack[sp -= N] = stack[sp])". What I want to avoid is: "(stack[++sp]=MARK, stack[sp]=exp, stack[sp -= N] == MARK ? stack[sp]=stack[sp+N]:stack[sp])" , where MARK is a value, that exp cannot evaluate to. I also want to avoid introducing "global" temporary variables, as exp can it self contain expressions of this type. I can not just use stack[sp+1],...,stack[sp+N] in exp, as this will do bad things for my garbage collection. Does anyone have a smart solution for this problem? In case you're interested, this is to be a part of the code generated by a (subset of)Scheme to C compiler, that I'm writing. The final compiler will be a part of an automated compiler generation system, using partial evaluation. Niels Ull Jacobsen, Inst. of Datalogy, U of Copenhagen, null@diku.dk (Speaking from the void ..) -- Niels Ull Jacobsen, Inst. of Datalogy, U of Copenhagen. null@diku.dk (Speaking from the void ..)
ckp@grebyn.com (Checkpoint Technologies) (04/10/90)
In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes: >I need to make an expression of the type: > >"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s. > >The expression is supposed to have the value of the right side of the >assignment, and to push this on the stack as well. The expression is to be a >part of a function argument, and can therefore not contain any local block >declarations. As long as that comma is really the comma *operator* and not the function argument separator, then the order of evaluation of your subexpressions *is* guaranteed. The left expression is evaluated first, the comma declares a sequence point (which means that all side effects are completed), and then the right hand side is evaluated, which becomes the result of the whole expression. The order is defined in both K&R C and ANSI C. Now, if your comma really is a function argument separator, then the order of evaluation is not guaranteed, and your concerns are justified. If your two subexpressions are supplying two parameters to a single function call then you're screwed. There's no way to make them evaluate left-to-right in all cases, and in fact it's common to evaluate function arguments right-to-left, because on many machines that's the order in which they are pushed onto the stack as they become function arguments. This seems to be a commonly misunderstood thing. There are a few operators whose order of evaluation *is* guaranteed, and the comma operator is one of them. Others are && and ||, these are always performed left to right with a sequence point in between. There may be others I don't remember right now. Oh, yes, the "conditional" operator ? : is guaranteed left to right (sort of); the condition expression is evaluated first, then a sequence point is declared, then one of the subexpressions is evaluated but not the other.
ckp@grebyn.com (Checkpoint Technologies) (04/10/90)
In article <19539@grebyn.com> ckp@grebyn.UUCP (Checkpoint Technologies) writes: >In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes: >>I need to make an expression of the type: >> >>"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s. >> >>The expression is supposed to have the value of the right side of the >>assignment, and to push this on the stack as well. The expression is to be a >>part of a function argument, and can therefore not contain any local block >>declarations. > > [ then I talk about the comma operator, completely missing the point ] OOPS - I misread the question. Well, what I said about comma is true, even if you weren't asking about it... Well, then, you're using ++sp many times in the same expression it seems, once on the left side ("stack[++sp] = ..." and several times on the right. This is not gonna work. But I do have a suggestion. I presume you're building a stack machine, such that a stack operator takes several stack arguments, pops them, and writes one stack result in their place. Try doing it this way: ( sp += N, stack[sp] = exp) where exp contains several instances of stack[sp-C], where each C is a negative offset to the argument you wish. Now this expression exp contains no side effects and therefore it's order of evaluation is unimportant. The stack 'pop' operation is performed first. The value of this expression will be the value stored into the 'result' stack location, which is what you wanted, and it's why I put the stack pointer modify operation first.
karl@haddock.ima.isc.com (Karl Heuer) (04/10/90)
In article <19539@grebyn.com> ckp@grebyn.UUCP (Checkpoint Technologies) writes: >In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes: >>"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s. > >As long as that comma is really the comma *operator* and not the >function argument separator, then the order of evaluation of your >subexpressions *is* guaranteed.... I think the problem was with the multiple references to `sp' on the left side of the comma. Niels: am I correct in assuming that (stack[++sp] = stack[++sp] + stack[++sp], stack[sp -= 2]) is an example of the generated code? My recommendation is to force your translator to generate code like (++sp, stack[sp] = stack[sp+1] + stack[sp+2]) instead. That's the only way to be sure that the compiler knows what you're talking about. Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint
null@rimfaxe.diku.dk (Niels Ull Jacobsen) (04/11/90)
karl@haddock.ima.isc.com (Karl Heuer) writes: >In article <1990Apr8.185047.7385@diku.dk> null@diku.dk (Niels Ull Jacobsen) writes: >>I need to make an expression of the type: >> >>"( stack[++sp]= exp , stack[sp -= N])", where exp contains N "stack[++sp]"'s. >> >>The expression is supposed to have the value of the right side of the >>assignment, and to push this on the stack as well. The expression is to be a >>part of a function argument, and can therefore not contain any local block >>declarations. >I think the problem was with the multiple references to `sp' on the left side >of the comma. Niels: am I correct in assuming that > (stack[++sp] = stack[++sp] + stack[++sp], stack[sp -= 2]) >is an example of the generated code? >My recommendation is to force your translator to generate code like > (++sp, stack[sp] = stack[sp+1] + stack[sp+2]) >instead. That's the only way to be sure that the compiler knows what you're >talking about. Thank you, but your assumption is wrong. I am not making a stack machine, so the arguments will not be on the stack. The exp could itself contain expressions of this type. I could have an expression like : (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]), (stack[++sp] = make_cons(x,z), stack[sp -= 0])), stack[sp -= 2]) The stack is actually only used to keep track of the cons-cells for the garbage collection. >Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint In article <19539@grebyn.com> ckp@grebyn.UUCP (Checkpoint Technologies) writes: >Well, then, you're using ++sp many times in the same expression it >seems, once on the left side ("stack[++sp] = ..." and several times on >the right. This is not gonna work. But I do have a suggestion. >I presume you're building a stack machine, such that a stack operator >takes several stack arguments, pops them, and writes one stack result >in their place. Try doing it this way: >( sp += N, stack[sp] = exp) >where exp contains several instances of stack[sp-C], > where each C is a negative offset to the argument you wish. Thank you, but that won't work either, see above. Niels Ull Jacobsen, Inst. of Datalogy, U of Copenhagen. null@diku.dk (Speaking from the void ..)
diamond@tkou02.enet.dec.com (diamond@tkovoa) (04/11/90)
In article <1990Apr10.195822.14808@diku.dk> null@rimfaxe.diku.dk (Niels Ull Jacobsen) writes: > (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]), > (stack[++sp] = make_cons(x,z), stack[sp -= 0])), > stack[sp -= 2]) My stack just overflowed. Let's try color coding. > (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]), black brown RRed red orange yellow > (stack[++sp] = make_cons(x,z), stack[sp -= 0])), GGrn green blue violet > stack[sp -= 2]) gray white OK. The red side effect (updating sp) must be completed before the orange comma's sequence point. The green side effect must be completed before the blue sequence point. However, the yellow comma is not an operator and is not a sequence point. Therefore green,red,orange,blue is a legal evaluation order. (And many others.) In fact, RRed and GGrn may be the same element of stack. The brown side effect must be completed before the violet sequence point. However, this may occur before, after, or intermixed with red, green, etc. Gray and white are safe. They leave the correct value in sp, and they fetch the correct element of stack. However, the correct element of stack might not have been the target in assigning to black. You asked for a fix to black, brown, gray, and white. It might be possible. However, red and green cannot be fixed. You have to hack your expression generator. Now I'm going color-blind. -- Norman Diamond, Nihon DEC diamond@tkou02.enet.dec.com This_blank_intentionally_left_underlined________________________________________
ckp@grebyn.com (Checkpoint Technologies) (04/11/90)
In article <1990Apr10.195822.14808@diku.dk> null@rimfaxe.diku.dk (Niels Ull Jacobsen) writes: > > (stack[++sp] = g((stack[++sp] = make_cons(x,y), stack[sp -= 0]), > (stack[++sp] = make_cons(x,z), stack[sp -= 0])), > stack[sp -= 2]) > >The stack is actually only used to keep track of the cons-cells for >the garbage collection. Hmm... Sticky. Something else to note is that a function call declares a sequence point, therefore side effects are completed. I see you're calling g() above, so any (single) sp++ in the function arguments is guaranteed to be done before the function call .. but there's no relation between that and the calculation of the lvalue of the result from the function call, so this may not help. Hopefully your compiler will see that "sp -= 0" is a non-operation and not generate any subtraction. Philosophical question: is this still a side effect? Since this was generated from a preprocessor I assume that 0 may be a non-zero value in some cases, in which case... Unfortunately I don't think I see an answer without temporary variables and separate statements.