| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
C has only positive constants: -1 is really an expression,
the unary '-' operator applied to the constant 1. '-1' as
a constant value only exists after the expansion of constant
expressions.
This is rather unfortunate since it inhibits easy testing
of such constants in the evaluation phase, like here for
restricted_value().
So, expand expressions like +CTE, -CTE or ~CTE before
calling restricted_value().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When bitwise types were added [1] the signedness modifiers
were removed from them. More exactly, it was MOD_SPECIFIER
which was removed. I suppose this was done because then
MOD_SPECIFIER contained the signedness bits but also MOD_CHAR,
MOD_LONG, ... and those had to be removed.
But currently MOD_SPECIFIER contains only MOD_SIGNEDNESS
and the signedness info can be useful for bitwise types too.
So, do not removed anymore MOD_SPECIFIER from the bitwise
types' modifiers.
[1] commit 032f492af0ac ("[PATCH] __attribute__((bitwise))")
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, bitwise types are restricted to bitwise operations
(&, |, ^ and ~) as well as equality comparisons.
This patch makes the others comparisons valid for bitwise types
too.
Warning: This change make sense in the context of [1] but
doesn't make sense for the 'main' bitwise types:
__be32 and friends.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, the only value bitwise types can act on is 0
because the this value is anyway invariant for all bitwise
operations and endianness conversions.
But, a bit-pattern of all ones has the same properties and
is also very often used.
So, accept all ones as a valid value for bitwise operations.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently bitwise types only support bitwise operations
(&, |, ^ and ~) and the constant 0 (since this value is
invariant for all bitwise operations and endianness conversion).
But the incoming series will relax this a little bit.
So, add a few testcases for it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In kernel's arch/mips/Makefile the whole content of gcc's -dM is used
for CHECKFLAGS. This conflict with some macros also defined internally:
builtin:1:9: warning: preprocessor token __ATOMIC_ACQUIRE redefined
builtin:0:0: this was the original definition
Fix this by using a weak define for these macros.
Reported-by: Randy Dunlap <rdunlap@infradead.org>
Reported-by: kernel test robot <lkp@intel.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* cgcc: do not die on '-x assembler'
* fix crash when inlining casts of erroneous expressions
- allow show_token() on TOKEN_ZERO_IDENT
|
|
TOKEN_ZERO_IDENTs are created during the evaluation of pre-processor
expressions but which otherwise are normal idents and were first tokenized
as TOKEN_IDENTs.
As such, they could perfectly be displayed by show_token() but are not.
So, in error messages they are displayed as "unhandled token type '4'",
which is not at all informative.
Fix this by letting show_token() process them like usual TOKEN_IDENTs.
Idem for quote_token().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Acked-by: Linus Torvalds <torvalds@linux-foundation.org>
|
|
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>
|
|
Currently cgcc will die if the option '-x' is used with any argument
other than 'c'.
It makes sense since sparse can only handle C files but it can be
useful in a project to simply use something like:
make CC=cgcc
So, instead of die()ing, avoid calling sparse if such '-x' option
is used, like already done by default for non .c files.
Original-patch-by: Tom Rix <trix@redhat.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* riscv: small improvements of '-march' parsing
|
|
"g" goes along with the base ISA, but it was being treated as an
extension. This allows for all sorts of odd ISA strings to be accepted
by sparse, things like "rv32ig" or "rv32gg". We're still allowing
some oddities, like "rv32ga", but this one was easy to catch.
Signed-off-by: Palmer Dabbelt <palmer@rivosinc.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This made sense when we die()d on unknown ISA extensions, but now that
we're just warning it's actually a bit detrimental: users won't see that
their unimplemented ISA extensions are silently having the wrong
definitions set, which may cause hard to debug failures.
Signed-off-by: Palmer Dabbelt <palmer@rivosinc.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
GCC's semantics for "-march=X -march=Y" are that Y entirely overrides X,
but sparse takes the union of these two ISA strings. This fixes the
behavior by setting, instead of oring, the flags whenever a base ISA is
encountered. RISC-V ISA strings can only have a single base ISA, it's
not like x86 where the 64-bit ISA is an extension of the 32-bit ISA.
[Luc Van Oostenryck: reset the flags at the start of the parsing loop]
Signed-off-by: Palmer Dabbelt <palmer@rivosinc.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Parsing RISC-V ISA strings is extremely complicated: there are many
extensions, versions of extensions, versions of the ISA string rules,
and a bunch of unwritten rules to deal with all the bugs that fell out
of that complexity.
Rather than die()ing when the ISA string parsing fails, just stop parsing
where we get lost and emit a warning. Changes tend to end up at
the end of the ISA string, so that's probably going to work (and if
it doesn't there's a warning to true and clue folks in).
This does have the oddity in that "-Wsparse-error" is ignored for this
warning but this option was never meant to be used at this stage of
the processing..
[Luc Van Oostenryck: drop handling of "-Wsparse-error"]
Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
Based-on-patch-by: Palmer Dabbelt <palmer@rivosinc.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* small improvements to cast_value()
|
|
The last two arguments of cast_value() are the old expression and
the oldtype which suggest that this oldtype can be distinct from the
type of the old expression.
But this is not the case because internally the type used to retrieve
the value of the expression is the type of the expression itself (old->ctype)
the type which is used and the two types must be the same (or at least
be equivalent).
So, remove the error-prone last argument and always us the type of the
expression itself.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The first two arguments of cast_value() are the new expression and the
type wanted for it. This type is then used to calculate the new value.
But the type of the expression must be assigned separately (usually
after the cast because the old and the new expression can refer to
the same object).
To avoid any possible inconsistencies, assign the new type during the
casting itself.
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>
|
|
* cgcc: add Xtensa support
|
|
Add support for the Xtensa architecture.
Signed-off-by: Guennadi Liakhovetski <guennadi.liakhovetski@linux.intel.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Clang has an option "-meabi <arg>" which is used by the kernel for ARMv7.
This kind of option, taking a argument without a separating '=', can't
be ignored like most other options and must this be special-cased.
So, add the special case for this option and consume the argument if it's
one of the valid one.
Link: https://lore.kernel.org/r/20220331110118.vr4miyyytqlssjoi@pengutronix.de
Reported-by: Marc Kleine-Budde <mkl@pengutronix.de>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* riscv: add the Zicsr extension
* riscv: add the Zifencei extension
|
|
Recent versions of binutils default to an ISA spec version that doesn't
include Zifencei as part of I, so Linux has recently started passing
this in -march.
[ Luc Van Oostenryck: move this patch at the start of the series ]
Signed-off-by: Palmer Dabbelt <palmer@rivosinc.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Recent versions of binutils default to an ISA spec version that doesn't
include Zicsr as part of I, so Linux has recently started passing this
in -march.
[ Luc Van Oostenryck: move this patch at the start of the series ]
Signed-off-by: Palmer Dabbelt <palmer@rivosinc.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Subtracting (char *)0 is undefined behavior. Newer compilers warn
about this unless it is done in system headers.
Signed-off-by: Richard Palethorpe <rpalethorpe@suse.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Bernhard Voelker noticed that the date in the release notes
is one year off. Fix this.
Reported-by: Bernhard Voelker <mail@bernhard-voelker.de>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* semind: Index more symbols
For indexing purposes, macros definitions and typedefs are added to the
semind database. Functions that are not used in the code are also indexed.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* fix regression disabling the 'memcpy-max-count' check.
* warn about a 'case label' on empty statement
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
For indexing purposes, it is useful to see type definitions.
$ semind search __kernel_ulong_t
(def) include/uapi/asm-generic/posix_types.h 16 23 typedef unsigned long __kernel_ulong_t;
Signed-off-by: Alexey Gladkov <gladkov.alexey@gmail.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add the ability to dissect to see macro definitions. The patch does not
add full support for the usage of macros, but only their definitions.
Signed-off-by: Alexey Gladkov <gladkov.alexey@gmail.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently dissect sees only used symbols. For indexing purposes, it is
useful to see all declared symbols.
$ nl -s\ -w2 ./z.c
1 struct foo {
2 int member;
3 };
4 #ifdef OPT
5 static void func1(void) {
6 struct foo *x;
7 return 0;
8 }
9 #endif
10 static inline void func2(void) { return; }
11 void func(void) { return; }
$ ./test-dissect ./z.c
FILE: ./z.c
11:6 def f func void ( ... )
$ ./test-dissect --param=dissect-show-all-symbols ./z.c
FILE: ./z.c
1:8 def s foo struct foo
2:13 def m foo.member int
10:20 def f func2 void ( ... )
11:6 def f func void ( ... )
Signed-off-by: Alexey Gladkov <gladkov.alexey@gmail.com>
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>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* small fixes for the symbolic checker
|
|
Casts were using the target type for their operands.
Fix this by using the new helper mkivar() for them.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Most instructions have one associated type, the 'target type'.
Some, like compares, have another one too, the 'input type'.
So, when creating a bitvector from an instruction, we need to specify
the type in some way.
So, create an helper for both cases: mktvar() and mkivar().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
in sparse, constants (PSEUDO_VALs) are not typed, so the same pseudo
can be used to represent 1-bit 0, 8-bit 0, 16-bit 0, ...
That's incompatible with the bit vectors used here, so we can't associate
a PSEUDO_VAL with its own bitvector like it's done for PSEUDO_REGs.
A fresh one is needed for each occurrence (we could use a small table
but won't bother).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some instructions have no effects and so can just be ignored here.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When reporting an unsupported instruction, display the instruction
together with the diagnostic message.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Since commit 226b62bc2ee4 ("eval_insn: give an explicit type to compare's operands")
it's needed to set the operands' type of every compare instructions but
it was missing in this case where a select is transformed into a compare.
So, add the missing type.
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>
|
|
It's not 100% clear than this is indeed a simplification but:
1) from a pure instruction count point of view, it doesn't make
things worst
2) in most place where it applies, the masking is made redundant
and is thus eliminated
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>
|
|
Add a small helper to test if a pseudo is a positive (= non-negative)
constant (for a given bitsize).
It's meant to make some conditions more readable.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
In rewrite_load_instruction(), if the load instruction is converted
into a phi-node, its address is then no more used and must be removed.
However, this is only done when this address is not a symbol.
This was explicitly done in the following commit because of the problem
of removing an element from the usage list while walking this list:
602f6b6c0d41 ("Leave symbol pseudo usage intact when doing phi-node conversion.")
But currently rewrite_load_instruction() is only used during memops
simplification where the usage list is not walked.
So, kill the address' usage unconditionally.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The loop in rewrite_load_instruction() uses first_pseudo() to not have
to special case the first element.
But this slightly complicates further changes.
So, simply use a null-or-no-null test inside the loop to identify
this first element.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In rewrite_load_instruction(), when testing if all phi-sources are
the same, the candidate is given an identifier if it hasn't one already.
But doing this inside this loop is strange:
* the pseudo may, at the end, not be selected but is changed anyway
* the identifier should be given either when the phi-source is created
or at the end of the loop if selected.
So, do not change the identifier inside the selection loop.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The comment above rewrite_load_instruction(), about comparing phi-lists
for equality, was (most probably) written when there was some intention
to do CSE on phi-nodes or phi-sources.
However, such CSE is currently not an objective at all.
So, remove this comment.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
find_dominating_parents() has an argument 'generation' used
to check if a BB has already been visited.
But this argument is not needed since this generation is also
stored in the field ::generation of the current BB.
So, remove this argument.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The first argument of dominates(), 'pseudo', is simply the 'src'
pseudo of it's second argument, the load or store instruction.
It's thus not needed to give it in a separate argument.
So, remove this redundant argument, since it makes things
slightly clearer.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* memops: kill more dead stores
|
|
* linear: only allocate call instructions when needed
|
|
* TODO: add some notes about pseudos being typeless
|
|
Pseudos are untyped. It's usually OK because their type can nevertheless
be retrieved in a simple way. But it also complicates things and
worse in some cases the type is completely lost.
Tell a bit more about it in the TODO file.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* add a symbolic checker
|
|
It can be useful to use the same testcase for the symbolic checker
and normal sparse (or test-linearize) processing.
So, there must be a mean to somehow ignore the assertions used
for the symbolic checker when it's not used (since these are otherwise
not known to sparse).
Resolve this by adding a predefine, __SYMBOLIC_CHECKER__, to the
symbolic checker.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
The current .gitignore specifies that the generated programs
must be ignored. Good.
However, this is done by just specifying the name of the program
which has the effect of having any files or directories with the
same name to be ignored too. This is not intended.
Fix this using the pattern '/<name>' instead so that they match
in the root folder.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This can be used to define some generic (polymorphic) builtin
with a signature like:
<name>(int)
<name>(T, T)
<name>(int, T)
<name>(int, T, long, T, ... T)
where T is some integer type which will be instantiated at each call.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When linearizing a call expression, the corresponding instruction is
allocated very early:
- before the valdity are done
- before the linearization is handled to one of the specific methods
In both case it means that the allocated instruction is not used.
Fix this by doing the allocation only once it's needed.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Make declare_builtins() extern so that it can be used from other files.
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'
|
|
Transformations made by try_to_simplify_bb() are invalid if
there isn't a one-to-one correspondence between the BB's parents
and the phi-sources of the phi-node(s) in the BB.
This correspondence is currently checked by checking if the number
of phi-sources and the number of parent are equal, but this is
only an approximation.
Change this check into an exact one, using the fact that BBs in
the parent list and phi-sources in the phi_list are in the same order.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
so they shouldn't be killed.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Move the test/replace part of the store simplification in a
separate function so that it can be reused.
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>
|
|
add_instruction_to_end() and insert_last_instruction() do exactly
the same thing but with the arguments in the opposite order.
So, replace add_instruction_to_end() by insert_last_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
It's relatively common to have to add an instruction at the end of a BB.
More exactly, at the end but just before the terminator instruction.
What is done for this is:
1) remove the terminator
2) add the new instruction
3) add the terminator back
This is a bit tedious, need to declare a temporary variable for the
terminator and, more generally, it's low-level details.
So, add an helper for doing this: insert_last_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
When a parent is removed from a BB containing one or several phi-nodes,
the corresponding phi-sources become irrelevant and need to be removed
from the phi-nodes.
Add an helper for doing this: remove_phisources().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Since the existing branch is now reused, nothing is inserted anymore.
So, rename this function to the more explanatory: convert_to_jump().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
insert_branch() modifies the CFG and the usage of pseudos so these
changes must be, in a way or another, notify to the upper layers.
Currently this is done by setting 'repeat_phase' in the function
itself.
Let this function to also report the changes via its return value
since this is usually useful for the caller to know and tend to
leaner code too.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Now that insert_branch() doesn't need to allocate a new instruction,
there is no more reasons to have it defined in linearize.c
So move it to flow.c which is more concerned with CFG changes.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
insert_branch() changes a switch or a conditional branch into a jump.
This is implemented by deleting the old instruction and allocating
the new one. This is not needed here since no reference to the
old instruction is kept.
So, simply reuse the terminating instruction and change it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Fold remove_parent() into its only user, insert_branch(), since it's
now just a wrapper around remove_bb_from_list().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
remove_parent() is a simple wrapper around remove_bb_from_list()
which also set REPEAT_CFG_CLEANUP if the list becomes empty.
But its only user, insert_branch(), doesn't need REPEAT_CFG_CLEANUP
to be set.
So, simplify this wrapper by keeping only the call to remove_bb_from_list().
|
|
insert_branch()'s first argument must be the BB of the instruction
given in the second argument.
So, remove it from the argument and simply use insn->bb instead.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The commit 7cd2ce022575 ("simplify CBR-CBR on the same condition")
added a generalization of the existing CBR-CBR simplification
using the dominance tree.
The problem is that as soon as a change is made to the CFG, the
dominance tree become invalid and should be rebuilt (which is costly
to do for each CFG changes) or updated (which is quite complex).
So, for now, revert this commit.
Reverts: 7cd2ce022575fbd383bb39b54f1e0fa402919da2.
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>
|
|
It's not clear if this is an optimization or not.
So, remove it.
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 implementation of a 'sparse set without initialization' was
somehow needed during the initial design but it's not needed anymore.
So, remove the implementation and replace its use by the usual
bb->generation mechanism.
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>
|
|
* phi-sources can only have a single user (or none)
|
|
* ptrlist: small API improvements
These improvements will be used by various incoming series.
Thanks to Ramsay Jones for finding a bunch of typos and
suggesting some improved phrasing.
-- Luc
|
|
Currently, OP_PHISOURCES have a list as member, 'phi_users',
that should link to all phi-nodes using them but:
*) phi-sources are never shared between phi-nodes
*) this list is useless because it's only created during liveness
and not used after.
So, replace the list by a simple pointer to hold the unique phi-node
using it and keep this link updated during all its lifetime.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Acked-by: Linus Torvalds <torvalds@linux-foundation.org>
|
|
The function linearize_ptr_list() is annoying to use because it
returns the number of elements put in the array. So, if you need
to know if the list contained the expected number of entries,
you need to allocate an array with one extra entry and check
that the return value is one less than this size.
So, change the function to return the total number of entries
in the list. In other words, the return value corresponds now to
the number of entries that could be copied if the size would be
unlimited, much like it's done for snprintf().
The number of entries effectively copied stays, of course,
limited by the size specified for the array.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The ptrlist API has a function to copy the elements of a ptrlist
into an array but it's not typed and thus needs a wrapper (or casts)
for each type it's used for. Also, 'linearize' is confusing since
this is unrelated to Sparse's linearization.
Simplify this by adding a generic (but type-safe) macro for this
with a more descriptive name: ptr_list_to_array()
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Sparse has a few extra checkers for some functions.
The one for memset has its own helper to retrieve its 3rd arguments.
Remove this helper and use the generic ptr_list_nth() instead.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Some algorithms need a stack or a working list from which the
last element can be removed. The ptrlist API has a function to do
this but it's not typed and thus needs a wrapper for each type
it's used for.
Simplify this by adding a generic (but type-safe) macro for this
while also giving it a nicer name: pop_ptr_list().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The name of the macro TYPEOF() is too generic and doesn't explain
that it only returns the type of the pointers stored in ptrlists.
So, change the name to something more explicit: PTRLIST_TYPE().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The macro TYPEOF() return the type of the addresses of the pointers
stored in the list. That's one level too much in general.
Change it to simply return the type of the stored pointers.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* slice: small reorg of OP_SLICE in preparation for some incoming changes
|
|
* pre-processing: strip leading "./" from include paths
|
|
* fix the type in the assignment of 0 to a restricted variable
|
|
An header file like 'header.h':
#pragma once
#include "./header.h"
doesn't work because:
1) both filenames are different, so it will be be included anyway
2) after that it will be included again under the name "././header.h"
and so on until it eventually fails with ENAMETOOLONG.
Prevent this by stripping leading "./"s in the paths.
This is not good enough for testing file equivalence by is enough to
avoid the loop.
Link: https://lore.kernel.org/r/CAHk-=wjFWZMVWTbvUMVxQqGKvGMC_BNrahCtTkpEjxoC0k-T=A@mail.gmail.com
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
|
|
When displaying an OP_SLICE, the width is shown but the size
of the source pseudo is useful too. So, display this size in
a similar manner to the unops.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
OP_SLICE's source's type is needed for some simplifications.
For example, in some cases it can be simplified into OP_TRUNC.
So, merge its representation with the one for unops which also
need the source's type.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
EXPR_SLICE::r_nrbits is necessarily equal to its type's bit size.
So remove this redundancy.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
OP_SLICE::len is necessarily equal to the result size.
So remove this redundancy.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Commits 34c57a7f ("asm-mem: does it clobber memory?", 2021-02-20) and
d6721b38 ("asm-mem: does it output to memory?", 2021-02-20) both add
a single bit bitfield to the 'struct asm' part of the union contained
within the 'struct instruction'. This causes the 'selfcheck' target
to issue several 'dubious one-bit signed bitfield' errors.
In order to suppress these errors, change the type of the bitfields to
an unsigned type.
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* expand __builtin_object_size()
|
|
* asm: output *memory* operands need their address as *input*
* asm: teach dominates() about OP_ASM
|
|
__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>
|
|
If an asm statement have a memory output operand, it modifies memory.
Since this information is needed during memops simplification,
add this info directly in the corresponding instruction,
avoiding the need to scan the output operands list each time.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
An asm statement can specify that it clobbers memory.
Add this info directly in the corresponding instruction, avoiding
the need to scan the clobber list each time.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
To prepare the handling of OP_ASM instructions, reorganize the
opcode tests to use a switch.
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 functions add_asm_input() and add_asm_output() are very similar.
So, factorize out the common part.
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>
|
|
The library operation on pointer list necessarily act on the untyped
version of the list. To use them with type checking, they must either
be wrapped in inline function using the desired type or be used via
some macro doing the type checking.
Do this later solution for ptr_list_nth_entry().
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>
|
|
* simplify and canonicalize signed compares
|
|
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>
|
