| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
* Support LLVM-15 and later
|
|
LLVM 15 switched to opaque pointers by default and no longer supports typed pointers.
Remove deprecated LLVM calls and update test.
Original-patch-by: Vladimir Petko <vladimir.petko@canonical.com>
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
Grep (or maybe only some recent versions) complains when using the (wrong)
'\\t' pattern.
This pattern was used only once to check if the following pattern was at
the beginning of an instruction.
Prefer to use the more explicit '^.' pattern, already used in other tests.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The infinite loop is triggered by some fairly simple code on Zephyr and is
caused by some exchange of pseudos done without checking the canonical order.
Fix this by adding the check for the canonical order.
Also use can_move_to() instead of the simpler one_use() to check the dominance
of the moved pseudos.
Link: https://github.com/zephyrproject-rtos/zephyr/issues/63417
Link: https://lore.kernel.org/linux-sparse/AD16C022-C5F3-4DA2-A1A0-775E4C95A7A1@intel.com/
Reported-by: Marc Herbert <marc.herbert@intel.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The kernel has recently started using the __cleanup__ attribute. Save
a pointer to cleanup function.
Signed-off-by: Dan Carpenter <dan.carpenter@linaro.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix "unreplaced" warnings caused by using typeof() on inline functions
* cleanup related to inlining of variadic functions
|
|
Inlining of variadic functions needs some special cases.
Add some testcases for this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, sparse do all its inlining at the tree level, during
constant expansion. To not mix-up the evaluation of the original
function body in case the address of an inline function is taken or
when the function can't otherwise be inlined, the statements and
symbols lists of inline functions are kept in separated fields.
Then, if the original body must be evaluated it must first be
'uninlined' to have a copy in the usual fields.
This make sense when dealing with the definition of the function.
But, when using typeof() on functions, the resulting type doesn't
refer to this definition, it's just a copy of the type and only
of the type. There shouldn't be any reasons to uninline anything.
However, the distinction between 'full function' and 'type only'
is not made during evaluation and the uninlining attempt produce
a lot of "warning: unreplaced symbol '...'" because of the lack
of a corresponding definition.
Fix this by not doing the uninlining if the symbol lack a definition.
Note: It would maybe be more appropriate for EXPR_TYPE to use
a stripped-own version of evaluate_symbol() doing only the
examination of the return and argument types, bypassing the
attempt to uninline the body and evaluate the initializer and
the statements since there is none of those for an EXPR_TYPE.
Link: https://lore.kernel.org/all/202206191726.wq70mbMK-lkp@intel.com
Reported-by: kernel test robot <lkp@intel.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Sparse do inlining very early, during expansion, just after (type)
evaluation and before IR linearization, and is done even if some
errors have been found. This means that the inlining must be robust
against erroneous code.
However, during inlining, a cast expression is always dereferenced and
a crash will occur if not valid (in which case it should be null).
Fix this by checking for null cast expressions and directly returning
NULL, like done for the inlining of the other invalid expressions.
Link: https://lore.kernel.org/r/e42698a9-494c-619f-ac16-8ffe2c87e04e@intel.com
Reported-by: kernel test robot <lkp@intel.com>
Reported-by: Yafang Shao <laoar.shao@gmail.com>
Reported-by: Yujie Liu <yujie.liu@intel.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix zero/sign extension of integer character constants
* handle clang's option "-meabi gnu"
* fix infinite loop when expanding __builtin_object_size() with self-init vars
|
|
An integer character constant has type 'int' but, subtly enough,
its value is the one of a 'char' converted to an 'int'.
So, do this conversion.
Also set the type of wide character constants from 'long' to 'wchar_t'.
Link: https://lore.kernel.org/r/20210927130253.GH2083@kadam
Reported-by: Dan Carpenter <dan.carpenter@oracle.com>
Reported-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
expand_object_size(), used to expand __builtin_object_size(),
recursively try to get the parent initializer. This fails miserably
by looping endlessly when the object is a self-initialized variable.
For the moment, fix this in the most obvious way: stop the recursion
and do not expand such variables.
Note: I wouldn't be surprised if these self-initialized variables create
other problems elsewhere. Maybe we should remove their initializer
and somehow mark them as "do not warn about -Wuninitialized"
(well, there is no such warnings *yet*).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Commit 0d6bb7e1 ("handle more graciously labels with no statement",
2020-10-26) allowed a label to appear just before the closing brace
of a compound statement. This is not valid C (which would require
at least a null statement). Similarly, a case label is also not
allowed to appear just before a closing brace.
So, extend the solution of commit 0d6bb7e1 to issue a warning for
case labels and 'insert' a null statement.
Note that the next C standard (C23 ?) will allow even more freedom
in the placement of labels (see N2508 [1]) and make this placement
(along with others) legal C.
[1] https://www9.open-std.org/JTC1/SC22/WG14/www/docs/n2508.pdf
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
commit a69f8d70 ("ptrlist: use ptr_list_nth() instead of linearize_ptr_\
list()", 2021-02-14) replaced a call to a local helper with a more generic
ptr_list function. The local function, argument(), was used to retrieve
the 'argno' argument to a function call, counting the arguments from one.
This call was replaced by the generic ptr_list_nth() function, which
accessed the ptr_list counting from zero. The 'argno' passed to the call to
argument() was 3 (the byte count), which when passed to ptr_list_nth()
was attempting to access the 4th (non-existent) argument. (The resulting
null pointer was then passed to check_byte_count() function, which had
an null-pointer check and so did not dereference the null pointer). This
effectively disabled the memcpy-max-count check.
In order to fix the check, change the 'argno' of 3 to the 'index' of 2.
Also, add a simple regression test.
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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))
|
|
The current code will simplify away some casts at evaluation time
but doesn't take in account some special cases:
* (bool)~<int> is not equivalent to ~(bool)<int> (anything not all 0 or 1)
* (float)~<int> is not equivalent to ~(float)<int> which doesn't make sense.
* (int)(float)<int> is not a no-op if the (float) overflows
This kind of simplification is better done on the IR where the different
kind of casts correspond to distinct instructions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The goal is double:
1) be able to do the NOT operation on the smaller type
2) more importantly, give the opportunity to the TRUNC to
cancel with a previous ZEXT if there is one.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Such compares with a signed value are relatively common and can be
easily be simplified into a single unsigned compare. So, do it.
Note: This simplification triggers only 27 times in a x86-64 defconfig
kernel. I expected more but I suppose it's because most checks
aren't done against a constant or are done with unsigned values.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, signed compares against a constant are canonicalized
toward the smallest possible constant. So, the following
canonicalization are done:
x < 256 --> x <= 255
x < -2047 --> x <= -2048
This has two advantages:
1) it maximalizes the number of constants possible for a given bit size.
2) it allows to remove all < and all >=
But it has also a serious disadvantages: a simple comparison against
zero, like:
x >= 0
is canonicalized into:
x > -1
Which can be more costly for some architectures if translated as such ,
is also less readable than the version using 0 and is also sometimes
quite more complicated to match in some simplification patterns.
So, canonicalize it using 'towards 0' / using the smallest constant
in absolute value.
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.
|
|
and remove one that didn't made much sense.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* memops: kill more dead stores
|
|
* add a symbolic checker
|
|
A lot of simplifications are only valid when their variables
satisfy to some conditions (like "is within a given range" or
"is a power of two").
So, allow to add such pre-conditions via new _assume() statements.
Internally, all such preconditions are ANDed together and what is
checked is they imply the assertions:
AND(pre-condition) implies assertion 1
...
Note: IIUC, it seems that boolector has a native mechanism for such
things but I'm not sure if t can be used here.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Since, the symbolic checker check expressions at the ... symbolic
level, this can be used to check if two expressions are equivalent
but not if this equivalence is effectively used.
So, add a new assertion (this time not at the symbolic level) to
check if an expression which is expected to simplify to a constant
is effectively simplified to this constant.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
With the SMT solver used here, by default, once an expression is
checked it's kinda consumed by the process and can't be reused
anymore for another check.
So, enable the incremental mode: it allows to call boolecter_sat()
several times.
Note: Another would be, of course, to just AND together all assertions
and just check this but then we would lost the finer grained
diagnostic in case of failure.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Testing the equivalence of two sub-expressions can be done with
with a single assertion like __assert(A == B).
However, in some cases, Sparse can use the equality to simplify
the whole expression although it's unable to simplify one of
the two sub-expressions into the other.
So, add a new assertion, __assert_eq(), testing the equality of
the two expressions given in argument independently of each other.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some instruction simplifications can be quite tricky and thus easy to
get wrong. Often, they also are hard to test (for example, you can
test it with a few input values but of course not all combinations).
I'm used to validate some of these with an independent tool
(Alive cfr. [1], [2]) which is quite neat but has some issues:
1) This tool doesn't work with Sparse's IR or C source but it needs to
have the tests written in its own language (very close to LLVM's IR).
So it can be used to test if the logic of a simplification but
not if implemented correctly.
2) This tool isn't maintained anymore (has some bugs too) and it's
successor (Alive2 [3]) is not quite as handy to me (I miss the
pre-conditions a lot).
So, this patch implement the same idea but fully integrated with
Sparse. This mean that you can write a test in C, let Sparse process
and simplify it and then directly validate it and not only for
a few values but symbolically, for all possible values.
Note: Of course, this is not totally stand-alone and depends on
an external library for the solver (Boolector, see [4], [5]).
Note: Currently, it's just a proof of concept and, except the
included tests, it's only very slightly tested (and untested
with anything more complex than a few instructions).
[1] https://blog.regehr.org/archives/1170
[2] https://www.cs.utah.edu/~regehr/papers/pldi15.pdf
[3] https://blog.regehr.org/archives/1722
[4] https://boolector.github.io/
[5] https://boolector.github.io/papers/BrummayerBiere-TACAS09.pdf
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
match_attribute() will crash when the token has the same identifier
as one of the attributes but is not an attribute. In this case,
the corresponding symbol_op will be null but this is not checked.
This seems to happen only with old-style declarations.
Fix this by adding the missing null-check.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The current implementation of remove_merging_phisrc() can't work correctly
when these phi-sources belong to a basic block with several children
to the same target basic block (this happens commonly with OP_SWITCH).
Fix this by directly scanning the source basic block for the presence
of any phi-source. Once identified, the processing is kept unchanged:
remove these phi-sources if a sibling phi-source will 'overwrite' them
in the target block.
Fixes: 2fdaca9e7175e62f08d259f5cb3ec7c9725bba68
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* testsuite: add option '-r' to 'test-suite format'
|
|
In a phi-node,pseudo_list_size() can't be used for counting its arguments
because VOIDs must be ignored.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A store is called 'redundant' when the corresponding location
already contains the value that will be stored.
This patch removes such stores in the case where the memops
which make them redundant is in the same basic block.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
kill_dominated_stores() identify and remove dead stores
(stores unneeded because the same location is overwritten later
by another store) only when both stores are in the same basic block.
Slightly improve this by also handling the case when the dead store
is in a parent BB of the "live" store.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Because laziness is a virtue, add an option '-r' to the 'format'
subcommand of the testsuite to quickly create a test template for
linearized code which should just return 1.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Like for CBR-BR conversion, when a target BB containing one or several
phi-nodes is removed from an OP_SWITCH, the corresponding phi-source
must be removed from the phi-node.
However this is not done yet.
Changing this by adding some code to convert_to_jump() to remove all
phi-sources from the discarded targets if the converted instruction
is an OP_SWITCH.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If a conditional branch has identical targets, it should be
converted to a simple jump.
This is done but using its own code.
Change this by using the existing convert_to_jump() instead.
This also allows any redundant phi-sources to be removed.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When a parent is removed from a BB containing one or several phi-nodes,
the corresponding phi-sources must be removed from the phi-node.
However this is not done and consequentially:
* it becomes impossibly to correctly reason about the flow of values
through these phi-nodes.
* simplifications are missed (e.g. if-conversion).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
and same for its dual: ((x & M) != M) --> ((x & M) == 0)
Beside the canonicalization itself, these simplifications are
useful because the compare against 0 can often be further
simplified (for example when it is used by OP_CBR or OP_SELECT).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix SSA conversion of mismatched memops
* simplify CMP(AND(x,M), C) and CMP(OR(x,M), C)
|
|
MARK_CURRENT_DELETED() was added for the case(s) where an element
must be removed from the list but the address of the other elements
must not be changed. In this case of effectively removing the
element from it list, the element is 'marked' as deleted in the list
and the list walking macros will later take this in account.
However, this is never needed for multi-jumps.
So, use the usual DELETE_CURRENT_PTR() for them.
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>
|
|
These tests are written by testing if the comparisons are equal
to their expected value: 0 or 1. So, a compare of a compare
but such compares of compare have their own simplification
which defeats what's tested here.
So, rewrite the test to avoid such compares of compare.
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>
|
|
Packed bitfields are incompatible with the SSA conversion
which works on the assumption that memory operations are done
on the whole symbol.
So, directly exclude packed bitfields from the SSA conversion.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The SSA conversion is incorrect when the size or offset of the
memory operations doesn't match. It shouldn't be done at all.
So, add a few testcases for this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix the type in the assignment of 0 to a restricted variable
|
|
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* expand __builtin_object_size()
|
|
__builtin_object_size() is one of these builtins that must be
somehow expanded because it can't possibly be implemented at
runtime. It's used by the kernel's copy_{to,from}_user() and
the 'fortified' string functions, as well as by userspace's
'checked string/memory functions' like __builtin___memcpy_chk().
So, use the normal builtin expansion interface for this one too.
This gets rid of 2/3 of them when used on the kernel and shaves
~0.5% of the total IR code (with x86's defconfig).
Notes:
1) What is covered is an object symbol, with an optional designator
of arbitrary complexity, ignoring casts and accessed via
an optional chain of simple dereferences. Maybe some access
path need to be added.
2) Anything with dynamic value is currently considered either as
unknown (VLAs, variables or parameters) or left for a later
stage (any function calls, including functions known to allocate
memory given that attribute alloc_size() is not yet supported).
3) It's not totally clear to me when to give up (and thus return
'size unknown') and when things can or must be left to the
simplification phase. This matters because __builtin_object_size()
is relatively often used with __builtin_constant_p().
4) Currently, only type 0 is really supported. Given the way
designators are evaluated and expanded (information is lost because
the expressions are overwritten), to support the other types, the
expansion of __builtin_object_size() should be done during
evaluation itself, much like it's done for sizeof() and
offsetof().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Assignment to restricted variables are severely ... restricted.
Nevertheless, one value is always fine because it has always
the same bit representation: 0.
So, 0 is accepted unconditionally but this creates a problem
because the type of this 0 needs to be adjusted. Otherwise
0 (int) is assigned as-is even on restricted variable with a
different bit-length.
Fix this by casting the value to the target type before accepting it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The function dominates() needs to know if an OP_ASM instruction
may modify.
Use the information now available in the instruction to return
the answer.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Memory simplification is done with the help of the function
dominates() which determine when memory instructions interfere.
This function handles OP_CALLs, OP_LOADs and OP_STOREs but
memory can also be changed via OP_ASMs.
Add a testcase showing this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The addresses needed by memory output operands are linearized
(and placed) after the ASM instruction needing them.
So, split add_asm_output() in 2 parts: one generating only the
addresses for memory operands and called before issuing the body,
and another one doing the usual copy of (non-memory) output operands
back into their corresponding variables.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The addresses needed by memory output operands are linearized
(and placed) after the ASM instruction needing them.
So, add a test case for this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix add_join_conditional() when one of the alternative is VOID
|
|
add_join_conditional()'s job is to take the 2 alternatives
of the conditional, make a phi-node from them and return
the corresponding pseudo but if one of the alternatives
is not available it's useless to create a phi-node and
the other alternative can then directly be returned.
The problem is that in this later case, the pseudo directly
returned is the PSEUDO_PHI of the corresponding phi-source.
This gives erroneous code like, for example:
phisrc.32 %phi1 <- $0
ret.32 %phi1
instead of:
ret.32 $0
since the %ph1 should only be used by a phi-node instruction.
Fix this by returning phi-source's operand instead.
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
* 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>
|
|
* 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>
|
|
'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>
|
|
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>
|
|
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>
|
|
* 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}
|
|
* 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>
|
|
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>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
* simplify & canonicalize compares
|
|
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>
|
|
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 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 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>
|
|
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>
|
|
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>
|
|
'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
|
|
* simplify and canonicalize unsigned compares
* basic unop simplifications
|
|
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>
|
|
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>
|
|
Add a few testcases for the simplification of unary operations.
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>
|
|
* 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>
|
|
Not really a simplification in itself but it make some other
simplification a little easier (already because there is one
argument less to be matched).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Do this simplification once for all associative binops.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
At expansion phase, when simplified, all constants are truncated
to the size of the operations that generate them.
This should be done during simplification too because:
*) if some constants are sometimes truncated and sometimes
sign-extended, CSE will miss some opportunities.
*) it's not possible to sign-extend them because it's not
always known if the constant is used in a signed context or not.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add some testcases about basic simplifications of additions
and subtractions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix and complete the evaluation of atomic builtins
|
|
The first argument is supposed to be a pointer to a bool, but
of course, a volatile qualified pointer should be accepted too.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Reuse the generic method for all these builtins.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
|
|
If the evaluation of the return expression failed a following test
can dereference the pointer holding the expression's type ...
which is null. Bad.
Fix this by adding the missing null pointer test.
Fixes: 3bc32d46494c404df7905fceaca9156830ff97f1
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Built-in functions are meant to be expanded by the compiler. As such,
they don't have an address.
So, issue an error when trying take the address of a built-in function.
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 warning about the nesting of flexible array members is
given with the location of the outer struct or union but
that is not very interesting. What is needed is the location
of the member causing this nesting.
So, fix the warning message to use the member's location.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
|
|
|
|
There is a common pattern on how to allocate memory for a flexible-size
structure, e.g.
union {
struct flex f; /* Structure that contains a flexible array. */
char buf[MAX_SIZE]; /* Memory buffer for structure 'flex' and
its flexible array. */
};
There is another example of such thing in CMSG manpage with the
alignment purposes:
union { /* Ancillary data buffer, wrapped in a union
in order to ensure it is suitably aligned */
char buf[CMSG_SPACE(sizeof(myfds))];
struct cmsghdr align;
} u;
Such unions could form an array in case user wants multiple
instances of them. For example, if you want receive up to
32 network packets via recvmmsg(), you will need 32 unions like 'u'.
Open vSwitch does exactly that and fails the check.
So, add a new option, -W[no-]flex-array-union, to enable or disable
any warning concerning flexible arrays and unions. This option needs
at least one of -Wflex-array-{array,nested,union} to be enabled in
order to have any effect.
Signed-off-by: Ilya Maximets <i.maximets@ovn.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The current implementation of the usual conversion doesn't handle
correctly the case of 'long' + 'unsigned int' on a 32-bit arch.
The resulting type is 'unsigned int' instead of 'unsigned long'.
Fix this by following closely the C99's wording.
This now gives the expected result for C89 & C99 on 32 & 64-bit archs
(as tested with the GCC testsuite).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The pointer to bool conversion used an indirect intermediate
conversion to an int because the pointer was compared to 0
and not to a null pointer. The final result is the same
but the intermediate conversion generated an unneeded OP_PTRTOU
instruction which made some tests to fail.
Fix this by directly comparing to a null pointer of the same
type as the type to convert.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This test was for a failed experience. Remove it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
A structure or a union containing another aggregate type containing,
possibly recursively, a flexible array is quite error prone and make
not much sense. So, add an option -Wflexible-array-nested to warn
on such usage.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
An array of some aggregate type containing, possibly recursively,
a flexible array is pretty non-sensical. So, add an option
-Wflexible-array-array to warn on such usage.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Using sizeof() on a structure containing a flexible array
will ignore the 'flexible' part. This is maybe what is expected
but maybe not, so add an option -Wflexible-array-sizeof to
warn on such usage.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
