Avoid linear complexity in LRU eviction

[vezenovm]

Problem

During the initial spilling work introduced in #11556 we must linearly search to evict a value in the LRU. This could potentially degrade compilation if we ever have a lot of live values. Although the number of live values in a block should be small this is good to note.

Happy Case

I have posted @aakoshh's idea from #11556 (comment) below:

Here's an idea to avoid the linear complexity of searching and moving values.

1. We could have a monotonic touch counter that increases with every call to touch.
2. The LRU would consist of two maps:

• lru_counters: HashMap<ValueId, TouchCounter> would remember the value of the counter when the value was last touched
• lru_order: BTreeSet<(TouchCounter, ValueId)> would keep values ordered by the time they were touched, oldest ones accessible through lru_order.first() and lru_order.iter().

3. touch would look up the value in lru_counters, remove the current count if necessary, then insert the new values in both lru_counters and lru_order.

This would bring the complexity down to logarithmic, which might be a good idea if this is called every time we use a value in SSA.

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response