Repository: bytecodealliance/wasmtime (rust)

Issue:
Cranelift: "register allocation: SSA(VReg(vreg = 145, class = Int), Inst(0))" in upcoming 0.93 when compiling with optimizations
### `.clif` Test Case

```
test compile
set opt_level=speed_and_size
target aarch64

function u0:33() system_v {
    ss0 = explicit_slot 32
    sig0 = (i64, i64, i64, i64, i64) -> i64, i64 system_v
    fn0 = colocated u0:0 sig0
    jt0 = jump_table [block36, block38]

block0:
    v80 = iconst.i32 0
    v91 = iconst.i64 0
    v92 = iconst.i64 0
    v96 = iconst.i64 0
    v235 = iconst.i64 0
    v236 = iconst.i64 0
    v237 = iconst.i64 0
    v238, v239 = call fn0(v236, v237, v91, v92, v235)  ; v236 = 0, v237 = 0, v91 = 0, v92 = 0, v235 = 0
    v97 = iadd v238, v96  ; v96 = 0
    br_table v80, block37, jt0  ; v80 = 0

block36:
    trap user0

block37:
    trap unreachable

block38:
    v98 = load.i8 notrap v97
    v99 = fcvt_from_uint.f64 v98
    stack_store v99, ss0
    trap user0
}
```

### Steps to Reproduce

* `clif-util test repro.clif`

### Expected Results

Compiles

### Actual Results

Regalloc checker error: `register allocation: SSA(VReg(vreg = 145, class = Int), Inst(0))`

### Versions and Environment

Cranelift version or commit: Cranelift 0.93 (43022c862a1d497f4b8c7c2fce47148775503add on the release-6.0.0 branch) which is not yet released.

Operating system: Linux

Architecture: AArch64

Pull request:
egraphs: fix accidental remat of call.
In the provided test case in #5716, the result of a call was then added to 0. We have a rewrite rule that sets the remat-bit on any add of a value and a constant, because these frequently appear (e.g. from address offset calculations) and this can frequently reduce register pressure (one long-lived base vs. many long-lived base+offset values). Separately, we have an algebraic rule that `x+0` rewrites to `x`.

The result of this was that we had an eclass with the remat bit set on the add, but the add was also union'd into the call. We pick the latter during extraction, because it's cheaper not to do the add at all; but we still get the remat bit, and try to remat a call (!), which blows up later.

This PR fixes the logic to look up the "best value" for a value (i.e., whatever extraction determined), and look up the remat bit on *that* node, not the canonical node.

(Why did the canonical node become the iadd and not the call? Because the former had a lower value-number, as an accident of IR construction; we don't impose any requirements on the input CLIF's value-number ordering, and I don't think this breaks any of the important acyclic properties, even though there is technically a dependence from a lower-numbered to a higher-numbered node. In essence one can think of them as having "virtual numbers" in any true topologically-sorted order, and the only place the actual integer indices matter should be in choosing the "canonical ID", which is just used for dedup'ing, modulo this bug.)

Fixes #5716.

<!--

Please ensure that the following steps are all taken care of before submitting
the PR.

- [ ] This has been discussed in issue #..., or if not, please tell us why
  here.
- [ ] A short description of what this does, why it is needed; if the
  description becomes long, the matter should probably be discussed in an issue
  first.
- [ ] This PR contains test cases, if meaningful.
- [ ] A reviewer from the core maintainer team has been assigned for this PR.
  If you don't know who could review this, please indicate so. The list of
  suggested reviewers on the right can help you.

Please ensure all communication adheres to the [code of
conduct](https://github.com/bytecodealliance/wasmtime/blob/master/CODE_OF_CONDUCT.md).
-->


Patch:
diff --git a/cranelift/codegen/src/egraph/elaborate.rs b/cranelift/codegen/src/egraph/elaborate.rs
index 68f4238cf..d52927ffe 100644
--- a/cranelift/codegen/src/egraph/elaborate.rs
+++ b/cranelift/codegen/src/egraph/elaborate.rs
@@ -278,6 +278,14 @@ impl<'a> Elaborator<'a> {
                         before
                     );
 
+                    // Get the best option; we use `value` (latest
+                    // value) here so we have a full view of the
+                    // eclass.
+                    trace!("looking up best value for {}", value);
+                    let (_, best_value) = self.value_to_best_value[value];
+                    debug_assert_ne!(best_value, Value::reserved_value());
+                    trace!("elaborate: value {} -> best {}", value, best_value);
+
                     let remat = if let Some(elab_val) =
                         self.value_to_elaborated_value.get(&canonical_value)
                     {
@@ -287,7 +295,7 @@ impl<'a> Elaborator<'a> {
                         // from another block. If so, ignore the hit
                         // and recompute below.
                         let remat = elab_val.in_block != self.cur_block
-                            && self.remat_values.contains(&canonical_value);
+                            && self.remat_values.contains(&best_value);
                         if !remat {
                             trace!("elaborate: value {} -> {:?}", value, elab_val);
                             self.stats.elaborate_memoize_hit += 1;
@@ -304,20 +312,12 @@ impl<'a> Elaborator<'a> {
                         // Value not available; but still look up
                         // whether it's been flagged for remat because
                         // this affects placement.
-                        let remat = self.remat_values.contains(&canonical_value);
+                        let remat = self.remat_values.contains(&best_value);
                         trace!(" -> not present in map; remat = {}", remat);
                         remat
                     };
                     self.stats.elaborate_memoize_miss += 1;
 
-                    // Get the best option; we use `value` (latest
-                    // value) here so we have a full view of the
-                    // eclass.
-                    trace!("looking up best value for {}", value);
-                    let (_, best_value) = self.value_to_best_value[value];
-                    debug_assert_ne!(best_value, Value::reserved_value());
-                    trace!("elaborate: value {} -> best {}", value, best_value,);
-
                     // Now resolve the value to its definition to see
                     // how we can compute it.
                     let (inst, result_idx) = match self.func.dfg.value_def(best_value) {
diff --git a/cranelift/isle/isle/src/lexer.rs b/cranelift/isle/isle/src/lexer.rs
index d76b1e16a..a69894449 100644
--- a/cranelift/isle/isle/src/lexer.rs
+++ b/cranelift/isle/isle/src/lexer.rs
@@ -232,7 +232,7 @@ impl<'a> Lexer<'a> {
                 debug_assert!(!s.is_empty());
                 Ok(Some((start_pos, Token::Symbol(s.to_string()))))
             }
-            c if (c >= b'0' && c <= b'9') || c == b'-' => {
+            c @ (b'0'..=b'9' | b'-') => {
                 let start_pos = self.pos();
                 let neg = if c == b'-' {
                     self.advance_pos();
@@ -258,16 +258,8 @@ impl<'a> Lexer<'a> {
                 // string-to-integer conversion.
                 let mut s = vec![];
                 while self.pos.offset < self.buf.len()
-                    && ((radix == 10
-                        && self.buf[self.pos.offset] >= b'0'
-                        && self.buf[self.pos.offset] <= b'9')
-                        || (radix == 16
-                            && ((self.buf[self.pos.offset] >= b'0'
-                                && self.buf[self.pos.offset] <= b'9')
-                                || (self.buf[self.pos.offset] >= b'a'
-                                    && self.buf[self.pos.offset] <= b'f')
-                                || (self.buf[self.pos.offset] >= b'A'
-                                    && self.buf[self.pos.offset] <= b'F')))
+                    && ((radix == 10 && self.buf[self.pos.offset].is_ascii_digit())
+                        || (radix == 16 && self.buf[self.pos.offset].is_ascii_hexdigit())
                         || self.buf[self.pos.offset] == b'_')
                 {
                     if self.buf[self.pos.offset] != b'_' {
diff --git a/cranelift/isle/isle/src/parser.rs b/cranelift/isle/isle/src/parser.rs
index a305d6ce9..583f952d7 100644
--- a/cranelift/isle/isle/src/parser.rs
+++ b/cranelift/isle/isle/src/parser.rs
@@ -45,7 +45,7 @@ impl<'a> Parser<'a> {
         }
     }
 
-    fn take<F: Fn(&Token) -> bool>(&mut self, f: F) -> Result<Token> {
+    fn expect<F: Fn(&Token) -> bool>(&mut self, f: F) -> Result<Token> {
         if let Some(&(pos, ref peek)) = self.lexer.peek() {
             if !f(peek) {
                 return Err(self.error(pos, format!("Unexpected token {:?}", peek)));
@@ -56,6 +56,17 @@ impl<'a> Parser<'a> {
         }
     }
 
+    fn eat<F: Fn(&Token) -> bool>(&mut self, f: F) -> Result<Option<Token>> {
+        if let Some(&(_pos, ref peek)) = self.lexer.peek() {
+            if !f(peek) {
+                return Ok(None);
+            }
+            Ok(Some(self.lexer.next()?.unwrap().1))
+        } else {
+            Ok(None) // EOF
+        }
+    }
+
     fn is<F: Fn(&Token) -> bool>(&self, f: F) -> bool {
         if let Some(&(_, ref peek)) = self.lexer.peek() {
             f(peek)
@@ -80,16 +91,10 @@ impl<'a> Parser<'a> {
         self.is(|tok| *tok == Token::At)
     }
     fn is_sym(&self) -> bool {
-        self.is(|tok| tok.is_sym())
+        self.is(Token::is_sym)
     }
     fn is_int(&self) -> bool {
-        self.is(|tok| tok.is_int())
-    }
-    fn is_sym_str(&self, s: &str) -> bool {
-        self.is(|tok| match tok {
-            &Token::Symbol(ref tok_s) if tok_s == s => true,
-            _ => false,
-        })
+        self.is(Token::is_int)
     }
 
     fn is_const(&self) -> bool {
@@ -99,25 +104,33 @@ impl<'a> Parser<'a> {
         })
     }
 
-    fn lparen(&mut self) -> Result<()> {
-        self.take(|tok| *tok == Token::LParen).map(|_| ())
+    fn expect_lparen(&mut self) -> Result<()> {
+        self.expect(|tok| *tok == Token::LParen).map(|_| ())
     }
-    fn rparen(&mut self) -> Result<()> {
-        self.take(|tok| *tok == Token::RParen).map(|_| ())
+    fn expect_rparen(&mut self) -> Result<()> {
+        self.expect(|tok| *tok == Token::RParen).map(|_| ())
     }
-    fn at(&mut self) -> Result<()> {
-        self.take(|tok| *tok == Token::At).map(|_| ())
+    fn expect_at(&mut self) -> Result<()> {
+        self.expect(|tok| *tok == Token::At).map(|_| ())
     }
 
-    fn symbol(&mut self) -> Result<String> {
-        match self.take(|tok| tok.is_sym())? {
+    fn expect_symbol(&mut self) -> Result<String> {
+        match self.expect(Token::is_sym)? {
             Token::Symbol(s) => Ok(s),
             _ => unreachable!(),
         }
     }
 
-    fn int(&mut self) -> Result<i128> {
-        match self.take(|tok| tok.is_int())? {
+    fn eat_sym_str(&mut self, s: &str) -> Result<bool> {
+        self.eat(|tok| match tok {
+            &Token::Symbol(ref tok_s) if tok_s == s => true,
+            _ => false,
+        })
+        .map(|token| token.is_some())
+    }
+
+    fn expect_int(&mut self) -> Result<i128> {
+        match self.expect(Token::is_int)? {
             Token::Int(i) => Ok(i),
             _ => unreachable!(),
         }
@@ -136,9 +149,9 @@ impl<'a> Parser<'a> {
     }
 
     fn parse_def(&mut self) -> Result<Def> {
-        self.lparen()?;
+        self.expect_lparen()?;
         let pos = self.pos();
-        let def = match &self.symbol()?[..] {
+        let def = match &self.expect_symbol()?[..] {
             "pragma" => Def::Pragma(self.parse_pragma()?),
             "type" => Def::Type(self.parse_type()?),
             "decl" => Def::Decl(self.parse_decl()?),
@@ -150,7 +163,7 @@ impl<'a> Parser<'a> {
                 return Err(self.error(pos, format!("Unexpected identifier: {}", s)));
             }
         };
-        self.rparen()?;
+        self.expect_rparen()?;
         Ok(def)
     }
 
@@ -182,7 +195,7 @@ impl<'a> Parser<'a> {
 
     fn parse_ident(&mut self) -> Result<Ident> {
         let pos = self.pos();
-        let s = self.symbol()?;
+        let s = self.expect_symbol()?;
         self.str_to_ident(pos, &s)
     }
 
@@ -216,7 +229,7 @@ impl<'a> Parser<'a> {
         let mut is_nodebug = false;
 
         while self.lexer.peek().map_or(false, |(_pos, tok)| tok.is_sym()) {
-            let sym = self.symbol()?;
+            let sym = self.expect_symbol()?;
             if sym == "extern" {
                 is_extern = true;
             } else if sym == "nodebug" {
@@ -241,20 +254,18 @@ impl<'a> Parser<'a> {
 
     fn parse_typevalue(&mut self) -> Result<TypeValue> {
         let pos = self.pos();
-        self.lparen()?;
-        if self.is_sym_str("primitive") {
-            self.symbol()?;
+        self.expect_lparen()?;
+        if self.eat_sym_str("primitive")? {
             let primitive_ident = self.parse_ident()?;
-            self.rparen()?;
+            self.expect_rparen()?;
             Ok(TypeValue::Primitive(primitive_ident, pos))
-        } else if self.is_sym_str("enum") {
-            self.symbol()?;
+        } else if self.eat_sym_str("enum")? {
             let mut variants = vec![];
             while !self.is_rparen() {
                 let variant = self.parse_type_variant()?;
                 variants.push(variant);
             }
-            self.rparen()?;
+            self.expect_rparen()?;
             Ok(TypeValue::Enum(variants, pos))
         } else {
             Err(self.error(pos, "Unknown type definition".to_string()))
@@ -272,56 +283,41 @@ impl<'a> Parser<'a> {
             })
         } else {
             let pos = self.pos();
-            self.lparen()?;
+            self.expect_lparen()?;
             let name = self.parse_ident()?;
             let mut fields = vec![];
             while !self.is_rparen() {
                 fields.push(self.parse_type_field()?);
             }
-            self.rparen()?;
+            self.expect_rparen()?;
             Ok(Variant { name, fields, pos })
         }
     }
 
     fn parse_type_field(&mut self) -> Result<Field> {
         let pos = self.pos();
-        self.lparen()?;
+        self.expect_lparen()?;
         let name = self.parse_ident()?;
         let ty = self.parse_ident()?;
-        self.rparen()?;
+        self.expect_rparen()?;
         Ok(Field { name, ty, pos })
     }
 
     fn parse_decl(&mut self) -> Result<Decl> {
         let pos = self.pos();
 
-        let pure = if self.is_sym_str("pure") {
-            self.symbol()?;
-            true
-        } else {
-            false
-        };
-        let multi = if self.is_sym_str("multi") {
-            self.symbol()?;
-            true
-        } else {
-            false
-        };
-        let partial = if self.is_sym_str("partial") {
-            self.symbol()?;
-            true
-        } else {
-            false
-        };
+        let pure = self.eat_sym_str("pure")?;
+        let multi = self.eat_sym_str("multi")?;
+        let partial = self.eat_sym_str("partial")?;
 
         let term = self.parse_ident()?;
 
-        self.lparen()?;
+        self.expect_lparen()?;
         let mut arg_tys = vec![];
         while !self.is_rparen() {
             arg_tys.push(self.parse_ident()?);
         }
-        self.rparen()?;
+        self.expect_rparen()?;
 
         let ret_ty = self.parse_ident()?;
 
@@ -338,21 +334,12 @@ impl<'a> Parser<'a> {
 
     fn parse_extern(&mut self) -> Result<Extern> {
         let pos = self.pos();
-        if self.is_sym_str("constructor") {
-            self.symbol()?;
-
+        if self.eat_sym_str("constructor")? {
             let term = self.parse_ident()?;
             let func = self.parse_ident()?;
             Ok(Extern::Constructor { term, func, pos })
-        } else if self.is_sym_str("extractor") {
-            self.symbol()?;
-
-            let infallible = if self.is_sym_str("infallible") {
-                self.symbol()?;
-                true
-            } else {
-                false
-            };
+        } else if self.eat_sym_str("extractor")? {
+            let infallible = self.eat_sym_str("infallible")?;
 
             let term = self.parse_ident()?;
             let func = self.parse_ident()?;
@@ -363,8 +350,7 @@ impl<'a> Parser<'a> {
                 pos,
                 infallible,
             })
-        } else if self.is_sym_str("const") {
-            self.symbol()?;
+        } else if self.eat_sym_str("const")? {
             let pos = self.pos();
             let name = self.parse_const()?;
             let ty = self.parse_ident()?;
@@ -380,13 +366,13 @@ impl<'a> Parser<'a> {
 
     fn parse_etor(&mut self) -> Result<Extractor> {
         let pos = self.pos();
-        self.lparen()?;
+        self.expect_lparen()?;
         let term = self.parse_ident()?;
         let mut args = vec![];
         while !self.is_rparen() {
             args.push(self.parse_ident()?);
         }
-        self.rparen()?;
+        self.expect_rparen()?;
         let template = self.parse_pattern()?;
         Ok(Extractor {
             term,
@@ -400,7 +386,7 @@ impl<'a> Parser<'a> {
         let pos = self.pos();
         let prio = if self.is_int() {
             Some(
-                i64::try_from(self.int()?)
+                i64::try_from(self.expect_int()?)
                     .map_err(|err| self.error(pos, format!("Invalid rule priority: {}", err)))?,
             )
         } else {
@@ -430,34 +416,31 @@ impl<'a> Parser<'a> {
         let pos = self.pos();
         if self.is_int() {
             Ok(Pattern::ConstInt {
-                val: self.int()?,
+                val: self.expect_int()?,
                 pos,
             })
         } else if self.is_const() {
             let val = self.parse_const()?;
             Ok(Pattern::ConstPrim { val, pos })
-        } else if self.is_sym_str("_") {
-            self.symbol()?;
+        } else if self.eat_sym_str("_")? {
             Ok(Pattern::Wildcard { pos })
         } else if self.is_sym() {
-            let s = self.symbol()?;
-            let var = self.str_to_ident(pos, &s)?;
+            let var = self.parse_ident()?;
             if self.is_at() {
-                self.at()?;
+                self.expect_at()?;
                 let subpat = Box::new(self.parse_pattern()?);
                 Ok(Pattern::BindPattern { var, subpat, pos })
             } else {
                 Ok(Pattern::Var { var, pos })
             }
         } else if self.is_lparen() {
-            self.lparen()?;
-            if self.is_sym_str("and") {
-                self.symbol()?;
+            self.expect_lparen()?;
+            if self.eat_sym_str("and")? {
                 let mut subpats = vec![];
                 while !self.is_rparen() {
                     subpats.push(self.parse_pattern()?);
                 }
-                self.rparen()?;
+                self.expect_rparen()?;
                 Ok(Pattern::And { subpats, pos })
             } else {
                 let sym = self.parse_ident()?;
@@ -465,7 +448,7 @@ impl<'a> Parser<'a> {
                 while !self.is_rparen() {
                     args.push(self.parse_pattern()?);
                 }
-                self.rparen()?;
+                self.expect_rparen()?;
                 Ok(Pattern::Term { sym, args, pos })
             }
         } else {
@@ -476,19 +459,17 @@ impl<'a> Parser<'a> {
     fn parse_iflet_or_expr(&mut self) -> Result<IfLetOrExpr> {
         let pos = self.pos();
         if self.is_lparen() {
-            self.lparen()?;
-            let ret = if self.is_sym_str("if-let") {
-                self.symbol()?;
+            self.expect_lparen()?;
+            let ret = if self.eat_sym_str("if-let")? {
                 IfLetOrExpr::IfLet(self.parse_iflet()?)
-            } else if self.is_sym_str("if") {
+            } else if self.eat_sym_str("if")? {
                 // Shorthand form: `(if (x))` desugars to `(if-let _
                 // (x))`.
-                self.symbol()?;
                 IfLetOrExpr::IfLet(self.parse_iflet_if()?)
             } else {
                 IfLetOrExpr::Expr(self.parse_expr_inner_parens(pos)?)
             };
-            self.rparen()?;
+            self.expect_rparen()?;
             Ok(ret)
         } else {
             self.parse_expr().map(|expr| IfLetOrExpr::Expr(expr))
@@ -515,15 +496,13 @@ impl<'a> Parser<'a> {
     fn parse_expr(&mut self) -> Result<Expr> {
         let pos = self.pos();
         if self.is_lparen() {
-            self.lparen()?;
+            self.expect_lparen()?;
             let ret = self.parse_expr_inner_parens(pos)?;
-            self.rparen()?;
+            self.expect_rparen()?;
             Ok(ret)
-        } else if self.is_sym_str("#t") {
-            self.symbol()?;
+        } else if self.eat_sym_str("#t")? {
             Ok(Expr::ConstInt { val: 1, pos })
-        } else if self.is_sym_str("#f") {
-            self.symbol()?;
+        } else if self.eat_sym_str("#f")? {
             Ok(Expr::ConstInt { val: 0, pos })
         } else if self.is_const() {
             let val = self.parse_const()?;
@@ -532,7 +511,7 @@ impl<'a> Parser<'a> {
             let name = self.parse_ident()?;
             Ok(Expr::Var { name, pos })
         } else if self.is_int() {
-            let val = self.int()?;
+            let val = self.expect_int()?;
             Ok(Expr::ConstInt { val, pos })
         } else {
             Err(self.error(pos, "Invalid expression".into()))
@@ -540,15 +519,14 @@ impl<'a> Parser<'a> {
     }
 
     fn parse_expr_inner_parens(&mut self, pos: Pos) -> Result<Expr> {
-        if self.is_sym_str("let") {
-            self.symbol()?;
-            self.lparen()?;
+        if self.eat_sym_str("let")? {
+            self.expect_lparen()?;
             let mut defs = vec![];
             while !self.is_rparen() {
                 let def = self.parse_letdef()?;
                 defs.push(def);
             }
-            self.rparen()?;
+            self.expect_rparen()?;
             let body = Box::new(self.parse_expr()?);
             Ok(Expr::Let { defs, body, pos })
         } else {
@@ -563,11 +541,11 @@ impl<'a> Parser<'a> {
 
     fn parse_letdef(&mut self) -> Result<LetDef> {
         let pos = self.pos();
-        self.lparen()?;
+        self.expect_lparen()?;
         let var = self.parse_ident()?;
         let ty = self.parse_ident()?;
         let val = Box::new(self.parse_expr()?);
-        self.rparen()?;
+        self.expect_rparen()?;
         Ok(LetDef { var, ty, val, pos })
     }
 


Test patch:
diff --git a/cranelift/filetests/filetests/egraph/issue-5716.clif b/cranelift/filetests/filetests/egraph/issue-5716.clif
new file mode 100644
index 000000000..7763d3eac
--- /dev/null
+++ b/cranelift/filetests/filetests/egraph/issue-5716.clif
@@ -0,0 +1,41 @@
+;; This tests that a call does not get rematerialized, even if a remat flag is
+;; set on a different node in its eclass.
+;;
+;; Below, `v97` is an add of `v238` (the call's first return value) and a
+;; constant 0; a mid-end rule rewrites this to just `v238` (i.e., `v97` is unioned
+;; in). Separately, a rule states that an add of a value and a constant always
+;; gets rematerialized at use. When `v97` is used in a later block, it would have
+;; rematerialized the add; except, if we instead use the result of the call
+;; directly, we should *not* remat the call. If we do, a compile error results
+;; later.
+
+test compile
+set opt_level=speed_and_size
+target aarch64
+
+function u0:33() system_v {
+ss0 = explicit_slot 32
+sig0 = (i64, i64, i64, i64, i64) -> i64, i64 system_v
+fn0 = colocated u0:0 sig0
+jt0 = jump_table [block36, block38]
+block0:
+  v80 = iconst.i32 0
+  v91 = iconst.i64 0
+  v92 = iconst.i64 0
+  v96 = iconst.i64 0
+  v235 = iconst.i64 0
+  v236 = iconst.i64 0
+  v237 = iconst.i64 0
+  v238, v239 = call fn0(v236, v237, v91, v92, v235) ; v236 = 0, v237 = 0, v91 = 0, v92 = 0, v235 = 0
+  v97 = iadd v238, v96 ; v96 = 0
+  br_table v80, block37, jt0 ; v80 = 0
+block36:
+  trap user0
+block37:
+  trap unreachable
+block38:
+  v98 = load.i8 notrap v97
+  v99 = fcvt_from_uint.f64 v98
+  stack_store v99, ss0
+  trap user0
+}