Eigen Compiler Suite

because it optimises forward rather than backward

Not sure what that means. But as far as I understand the code in cdemitter, there is no provision to get rid of e.g. line 2, 4 and 6 in the following fragment:

    enter    0
    mov    s4 $0, s4 3
    push    s4 $0
    mov    s4 $1, s4 1
    push    s4 $1
    mov    fun $0, fun @foo
    call    fun $0, 8

The emitter is also able to optimise cases where constant folding

I'm sure it works for many cases, but when the code generator decides to assign constants to physical registers before everything is folded, it's much harder to correct afterwards.

I attached the cod an results of the run when line 541 (in case ND_NUM, r0 = e->Move(Code::Imm(ty,node->val)); // mov %s $0, %s %Ld) is modified to "r0 = Code::Imm(ty,node->val); // mov %s $0, %s %Ld"

Here e.g. a part of the diff of 00005.cod without the code modification:

From my humble point of view, this is not a type problem, but apparently the value of r0 is overwritten several times before it is used, so it's rather a coincidence which value is finally moved to R4.

There was an oversight in the emitter which did not optimise conversions, see attached patch file.

But as far as I understand the code in cdemitter, there is no provision to get rid of e.g. line 2, 4 and 6 in the following fragment:

You are explicitly requesting a move instruction using the Move function.

From my humble point of view, this is not a type problem, but apparently the value of r0 is overwritten several times before it is used, so it's rather a coincidence which value is finally moved to R4.

Make sure that the return statement itself moves into the result register. What do you mean by R4?

Thanks for the patch. In what respect does the patch change the behaviour? I didn't notice a difference.

You are explicitly requesting a move instruction using the Move

Because there was a move instruction in the original code, and there are apparently fails and segfaults if left out; you recommended that I use smart operands instead of peephole optimizer rules; but as we now have found out, the latter is unavoidable.

What do you mean by R4?

Apparently typed before thinking. I meant "passed as an argument to _Exit". The mov operations left out in consequence of the change are obviously necessary to meet the program logic and cannot be left out. So we cannot simply assign r0 = Imm(), but there should be a logic to find out wheter a mov is required or not; the peephole optimizer is much easier to implement than such a logic.

In the attached patch file I basically removed unnecessary moves but made sure that the return statement moves into the result register. I have only tested it for test case 00005 but as expected, none of your optimisier rules were triggered.

Please keep in mind that conditional evaluations of two expressions might not end up in the same register. For this you have to fix the register of the first expression and then move the result of the second expression into that register before unfixing it, otherwise either the emitter or the back-end might use different registers for both results. See Emitter2::Minimize for an example.

I have only tested it for test case 00005 but as expected, none of your optimisier rules were triggered.

How did you test it? I repeated the same test with line 541 "Move" removed (i.e. r0 = Code::Imm(ty,node->val);) and the testcase still failed. If I leave the Move, everything works as expected. Also the number of MOV-PUSH detected by the optimizer is alway the same (with/without patch, with/without line 541 "Move"). But that's no issue for me, so you don't have to spend time with that.

conditional evaluations of two expressions might not end up in the same register.

But I assume it is well represented by the r0 variable; that's all I need; I don't care which actual IR register the result is in; the generator is fully agnostic towards registers. Actually I don't exactly understand what you mean. What is a "conditional evaluations of two expressions", and why should they "end up in the same register"? Is this an issue connected with SmartOps or the later stages?

The test case fails because the return statement and the actual call to _Exit do not use the same virtual register.

Virtual registers are assigned to physical ones as needed, so there is no direct mapping. Even if you always use the same virtual register, it might end up in a different physical register, see this example.

A conditional expression like x ? y : z has to evaluate either y or z. If you just put the result of both into the same register you might end up with a different mapping as shown above. The fix and unfix instruction pair allows to fix the physical mapping for exactly this purpose and thus acts as a Φ function.

Another potential problem are registers currently in use before a function call which must to be spilled onto the stack because their contents is invalidated after returning. You can instruct the emitter to automatically save and restore a register using the SaveRegister and RestoreRegister function pair. They must be called whenever you have to evaluate two or more expressions at the same time like in binary operations or assignments. Just save the result of the first evaluation before evaluating the second one and restore it afterwards. Every time before you push the arguments for a function call you can then use a variable of type RestoreRegisterState which automatically takes care of actually restoring the values of all saved registers at the end of its lifetime. See the Oberon emitter for examples.

This is all interesting, but we're talking about an issue which only occurs if I leave out the Move operation associated with the integer literal; the literal is thus associated with a SmartOp which is remains an Imm during the whole code and is never assigned a register at all. At least that's what the diff image above shows. The red parts are the ones removed by the change, yellow the ones added. The "return 0;" which is the only correct outcome is no longer reflected in the code at all. This all just demonstrates that one cannot simply replace Move by assigning Imm to a SmartOp. That's the kind of issue we always meet in the context of optimizations. Anyway, I leave the Move where it is and continue with the peephole optimizer to be on the safe side.

This is why the missing move into the result register in the return statement is essential. If you only assign the immediate value to your global variable rather than actually generating code in the return statement, it should be pretty clear that the variable will always hold the value of the last traversed return statement as in this code sequence:

if(x)
    return 0;
else
    return 1;

But even if you leave the move operation associated with the integer literal, you are assigning the value to two potentially different virtual or phyiscal registers because of the issue raised above. The mapping of the result register however stays the same. Also make sure to actually pass the value of that register to the _Exit function.

Did you apply the codegen patch from above and compare the results?

The mapping of the result register however stays the same.

Which would be a good reason to use $res for intermediate results as well (remember our discussion, from which I finally switched to $R0 for inermediate results).

Did you apply the codegen patch from above and compare the results?

Yes, as reported above (https://software.openbrace.org/projects/ecs/activity?from=2024-06-18).

Here is what I got for test case 00005 using the codegen patch. Seems to be pretty OK and your optimiser had nothing to do.

I assume you compiled with your ECS compiler; I've noticed your compilers makes the much better IR upfront; chibicc is rather a toy in comparison.

Tonight I will do more experiments with the optimizer; I doubt I will reach the elegance of your version, but there are still things I think the peephole optimizer can do.

Attached the current state with and without optimizer.

Here the attachment, after all.

There seems to be a misunderstanding. The code for test case 00005 was generated with your ecc compiler. I just applied the codegen patch from RE: A small C compiler generating Eigen IR.

That's strange; why then I get completely different results? Can you please give me some hints so I can reproduce your results? Which commit of ecc are you using?

I think the commit is named in the patch file.

Ok, now I see the issue; I didn't realize that you sent another patch; I just had convert.diff so far, and all my results and comments referred to that one; sorry for confusion. Now I downloaded your patch and will stash my current version and apply it; stay tuned.

Now I applied your patch and run the nolib testcases. Success rate is 127 of 151. The console output is in results.txt in the attached zip together with the generated cods.

Of the non-successful cases there are 24 which just produce a wrong result, and 19 cause an assert in

cdemitter2.cpp:1001: ECS::Code::Emitter2::SmartOperand::SmartOperand(const ECS::Code::Operand&): Assertion `!HasRegister (operand) || !IsUser (operand.register_)'

I will have a closer lookt at your changes now.

correction: only 4 produce a wrong result: 00076, 00109, 00137, 00138
and one a segfault: bitfields

Both path 315 and orig side by side in codegen.cpp, enabled by define: https://github.com/rochus-keller/EiGen/commit/02ed1869b6451a4eed22e11bd386aad119157a70

I started to refactor codegen.cpp so that there is no longer a module r0 variable, but every smart op is on the stack, as you sugested.

I now refactored codegen.cpp so that there is no longer a global r0 and gen_expr & co return Smart Ops as a result.

Here is the code https://github.com/rochus-keller/EiGen/blob/ecc_smart_emitter_expr/ecc/codegen.cpp

Attached are the results of the nolib testcases (71 ok, rest assertions).

I will continue tonight and check where the assertions come from.

Now all nolib testcases work successfully!

I was able to track down the issues and now understand the concept much better - which would never have been possible without your help, so thank you very much again!

One of my misconceptions was to understand the emitter API just as a code representation of the IR; but actually it's yet another IR on a higher level.

I attached the cod and results files of the runs with and without the peephole optimizer.

There are still a few mov operations which have been removed by the peephole optimizer, and I will now look for the reason and check the cod for more optimization possibilities.

All six optimizations in 00030.cod look like this:

but when I change line 693 from

            res = e->Move(Code::Reg(type,Code::RRes)); // mov %s $0, %s $res

            res = Code::Reg(type,Code::RRes); // mov %s $0, %s $res

ECS::Code::Emitter2::SmartOperand::SmartOperand(const ECS::Code::Operand&): Assertion `!HasRegister (operand) || !IsUser (operand.register_)' failed.

The Call function is overloaded and returns the result register if the first argument is a type. You could do something like this:

res = e->Call(getCodeType(ret), f,stack_slots * target_stack_align);

That worked! Now the optimizer has no work left - unbelievable!

cod files attached.