| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
|
|
* llvm: avoid trivial recursion in symbol_type()
* llvm: enable LLVM on arm64
|
|
Currently, all architectures but the i386/x86 ones are excluded
from the LLVM backend, mainly because the lack of testing.
Since I can test it now, allow arm64/aarch64 too.
Note: this patch is somehow incomplete because the layout is not set
but it's not clear what exactly the layout is needed for and at
least it allows to run the testsuite on this architecture.
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
* Support LLVM-15 and later
|
|
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
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>
|
|
So, add the corresponding flags.
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
So, add the corresponding flags.
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
These may be needed once the V extension is enabled.
So add them.
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
I've started hitting this in CI while testing Andy's vector enablement
series. I'm not entirely sure if there is more to do here, other than
squeezing in the duplicate of what has been done for other extensions.
Signed-off-by: Conor Dooley <conor.dooley@microchip.com>
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
In 2 places, we duplicate the storage for a string (with strdup) and we
also calculate its length via strlen(). Both operation are unneeded
as the length is already calculated in the struct string and the pointer
to the string data can be safely reused since Sparse will not modify or free it.
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
LLVM-14 still support LLVMBuildCall() and friends but deprecated them via
the attribute, so warnings are issued when compiling.
Suppress these warnings to keep builds clean.
Signed-off-by: Luc Van Oostenryck <lucvoo@kernel.org>
|
|
* make doc generation OK again on readthedocs
* suppress a warning in the testsuite
|
|
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>
|
|
Read the Docs now requires a config file in the project top directory.
So, here it is.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Newer versions of Sphinx don't support 'None' for 'language'.
So, set 'en' as language'.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Sphinx versions older than 1.7 don't need and don't support 'html_context'.
So, set 1.8 as the minimal version and remove 'html_context' from the config.
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 resulting string from snprintf, won't be nearly 64 bytes, but "buf"
is only 16 bytes long here. This causes FORTIFY_SOURCE to complain when
given the right options.
Signed-off-by: Jeff Layton <jlayton@kernel.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Current gcc options only support the little endian mode on Xtensa,
switch over to it.
Signed-off-by: Guennadi Liakhovetski <guennadi.liakhovetski@linux.intel.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This was recently added to binutils and with any luck will soon be in
Linux, without it sparse will fail when trying to build new kernels on
systems with new toolchains.
Signed-off-by: Palmer Dabbelt <palmer@rivosinc.com>
Tested-by: Conor Dooley <conor.dooley@microchip.com>
Tested-by: Geert Uytterhoeven <geert+renesas@glider.be>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This was recently added to binutils and with any luck will soon be in
Linux, without it sparse will fail when trying to build new kernels on
systems with new toolchains.
Signed-off-by: Palmer Dabbelt <palmer@rivosinc.com>
Tested-by: Conor Dooley <conor.dooley@microchip.com>
Tested-by: Geert Uytterhoeven <geert+renesas@glider.be>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
* teach Sparse about 'cleanup' attribute so that Smatch can handle it
|
|
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
|
|
We usually don't free allocated memory because it's not known
when the allocated objects aren't used anymore.
But here it's pretty obvious, so free this symbol list.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In inline_function(), the statement that will correspond to the
inlined code is allocated in the function declaration but then
it's checked if the function can be allocated or not.
This is not much memory and the checks should succeed most of the time
but it's clearer if the statement is allocated after the checks.
So, move the allocation after the checks.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
In inline_function(), we need to iterate over the parameters
and the (effective) arguments. An itermediate variable is used for
each: "name_list" and "arg_list".
These confuse me a lot (especially "name_list", "param_list" would
be much more OK) and are just used once.
So, avoid using an intermediate variable for these.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When inlining a function call, the arguments of this call must
somehow be assigned to the names used in the function definition.
This is done via a STMT_DECLARATION associated to the top
STMT_COMPOUND which now correspond to the inlined code.
This is perfectly fine for the normal case of non-variadic function
but when inlining a variadic function there is no corresponding name
to assign the non-fixed arguments to (such arguments must either be
not used at all or copied via __builtin_va_arg_pack()). What's then
happening is essentially that these variables are self-assigned.
Not Good.
This seems to be relatively harmless but is confusing.
So only put the fixed/named arguments in the declaration list.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
When inlining a variadic function the extra arguments are
added in the declaration list as SYM_NODE but these arguments
can already be SYM_NODEs.
Sparse doesn't support everywhere such nested nodes (they must
be merged) but in this case it's fine as the node will be merged
when evaluated.
Add a comment telling the situation is fine.
Also, move the code to where the variadic arguments are handled
since the fixed one will be anyway directly overwritten.
Note: Sparse doesn't really support inlining of variadic functions
but is fine when the arguments are not used (and such cases
occur in the kernel).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
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>
|
