| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
- Add newline to provide concise module summary
- Add wikipedia link
- Italicize O notation
|
|
We don't need the `scc_dependency_order` vector, `all_sccs` is already
in dependency order.
|
|
|
|
|
|
|
|
|
|
This is perhaps better than the linked list approach I was using
before. Lower memory overhead, Theta(N+E) storage. Does require a
sort. =)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The strategy is this:
- we compute SCCs once all outlives constraints are known
- we allocate a set of values **per region** for storing liveness
- we allocate a set of values **per SCC** for storing the final values
- when we add a liveness constraint to the region R, we also add it
to the final value of the SCC to which R belongs
- then we can apply the constraints by just walking the DAG for the
SCCs and union'ing the children (which have their liveness
constraints within)
There are a few intermediate refactorings that I really ought to have
broken out into their own commits:
- reverse the constraint graph so that `R1: R2` means `R1 -> R2` and
not `R2 -> R1`. This fits better with the SCC computation and new
style of inference (`->` now means "take value from" and not "push
value into")
- this does affect some of the UI tests, since they traverse the
graph, but mostly the artificial ones and they don't necessarily
seem worse
- put some things (constraint set, etc) into `Rc`. This lets us root
them to permit mutation and iteration. It also guarantees they don't
change, which is critical to the correctness of the algorithm.
- Generalize various helpers that previously operated only on points
to work on any sort of region element.
|
|
|
