[semantic-arc-opts] Instead of tracking owned value introducers, track incoming values that are seen from owned value introducers.
[semantic-arc-opts] Instead of tracking owned value introducers, track incoming values that are seen from owned value introducers.

TLDR: This will allow me to in a forthcoming commit to eliminate the extra run
of the peephole optimizer to seed the phi arg analysis since this eliminates
potential data invalidation issues. That being said, I am formalizing the
language/model in the pass a little in this commit, so I wanted to give a long
description below.

----

In this commit, I am formalizing some of the language around this optimization
away phi nodes specifically and more towards a notion that Andy and I have
discussed called "Joined Live Ranges". The idea is a "Live Range" in OSSA is an
owned value together with its set of forwarding uses. The owned value is in a
certain sense the equivalence class representative of all of the values that are
derived from the owned value via forwarding instructions.

This works well as long as all of the "forwarding" instructions only derive
their ownership from a single operand. Some instructions without that property
are branch, tuple, struct. Since such a "forwarding" instruction derives its
ownership by merging the ownership of multiple operands, if multiple of its
operands are non-trivial owned operands, we are in a sense joining together the
live ranges of those non-trivial owned operands. The main implication of this is
that if we want to convert the joined live range from owned to guaranteed, we
can only do it if we can also do it for all of its incoming values at the same
time.

This creates a conundrum though since this pass has been written like a peephole
pass which is ill-suited to be converted into this form. So instead, this pass
seeds an analysis from peephole runs that /could/ have been converted from owned
to guaranteed except for a specific joined live range. Then after we reach a
fixed point, we use that information from the failed peepholes to try to
eliminate the joined live ranges.

This approach is a good approach, but if implemented in certain ways exposes the
risk of problems around touching invalidated data. Specifically, before this
patch, this was implemented with the concern that each branch
instruction (currently the only supported type of joined live range instruction)
could be paired with multiple owned value introducers. This is because
initially, we were allowing for tuple, struct with multiple non-trivial operands
to be used as owned value introducers. This implied that we could not rely on
just storing a bool per joined live range operand since we would need to know
that all introducers associated with the operand were optimizable.

After some thought/discussion, I realized that this sort of optimization can
also apply to tuple/struct/similar insts. This let to the shift in
thinking/realization that we could talk instead about general joined live ranges
and handle tuple/struct/similar instructions just like they were branch/phi! As
such, if we assume that all such instructions are treated as separate
LiveRanges, then we know that our branch can only have a single owned value
introducer since we do not look through /any/ joined live ranges when computing
LiveRanges.

This realization then allows us to store a single bool value marking the operand
on the joined live range as being one that we /may/ be able to optimize. This
then allows us to simplify the state we handle and not have to worry about
storing memory to instructions that may be eliminated. Since we have a joined
live range use, we know that any value that is used by the joined live range can
not be eliminated by the peephole optimizer.

roambotics/swift,aschwaighofer/swift,harlanhaskins/swift,airspeedswift/swift,stephentyrone/swift,ahoppen/swift,atrick/swift,nathawes/swift,ahoppen/swift,jmgc/swift,allevato/swift,apple/swift,glessard/swift,JGiola/swift,parkera/swift,hooman/swift,apple/swift,rudkx/swift,xwu/swift,harlanhaskins/swift,airspeedswift/swift,tkremenek/swift,xwu/swift,tkremenek/swift,jckarter/swift,aschwaighofer/swift,nathawes/swift,nathawes/swift,JGiola/swift,apple/swift,xwu/swift,apple/swift,apple/swift,benlangmuir/swift,xwu/swift,benlangmuir/swift,benlangmuir/swift,jckarter/swift,JGiola/swift,CodaFi/swift,glessard/swift,allevato/swift,parkera/swift,allevato/swift,hooman/swift,rudkx/swift,stephentyrone/swift,parkera/swift,jmgc/swift,nathawes/swift,jmgc/swift,jckarter/swift,airspeedswift/swift,rudkx/swift,jckarter/swift,jmgc/swift,CodaFi/swift,JGiola/swift,hooman/swift,harlanhaskins/swift,hooman/swift,parkera/swift,CodaFi/swift,aschwaighofer/swift,gregomni/swift,allevato/swift,atrick/swift,allevato/swift,aschwaighofer/swift,aschwaighofer/swift,nathawes/swift,tkremenek/swift,allevato/swift,stephentyrone/swift,jckarter/swift,roambotics/swift,aschwaighofer/swift,jmgc/swift,jmgc/swift,CodaFi/swift,roambotics/swift,gregomni/swift,gregomni/swift,tkremenek/swift,stephentyrone/swift,harlanhaskins/swift,jckarter/swift,gregomni/swift,jckarter/swift,atrick/swift,parkera/swift,benlangmuir/swift,gregomni/swift,glessard/swift,jmgc/swift,apple/swift,ahoppen/swift,allevato/swift,ahoppen/swift,airspeedswift/swift,stephentyrone/swift,stephentyrone/swift,roambotics/swift,hooman/swift,gregomni/swift,xwu/swift,tkremenek/swift,CodaFi/swift,tkremenek/swift,hooman/swift,parkera/swift,harlanhaskins/swift,rudkx/swift,atrick/swift,rudkx/swift,airspeedswift/swift,JGiola/swift,hooman/swift,harlanhaskins/swift,stephentyrone/swift,ahoppen/swift,xwu/swift,atrick/swift,nathawes/swift,CodaFi/swift,aschwaighofer/swift,roambotics/swift,tkremenek/swift,roambotics/swift,benlangmuir/swift,CodaFi/swift,airspeedswift/swift,nathawes/swift,xwu/swift,ahoppen/swift,benlangmuir/swift,glessard/swift,glessard/swift,parkera/swift,airspeedswift/swift,JGiola/swift,glessard/swift,parkera/swift,atrick/swift,harlanhaskins/swift,rudkx/swift