summary refs log tree commit diff
AgeCommit message (Collapse)Author
2019-04-26new large test to evaluate performanceQuentin Carbonneaux
This was generated by csmith and then compiled to qbe il by Michael Forney's C compiler.
2019-04-26update conaddr test to catch early segfaultsQuentin Carbonneaux
2019-04-26Fix config.h dependency when OBJDIR != objMichael Forney
2019-04-26amd64/isel: Error if alloc size doesn't fit in Tmp slot typeMichael Forney
2019-04-26Allow stack allocations larger than SHRT_MAX * 4 bytesMichael Forney
Slots are stored as `int` in Fn, so use the same type in Tmp. Rearrange the fields in Tmp slightly so that sizeof(Tmp) stays the same (at least on 64-bit systems).
2019-04-26restore some code from b4a98cQuentin Carbonneaux
I had forgotten that %rip can only be used as base when there is no index. I also added a test which stresses addressing selection with and without constants.
2019-04-25cleanup amd64 constant addressingQuentin Carbonneaux
We now emit correct code when the user refers to a specific constant address. I also made some comments clearer in the instruction selection pass and got rid of some apparently useless code.
2019-04-24Fix default config.h for arm64Michael Forney
2019-04-17avoid some gcc warningsQuentin Carbonneaux
In this case, the potential truncations flagged by gcc are only affecting debug information.
2019-04-16bump NString and NPredQuentin Carbonneaux
Michael Forney needs this to run his compiler on interesting programs.
2019-04-15handle big constants moves to slotsQuentin Carbonneaux
There is no flavor of mov which can set 8 bytes of memory to a constant not representable as an int32. The solution is simply to emit two movs of 4 bytes each.
2019-04-11properly detect ssa formQuentin Carbonneaux
Previously, we would skip ssa construction when a temporary has a single definition. This is only part of the ssa invariant: we must also check that all uses are dominated by the single definition. The new code does this. In fact, qbe does not store all the dominators for a block, so instead of walking the idom linked list we use a rough heuristic and declare conservatively that B0 dominates B1 when one of the two conditions is true: a. B0 is the start block b. B0 is B1 Some measurements on a big file from Michael Forney show that the code is still as fast as before this patch.
2019-04-08make sure a spill slot is initializedQuentin Carbonneaux
If an instruction does not have a result, the variable `s` is not set. This could lead to a bogus slot assignment.
2019-03-14Rearrange the fields in Ins so the bit-fields get packed togetherMichael Forney
2019-03-13simple heuristic to reuse stack slotsQuentin Carbonneaux
On test/spill1.ssa, the stack frame of the function f() goes from 56 bytes to 40 bytes. That's a reduction of close to 30%. This patch also opens the door to folding operations on spill slots. For example movl $15, %r15d addl -X(%rbp), %r15d movl %r15d, -X(%rbp) should become add $15, -X(%rbp) when %r15d is not used afterwards.
2019-03-12improve range-checking macrosQuentin Carbonneaux
They are now linear and can be safely used with arguments that have side-effects. This patch also introduces an iscall() macro and uses it to fix a missing check for Ovacall in liveness analysis.
2019-03-12emit valid code for mem->mem copiesQuentin Carbonneaux
2019-03-09add a stress test for phi spillingQuentin Carbonneaux
2019-03-09make sure phis are temporaries in regaQuentin Carbonneaux
In fact, after spilling, a phi can be a temporary or a slot. I am now pondering whether this is a good idea or not because it causes annoying mem->mem movs after register allocation.
2019-03-08use a hash table to parse temporariesQuentin Carbonneaux
2019-03-07fix in load elimination (vacall is a call)Michael Forney
2019-03-01skip expensive ssa-building loop when possibleQuentin Carbonneaux
If a temporary is assigned exactly once (most are), there is no need to do any work to put it in ssa form. On an input file of ~35k loc, this makes the processing time go from 2.9 secs to 1.2 secs.
2019-02-28update copyright yearsQuentin Carbonneaux
2019-02-27Let runtime crash on zero div, don't fold it.Andrew Chambers
Remarks from Quentin: It is an important decision to use Bot and not Top as the result of 'x / 0'. By using Bot, we refuse to give a warrant to the compiler that would allow meaningless subsequent decisions. An example follows. Clang, on my computer, will build a program which prints "Ho" when fed the following C: int main() { puts(1/0 ? "Hi" : "Ho"); } On the other hand, a C compiler based on QBE will build a program which crashes, as one would expect. See also https://c9x.me/notes/2014-09-10.html
2019-02-26new copy elimination passQuentin Carbonneaux
The sparse data-flow analysis used for copy elimination before this patch could sometimes diverge. The core reason for this behavior is that the visitphi() function was not monotonic in the following copy-of lattice: top (represented as the temp / | \ itself) x y z ... \ | / bot (represented as R) This monotonicity defect could be fixed by reverting 2f41ff03, but then the pass would end up missing some redundant phis. This patch re-implements the pass from scratch using a different approach. The new algorithm should get rid of all redundant copies. On the other hand, it can run slower than the monotonic sparse data-flow analysis because, in the worst case, an instruction in a phi cluster can be visited as many times as there are phis in the input program. Thanks to Michael Forney for reviewing and testing the new pass.
2019-02-25prefer bigger amd64 addressingQuentin Carbonneaux
Before, amatch() would prefer matching "o + b" to "o + s*i" and "b + s*i".
2019-02-21fix amd64 addressing mode matcherQuentin Carbonneaux
The numberer made some arranging choices when numbering arguments of an instruction, but these decisions were ignored when matching. The fix is to reconcile numbering and matching.
2019-02-21doc: Aggregate types can be nestedMichael Forney
2019-02-21Fix assertion failure if temporary was spilled in all predecessorsMichael Forney
Since ce0ab53ed7, we skip over predecessors that spilled the temporary. However, if all predecessors spilled, then we might not have an entry in `rl`, triggering an assertion failure in the following loop.
2019-02-21amd64: Fix typo in truncd instructionMichael Forney
2019-02-21doc: Include `align` in data BNFMichael Forney
2019-02-21Fix typoMichael Forney
2019-02-18mark phi arguments as escapingQuentin Carbonneaux
Thanks to Michael Forney for spotting this oversight and providing the test case. Note: because esc() leaves ABot unchanged, the assertion "a->type == ABot" on line 122 remains valid.
2019-02-06soften heuristic of 316b57Quentin Carbonneaux
Instead of systematically spilling any temp live in an exit branch but not in the part of the loop already processed, only spill when it is already known to have been spilled.
2019-02-062 bug fixes in regaQuentin Carbonneaux
The worst one was that "part 3" of rega() could break the critical invariant that two interferring temporaries get assigned different registers. This is fixed by being careful when changing the register of a temporary based on predecessor blocks. Thanks to Michael Forney for reporting these bugs and helping with the analysis.
2019-02-05fix a bad bug in regalloc boilerplateQuentin Carbonneaux
That was silly... I believe qbe still managed to work because bitsets are only used inside a basic block where rcopy() is not used.
2019-02-05new spiller heuristic for loopsQuentin Carbonneaux
If a variable is spilled in a loop, the spiller now tries to keep it spilled over the whole loop. Thanks to Michael Forney for sharing a test case exhibiting a pathological reload.
2018-04-26more compiler warnings...Quentin Carbonneaux
2018-04-26Fix compiler warnings.Emil Skoeldberg
Compiler warned about comparison between signed and unsigned values.
2017-10-07fix compiler command in testccEugene Sharygin
This commit adds missing quotation marks around the argument to the function, and changes the value of `-x' option to `c` (lowercase) as per GCC manual [1]. [1]: https://gcc.gnu.org/onlinedocs/gcc-7.2.0/gcc/Overall-Options.html
2017-09-25adjust test.sh for ubuntuQuentin Carbonneaux
2017-09-22mark printf call as variadic in testQuentin Carbonneaux
2017-08-17fix bug in jumps simplificationQuentin Carbonneaux
In presence of jump loops, the algorithm would create cycles in the disjoint-set data structure. This caused infinite recursion and stack overflows.
2017-07-30fix dynamic stack allocs for amd64Quentin Carbonneaux
The arm64 might have the same problem but it is currently unable to handle them even in instruction selection. Thanks to Jean Dao for reporting the bug.
2017-06-06fix fp subtractions on amd64Quentin Carbonneaux
The stashing of constants in gas.c was also changed to support 16-bytes constants.
2017-06-06isreg() does not need to be inlinedQuentin Carbonneaux
2017-06-06fix floating-point divisionQuentin Carbonneaux
It never worked until today.
2017-05-17free the typ vector at the end of parse()Quentin Carbonneaux
2017-05-17intern symbol namesQuentin Carbonneaux
Symbols in the source file are still limited in length because the rest of the code assumes that strings always fit in NString bytes. Regardless, there is already a benefit because comparing/copying symbol names does not require using strcmp()/strcpy() anymore.
2017-05-16new hinting in the register allocatorQuentin Carbonneaux
The previous heuristics were ad hoc and it was hard to understand why they worked at all. This patch can be summarized in three points: 1. When a register is freed (an instruction assigns it), we try to find if a temporary would like to be in it, and if we find one, we move it in the newly freed register. I call this an "eager move". 2. Temporaries now remember in what register they were last allocated; this information is stored in the field Tmp.visit, and prevails on the field Tmp.hint when it is set. (This makes having the same hint for interfering temporaries not so disastrous.) 3. Blocks are now allocated in "onion" order, from the innermost loop to the outermost. This is the change I am the least sure about; it should be evaluated thorougly.