Add memoization for const function evaluations

When a const function is being evaluated, as long as all its
arguments are zero-sized-types (or it has no arguments) then we
can trivially memoize the evaluation result using the existing
query mechanism.

10 files changed, 101 insertions, 132 deletions

diff --git a/src/librustc/mir/interpret/mod.rs b/src/librustc/mir/interpret/mod.rs
index 31c50610ac4..65f4ee88a9c 100644
--- a/src/librustc/mir/interpret/mod.rs
+++ b/src/librustc/mir/interpret/mod.rs
@@ -123,7 +123,10 @@ use rustc_data_structures::tiny_list::TinyList;
 use rustc_macros::HashStable;
 use byteorder::{WriteBytesExt, ReadBytesExt, LittleEndian, BigEndian};
 
-/// Uniquely identifies a specific constant or static.
+/// Uniquely identifies one of the following:
+/// - A constant
+/// - A static
+/// - A const fn where all arguments (if any) are zero-sized types
 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, RustcEncodable, RustcDecodable)]
 #[derive(HashStable, Lift)]
 pub struct GlobalId<'tcx> {
diff --git a/src/librustc_mir/const_eval.rs b/src/librustc_mir/const_eval.rs
index 640b5fbdff3..3352f7ae658 100644
--- a/src/librustc_mir/const_eval.rs
+++ b/src/librustc_mir/const_eval.rs
@@ -146,7 +146,16 @@ fn eval_body_using_ecx<'mir, 'tcx>(
     let name = ty::tls::with(|tcx| tcx.def_path_str(cid.instance.def_id()));
     let prom = cid.promoted.map_or(String::new(), |p| format!("::promoted[{:?}]", p));
     trace!("eval_body_using_ecx: pushing stack frame for global: {}{}", name, prom);
-    assert!(body.arg_count == 0);
+
+    // Assert all args (if any) are zero-sized types; `eval_body_using_ecx` doesn't
+    // make sense if the body is expecting nontrival arguments.
+    // (The alternative would be to use `eval_fn_call` with an args slice.)
+    for arg in body.args_iter() {
+        let decl = body.local_decls.get(arg).expect("arg missing from local_decls");
+        let layout = ecx.layout_of(decl.ty.subst(tcx, cid.instance.substs))?;
+        assert!(layout.is_zst())
+    };
+
     ecx.push_stack_frame(
         cid.instance,
         body.span,
diff --git a/src/librustc_mir/interpret/terminator.rs b/src/librustc_mir/interpret/terminator.rs
index daa0a5e1bc4..7285836d1c3 100644
--- a/src/librustc_mir/interpret/terminator.rs
+++ b/src/librustc_mir/interpret/terminator.rs
@@ -7,7 +7,7 @@ use syntax::source_map::Span;
 use rustc_target::spec::abi::Abi;
 
 use super::{
-    InterpResult, PointerArithmetic,
+    GlobalId, InterpResult, PointerArithmetic,
     InterpCx, Machine, OpTy, ImmTy, PlaceTy, MPlaceTy, StackPopCleanup, FnVal,
 };
 
@@ -284,6 +284,18 @@ impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
             ty::InstanceDef::DropGlue(..) |
             ty::InstanceDef::CloneShim(..) |
             ty::InstanceDef::Item(_) => {
+                // If this function is a `const fn` then as an optimization we can query this
+                // evaluation immediately.
+                //
+                // For the moment we only do this for functions which take no arguments
+                // (or all arguments are ZSTs) so that we don't memoize too much.
+                if self.tcx.is_const_fn_raw(instance.def.def_id()) &&
+                   args.iter().all(|a| a.layout.is_zst())
+                {
+                    let gid = GlobalId { instance, promoted: None };
+                    return self.eval_const_fn_call(gid, ret);
+                }
+
                 // We need MIR for this fn
                 let body = match M::find_fn(self, instance, args, ret, unwind)? {
                     Some(body) => body,
@@ -449,6 +461,25 @@ impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
         }
     }
 
+    /// Evaluate a const function where all arguments (if any) are zero-sized types.
+    /// The evaluation is memoized thanks to the query system.
+    fn eval_const_fn_call(
+        &mut self,
+        gid: GlobalId<'tcx>,
+        ret: Option<(PlaceTy<'tcx, M::PointerTag>, mir::BasicBlock)>,
+    ) -> InterpResult<'tcx> {
+        trace!("eval_const_fn_call: {:?}", gid);
+
+        let place = self.const_eval_raw(gid)?;
+        let dest = ret.ok_or_else(|| err_ub!(Unreachable))?.0;
+
+        self.copy_op(place.into(), dest)?;
+
+        self.return_to_block(ret.map(|r| r.1))?;
+        self.dump_place(*dest);
+        return Ok(())
+    }
+
     fn drop_in_place(
         &mut self,
         place: PlaceTy<'tcx, M::PointerTag>,
diff --git a/src/test/ui/consts/const-fn-zst-args.rs b/src/test/ui/consts/const-fn-zst-args.rs
new file mode 100644
index 00000000000..82c27b37573
--- /dev/null
+++ b/src/test/ui/consts/const-fn-zst-args.rs
@@ -0,0 +1,14 @@
+// build-pass
+
+// Check that the evaluation of const-functions with
+// zero-sized types as arguments compiles successfully
+
+struct Zst {}
+
+const fn foo(val: Zst) -> Zst { val }
+
+const FOO: Zst = foo(Zst {});
+
+fn main() {
+    const _: Zst = FOO;
+}
diff --git a/src/test/ui/consts/const-size_of-cycle.stderr b/src/test/ui/consts/const-size_of-cycle.stderr
index 5b06ade44c5..db1932a9209 100644
--- a/src/test/ui/consts/const-size_of-cycle.stderr
+++ b/src/test/ui/consts/const-size_of-cycle.stderr
@@ -10,6 +10,11 @@ note: ...which requires const-evaluating + checking `Foo::bytes::{{constant}}#0`
 LL |     bytes: [u8; std::mem::size_of::<Foo>()]
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^
 note: ...which requires const-evaluating `Foo::bytes::{{constant}}#0`...
+  --> $DIR/const-size_of-cycle.rs:5:17
+   |
+LL |     bytes: [u8; std::mem::size_of::<Foo>()]
+   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^
+note: ...which requires const-evaluating `std::mem::size_of`...
   --> $SRC_DIR/libcore/mem/mod.rs:LL:COL
    |
 LL |     intrinsics::size_of::<T>()
diff --git a/src/test/ui/consts/uninhabited-const-issue-61744.rs b/src/test/ui/consts/uninhabited-const-issue-61744.rs
index 4509ebc6338..e10b38a614a 100644
--- a/src/test/ui/consts/uninhabited-const-issue-61744.rs
+++ b/src/test/ui/consts/uninhabited-const-issue-61744.rs
@@ -1,11 +1,11 @@
 // compile-fail
 
 pub const unsafe fn fake_type<T>() -> T {
-    hint_unreachable() //~ ERROR any use of this value will cause an error
+    hint_unreachable()
 }
 
 pub const unsafe fn hint_unreachable() -> ! {
-    fake_type()
+    fake_type() //~ ERROR cycle detected when const-evaluating `hint_unreachable` [E0391]
 }
 
 trait Const {
@@ -15,5 +15,5 @@ trait Const {
 impl <T> Const for T {}
 
 pub fn main() -> () {
-    dbg!(i32::CONSTANT); //~ ERROR erroneous constant used
+    dbg!(i32::CONSTANT);
 }
diff --git a/src/test/ui/consts/uninhabited-const-issue-61744.stderr b/src/test/ui/consts/uninhabited-const-issue-61744.stderr
index f390676fda6..2a25ecc55e8 100644
--- a/src/test/ui/consts/uninhabited-const-issue-61744.stderr
+++ b/src/test/ui/consts/uninhabited-const-issue-61744.stderr
@@ -1,73 +1,21 @@
-error: any use of this value will cause an error
+error[E0391]: cycle detected when const-evaluating `hint_unreachable`
+  --> $DIR/uninhabited-const-issue-61744.rs:8:5
+   |
+LL |     fake_type()
+   |     ^^^^^^^^^^^
+   |
+note: ...which requires const-evaluating `fake_type`...
   --> $DIR/uninhabited-const-issue-61744.rs:4:5
    |
 LL |     hint_unreachable()
    |     ^^^^^^^^^^^^^^^^^^
-   |     |
-   |     reached the configured maximum number of stack frames
-   |     inside call to `hint_unreachable` at $DIR/uninhabited-const-issue-61744.rs:4:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<!>` at $DIR/uninhabited-const-issue-61744.rs:8:5
-   |     inside call to `fake_type::<i32>` at $DIR/uninhabited-const-issue-61744.rs:12:36
-...
-LL |     const CONSTANT: i32 = unsafe { fake_type() };
-   |     ---------------------------------------------
-   |
-   = note: `#[deny(const_err)]` on by default
-
-error[E0080]: erroneous constant used
-  --> $DIR/uninhabited-const-issue-61744.rs:18:10
+   = note: ...which again requires const-evaluating `hint_unreachable`, completing the cycle
+note: cycle used when const-evaluating `fake_type`
+  --> $DIR/uninhabited-const-issue-61744.rs:4:5
    |
-LL |     dbg!(i32::CONSTANT);
-   |          ^^^^^^^^^^^^^ referenced constant has errors
+LL |     hint_unreachable()
+   |     ^^^^^^^^^^^^^^^^^^
 
-error: aborting due to 2 previous errors
+error: aborting due to previous error
 
-For more information about this error, try `rustc --explain E0080`.
+For more information about this error, try `rustc --explain E0391`.
diff --git a/src/test/ui/infinite/infinite-recursion-const-fn.rs b/src/test/ui/infinite/infinite-recursion-const-fn.rs
index 020c417bf61..8289a3db6fc 100644
--- a/src/test/ui/infinite/infinite-recursion-const-fn.rs
+++ b/src/test/ui/infinite/infinite-recursion-const-fn.rs
@@ -1,6 +1,6 @@
 //https://github.com/rust-lang/rust/issues/31364
 
-const fn a() -> usize { b() } //~ ERROR evaluation of constant value failed
+const fn a() -> usize { b() } //~ ERROR cycle detected when const-evaluating `a` [E0391]
 const fn b() -> usize { a() }
 const ARR: [i32; a()] = [5; 6];
 
diff --git a/src/test/ui/infinite/infinite-recursion-const-fn.stderr b/src/test/ui/infinite/infinite-recursion-const-fn.stderr
index 9e0530de425..6bd5e035f57 100644
--- a/src/test/ui/infinite/infinite-recursion-const-fn.stderr
+++ b/src/test/ui/infinite/infinite-recursion-const-fn.stderr
@@ -1,66 +1,21 @@
-error[E0080]: evaluation of constant value failed
+error[E0391]: cycle detected when const-evaluating `a`
   --> $DIR/infinite-recursion-const-fn.rs:3:25
    |
 LL | const fn a() -> usize { b() }
    |                         ^^^
-   |                         |
-   |                         reached the configured maximum number of stack frames
-   |                         inside call to `b` at $DIR/infinite-recursion-const-fn.rs:3:25
+   |
+note: ...which requires const-evaluating `b`...
+  --> $DIR/infinite-recursion-const-fn.rs:4:25
+   |
 LL | const fn b() -> usize { a() }
-   |                         ---
-   |                         |
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
-   |                         inside call to `a` at $DIR/infinite-recursion-const-fn.rs:4:25
+   |                         ^^^
+   = note: ...which again requires const-evaluating `a`, completing the cycle
+note: cycle used when const-evaluating `ARR::{{constant}}#0`
+  --> $DIR/infinite-recursion-const-fn.rs:5:18
+   |
 LL | const ARR: [i32; a()] = [5; 6];
-   |                  --- inside call to `a` at $DIR/infinite-recursion-const-fn.rs:5:18
+   |                  ^^^
 
 error: aborting due to previous error
 
-For more information about this error, try `rustc --explain E0080`.
+For more information about this error, try `rustc --explain E0391`.
diff --git a/src/test/ui/invalid_const_promotion.rs b/src/test/ui/invalid_const_promotion.rs
index 6d59bb385dc..91115ef74b8 100644
--- a/src/test/ui/invalid_const_promotion.rs
+++ b/src/test/ui/invalid_const_promotion.rs
@@ -17,12 +17,16 @@ use std::env;
 use std::process::{Command, Stdio};
 
 // this will panic in debug mode and overflow in release mode
+//
+// NB we give bar an unused argument because otherwise memoization
+// of the const fn kicks in, causing a different code path in the
+// compiler to be executed (see PR #66294).
 #[stable(feature = "rustc", since = "1.0.0")]
 #[rustc_promotable]
-const fn bar() -> usize { 0 - 1 }
+const fn bar(_: bool) -> usize { 0 - 1 }
 
 fn foo() {
-    let _: &'static _ = &bar();
+    let _: &'static _ = &bar(true);
 }
 
 #[cfg(unix)]