Subzero: Control whether deleted instructions are retained.

Subzero: Control whether deleted instructions are retained.

Normally, deleted instructions are preserved in the Cfg, and printed as part of dump output.  This helps debugging by partially explaining the provenance of new instructions that originated from the deleted instructions.

However, these instructions slow down iteration over the instruction list, and checking their deleted status may pollute the cache.

As such, in a non-DUMP enabled build, we repurpose the renumberInstructions() pass to also unlink deleted instructions as needed.

A flag is provided to override this behavior, in case we have to debug a situation where a bug only manifests in a DUMP build and not a non-DUMP build, or vice versa.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4360
R=eholk@chromium.org, jpp@chromium.org

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

[Jim Stichnoth, 2016-03-12 23:40:28]

Description was changed from

==========
Subzero: Control whether deleted instructions are retained.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4360
==========

to

==========
Subzero: Control whether deleted instructions are retained.

Normally, deleted instructions are preserved in the Cfg, and printed as part of
dump output.  This helps debugging by partially explaining the provenance of new
instructions that originated from the deleted instructions.

However, these instructions slow down iteration over the instruction list, and
checking their deleted status may pollute the cache.

As such, in a non-DUMP enabled build, we repurpose the renumberInstructions()
pass to also unlink deleted instructions as needed.

A flag is provided to override this behavior, in case we have to debug a
situation where a bug only manifests in a DUMP build and not a non-DUMP build,
or vice versa.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4360
==========

[Jim Stichnoth, 2016-03-12 23:41:11]

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

[Eric Holk, 2016-03-14 13:20:14]

lgtm

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp#newcode60
src/IceCfgNode.cpp:60: for (++Next; I != E; I = Next++) {
Does a ranged for loop work here?

https://codereview.chromium.org/1790063003/diff/1/src/IceClFlags.cpp
File src/IceClFlags.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceClFlags.cpp#newcode486
src/IceClFlags.cpp:486: OutFlags.KeepDeletedInsts = Ice::BuildDefs::dump();
Is there a way to tie this reference to Ice::BuildDefs::dump() to the previous
one (line 145)? It seems like we have a lot of duplication of default values
here.

[John, 2016-03-14 13:27:15]

lgtm

https://codereview.chromium.org/1790063003/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceCfg.cpp#newcode281
src/IceCfg.cpp:281: /// instructions from the Cfg, to speed up later passes over
the instructions.
Maybe document the .h file instead?

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp#newcode56
src/IceCfgNode.cpp:56: template <typename List> void
removeDeletedAndRenumber(List *L, Cfg *Func) {
You don't need a template here -- L is always an InstList.

[Jim Stichnoth, 2016-03-14 13:51:16]

https://codereview.chromium.org/1790063003/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceCfg.cpp#newcode281
src/IceCfg.cpp:281: /// instructions from the Cfg, to speed up later passes over
the instructions.
On 2016/03/14 13:27:15, John wrote:
> Maybe document the .h file instead?

Done.

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp#newcode56
src/IceCfgNode.cpp:56: template <typename List> void
removeDeletedAndRenumber(List *L, Cfg *Func) {
On 2016/03/14 13:27:15, John wrote:
> You don't need a template here -- L is always an InstList.

In one case it's InstList, in another case it's PhiList.

Now I realize that InstList and PhiList happen to be the same.  I actually
wanted PhiList to be ilist<InstPhi>, but SFINAE issues.  (This is documented in
IceDefs.h.)  I'd prefer to keep this templated for if/when PhiList diverges.

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp#newcode60
src/IceCfgNode.cpp:60: for (++Next; I != E; I = Next++) {
On 2016/03/14 13:20:14, Eric Holk wrote:
> Does a ranged for loop work here?

I don't think so, because erase(I) invalidates iterator I, so the implicit ++I
at the end of the loop body is invalid.

One thought is something like this:

  for (auto &I : *L) {
    if (...) {
      auto Prev = I;
      --Prev
      L->erase(I);
      I = Prev;
    } else {
      I->renumber(Func);
    }
  }

except this breaks when the very first instruction is to be deleted because you
can't back up past the start of the list.  So you could start it off with a
separate loop that erases the initial deleted items.

I think the original implementation is cleaner. :)

https://codereview.chromium.org/1790063003/diff/1/src/IceClFlags.cpp
File src/IceClFlags.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceClFlags.cpp#newcode486
src/IceClFlags.cpp:486: OutFlags.KeepDeletedInsts = Ice::BuildDefs::dump();
On 2016/03/14 13:20:14, Eric Holk wrote:
> Is there a way to tie this reference to Ice::BuildDefs::dump() to the previous
> one (line 145)? It seems like we have a lot of duplication of default values
> here.

Yeah, this is definitely obnoxious and out of control.

I plan to deal with this as part of
https://bugs.chromium.org/p/nativeclient/issues/detail?id=4084 .  Specifically,
almost all these flags become global, so there's no need to manipulate them
through an object.

[Eric Holk, 2016-03-14 14:01:04]

still lgtm

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp#newcode60
src/IceCfgNode.cpp:60: for (++Next; I != E; I = Next++) {
On 2016/03/14 13:51:16, stichnot wrote:
> On 2016/03/14 13:20:14, Eric Holk wrote:
> > Does a ranged for loop work here?
> 
> I don't think so, because erase(I) invalidates iterator I, so the implicit ++I
> at the end of the loop body is invalid.
> 
> One thought is something like this:
> 
>   for (auto &I : *L) {
>     if (...) {
>       auto Prev = I;
>       --Prev
>       L->erase(I);
>       I = Prev;
>     } else {
>       I->renumber(Func);
>     }
>   }
> 
> except this breaks when the very first instruction is to be deleted because
you
> can't back up past the start of the list.  So you could start it off with a
> separate loop that erases the initial deleted items.
> 
> I think the original implementation is cleaner. :)

Ah, I see. I figured you had a good reason :)

https://codereview.chromium.org/1790063003/diff/1/src/IceClFlags.cpp
File src/IceClFlags.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceClFlags.cpp#newcode486
src/IceClFlags.cpp:486: OutFlags.KeepDeletedInsts = Ice::BuildDefs::dump();
On 2016/03/14 13:51:16, stichnot wrote:
> On 2016/03/14 13:20:14, Eric Holk wrote:
> > Is there a way to tie this reference to Ice::BuildDefs::dump() to the
previous
> > one (line 145)? It seems like we have a lot of duplication of default values
> > here.
> 
> Yeah, this is definitely obnoxious and out of control.
> 
> I plan to deal with this as part of
> https://bugs.chromium.org/p/nativeclient/issues/detail?id=4084 . 
Specifically,
> almost all these flags become global, so there's no need to manipulate them
> through an object.

Ok, great!

[John, 2016-03-14 14:55:50]

lgtm

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/1790063003/diff/1/src/IceCfgNode.cpp#newcode56
src/IceCfgNode.cpp:56: template <typename List> void
removeDeletedAndRenumber(List *L, Cfg *Func) {
On 2016/03/14 13:51:15, stichnot wrote:
> On 2016/03/14 13:27:15, John wrote:
> > You don't need a template here -- L is always an InstList.
> 
> In one case it's InstList, in another case it's PhiList.
> 
> Now I realize that InstList and PhiList happen to be the same.  I actually
> wanted PhiList to be ilist<InstPhi>, but SFINAE issues.  (This is documented
in
> IceDefs.h.)  I'd prefer to keep this templated for if/when PhiList diverges.

Well, not a big deal --hence the previous LGTM, but this is yet another case of
convoluted code that does not need to be so...

The problem is not SFINAE: every Ice::Inst has ilist methods in it -- hooray for
intrusive lists! --, and they all return Inst * (because the Ice::Inst inherits
from llvm::ilist<Inst>)

if you

using PhiList = llvm::ilist<InstPhi>

the for loops become:

using llvm::ilist;
for (ilist<PhiInst>::iterator it = Phis.begin(); it != Phis.end(); ++it) {
}

now, because

class Inst : public ilis<Inst>;
class InstHighLevel : public Inst;
class InstPhi : public InstHistLevel;

typedecl(Phis.begin()) == ilist<Inst>::iterator,

and hence all hell break loose.

If phi lists are so special, maybe they should not inherit from Inst.

As I said, I **personally** would not create the template here -- I would prefer
to fix this if the two ever diverge -- but really, this is a matter of taste,
and the current solution has no drawbacks.

[Jim Stichnoth, 2016-03-14 15:37:56]

Description was changed from

==========
Subzero: Control whether deleted instructions are retained.

Normally, deleted instructions are preserved in the Cfg, and printed as part of
dump output.  This helps debugging by partially explaining the provenance of new
instructions that originated from the deleted instructions.

However, these instructions slow down iteration over the instruction list, and
checking their deleted status may pollute the cache.

As such, in a non-DUMP enabled build, we repurpose the renumberInstructions()
pass to also unlink deleted instructions as needed.

A flag is provided to override this behavior, in case we have to debug a
situation where a bug only manifests in a DUMP build and not a non-DUMP build,
or vice versa.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4360
==========

to

==========
Subzero: Control whether deleted instructions are retained.

Normally, deleted instructions are preserved in the Cfg, and printed as part of
dump output.  This helps debugging by partially explaining the provenance of new
instructions that originated from the deleted instructions.

However, these instructions slow down iteration over the instruction list, and
checking their deleted status may pollute the cache.

As such, in a non-DUMP enabled build, we repurpose the renumberInstructions()
pass to also unlink deleted instructions as needed.

A flag is provided to override this behavior, in case we have to debug a
situation where a bug only manifests in a DUMP build and not a non-DUMP build,
or vice versa.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4360
R=eholk@chromium.org, jpp@chromium.org

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

[Jim Stichnoth, 2016-03-14 15:37:58]

Committed patchset #2 (id:20001) manually as
76719b4aab9bdc44a9d37004aba64471790ab574 (presubmit successful).