| Age | Commit message (Collapse) | Author |
|---|
|
|
|
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
|
|
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.
|
|
Before, amatch() would prefer matching
"o + b" to "o + s*i" and "b + s*i".
|
|
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.
|
|
|
|
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.
|
|
|
|
|
|
|
|
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.
|
|
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.
|
|
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.
|
|
That was silly... I believe qbe still
managed to work because bitsets are only
used inside a basic block where rcopy()
is not used.
|
|
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.
|
|
|
|
Compiler warned about comparison between signed and unsigned values.
|
|
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
|
|
|
|
|
|
In presence of jump loops, the algorithm would
create cycles in the disjoint-set data structure.
This caused infinite recursion and stack overflows.
|
|
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.
|
|
The stashing of constants in gas.c was also
changed to support 16-bytes constants.
|
|
|
|
It never worked until today.
|
|
|
|
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.
|
|
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.
|
|
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.)
|
|
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.
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
Ori needs this. It should not cost much more memory at runtime,
only a minimal amount of address space.
|
|
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.
|
|
|
|
With the default toolchain, it looks like we have to
make sure all symbols are loaded using rip-relative
addressing.
|
|
Intended usage: c_count `make src` (or similar).
|
|
|
|
|
|
|
|
|
|
The vararg tests had to be changed because
va_list is 32-bit wide on arm. The astute
reader will notice that the way we pass
va_list values is wrong, we should be using
the ':valist' type as defined below instead
of 'l'. But eh, that works for now, because
of the ABI.
type :valist = align 8 { 32 }
|
|
|
|
|
|
The arm64 ABI needs to know precisely what
floating point types are being used, so we
need to store that information.
I also made typ[] a dynamic array.
|
|
This big diff does multiple changes to allow
the addition of new targets to qbe. The
changes are listed below in decreasing order
of impact.
1. Add a new Target structure.
To add support for a given target, one has to
implement all the members of the Target
structure. All the source files where changed
to use this interface where needed.
2. Single out amd64-specific code.
In this commit, the amd64 target T_amd64_sysv
is the only target available, it is implemented
in the amd64/ directory. All the non-static
items in this directory are prefixed with either
amd64_ or amd64_sysv (for items that are
specific to the System V ABI).
3. Centralize Ops information.
There is now a file 'ops.h' that must be used to
store all the available operations together with
their metadata. The various targets will only
select what they need; but it is beneficial that
there is only *one* place to change to add a new
instruction.
One good side effect of this change is that any
operation 'xyz' in the IL now as a corresponding
'Oxyz' in the code.
4. Misc fixes.
One notable change is that instruction selection
now generates generic comparison operations and
the lowering to the target's comparisons is done
in the emitter.
GAS directives for data are the same for many
targets, so data emission was extracted in a
file 'gas.c'.
5. Modularize the Makefile.
The Makefile now has a list of C files that
are target-independent (SRC), and one list
of C files per target. Each target can also
use its own 'all.h' header (for example to
define registers).
|
