| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
The linearization step sometimes creates a lot of intermediate
basic blocks, often containing just a branch. Their presence often
make things more complicated than needed (more work to do in later
phases, visual clutter when inspection the IR 'by hand') and they
can sometimes, indirectly hinder some optimizations.
Happily, most of them can trivially be optimized away.
So, add a CFG simplification phase running very early and doing:
*) jump threading (eliminate jump to jump)
*) merge single-child/sinle-parents basic blocks.
These changes slightly decrease the number of 'context imbalance'
warnings (32 less on a total of 995 warnings) and the size of
the generated IR (only ~0.4% but this is very significant relatively
to most other simplifications).
They also seem to improve the kernel tests' running time:
before after
real 4m19.261s real 4m17.548s
user 72m03.634s user 71m34.642s
sys 29m05.573s sys 29m01.856s
but it's probably just noise.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
As an experiment about the linearization of builtins,
try this easy one (and statically expand it if the
argument is constant).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Sparse complains when a shift amount is too big for the size
of its operand or if it's negative.
However, it does this even for expressions that are never evaluated.
It's especially annoying in the kernel for type generic macros,
for example the ones in arch/*/include/asm/cmpxchg.h
So, remove all warnings done at expansion time and avoid any
simplifications of such expressions. Same, at linearization
and optimization time but in this case mark the instructions as
'tainted' to inhibit any further simplifications. Finally, at the
end of the optimization phase, warn for the tainted instructions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, the tree inlining is done very early, during the
evaluation phase. This means that the inlining is done even
if the corresponding call belong to a sub-expression that
will be discarded during the expansion phase.
Usually this is not a problem but in some pathological
cases it can lead to a huge waste of memory and CPU time.
So, move this inline expansion to ... the expansion phase.
Also, re-expand the resulting expression since constant
arguments may create new opportunities for simplification.
Note: the motivation for thsi is a pathological case in the
kernel where a combination of max_t() + const_ilog2() +
roundup_pow_of_two() + cpumask_weight() + __const_hweight*()
caused Sparse to use 2.3Gb of memory. With this patch
the memory consumption is down to 247Mb.
Link: https://marc.info/?l=linux-sparse&m=158098958501220
Link: https://lore.kernel.org/netdev/CAHk-=whvS9x5NKtOqcUgJeTY7dfdAHc
Reported-by: Randy Dunlap <rdunlap@infradead.org>
Originally-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, in expand_dereference(), the dereference of a symbol with
a complex type is considered as costing as high as a non-symbol
because it's not recognised it's a symbol.
However, both cases should have exactly the same cost since they
address calculation amounts to 'symbol + offset'.
So, instead of taking in account a single level of
symbol + offset
let's use a loop for this in order to handle
symbol [+ offset]*
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, constant_symbol_value() is doing the expansion
of a constant initializer when an explicit one is found
but nothing is done if the initilizer is an implicit one.
Fix this by:
* adding an helper to lookup the corresponding type from
offset;
* using this helper to get the correct kind for the value:
- a 0-valued EXPR_VALUE for integers
- a 0.0-valued EXPR_FVALUE for floats.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, the expansion of constant initializers is done
whenever the offset in the initializer match the one
being expanded.
However, it's not correct to do this expansion of an
integer with the initializer for a float and vice-versa.
Fix this by adding the corresponding tests to the other
tests of the value.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, the expansion of constant initializers is done
whenever the offset in the initializer match the one
we're expanding.
However, it's not correct to do this expansion if their
size doesn't match since in this case the value of one
doesn't represent the value of the other.
Fix this by adding a check for the size.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Symbols which have their address taken (with the 'addressof'
operator: &) are marked as such (with the modifier MOD_ADDRESSABLE).
But degenerated arrays and functions have their address implicitly
taken.
MOD_ADDRESSABLE is used to prevent to replace a symbol dereference
nto the value used to initialize to it. For example, in code like:
static int foo(void)
{
int x[2] = { 1, 2 };
return x[1];
}
the return expression can be replaced by 2. This is not the case
case if the array is first passed in a function call, like here:
extern void def(void *, unsigned int);
static int bar(void)
{
int x[2] = { 1, 2 };
def(x, sizeof(x));
return x[1];
}
Fix this by marking degenerated arrays (and functions) as also
being addressable.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Constant expansion of symbols with a complex type is not done
like for simpler ones. Only the first-level EXPR_INITIALIZER
is handled.
Add some testcases for this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, in expand_dereference(), the dereference of a symbol with
a complex type is considered as costing as high as a non-symbol
because it's not recognised it's a symbol.
Add a testcase for this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Sparse can't do this yet.
So, add a testcase for it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, constant_symbol_value() is doing the expansion
of a constant initializer when an explicit one is found
but nothing is done for the default/implicit ones.
Add a testcase to illustrate this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Several issues were covered by the same testcase.
Fix this by splitting the testcases.
Also, rename these testcases to a more descriptive name.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, ASM operands aren't expanded or even evaluated.
This causes Sparse to emit warnings about 'unknown expression'
during the linearization of these operands if they contains,
for example, calls to __builtin_compatible_types_p().
Note: the correct handling of ASM operands needs to make
the distinction between 'memory' operands and 'normal'
operands. For this, it is needed to look at the constraints
and these are architecture specific. The patches in this
series only consider the constraints m, v, o & Q as
being for memory operands and, happily, these seems
to cover most usage for the most common architectures.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The operands of extended ASM need to be expanded, exactly
like any other expression. For example, without this expansion
expressions with __builtin_compatible_types_p() can't be
linearized and will issue a 'warning unknown expression".
So, add the missing expansion of ASM operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
ASM statements are quite complex.
Add some tests to catch some potential errors.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Compound literals, like all other expressions, need to be be
expanded before linearization, but this is currently not done.
As consequence, some builtins are unexpectedly still present,
same for EXPR_TYPEs, ... with error messages like:
warning: unknown expression
at linearization.
Fix this by adding the missing expansion of compound literals.
Note: as explained in the code itself, it's not totally clear
how compound literals can be identified after evaluation.
The code here consider all anonymous symbols with an
initializer as being a compound literal.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Compound literals are currently not expanded.
Add a test for this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
During the expansion of shifts, the variable 'conservative' is used
to inhibit any possible diagnostics (for example, because the needed
information is if the expression is a constant or not).
However, this must not inhibit the simplification of valid shift
expressions. Unfortunately, by moving the validation inside
check_shift_count(), this what was done by commit
0b73dee01 ("big-shift: move the check into check_shift_count()").
Found through a false positive VLA detected in the Linux kernel.
The array size was computed through min() on a shifted constant value
and sparse complained about it.
Fix this by changing the logic of check_shift_count():
1) moving the test of 'conservative' inside check_shift_count()
and only issuing warnings if set.
2) moving the warning part in a separate function: warn_shift_count()
3) let check_shift_count() return if the shift count is valid
so that the simplication can be eluded if not.
Fixes: 0b73dee0171a15800d0a4ae6225b602bf8961599
Signed-off-by: Thomas Weißschuh <thomas@t-8ch.de>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
If the flag '-m64' is used on a 32-bit architecture/machine having
int32_t set to 'long', then these int32_t are forced to 64-bit ...
So, ignore the effect of -m64 on these archs and ignore
'64-bit only' tests on them.
Reported-by: Uwe Kleine-König <uwe@kleine-koenig.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Tested-by: Uwe Kleine-König <uwe@kleine-koenig.org>
|
|
In do_show_type(), builtin_typename() is used to display builtin
(base) types and modifier_string() is used to display modifiers.
However, most base types contains some intrinsic modifiers, the
type specifiers. So, a type like 'unsigned long' is displayed as
'unsigned long [unsigned] [long]'.
Fix this redundancy by not displaying the specifiers when displaying
a base_type (or an enum).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Often show_typename() is used to display a type and the associated
identifier is irrelevant but is displayed nevertheless.
However, when the identifier is itself not present, it is still
displayed as '<noident>', which is just noise and can be confusing.
Fix this by displaying nothing for null identifiers in show_typename().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The expression corresponding to the function pointer of indirect
call can be arbirarily complex. For example, it can contain a
statement expression or another call, possibly inlined.
These expressions must be expanded to insure that sub-expressions
involving 'sizeof()' or other operators taking a type as argument
(like __builtin_compatible_types_p()) are no more present (because
these expressions always evaluate to a compile-time constant and
so are not expected and thus not handled at linearization time).
However, this is not currently enforced, possibly causing some
failures during linearization with warnings like:
warning: unknown expression (4 0)
(which correspond to EXPR_TYPE).
Fix this, during the expansion of function calls, by also expanding
the corresponding designator.
References: https://lore.kernel.org/lkml/1542623503-3755-1-git-send-email-yamada.masahiro@socionext.com/
Reported-by: Masahiro Yamada <yamada.masahiro@socionext.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Tested-by: Masahiro Yamada <yamada.masahiro@socionext.com>
|
|
Add a testcase showing function designator are not expanded.
References: https://lore.kernel.org/lkml/1542623503-3755-1-git-send-email-yamada.masahi>
Reported-by: Masahiro Yamada <yamada.masahiro@socionext.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Casts to integer used to be done with only 2 instructions:
OP_CAST & OP_SCAST.
Those are not very convenient as they don't reflect the real
operations that need to be done.
This patch specialize these instructions in:
- OP_TRUNC, for casts to a smaller type
- OP_ZEXT, for casts that need a zero extension
- OP_SEXT, for casts that need a sign extension
- Integer-to-integer casts of the same size are considered as
a NOPs and are, in fact, never emitted.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Typewisely, sparse process __builtin_expect() as:
1) returning 'int'
2) taking any type in first & second arg
3) returning exactly its first argument, silently, even
if this conflicts with 1).
but this doesn't match with how gcc declare it:
long __builtin_expect(long, long);
Fix this by giving the proper prototype to this builtin
and removing the bogus 'returns an int'.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
__builtin_isinf(), isnan() & isnormal() are all special cases
of __builtin_fpclassify().
Add a few cases testing if those are correctly expanded if
when the argument is a constant.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
More specifically: for __builtin_nan(), _huge_val() & _inf()
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
