10 files changed, 192 insertions, 104 deletions
diff --git a/linearize.c b/linearize.c
index c2010c4b..2e9a5638 100644
--- a/linearize.c
+++ b/linearize.c
@@ -878,6 +878,7 @@ pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *t
  */
 struct access_data {
 	struct symbol *type;		// ctype
+	struct symbol *btype;		// base type of bitfields
 	pseudo_t address;		// pseudo containing address ..
 	unsigned int offset;		// byte offset
 };
@@ -934,14 +935,13 @@ static int linearize_address_gen(struct entrypoint *ep,
 
 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
 {
-	struct symbol *btype = bitfield_base_type(ad->type);
 	struct instruction *insn;
 	pseudo_t new;
 
 	if (!ep->active)
 		return VOID;
 
-	insn = alloc_typed_instruction(OP_LOAD, btype);
+	insn = alloc_typed_instruction(OP_LOAD, ad->btype);
 	new = alloc_pseudo(insn);
 
 	insn->target = new;
@@ -959,7 +959,7 @@ static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t va
 	if (!bb)
 		return;
 
-	store = alloc_typed_instruction(OP_STORE, bitfield_base_type(ad->type));
+	store = alloc_typed_instruction(OP_STORE, ad->btype);
 	store->offset = ad->offset;
 	use_pseudo(store, value, &store->target);
 	use_pseudo(store, ad->address, &store->src);
@@ -990,12 +990,13 @@ static pseudo_t linearize_store_gen(struct entrypoint *ep,
 		struct access_data *ad)
 {
 	struct symbol *ctype = ad->type;
-	struct symbol *btype = bitfield_base_type(ctype);
+	struct symbol *btype;
 	pseudo_t store = value;
 
 	if (!ep->active)
 		return VOID;
 
+	btype = ad->btype = bitfield_base_type(ctype);
 	if (type_size(btype) != type_size(ctype)) {
 		pseudo_t orig = add_load(ep, ad);
 		store = linearize_bitfield_insert(ep, orig, value, ctype, btype);
@@ -1079,12 +1080,13 @@ static pseudo_t linearize_bitfield_extract(struct entrypoint *ep,
 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
 {
 	struct symbol *ctype = ad->type;
-	struct symbol *btype = bitfield_base_type(ctype);
+	struct symbol *btype;
 	pseudo_t new;
 
 	if (!ep->active)
 		return VOID;
 
+	btype = ad->btype = bitfield_base_type(ctype);
 	new = add_load(ep, ad);
 	if (ctype->bit_size != type_size(btype))
 		new = linearize_bitfield_extract(ep, new, ctype, btype);
@@ -1105,7 +1107,7 @@ static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
 {
 	struct access_data ad = { NULL, };
-		pseudo_t old, new, one;
+	pseudo_t old, new, one;
 	int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
 
 	if (!linearize_address_gen(ep, expr->unop, &ad))
@@ -1117,7 +1119,11 @@ static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr
 		one = add_setfval(ep, expr->ctype, expr->op_value);
 	else
 		one = value_pseudo(expr->op_value);
-	new = add_binary_op(ep, expr->ctype, op, old, one);
+	if (ad.btype != ad.type)
+		old = cast_pseudo(ep, old, ad.type, ad.btype);
+	new = add_binary_op(ep, ad.btype, op, old, one);
+	if (ad.btype != ad.type)
+		new = cast_pseudo(ep, new, ad.btype, ad.type);
 	linearize_store_gen(ep, new, &ad);
 	return postop ? old : new;
 }
@@ -1772,14 +1778,6 @@ static pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
 	return cast_pseudo(ep, src, orig->ctype, expr->ctype);
 }
 
-static pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad)
-{
-	struct expression *init_expr = pos->init_expr;
-
-	ad->offset = pos->init_offset;
-	return linearize_initializer(ep, init_expr, ad);
-}
-
 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
 {
 	switch (initializer->type) {
@@ -1791,7 +1789,8 @@ static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *
 		break;
 	}
 	case EXPR_POS:
-		linearize_position(ep, initializer, ad);
+		ad->offset = initializer->init_offset;
+		linearize_initializer(ep, initializer->init_expr, ad);
 		break;
 	default: {
 		pseudo_t value = linearize_expression(ep, initializer);
diff --git a/simplify.c b/simplify.c
index b9a32e23..ef98b205 100644
--- a/simplify.c
+++ b/simplify.c
@@ -575,12 +575,26 @@ static long long check_shift_count(struct instruction *insn, unsigned long long
 	return sval;
 }
 
+static int simplify_or_lsr(struct instruction *insn, pseudo_t src, pseudo_t other, unsigned shift)
+{
+	// src->def->opcode == OP_AND
+	pseudo_t src2 = src->def->src2;
+
+	if (!constant(src2))
+		return 0;
+	if (((unsigned long long) src2->value) >> shift)
+		return 0;
+	return replace_pseudo(insn, &insn->src1, other);
+}
+
 static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
 {
 	struct instruction *def;
+	unsigned long long mask;
 	unsigned long long nval;
 	unsigned int size;
 	pseudo_t src2;
+	pseudo_t src;
 
 	if (!value)
 		return replace_with_pseudo(insn, pseudo);
@@ -627,14 +641,54 @@ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long v
 		break;
 	case OP_LSR:
 		size = operand_size(insn, pseudo);
-		/* fall through */
-	case OP_SHL:
 		if (value >= size)
 			goto zero;
-		if (pseudo->type != PSEUDO_REG)
+		switch(DEF_OPCODE(def, pseudo)) {
+		case OP_AND:
+			// replace (A & M) >> S
+			// by      (A >> S) & (M >> S)
+			if (!constant(def->src2))
+				break;
+			if (nbr_users(pseudo) > 1)
+				break;
+			mask = def->src2->value;
+			def->opcode = OP_LSR;
+			def->src2 = insn->src2;
+			insn->opcode = OP_AND;
+			insn->src2 = value_pseudo(mask >> value);
+			return REPEAT_CSE;
+		case OP_LSR:
+			goto case_shift_shift;
+		case OP_OR:
+			// replace ((A & M) | B) >> S
+			// by      (B >> S)
+			// when	(M >> S) == 0
+			src = def->src1;
+			if (def_opcode(src) == OP_AND)
+				return simplify_or_lsr(insn, src, def->src2, value);
+			src = def->src2;
+			if (def_opcode(src) == OP_AND)
+				return simplify_or_lsr(insn, src, def->src1, value);
 			break;
-		def = pseudo->def;
-		if (def->opcode == insn->opcode) {
+		case OP_SHL:
+			// replace (A << S) >> S
+			// by      A & (Mask(size) >> S)
+			if (!constant(def->src2))
+				break;
+			if (def->src2->value != value)
+				break;
+			size = insn->size - value;
+			insn->opcode = OP_AND;
+			insn->src2 = value_pseudo((1ULL << size) - 1);
+			return replace_pseudo(insn, &insn->src1, def->src1);
+		}
+		break;
+	case OP_SHL:
+		if (value >= size)
+			goto zero;
+		switch(DEF_OPCODE(def, pseudo)) {
+		case OP_SHL:
+		case_shift_shift:		// also for LSR - LSR
 			if (def == insn)	// cyclic DAG!
 				break;
 			src2 = def->src2;
@@ -770,18 +824,41 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 	return 0;
 }
 
+static int simplify_and_or_mask(struct instruction *insn, pseudo_t and, pseudo_t other, unsigned long long mask)
+{
+	struct instruction *def = and->def;
+
+	if (!constant(def->src2))
+		return 0;
+	if (def->src2->value & mask)
+		return 0;
+	return replace_pseudo(insn, &insn->src1, other);
+}
+
 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
 {
 	pseudo_t old = insn->src1;
 	unsigned long long omask;
 	unsigned long long nmask;
 	struct instruction *def;
+	pseudo_t src1, src2;
 	int osize;
 
 	switch (DEF_OPCODE(def, old)) {
 	case OP_FPCMP ... OP_BINCMP_END:
 		osize = 1;
 		goto oldsize;
+	case OP_OR:
+		// Let's handle ((A & M') | B ) & M
+		// or           (B | (A & M')) & M
+		// when M' & M == 0
+		src1 = def->src1;
+		src2 = def->src2;
+		if (def_opcode(src1) == OP_AND)
+			return simplify_and_or_mask(insn, src1, src2, mask);
+		if (def_opcode(src2) == OP_AND)
+			return simplify_and_or_mask(insn, src2, src1, mask);
+		break;
 	case OP_ZEXT:
 		osize = def->orig_type->bit_size;
 		/* fall through */
@@ -1091,7 +1168,7 @@ static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
 
 offset:
 	/* Invalid code */
-	if (new == orig) {
+	if (new == orig || new == addr) {
 		if (new == VOID)
 			return 0;
 		/*
@@ -1103,8 +1180,9 @@ offset:
 		 */
 		if (repeat_phase & REPEAT_CFG_CLEANUP)
 			return 0;
-		new = VOID;
 		warning(insn->pos, "crazy programmer");
+		replace_pseudo(insn, &insn->src, VOID);
+		return 0;
 	}
 	insn->offset += off->value;
 	replace_pseudo(insn, &insn->src, new);
diff --git a/validation/linear/bitfield-inc.c b/validation/linear/bitfield-inc.c
index ed8efe7d..56997592 100644
--- a/validation/linear/bitfield-inc.c
+++ b/validation/linear/bitfield-inc.c
@@ -10,7 +10,6 @@ void inc(struct s *p)
 /*
  * check-name: bitfield-inc
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: add\\.5
diff --git a/validation/linear/bitfield-size.c b/validation/linear/bitfield-size.c
index 7f9725f9..841bdd0a 100644
--- a/validation/linear/bitfield-size.c
+++ b/validation/linear/bitfield-size.c
@@ -49,41 +49,45 @@ upostinc:
 	load.64     %r1 <- 0[x]
 	load.32     %r2 <- 0[%r1]
 	trunc.3     %r3 <- (32) %r2
-	add.3       %r4 <- %r3, $1
-	load.32     %r5 <- 0[%r1]
-	zext.32     %r6 <- (3) %r4
-	and.32      %r7 <- %r5, $0xfffffff8
-	or.32       %r8 <- %r7, %r6
-	store.32    %r8 -> 0[%r1]
-	zext.32     %r9 <- (3) %r3
-	phisrc.32   %phi1(return) <- %r9
+	zext.32     %r4 <- (3) %r3
+	add.32      %r5 <- %r4, $1
+	trunc.3     %r6 <- (32) %r5
+	load.32     %r7 <- 0[%r1]
+	zext.32     %r8 <- (3) %r6
+	and.32      %r9 <- %r7, $0xfffffff8
+	or.32       %r10 <- %r9, %r8
+	store.32    %r10 -> 0[%r1]
+	zext.32     %r11 <- (3) %r4
+	phisrc.32   %phi1(return) <- %r11
 	br          .L1
 
 .L1:
-	phi.32      %r10 <- %phi1(return)
-	ret.32      %r10
+	phi.32      %r12 <- %phi1(return)
+	ret.32      %r12
 
 
 upreinc:
 .L2:
 	<entry-point>
 	store.64    %arg1 -> 0[x]
-	load.64     %r11 <- 0[x]
-	load.32     %r12 <- 0[%r11]
-	trunc.3     %r13 <- (32) %r12
-	add.3       %r14 <- %r13, $1
-	load.32     %r15 <- 0[%r11]
-	zext.32     %r16 <- (3) %r14
-	and.32      %r17 <- %r15, $0xfffffff8
-	or.32       %r18 <- %r17, %r16
-	store.32    %r18 -> 0[%r11]
-	zext.32     %r19 <- (3) %r14
-	phisrc.32   %phi2(return) <- %r19
+	load.64     %r13 <- 0[x]
+	load.32     %r14 <- 0[%r13]
+	trunc.3     %r15 <- (32) %r14
+	zext.32     %r16 <- (3) %r15
+	add.32      %r17 <- %r16, $1
+	trunc.3     %r18 <- (32) %r17
+	load.32     %r19 <- 0[%r13]
+	zext.32     %r20 <- (3) %r18
+	and.32      %r21 <- %r19, $0xfffffff8
+	or.32       %r22 <- %r21, %r20
+	store.32    %r22 -> 0[%r13]
+	zext.32     %r23 <- (3) %r18
+	phisrc.32   %phi2(return) <- %r23
 	br          .L3
 
 .L3:
-	phi.32      %r20 <- %phi2(return)
-	ret.32      %r20
+	phi.32      %r24 <- %phi2(return)
+	ret.32      %r24
 
 
 ucpy:
@@ -91,15 +95,15 @@ ucpy:
 	<entry-point>
 	store.64    %arg1 -> 0[d]
 	store.64    %arg2 -> 0[s]
-	load.64     %r21 <- 0[s]
-	load.32     %r22 <- 0[%r21]
-	trunc.3     %r23 <- (32) %r22
-	load.64     %r24 <- 0[d]
-	load.32     %r25 <- 0[%r24]
-	zext.32     %r26 <- (3) %r23
-	and.32      %r27 <- %r25, $0xfffffff8
-	or.32       %r28 <- %r27, %r26
-	store.32    %r28 -> 0[%r24]
+	load.64     %r25 <- 0[s]
+	load.32     %r26 <- 0[%r25]
+	trunc.3     %r27 <- (32) %r26
+	load.64     %r28 <- 0[d]
+	load.32     %r29 <- 0[%r28]
+	zext.32     %r30 <- (3) %r27
+	and.32      %r31 <- %r29, $0xfffffff8
+	or.32       %r32 <- %r31, %r30
+	store.32    %r32 -> 0[%r28]
 	br          .L5
 
 .L5:
@@ -110,44 +114,48 @@ spostinc:
 .L6:
 	<entry-point>
 	store.64    %arg1 -> 0[x]
-	load.64     %r29 <- 0[x]
-	load.32     %r30 <- 0[%r29]
-	trunc.3     %r31 <- (32) %r30
-	add.3       %r32 <- %r31, $1
-	load.32     %r33 <- 0[%r29]
-	zext.32     %r34 <- (3) %r32
-	and.32      %r35 <- %r33, $0xfffffff8
-	or.32       %r36 <- %r35, %r34
-	store.32    %r36 -> 0[%r29]
-	zext.32     %r37 <- (3) %r31
-	phisrc.32   %phi3(return) <- %r37
+	load.64     %r33 <- 0[x]
+	load.32     %r34 <- 0[%r33]
+	trunc.3     %r35 <- (32) %r34
+	zext.32     %r36 <- (3) %r35
+	add.32      %r37 <- %r36, $1
+	trunc.3     %r38 <- (32) %r37
+	load.32     %r39 <- 0[%r33]
+	zext.32     %r40 <- (3) %r38
+	and.32      %r41 <- %r39, $0xfffffff8
+	or.32       %r42 <- %r41, %r40
+	store.32    %r42 -> 0[%r33]
+	zext.32     %r43 <- (3) %r36
+	phisrc.32   %phi3(return) <- %r43
 	br          .L7
 
 .L7:
-	phi.32      %r38 <- %phi3(return)
-	ret.32      %r38
+	phi.32      %r44 <- %phi3(return)
+	ret.32      %r44
 
 
 spreinc:
 .L8:
 	<entry-point>
 	store.64    %arg1 -> 0[x]
-	load.64     %r39 <- 0[x]
-	load.32     %r40 <- 0[%r39]
-	trunc.3     %r41 <- (32) %r40
-	add.3       %r42 <- %r41, $1
-	load.32     %r43 <- 0[%r39]
-	zext.32     %r44 <- (3) %r42
-	and.32      %r45 <- %r43, $0xfffffff8
-	or.32       %r46 <- %r45, %r44
-	store.32    %r46 -> 0[%r39]
-	zext.32     %r47 <- (3) %r42
-	phisrc.32   %phi4(return) <- %r47
+	load.64     %r45 <- 0[x]
+	load.32     %r46 <- 0[%r45]
+	trunc.3     %r47 <- (32) %r46
+	zext.32     %r48 <- (3) %r47
+	add.32      %r49 <- %r48, $1
+	trunc.3     %r50 <- (32) %r49
+	load.32     %r51 <- 0[%r45]
+	zext.32     %r52 <- (3) %r50
+	and.32      %r53 <- %r51, $0xfffffff8
+	or.32       %r54 <- %r53, %r52
+	store.32    %r54 -> 0[%r45]
+	zext.32     %r55 <- (3) %r50
+	phisrc.32   %phi4(return) <- %r55
 	br          .L9
 
 .L9:
-	phi.32      %r48 <- %phi4(return)
-	ret.32      %r48
+	phi.32      %r56 <- %phi4(return)
+	ret.32      %r56
 
 
 scpy:
@@ -155,15 +163,15 @@ scpy:
 	<entry-point>
 	store.64    %arg1 -> 0[d]
 	store.64    %arg2 -> 0[s]
-	load.64     %r49 <- 0[s]
-	load.32     %r50 <- 0[%r49]
-	trunc.3     %r51 <- (32) %r50
-	load.64     %r52 <- 0[d]
-	load.32     %r53 <- 0[%r52]
-	zext.32     %r54 <- (3) %r51
-	and.32      %r55 <- %r53, $0xfffffff8
-	or.32       %r56 <- %r55, %r54
-	store.32    %r56 -> 0[%r52]
+	load.64     %r57 <- 0[s]
+	load.32     %r58 <- 0[%r57]
+	trunc.3     %r59 <- (32) %r58
+	load.64     %r60 <- 0[d]
+	load.32     %r61 <- 0[%r60]
+	zext.32     %r62 <- (3) %r59
+	and.32      %r63 <- %r61, $0xfffffff8
+	or.32       %r64 <- %r63, %r62
+	store.32    %r64 -> 0[%r60]
 	br          .L11
 
 .L11:
diff --git a/validation/optim/and-lsr.c b/validation/optim/and-lsr.c
index df6b72f3..439eb822 100644
--- a/validation/optim/and-lsr.c
+++ b/validation/optim/and-lsr.c
@@ -8,7 +8,6 @@ unsigned int foo(unsigned int x)
 /*
  * check-name: and-lsr
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: and\\..*\\$15
diff --git a/validation/optim/mask-lsr.c b/validation/optim/mask-lsr.c
index 1d37c91e..ec636444 100644
--- a/validation/optim/mask-lsr.c
+++ b/validation/optim/mask-lsr.c
@@ -8,7 +8,6 @@ unsigned int foo(unsigned int x, unsigned int y)
 /*
  * check-name: mask-lsr
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: %arg1
diff --git a/validation/optim/mask-out.c b/validation/optim/mask-out.c
index bf116873..ac85aec8 100644
--- a/validation/optim/mask-out.c
+++ b/validation/optim/mask-out.c
@@ -6,7 +6,6 @@ unsigned mask(unsigned a, unsigned b)
 /*
  * check-name: mask-out
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: %arg1
diff --git a/validation/optim/shift-zext.c b/validation/optim/shift-zext.c
index 070416f3..30409bec 100644
--- a/validation/optim/shift-zext.c
+++ b/validation/optim/shift-zext.c
@@ -6,7 +6,6 @@ unsigned int foo(unsigned int x)
 /*
  * check-name: shift-zext
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: and\\..*%arg1, \\$0xfff
diff --git a/validation/optim/shl-lsr.c b/validation/optim/shl-lsr.c
new file mode 100644
index 00000000..4f4b7e66
--- /dev/null
+++ b/validation/optim/shl-lsr.c
@@ -0,0 +1,14 @@
+unsigned mask(unsigned x)
+{
+	return (x << 15) >> 15;
+}
+
+/*
+ * check-name: shl-lsr
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-contains: and\\..*0x1ffff
+ * check-output-excludes: lsr\\.
+ * check-output-excludes: shl\\.
+ */
diff --git a/validation/optim/store-load-bitfield.c b/validation/optim/store-load-bitfield.c
index 1d8ff240..f68cb600 100644
--- a/validation/optim/store-load-bitfield.c
+++ b/validation/optim/store-load-bitfield.c
@@ -28,21 +28,15 @@ int sfoo(int a)
 ufoo:
 .L0:
 	<entry-point>
-	and.32      %r4 <- %arg1, $7
-	shl.32      %r5 <- %r4, $2
-	lsr.32      %r9 <- %r5, $2
-	and.32      %r11 <- %r9, $7
+	and.32      %r11 <- %arg1, $7
 	ret.32      %r11
 
 
 sfoo:
 .L2:
 	<entry-point>
-	and.32      %r16 <- %arg1, $7
-	shl.32      %r17 <- %r16, $2
-	lsr.32      %r21 <- %r17, $2
-	trunc.3     %r22 <- (32) %r21
-	sext.32     %r23 <- (3) %r22
+	trunc.3     %r16 <- (32) %arg1
+	sext.32     %r23 <- (3) %r16
 	ret.32      %r23