Subzero: Optimize live range overlaps() computation through trimming.

Subzero: Optimize live range overlaps() computation through trimming.

The main optimization is for the repeated overlaps() calls against the Inactive set, by iteratively trimming away the early sections of the Inactive live ranges that can no longer overlap with Cur.

A more minor optimization doesn't bother checking pure point-valued Inactive ranges for expiring or reactivating.

BUG= none
R=jvoung@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=037fa1d997307fd68c7e6d9c385e30890d65604d

[Jim Stichnoth, 2014-10-04 15:47:38]

stichnot@chromium.org changed reviewers:
+ jvoung@chromium.org

[Jim Stichnoth, 2014-10-04 15:52:13]

This gains anywhere from 5-30% across the spec2k components.

The linearScan() time is now down in the neighborhood of liveness analysis, live
range construction, and textual code emission, instead of being at 2-3x those
levels.

[jvoung (off chromium), 2014-10-05 20:34:14]

Great speedup!

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:128: bool LiveRange::overlaps(InstNumberT OtherBegin) const {
Would it help to have this overlaps() check use a trimmed Range too?

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:164: while (TrimmedBegin != Range.end() &&
TrimmedBegin->second <= Lower)
I might be reading this wrong, but it looks like trim() pushes the ranges past
"Lower" w/ testing that while "TrimmedBegin->second <= Lower", keep bumping.

Should trim() only push up till Lower >= TrimmedBegin->first? Intuitively, that
seems like that would bump past ranges that clearly won't overlap, but keeps the
very last range that could still overlap?

https://codereview.chromium.org/627203002/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/627203002/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:338: assert(Item.Var->hasReg());
Is there any benefit to trimming the UnhandledPrecolored?

[Jim Stichnoth, 2014-10-06 13:38:02]

I still want to make another pass on this.  The trim() stuff is still too
fragile, and as you pointed out, there are more opportunities to use it.

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:128: bool LiveRange::overlaps(InstNumberT OtherBegin) const {
On 2014/10/05 20:34:13, jvoung wrote:
> Would it help to have this overlaps() check use a trimmed Range too?

I think you're right.

There are two instances of overlapsStart() that should directly benefit from
this.

For the calls to overlapsDefs(), which call overlaps(InstNumberT), the best
would be to trim the Defs list (and make sure the list is sorted).

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:164: while (TrimmedBegin != Range.end() &&
TrimmedBegin->second <= Lower)
On 2014/10/05 20:34:13, jvoung wrote:
> I might be reading this wrong, but it looks like trim() pushes the ranges past
> "Lower" w/ testing that while "TrimmedBegin->second <= Lower", keep bumping.
> 
> Should trim() only push up till Lower >= TrimmedBegin->first? Intuitively,
that
> seems like that would bump past ranges that clearly won't overlap, but keeps
the
> very last range that could still overlap?

Are you asking e.g. what would happen if "this" live range is [1:10),[20:30) and
Cur is [10:15) such that Lower=10 in this method?  In this case, it is OK to
advance this->TrimmedBegin to the [20:30) element because [1:10) and [10:15) do
not overlap.

https://codereview.chromium.org/627203002/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/627203002/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:338: assert(Item.Var->hasReg());
On 2014/10/05 20:34:14, jvoung wrote:
> Is there any benefit to trimming the UnhandledPrecolored?

It shouldn't have any benefit.  By definition, the Unhandled live ranges begin
at or after the start of Cur's live range, so trim() should not actually do
anything.

[jvoung (off chromium), 2014-10-06 21:57:26]

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/627203002/diff/20001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:164: while (TrimmedBegin != Range.end() &&
TrimmedBegin->second <= Lower)
On 2014/10/06 13:38:01, stichnot wrote:
> On 2014/10/05 20:34:13, jvoung wrote:
> > I might be reading this wrong, but it looks like trim() pushes the ranges
past
> > "Lower" w/ testing that while "TrimmedBegin->second <= Lower", keep bumping.
> > 
> > Should trim() only push up till Lower >= TrimmedBegin->first? Intuitively,
> that
> > seems like that would bump past ranges that clearly won't overlap, but keeps
> the
> > very last range that could still overlap?
> 
> Are you asking e.g. what would happen if "this" live range is [1:10),[20:30)
and
> Cur is [10:15) such that Lower=10 in this method?  In this case, it is OK to
> advance this->TrimmedBegin to the [20:30) element because [1:10) and [10:15)
do
> not overlap.


Okay, I see I think I was confused by the order of the comparison (Lower on the
left vs right).

[Jim Stichnoth, 2014-10-07 17:01:40]

I tried trimming the variable definitions list as well, for the overlap validity
tests, but there was no real performance difference, so I removed that code. 
Patchsets 3 and 4 can be compared if we eventually want it back.

[jvoung (off chromium), 2014-10-07 18:07:44]

lgtm

[Jim Stichnoth, 2014-10-07 18:09:42]

Committed patchset #4 (id:60001) manually as
037fa1d997307fd68c7e6d9c385e30890d65604d (presubmit successful).