better encodings for funnel shifts
MODIFY
smt/expr.cpp
smt/expr.cpp
@@ -576,18 +576,16 @@ expr expr::lshr(const expr &rhs) const {
expr expr::fshl(const expr &a, const expr &b, const expr &c) {
C2(a);
- auto nbits = a.bits();
- expr c_mod_width = c.urem(mkUInt(nbits, nbits)).zext(nbits);
- expr res = a.concat(b) << c_mod_width;
- return res.extract(2 * nbits - 1, nbits); // upper half (MSB)
+ auto width = mkUInt(a.bits(), a.bits());
+ expr c_mod_width = c.urem(width);
+ return a << c_mod_width | b.lshr(width - c_mod_width);
}
expr expr::fshr(const expr &a, const expr &b, const expr &c) {
C2(a);
- auto nbits = a.bits();
- expr c_mod_width = c.urem(mkUInt(nbits, nbits)).zext(nbits);
- expr res = a.concat(b).lshr(c_mod_width);
- return res.extract(nbits - 1, 0); // lower half (LSB)
+ auto width = mkUInt(a.bits(), a.bits());
+ expr c_mod_width = c.urem(width);
+ return a << (width - c_mod_width) | b.lshr(c_mod_width);
}
expr expr::shl_no_soverflow(const expr &rhs) const {

ADD
tests/unit/fshl/folds32.opt
+Name: single shift by masked value
+%c_mod_width = urem i32 %c, i32 32
+%t = shl i32 %a, i32 %c_mod_width
+ =>
+%t = fshl i32 %a, i32 0, i32 %c
+
+Name: single shift by value
+%t = shl i32 %a, i32 %c
+ =>
+%t = fshl i32 %a, i32 0, i32 %c
+
+Name: rotate by masked value
+%c_mod_width = urem i32 %c, 32
+%neg_c_mod_width = sub i32 32, %c_mod_width
+%highpart = shl i32 %a, %c_mod_width
+%lowpart = lshr i32 %a, %neg_c_mod_width
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshl i32 %a, i32 %a, i32 %c
+
+Name: rotate by value
+%neg_c = sub i32 32, %c
+%highpart = shl i32 %a, %c
+%lowpart = lshr i32 %a, %neg_c
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshl i32 %a, i32 %a, i32 %c
+
+Name: funnel shift by masked value
+%c_mod_width = urem i32 %c, 32
+%neg_c_mod_width = sub i32 32, %c_mod_width
+%highpart = shl i32 %a, %c_mod_width
+%lowpart = lshr i32 %b, %neg_c_mod_width
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshl i32 %a, i32 %b, i32 %c
+
+Name: funnel shift by value
+%neg_c = sub i32 32, %c
+%highpart = shl i32 %a, %c
+%lowpart = lshr i32 %b, %neg_c
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshl i32 %a, i32 %b, i32 %c

ADD
tests/unit/fshr/folds32.opt
+Name: single shift by masked value
+%c_mod_width = urem i4 %c, i4 4
+%t = lshr i4 %b, i4 %c_mod_width
+ =>
+%t = fshr i4 0, i4 %b, i4 %c
+
+Name: single shift by value
+%t = lshr i32 %b, i32 %c
+ =>
+%t = fshr i32 0, i32 %b, i32 %c
+
+Name: rotate by masked value
+%c_mod_width = urem i32 %c, 32
+%neg_c_mod_width = sub i32 32, %c_mod_width
+%highpart = shl i32 %b, %neg_c_mod_width
+%lowpart = lshr i32 %b, %c_mod_width
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshr i32 %b, i32 %b, i32 %c
+
+Name: rotate by value
+%neg_c = sub i32 32, %c
+%highpart = shl i32 %b, %neg_c
+%lowpart = lshr i32 %b, %c
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshr i32 %b, i32 %b, i32 %c
+
+Name: funnel shift by masked value
+%c_mod_width = urem i32 %c, 32
+%neg_c_mod_width = sub i32 32, %c_mod_width
+%highpart = shl i32 %a, %neg_c_mod_width
+%lowpart = lshr i32 %b, %c_mod_width
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshr i32 %a, i32 %b, i32 %c
+
+Name: funnel shift by value
+%neg_c = sub i32 32, %c
+%highpart = shl i32 %a, %neg_c
+%lowpart = lshr i32 %b, %c
+%t = or i32 %highpart, %lowpart
+ =>
+%t = fshr i32 %a, i32 %b, i32 %c

better encodings for funnel shifts (#143)