Eigen Compiler Suite

Thanks for the update. There is no optimiser per se but the intermediate code emitter already contains several optimisations like constant folding.

Just added the -lib option and the barebone targets and integrated the lib and mem linker.

the intermediate code emitter already contains several optimisations like constant folding.

chibicc indeed makes no constant folding. I consider implementing a version with the cdemitter, mostly to avoid a text representation between parser and generator. The API seems pretty complex though. What are your plans concerning IR (or lower) optimizations?

What are your plans concerning IR (or lower) optimizations?

There was an independent code optimiser that does nothing at the moment, but optimised code in a more sophisticated way. Other than that there are no further optimisations planned.

The API seems pretty complex though.

Most protected member functions of the Emitter::Context class map directly to the corresponding intermediate code instructions. Most of them provide overloads that return smart operands which take care of automatic register allocation if the result of the operation returns a register. Other operations are utility functions to create sections or turn operands into register or memory operands, or to reuse registers when needed.

In case you're interested, over the weekend I implemented a C++ version of codegen which uses a simplified version of cdemitter.

Emit(Instruction) can be overloaded, which I use to implement a simple peephole optimizer (see https://github.com/rochus-keller/EiGen/blob/acacf099b24304e9e4407eed2765d3a5ff7cd68b/ecc/codegen.cpp#L1344).

I tested with the nolib test cases and all are ok.

Next I will compare the generated cod files and add more rules as needed.

The current implementation uses cdgenerator to generate a textual representation; I'm aware that I could pass Sections to the backend, but I will continue to pass the textual representation for the time being (easier to debug).

Attached two examples.

Instead of adding more rules to your peephole optimiser, I would suggest changing your expression evaluation functions to return smart operands rather than pushing values on the stack. This way you will automatically get decent intermediate code in the first place.

It wasn't clear to me how to use the smart operands, especially not without turning all the existing code upside down.

The following template might give you an idea how to use smart operands:

static Code::Emitter2::SmartOperand gen_expr(Node *node) {
    switch (node->kind) {
    case ND_NUM:
        switch (node->ty->kind) {
        case TY_FLOAT: case TY_DOUBLE: case TY_LDOUBLE:
            return Code::FImm(getCodeType(node->ty),node->fval));
        default:
            return Code::Imm(getCodeType(node->ty),node->val);
        }
    case ND_NEG:
        return e->Negate (gen_expr(node->lhs));

Negating an immediate value operand also yields an immediate value. Otherwise the emitter generates the necessary instruction and returns a register that holds the result for the lifetime of the smart operand. For more information see the intermediate code emitter for Oberon for example.

I rather prefer not to refactor gen_expr as a function since this affects the whole code at once and cannot be done incrementally. But the use of Register R0 is a kind of "invariant", so I could use something like a global "static SmartOperand r0" instead whereever I would use Code::R0; but then I guess I have to call "Convert (const Type&, const Operand&, Hint = RVoid);" on r0 allover to make sure it fits.

What are actually the Hint parameters for which are present at most Emitter members?

But the use of Register R0 is a kind of "invariant", so I could use something like a global "static SmartOperand r0" instead

Please consider that complex expressions might require several registers to compute their value without spilling.

What are actually the Hint parameters for which are present at most Emitter members?

The optional hint parameter names a register that is desired but not guaranteed to store the result. This is useful for reusing registers in complex expressions if it is save to do so, or placing the result directly into the result register while evaluating return statements.

How can I translate an expression like the following

    const Code::Type type = getCodeType(ty);
    e->Move(Code::Reg(type,Code::R0),Code::Mem(type,Code::R0)); // mov %s $0, %s [$0]

to something like:

    const Code::Type type = getCodeType(ty);
   r0 = e->Move(Code::Mem(type,Code::R0)); // should have something like Deref(type, r0)

where r0 is a module "static SmartOperator r0;" variable?

The corresponding function is called MakeMemory.

Same question for this case:

    const Code::Type type = getCodeType(ty);
    // mov %s [%s], %s $0", type, tmp, type );
    e->Move(Code::Mem(type,Code::Register(tmpReg)),Code::Reg(type,Code::R0));

which should translate in something like

    const Code::Type type = getCodeType(ty);
    // mov %s [%s], %s $0", type, tmp, type );
   SmartOperator tmpReg = e->Move(r0);

Assuming tmpReg is an operand like r0:

e->Move (MakeMemory (type, tmpReg), r0);

Ok, thanks.

And for the previous case, which one is correct:

A:

    const Code::Type type = getCodeType(ty);
    r0 = e->Move(e->MakeMemory(type,r0)); // mov %s $0, %s [$0]

or B:

    const Code::Type type = getCodeType(ty);
    r0 = e->MakeMemory(type,r0); // mov %s $0, %s [$0]

?

Neither. All functions that return a smart operand might yield a completely different register so A does not work. The function MakeMemory just creates a memory operand from an operand of pointer type, so B does not work either. Reusing a dedicated register for all results does not scale well and makes the resulting code more complicated because the emitter is not designed to be used that way:

auto result = Code::Reg (type, R0);
e->Move (result, e->MakeMemory (type, r0));
r0 = result;

Compare with this:

return e->MakeMemory (type, gen_addr(node));

r0 doesn't have to be register R0; it's just used to transfer the result of an expression; essentially I replace all instances of Code::R0 to a global SmartOperand called r0. I hope this works; after the migration to SmartOperands, my code no longer uses buy() and sell(), i.e. doesn't care which user register is actually used; hope this will work.

r0 doesn't have to be register R0

In this case use this:

r0 = e->MakeRegister (e->MakeMemory(type,r0));

What is the difference to

r0 = e->Move(e->MakeMemory(type,r0)); // mov %s $0, %s [$0]

?

MakeRegister reuses the register when possible. Move always moves into a different register unless a hint is given.

Ok, thanks.

Now I fully migrated codegen.cpp to use SmartOperands instead of explicit R0 with my own register allocator. Here is the code: https://github.com/rochus-keller/EiGen/blob/ecc_smart_emitter/ecc/codegen.cpp

I tested with the nolib testcases and everything seems to work.

But it still activates the peephole optimizer, so the SmartOps don't seem to find all optimization possibilities.

I attached the generated nolib testcase cod files for a) my yesterdays cdemitter based implementation without optimization (nolib_cdemitter_no_opt.tar.gz), b) my todays smartops based implementation without optimization (nolib_smart_emitter_no_opt.tar.gz) and c) the latter with the peephole optimizer enabled (nolib_smart_emitter_opt.tar.gz).

The effect of the smartops is visible by using different registers and by things like e.g.

(showing the diff of 00024.cod)

As it seems the peephole optimizer has still the same amount of work and doesn't interfere with the effect of the SmartOps.

Most calls of the Move function in your code emitter are unnecessary. Strictly speaking, it is only required for assignments. In all other cases, it forces the result to be moved into a register which generates more code and inhibits all other optimisations as well. Consider placing all results directly into the variable:

r0 = Code::Imm(ty,node->val);

Consider placing all results directly into the variable: r0 = Code::Imm(ty,node->val);

That seems to be pretty fragile. I tried with all instances of immediate values. Most cause at least one failed test or segfault. The ones which seem to work are likely not covered by a test case.

I also tried this with Code::Adr, with essentially the same result.

Please run your tests against the intermediate code interpreter. There might be some issue with unmatched types.

I will try, but I'm not confident, since constant foldig is for very good reasons usually done during compilation, i.e. before code generation. There are also known cases where cdrun fails because of design decisions of chibicc I'm not going to revise. And it is also known that applying a peephole optizer is easier than avoiding all redundancies in the code generator. So I don't expect to get beautiful IR just because of the SmartOps.

If used correctly, the emitter generates decent code because it optimises forward rather than backward, i.e. it tries to omit code rather than patching it afterwards. Your existing peephole optimisations will most likely not be triggered at all. The emitter is also able to optimise cases where constant folding is usually not applied beforehand. Indexing into multidimensional arrays for example oftentimes yields a single operand without generating any code.