Subzero: Find rematerializable variables transitively.

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 612 matching lines @@
     // do not have a known offset from either the stack or frame pointer.
     // They grow up from a user pointer from an alloca.
     sortAndCombineAllocas(AlignedAllocas, MaxAlignment, Insts, BVT_UserPointer);
   }
   // Otherwise, fixed size allocas are always addressed relative to the stack
   // unless there are dynamic allocas.
   // TODO(sehr): re-enable frame pointer and decrementing addressing.
   AllocaBaseVariableType BasePointerType =
       (HasDynamicAllocation ? BVT_UserPointer : BVT_StackPointer);
   sortAndCombineAllocas(FixedAllocas, MaxAlignment, Insts, BasePointerType);
+
+  if (!FixedAllocas.empty() || !AlignedAllocas.empty())
+    // No use calling findRematerializable() unless there is some
+    // rematerializable alloca instruction to seed it.
+    findRematerializable();
+}
+
+/// Scan the function to find additional rematerializable variables.  This is
+/// possible when the source operand of an InstAssignment is a rematerializable
+/// variable, or the same for a pointer-type InstCast::Bitcast, or when an
+/// InstArithmetic is an add of a rematerializable variable and an immediate.
+/// Note that InstAssignment instructions and pointer-type InstCast::Bitcast
+/// instructions generally only come about from the IceConverter's treatment of
+/// inttoptr, ptrtoint, and bitcast instructions.  TODO(stichnot): Consider
+/// other possibilities, however unlikely, such as InstArithmetic::Sub, or
+/// commutativity.
+void Cfg::findRematerializable() {
+  // Scan the instructions in order, and repeat until no new opportunities are
+  // found.  It may take more than one iteration because a variable's defining
+  // block may happen to come after a block where it is used, depending on the
+  // CfgNode linearization order.
+  bool FoundNewAssignment;
+  do {
+    FoundNewAssignment = false;
+    for (CfgNode *Node : getNodes()) {
+      // No need to process Phi instructions.
+      for (Inst &Instr : Node->getInsts()) {
+        if (Instr.isDeleted())
+          continue;
+        Variable *Dest = Instr.getDest();
+        if (Dest == nullptr)
+          continue;
+        if (Dest->isRematerializable())
+          continue;
+        if (auto *Arith = llvm::dyn_cast<InstArithmetic>(&Instr)) {
+          // Just look at Add for now.
+          if (Arith->getOp() == InstArithmetic::Add) {
+            // Assume "v+10" for now, don't bother considering "10+v".
+            if (auto *Src0Var = llvm::dyn_cast<Variable>(Arith->getSrc(0))) {
+              if (Src0Var->isRematerializable()) {

[John, 2015/11/12 20:43:14]

soooo many nest levels. My brain hurts... :(

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

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]

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:47]

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

+                if (auto *Src1Imm =
+                        llvm::dyn_cast<ConstantInteger32>(Arith->getSrc(1))) {
+                  Dest->setRematerializable(Src0Var->getRegNum(),
+                                            Src0Var->getStackOffset() +
+                                                Src1Imm->getValue());
+                  FoundNewAssignment = true;
+                }
+              }
+            }
+          }
+          continue;
+        } // end of InstArithmetic
+        if (auto *Assign = llvm::dyn_cast<InstAssign>(&Instr)) {
+          if (auto *Src0Var = llvm::dyn_cast<Variable>(Assign->getSrc(0))) {
+            if (Src0Var->isRematerializable()) {
+              Dest->setRematerializable(Src0Var->getRegNum(),
+                                        Src0Var->getStackOffset());
+              FoundNewAssignment = true;
+            }
+          }
+          continue;
+        } // end of InstAssign
+        if (auto *Cast = llvm::dyn_cast<InstCast>(&Instr)) {
+          if (Cast->getCastKind() == InstCast::Bitcast) {
+            if (auto *Src0Var = llvm::dyn_cast<Variable>(Cast->getSrc(0))) {
+              if (Src0Var->isRematerializable() &&
+                  Src0Var->getType() == Dest->getType()) {
+                Dest->setRematerializable(Src0Var->getRegNum(),
+                                          Src0Var->getStackOffset());
+                FoundNewAssignment = true;
+              }
+            }
+          }
+        } // end of InstCast
+      }
+    }
+  } while (FoundNewAssignment);
 }
 
 void Cfg::doAddressOpt() {
   TimerMarker T(TimerStack::TT_doAddressOpt, this);
   for (CfgNode *Node : Nodes)
     Node->doAddressOpt();
 }
 
 void Cfg::doNopInsertion() {
   if (!Ctx->getFlags().shouldDoNopInsertion())
@@ skipping 257 matching lines @@
   OstreamLocker L(Ctx);
   Ostream &Str = Ctx->getStrEmit();
   IceString MangledName = Ctx->mangleName(getFunctionName());
   const Assembler *Asm = getAssembler<>();
   const bool NeedSandboxing = Ctx->getFlags().getUseSandboxing();
 
   emitTextHeader(MangledName, Ctx, Asm);
   deleteJumpTableInsts();
   if (Ctx->getFlags().getDecorateAsm()) {
     for (Variable *Var : getVariables()) {
-      if (Var->getStackOffset()) {
+      if (Var->getStackOffset() && !Var->isRematerializable()) {
         Str << "\t" << Var->getSymbolicStackOffset(this) << " = "
             << Var->getStackOffset() << "\n";
       }
     }
   }
   for (CfgNode *Node : Nodes) {
     if (NeedSandboxing && Node->needsAlignment()) {
       Str << "\t" << Asm->getAlignDirective() << " "
           << Asm->getBundleAlignLog2Bytes() << "\n";
     }
@@ skipping 73 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice