Subzero : Live Range Splitting after initial Register Allocation

Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with
too few uses, the register allocator is run again and
the new variables that manage to get registers are inserted.

BUG=None
R=stichnot@chromium.org

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

[manasijm, 2016-07-28 21:44:27]

manasijm@google.com changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, kschimpf@google.com,
stichnot@chromium.org

[manasijm, 2016-07-28 22:00:12]

Description was changed from

==========
Live Range Splitting on the Basic Block Level
BUG=
==========

to

==========
Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with too few uses, the
register allocator is run again and the new variables that manage to get
registers are inserted.

BUG=None
==========

[manasijm, 2016-07-28 22:00:37]

Description was changed from

==========
Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with too few uses, the
register allocator is run again and the new variables that manage to get
registers are inserted.

BUG=None
==========

to

==========
Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with too few uses, the
register allocator is run again and 
the new variables that manage to get registers are inserted.

BUG=None
==========

[manasijm, 2016-07-28 22:01:01]

Description was changed from

==========
Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with too few uses, the
register allocator is run again and 
the new variables that manage to get registers are inserted.

BUG=None
==========

to

==========
Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with
too few uses, the register allocator is run again and 
the new variables that manage to get registers are inserted.

BUG=None
==========

[Jim Stichnoth, 2016-07-29 17:04:07]

Initial comments while I study the implementation in IceTargetLowering.cpp.

https://codereview.chromium.org/2172313002/diff/120001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceCfgNode.cpp#new...
src/IceCfgNode.cpp:462: if (Func->getLiveness()->getLiveIn(this).size() >=
VarNum) {
Shouldn't the '>=' be '>' ?

In any case, I think a more standard bounds-check idiom is:

  if (VarNum < Func->getLiveness()->getLiveIn(this).size()) {

Also, with repeated getLiveIn() calls, it might be clearer and more efficient to
do this:

  auto blah = Func->getLiveness()->getLiveIn(this);
  if (VarNum < blah.size()) {
    assert(!blah[VarNum]);
    blah[VarNum] = true;
  }

https://codereview.chromium.org/2172313002/diff/120001/src/IceClFlags.def
File src/IceClFlags.def (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceClFlags.def#new...
src/IceClFlags.def:170: X(GlobalSplitting, bool, dev_opt_flag,
"global-splitting",                   \
I would suggest this:

X(SplitGlobalVars, bool, dev_opt_flag, "split-global-vars",

for extra clarity, also consistency with my local var splitting CL.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.cpp#new...
src/IceOperand.cpp:105: if (!getFlags().getGlobalSplitting()) {
Remove the '!' and reverse the if/then/else branches.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.cpp#new...
src/IceOperand.cpp:116: // Disable merging to make sure a live range 'segment'
has a single node.
I think you could still merge if the node is the same?  But I don't think that
would ever actually happen in today's code.  Maybe note this in a comment?  e.g.
"Merging could be allowed if the nodes are the same, but this currently never
happens in practice."

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:625: void addSegment(RangeElementType Segment) {
How about:

void addSegment(RangeElementType Segment, CfgNode *Node = nullptr) {
  addSegment(Segment.first, Segment.second, Node);
}

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:646: SizeT getNumSegments() { return Range.size(); }
SizeT getNumSegments() const ...

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:648: const RangeType &getSegments() { return Range; }
can this be const?

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:649: CfgNode *getNodeForSegment(InstNumberT Begin) { return
NodeMap[Begin]; }
const?

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:333: Vars.clear();
You may want to do something like:

  Vars.reserve(Func->getVariables().size() + ExtraVars.size());

Could also subtract ExcludeVars.size() if you're sure that ExcludeVars is a
subset of Func->getVariables().

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:335: if (ExcludeVars.find(Var) == ExcludeVars.end())
I haven't studied the code that manages ExtraVars and ExcludeVars, so I could be
off base here.

I can imagine why you want ExtraVars to be sorted, but it doesn't seem to be
necessary for ExcludeVars.  As such, if there are a lot of excluded vars, the
complexity here could be O(N log N) instead of O(N).

You could solve this by using an unordered_set, or by doing a "parallel"
iteration through the two sorted collections.  The parallel iteration code is
tricky - see for example LiveRange::overlaps() - so I would prefer the
unordered_set.

Using unordered_set means that ExtraVars and ExcludeVars no longer have the same
type, which is a bit sad.  However, maybe ExtraVars should be an unordered_set
as well?  Again, I haven't looked at the code yet that builds up ExtraVars, but
maybe they're already in sorted order and you could use a CfgVector?  If not,
they could be inserted during the initial phase into an unordered_set, then
sorted here before inserting.  See
http://llvm.org/docs/ProgrammersManual.html#a-sorted-vector , and also a use of
that pattern in CfgNode::livenessAddIntervals().

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:336: Vars.push_back(Var);
I think we prefer emplace_back() instead of push_back().

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:338: for (auto *ExtraVar : ExtraVars) {
You might be able to do something more compact like this:

  Vars.insert(Vars.end(), ExtraVars.begin(), ExtraVars.end());

though it's also nice to have consistent structure with the previous loop.

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:474: if (RegUses[RegAlias] > 0)
This seems really suspicious, and I can't work out why it shouldn't be an error.
 Do you have a good example?

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:29: #include "IceLiveness.h"
sort

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:550: void
TargetLowering::postRegallocSplitting(LinearScan &RegAllocator,
These days we avoid passing by non-const ref, so make this "LinearScan
*RegAllocator".

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.h:32: #include "IceRegAlloc.h"
sort

https://codereview.chromium.org/2172313002/diff/120001/src/IceTimerTree.def
File src/IceTimerTree.def (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceTimerTree.def#n...
src/IceTimerTree.def:37: X(globalSplitting)                                     
                     \
How about "splitGlobalVars"?  (for extra clarity, and consistency with my local
var splitting CL)

[Jim Stichnoth, 2016-07-29 19:14:32]

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:517: }
blank line after this

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:519: CfgVector<Inst *> GetInstructionsInRange(CfgNode
*Node, InstNumberT Start,
lowercase getInstructionsInRange per coding style

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:519: CfgVector<Inst *> GetInstructionsInRange(CfgNode
*Node, InstNumberT Start,
Does this function assume that instruction numbers are monotonically increasing?
 such as the case after renumbering.

If so, I would make a few changes:

1. Document this.

2. Add an assert as instructions are processed to validate this.

3. Use the standard "if (Instr.isDeleted()) continue;" at the start of the loop
body.

4. Change the "== End" comparison in the loop to ">= End", and maybe move that
test to the top of the loop body.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:524: for (auto &Inst : Insts) {
Name this Instr instead of Inst which is a type name.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:525: if (!Started) {
Restructure as "if (Started) ... else ..."

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:531: } else {
Is the "else continue" necessary?  It doesn't look like there's any code left in
the loop body to execute.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:552: TimerMarker T(TimerStack::TT_globalSplitting,
Func->getContext());
Newer Subzero style is to name this "_" instead of "T" (assuming there isn't
already an RAII variable named "_").

Also, use the ctor that takes a Cfg rather than GlobalContext pointer.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:554: for (Variable *Var : Func->getVariables()) {
Please add some documentation in the code as to what's going on.  It doesn't
have to be excessive, but at least describe each of the 3 top-level loops.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:579: GetInstructionsInRange(Node, Segment.first,
Segment.second)) {
(This might be too much to ask for an initial feature that is behind a flag, so
at the very least document it with a TODO.)

I suspect a lot of time (and memory) is spent copying instruction ranges into
vectors of instruction pointers.  Could you instead return begin and end
iterators?  Since instruction ranges come from getPhis() and getInsts(), you
would probably want an iterator wrapper that allows you to iterate over phis and
insts sequentially and transparently.  (Such an iterator would be nice in a
couple other places that iterate identically over both lists.)

I suppose this could break down or be tricky if you need to add new instructions
while you iterate.

In this case, the handful (I suppose) of new instructions could be added at the
end after the iteration has completed.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:595: if (Info.UseCount < 3)
Use a static constexpr variable to self-document this magic constant.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:618: if (ExtraVar->hasReg()) {
how about:

  if (!ExtraVar->hasReg())
    continue;

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:619: Func->addVariable(ExtraVar);
I'm not thrilled about how these extra variables are created, especially the
idea that Variable::Number is no longer const -- what's to prevent some future
well-meaning code from changing a variable's Number and invalidating all the
assumptions about persistence?

What if you create these variables the normal way, and just leave them unused in
Cfg::Variables[] ?

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:638: for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {
Document that it's safe to iterate over the top-level src operands rather than
using FOREACH_VAR_IN_INST(), because any variables inside e.g. mem operands
should already have registers.

[manasijm, 2016-08-01 22:20:05]

https://codereview.chromium.org/2172313002/diff/120001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceCfgNode.cpp#new...
src/IceCfgNode.cpp:462: if (Func->getLiveness()->getLiveIn(this).size() >=
VarNum) {
On 2016/07/29 17:04:06, stichnot wrote:
> Shouldn't the '>=' be '>' ?
> 
> In any case, I think a more standard bounds-check idiom is:
> 
>   if (VarNum < Func->getLiveness()->getLiveIn(this).size()) {
> 
> Also, with repeated getLiveIn() calls, it might be clearer and more efficient
to
> do this:
> 
>   auto blah = Func->getLiveness()->getLiveIn(this);
>   if (VarNum < blah.size()) {
>     assert(!blah[VarNum]);
>     blah[VarNum] = true;
>   }

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.cpp#new...
src/IceOperand.cpp:105: if (!getFlags().getGlobalSplitting()) {
On 2016/07/29 17:04:06, stichnot wrote:
> Remove the '!' and reverse the if/then/else branches.

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.cpp#new...
src/IceOperand.cpp:116: // Disable merging to make sure a live range 'segment'
has a single node.
On 2016/07/29 17:04:06, stichnot wrote:
> I think you could still merge if the node is the same?  But I don't think that
> would ever actually happen in today's code.  Maybe note this in a comment? 
e.g.
> "Merging could be allowed if the nodes are the same, but this currently never
> happens in practice."

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:625: void addSegment(RangeElementType Segment) {
On 2016/07/29 17:04:07, stichnot wrote:
> How about:
> 
> void addSegment(RangeElementType Segment, CfgNode *Node = nullptr) {
>   addSegment(Segment.first, Segment.second, Node);
> }

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:646: SizeT getNumSegments() { return Range.size(); }
On 2016/07/29 17:04:07, stichnot wrote:
> SizeT getNumSegments() const ...

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:648: const RangeType &getSegments() { return Range; }
On 2016/07/29 17:04:07, stichnot wrote:
> can this be const?

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceOperand.h#newco...
src/IceOperand.h:649: CfgNode *getNodeForSegment(InstNumberT Begin) { return
NodeMap[Begin]; }
On 2016/07/29 17:04:07, stichnot wrote:
> const?

Probably not.

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:333: Vars.clear();
On 2016/07/29 17:04:07, stichnot wrote:
> You may want to do something like:
> 
>   Vars.reserve(Func->getVariables().size() + ExtraVars.size());
> 
> Could also subtract ExcludeVars.size() if you're sure that ExcludeVars is a
> subset of Func->getVariables().

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:336: Vars.push_back(Var);
On 2016/07/29 17:04:07, stichnot wrote:
> I think we prefer emplace_back() instead of push_back().

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:338: for (auto *ExtraVar : ExtraVars) {
On 2016/07/29 17:04:07, stichnot wrote:
> You might be able to do something more compact like this:
> 
>   Vars.insert(Vars.end(), ExtraVars.begin(), ExtraVars.end());
> 
> though it's also nice to have consistent structure with the previous loop.

Acknowledged.

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:474: if (RegUses[RegAlias] > 0)
On 2016/07/29 17:04:07, stichnot wrote:
> This seems really suspicious, and I can't work out why it shouldn't be an
error.
>  Do you have a good example?

Should have removed it before submitting. Thanks

https://codereview.chromium.org/2172313002/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:976: if (!SplittingMode)
This turned out to be unnecessary too.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:29: #include "IceLiveness.h"
On 2016/07/29 17:04:07, stichnot wrote:
> sort

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:517: }
On 2016/07/29 19:14:31, stichnot wrote:
> blank line after this

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:519: CfgVector<Inst *> GetInstructionsInRange(CfgNode
*Node, InstNumberT Start,
On 2016/07/29 19:14:31, stichnot wrote:
> lowercase getInstructionsInRange per coding style

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:524: for (auto &Inst : Insts) {
On 2016/07/29 19:14:32, stichnot wrote:
> Name this Instr instead of Inst which is a type name.

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:525: if (!Started) {
On 2016/07/29 19:14:31, stichnot wrote:
> Restructure as "if (Started) ... else ..."

Acknowledged.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:531: } else {
On 2016/07/29 19:14:31, stichnot wrote:
> Is the "else continue" necessary?  It doesn't look like there's any code left
in
> the loop body to execute.

Acknowledged.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:550: void
TargetLowering::postRegallocSplitting(LinearScan &RegAllocator,
On 2016/07/29 17:04:07, stichnot wrote:
> These days we avoid passing by non-const ref, so make this "LinearScan
> *RegAllocator".

Not passing a LinearScan object anymore.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:552: TimerMarker T(TimerStack::TT_globalSplitting,
Func->getContext());
On 2016/07/29 19:14:31, stichnot wrote:
> Newer Subzero style is to name this "_" instead of "T" (assuming there isn't
> already an RAII variable named "_").
> 
> Also, use the ctor that takes a Cfg rather than GlobalContext pointer.

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:554: for (Variable *Var : Func->getVariables()) {
On 2016/07/29 19:14:31, stichnot wrote:
> Please add some documentation in the code as to what's going on.  It doesn't
> have to be excessive, but at least describe each of the 3 top-level loops.

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:579: GetInstructionsInRange(Node, Segment.first,
Segment.second)) {
On 2016/07/29 19:14:32, stichnot wrote:
> (This might be too much to ask for an initial feature that is behind a flag,
so
> at the very least document it with a TODO.)
> 
> I suspect a lot of time (and memory) is spent copying instruction ranges into
> vectors of instruction pointers.  Could you instead return begin and end
> iterators?  Since instruction ranges come from getPhis() and getInsts(), you
> would probably want an iterator wrapper that allows you to iterate over phis
and
> insts sequentially and transparently.  (Such an iterator would be nice in a
> couple other places that iterate identically over both lists.)
> 
> I suppose this could break down or be tricky if you need to add new
instructions
> while you iterate.
> 
> In this case, the handful (I suppose) of new instructions could be added at
the
> end after the iteration has completed.

Acknowledged.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:595: if (Info.UseCount < 3)
On 2016/07/29 19:14:31, stichnot wrote:
> Use a static constexpr variable to self-document this magic constant.

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:618: if (ExtraVar->hasReg()) {
On 2016/07/29 19:14:31, stichnot wrote:
> how about:
> 
>   if (!ExtraVar->hasReg())
>     continue;

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:619: Func->addVariable(ExtraVar);
On 2016/07/29 19:14:31, stichnot wrote:
> I'm not thrilled about how these extra variables are created, especially the
> idea that Variable::Number is no longer const -- what's to prevent some future
> well-meaning code from changing a variable's Number and invalidating all the
> assumptions about persistence?
> 
> What if you create these variables the normal way, and just leave them unused
in
> Cfg::Variables[] ?

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.cpp:638: for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {
On 2016/07/29 19:14:31, stichnot wrote:
> Document that it's safe to iterate over the top-level src operands rather than
> using FOREACH_VAR_IN_INST(), because any variables inside e.g. mem operands
> should already have registers.

Copied this as is. :)

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceTargetLowering....
src/IceTargetLowering.h:32: #include "IceRegAlloc.h"
On 2016/07/29 17:04:07, stichnot wrote:
> sort

Done.

https://codereview.chromium.org/2172313002/diff/120001/src/IceTimerTree.def
File src/IceTimerTree.def (right):

https://codereview.chromium.org/2172313002/diff/120001/src/IceTimerTree.def#n...
src/IceTimerTree.def:37: X(globalSplitting)                                     
                     \
On 2016/07/29 17:04:07, stichnot wrote:
> How about "splitGlobalVars"?  (for extra clarity, and consistency with my
local
> var splitting CL)

Done.

[Jim Stichnoth, 2016-08-02 05:57:50]

https://codereview.chromium.org/2172313002/diff/160001/src/IceClFlags.def
File src/IceClFlags.def (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceClFlags.def#new...
src/IceClFlags.def:171: cl::desc("Live range splitting after initial register
allocation"),          \
To be consistent with the rest of the file, these continuation lines should be
indented 2 spaces.

https://codereview.chromium.org/2172313002/diff/160001/src/IceClFlags.def#new...
src/IceClFlags.def:171: cl::desc("Live range splitting after initial register
allocation"),          \
I suggest "Global live range splitting ..."

To contrast with local variable splitting.

https://codereview.chromium.org/2172313002/diff/160001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceOperand.h#newco...
src/IceOperand.h:649: CfgNode *getNodeForSegment(InstNumberT Begin) { return
NodeMap[Begin]; }
Should probably assert that NodeMap contains Begin.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:533: Result.push_back(&Instr);
emplace_back ?

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:535: if (Instr.getNumber() == End) {
Can this be ">=", just to be safe?  just in case the "End" instruction doesn't
actually exist, or is deleted

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:544: }
add blank line afterwards

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:557: // Find variables that does not have registers
but are allowed to. Also skip
that do not

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:589: for (SizeT j = 0; j <
Instr->getSrc(i)->getNumVars(); ++j) {
For local variable splitting, I made the assumption that any variables without a
register must appear as a top-level operand, i.e. the "for j" loop is not
needed.

You could do that here.  But if not, can you use the FOREACH_VAR_IN_INST macro?

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:599: if (Instr->getDest() == Info.Replacing &&
!llvm::isa<InstPhi>(Instr)) {
It looks like Phi instructions are not considered for src operands or for the
dest variable, so can they be rejected in the loop over instructions?

However, I don't understand why they should be rejected when considering dest
variables.  Add a comment to describe?  Maybe a TODO if it's a mystery?

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:629: // Modify the Cfg to use the new variables that
now now have registers.
now now

https://codereview.chromium.org/2172313002/diff/160001/src/IceTimerTree.def
File src/IceTimerTree.def (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceTimerTree.def#n...
src/IceTimerTree.def:37: X(splitGlobalVars)                                     
                     \
sort

[manasijm, 2016-08-02 21:41:59]

https://codereview.chromium.org/2172313002/diff/160001/src/IceClFlags.def
File src/IceClFlags.def (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceClFlags.def#new...
src/IceClFlags.def:171: cl::desc("Live range splitting after initial register
allocation"),          \
On 2016/08/02 05:57:50, stichnot wrote:
> I suggest "Global live range splitting ..."
> 
> To contrast with local variable splitting.

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceClFlags.def#new...
src/IceClFlags.def:171: cl::desc("Live range splitting after initial register
allocation"),          \
On 2016/08/02 05:57:50, stichnot wrote:
> To be consistent with the rest of the file, these continuation lines should be
> indented 2 spaces.

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceOperand.h#newco...
src/IceOperand.h:649: CfgNode *getNodeForSegment(InstNumberT Begin) { return
NodeMap[Begin]; }
On 2016/08/02 05:57:50, stichnot wrote:
> Should probably assert that NodeMap contains Begin.

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:533: Result.push_back(&Instr);
On 2016/08/02 05:57:50, stichnot wrote:
> emplace_back ?

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:535: if (Instr.getNumber() == End) {
On 2016/08/02 05:57:50, stichnot wrote:
> Can this be ">=", just to be safe?  just in case the "End" instruction doesn't
> actually exist, or is deleted

That seems to result in missing a lot of opportunities. Added a comment.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:544: }
On 2016/08/02 05:57:50, stichnot wrote:
> add blank line afterwards

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:557: // Find variables that does not have registers
but are allowed to. Also skip
On 2016/08/02 05:57:50, stichnot wrote:
> that do not

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:589: for (SizeT j = 0; j <
Instr->getSrc(i)->getNumVars(); ++j) {
On 2016/08/02 05:57:50, stichnot wrote:
> For local variable splitting, I made the assumption that any variables without
a
> register must appear as a top-level operand, i.e. the "for j" loop is not
> needed.
> 
> You could do that here.  But if not, can you use the FOREACH_VAR_IN_INST
macro?

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:599: if (Instr->getDest() == Info.Replacing &&
!llvm::isa<InstPhi>(Instr)) {
On 2016/08/02 05:57:50, stichnot wrote:
> It looks like Phi instructions are not considered for src operands or for the
> dest variable, so can they be rejected in the loop over instructions?
> 
> However, I don't understand why they should be rejected when considering dest
> variables.  Add a comment to describe?  Maybe a TODO if it's a mystery?

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:629: // Modify the Cfg to use the new variables that
now now have registers.
On 2016/08/02 05:57:50, stichnot wrote:
> now now

Done.

https://codereview.chromium.org/2172313002/diff/160001/src/IceTimerTree.def
File src/IceTimerTree.def (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceTimerTree.def#n...
src/IceTimerTree.def:37: X(splitGlobalVars)                                     
                     \
On 2016/08/02 05:57:50, stichnot wrote:
> sort

Done.

[Jim Stichnoth, 2016-08-04 01:59:17]

otherwise lgtm

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/2172313002/diff/160001/src/IceTargetLowering....
src/IceTargetLowering.cpp:599: if (Instr->getDest() == Info.Replacing &&
!llvm::isa<InstPhi>(Instr)) {
On 2016/08/02 21:41:59, manasijm wrote:
> On 2016/08/02 05:57:50, stichnot wrote:
> > It looks like Phi instructions are not considered for src operands or for
the
> > dest variable, so can they be rejected in the loop over instructions?
> > 
> > However, I don't understand why they should be rejected when considering
dest
> > variables.  Add a comment to describe?  Maybe a TODO if it's a mystery?
> 
> Done.

I don't see any new comment or TODO on this issue?

[manasijm, 2016-08-04 19:33:26]

Description was changed from

==========
Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with
too few uses, the register allocator is run again and 
the new variables that manage to get registers are inserted.

BUG=None
==========

to

==========
Live Range Splitting after initial Register Allocation

After register allocation is done once, this pass targets
the variables that do not get registers, break them into
multiple variables with shorter (at most spanning a basic
block) live ranges. After discarding the new variables with
too few uses, the register allocator is run again and
the new variables that manage to get registers are inserted.

BUG=None
R=stichnot@chromium.org

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

[manasijm, 2016-08-04 19:33:32]

Committed patchset #11 (id:200001) manually as
7cd926d6d4f401dd3595e0682f48ede3e04ac7f7 (presubmit successful).