Closed
Description
The present set of NLL patches uses a terribly inefficient representation for regions consisting of two btrees. I think what we probably want is to use a librustc_data_structures::bitvec::BitMatrix, which is a 2D matrix where each cell can be a boolean. The "rows" here would be the region indices and the "columns" would be the locations + free regions.
As of #45668, the representation of Region is encapsulated within the region_context.rs module, so this change should be fairly easy to make. The basic idea would be that, when we initialize the RegionInferenceContext, we have on hand everything we need to allocate the BitMatrix -- that is, we know how many rows and columns we will need.
So the basic steps would be:
- Create a map from each free region to its column index
- For convenience, these may want to be the same as the free region's variable index (which also start from 0).
- Create a map from each MIR
Locationto its column index.- These would start from the column indices used for free regions.
- The code to enumerate locations can be found in
init_free_regions; it is basically a loop over the basic blocks and then the locations within each basic block.
- Remove the
valuefield fromRegionDefinition- We will replace it with a
BitMatrixstored as a field in theRegionInferenceContext
- We will replace it with a
- Adjust users of the
valuefield likeregion_contains_point, this should be largely straightforward - We'll have to adjust the bitset propagation code -- this could be tricky since it has to copy from one row into another, but I think
BitMatrixalready supports some APIs for that, we may want to add a few more or just tweak howDFSworks