Remove pure nodes from the `Layout` of the function, ensuring that only the "side-effect skeleton" remains, and also optimize the pure nodes. This is the first step of egraph-based processing and turns the pure CFG-based CLIF into a CFG skeleton with a sea of (optimized) nodes tying it together. As we walk through the code, we eagerly apply optimization rules; at any given point we have a "latest
(&mut self)
| 784 | /// only refer to its subset that exists at this stage, to |
| 785 | /// maintain acyclicity.) |
| 786 | fn remove_pure_and_optimize(&mut self) { |
| 787 | let mut cursor = FuncCursor::new(self.func); |
| 788 | let mut value_to_opt_value: SecondaryMap<Value, Value> = |
| 789 | SecondaryMap::with_default(Value::reserved_value()); |
| 790 | |
| 791 | // Map from instruction to value for hash-consing of pure ops |
| 792 | // into the egraph. This can be a standard (non-scoped) |
| 793 | // hashmap because pure ops have no location: they are |
| 794 | // "outside of" control flow. |
| 795 | // |
| 796 | // Note also that we keep the controlling typevar (the `Type` |
| 797 | // in the tuple below) because it may disambiguate |
| 798 | // instructions that are identical except for type. |
| 799 | // |
| 800 | // We store both skeleton and non-skeleton instructions in the |
| 801 | // GVN map; for skeleton instructions, we only store those |
| 802 | // that are idempotent, i.e., still eligible to GVN. Note that |
| 803 | // some skeleton instructions are idempotent but do not |
| 804 | // produce a value: e.g., traps on a given condition. To allow |
| 805 | // for both cases, we store an `Option<Value>` as the value in |
| 806 | // this map. |
| 807 | let mut gvn_map: ScopedHashMap<(Type, InstructionData), Option<Value>> = |
| 808 | ScopedHashMap::with_capacity(cursor.func.dfg.num_values()); |
| 809 | |
| 810 | // The block in the domtree preorder traversal at each level |
| 811 | // of the GVN map. |
| 812 | let mut gvn_map_blocks: Vec<Block> = vec![]; |
| 813 | |
| 814 | // To get the best possible merging and canonicalization, we |
| 815 | // track where a value is "available" at: this is the |
| 816 | // domtree-nearest-ancestor join of all args if the value |
| 817 | // itself is pure, otherwise the block where the value is |
| 818 | // defined. (And for union nodes, the |
| 819 | // domtree-highest-ancestor, i.e., the meet or the dual to the |
| 820 | // above join.) |
| 821 | let mut available_block: SecondaryMap<Value, Block> = |
| 822 | SecondaryMap::with_default(Block::reserved_value()); |
| 823 | |
| 824 | // To avoid blowing up eclasses too much, we track the size of |
| 825 | // each eclass reachable by a tree of union nodes from a given |
| 826 | // value ID, and we avoid union'ing additional values into an |
| 827 | // eclass when it reaches `ECLASS_ENODE_LIMIT`. |
| 828 | // |
| 829 | // For efficiency, this encodes size minus one: so a value of |
| 830 | // zero (which is cheap to bulk-initialize) means a singleton |
| 831 | // eclass of size one. This also allows us to avoid explicitly |
| 832 | // writing the size for any values that are not union nodes. |
| 833 | let mut eclass_size: SecondaryMap<Value, u8> = SecondaryMap::with_default(0); |
| 834 | |
| 835 | // This is an initial guess at the size we'll need, but we add |
| 836 | // more values as we build simplified alternative expressions so |
| 837 | // this is likely to realloc again later. |
| 838 | available_block.resize(cursor.func.dfg.num_values()); |
| 839 | |
| 840 | // See `EgraphBlockIter` for why we use this particular block |
| 841 | // ordering. |
| 842 | let domtree = self.domtree; |
| 843 | for block in EgraphBlockIter::new(domtree) { |
no test coverage detected