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();
+}
+
+namespace {
+
+// Helpers for findRematerializable().  For each of them, if a suitable
+// rematerialization is found, the instruction's Dest variable is set to be
+// rematerializable and it returns true, otherwise it returns false.
+
+bool rematerializeArithmetic(const Inst *Instr) {
+  // Check that it's an Arithmetic instruction with an Add operation.
+  auto *Arith = llvm::dyn_cast<InstArithmetic>(Instr);
+  if (Arith == nullptr || Arith->getOp() != InstArithmetic::Add)
+    return false;
+  // Check that Src(0) is rematerializable.
+  auto *Src0Var = llvm::dyn_cast<Variable>(Arith->getSrc(0));
+  if (Src0Var == nullptr || !Src0Var->isRematerializable())
+    return false;
+  // Check that Src(1) is an immediate.
+  auto *Src1Imm = llvm::dyn_cast<ConstantInteger32>(Arith->getSrc(1));
+  if (Src1Imm == nullptr)
+    return false;
+  Arith->getDest()->setRematerializable(
+      Src0Var->getRegNum(), Src0Var->getStackOffset() + Src1Imm->getValue());
+  return true;
+}
+
+bool rematerializeAssign(const Inst *Instr) {
+  // An InstAssign only originates from an inttoptr or ptrtoint instruction,
+  // which never occurs in a MINIMAL build.
+  if (BuildDefs::minimal())
+    return false;
+  // Check that it's an Assign instruction.
+  if (!llvm::isa<InstAssign>(Instr))
+    return false;
+  // Check that Src(0) is rematerializable.
+  auto *Src0Var = llvm::dyn_cast<Variable>(Instr->getSrc(0));
+  if (Src0Var == nullptr || !Src0Var->isRematerializable())
+    return false;
+  Instr->getDest()->setRematerializable(Src0Var->getRegNum(),
+                                        Src0Var->getStackOffset());
+  return true;
+}
+
+bool rematerializeCast(const Inst *Instr) {
+  // An pointer-type bitcast never occurs in a MINIMAL build.
+  if (BuildDefs::minimal())
+    return false;
+  // Check that it's a Cast instruction with a Bitcast operation.
+  auto *Cast = llvm::dyn_cast<InstCast>(Instr);
+  if (Cast == nullptr || Cast->getCastKind() != InstCast::Bitcast)
+    return false;
+  // Check that Src(0) is rematerializable.
+  auto *Src0Var = llvm::dyn_cast<Variable>(Cast->getSrc(0));
+  if (Src0Var == nullptr || !Src0Var->isRematerializable())
+    return false;
+  // Check that Dest and Src(0) have the same type.
+  Variable *Dest = Cast->getDest();
+  if (Dest->getType() != Src0Var->getType())
+    return false;
+  Dest->setRematerializable(Src0Var->getRegNum(), Src0Var->getStackOffset());
+  return true;
+}
+
+} // end of anonymous namespace
+
+/// 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 || Dest->isRematerializable())
+          continue;
+        if (rematerializeArithmetic(&Instr) || rematerializeAssign(&Instr) ||
+            rematerializeCast(&Instr)) {
+          FoundNewAssignment = true;
+        }
+      }
+    }
+  } 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