Subzero: Find rematerializable variables transitively.

Subzero: Find rematerializable variables transitively.

There are situations where a variable is assigned as the result of a rematerializable alloca instruction, and then another variable is assigned as essentially a known-offset interior pointer into the alloca space.  In this case, the secondary variable is also rematerializable.

We add a pass, after alloca analysis, to find these derived variables and mark them transitively as rematerializable.  Because we lack use-def chains (or in fact any map to variable use locations), we need to iterate over the CFG until convergence.  Fortunately, this is pretty cheap, and not even done unless the alloca analysis seeds it with an initial set of rematerializable variables.

This analysis is only really needed for arithmetic instructions, but we also need to apply it to assignments and pointer-type bitcasts that are added when the IceConverter directly parses a .ll file rather than a .pexe file.

BUG= none
R=jpp@chromium.org, sehr@chromium.org

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

[Jim Stichnoth, 2015-11-12 19:48:19]

Description was changed from

==========
Subzero: Find rematerializable variables transitively.

BUG= none
==========

to

==========
Subzero: Find rematerializable variables transitively.

There are situations where a variable is assigned as the result of a
rematerializable alloca instruction, and then another variable is assigned as
essentially a known-offset interior pointer into the alloca space.  In this
case, the secondary variable is also rematerializable.

We add a pass, after alloca analysis, to find these derived variables and mark
them transitively as rematerializable.  Because we lack use-def chains (or in
fact any map to variable use locations), we need to iterate over the CFG until
convergence.  Fortunately, this is pretty cheap, and not even done unless the
alloca analysis seeds it with an initial set of rematerializable variables.

This analysis is only really needed for arithmetic instructions, but we also
need to apply it to assignments and pointer-type bitcasts that are added when
the IceConverter directly parses a .ll file rather than a .pexe file.

BUG= none
==========

[Jim Stichnoth, 2015-11-12 20:07:20]

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

[Jim Stichnoth, 2015-11-12 20:08:05]

I was trying to get 1-2% gain on perlbmk, but the surprise looks like 7-8% on
eon.

[John, 2015-11-12 20:43:15]

lgtm

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp#newcode672
src/IceCfg.cpp:672: if (Src0Var->isRematerializable()) {
soooo many nest levels. My brain hurts... :(

[Jim Stichnoth, 2015-11-12 21:02:44]

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp#newcode672
src/IceCfg.cpp:672: if (Src0Var->isRematerializable()) {
On 2015/11/12 20:43:14, John wrote:
> soooo many nest levels. My brain hurts... :(

I hear you...  Unfortunately, the "best" order for encouraging short-circuiting,
injects those pesky dyn_casts in the middle.

I could just suck it up and do something like this:

auto *Arith = llvm::dyn_cast<InstArithmetic>(&Instr);
auto *Src0Var = Arith ? llvm::dyn_cast<Variable>(Arith->getSrc(0)) : nullptr;
if (Arith && Src0Var && Arith->getOp() == InstArithmetic::Add &&
Src0Var->isRematerializable()) {
...

What do you think?  Other suggestions?

[John, 2015-11-12 21:11:39]

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp#newcode672
src/IceCfg.cpp:672: if (Src0Var->isRematerializable()) {
On 2015/11/12 21:02:44, stichnot wrote:
> On 2015/11/12 20:43:14, John wrote:
> > soooo many nest levels. My brain hurts... :(
> 
> I hear you...  Unfortunately, the "best" order for encouraging
short-circuiting,
> injects those pesky dyn_casts in the middle.
> 
> I could just suck it up and do something like this:
> 
> auto *Arith = llvm::dyn_cast<InstArithmetic>(&Instr);
> auto *Src0Var = Arith ? llvm::dyn_cast<Variable>(Arith->getSrc(0)) : nullptr;
> if (Arith && Src0Var && Arith->getOp() == InstArithmetic::Add &&
> Src0Var->isRematerializable()) {
> ...
> 
> What do you think?  Other suggestions?

I would create small helper functions, e.g.,

if (const auto *Arith = ..) {
  findRematerializableArith(...);
}

namespace {

bool findRematerializableArith(const InstArith *Arith) {
  if (!Arith->getOp() == Add)
    return false;

  const auto *Src0Var = llvm::dyn_cast<Variable>(Arith->getSrc(0));
  if (Src0Var == nullptr)
    return false;

  if (!Src0Var->isRematerializable())
    return false;

  const auto *Src1Imm = llvm::dyn_cast<ConstantInteger32>(Arith->getSrc(1));
  if (Src1Imm == nullptr)
    return false;

  Dest->setRematerializable(...);
  return true;
}
} // end of anonymous namespace

In general, if you need a lot of nest levels, you're probably doing something
not trivial, so creating these little helper functions help readability a lot
(not if you name it findRematerializableArith, or processRematerializable Arith;
but maybe if you name it rematerializeDest(...) then the code is clear(er).)

Note: This function inspects a lot from arith (it needs Dest, Src0, Src1, and
Op), so I would still pass Arith (but as a const InstArith.) Had the number of
parameters been, 1, or 2, I would just pass them.

[Jim Stichnoth, 2015-11-13 01:18:48]

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/1441793002/diff/20001/src/IceCfg.cpp#newcode672
src/IceCfg.cpp:672: if (Src0Var->isRematerializable()) {
On 2015/11/12 21:11:39, John wrote:
> On 2015/11/12 21:02:44, stichnot wrote:
> > On 2015/11/12 20:43:14, John wrote:
> > > soooo many nest levels. My brain hurts... :(
> > 
> > I hear you...  Unfortunately, the "best" order for encouraging
> short-circuiting,
> > injects those pesky dyn_casts in the middle.
> > 
> > I could just suck it up and do something like this:
> > 
> > auto *Arith = llvm::dyn_cast<InstArithmetic>(&Instr);
> > auto *Src0Var = Arith ? llvm::dyn_cast<Variable>(Arith->getSrc(0)) :
nullptr;
> > if (Arith && Src0Var && Arith->getOp() == InstArithmetic::Add &&
> > Src0Var->isRematerializable()) {
> > ...
> > 
> > What do you think?  Other suggestions?
> 
> I would create small helper functions, e.g.,
> 
> if (const auto *Arith = ..) {
>   findRematerializableArith(...);
> }
> 
> namespace {
> 
> bool findRematerializableArith(const InstArith *Arith) {
>   if (!Arith->getOp() == Add)
>     return false;
> 
>   const auto *Src0Var = llvm::dyn_cast<Variable>(Arith->getSrc(0));
>   if (Src0Var == nullptr)
>     return false;
> 
>   if (!Src0Var->isRematerializable())
>     return false;
> 
>   const auto *Src1Imm = llvm::dyn_cast<ConstantInteger32>(Arith->getSrc(1));
>   if (Src1Imm == nullptr)
>     return false;
> 
>   Dest->setRematerializable(...);
>   return true;
> }
> } // end of anonymous namespace
> 
> In general, if you need a lot of nest levels, you're probably doing something
> not trivial, so creating these little helper functions help readability a lot
> (not if you name it findRematerializableArith, or processRematerializable
Arith;
> but maybe if you name it rematerializeDest(...) then the code is clear(er).)
> 
> Note: This function inspects a lot from arith (it needs Dest, Src0, Src1, and
> Op), so I would still pass Arith (but as a const InstArith.) Had the number of
> parameters been, 1, or 2, I would just pass them.

OK thanks.  I split it into helper calls.  PTAL.

[sehr, 2015-11-13 21:46:26]

lgtm

[Jim Stichnoth, 2015-11-13 22:28:29]

Committed patchset #3 (id:40001) manually as
3607b6c924922d261cbc75b68e07a1e2a5aec5dc (presubmit successful).