6 ms·
Hand-optimizing the TCC code generator
- baruch 5y agoThe generated function also has a subtract zero from rsp which could just be plain eliminated. Though it's probably rarer to have this in general code, it means there are no local variables. Looks like there are still some low hanging fruits in there :-)
- FPGAhacker 5y agoI thought maybe it was there to set or clear flags.
- mmastrac 5y agoIt looks like a generic prologue. Ideally the code generator would detect that no stack frame is required whatsoever and just emit the barebones return. It's possible that the prologue is generated ahead of time and then patched as the codegen determines how many locals it needs. You could do a second pass if you detect no locals (you'd need to as you'll be computing new offsets for relative branches/loads/etc), or potentially generate two versions of each function as you compile and only commit the one that is smaller but those are some pretty big tradeoffs. I don't have any idea how TCC is organized internally but my money would be on a generic prologue getting fixed up after-the-fact. EDIT: I think that it might generate the prolog by rewinding to the beginning of the function here: https://github.com/TinyCC/tinycc/blob/e2e5377e7b68d57def00acda17ffcfca6dce8b84/x86_64-gen.c#L1615 https://github.com/TinyCC/tinycc/blob/e2e5377e7b68d57def00ac... I'm not sure if sub rsp, 0 is faster than just filling w/a NOP but that could always be someone's future experiment.
- lionkor 5y agoA wonderful and fun read! I've been writing my own compiler for my own language, and this may just be the motivation I needed to add optimizations to it! I was always thiking about really deep semantic analysis and optimization based on that, but this seems effective, simple, and like great fun!
- gary_0 5y agoI had a vicarious feeling of satisfaction seeing that low-hanging fruit getting plucked.
- magicalhippo 5y agoSemi-related, besides TCC, are there any other C-ish compilers that are easily ported to a new ISA any of you can recommend? Been playing with FPGA softcores, and while writing a compiler can be fun it kinda detracts from the main project.
- bajsejohannes 5y agoAre you making your own softcores? Do you have a recommendation for getting started with that? I've recently gotten interested in making CPUs from logic gates, but I have no idea how to transfer that knowledge to FPGAs.
- magicalhippo 5y agoI'm fairly fresh to this field, so hopefully someone else can come along and give a better answer. I just picked up an iCE40[1] and Cyclone IV dev board[2] and started hacking Verilog. I know Verilog isn't the best option around, and I'm planning on moving onto something better but for now it was easy to get started, and from what I could see many of those better tools end up generating Verilog so would be nice to be able to debug that. If you know how to think in logic-gate-terms then FPGAs won't be that difficult I suspect. Essentially either you have plain logic gates where the output is purely a function of the inputs, or you have edge-triggered logic thanks to flip-flops. Just think of it as writing code that specifies how to wire up set of logic gates, muliplexers and flip-flops. As a brief example, here's an excerpt from my very first ALU: wire [8:0] res_and; wire [8:0] res_xor; wire [8:0] res_add; assign res_and = (bus_a & bus_b); assign res_xor = (bus_a ^ bus_b); assign res_add = (bus_a + bus_b); always @(posedge clk) case (op_sel) OP_AND: result <= res_and; OP_XOR: result <= res_xor; OP_ADD: result <= res_add; default: result <= 0; endcase Here "bus_a" and "bus_b" are wires (which may come from registers), while "result" is a register. The wires don't hold state, while registers can. The <= means to latch the right side into the left side, in this case on a positive edge of clk. The case statement is just a multiplexer. At least to me, it feels very much like "writing a circuit". [1]: https://www.latticesemi.com/en/Products/DevelopmentBoardsAndKits/iCE40UltraPlusBreakoutBoard https://www.latticesemi.com/en/Products/DevelopmentBoardsAnd... [2]: https://www.aliexpress.com/item/32949281189.html https://www.aliexpress.com/item/32949281189.html
- deleted 5y ago[deleted]
- sourabhsybero 5y agoIf you are working on your own compiler, this may help a lot. Working on TCC is always good experience.
- jokoon 5y agoI'm thinking about using tcc as game scripting language. Not really sure if it's a good idea or if it's practical. I want to believe that it is, but it might quite verbose to use.
- melissalobos 5y agoReally GCC -O1 is usually plenty fast if you are just precompiling things at startup that your main executable would dynamically load. The bigger question is, would you really want to be using a language with manual memory management for writing extensions to a program? Maybe including the boehm gc with it would not be terrible.
- ratboy666 5y agoSure -- the compiler is small enough to include -- and fast enough. Bellard did an experiment where TCC was used to compile the Linux kernel on boot. Remarkable. Yes, the source may be verbose. But, the API exposed would be C, and most systems have a C FFI. Instead of TCC, you may wish to consider Quick JS (Bellard's Javascript interpreter). The reason I use TCC is to validate C code. TCC evaluates arguments left to right, whereas GCC does right to left...
- abbeyj 5y agoIs it always safe to make this change without considering the surrounding code? If you start with this code: testl %ebx, %ebx # Set zero flag if %ebx is zero movl $0, %eax # Set %eax to zero jz somewhere # Jump if %ebx was zero then after optimization you get this: testl %ebx, %ebx # Set zero flag if %ebx is zero xorl %eax, %eax # Set %eax to zero *and set zero flag* jz somewhere # Jump always Maybe this is OK because TCC doesn't (currently) generate any code like this.
- kazinator 5y agoGreat point. Now if the program were divided into basic blocks, then any jump based on flags would necessarily be the last instruction of the current basic block. Suppose that the program has the property that flags are always consumed in the same basic block. Then the control info is enough. So whenever we replace movl $0, eax, by xor, we can just check whether or not we are in a basic block that ends with a jump conditional on the Z flag. If that doesn't hold, we need data flow info. For each instruction, we can know from doing data flow analysis whether there are any live flags: CPU flags whose current values are used down later in the program. E.g. say we have: movl $0, %eax movl $0, %ecx movl abc, %esi clz Here, data flow analysis tells us that the Z flag is dead at the movl instruction, because the only possible execution path reaches a clz, and nothing uses the Z flag before then. Thus we are free to clobber it. Moreover, when we do so, the data flow picture doesn't change. The Z flag is dead at the movl, and is still dead when that is replaced by xorl. The optimization doesn't require a recalculation of the data flow info.