| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
* fix and improve the check that protects try_to_simplify_bb()
* fix remove_merging_phisrc() with duplicated CFG edges.
|
|
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>
|
|
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>
|
|
These two functions are now exactly the same, so replace the
first one by the second one.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The function rewrite_load_instruction() is defined in flow.c but:
* is not directly related to 'flow'
* it's only used in memops.c
* needs some change related to simplify_loads().
So, move this code to memops.c
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The few external functions defined in simplify.h are declared
in flow.h (for historical reasons).
In preparation for some changes, create a specific headers for these.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Since simplify_memops() must be called unconditionally (see [1])
it's useless to set REPEAT_SYMBOL_CLEANUP (at the condition that
REPEAT_CSE is set instead).
So remove it's definition and set REPEAT_CSE instead when needed).
[1] 6b5e7cf5ac39 ("cfg: call simplify_memops() unconditionally.")
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
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>
|
|
The values produced by expressions are not always used,
it's normal. However this produce useless code that will
need to be removed, sooner or later.
Currently, this removal of dead instructions is done as
part of the normal instruction simplification where each
kind of instruction are checked if it is used or not and,
if not, the usage is removed from the operands and the
instruction itself is removed. This has several drawbacks:
* this is done at each simplification cycle while it is
only needed just after linearization
* there is a large overlap between what is needed to correctly
remove these dead instructions and kill_instruction()
* instructions which are not simplified are forgotten
for this and thus never removed.
Change this by adding a separate function to remove these
deadborn instructions.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
There are several places where it can be usefull to
remove dead stores but the existing function for this is
local to flow.c & doesn't have an interface easy to use.
Change this make a clean interface for this functionality.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Add an helper to remove the usage of a pseudo like kill_use() do
but without trying to kill (recursively!) the defining instruction
if the usage drop to zero.
This function is meant to be used when it is not yet safe to
kill instructions. If the usage drop to zero, nothing special is
done, the instruction becomes dead and will be eliminated later.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The REPEAT_... flags are used as bitfield but the last one
introduced (by myself): REPEAT_CFG_CLEANUP was wrongly defined
to the next value instead of the next bit.
Fix this by defining it to the right value.
Also change all the definition to use '1 << ...' to clearly
show we expect uniq bit values here.
Fixes: 917d37ad7681c88fc4d8df484f7b10d550190df8
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
The code for the inner optimization loop was in the same file
than the one for CSE. Now that the CSE have a well defined
interface, we can move this inner loop together with
the main optimization loop in optimize.c
This move make the code better structured and make it easier
to understand the optimization logic and make any experiment
or needed changes to it.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Currently, the interface for liveness analysis is declared
in the flow.h header file. There is no a real need to move
it to its own file but it's the dual of the previous patch
and help a bit to make the code structure clearer.
Move the prototype for liveness analysis to its own header.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
This let us take others actions if no changes have been made
and allow simpler call to this function since its effect on
'repeat_phase' can be directly returned.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
These functions are clearly meant to be used locally.
Furthermore, some have no prototypes.
Make these functions static and remove the prototype
when one was present.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
|
|
There is essentially three cases where kill_instruction() is
called:
1) when implicitely removing an instruction via
kill_use()/remove_usage() once all users of (the target of)
this instruction have been removed and so this instruction
become unneeded.
2) when explicitely removing a specific instruction.
3) when explicitely removing all instructions in a basic block
because it became unreachable.
For 'pure' instructions, like the arithmetic operators, these
three cases can be handled exactly the same but for instructions
having side-effects, special care is needed.
For them case 1) should do nothing while cases 2) & 3) should
remove the instruction and adjust the usage of its operands like
for normal instructions.
To handle this gracefully:
- rename kill_instruction() into kill_insn()
- add a new argument ('force') to kill_insn()
- create kill_instruction() & kill_instruction_force() as inline
functions calling kill_insn() with 'force' set respectively to 0 & 1.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
... and thus possible to include them in arbitrary order and without any
external dependencies.
Signed-off-by: Kamil Dudka <kdudka@redhat.com>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
Hello,
attached are patch, testing input for test-unssa and its outputs before patch
and after patch. Thanks in advance for considering the patch!
Kamil
test:
.L0x7f9fb2030010
<entry-point>
phisrc.32 %phi2(ptr) <- %arg1
br .L0x7f9fb2030130
.L0x7f9fb2030130
copy.32 %r1(ptr) <- %r5(ptr)
br %r1(ptr), .L0x7f9fb2030058, .L0x7f9fb20300e8
.L0x7f9fb2030058
load.32 %r3 <- 0[%r1(ptr)]
phisrc.32 %phi3(ptr) <- %r3
br .L0x7f9fb2030130
.L0x7f9fb20300e8
ret
test:
.L0x7f4a7f7f1010
<entry-point>
copy.32 %r5(ptr) <- %arg1
br .L0x7f4a7f7f1130
.L0x7f4a7f7f1130
copy.32 %r1(ptr) <- %r5(ptr)
br %r1(ptr), .L0x7f4a7f7f1058, .L0x7f4a7f7f10e8
.L0x7f4a7f7f1058
load.32 %r3 <- 0[%r1(ptr)]
copy.32 %r5(ptr) <- %r3
br .L0x7f4a7f7f1130
.L0x7f4a7f7f10e8
ret
>From 66a02fa7cec780fc88d6ef4cce7a1e704928808a Mon Sep 17 00:00:00 2001
From: Kamil Dudka <kdudka@redhat.com>
Date: Sun, 9 Aug 2009 10:22:11 +0200
Subject: [PATCH] unssa: track uses when replacing a phi node
The output of test-unssa is inconsistent for a simple test-case without
this patch:
static void test(void **ptr)
{
while (ptr) {
ptr = *ptr;
}
}
Signed-off-by: Kamil Dudka <kdudka@redhat.com>
Signed-off-by: Christopher Li <sparse@chrisli.org>
|
|
This shows that we have some inlining bug where we seem to
be corrupting the offsetting of an array. So right now the
warnings we get in the kernel seem to be bogus, but this
should help find that other bug too, and it doesn't trigger
often enough to be too distracting.
|
|
Now that we have full pseudo usage lists, we can also add
deathnotes to pseudos in the instruction stream.
NOTE! We add the deathnote to _before_ the last instruction
that uses that pseudo. That looks a bit strange, but it's
actually what you want: when we traverse the instuctions, we
want to know that the inputs are dead.
|
|
regular CSE.
The CSE case is totally different: since both children use the same
pseudos, there can be no question that a common parent wouldn't
have that pseudo live.
|
|
The "constant conditional" stuff in flow simplification is now
handled by the trivial instruction simplification, so the only
thing that remained was the conditional flow based on following
constant PHI-nodes. And that one can be much more effectively
done after liveness analysis, when we can decide to skip even
non-empty blocks if the target we are skipping to doesn't care
about this particular block.
|
|
|
|
Let's try to make sure that once I get these flow bugs ironed
out they won't come creeping back in.
|
|
node re-writing.
We'll want to do it for CSE too.
|
|
It's a bit more simple-minded than the symbol simplification,
and it can be more costly. So we start off with the (cheap)
symbol simplification algorithm, and then use this new more
generic phase later.
This allows us to remove extra loads (and, in theory, stores,
but the dead store elimination is so simple-minded right now
that it's effectively useless).
|
|
And rename the argument.
|
|
And clean up naming while at it ("insn" -> "instruction"). Shorthand
is fine for local things, but when we expose them globally we're
better off typing a few extra characters.
|
|
track of which instructions use which pseudos.
It also verifies the usage, which shows a few bugs in
structure handling.
|
|
repeating CSE itself.
In particular, some symbol address simplifications imply that
we should repeat symbol simplification, since things may have
improved.
|
|
When done carefully, this allows us to rewrite pseudo usage,
as long as we make sure to fix up all the usage chains.
In particular, we can now simplify memops and turn an access
of a symbol through a pointer into a direct symbol access.
|
|
We want to make sure that we kill them properly, so that
any pseudos they depended on or generated are also killed.
|
|
Also export "kill_bb()", since others want to use it too.
|
|
Also, allow marking a pseudo unused by setting it to VOID,
which just disables further renaming of that use. This is
needed to make phi-source instructions (that can be shared
among multiple phi-nodes thanks to CSE) be collectable.
We used to just mark the phi source dead, but that was
wrong, since _another_ phi node might be using it.
|
|
This does branches-to-branches and trivial dead basicblock
removal before CSE (so that CSE can do a better job).
|
|
Instead of using the "convert_load_insn()" that converts them to
OP_LNOP's, which ends up confusing instruction printout horribly.
|
|
This makes us able to CSE stuff where one subexpression
directly dominates another.
But we still don't do any fancy code motion in the non-
dominance case.
|
|
It ain't very smart yet, but give it time.
In particular, right now it gathers information for the
whole function, but it only does the actual replacement
if the instructions are in the same basic block.
|
|
Small files are good. Now "linearize" really just contains the
code that does a straightforward linearization of the tree, and
flow.c contains the stuff that tries to analyse the result.
|
