| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
into next
* no needs to use MARK_CURRENT_DELETED() for multi-jumps
* canonicalize ((x & M) == M) --> ((x & M) != 0) when M is a power-of-2
* simplify AND(x >= 0, x < C) --> (unsigned)x < C
* simplify TRUNC(x) {==,!=} C --> AND(x,M) {==,!=} C
* remove early simplification of casts during evaluation
* but this back as simplificaion of TRUNC(NOT(x)) --> NOT(TRUNC(x))
|
|
Add a small helper to test if a pseudo is a positive (= non-negative)
constant (for a given bitsize).
It's meant to make some conditions more readable.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix and improve the check that protects try_to_simplify_bb()
* fix remove_merging_phisrc() with duplicated CFG edges.
|
|
It's relatively common to have to add an instruction at the end of a BB.
More exactly, at the end but just before the terminator instruction.
What is done for this is:
1) remove the terminator
2) add the new instruction
3) add the terminator back
This is a bit tedious, need to declare a temporary variable for the
terminator and, more generally, it's low-level details.
So, add an helper for doing this: insert_last_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Now that insert_branch() doesn't need to allocate a new instruction,
there is no more reasons to have it defined in linearize.c
So move it to flow.c which is more concerned with CFG changes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
insert_branch()'s first argument must be the BB of the instruction
given in the second argument.
So, remove it from the argument and simply use insn->bb instead.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The SSA conversion works under the assumption that all the memory
operations on a given symbol always refer to the same object.
So, exclude the conversion of variables where:
* memory operations do not always match in size or offset
* there is an implicit integer/float conversion.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* phi-sources can only have a single user (or none)
|
|
Currently, OP_PHISOURCES have a list as member, 'phi_users',
that should link to all phi-nodes using them but:
*) phi-sources are never shared between phi-nodes
*) this list is useless because it's only created during liveness
and not used after.
So, replace the list by a simple pointer to hold the unique phi-node
using it and keep this link updated during all its lifetime.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Acked-by: Linus Torvalds <torvalds@linux-foundation.org>
|
|
* slice: small reorg of OP_SLICE in preparation for some incoming changes
|
|
OP_SLICE's source's type is needed for some simplifications.
For example, in some cases it can be simplified into OP_TRUNC.
So, merge its representation with the one for unops which also
need the source's type.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
OP_SLICE::len is necessarily equal to the result size.
So remove this redundancy.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Commits 34c57a7f ("asm-mem: does it clobber memory?", 2021-02-20) and
d6721b38 ("asm-mem: does it output to memory?", 2021-02-20) both add
a single bit bitfield to the 'struct asm' part of the union contained
within the 'struct instruction'. This causes the 'selfcheck' target
to issue several 'dubious one-bit signed bitfield' errors.
In order to suppress these errors, change the type of the bitfields to
an unsigned type.
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If an asm statement have a memory output operand, it modifies memory.
Since this information is needed during memops simplification,
add this info directly in the corresponding instruction,
avoiding the need to scan the output operands list each time.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
An asm statement can specify that it clobbers memory.
Add this info directly in the corresponding instruction, avoiding
the need to scan the clobber list each time.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix rem_usage() when the pseudo has a use list but is not PSEUDO_REG
* ptrlist: avoid mixing reverse and non-reverse macros
* shrink struct basic_block
|
|
Add the helper has_definition() to check if the pseudo belong to one
of the pseudo types having a definition: PSEUDO_REG & PSEUDO_PHI.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Reorganize the members of struct BB, avoiding padding and making better
use of the union, to shrink its size from 104 to 96 bytes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The calculation of the canonical order is currently somehow
complicated.
Fix this by reordering the definition of the different type of
pseudos so that they are already in canonical order and just
comparing the types to determine the order.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The return type of IR instructions is stored in the field
::type of struct instruction and this struct has no space
to hold the type of the operand(s). This is not a problem
for most instructions because there is an easy way to get
the operands' type. For example, for binops both types
must be the same so they are used interchangeably.
However, for compare instructions both types can be different
and there is no easy way to get the type of the operands.
Currently, this is ignored and creates some errors. It
also blocks simplifications that need this type information.
But compares instructions need only 2 operands, there is
thus one 'slot' left. So, use this slot for the operands' type.
This solves the current errors, allows new simplifications
and has very little impact on existing code. Of course,
this type information needs now to be tracked and adjusted
whenever the operands change or an instruction is changed
into a compare.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* replace nbr_users() & multi_users() by one_use()
|
|
During simplification, we're only interested to know if a pseudo
is used only once or more than once. This can be checked quicker
than getting the exact number of users.
So, replace the last call to nbr_users() and the calls to multi_users()
by a call to one_use() which has a slightly clearer name.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
These days, declaring arrays bigger than 2GB or doing pointer
arithmetic with an offset larger than 2^31 is maybe not usual but
certainly not outrageous.
However, currently Sparse silently truncates 32 bits the offsets
of memory accesses.
So, fix this by using 64-bit offsets for memory accesses.
Also, use a signed type since these offsets can be negative.
Note: I had a really nice (real) example for this but the margin
of this patch is too small for it (and now I've lost it).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Since memory operands are only some kind of reference, the pseudo
in an output operand is not defined by the statement, the reference
is only used.
Fix the liveness processing accordingly.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* remove more complex phi-nodes
|
|
* fix linearization of unreachable switch + label
|
|
as it will be needed before it was defined in simplify.c and
can be useful in other files too.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
All branches must target an existing BB.
Validate that it is the case for BR, CBR & SWITCH
(COMPUTEDGOTO is left aside for the moment).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* consolidate instruction's properties into an opcode table
|
|
Opcodes are defined in linearize.c:enum opcode.
The file opcode.c also contains a table with opcodes properties.
Centralize these definitions into a single file: opcode.def that
will then be reused for enum opcode & the table.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When simplifying memops, it's needed to check if the memops
is a volatile access or not. This is currently done by checking
insn->type->ctype.modifiers & MOD_VOLATILE which is rather long
but also incorrect for bitfields.
Prepare to fix this by adding a flag to struct instruction directly
telling if the access is volatile.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The field 'orig_type' is only used for casts while 'offset' is only
used for memops.
Split this in two separated sub-structures so that we can add an
additional field for memops without increasing the total size.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
OP_SYMADDR take a single operand 'symbol' but this instruction
is very much like other unops and using the same operand's name
allow to avoid some special cases.
So, s/symbol/src/ for OP_SYMADDRs.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* do 'classical' SSA conversion (via the iterated dominance frontier).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* add optimized version of some list operations
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
For liveness analysis, the ptrlists need to be used as sets. IOW,
before adding a new element, it's needed to check if it doesn't
already belong to the list.
This check is currently done, specifically for pseudos, using the
list walking macros FOR_EACH_PTR/END_FOR_EACH_PTR.
Add a new generic ptrlist function: lookup_ptr_list_entry() which
test if a given pointer already belong to the list.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When doing IR simplification, to know if an instruction can be
destructively modified, it's needed to know if the pseudo it defines
is used by a single instruction or not. Currently this is done using
ptr_list_size() which needs to walk the whole list.
This walk is relatively costly when the list is long but knowing
if the list contains more than 1 element can often be answered
more cheaply since an answer can be returned as soon as it's
known that the list contains at least 2 elements.
Add the helpers ptr_list_multiple() and multi_users().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Sometimes we need to know if a list is empty, for example, in
order to determine if a pseudo has some users or not.
Currently, this is done using ptr_list_size(), which always
walks the whole list but the needed answer can be returned as
soon as it's known that the list contains at least one element.
Add the helper ptr_list_empty() and use it for has_users().
This gives a speedup up to 18% on some pathological workloads.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This small helper was used in unssa.c but is useful elsewhere too.
Move it as an inline function to linearize.h and rename it to
'nbr_users()' since it is close to the existing 'has_users()'.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This patch optimize the very simple implementation of the
phi-node renaming at the end of the SSA conversion.
It avoids the need to rescan the whole function to find the phi-nodes
by using a worklist to put the phi-nodes during the renaming
of non-phi nodes instructions.
This optimization avoids O(n^2) behaviour in some pathological cases.
Note: A lot of optimizations can be done for the renaming.
For the moment, things are kept as simplest as possible,
the goal being to have correctness first.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This implement the first phase of classical SSA conversion:
the placement of phi-nodes at the dominance frontier.
The implementation is rather straight-forward:
* for each pseudo used to make an access do:
* reject cases that can't be converted:
- volatile accesses
- symbols externally visible
- complex types that should not be converted
* scan the concerned instructions and BBs
* if there is only 1 store the loads may be directly
converted (if dominated by the store!)
* if all accesses are in a single BB, then no phi-nodes
are needed and the accesses can be rewritten easily
* otherwise we compute the iterated dominance frontier of
the BBs just scanned and insert the phi-nodes there.
* finally, some cleanup is done on dead stores
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This helper is used later during the SSA construction and is,
as its name suggest, used to insert phi-nodes in the
instruction stream.
More exactly, the phi-node will be put at the begining of the
specified BB, just after the others phi-nodes but before
any other instructions, as required for their semantics
(although, it's less important for sparse since each operand
correspond first to a phi-source, so no phi-node directly
depending on themselves in sparse).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Processing in the middle-end are much easier if undefined values
have been clearly identified. Once done, we can then make
choices like:
- give some warnings about uninitialized variables
- always initialize them to zero
- allow arbitraly simplification
- ...
Prepare this by declaring a new type of pseudo: PSEUDO_UNDEF
somewhat similar to PSEUDO_VOID.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Build the CFG's dominance tree and for each BB record:
- the immediate dominator as bb->idom (is null for entry BB).
- the list of immediately dominated BB as bb->doms.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Do a DFS on the CFG and record the (reverse) postorder.
Use this order for the normal BB traversal (ep->bbs).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Now that these instructions are not generated anymore,
we can remove all related code, defines and doc.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Casts to integer used to be done with only 2 instructions:
OP_CAST & OP_SCAST.
Those are not very convenient as they don't reflect the real
operations that need to be done.
This patch specialize these instructions in:
- OP_TRUNC, for casts to a smaller type
- OP_ZEXT, for casts that need a zero extension
- OP_SEXT, for casts that need a sign extension
- Integer-to-integer casts of the same size are considered as
a NOPs and are, in fact, never emitted.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently all casts to pointers are processed alike. This is
simple but rather unconvenient in later phases as this
correspond to different operations that obeys to different
rules and which later need extra checks.
Change this by using a specific instructions (OP_UTPTR) for
[unsigned] integer to pointers.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently all casts to pointers are processed alike.
This is simple but rather unconvenient as it correspond to
different operations that obeys to different rules and
which later need extra checks.
Change this by using a specific instructions (OP_UTPTR) for
unsigned integer to pointers.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, casts from floats to integers are processed like
integers (or any other type) to integers. This is simple but
rather unconvenient as it correspond to different operations
that obeys to different rules and which later need extra checks.
Change this by directly using specific instructions:
- FCVTU for floats to unsigned integers
- FCVTS for floats to signed integers
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, all casts to a floating point type use OP_FPCAST.
This is maybe simple but rather uncovenient as it correspond
to several quite different operations that later need extra
checks.
Change this by directly using different instructions for the
different cases:
- FCVTF for float-float conversions
- UCVTF for unsigned integer to floats
- SCVTF for signed integer to floats
and reject attempts to cast a pointer to a float.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some operations are exactly the same for all unops, including casts.
To make things more readable and decrease the amount of churn, create
a range OP_UNOP - OP_UNOP_END like already done for binops.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently OP_SYMADDR are defined the same as OP_SETVAL.
However, OP_SYMADDRs don't need the field 'struct expression *val'
and OP_SETVALs don't need the field 'pseudo_t symbol' which
suggest that those two should be splitted. In fact, OP_SYMADDR,
having just one pseudo as operand and producing one pseudo, is
simply an unary op like OP_NOT, OP_NEG, ...
Change this by letting OP_SYMADDRs use the field 'src' as
the others unops do.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This give us:
- a clearer name (than alloc_phi())
- more flexibility when we need the instruction and not the pseudo.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add an helper to display labels.
This allow us to:
*) abstract away the details of how to display them
*) gracefully handle abnormal cases of a null label.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Testing the value of a pseudo against zero is relatively
common but it needs to test the type of the pseudo before
testing the value itself.
Add 2 small helpers for this: is_zero() & is_nonzero().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
During the processing, some verification are done and if the
check fails, a warning is normally issued. But some checks are
done at several steps and so the same warning can be give
several time, which is annoying.
Add to instructions a field '.tainted' which will allow to
mark instructions which fail some checks and have already
warned about.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In struct instruction, .target is normally used to hold
the result. Its value is thus produced/defined by instructions.
On the contrary, .cond is used as an input value and is
thus used by instructions.
However, these two fields belong to the same union. This
creates slight complications for code, like liveness analysis
which care about which fields are used and which are defined
by the instructions.
Change this by unionizing .cond with .src, .src1 & friends instead
of with .target.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some of the IR instructions have been defined but are
never generated.
Remove them as they have no purposes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
No instructions have an opcode set to OP_[LS]NOP anymore
so we can now remove all remaining traces of these opcode.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, we have OP_MULS & OP_MULU but unless it's full,
widening multiplication both must give exactly the same
result (the world run on 2's complement CPUs now, right?).
Also, the IR doesn't have widening multiplication but
only instruction where both operands and the result have
the same size.
So, since theer is no reasons to keep 2 instructions,
merge OP_MULS & OP_MULU into a single one: OP_MUL.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
'struct pseudo_ptr_list' was used to store pseudo usage
but this structure is not used since commit e7fb6e092
(Add instruction to pseudo user tracking).
Remove the leftovers.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This is a wrapper around pseudo_user_list_size() which
can directly be used on a pseudo.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add pseudo_user_list_size() instead of having to use
ptr_list_size() with an ugly cast.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
OP_SETVAL is used to create floating-point and string
as well as labels-as-values. This multi-purpose aspect
sometimes make things a bit more complicated.
Change this by using a new instruction for the direct
creation of floating-point literals without needing
to have an intermediate EXPR_FVALUE.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Floating-point arithmetic is quite different from the
arithmetic on integers or the one of real numbers.
In particular, most transformations, simplifications that can
be done on integers are invalid when done on floats.
For example:
- associativity doesn't hold
- distributivity doesn't hold
- comparison is tricky & complex
This is because (among others things):
- limited precision, rounding everywhere
- presence of signed zeroes
- presence of infinities
- presence of NaNs (signaling or quiet)
- presence of numbers without inverse
- several kind of exceptions.
Since they don't follow the same rules as their integer
counterpart, better to give them a specific opcode
instead of having to test the type of the operands at
each manipulation.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Comparision of floating-point values can't be done
like for integral values because of the possibility to have
NaNs which can't be ordered with normal values or even between
themselves.
The real difference appears once there is any "reasoning"
done with the result of the comparison. For example, once NaNs
are taken in account: "!(a < b)" and "(a >= b)" are not the same.
In fact the usual comparison operators must be reinterpreted
as implicitely first testing if any of the operand is a Nan
and return 'false' if it is the case. Thus "a < b" becomes
"!isnan(a) && !isnan(b) && (a < b)".
If we need to negate the comparison we get "!(a < b)" which
naturally becomes "isnan(a) || isnan(b) || (a >= b)".
We thus need two sets of operators for comparison of floats:
one for the "ordered" values (only true if neither operand
is a Nan) and one for the "values" (also true if either
operand is a NaN). A negation of the comparison switch from one
of the set to the other.
So, introduce another set of instructions for the comparison
of floats.
Note: the C standard requires that:
*) "x == x" is false if x is a NaN,
*) "x != x" is true if x is a NaN,
and this is coherent with "x != x" <-> "!(x == x)".
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently the different cases of a switch-statement, or more
exactly the 'struct multijmp' that hold the value of these cases
excepted only value of 'int' type. Trying to use a wider value
results in the value being truncated but any integer value should
be valid.
Fix this by unsigned 'long long' to hold these values.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, OP_PHISOURCEs are given a size but not a type.
For consistency and for sparse-LLVM which need it,
give them a type too.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The linearized code, sparse's IR, have no use of C's complex type
system. Those types are checked in previous phases and the pseudos
doesn't have a type directly attached to them as all the needed
typing info info are conveyed by the instructions.
In particular, PSEUDO_VAL (used for integer and address constants)
are completely typeless.
There is a problem with this when calling a variadic function
with a constant argument as in this case there is no type in the
function prototype (for the variadic part, of course) and there is
no defining instructions holding the type of the argument.
Possible but rejected solutions are:
* give a full type to all pseudos
This is silly as, for example 'int 0' and 'unsigned int 0'
are, really, the same constants.
* give simply a size to all pseudos
This seems to be simple enough but *currently* it negatively
impacts CSE (maybe because of some others deficiencies in
the type system, especially for casts).
* give a type to all function arguments via a new instruction
that would mimic argument passing (OP_ARG or OP_PUSH).
This solution is interesting, especially as it gives a placeholder
for real argument passing at code generation time, but:
0) they can be added, if needed, when some code generation
will be done.
1) it creates a superfluous instruction for every argument
of every function call
2) these instructions are essentially copy instructions in
disguise.
So, since the problem only exist for constants used in variadic
arguments (and currently, it's only a problem for sparse-llvm),
the solution selected is to add to OP_CALLs a list holding the
type of all arguments. More exactly, it reuses the field .fntype
which was used to store the type of the function, and changes
it to a list holding the function type *and* the type of all
effective arguments.
Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some optimizations transform an instruction opcode
into another. For example, it may be needed to know
the opcode corresponding to the negation of a comparison.
This patch make this easy and flexible by adding a table
for the relation between opcodes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This helper is also made unneeded since the introduction of OP_CBR.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
OP_BR instructions exist in two flavours, relatively much
differentiated: conditional & non-conditional. One has an
operand (and thus its usage need to be cared for, must be
handled in liveness analysis, ..) the other has not; one has
two BB target, the other only one.
There is essentially no places in the code where both flavours
are handled the same. Sometimes they both must be handled but
each with their specificities but in most cases only one of
them is concerned and we need to filter out the other one.
In both cases it means that we need to check what kind we're
dealing with.
There is already a problem with this because there is
several ways to test which kind an OP_BR is and they
are not exactly equivalent:
1) testing if insn->cond is NULL
2) testing if one of insn->bb_true or ->bb_false is NULL.
There exist also an helper (is_branch_goto()) which does
the second tests but which is never used.
It appears that the first test should not be used because
in some cases an conditional OP_BR is changed into
a non-conditional one by (amongst others things) setting
it's ->cond to VOID. We should thus always use the seconds
test (which need two compares with NULL).
This could be corrected in several ways (like changing all
the places wheer the first test is used, use the helper
everywhere or never set ->cond to VOID) but the simplest
is to simply split them in two separated instructions:
OP_BR & OP_CBR, especailly given the fact that in most cases
the OP_BR was first selected by a switch (opcode).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
This field was introduced (I think) for OP_SWITCH but is
not needed anymore as OP_SWITCH has its own entry with a field
fOr multijump list.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
test-linearize displays basic block's labels by using
'.L0x' plus the address of the bb struct. This is certainly
convenient as an UID but it has the disadvantage that these
names change at each run and are thus not comparable.
This complicate testing quite a bit.
Let change this by giving a simple sequential number to each bb
and simply display them as: '.L1', '.L2', ...
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
On Tue, Aug 30, 2011 at 10:43 AM, Jeff Garzik <jeff@garzik.org> wrote:
> * if someone knows how to access a function declaration, I can solve the
> varargs problem
Hmm. Right now we do not have access to the function declaration at
linearize time. We've checked that the arguments match, and we've cast
the arguments to the right types (evaluate.c), so the thinking was
that you just use the arguments as-is.
But if llvm needs the declaration of a function, we'd need to squirrel it away.
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Christopher Li <sparse@chrisli.org>
Cc: Jeff Garzik <jgarzik@redhat.com>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[ penberg@kernel.org: Fix validation/context.c breakage. ]
Signed-off-by: Pekka Enberg <penberg@kernel.org>
|
|
It gets the code a bit farther, with the following test case:
int foo(int x)
{
if (x > 0xffff)
x++;
else
x--;
return x;
}
* run with
./sparse-llvm hello.c | llvm-dis
for an IMO more useful disassembly than via 'llc'
* add 'priv' to struct basic_block
* run a first pass through the BB's, creating LLVMBasicBlockRef's and assigning
them to bb->priv
* comment out unssa() call, and implement OP_PHI and OP_PHISOURCE, which LLVM
directly supports.
* remove '%' prefix from PSEUDO_REG names, as it was redundant and made
llvm-dis output ugly
* implement support for conditional and unconditional branches (OP_BR)
* implement OP_COPY. a possibly better implementation would be a single-source
LLVMBuildPhi
[ penberg@kernel.org: minor cleanups ]
Signed-off-by: Pekka Enberg <penberg@kernel.org>
|
|
Signed-off-by: Pekka Enberg <penberg@kernel.org>
|
|
It's unfortunate to use 'true' and 'false' as identifiers in a system
header. It clashes with corresponding macros from <stdbool.h> when
included before <sparse/linearize.h>.
Signed-off-by: Kamil Dudka <kdudka@redhat.com>
Acked-by: Hannes Eder <hannes@hanneseder.net>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
> Do you want to resend your change which revert the context changes?
> Make it base on Josh's git's tree and I will merge your changes in my
> branch.
Below. Or I can give it to you in git if you prefer. I still think we
should redo this in some form so that annotations with different
contexts can work properly, but I don't have time to take care of it
right now.
johannes
>From ca95b62edf1600a2b55ed9ca0515d049807a84fc Mon Sep 17 00:00:00 2001
From: Johannes Berg <johannes@sipsolutions.net>
Date: Tue, 23 Dec 2008 10:53:19 +0100
Subject: [PATCH] Revert context tracking code
|
|
Currently there is no generic way to derive phy
type information from the instruction flow.
Signed-off-by: David Given <dg@cowlark.com>
|
|
My optimisation to avoid recursion into BBs when checking contexts
lead to a failure in a case like this:
static int warn_conditional(void)
{
if (condition)
return 0;
a();
if (condition == 0)
return 1;
r();
return 0;
}
because some blocks are called with different contexts and thus
need to be checked multiple times.
The obvious fix would be to decrease the recursion depth at the
end of the BB check function, but that, while correct, leads to
extremely long sparse runtimes on somewhat complex functions.
Thus, this patch also makes sparse cache which contexts it has
checked a block in and avoid the re-checking in that case.
Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
|
|
This patch enables a very simple form of conditional context tracking,
namely something like
if (spin_trylock(...)) {
[...]
spin_unlock(...);
}
Note that
__ret = spin_trylock(...);
if (__ret) {
[...]
spin_unlock(...);
}
does /not/ work since that would require tracking the variable and doing
extra checks to ensure the variable isn't globally accessible or similar
which could lead to race conditions.
To declare a trylock, one uses:
int spin_trylock(...) __attribute__((conditional_context(spinlock,0,1,0)))
{...}
Note that doing this currently excludes that function itself from context
checking completely.
Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
|
|
The sparse man page promises that it will check this:
Functions with the extended attribute
__attribute__((context(expression,in_context,out_context))
require the context expression (for instance, a lock) to have the
value in_context (a constant nonnegative integer) when called,
and return with the value out_context (a constant nonnegative
integer).
It doesn't keep that promise though, nor can it, especially with
contexts that can be acquired recursively (like RCU in the kernel.)
This patch makes sparse track different contexts, and also follows
up on that promise, but with slightly different semantics:
* the "require the context to have the value" is changed to require
it to have /at least/ the value if 'in_context',
* an exact_context(...) attribute is introduced with the previously
described semantics (to be used for non-recursive contexts),
* the __context__ statement is extended to also include a required
context argument (same at least semantics),
Unfortunately, I wasn't able to keep the same output, so now you'll
see different messages from sparse, especially when trying to unlock
a lock that isn't locked you'll see a message pointing to the unlock
function rather than complaining about the basic block, you can see
that in the test suite changes.
This patch also contains test updates and a lot of new tests for the
new functionality. Except for the changed messages, old functionality
should not be affected.
However, the kernel use of __attribute__((context(...)) is actually
wrong, the kernel often does things like:
static void *dev_mc_seq_start(struct seq_file *seq, loff_t * pos)
__acquires(dev_base_lock)
{
[...]
read_lock(&dev_base_lock);
[...]
}
rather than
static void *dev_mc_seq_start(struct seq_file *seq, loff_t * pos)
__acquires(dev_base_lock)
{
[...]
__acquire__(dev_base_lock);
read_lock(&dev_base_lock);
[...]
}
(and possibly more when read_lock() is annotated appropriately, such
as dropping whatever context read_lock() returns to convert the context
to the dev_base_lock one.)
Currently, sparse doesn't care, but if it's going to check the context
of functions contained within another function then we need to put the
actual __acquire__ together with acquiring the context.
The great benefit of this patch is that you can now document at least
some locking assumptions in a machine-readable way:
before:
/* requires mylock held */
static void myfunc(void)
{...}
after:
static void myfunc(void)
__requires(mylock)
{...}
where, for sparse,
#define __requires(x) __attribute__((context(x,1,1)))
Doing so may result in lots of other functions that need to be annoated
along with it because they also have the same locking requirements, but
ultimately sparse can check a lot of locking assumptions that way.
I have already used this patch and identify a number of kernel bugs by
marking things to require certain locks or RCU-protection and checking
sparse output. To do that, you need a few kernel patches which I'll
send separately.
Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
|
|
Signed-off-by: Josh Triplett <josh@freedesktop.org>
|
|
For inline functions, Sparse inlines the function body at evaluation. It is
very hard to find out the original function call. This change preserves the
original call as an annotation.
Signed-Off-By: Christopher Li <sparse@chrisli.org>
|
|
Signed-off-by: Josh Triplett <josh@freedesktop.org>
|
|
Signed-off-by: Josh Triplett <josh@freedesktop.org>
|
|
The current way of tracking pseudo register user is by
keeping a list of the address of the pseudo_t member.
This address can be in part of the instruction member, the
worse case is in the argument list of the call instruction.
As the comment for address_taken() said, using the container
to get instruction pointer is wrong. It use to work with instruction
that relate to symbol address. But that is not true any more. Even
worse, it is very hard to track the pseudo usage other than symbol
address. The only reason symbol address used to works for call instruction
is because call instruction did not directly use the symbol address.
I bit the bullet and just add the instruction pointer to pair with
the pseudo user pointer. So it will work with the case that the
user instruction is call as well.
Testing:
I compare the linearize result with/without the patch on a few
sparse source file it self. The linearize generate exactly
the same result except the symbol address changes. Which is
predictable different because the pseudo user structure allocate
memory.
Singed-Off-By: Christopher Li <sparse@chrisli.org>
|
|
A pseudo list contains more information. It can
get to the symbol as well as the usage information.
Now it is much easier to answer questions like
"What functions does this function call?".
Signed-Off-By: Christopher Li <sparse@chrisli.org>
|
|
The opcode enum defines the boundary values OP_TERMINATOR and
OP_TERMINATOR_END for terminator instructions; use those in bb_terminated
rather than the specific values they currently equal.
Signed-off-by: Josh Triplett <josh@freedesktop.org>
|
|
sparse currently only tracks one global context for __context__ and
__attribute__((context)).
This adds support for parsing an additional argument to each of these
which gives a context expression. For __attribute__((context)), store
each context attribute as a separate context structure containing the
expression, the entry context, and the exit context, and keep a list of
these structures in the ctype. For __context__, store the context
expression in the context instruction. Modify the various frontends to
adapt to this change, without changing functionality.
This change should not affect parsing of programs which worked with
previous versions of sparse, unless those programs use comma expressions
as arguments to __context__ or __attribute__((context)), which seems
highly dubious and unlikely. sparse with -Wcontext generates identical
output with or without this change on Linux 2.6.18-rc4.
Signed-off-by: Josh Triplett <josh@freedesktop.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
We return a well-defined type (a pointer to the pseudo_t we added), so
don't cast it to "void *" unnecessarily.
Type safety is good.
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
For now, it use a simple method but which introduces a lot more copies
than necessary. Can be fixed later.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@looxix.net>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
This is needed to translate SSA back to normal form.
Maybe we should split this in two distinct ops: The first ones
correspond to the old OP_PHISOURCE (but if the same phisrc feed several
phi-nodes, we need sevarel distinct copy instruction); at this stage
they are the only instruction that can define a pseudo in multiple
places. The other ones being the "normal" copies.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@looxix.net>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
You can mark a function as requiring a lock, or requiring being called
without a lock.
|
|
Rather than tying everything to the beginning basic block
position.
This should be able to pinpoint instruction issues much more
exactly and readably.
|
|
|
|
Otherwise we lose the information what the target
type is (we only have the bit-size of the target).
|
|
This is OP_MUL/OP_DIV/OP_MOD/OP_SHR.
We actually do the constant simplifications still wrong, but
now the information is all there.
|
|
(symbol addresses).
They are pretty different. Symbol addresses have special meaning during
various phases, from symbol simplification to CSE.
|
|
The asm_inputs/outputs "expression list" is not really an
expression list any more: it is a list of "triples", where
the first entry is the identifier name, the second one is
the constraint string, and the third one is the expression.
|
|
This also makes the OP_ASM data structures a bit more structured
in order to contain all the required information.
|
|
Not only does it make sense, but the back-end needs to
know what pseudos got allocated ;)
|
|
the list or not.
|
|
and labels. And comments, for that matter.
This eventually allows us to buffer them up, rather than print
them out directly. Which we'll need to do if we want to fix up
frame offsets etc (for register save areas). And other post-
processing.
Also, for comments, make "show_instruction()" return the string
rather than print it out.
|
|
|
|
We already did this, we just didn't have a visible prototype.
|
|
white-space.
|
|
This allows us to always see which pseudos are nonlocally affected
by the phi source.
We can only do this after the instruction flow is fixed, together
with the OP_DEATHNOTE phase.
|
|
This doesn't actually save the register class information, so
you can't do proper register allocation, but it does all the
input reading and store to outputs.
Still need to teach the liveness analysis about the _usage_ rules.
|
|
a special basic block.
This removes a lot of special cases, since now flow doesn't have any
special BB to worry about. It also gives a clear definition point for
argument pseudos, and thus makes liveness tracking lose a special
case.
|
|
We want to use it in almost any debugging schenario, so why not
just admit that.
|
|
Now that we have full pseudo usage lists, we can also add
deathnotes to pseudos in the instruction stream.
NOTE! We add the deathnote to _before_ the last instruction
that uses that pseudo. That looks a bit strange, but it's
actually what you want: when we traverse the instuctions, we
want to know that the inputs are dead.
|
|
This was originally done so that "struct instruction" would be
smaller, but it has since grown anyway (for the memops), so splitting
OP_SEL into two instructions no longer makes sense, and makes it
harder on CSE.
|
|
This does trivial simplification of casting to the same
typesize. HOWEVER. We split casts up into whether they
cast to a dereferencable pointer type or not, and we don't
simplify pointer casts. This should mean that if we
ever want to do type-based alias analysis, we can still
avoid casted accesses.
(If we do type-based alias analysis, we'll also need to make
a union access do a cast. Which we probably should do anyway).
|
|
This is purely for debugging. It's only used to show what symbol
a pseudo might be (and I stress "might", since CSE can and does
screw it up) associated with.
Also print out the def list for a basic block when verbose.
It all makes it a bit easier to guess what's up.
|
|
This should basically allow us to do register allocation. Or
maybe it's too broken. But the results look reasonable from a
quick manual peek.
|
|
We should drop symbol types by now, and base things on just raw
sizes. Anything else just doesn't work from a CSE standpoint.
Some things may care about actual types later, notably the type-
based alias analysis. Those types still exist in the cast nodes.
Also, make the printout be more readable.
|
|
Very useful for debugging, since otherwise it's often
impossible to find all the other basic blocks.
|
|
It will assrt if it can't find that many entries.
Zero means "all the ones you can find", aka old behaviour.
|
|
Besides, the code is cleaner now - we can use our helper functions.
|
|
We don't have usage counters, we have usage lists these days.
|
|
track of which instructions use which pseudos.
It also verifies the usage, which shows a few bugs in
structure handling.
|
|
You just have to be a bit crazy (*), and use "__typeof__" in
creative ways.
(*) Ok, a _lot_ crazy. But dammit, I want type-safety _and_
convenience, and I'm willing to do a few crazy macros to get
it.
|
|
The list pointer traversal macros are very easy to use, but
you can also mis-use them by passing in the wrong pointer type
without the macros having any chance to warn you about it.
Until now.
|
|
has to agree on it or bad things happen.
|
|
This allows us to notice when a symbol address usage is
trivially dead, and optimize such a symbol better since
we don't have to worry about the address being used to
access it.
|
|
from child and parent lists.
|
|
Also, remove OP_SEL from the "binop" list - it really really isn't,
since it has a third implied input in the OP_SETCC.
|
|
And make sure to set the bb on the branch we create.
|
|
This makes it easier to verify that they are used only in phi-nodes,
not anywhere else.
|
|
- value pseudos
- clear the list on usage transfer
- don't re-use OP_SWITCH as OP_BR when simplifying.
|
|
This made the phi-source CSE generate garbage, since the information
wasn't updated in the phi list of the user.
Move use_pseudo() to header file, since flow wants to use it too now.
|
|
The instruction contains everything "struct phi" had, namely
source bb and pseudo. And generating a new pseudo means that
we not only have the pointer to the instruction that defines
the phi-node (in pseudo->def), we also end up with automatic
phi-node usage tracking (pseudo->users).
The changes may look large, but almost all of this is just
direct search-and-replace of the old phi-node usage.
|
|
We can turn trivial phi-nodes into OP_SEL instructions instead,
and generally improve code flow.
This doesn't remove the empty blocks this results in yet, so
it's not quite as dramatic as it could be, but it does the hard
work. Empty block removal is trivial.
|
|
Instead of using the "convert_load_insn()" that converts them to
OP_LNOP's, which ends up confusing instruction printout horribly.
|
|
Small files are good. Now "linearize" really just contains the
code that does a straightforward linearization of the tree, and
flow.c contains the stuff that tries to analyse the result.
|
|
It happens. Deal with it gracefully, and turn it into
the proper jump.
|
|
Trivial basic block merging. I should do switch and branch
following too. Maybe next.
|
|
They only made sense with the original (broken) pseudo
liveness analysis.
|
|
We really don't care about all bb usage, only about the phi-nodes
that use bb's. All the other usage is pretty obvious from the
flow graph, no need to add them to the list (and if we _only_ add
phi-nodes, then it becomes easier to check whether a bb needs to
be saved due to phi-node issues).
The pseudo usage has nothing to do with an instruction, so don't
mix in the instruction into it.
|
|
Non-local symbols need more care. Function calls and pointer
accesses can obviously clash with them, so we're less likely
to find good domination. But every little piece helps.
|
|
We'll need this to efficiently rewrite bb's.
|
|
Instead of having magic iterators over the last instruction
of a basic block, we just add a list of "children" to each
basic block.
This removes all the packing logic, because it needs to be
totally rewritten to work with the new iterators.
|
|
Duh. They really were different types. One was a list of pointers to pseudos,
the other is just a list of pseudos.
Cset exclude: torvalds@ppc970.osdl.org|ChangeSet|20041112172911|52083
|
|
Use "pseudo_list" rather than "pseudo_ptr_list" type.
|
|
This looks for dominating stores and the whole enchilada.
It's likely buggy as hell.
|
|
We just look when a store dominates a load, and replace
the load with the source of the dominating store.
It would even be useful, but we give up at basic block
borders. Retard, I tell you.
|
|
This shows an interesting (?) bug with uninlining, where we seem to
go through the same symbol twice, resulting in complaints about symbols
used in strange ways (because we see an instruction that we have already
NOP'ped out, using a symbol).
I'm not convinced this is a bug yet - it might just be that we really
_can_ reach the same symbol twice. But I _think_ it means our uninliner
may have problems.
|
|
They don't really buy us anything, and while generating them
is easy, keeping them up-to-date is not.
Also, don't print out the killed OP_LOAD/OP_STORE instructions
that we voided by making the target be VOID.
|
|
the pseudos, not the instructions that use them.
That makes replacing a pseudo trivial: just walk the
list, and overwrite the thing we have a pointer to.
We also take advantage of the fact that symbol pseudos
only exist in the "address" part of memory load, so
if we know the pointer to the pseudo, we can calculate
the pointer to the instruction.
This makes the symbol pseudo replacement a lot more
effective.
|
|
This still leaves varargs wrong, but we'll get to that eventually.
|
|
We add a per-symbol pseudo, and just track them that way.
|
|
Well, at least part of the use pointers. I probably missed some uses.
|
|
A "value pseudo" is a pseudo that just has a constant value
at any particular time. Instead of allocating a real pseudo
for it, and associating the pseudo with an expression, the
pseudo itself is directly associated with the value.
Also remove a few explicit death-notes: branches and calls
always kill their arguments, so make that implicit rather
than waste time addign explicit notes.
|
|
This simplifies stuff that wants to allow either a calculated
expression pseudo, or a symbol. Use one of the pseudo-pseudos
for the symbol, and pass that one around.
First use: the address.
|
|
The memory access initialization would keep a cache of "original value
of the memory access" which means that we only do one read of a field
even if it's an update of a bitfield. But that means that the usage of
the pseudo in question needs refcounting.
|
|
This generates a "struct access_data" structure, which contains all
the offsetting/symbol information for the access, and which makes
things like bitfields and read-modify-writes all use the same basic
information.
|
|
linearized tree.
This just copies all the phi node information into the
source of the phi node, so that the linearized thing looks
a bit more like "real" assembly language. It's likely
bogus in many ways, but I want to make a pretty-printer
for the linearized output, and this will make it much
much easier to do.
|
|
It's a hell of a lot easier to add them when generating the
linearized output than it is to go back and analyse them later.
We know when we throw values away, so just note it.
NOTE NOTE NOTE! This is only a rough first draft. Not complete.
|
|
It's really pretty fake, but we used to ignore initializers
completely, so this is certainly better than that. Now we at
least linearize all the sub-expressions, and we do a kind
of fake assignment.
|
|
This allows us to get rid of the loop that searches for the def
of a pseudo when simplifying <phi+br> blocks.
|
|
half-way sane value.
This makes it easier to tell people where a linearizer
event happened. It won't be exact, but at least it will
be _somewhere_ closer than just saying "it was in this
function".
|
|
It just ends up propagating the expression to the linearizer,
which creates an internal "context" instruction for it.
|
|
packing blocks.
The entrypoint doesn't necessarily end up being the first
basic block in the list of blocks after we have packed them.
|
|
Handling of non-lvalue compound objects:
We introduce a new primitive - EXPR_SLICE. Meaning is "that many bits
from that offset in that non-lvalue struct or union". It is used when
we try to get a member out of a non-lvalue struct or union (subsequent .<field>
just narrow the slice). And as far as scalar, struct and union fields count,
that's it. The only subtle point is handling of array fields. And there
I'm doing what C99 requires - they *do* decay to real, honest pointers,
causing a copy of object to memory if needed. We get an anonymous object
that lives until the next sequence point; optimizer is certainly free to
get rid of it completely if it can make do with the value we'd copied there.
Note that you _are_ allowed to say
foo().a[1] = 0;
It doesn't make sense, since the value you've assigned will be immediately
lost (and any optimizer will turn that into f()), but it is legitimate and
it avoids a *lot* of PITA in describing semantics.
It covers only array decay - any other member of non-lvalue struct or union
is *not* an lvalue and in
struct foo {int x; int y[2];};
struct foo a(void);
...
a().x = 0; /* not allowed, non-lvalue */
a().y[0] = 1; /* allowed, but pointless */
you will get an error from the first assignment, but not from the second
one.
Signed-off-by: Al Viro <viro@parcelfarce.linux.org.uk>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
|
|
Since the "struct instruction" format doesn't allow for
all the data a select needs, we create two pseudo-instructions
instead, and generate a select as a combination of the two:
OP_SETCC + OP_SEL.
We should possibly do the same thing for conditional branches.
|
|
Make linearize.h show the right ops for the logical (as opposed to
binary) and/or EXPR_BINOP.
|
|
expression.
This is just a very high-level cost, mainly distinguishing
between "safe" and "unsafe" operations, so that we can
determine if we can turn a C conditional into a select
statement, or a logical op into one without short-ciruiting.
|
|
We need to emit an OP_COMPUTEDGOTO instruction with a
full list of potential targets.
|
|
simplify_int_binop() was completely broken for comparisons - there the
signedness of (converted) arguments can not be obtained from type of
result. IOW, we had all comparisons in constant expressions done as
signed ones.
Fixed by introducing new primitives for unsigned versions of
comparions (SPECIAL_UNSIGNED_LT, etc.) and remapping in evaluate_compare()
once we know the types. That also fixes similar mess in compile-i386 and
linearize.
|
|
Allow it to be used by multiple callers.
|
|
This fixes the linearization of "return", to use the proper symbol
target that the front end has already set up for it:
- linearize_statement(), case "STMT_COMPOUND" needs to create a label
at the _end_ (aftre doing the linearization of all the other stuff) if
"stmt->ret" is non-NULL.
- STMT_RETURN needs to move the return expression to the return variable,
and goto the return label.
|
|
- add pre/post op and assign add etc.
- change the call instruction have a list of arguments.
- change the pseudo_t to be struct pseudo_t *, prepare
for adding stuff to pseudo_t.
|
|
This is another small step. It adds binary ops, compare ops and ret.
The classic recursive Fibonacci numbers function should be working.
|
|
Here is the updated version of the patch.
I tried to do as well on the iterator flattening as the old code, but
then realized that the end result will be about as complex as what was
there from before. So instead I wrote a simple pass to stitch the basic
blocks together. It does two things: ff it is an empty block with a
goto, it transfers the outgoing edge directly to the target. And if the
only parent ends with a goto, it combines the block with the parent.
There is also dead code elimination. So I removed the previous entry
point hack for while loops. There is no need for that any more, and the
end result is that we generate very compact basic blocks, often better
than the previous approach did.
The extra pass can almost certainly be reused for other back end passes.
I also did:
- add some lib functions to delete a point from the ptr_list while
iterating.
- Ignore labels which are not used
- some minor bug fixing to the previous patch
Know problem:
- it doesn't deal with phi correctly, I need to redo the phi base
on Tommy's suggestion.
|
|
This improves the dead code eliminate for iterators that begin in an
unreachable section (eg a "while" statement inside a "if (0)").
The idea is that have a decoy entrypoint for those while loops. On copy
the basic block back only if there is C level label was found inside the
block.
It is tempting that left the dead code elimination and constant
propagation to the some back end pass.
|
|
And add a "OP_BADOP" linearization for expressions
that we don't do yet, so that it's easier to see what
is missing..
|
|
(Btw - a number of the linearizations are pretty spotty,
and not doing the right thing in the details. It's more
concept thing).
|
|
|
|
Linearize some simple expressions, the rest we just ignore
for now. This is crapola. I'm really not sure this is the
right way at all, but I don't see any good alternatives.
|
|
true basic blocks (with all exits at the bottom).
This will simplify some of the analysis.
|
|
It's almost understandable now.
|
|
symbol that "owns" it (unless it is entirely statically
unreachable).
Use this to do trivial constant conditional folding.
|
|
This required making the inter-BB trampoline to be done
using indirection through a symbol, rather than as direct
pointers from one BB to another. Fix up code to match.
Avoid a few warnings by handling GOTO_BB in the case
statements.
|
|
Right now we only really do trivial if-statements, but the
ideas are all there now.
|
|
"concat_ptr_list" (which also is more accurate).
Declare linearize_symbol().
|
|
yet, but the framework is there.
When we linearize the tree we just generate a list of basic
blocks of statement expressions (and branches between them,
although that "small details" isn't actually done yet ;).
|
