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
Location to 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
value field from RegionDefinition
- Adjust users of the
value field like region_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
BitMatrix already supports some APIs for that, we may want to add a few more or just tweak how DFS works
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
Regionis encapsulated within theregion_context.rsmodule, so this change should be fairly easy to make. The basic idea would be that, when we initialize theRegionInferenceContext, we have on hand everything we need to allocate theBitMatrix-- that is, we know how many rows and columns we will need.So the basic steps would be:
Locationto its column index.init_free_regions; it is basically a loop over the basic blocks and then the locations within each basic block.valuefield fromRegionDefinitionBitMatrixstored as a field in theRegionInferenceContextvaluefield likeregion_contains_point, this should be largely straightforwardBitMatrixalready supports some APIs for that, we may want to add a few more or just tweak howDFSworks