From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
To: linux-sparse@vger.kernel.org
Cc: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Subject: [PATCH 2/2] cse: place common expressions in the Lowest Common Dominator
Date: Fri, 4 Dec 2020 18:16:04 +0100 [thread overview]
Message-ID: <20201204171604.69635-3-luc.vanoostenryck@gmail.com> (raw)
In-Reply-To: <20201204171604.69635-1-luc.vanoostenryck@gmail.com>
Currently, during CSE, common expressions are eliminated if either:
1) they belong to the same Basic Block;
2) one of the expressions dominates the other (so, one of the BB they
belong dominates the other);
3) they have a single parent which is the same for both.
The third case can be extended to another suitable ancestor:
any common dominator would be OK, which is exactly what is done in
this patch.
Note: This patch is interesting because it allows significantly more
common expressions to be eliminated. However, it has the annoying
disadvantage of making the 'context imbalance' problem slightly
worse. So, it's not intended to be merged as-is.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
cse.c | 38 ++++++++++----------------------------
1 file changed, 10 insertions(+), 28 deletions(-)
diff --git a/cse.c b/cse.c
index 1e58a973ecf6..c33babf2c6c8 100644
--- a/cse.c
+++ b/cse.c
@@ -279,20 +279,6 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct
return def;
}
-static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
-{
- struct basic_block *parent;
-
- if (bb_list_size(bb1->parents) != 1)
- return NULL;
- parent = first_basic_block(bb1->parents);
- if (bb_list_size(bb2->parents) != 1)
- return NULL;
- if (first_basic_block(bb2->parents) != parent)
- return NULL;
- return parent;
-}
-
static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
{
delete_ptr_list_entry((struct ptr_list **)list, insn, count);
@@ -318,7 +304,7 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
b2 = i2->bb;
/*
- * Currently we only handle the uninteresting degenerate case where
+ * First try the uninteresting degenerate case where
* the CSE is inside one basic-block.
*/
if (b1 == b2) {
@@ -332,22 +318,18 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
warning(b1->pos, "Whaa? unable to find CSE instructions");
return i1;
}
- if (domtree_dominates(b1, b2))
- return cse_one_instruction(i2, i1);
- if (domtree_dominates(b2, b1))
+ /* Then try the case where one of the BB already dominate the other. */
+ common = bb_common_dominator(b1, b2);
+ if (common == b1)
+ return cse_one_instruction(i2, i1);
+ if (common == b2)
return cse_one_instruction(i1, i2);
- /* No direct dominance - but we could try to find a common ancestor.. */
- common = trivial_common_parent(b1, b2);
- if (common) {
- i1 = cse_one_instruction(i2, i1);
- remove_instruction(&b1->insns, i1, 1);
- add_instruction_to_end(i1, common);
- } else {
- i1 = i2;
- }
-
+ /* No direct dominance - use the common dominator. */
+ cse_one_instruction(i2, i1);
+ remove_instruction(&b1->insns, i1, 1);
+ add_instruction_to_end(i1, common);
return i1;
}
--
2.29.2
prev parent reply other threads:[~2020-12-04 17:19 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-12-04 17:16 [RFC PATCH 0/2] cse: place common expressions in the Lowest Common Dominator Luc Van Oostenryck
2020-12-04 17:16 ` [PATCH 1/2] flowgraph: add a function to calculate the Lowest Common Denominator Luc Van Oostenryck
2020-12-04 17:16 ` Luc Van Oostenryck [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20201204171604.69635-3-luc.vanoostenryck@gmail.com \
--to=luc.vanoostenryck@gmail.com \
--cc=linux-sparse@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.