[RFC] CSE: relax type checking in hashing/compare

[RFC] CSE: relax type checking in hashing/compare

[Luc Van Oostenryck]

Currently in a function like here below the comparision is not
optimized away. This is because CSE doesn't recognize 'a = &g'
and 'b = &g' as being equivalent expressions.
	static int foo(void) {
		extern int g;
		void *a = &g;
		void *b = &g;
		return a == b;
	}

The problem come in fact from the implicit cast, more precisely, 
because the two '&g' generate their own symbol and thus have
distinct types.

I made a patch (see the second one in this non-serie) so that
cast from equivalent types hash identically. It worked well
but after a while I concluded that it was not really needed.
Indeed, in the context of CSE, to consider two instructions as
equivalent, the first thing that need to be equal is their source
operands. Isn't it already the case that if we use the same pseudo
in two instructions, the type of these pseudo in each instructions
must already be, if not identical, at least 'sufficently equivalent'?

I'm missing something?

If not, then the following simple patch should be correct.

Note: this patch give almost the same results as my original,
complex version. Both can eliminate quite a few casts (the
output of test-linearize on a subset of GCC's testsuite gives
a good 33K diff), both gives correct results for the case I've
checked and when using sparse on a kernel's allyesconfig run,
both give exactly the same warnings with ot without the patch).

Luc Van Oostenryck

---
 cse.c | 12 ------------
 1 file changed, 12 deletions(-)

diff --git a/cse.c b/cse.c
index 89812afae..d7f5de302 100644
--- a/cse.c
+++ b/cse.c
@@ -91,13 +91,6 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 	case OP_CAST:
 	case OP_SCAST:
 	case OP_PTRCAST:
-		/*
-		 * This is crap! Many "orig_types" are the
-		 * same as far as casts go, we should generate
-		 * some kind of "type hash" that is identical
-		 * for identical casts
-		 */
-		hash += hashval(insn->orig_type);
 		hash += hashval(insn->src);
 		break;
 
@@ -235,11 +228,6 @@ static int insn_compare(const void *_i1, const void *_i2)
 	case OP_CAST:
 	case OP_SCAST:
 	case OP_PTRCAST:
-		/*
-		 * This is crap! See the comments on hashing.
-		 */
-		if (i1->orig_type != i2->orig_type)
-			return i1->orig_type < i2->orig_type ? -1 : 1;
 		if (i1->src != i2->src)
 			return i1->src < i2->src ? -1 : 1;
 		break;

[RFC,original PATCH] CSE: let equivalent cast hash & compare identically

[Luc Van Oostenryck]

---
 cse.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 64 insertions(+), 14 deletions(-)

diff --git a/cse.c b/cse.c
index 89812afae..aab6bc7a4 100644
--- a/cse.c
+++ b/cse.c
@@ -34,6 +34,49 @@ static int phi_compare(pseudo_t phi1, pseudo_t phi2)
 	return 0;
 }
 
+// for cast's hashing & comparison
+struct typeinfo {
+	struct symbol *type;
+	unsigned int size;
+	int kind;
+};
+
+static void get_typeinfo(struct symbol *type, struct typeinfo *info)
+{
+	struct symbol *basetype;
+
+redo:
+	basetype = type->ctype.base_type;
+	switch (type->type) {
+	case SYM_NODE:
+		type = basetype;
+		goto redo;
+
+	case SYM_BASETYPE:
+		if (basetype == &int_ctype)
+			break;
+		if (basetype == &fp_type)
+			break;
+		basetype = type;
+		break;
+
+	case SYM_ENUM:
+	case SYM_BITFIELD:
+	case SYM_PTR:
+	case SYM_FN:
+	case SYM_ARRAY:
+		break;
+
+	default:
+		basetype = type;
+		break;
+	}
+
+	info->type = basetype;
+	info->size = type->bit_size;
+	info->kind = type->type;
+	return;
+}
 
 static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
 {
@@ -90,16 +133,16 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 
 	case OP_CAST:
 	case OP_SCAST:
-	case OP_PTRCAST:
-		/*
-		 * This is crap! Many "orig_types" are the
-		 * same as far as casts go, we should generate
-		 * some kind of "type hash" that is identical
-		 * for identical casts
-		 */
-		hash += hashval(insn->orig_type);
+	case OP_PTRCAST: {
+		struct typeinfo info;
+
+		get_typeinfo(insn->orig_type, &info);
+		hash += hashval(info.type);
+		hash += hashval(info.size);
+		hash += hashval(info.kind);
 		hash += hashval(insn->src);
 		break;
+	}
 
 	/* Other */
 	case OP_PHI: {
@@ -234,15 +277,22 @@ static int insn_compare(const void *_i1, const void *_i2)
 
 	case OP_CAST:
 	case OP_SCAST:
-	case OP_PTRCAST:
-		/*
-		 * This is crap! See the comments on hashing.
-		 */
-		if (i1->orig_type != i2->orig_type)
-			return i1->orig_type < i2->orig_type ? -1 : 1;
+	case OP_PTRCAST: {
+		struct typeinfo info1, info2;
+
+		get_typeinfo(i1->orig_type, &info1);
+		get_typeinfo(i2->orig_type, &info2);
+
 		if (i1->src != i2->src)
 			return i1->src < i2->src ? -1 : 1;
+		if (info1.type != info2.type)
+			return info1.type < info2.type ? -1 : 1;
+		if (info1.size != info2.size)
+			return info1.size < info2.size ? -1 : 1;
+		if (info1.kind != info2.kind)
+			return info1.kind < info2.kind ? -1 : 1;
 		break;
+	}
 
 	default:
 		warning(i1->pos, "bad instruction on hash chain");
-- 
2.11.0

Re: [RFC] CSE: relax type checking in hashing/compare

[Christopher Li]

On Fri, Feb 17, 2017 at 8:06 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> I made a patch (see the second one in this non-serie) so that
> cast from equivalent types hash identically. It worked well
> but after a while I concluded that it was not really needed.
> Indeed, in the context of CSE, to consider two instructions as
> equivalent, the first thing that need to be equal is their source
> operands. Isn't it already the case that if we use the same pseudo
> in two instructions, the type of these pseudo in each instructions
> must already be, if not identical, at least 'sufficently equivalent'?

I think so. I will apply this version to sparse-next.

Chris

Re: [RFC] CSE: relax type checking in hashing/compare

[Christopher Li]

On Fri, Feb 17, 2017 at 8:06 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> I'm missing something?
>
> If not, then the following simple patch should be correct.

This patch is missing a S-O-B. Can you add one?

Thanks

Chris

Re: [RFC] CSE: relax type checking in hashing/compare

[Luc Van Oostenryck]

On Mon, Feb 27, 2017 at 04:11:44PM +0800, Christopher Li wrote:
> On Fri, Feb 17, 2017 at 8:06 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > I'm missing something?
> >
> > If not, then the following simple patch should be correct.
> 
> This patch is missing a S-O-B. Can you add one?

I did this purposely because it was a RFC.
Also:
- I still have some doubts about this patch
- It won't solve anything, only allow more CSE (but maybe more than
  really wanted)
- There is no urgency at all.

So I think it would be better to not include it in the coming release
and instead let it ripe a little bit.

But if you really prefer to include it, maybe not in a release but
in another branch, it's fine for me also.

    Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

Re: [RFC] CSE: relax type checking in hashing/compare

[Christopher Li]

On Mon, Feb 27, 2017 at 1:40 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Mon, Feb 27, 2017 at 04:11:44PM +0800, Christopher Li wrote:
>> On Fri, Feb 17, 2017 at 8:06 AM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>> > I'm missing something?
>> >
>> > If not, then the following simple patch should be correct.
>>
>> This patch is missing a S-O-B. Can you add one?
>
> I did this purposely because it was a RFC.
> Also:
> - I still have some doubts about this patch
> - It won't solve anything, only allow more CSE (but maybe more than
>   really wanted)
> - There is no urgency at all.
>
> So I think it would be better to not include it in the coming release
> and instead let it ripe a little bit.

I am catching up with the patches in the order it was send out. I will
leave this
one alone then.

Chris

Re: [RFC] CSE: relax type checking in hashing/compare

[Luc Van Oostenryck]

On Wed, Apr 19, 2017 at 2:32 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Mon, Feb 27, 2017 at 1:40 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> On Mon, Feb 27, 2017 at 04:11:44PM +0800, Christopher Li wrote:
>>> On Fri, Feb 17, 2017 at 8:06 AM, Luc Van Oostenryck
>>> <luc.vanoostenryck@gmail.com> wrote:
>>> > I'm missing something?
>>> >
>>> > If not, then the following simple patch should be correct.
>>>
>>> This patch is missing a S-O-B. Can you add one?
>>
>> I did this purposely because it was a RFC.
>> Also:
>> - I still have some doubts about this patch
>> - It won't solve anything, only allow more CSE (but maybe more than
>>   really wanted)
>> - There is no urgency at all.
>>
>> So I think it would be better to not include it in the coming release
>> and instead let it ripe a little bit.
>
> I am catching up with the patches in the order it was send out. I will
> leave this
> one alone then.
>
> Chris

Yes, please.
I'll return to it later when I'll have looked a bit more closed what
would be the impact.

-- Luc