| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
This guarantees the generated version.h will exist before attempting
to compile any c files that include it.
Several source files include the generated version.h, but not all
declare a proper make dependency.
$ grep -r 'version\.h' *.c
compile-i386.c:#include "version.h"
lib.c:#include "version.h"
options.c:#include "version.h"
This allows a sufficiently parallelized make invocation to encounter
ENOENT.
CC compile-i386.o
compile-i386.c:60:21: fatal error: version.h: No such file or directory
compilation terminated.
Makefile:253: recipe for target 'compile-i386.o' failed
make: *** [compile-i386.o] Error 1
Signed-off-by: Kyle Russell <bkylerussell@gmail.com>
[luc.vanoostenryck@gmail.com: modified so that only version.c depends on version.h]
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When computing the absolute value using an expression like:
(a > 0) ? a : -a
it's irrelevant to use '>' or '>=', both will give the same
result since 0 is its own negation.
Canonicalize these equivalent expressions, such that OP_GE
is always used.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Both compares and OP_SELECT are anti-symmetrical: swapping
the arguments is equivalent to inversing the condition.
As consequence, when combined, they're symmetrical:
swapping the arguments of the compare (or equivalently reversing
the direction of the compare) and swapping the operand of the
OP_SELECT is a no-op, both forms are equivalent.
So, canonicalize these to always use OP_GT or OP_GE.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Modify the constants to canonicalize (x < C) to (x <= (C-1)) and
(x <= C) to (x > (C-1)). This choice is partially arbitrary but
1) it's the one with the smallest positive constants,
2) it eliminates all OP_SET_LT & OP_SET_GE with a constant.
A disadvantage of this choice is that we lost some compares with 0:
(x < 0) is now canonicalized into (x <= -1).
Note: Another good choice would be to canonicalize using the
smallest absolute constants. This would keep compares with 0
but would also keep the 4 kinds of comparison.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Compares with SMIN + 1 or SMAX - 1 are equivalent to an equality
testing. For example, (x < SMIN + 1) is the same as (x == SMIN).
Canonicalize these to the equality testing since these are usually
simpler to handle.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The remaining compares with SMIN or SMAX are equivalent to an
equality testing. For example, (x < SMAX) is the same as (x != SMAX).
Canonicalize these to the equality testing since these are usually
simpler to handle.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Simplify away signed compares with SMIN or SMAX which can be
statically be determined to be always true or always false.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed compares miss some simplifications/canonicalizations.
Add some testcases for them.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In Sparse, the PSEUDO_VALUEs are required to be truncated at their
effective size. For example, for a 32-bit instruction and Sparse using
64-bit integers, a pseudo of -1 must contain the value 0x00000000ffffffff,
not 0xffffffffffffffff.
Add the missing truncation in the canonicalization here.
Fixes: c355e5ac5dce35f3d95c30cd5e2e9a5074c38437
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Commit a1c1b9236d5d ("cmp: simplify sext(x) cmps {SMAX,SMIN}")
had a double error (wrong size and wrong compare direction) which
was hidden because of too narrow testcases.
So, fix the simplification and extend the testcases.
Fixes: a1c1b9236d5d4af1681a45ced26f8350bd7721c2
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When handling compares of an {zero,sign}-extended value, the
size of these extended values are used but this size is just
the operands' size of the compares.
Make this clearer by using a single variable 'size' for it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
|
|
A logical shift right followed by a sign extension is equivalent
to an arithmetic shift. Teach this to sparse.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
can_move_to() is used to test if it is safe for a given pseudo to
be used by some instruction. This is done by checking that the
pseudo is defined 'before' the instruction.
This should, of course, reject the cases where the pseudo is defined
by the instruction itself because it would create a circular definition.
However, this special case was not checked.
Fix this by adding the missing check.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* handle qualified anonymous structures
|
|
|
|
The kernel is trying to use a unnamed struct to mark a group of
fields as being 'const' and get a warning if one of its member is
assigned. GCC gives indeed a warning but Sparse and clang don't.
So, the type qualifiers of the anonymous struct need to be propagate
to the members.
An easy, one-liner, solution is to handle this inside find_identifier(),
where access to the members are recursively searched inside sub-structures.
It's very easy but it feels wrong to do semantics inside this function.
Worse, it's only working for members that are effectively accessed,
doing a type evaluation on the anonymous struct (or its parent)
would, by itself, not handle this.
So, the solution chosen here is to handle this during type examination,
more precisely, inside examine_struct_union_type(), where things are
a bit more complicated (it can't be done when examining the members
themselves because only the parent SYM_STRUCT is accessible and the
qualifiers are in the SYM_NODE, so it needs to be done when examining
the anonymous struct itself) but can be done for all members.
Note: It would seem logical to also handle at least all qualifier-like
attributes but GCC seems to only bother with the true qualifiers
and ignore things like attributes and alignment specifiers.
Link: lore.kernel.org/r/CAHk-=wj4Kviw8q2Sx9vrrvyn3uWK-zNi4uGRx=5bzde0Cio8uQ@mail.gmail.com
Link: lore.kernel.org/r/CAHk-=wjdJmL22+zk3_rWAfEJJCf=oDxiJ530qk-WNk_Ji0qhxw@mail.gmail.com
Thanks-to: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In commit 4a5f616407e2 ("cmp: canonicalize sext(x) cmpu C (with C >= SMAX)"),
the operand is replaced to avoid a sign extension but the corresponding
type was not updated. Fix this now.
Fixes: 4a5f616407e26efb67013f8267adef2d6e093bf1
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A trivial patch to remove an unused parameter.
Link: https://lore.kernel.org/linux-sparse/1282818698.12802.23.camel@thorin
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
I understand why the compiler would complain about this
'maybe-uninitialized' variable (it's always initialized when used)
but I don't understand why the warning suddenly occurs while the
variable have already been dereferenced several times; But well ...
Initialize it with NULL to shut up the warning.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* packed: add support for __packed struct
|
|
* 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
|
|
rem_usage() is used to remove an element from a def-use chain. Optionally,
if the chain become empty, the defining instruction can also be killed.
This optional part is currently be done on all pseudos but only those
having a definition should be concerned.
Fix this by adding a check so that only PSEUDO_REGs and PSEUDO_PHIs are killed.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
Now that the 'packed' attribute is parsed and propagated into
the type system, adapt the layout of structures.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
There is (at least) 2 ways by which packed bitfields doesn't
follow normal layout/access rules and as consequence can't (always)
be accessed the usual way (load the whole underlying word, then shift
and mask to isolate the bitfield).
At least two different cases are a concern:
1) there is no padding at the end of a bitfield sequence. For example,
the following struct is only 3 bytes width:
struct s {
int f:24;
} __packed;
So, trying to access the bitfield by first doing a 32-bit load
will create an out-of-bound access.
2) a bitfield smaller than one word may need more than one word to be
accessed. For example, with the following struct
struct {
int a:5;
int f:30;
int z:5;
} __packed;
the bitfield 'f', while smaller than one 32-bit word, can't be accessed
with a single 32-bit access.
At machine level, these bitfields should be accessed with several, possibly
smaller, loads and their corresponding values reconstructed from these,
making things much more complicated than for non-packed bitfields.
But at IR level, things can be a little more flexible and things can stay
simple by using sub-word or super-word accesses (until these need to
be lowered to be usable at machine level). In other words, the example here
can be safely accessed with respectively a 24-bit and a 40-bit load.
This is what is done in this patch.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
GCC's syntax for type attributes is specified as:
An attribute specifier list may appear as part of a struct,
union or enum specifier. It may go either immediately after
the struct, union or enum keyword, or after the closing brace.
The former syntax is preferred. Where attribute specifiers
follow the closing brace, they are considered to relate to
the structure, union or enumerated type defined, not to any
enclosing declaration the type specifier appears in, and the type
defined is not complete until after the attribute specifiers.
In the section about type attributes, it's also said:
You may specify type attributes in an enum, struct or union type
declaration or definition by placing them immediately after the
struct, union or enum keyword. A less preferred syntax is to
place them just past the closing curly brace of the definition.
So, while placing the attribute after the closing curly is not
preferred, it is cleary legal (and it seems to be much more popular
than placing them just after the struct, union or enum keyword).
However, currently sparse doesn't handle this correctly:
- these attributes are parsed in declaration_specifiers() and
added to the current decl_state
- when the ';' ending the type declaration is reached, the plain
struct/union/enum is used and the content of the decl_state is
simply ignored.
- if the declaration is for a variable, then those attributes
are assigned to the variable (but not to the type).
Fix this by calling handle_attribute() once we have reached the
closing '}' of a struct/union/enum definition and applying these
attributes, if any, directly to the current base type.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In a declaration like:
struct <some attribute> { ... }
the attribute belong to the type but is currently handled as belonging
to the whole declaration.
Fix this by handling such attributes in a local 'decl_state' and
applying them once the closing '}' is reached.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Type attributes for struct can be placed either just after the
keyword 'struct' or after the '}' ending its definition but this
later case is currently ignored.
Prepare the handling of this by having the 3 following cases in sequence:
1) a tag is present
2) no tag present but is followed by an opening brace
3) neither of these, so it's an error.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Type attributes for struct can be placed either just after the
keyword 'struct' or after the '}' ending its definition but this
later case is currently ignored.
Prepare the handling of this by restructuring the code handling
struct specifiers, namely inverting the condition so that the
function can return early to make next patch's job easier.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Type attributes for struct can be placed either just after the
keyword 'struct' or after the '}' ending its definition but this
later case is currently ignored.
Prepare the handling of this by factoring the code common to both
cases in a single place.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
apply_ctype() will be needed earlier in the code.
So, move it's prototype up.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
apply_ctype()'s argument order confuse me endlessly as I'm much more
used to have the destination first and the source next (the so called
'assignment order' used for assignments but also in memcpy() and in
many sparse or library functions).
So, change the argument order of apply_ctype() to mimic the order
of memcpy()/assignment, to hopefully reduce my confusion.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
apply_ctype() is used to copy/apply things like modifiers
and address space from one type to another one.
But the names used for the two types are: 'ctype' & 'thistype'
which doesn't help at all to know which one is the 'source' type
and which one is the 'destination' type.
Change this by renaming these arguments to 'src' & 'dst'.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, packed bitfields are not handled correctly.
Add some testcases for them.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, packed structs are not handled correctly.
Add some testcases for them.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, type attributes are not handled correctly.
Add some testcases for them.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
There is more than one complexity in the evaluation of enums.
Add a test for enums with 'exotic' values not covered in other tests.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
sparse accept any type of integral value for enumerators
but address constants are also accepted, which is 'strange'.
Add a testcase for such 'enums'.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The macros used to iterate the ptrlists exist in two kinds:
those to iterate forward direction and those to iterate in the
reverse direction.
Those macros must be used in pair: one for the top of the loop and
one at the end of the loop. However, if we mix them, for example like:
FOR_EACH_PTR(list, var) {
...
} FOR_EACH_PTR_REVERSE(var);
things will still work for lists with a single block (most of them)
but will behave strangely and of course wrongly when reaching the
next block.
So, to avoid future debugging fun, add a unused variable, discarded
at compile time, but with distinct prefix for each direction. This way,
mixing the macros will create a warning at compile time.
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>
|
|
* fix parsing of tags used in the testcases
|
|
In testcases' tags, if a value contains 'check-' then this
value will be used as the tagname instead of the value.
Fix this by adding a bit more context in the regexp used for parsing these.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix killing OP_ASM
* move check_access() to late_warnings()
|
|
check_access() is called at each run of simplify_loads().
However, a bad access can belong to a dead branch and thus a
bad access warning can be issued for code that is not executed,
maybe specifically excluded.
So, move check_access() to late_warnings(), where all optimizations
have been done.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently OP_ASMs are only handled by default in kill_insn().
In consequence, the usage is not removed from their inputs,
possibly leaving dead pseudos.
Fix this by removing the usage on the input pseudos.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* let replace_with_pseudo() use kill_instruction()
* move rewrite_load_instruction() to memops.c
* replace convert_load_instruction() by replace_with_pseudo()
|
|
* memops: fix wrong killing of stores partially dominated by a load
* memops: kill dead loads before phi-node conversion
|
|
During load simplification it may happen that a load is unused
but if this fact is ignored and the usual conversion to a phi-node
is made, then this value may seem to be needed and can't anymore
be simplified away.
Fix this by removing dead loads during load simplification.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When a partial but overlapping load is followed by a store, this
load is not considered as dominating the store. This is a problem
for kill_dominated_stores() because the load will be simply ignored.
For example, in code like:
union {
u64 l;
int i;
} u;
int i;
u.l = x;
i = u.i;
u.l = y;
The load will be ignored, then the first store can be ignored too
and the value of 'i' will be undefined (but actually set to 0).
The root of the problem seems to be situated in dominates() where
a load is considered as dominating another memop only if both
correspond to the same 'access' (address and size).
This is probably fine when the other memop is itself a load (because
the value of the first load can't be reused for the second one) but
it's not when the other memop if a store.
So, to be safe, consider different-but-overlapping memops as neither
dominated or non-dominated but as "don't know".
Note: as explained here above, this can *probably* be relaxed when
both memops are loads but it's not 100% clear to me yet and
I found no examples where it actually make a difference.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
These two functions are now exactly the same, so replace the
first one by the second one.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The function rewrite_load_instruction() is defined in flow.c but:
* is not directly related to 'flow'
* it's only used in memops.c
* needs some change related to simplify_loads().
So, move this code to memops.c
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This function can be useful since it can be useful in other files,
for example in memops.c
So make it extern..
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The few external functions defined in simplify.h are declared
in flow.h (for historical reasons).
In preparation for some changes, create a specific headers for these.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In replace_with_pseudo(), the replaced instruction needs to be killed
and for this contains ts own code.
But this is a duplication of what is already done in kill_instruction().
So, replace this part of the code by a cal to kill_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* factorize (x OP1 z) OP2 (y OP1 z) into (x OP2 y) OP1 z
* factorize SHIFT(x, s) OP SHIFT(y, s) into SHIFT((x OP y), s)
* factorize SEL(x, OP(y,z), y) into OP(SEL(x, z, 0), y)
* convert SEL(x & BIT1, BIT2, 0) into SHIFT(x & BIT1, S)
|
|
Convert an expression like:
(x & (1 << A)) ? (1 << B) : 0
into:
(x & (1 << A)) << (B - A)
or:
(x & (1 << A)) >> (A - B)
Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add log2_exact() to get the base 2 logarithm of a value known
to be a power of 2.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add is_pow2() to test if a pseudo is a power of 2.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add is_power_of_2() to test if a value is a power of 2.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
'Factorize' and expression like:
x ? (y | z) : y;
into
(x ? z : 0) | y;
and some positional variants as well as replacing '|' by '+' or '^'.
Note: it's not very clear if this is really an improvement but it
allows some very nice simplification of 'bits translations'.
Note: the same can be done for others operations, for example it can
be done for '&' if '0' (the neuter value for '|', '+' and '^')
by '~0' (same with '*' and '1').
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add some testcase related to the simplification of expressions like:
if (val1 & BIT1)
val2 |= BIT2;
into
val2 |= (val1 & BIT1) {SHL/LSR} |BIT2-BIT1|;
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Factorize bitwise OPs of shifts with identical counts.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Factorize common distributive operations:
(x * z) + (y * z) --> (x + y) * z
(x | z) & (y | z) --> (x & y) | z
(x & z) | (y & z) --> (x | y) & z
(x & z) ^ (y & z) --> (x ^ y) & z
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Do some refactoring in simplify_add() to avoid some code
duplication there and better handle generic transforms
that need to be applied on both operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Do some refactoring in simplify_add() to prepare the next patch
which will avoid some code duplication there.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add an helper to replace a binop OP(a, b) and taking care to
drop the usage of the previous operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add two helpers to create instruction pair OUT(IN(a, b), c).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When transforming IR expressions, it may happen that we want to
reuse an instruction and move a pseudo into it but that this pseudo
is only defined later.
Add a small help to check this: can_move_to().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add some testcases for factorizations of:
(x * z) + (y * z) --> (x + y) * z
(x | z) & (y | z) --> (x & y) | z
(x & z) | (y & z) --> (x | y) & z
(x & z) ^ (y & z) --> (x ^ y) & z
and
(x << s) | (y << s) --> ((x | y) << s)
and same for &, ^, LSR and ASR.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix trivial_phi() when the target is before the single value
|
|
A phi-node is called 'trivial' if it only reference itself and a
single other value. In this case the only possible value for the
phi-node is this single other value which can thus replace the
phi-node.
However, the current code get this slightly wrong when the first
referenced value is itself and not the other value.
Fix this by moving up the test checking if it references itself.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* give a type to OP_SYMADDR
|
|
* put PSEUDO_ARGS and PSEUDO_REGs in canonical order too
* simplify (~x {&,|,^} x) --> {0,~0,~0}
* simplify ((x cmp y) {&,|,^} (x !cmp y)) --> {0,1,1}
|
|
Currently, OP_SYMADDRs are given a size but not a type.
But the type is needed for several things, the idea being
that for each instruction producing a pseudo (PSEUDO_REG)
it's possible to:
* retrieve its defining instruction
* retrieve its type via this defining instruction
Fix this by giving to OP_SYMADDRs the type of their symbol.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
|
|
* simplification of computed gotos with 1 or 2 targets
|
|
Simplify bitwise operations on a compare and its complement
into 0 (for &) or 1 for (| and ^).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Simplify bitwise operations on a pseudo and its complement
into 0 (for &) or ~0 for (| and ^).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
Currently, only binops containing PSEUDO_VAL, SYM or ARG were
put in canonical order. This means that binops containing only
PSEUDO_REGs are not ordered. This is not directly
a problem for CSE because commutativity is taken in account but:
* more combination need to be checked during simplification
* 'anti-commutative' operations like (a > b) & (b < a) are not
recognized as such.
So, take PSEUDO_REGs in account when checking if operands
are in canonical order.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, only binops containing PSEUDO_VAL or PSEUDO_SYM were
put in canonical order. This means that binops containing only
PSEUDO_ARGs or PSEUDO_REGs are not ordered. This is not directly
a problem for CSE because commutativity is taken in account but:
* more combination need to be checked during simplification
* 'anti-commutative' operations like (a > b) & (b < a) are not
recognized as such.
So, as a first step, also take PSEUDO_ARGs in account when checking
if operands are in canonical order.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Convert OP_SETVAL of a label into a new instruction: OP_LABEL.
There is 2 reasons to do this:
*) there is slightly less checking to be done in later phases
(since OP_SETVAL can be for labels but also strings)
*) OP_SETVAL is CSEd but this is largely useless because this
instruction is hashed on the expression's address and these
are (most) often not shared. With a separate instruction
for label expressions, their CSE is now OK because the hashing
is done on the BB.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A computed goto having as operand a select of 2 statically known addresses
(OP_SETVAL/EXPR_LABEL) is equivalent to a simple conditional branch.
Simplify such computed goto into the corresponding OP_CBR
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the OP_COMPUTEDGOTO's source pseudo is defined by a single
OP_SETVAL/EXPR_LABEL, then the corresponding basic block is the
only possible destination and the computed goto can then be
simplified into a simple branch.
So, convert such computed goto into a simple OP_BR which may
then participate in other flow simplifications.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In instructions, the first pseudo operands exist under different
names (.src1, .src, .cond, .phi_src) all aliased to each other.
Use this to simplify unops and others instructions with a single
pseudo operand.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Since simplify_memops() must be called unconditionally (see [1])
it's useless to set REPEAT_SYMBOL_CLEANUP (at the condition that
REPEAT_CSE is set instead).
So remove it's definition and set REPEAT_CSE instead when needed).
[1] 6b5e7cf5ac39 ("cfg: call simplify_memops() unconditionally.")
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When killing OP_SETVAL's, kill_use(&insn->src1) is called to
remove the usage of its first operand but OP_SETVAL has no
such operand.
Fix this by moving the corresponding entry with OP_SETFVAL and
others instruction without operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
|
|
* rebuild dominance tree during CFG cleanup
* simplify CBR-CBR on the same condition
|
|
The '++' and '--' operator used in evaluate_postop() are
'restricted' operators. It's thus unneeded to call restricted_unop()
on them as it will always return '1'.
It's also unneeded to test for TYPE_RESTRICT since it will also be
tested in unrestrict().
So, simply call unrestrict() unconditionally.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* unqual: comma expressions should drop qualifiers
* unqual: statement expressions should drop qualifiers
|
|
Statement expressions should be subjected to lvalue-conversion
and thus should drop qualifiers.
Fix this by calling unqualify_type() after array-to-pointer
conversion.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Comma expressions should be subjected to lvalue-conversion
and thus should drop qualifiers.
Fix this by calling unqualify_type() after array-to-pointer
conversion.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
It's possible that the input type is NULL, so add a check for it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add some testcases related to qualifier dropping / lvalue conversion.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Casts should drop qualifiers but Sparse doesn't do this yet.
The fix seems pretty simple: after having evaluated the type of
the cast, if this type is a SYM_NODE and contains qualifiers,
make a copy of the type with the qualifiers removed and use
this copy as the type.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
These declarations are not needed, so remove them.
A few of the other ones could/should be removed but
it would need to shuffle some code around.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* cfg: remove phi-sources when merging BBs
* cfg: remove phi-nodes when merging BBs
* cfg: add missing REPEAT_CFG_CLEANUP
* cfg: call simplify_memops() unconditionally.
* cfg: early CFG simplification
|
|
In situations like:
...
cbr <cond>, L1, L2
L1: L2:
... ...
L3:
cbr <cond>, L4, L5
since the conditions are the same and L3 is empty but the CBR,
all branches to L3 in L1 can be changed to branches to L4
(idem with L5 in L2). The same can be done in all BB 'in the
path between L1 and L3', more exactly in all BB dominated by L1,
this guarantee that the changes is only done on the BB where
the conditions match.
Note: This simplification kinda generalizes the current
simplify_branch_branch() but should itself generalized
to handle the presence of phi-sources in L3.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, the dominance tree is build once, just before the
SSA conversion.
However, changes in the CFG potentially changes the dominance
relationships.
So, rebuild the dominance tree after changes to the CFG.
Note: This doesn't seems to significantly affect the performance
(at least when used on the kernel):
before after
real 4m15.854s real 4m16.95&s
user 71m11.390s user 71m29.180s
sys 28m45.222s sys 28m46.145s
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The linearization step sometimes creates a lot of intermediate
basic blocks, often containing just a branch. Their presence often
make things more complicated than needed (more work to do in later
phases, visual clutter when inspection the IR 'by hand') and they
can sometimes, indirectly hinder some optimizations.
Happily, most of them can trivially be optimized away.
So, add a CFG simplification phase running very early and doing:
*) jump threading (eliminate jump to jump)
*) merge single-child/sinle-parents basic blocks.
These changes slightly decrease the number of 'context imbalance'
warnings (32 less on a total of 995 warnings) and the size of
the generated IR (only ~0.4% but this is very significant relatively
to most other simplifications).
They also seem to improve the kernel tests' running time:
before after
real 4m19.261s real 4m17.548s
user 72m03.634s user 71m34.642s
sys 29m05.573s sys 29m01.856s
but it's probably just noise.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, in the main optimization loop, simplify_memops()
is only called if REPEAT_SYMBOL_CLEANUP have been set. This
has (at least) two problems:
1) simplify_memops() may itself create other 'symbol cleanup'
opportunities. That's fine and when it happens REPEAT_SYMBOL_CLEANUP
is correctly set but this is directly lost because repeat_phase
is cleared just after. So, loads and stores are not always
optimized away as they should.
2) Loads & stores are not always done directly on symbols, in
fact, it often happens that they are done on some PSEUDO_REG.
Here too, loads and stores are not always optimized away as
they should.
So, call simplify_memops() unconditionally.
Note: this have only very small effects on the tests' running time:
before after after too
real 4m18.001s real 4m18.655s real 4m19.4
user 71m32.911s user 72m02.701s user 72m06.6
sys 29m06.523s sys 29m01.721s sys 29m06.8
which is under the noise I usually have.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
simplify_branch() & insert_branch() convert a conditional branch
into an unconditional one, removing a child which may then
become unreachable.
However, these function doesn't set REPEAT_CFG_CLEANUP and the
unreachable child may not be removed.
Fix this by setting the missing REPEAT_CFG_CLEANUP in these functions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When merging BBs, it's possible that the top BB feeds one or
several phi-nodes in the bottom BB. Since phi-nodes only make
sense for values incoming from the parent BBs, these phi-nodes
can and should be removed when merging the BBs.
So, when merging BBs, remove these related phi-nodes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When merging two basic blocks, it may happen that both of theses
blocks contain a phi-source for the same phi-node. In this case,
only the phi-source from the bottom BB must be taken in account,
it kinda overwrites the value from the top BB and the phi-source
from the top BB must be ignored, in fact it must be removed.
However, it is not the case and this extra phi-source creates
different kinds of problems. Among other things, it hinders
further simplifications. For example, the following code:
extern int array[2];
static inline int stupid_select(int idx)
{
if (idx)
idx = 0;
return array[idx];
}
int select(void)
{
int d = stupid_select(-1);
return d;
}
should boil down to a simple dereference of the array with
an index of zero, like:
select:
load.32 %r8 <- 0[array]
ret.32 %r8
but currently gives:
select:
phisrc.32 %phi3(idx) <- $0xffffffff
phisrc.32 %phi4(idx) <- $0
phi.32 %r12(idx) <- %phi3(idx), %phi4(idx)
sext.64 %r5 <- (32) %r12(idx)
mul.64 %r6 <- %r5, $4
add.64 %r7 <- %r6, array
load.32 %r8 <- 0[%r7]
ret.32 %r8
This patch takes care of the problem by:
* when merging 2 BBs, check when reaching a phi-source in the bottom BB
* if one is found, look after sibling phi-sources
* remove such sibling if belonging to the top BB.
With this change, the code above gives:
select:
phisrc.32 %phi4(idx) <- $0
phi.32 %r12(idx) <- %phi4(idx)
sext.64 %r5 <- (32) %r12(idx)
mul.64 %r6 <- %r5, $4
add.64 %r7 <- %r6, array
load.32 %r8 <- 0[%r7]
ret.32 %r8
which can the be simplified into the expected result.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Extract merge_bb() from pack_basic_blocks() in order to reuse this
part of the code in other simplification/finer grained version of
pack_basic_blocks().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When merging BBs, phi-sources from the bottom BB should 'overwrite'
the ones from the top BB which should be ignored.
Add a testcase from the incoming fix.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Reduced testcases (with creduce, of course) often needlessly have
undefined variables. Since these are untouched by the simplification
code and should not be present in source code, they should be avoided
in optimization testcases.
So, defines 'x' to some value other than 0.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
and instead of keeping the old name for compatibility, no it's rejected.
But well, purity of language is surely much more important than compatibility.
*long deep sigh*
So, use the new name (but it will for sure create problems when using
an older version of Sphinx).
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>
|
|
* do not call simplify_instruction() on removed instruction
* add debug helpers: show_insn_bb() & show_insn_entry()
|
|
* simplify & canonicalize compares
|
|
* simplify SEL(SEL(...), ...)
* simplify SEL(x == y, x, y) and friends
* simplify SEL(x, x, x) and SEL(x, 0, x)
|
|
The merge of the branch with the linear_isdigit() experiment
and the branch giving a type to OP_SETxx's arguments created
a semantic conflict: the compare used for the isidigt() builtin
needed the type too.
Fix this now.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The dual simplification select(x, 0, x) --> 0 was already
done but this one was forgotten, so add it now.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This simplification is already handled but explicitly kills it's 2
operands while this is done automatically when killing the instruction.
Also, it uses replace_with_value(0) which needs to recreate the
pseudo for 0 while it's already available via its operands.
So, changes to use replace_with_pseudo() and without the unneeded kills.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Compare instructions with both operands sign or zero-extended
from the same original size are equivalent to a compare of
the original values. If the values were zero-extended, a signed
compare becomes an unsigned one.
Simplify away the sign/zero-extensions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
An unsigned compare of a zero-extended value against a
constant outside of the original range is statically known.
Simplify to the corresponding 0/1.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A signed compare of a zero-extended value against a constant
outside of the original range is statically known.
Simplify to the corresponding 0/1.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A unsigned compare of a sign-extended value against a value
bigger than the original SMAX is equivalent to a signed
compare against 0.
Canonicalize to the signed compare against 0.
Note: ultimately both forms are just a test of the sign bit.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A signed compare of a sign-extended value against a constant
outside of the original range is statically known.
Simplify to the corresponding 0/1.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When doing a compare of a zero-extended value against a constant,
this extension can be dropped and the comparison done on the
original type if the constant is within the original range and
signed compares become the corresponding unsigned one.
Simplify away these sign-extensions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When doing a compare of a sign-extended value against a constant
the, sign-extension can be dropped and the comparison done on the
original type if the constant is within the original range.
Simplify away these sign-extensions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Unsigned <= or > against SMAX are equivalent to testing if the
value is positive or not (when interpreted as a signed number).
Canonicalize to this positive/negative test since it only needs
the constant 0 which make it easier to handle at later steps.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Unsigned compares with UMAX (or UMAX-1) are equivalent to
equality tests. These are preferable since it's easier to reason
about them in other simplifications.
So canonicalize these compares to equality tests.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
These compares are always true or false, so simplify them.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
An unsigned comparison like (x < 3) is equivalent to (x <= 2).
Canonicalize '<' & '>=' to '<=' & '>', such that the smallest
constant is used.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The current code for the simplification of compares is quite
simple but also repetitive because everything must be done 4 times,
one for each operations (<,<=,>=,>).
So, add 2 helpers to factor out the details of the common parts.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
simplify_constant_rightside() contains a few simplification
regarding unsigned compares but much more can be done for
unsigned and signed ones.
So, move the current simplification in a separate function.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The opcode table allows to efficiently store some properties of
the IR instructions and the correspondence between some of them.
One of these correspondences the 'signed' / 'unsigned' version
of otherwise identical instructions. This is useful for some
transformation of compare instructions but is not present yet
in the table. So, add this now.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the condition of a select instruction is a equality test of the
select's operands, then the result of the select is always the same as
its second operand. Same for the first operand with an inequality test.
Simplify away these selects.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the operands of a select instruction are identical, then
this select can be replaced by its operand.
If the condition of a select is a constant, the this select
can be replaced by one of its condition, depending on the
truth value of the condition.
This simplification is already done but:
* when src1 == src2, the condition's value is tested although
it may not be a constant. It's kinda OK because in all case
one of the operand will be selected and both are identical
but it's a bit weird and unclean.
* since the instruction will be replaced, the usage of its
condition and operands must be removed. This is done here but
the kill_instruction() inside replace_with_pseudo() take
already care of this.
So, separate the two cases and simply use replace_with_pseudo()
for both without bothering killing the operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the condition of a select is also a select, with constant
but non-zero operands, then the result of this inner select
is always true and the outer select can be replaced by its
second operand.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the condition of a select is also a select, both with the same
arguments: first a non-zero constant, then a zero constant, then
the outer select is equivalent to the inner one and can thus
be replaced by the result of the inner select (which is its own
condition).
Note: this is a special case of:
SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z)
and without this patch we'll have:
t = SEL(x, C, 0)
r = SEL(t, C, 0)
simplified into:
t = SEL(x, C, 0) // possibly unused now
r = SEL(x, C, 0)
but the present patch do
t = SEL(x, C, 0)
r = t
In other words, functionally, the result is the same but
now the result is taken from the first instruction.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the condition of a select is also a select but with constant
operands, some simplification can be done:
* if the second operand is 0, the original condition can be used,
* idem if the first operand is 0s but the operand must be swapped.
Originally-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The current testcase, because it's just checking test-linearize's
output as-is, is very sensitive to small simplification changes.
Fix this by changing the tests into equivalent tests and then just
checking that these tests return '1'. This allows to test only what
really matters for canonicalization and make these tests very robust.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* give an explicit type to compare's operands
|
|
As an experiment about the linearization of builtins,
try this easy one (and statically expand it if the
argument is constant).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When linearizing __builtin_fma(), the arguments were just
assigned but the corresponding usage was not tracked.
Fix this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Hmmm ... the wrong pointer was updated. Fix this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The current tags check-output-contains/excludes/pattern are
quite powerful and the new check-output-match is easy to use
but it can be even simpler. Indeed, a lot of IR simplifications/
canonicalizations can be tested by checking that the expression
to be tested is equivalent to another one. This is less precise
than some more specific tests but:
* it's a big advantage because it's less sensitive to 'noise'
like the exact number used by the pseudos or to the results
of some new simplifications or canonicalizations
* very often, this equivalence is what really matters and not
the exact transformation.
So, add a new utra-simple-to-use tag: just ask that all functions
of the tests return the same specified value (usually 1):
check-output-returns: <value>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The current tags check-output-contains/excludes/pattern are
quite powerful, universal, but they often need 'complex' regular
expressions with escaping which make them not so nice to read.
For testing IR results, a very common pattern is:
this instruction must have this (kind of) operand.
So, make a new tag for this. It does nothing than can't be done
with done with the previous ones, on the contrary, but is much
simpler to use:
check-output-match(instruction): operand
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
simplify_instruction() is called on every instructions, even
those already removed. It's useless (and annoying when debugging).
So, filter out removed instructions before calling simplify_instruction().
Fixes: c5ba883e6ac47381f8112ed33f22a931a79ac517
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
These 2 helpers are just small wrappers around show_instruction()
and show_entry() but can be called even when the instruction is
removed. They're just handy when debugging.
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>
|
|
Because of the lack of type information, compare instruction are
not always handled correctly. So, add some testcases for this.
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>
|
|
'old-style' and 'kill-dead'
* cleanup linearize_cond_branch()
* OP_INLINE should not use the function symbol
* add testcase for missing inline definition
* fix testing if a OP_CALL's function is pure
* warn on all missing parameter types
* kill dead instructions before any other simplifications
|
|
In C a label must precede a statement. A null statement is OK
but a closing braces is not.
So, catch this situation, emit a warning and continue as if a
null statement was there.
This occurs currently on v5.10-rc1 because of some ifdefery.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
kill_instruction() will kill an OP_CALL but only if it's a
forced kill or if the corresponding function is pure.
However, only functions called via a symbol pseudo are so killed.
Those called via a function pointer are not because only symbol
pseudos contain the function type needed to test the presence of
the MOD_PURE modifier.
Fix this by using the function type always available in the
instruction's ::fntypes member.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This is just a wrapper around first_ptr_list().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Dead instructions are removed when simplify_instruction() is
called but this is done in various places, depending on the kind
of instructions, sometimes after other simplifications.
Change this by using the instruction's flag OPF_TARGET at the very
beginning of simplify_instruction() to test which instructions are
dead and thus can be removed.
Note: OP_CALLs are special here as they're considered as always
returning a value but only calls to pure functions are
removed. This is OK since pure functions should always
return a value.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
OP_CALL keep a list with the type of the function itself
and of each of its arguments.
However, the function type added to the list is not the complete type
but its base type. So, we can't use the function's modifiers or contexts.
Fix this by storing the complete function type.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The instruction OP_INLINE is a kind of note or comment, indicating
that the code below it used to be the body of a function which has
now been inlined. The symbol of the original function is displayed
when this instruction is displayed but this symbol should not be
considered as being used by the instruction since there is no
dependency or def-use chain between the two.
So, replace the use_pseudo() by a simple assignment.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* simplify and canonicalize unsigned compares
* basic unop simplifications
|
|
* llvm: fix crash with llvm-11 / use real phi-nodes
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, simplify_unop() can only handle the simplification of
-(-x) and ~(~x).
Prepare it to handle more cases.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some unsigned compares against 0 or 1 are equivalent to testing
equality with 0 (x <= 0, x > 0, x < 1, x >= 1).
Canonicalize them to this later, more common form.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some unsigned compares against 0 are always true or always false
(x < 0 or x >= 0). Simplify them.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
No functional changes here, just some more consistency:
* systematically use break instead of 'return VOID'
* remove some superfluous curlies
* remove some unneeded blank lines
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add a few testcases for the simplification of unary operations.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
sparse-llvm crashes with LLVM-11. From what I can see, it's because
LLVM-11 doesn't like anymore that an instruction is first created
unattached to a basic block (LLVMClearInsertionPosition()) and
inserted at some later step (LLVMInsertIntoBuilder()). Since the
corresponding function still exist I suppose they're working correctly
and sparse-llvm somehow misuse them. I don't know.
However, this functionality is only used to create the alloca
instructions used to simulate the phi-nodes.
So, fix this crash by using real phi instructions for the phi-nodes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A warning is given for K&R parameters without type declaration
and these parameters are given an implicit type of int to
avoid several problems with false errors in the next stages.
However, this is only done for K&R functions with the optional
parameter type declarations. If the parameters has no type
declaration at all, no diagnostic is given and the type is left
as incomplete. In consequence, a function defined with a typo like
'int foo(oid)' instead of 'int foo(void)' is left undetected
(even with -Wold-style-definition and -Wstrict-prototypes enabled).
Fix this by:
1) adding the type check to declare_argument() so that
all parameters have a real type.
2) downgrade the diagnostic to a warning for K&R functions.
Fixes: 6f7aa5e84dacec8e27a8d70090bba26a1a1276de
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the address of an inline function is taken, a definition
for this function must be emitted.
However, sparse only do this if this inline function is defined
before it is used.
So add a testcase for this.
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>
|
|
* essential OP_ADD & OP_SUB simplifications
|
|
The patterns used here were based on looser semantic for OP_{SEXT,TRUNC}.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* teach sparse about -funsigned-bitfields
* let plain bitfields default to signed
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
