Tuesday, September 2, 2008

My failure to implement &&

I spent half of the past weekend implementing support for the logical AND operator for the Lestes compiler. I should say right at the beginning that I still haven't succeeded, but I decided to share the details of my struggle with you, the kind reader.

The state of the current && and || support is that the parser recognizes these constructs and generates semantic structures for them. The problem is that the part of the compiler which is supposed to generate the respective pseudo code is currently a mere assert() saying that these operators are not yet implemented.

The particular problem of implementing these two is their short-circuit evaluation. When you have, for example, A && B, you first need to evaluate A and if it evaluates to true, only then you can start evaluating B. Without this special feature of C/C++, I'd be able to implement && and || in half a minute, using the already existing template for binary operands. With short-circuit evaluation in place, I need to insert a couple of extra pseudo instructions in the right order:

  1. psp:
  2. psp(A):
  3. L = evaluate(A)
  4. nsp(A):
  5. PI_BF(L, msp2) /* skip evaluation of B */
  6. psp(B)
  7. R = evaulate(B)
  8. nsp(B)
  9. DEST = PI_LAND(L, R) /* logical AND */
  10. msp1:
  11. PI_BA(nsp)
  12. msp2:
  13. PI_MOV(L, DEST)
  14. nsp:
In the pseudo code snippet above, psp stands for previous sequence point and nsp stands for next sequence point. You can see that the sequence points figure as destinations for branch instructions PI_BF and PI_BA and that each expression is surrounded by the psp-nsp pair. nsp(A) and psp(B) are essential in that I must place the PI_BF instruction somewhere between the two, enforcing thus the order of evaluation to start with subexpression A. I added two extra sequence points msp1 and msp2 to help me to enforce order on the pseudo instructions in steps 9 through 14.

While I am quite successful in generating code for the end of the sequence, I can't figure out how to place the PI_BF pseudo instruction without generating an infinite loop. My guess is that somewhere in the Lestes code, something enforces the opposite order of evaluation of A and B. That would, of course, made the topological sort algorithm spin forever. I've tried to place the instruction between psp and nsp of the entire expression. That got me rid of the infinit loop, but I didn't get the right order.

I also can't figure out how to express the above 14 steps in the SSA form so that the DEST register is assigned to only once and there exists a single pseudo instruction which can be denoted as the origin of the register value.

Well, I guess I need to keep on trying. Every failure like this teaches me something new from Lestes and maybe it's worth the trouble just because of that.

No comments: