summary refs log tree commit diff
AgeCommit message (Collapse)Author
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.
2017-05-16change the computation of spill costs for phisQuentin Carbonneaux
I now take the view that a phi is "used" at the end of all the predecessors. (Think that copies are made to phis at the end of all predecessors.)
2017-05-16do not account for interferences in phi classesQuentin Carbonneaux
Before this commit, I tried to make sure that two interfering temporaries never ended up in the same phi class. This was to make sure that their register hints were not counterproductively stepping on each other's toes. The idea is fine, but: * the implementation is clumsy because it mixes the orthogonal concepts of (i) interference and (ii) phi classes; * the hinting process in the register allocator is hard to understand because the disjoint-set data structure used for phi classes is cut in arbitrary places. After this commit, the phi classes *really* are phi classes represented with a proper disjoint-set data structure.
2017-04-26Small corrections in documentationQuentin Rameau
2017-04-18documentation updateQuentin Carbonneaux
2017-04-16minor changes for env parameterQuentin Carbonneaux
Since the environment can only be of type `l`, do not require to write it down. I also tightened the type information of the `pare` and `arge` instructions.
2017-04-14remove html converterQuentin Carbonneaux
2017-04-11unscrew freebsd testsQuentin Carbonneaux
2017-04-11simplify amd64 aggregates classificationQuentin Carbonneaux
2017-04-10bump the size of the instruction bufferQuentin Carbonneaux
Ori needs this. It should not cost much more memory at runtime, only a minimal amount of address space.
2017-04-10simplify slot logic in alias analysisQuentin Carbonneaux
The previous code was buggy. It would put a stack pointer on the heap when handling "add $foo, 42". The new code is more straightforward and hopefully more correct. Only temporaries with a "stack" alias class will have a slot pointer.
2017-04-09always disable pie in testsQuentin Carbonneaux
2017-04-08misc fixes for osxQuentin Carbonneaux
With the default toolchain, it looks like we have to make sure all symbols are loaded using rip-relative addressing.