swift234

[sil-arc-opts] Dataflow based ARC Optimizer.

Overview
--------

This commit contains a dataflow based ARC Optimizer. Changing to a
dataflow framework allows us to perform the following additional
optimizations: the sequence optimization and the nested
increment-decrement optimization. I will describe them below. These
result in a 30% increase in the number of ref count instructions removed
from the standard library despite the stub analysis functions I am using
in this patch to ease review (more analysis will come later which will
improve the results).

*NOTE* In the following when I say RefCntValue I am refering to a value
with reference semantics.
*NOTE* In the following we assume that the frontend being incorrect and
emitting incorrect code in terms of globally balancing retain counts is
undefined behavior and will never happen.

Sequence Optimization
---------------------

Consider the following block of code:

  strong_retain %0
  ...
  strong_release %0

where ... could contain any code including ref count increments and
decrements. Since we are assuming the frontend is correct, we know that:

1. Before the strong_retain %0 must be alive implying RefCnt(%0) >= 1 at
   that point. Of course after the strong_retain, %0 must have
   RefCnt(%0) >= 2.

2. Before the strong_release %0 must also be alive implying RefCnt(%0)
   >= 1 at that point.

Thus if we can prove that there is at most 1x decrement in between the
retain/release, we can remove the retain/release pair safely. Thus
easily we know that we can remove the increment, decrement pair in the
following segment of code no manner what instruction unknown is:

  strong_retain %0
  unknown %0
  strong_release %0

But what about if we are processing more than 1 instruction? Consider
the following situation:

  strong_retain %0
  may_decrement %0
  may_use %0
  strong_release %0

In this situation, we can not remove the retain/release. This is because
of the following: Assume that may_use can not decrement %0 then:

1. Again we know that after the strong_retain RefCnt(%0) must be >= 2 and
   before the strong_release, RefCnt(%0) must be >= 1.
2. If we remove the retain/release, then we know that before
   may_decrement, RefCnt(%0) >= 1. Then may_decrement may decrement
   %0 causing it to be deallocated causing may_use to attempt to use a
   deallocated RefCntValue.

If may_use can decrement %0, then we could actually remove the
retain/release pair since in order for correctness to be gauranteed, we
know that after the strong_retain, RefCnt(%0) >= 3. But that is an
optimization for a later time.

Thus we can not remove the retain/release in this case. But we can get
around the issue by using the nested increment-decrement optimization.

Nested Increment-Decrement Optimization
---------------------------------------

The nested increment operation is based off of the notion that when one
has a nested retain pair on the same RefCntValue, the outer retain will
preserve the liveness of the value allowing the inner retain to be moved
freely. Consider the following code:

  ...                //        RefCnt(%0) >= 1
  strong_retain %0   // id 1 - RefCnt(%0) >= 2
  strong_retain %0   // id 2 - RefCnt(%0) >= 3
  may_decrement %0
  may_use %0
  strong_release %0  // id 3   RefCnt(%0) >= 2
  strong_release %0  // id 4   RefCnt(%0) >= 1
  ...

If we remove the inner retain-release pair, we will have that:

  ...                //        RefCnt(%0) >= 1
  strong_retain %0   // id 1 - RefCnt(%0) >= 2
  may_decrement %0
  may_use %0
  strong_release %0  // id 4   RefCnt(%0) >= 1
  ...

which again implies that %0 must be alive when may_use is
executed.

Again note that in this analysis, we are ignoring the possibility that
may_use may decrement %0 since in that case, we will know that
RefCnt(%0) >= 4 to gaurantee correctness before optimization implying
removing the retain/release pair is still correct.

Swift SVN r12629