[PATCH 8/9] simplify ((x & M) | (y << S)) >> S

[Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>]

This expression is simplified into:
	 ((x >> S) & M') | (y & M'')
with M' = (M >> S) and M'' = (~0 >> S)

This is a rather complex and specialized simplification but
it is the first of a two steps process to simplify some
bitfield acceesses. More exactly, the access is the store/reload
of a bitfield which is otherwise potentially uninitialized.
The next step will be the simplification of:
	 ((((x >> S) & M') | (y & M'')) & M'''
where (M' & M''') = 0. Then the whole expression is reduced to:
	 (y & (M'' & M'''))
which doesn't use x (potentially unintialized, or simply unknown).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
 simplify.c | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/simplify.c b/simplify.c
index e58c97c08..baea32378 100644
--- a/simplify.c
+++ b/simplify.c
@@ -580,11 +580,38 @@ static int simplify_or_lsr(struct instruction *insn, pseudo_t src, pseudo_t othe
 	// src->def->opcode == OP_AND
 	struct instruction *insn2 = src->def;
 	pseudo_t src2 = insn2->src2;
+	struct instruction *insn3;
 
 	if (!constant(src2))
 		return 0;
 	if ((((unsigned long long)src2->value) >> shift) == 0)
 		return replace_pseudo(insn, &insn->src1, other);
+	if (DEF_OPCODE(insn3, other) == OP_SHL && constant(insn3->src2)
+	    && insn3->src2->value == shift && nbr_users(src) == 1
+	    && nbr_users(other) == 1 && nbr_users(insn->src1) == 1) {
+		struct instruction *insn1 = insn->src1->def;
+		unsigned long long mask = insn2->src2->value;
+		unsigned size = insn->size;
+
+		// simplify ((x & M) | (y << S)) >> S
+		// into     ((x >> S) & M') | (y & M'')
+		// where M' = (M >> S) and M'' = (~0 >> S)
+
+		insn3->opcode = OP_AND;
+		insn3->src2 = value_pseudo(bits_mask(size - shift));
+
+		insn2->opcode = OP_LSR;
+		insn2->src2 = value_pseudo(shift);
+
+		insn1->opcode = OP_AND;
+		insn1->src2 = value_pseudo(mask >> shift);
+
+		insn->opcode = OP_OR;
+		use_pseudo(insn, other, &insn->src2);
+		remove_usage(other, &insn1->src2);
+
+		return REPEAT_CSE;
+	}
 	return 0;
 }
 
-- 
2.18.0

--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html