Auto merge of #44809 - arielb1:small-scope, r=eddyb

encode region::Scope using fewer bytes

Now that region::Scope is no longer interned, its size is more important. This PR encodes region::Scope in 8 bytes instead of 12, which should speed up region inference somewhat (perf testing needed) and should improve the margins on #36799 by 64MB (that's not a lot, I did this PR mostly to speed up region inference).

This is a perf-sensitive PR. Please don't roll me up.

r? @eddyb

This is based on  #44743 so I could get more accurate measurements on #36799.

6 files changed, 141 insertions, 47 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index e3ecaae953a..2bbf807807b 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -514,13 +514,8 @@ impl_stable_hash_for!(enum ty::cast::CastKind {
     FnPtrAddrCast
 });
 
-impl_stable_hash_for!(enum ::middle::region::Scope {
-    Node(local_id),
-    Destruction(local_id),
-    CallSite(local_id),
-    Arguments(local_id),
-    Remainder(block_remainder)
-});
+impl_stable_hash_for!(struct ::middle::region::FirstStatementIndex { idx });
+impl_stable_hash_for!(struct ::middle::region::Scope { id, code });
 
 impl<'gcx> ToStableHashKey<StableHashingContext<'gcx>> for region::Scope {
     type KeyType = region::Scope;
diff --git a/src/librustc/infer/error_reporting/mod.rs b/src/librustc/infer/error_reporting/mod.rs
index b24c9690a46..ead20b5eb5a 100644
--- a/src/librustc/infer/error_reporting/mod.rs
+++ b/src/librustc/infer/error_reporting/mod.rs
@@ -72,6 +72,8 @@ use syntax::ast::DUMMY_NODE_ID;
 use syntax_pos::{Pos, Span};
 use errors::{DiagnosticBuilder, DiagnosticStyledString};
 
+use rustc_data_structures::indexed_vec::Idx;
+
 mod note;
 
 mod need_type_info;
@@ -152,21 +154,21 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
                         return;
                     }
                 };
-                let scope_decorated_tag = match scope {
-                    region::Scope::Node(_) => tag,
-                    region::Scope::CallSite(_) => {
+                let scope_decorated_tag = match scope.data() {
+                    region::ScopeData::Node(_) => tag,
+                    region::ScopeData::CallSite(_) => {
                         "scope of call-site for function"
                     }
-                    region::Scope::Arguments(_) => {
+                    region::ScopeData::Arguments(_) => {
                         "scope of function body"
                     }
-                    region::Scope::Destruction(_) => {
+                    region::ScopeData::Destruction(_) => {
                         new_string = format!("destruction scope surrounding {}", tag);
                         &new_string[..]
                     }
-                    region::Scope::Remainder(r) => {
+                    region::ScopeData::Remainder(r) => {
                         new_string = format!("block suffix following statement {}",
-                                             r.first_statement_index);
+                                             r.first_statement_index.index());
                         &new_string[..]
                     }
                 };
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 6cce7447669..cede0c2b9a2 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -18,6 +18,7 @@ use ich::{StableHashingContext, NodeIdHashingMode};
 use util::nodemap::{FxHashMap, FxHashSet};
 use ty;
 
+use std::fmt;
 use std::mem;
 use std::rc::Rc;
 use syntax::codemap;
@@ -31,6 +32,7 @@ use hir::def_id::DefId;
 use hir::intravisit::{self, Visitor, NestedVisitorMap};
 use hir::{Block, Arm, Pat, PatKind, Stmt, Expr, Local};
 use mir::transform::MirSource;
+use rustc_data_structures::indexed_vec::Idx;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
                                            StableHasherResult};
 
@@ -95,8 +97,24 @@ use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
 /// placate the same deriving in `ty::FreeRegion`, but we may want to
 /// actually attach a more meaningful ordering to scopes than the one
 /// generated via deriving here.
+///
+/// Scope is a bit-packed to save space - if `code` is SCOPE_DATA_REMAINDER_MAX
+/// or less, it is a `ScopeData::Remainder`, otherwise it is a type specified
+/// by the bitpacking.
+#[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Copy, RustcEncodable, RustcDecodable)]
+pub struct Scope {
+    pub(crate) id: hir::ItemLocalId,
+    pub(crate) code: u32
+}
+
+const SCOPE_DATA_NODE: u32 = !0;
+const SCOPE_DATA_CALLSITE: u32 = !1;
+const SCOPE_DATA_ARGUMENTS: u32 = !2;
+const SCOPE_DATA_DESTRUCTION: u32 = !3;
+const SCOPE_DATA_REMAINDER_MAX: u32 = !4;
+
 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Debug, Copy, RustcEncodable, RustcDecodable)]
-pub enum Scope {
+pub enum ScopeData {
     Node(hir::ItemLocalId),
 
     // Scope of the call-site for a function or closure
@@ -135,7 +153,90 @@ pub enum Scope {
          RustcDecodable, Debug, Copy)]
 pub struct BlockRemainder {
     pub block: hir::ItemLocalId,
-    pub first_statement_index: u32,
+    pub first_statement_index: FirstStatementIndex,
+}
+
+#[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
+         RustcDecodable, Copy)]
+pub struct FirstStatementIndex { pub idx: u32 }
+
+impl Idx for FirstStatementIndex {
+    fn new(idx: usize) -> Self {
+        assert!(idx <= SCOPE_DATA_REMAINDER_MAX as usize);
+        FirstStatementIndex { idx: idx as u32 }
+    }
+
+    fn index(self) -> usize {
+        self.idx as usize
+    }
+}
+
+impl fmt::Debug for FirstStatementIndex {
+    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Debug::fmt(&self.index(), formatter)
+    }
+}
+
+impl From<ScopeData> for Scope {
+    #[inline]
+    fn from(scope_data: ScopeData) -> Self {
+        let (id, code) = match scope_data {
+            ScopeData::Node(id) => (id, SCOPE_DATA_NODE),
+            ScopeData::CallSite(id) => (id, SCOPE_DATA_CALLSITE),
+            ScopeData::Arguments(id) => (id, SCOPE_DATA_ARGUMENTS),
+            ScopeData::Destruction(id) => (id, SCOPE_DATA_DESTRUCTION),
+            ScopeData::Remainder(r) => (r.block, r.first_statement_index.index() as u32)
+        };
+        Self { id, code }
+    }
+}
+
+impl fmt::Debug for Scope {
+    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Debug::fmt(&self.data(), formatter)
+    }
+}
+
+#[allow(non_snake_case)]
+impl Scope {
+    #[inline]
+    pub fn data(self) -> ScopeData {
+        match self.code {
+            SCOPE_DATA_NODE => ScopeData::Node(self.id),
+            SCOPE_DATA_CALLSITE => ScopeData::CallSite(self.id),
+            SCOPE_DATA_ARGUMENTS => ScopeData::Arguments(self.id),
+            SCOPE_DATA_DESTRUCTION => ScopeData::Destruction(self.id),
+            idx => ScopeData::Remainder(BlockRemainder {
+                block: self.id,
+                first_statement_index: FirstStatementIndex { idx }
+            })
+        }
+    }
+
+    #[inline]
+    pub fn Node(id: hir::ItemLocalId) -> Self {
+        Self::from(ScopeData::Node(id))
+    }
+
+    #[inline]
+    pub fn CallSite(id: hir::ItemLocalId) -> Self {
+        Self::from(ScopeData::CallSite(id))
+    }
+
+    #[inline]
+    pub fn Arguments(id: hir::ItemLocalId) -> Self {
+        Self::from(ScopeData::Arguments(id))
+    }
+
+    #[inline]
+    pub fn Destruction(id: hir::ItemLocalId) -> Self {
+        Self::from(ScopeData::Destruction(id))
+    }
+
+    #[inline]
+    pub fn Remainder(r: BlockRemainder) -> Self {
+        Self::from(ScopeData::Remainder(r))
+    }
 }
 
 impl Scope {
@@ -144,16 +245,7 @@ impl Scope {
     /// NB: likely to be replaced as API is refined; e.g. pnkfelix
     /// anticipates `fn entry_node_id` and `fn each_exit_node_id`.
     pub fn item_local_id(&self) -> hir::ItemLocalId {
-        match *self {
-            Scope::Node(id) => id,
-
-            // These cases all return rough approximations to the
-            // precise scope denoted by `self`.
-            Scope::Remainder(br) => br.block,
-            Scope::Destruction(id) |
-            Scope::CallSite(id) |
-            Scope::Arguments(id) => id,
-        }
+        self.id
     }
 
     pub fn node_id(&self, tcx: TyCtxt, scope_tree: &ScopeTree) -> ast::NodeId {
@@ -177,7 +269,7 @@ impl Scope {
             return DUMMY_SP;
         }
         let span = tcx.hir.span(node_id);
-        if let Scope::Remainder(r) = *self {
+        if let ScopeData::Remainder(r) = self.data() {
             if let hir::map::NodeBlock(ref blk) = tcx.hir.get(node_id) {
                 // Want span for scope starting after the
                 // indexed statement and ending at end of
@@ -187,7 +279,7 @@ impl Scope {
                 // (This is the special case aluded to in the
                 // doc-comment for this method)
 
-                let stmt_span = blk.stmts[r.first_statement_index as usize].span;
+                let stmt_span = blk.stmts[r.first_statement_index.index()].span;
 
                 // To avoid issues with macro-generated spans, the span
                 // of the statement must be nested in that of the block.
@@ -387,7 +479,7 @@ impl<'tcx> ScopeTree {
         }
 
         // record the destruction scopes for later so we can query them
-        if let Scope::Destruction(n) = child {
+        if let ScopeData::Destruction(n) = child.data() {
             self.destruction_scopes.insert(n, child);
         }
     }
@@ -482,8 +574,8 @@ impl<'tcx> ScopeTree {
         let mut id = Scope::Node(expr_id);
 
         while let Some(&p) = self.parent_map.get(&id) {
-            match p {
-                Scope::Destruction(..) => {
+            match p.data() {
+                ScopeData::Destruction(..) => {
                     debug!("temporary_scope({:?}) = {:?} [enclosing]",
                            expr_id, id);
                     return Some(id);
@@ -573,9 +665,9 @@ impl<'tcx> ScopeTree {
             // infer::region_inference for more details.
             let a_root_scope = a_ancestors[a_index];
             let b_root_scope = a_ancestors[a_index];
-            return match (a_root_scope, b_root_scope) {
-                (Scope::Destruction(a_root_id),
-                 Scope::Destruction(b_root_id)) => {
+            return match (a_root_scope.data(), b_root_scope.data()) {
+                (ScopeData::Destruction(a_root_id),
+                 ScopeData::Destruction(b_root_id)) => {
                     if self.closure_is_enclosed_by(a_root_id, b_root_id) {
                         // `a` is enclosed by `b`, hence `b` is the ancestor of everything in `a`
                         scope_b
@@ -764,7 +856,7 @@ fn resolve_block<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'a, 'tcx>, blk:
                 visitor.enter_scope(
                     Scope::Remainder(BlockRemainder {
                         block: blk.hir_id.local_id,
-                        first_statement_index: i as u32
+                        first_statement_index: FirstStatementIndex::new(i)
                     })
                 );
                 visitor.cx.var_parent = visitor.cx.parent;
@@ -915,8 +1007,10 @@ fn resolve_expr<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'a, 'tcx>, expr:
             // Keep traversing up while we can.
             match visitor.scope_tree.parent_map.get(&scope) {
                 // Don't cross from closure bodies to their parent.
-                Some(&Scope::CallSite(_)) => break,
-                Some(&superscope) => scope = superscope,
+                Some(&superscope) => match superscope.data() {
+                    ScopeData::CallSite(_) => break,
+                    _ => scope = superscope
+                },
                 None => break
             }
         }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index cf7a29d2845..f714a5e14c4 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -26,6 +26,7 @@ use std::fmt;
 use std::usize;
 
 use rustc_const_math::ConstInt;
+use rustc_data_structures::indexed_vec::Idx;
 use syntax::abi::Abi;
 use syntax::ast::CRATE_NODE_ID;
 use syntax::symbol::Symbol;
@@ -530,17 +531,17 @@ impl fmt::Display for ty::RegionKind {
                 write!(f, "{}", br)
             }
             ty::ReScope(scope) if identify_regions() => {
-                match scope {
-                    region::Scope::Node(id) =>
+                match scope.data() {
+                    region::ScopeData::Node(id) =>
                         write!(f, "'{}s", id.as_usize()),
-                    region::Scope::CallSite(id) =>
+                    region::ScopeData::CallSite(id) =>
                         write!(f, "'{}cs", id.as_usize()),
-                    region::Scope::Arguments(id) =>
+                    region::ScopeData::Arguments(id) =>
                         write!(f, "'{}as", id.as_usize()),
-                    region::Scope::Destruction(id) =>
+                    region::ScopeData::Destruction(id) =>
                         write!(f, "'{}ds", id.as_usize()),
-                    region::Scope::Remainder(BlockRemainder { block, first_statement_index }) =>
-                        write!(f, "'{}_{}rs", block.as_usize(), first_statement_index),
+                    region::ScopeData::Remainder(BlockRemainder { block, first_statement_index }) =>
+                        write!(f, "'{}_{}rs", block.as_usize(), first_statement_index.index()),
                 }
             }
             ty::ReVar(region_vid) if identify_regions() => {
diff --git a/src/librustc_mir/build/scope.rs b/src/librustc_mir/build/scope.rs
index 20d3efdfffc..03273419432 100644
--- a/src/librustc_mir/build/scope.rs
+++ b/src/librustc_mir/build/scope.rs
@@ -555,8 +555,8 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
         // The outermost scope (`scopes[0]`) will be the `CallSiteScope`.
         // We want `scopes[1]`, which is the `ParameterScope`.
         assert!(self.scopes.len() >= 2);
-        assert!(match self.scopes[1].region_scope {
-            region::Scope::Arguments(_) => true,
+        assert!(match self.scopes[1].region_scope.data() {
+            region::ScopeData::Arguments(_) => true,
             _ => false,
         });
         self.scopes[1].region_scope
diff --git a/src/librustc_mir/hair/cx/block.rs b/src/librustc_mir/hair/cx/block.rs
index a8172a60174..6f6258f52f7 100644
--- a/src/librustc_mir/hair/cx/block.rs
+++ b/src/librustc_mir/hair/cx/block.rs
@@ -14,6 +14,8 @@ use hair::cx::to_ref::ToRef;
 use rustc::middle::region::{self, BlockRemainder};
 use rustc::hir;
 
+use rustc_data_structures::indexed_vec::Idx;
+
 impl<'tcx> Mirror<'tcx> for &'tcx hir::Block {
     type Output = Block<'tcx>;
 
@@ -71,7 +73,7 @@ fn mirror_stmts<'a, 'gcx, 'tcx>(cx: &mut Cx<'a, 'gcx, 'tcx>,
                     hir::DeclLocal(ref local) => {
                         let remainder_scope = region::Scope::Remainder(BlockRemainder {
                             block: block_id,
-                            first_statement_index: index as u32,
+                            first_statement_index: region::FirstStatementIndex::new(index),
                         });
 
                         let pattern = cx.pattern_from_hir(&local.pat);