From dd371a2069e84bf58702cb4c760681ee9c8aa874 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Mon, 31 Jul 2017 18:39:25 -0700 Subject: rustc: Inline bitwise modification operators These need to be inlined across crates to avoid showing up as one-instruction functions in profiles! In the benchmark from #43578 this decreased the translation item collection step from 30s to 23s, and looks like it also allowed vectorization elsewhere of the operations! --- src/librustc_data_structures/bitslice.rs | 2 ++ 1 file changed, 2 insertions(+) (limited to 'src/librustc_data_structures') diff --git a/src/librustc_data_structures/bitslice.rs b/src/librustc_data_structures/bitslice.rs index ba53578e579..f74af6ee163 100644 --- a/src/librustc_data_structures/bitslice.rs +++ b/src/librustc_data_structures/bitslice.rs @@ -134,9 +134,11 @@ pub trait BitwiseOperator { pub struct Union; impl BitwiseOperator for Union { + #[inline] fn join(&self, a: usize, b: usize) -> usize { a | b } } pub struct Subtract; impl BitwiseOperator for Subtract { + #[inline] fn join(&self, a: usize, b: usize) -> usize { a & !b } } -- cgit 1.4.1-3-g733a5 From daa764461d57ab69ef9fa9dcbf2a73c4fb0e6f94 Mon Sep 17 00:00:00 2001 From: Matt Brubeck Date: Wed, 2 Aug 2017 10:42:12 -0700 Subject: Remove unused fnv hash code --- src/librustc_data_structures/fnv.rs | 66 ------------------------------------- src/librustc_data_structures/lib.rs | 1 - 2 files changed, 67 deletions(-) delete mode 100644 src/librustc_data_structures/fnv.rs (limited to 'src/librustc_data_structures') diff --git a/src/librustc_data_structures/fnv.rs b/src/librustc_data_structures/fnv.rs deleted file mode 100644 index 5bd57236e7c..00000000000 --- a/src/librustc_data_structures/fnv.rs +++ /dev/null @@ -1,66 +0,0 @@ -// Copyright 2015 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use std::collections::{HashMap, HashSet}; -use std::default::Default; -use std::hash::{Hasher, Hash, BuildHasherDefault}; - -pub type FnvHashMap = HashMap>; -pub type FnvHashSet = HashSet>; - -#[allow(non_snake_case)] -pub fn FnvHashMap() -> FnvHashMap { - HashMap::default() -} - -#[allow(non_snake_case)] -pub fn FnvHashSet() -> FnvHashSet { - HashSet::default() -} - -/// A speedy hash algorithm for node ids and def ids. The hashmap in -/// liballoc by default uses SipHash which isn't quite as speedy as we -/// want. In the compiler we're not really worried about DOS attempts, so we -/// just default to a non-cryptographic hash. -/// -/// This uses FNV hashing, as described here: -/// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function -pub struct FnvHasher(u64); - -impl Default for FnvHasher { - /// Creates a `FnvHasher`, with a 64-bit hex initial value. - #[inline] - fn default() -> FnvHasher { - FnvHasher(0xcbf29ce484222325) - } -} - -impl Hasher for FnvHasher { - #[inline] - fn write(&mut self, bytes: &[u8]) { - let FnvHasher(mut hash) = *self; - for byte in bytes { - hash = hash ^ (*byte as u64); - hash = hash.wrapping_mul(0x100000001b3); - } - *self = FnvHasher(hash); - } - - #[inline] - fn finish(&self) -> u64 { - self.0 - } -} - -pub fn hash(v: &T) -> u64 { - let mut state = FnvHasher::default(); - v.hash(&mut state); - state.finish() -} diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs index bb27d479a41..3cb3e088364 100644 --- a/src/librustc_data_structures/lib.rs +++ b/src/librustc_data_structures/lib.rs @@ -65,7 +65,6 @@ pub mod snapshot_vec; pub mod stable_hasher; pub mod transitive_relation; pub mod unify; -pub mod fnv; pub mod fx; pub mod tuple_slice; pub mod veccell; -- cgit 1.4.1-3-g733a5 From 4e3a0b636fffdf9d514420681dc60ecbca221f42 Mon Sep 17 00:00:00 2001 From: Ariel Ben-Yehuda Date: Mon, 7 Aug 2017 15:56:43 +0300 Subject: rustc::middle::dataflow - visit the CFG in RPO We used to propagate bits in node-id order, which sometimes caused an excessive number of iterations, especially when macros were present. As everyone knows, visiting the CFG in RPO bounds the number of iterators by 1 plus the depth of the most deeply nested loop (times the height of the lattice, which is 1). Fixes #43704. --- src/librustc/middle/dataflow.rs | 17 +++++++++--- src/librustc_data_structures/graph/mod.rs | 36 ++++++++++++++++++++++++ src/librustc_data_structures/graph/tests.rs | 43 +++++++++++++++++++++++++++++ 3 files changed, 92 insertions(+), 4 deletions(-) (limited to 'src/librustc_data_structures') diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs index f6be7090091..d394c0f0c87 100644 --- a/src/librustc/middle/dataflow.rs +++ b/src/librustc/middle/dataflow.rs @@ -22,6 +22,9 @@ use std::mem; use std::usize; use syntax::ast; use syntax::print::pprust::PrintState; + +use rustc_data_structures::graph::OUTGOING; + use util::nodemap::NodeMap; use hir; use hir::intravisit::{self, IdRange}; @@ -523,12 +526,16 @@ impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> { changed: true }; + let nodes_po = cfg.graph.nodes_in_postorder(OUTGOING, cfg.entry); let mut temp = vec![0; words_per_id]; + let mut num_passes = 0; while propcx.changed { + num_passes += 1; propcx.changed = false; propcx.reset(&mut temp); - propcx.walk_cfg(cfg, &mut temp); + propcx.walk_cfg(cfg, &nodes_po, &mut temp); } + debug!("finished in {} iterations", num_passes); } debug!("Dataflow result for {}:", self.analysis_name); @@ -543,12 +550,15 @@ impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> { impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> { fn walk_cfg(&mut self, cfg: &cfg::CFG, + nodes_po: &[CFGIndex], in_out: &mut [usize]) { debug!("DataFlowContext::walk_cfg(in_out={}) {}", bits_to_string(in_out), self.dfcx.analysis_name); assert!(self.dfcx.bits_per_id > 0); - cfg.graph.each_node(|node_index, node| { + // Iterate over nodes in reverse postorder + for &node_index in nodes_po.iter().rev() { + let node = cfg.graph.node(node_index); debug!("DataFlowContext::walk_cfg idx={:?} id={} begin in_out={}", node_index, node.data.id(), bits_to_string(in_out)); @@ -563,8 +573,7 @@ impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> { // Propagate state on-exit from node into its successors. self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index); - true // continue to next node - }); + } } fn reset(&mut self, bits: &mut [usize]) { diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs index f94ed6b7209..f562ae0e3b8 100644 --- a/src/librustc_data_structures/graph/mod.rs +++ b/src/librustc_data_structures/graph/mod.rs @@ -308,6 +308,42 @@ impl Graph { DepthFirstTraversal::with_start_node(self, start, direction) } + pub fn nodes_in_postorder<'a>(&'a self, + direction: Direction, + entry_node: NodeIndex) + -> Vec + { + let mut visited = BitVector::new(self.len_nodes()); + let mut stack = vec![]; + let mut result = Vec::with_capacity(self.len_nodes()); + let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| { + if visited.insert(node.0) { + stack.push((node, self.adjacent_edges(node, direction))); + } + }; + + for node in Some(entry_node).into_iter() + .chain(self.enumerated_nodes().map(|(node, _)| node)) + { + push_node(&mut stack, node); + while let Some((node, mut iter)) = stack.pop() { + if let Some((_, child)) = iter.next() { + let target = child.source_or_target(direction); + // the current node needs more processing, so + // add it back to the stack + stack.push((node, iter)); + // and then push the new node + push_node(&mut stack, target); + } else { + result.push(node); + } + } + } + + assert_eq!(result.len(), self.len_nodes()); + result + } + /// Whether or not a node can be reached from itself. pub fn is_node_cyclic(&self, starting_node_index: NodeIndex) -> bool { // This is similar to depth traversal below, but we diff --git a/src/librustc_data_structures/graph/tests.rs b/src/librustc_data_structures/graph/tests.rs index bdefc39a61a..b6a0d4cff5a 100644 --- a/src/librustc_data_structures/graph/tests.rs +++ b/src/librustc_data_structures/graph/tests.rs @@ -175,3 +175,46 @@ fn is_node_cyclic_b() { let graph = create_graph_with_cycle(); assert!(graph.is_node_cyclic(NodeIndex(1))); } + +#[test] +fn nodes_in_postorder() { + let expected = vec![ + ("A", vec!["C", "E", "D", "B", "A", "F"]), + ("B", vec!["C", "E", "D", "B", "A", "F"]), + ("C", vec!["C", "E", "D", "B", "A", "F"]), + ("D", vec!["C", "E", "D", "B", "A", "F"]), + ("E", vec!["C", "E", "D", "B", "A", "F"]), + ("F", vec!["C", "E", "D", "B", "F", "A"]) + ]; + + let graph = create_graph(); + + for ((idx, node), &(node_name, ref expected)) + in graph.enumerated_nodes().zip(&expected) + { + assert_eq!(node.data, node_name); + assert_eq!(expected, + &graph.nodes_in_postorder(OUTGOING, idx) + .into_iter().map(|idx| *graph.node_data(idx)) + .collect::>()); + } + + let expected = vec![ + ("A", vec!["D", "C", "B", "A"]), + ("B", vec!["D", "C", "B", "A"]), + ("C", vec!["B", "D", "C", "A"]), + ("D", vec!["C", "B", "D", "A"]), + ]; + + let graph = create_graph_with_cycle(); + + for ((idx, node), &(node_name, ref expected)) + in graph.enumerated_nodes().zip(&expected) + { + assert_eq!(node.data, node_name); + assert_eq!(expected, + &graph.nodes_in_postorder(OUTGOING, idx) + .into_iter().map(|idx| *graph.node_data(idx)) + .collect::>()); + } +} -- cgit 1.4.1-3-g733a5