Subzero: Improve/refactor folding loads into the next instruction.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLoweringX8632 class, which
@@ skipping 464 matching lines @@
     return;
 
   // TODO: It should be sufficient to use the fastest liveness
   // calculation, i.e. livenessLightweight().  However, for some
   // reason that slows down the rest of the translation.  Investigate.
   Func->liveness(Liveness_Basic);
   if (Func->hasError())
     return;
   Func->dump("After x86 address mode opt");
 
+  doLoadOpt();
   Func->genCode();
   if (Func->hasError())
     return;
   Func->dump("After x86 codegen");
 
   // Register allocation.  This requires instruction renumbering and
   // full liveness analysis.
   Func->renumberInstructions();
   if (Func->hasError())
     return;
@@ skipping 70 matching lines @@
   if (Func->hasError())
     return;
   Func->dump("After stack frame mapping");
 
   // Nop insertion
   if (Ctx->getFlags().shouldDoNopInsertion()) {
     Func->doNopInsertion();
   }
 }
 
+namespace {
+
+// Converts a ConstantInteger32 operand into its constant value, or
+// MemoryOrderInvalid if the operand is not a ConstantInteger32.
+uint64_t getConstantMemoryOrder(Operand *Opnd) {
+  if (auto Integer = llvm::dyn_cast<ConstantInteger32>(Opnd))
+    return Integer->getValue();
+  return Intrinsics::MemoryOrderInvalid;
+}
+
+// Determines whether the dest of a Load instruction can be folded
+// into one of the src operands of a 2-operand instruction.  This is
+// true as long as the load dest matches exactly one of the binary
+// instruction's src operands.  Replaces Src0 or Src1 with LoadSrc if
+// the answer is true.
+bool canFoldLoadIntoBinaryInst(Operand *LoadSrc, Variable *LoadDest,
+                               Operand *&Src0, Operand *&Src1) {
+  if (Src0 == LoadDest && Src1 != LoadDest) {
+    Src0 = LoadSrc;
+    return true;
+  }
+  if (Src0 != LoadDest && Src1 == LoadDest) {
+    Src1 = LoadSrc;
+    return true;
+  }
+  return false;
+}
+
+} // end of anonymous namespace
+
+void TargetX8632::doLoadOpt() {
+  for (CfgNode *Node : Func->getNodes()) {
+    Context.init(Node);
+    while (!Context.atEnd()) {
+      Variable *LoadDest = nullptr;
+      Operand *LoadSrc = nullptr;
+      Inst *CurInst = Context.getCur();
+      Inst *Next = Context.getNextInst();
+      // Determine whether the current instruction is a Load
+      // instruction or equivalent.
+      if (auto *Load = llvm::dyn_cast<InstLoad>(CurInst)) {
+        // An InstLoad always qualifies.
+        LoadDest = Load->getDest();
+        const bool DoLegalize = false;
+        LoadSrc = formMemoryOperand(Load->getSourceAddress(),
+                                    LoadDest->getType(), DoLegalize);
+      } else if (auto *Intrin = llvm::dyn_cast<InstIntrinsicCall>(CurInst)) {
+        // An AtomicLoad intrinsic qualifies as long as it has a valid
+        // memory ordering, and can be implemented in a single
+        // instruction (i.e., not i64).
+        Intrinsics::IntrinsicID ID = Intrin->getIntrinsicInfo().ID;
+        if (ID == Intrinsics::AtomicLoad &&
+            Intrin->getDest()->getType() != IceType_i64 &&
+            Intrinsics::isMemoryOrderValid(
+                ID, getConstantMemoryOrder(Intrin->getArg(1)))) {
+          LoadDest = Intrin->getDest();
+          const bool DoLegalize = false;
+          LoadSrc = formMemoryOperand(Intrin->getArg(0), LoadDest->getType(),
+                                      DoLegalize);
+        }
+      }
+      // A Load instruction can be folded into the following
+      // instruction only if the following instruction ends the Load's
+      // Dest variable's live range.
+      if (LoadDest && Next && Next->isLastUse(LoadDest)) {
+        assert(LoadSrc);
+        Inst *NewInst = nullptr;
+        if (auto *Arith = llvm::dyn_cast<InstArithmetic>(Next)) {
+          Operand *Src0 = Arith->getSrc(0);
+          Operand *Src1 = Arith->getSrc(1);
+          if (canFoldLoadIntoBinaryInst(LoadSrc, LoadDest, Src0, Src1)) {
+            NewInst = InstArithmetic::create(Func, Arith->getOp(),
+                                             Arith->getDest(), Src0, Src1);
+          }
+        } else if (auto *Icmp = llvm::dyn_cast<InstIcmp>(Next)) {
+          Operand *Src0 = Icmp->getSrc(0);
+          Operand *Src1 = Icmp->getSrc(1);
+          if (canFoldLoadIntoBinaryInst(LoadSrc, LoadDest, Src0, Src1)) {
+            NewInst = InstIcmp::create(Func, Icmp->getCondition(),
+                                       Icmp->getDest(), Src0, Src1);
+          }
+        } else if (auto *Fcmp = llvm::dyn_cast<InstFcmp>(Next)) {
+          Operand *Src0 = Fcmp->getSrc(0);
+          Operand *Src1 = Fcmp->getSrc(1);
+          if (canFoldLoadIntoBinaryInst(LoadSrc, LoadDest, Src0, Src1)) {
+            NewInst = InstFcmp::create(Func, Fcmp->getCondition(),
+                                       Fcmp->getDest(), Src0, Src1);
+          }
+        } else if (auto *Select = llvm::dyn_cast<InstSelect>(Next)) {
+          Operand *Src0 = Select->getTrueOperand();
+          Operand *Src1 = Select->getFalseOperand();
+          if (canFoldLoadIntoBinaryInst(LoadSrc, LoadDest, Src0, Src1)) {
+            NewInst = InstSelect::create(Func, Select->getDest(),
+                                         Select->getCondition(), Src0, Src1);
+          }
+        } else if (auto *Cast = llvm::dyn_cast<InstCast>(Next)) {
+          // The load dest can always be folded into a Cast
+          // instruction.
+          Variable *Src0 = llvm::dyn_cast<Variable>(Cast->getSrc(0));
+          if (Src0 == LoadDest) {
+            NewInst = InstCast::create(Func, Cast->getCastKind(),
+                                       Cast->getDest(), LoadSrc);
+          }
+        }
+        if (NewInst) {
+          CurInst->setDeleted();
+          Next->setDeleted();
+          Context.insert(NewInst);
+          // Update NewInst->LiveRangesEnded so that target lowering
+          // may benefit.  Also update NewInst->HasSideEffects.
+          NewInst->spliceLivenessInfo(Next, CurInst);
+        }
+      }
+      Context.advanceCur();
+      Context.advanceNext();
+    }
+  }
+  Func->dump("After load optimization");
+}
+
 bool TargetX8632::doBranchOpt(Inst *I, const CfgNode *NextNode) {
   if (InstX8632Br *Br = llvm::dyn_cast<InstX8632Br>(I)) {
     return Br->optimizeBranch(NextNode);
   }
   return false;
 }
 
 IceString TargetX8632::RegNames[] = {
 #define X(val, encode, name, name16, name8, scratch, preserved, stackptr,      \
           frameptr, isI8, isInt, isFP)                                         \
@@ skipping 212 matching lines @@
   // If there is a separate locals area, this specifies the alignment
   // for it.
   uint32_t LocalsSlotsAlignmentBytes = 0;
   // The entire spill locations area gets aligned to largest natural
   // alignment of the variables that have a spill slot.
   uint32_t SpillAreaAlignmentBytes = 0;
   // A spill slot linked to a variable with a stack slot should reuse
   // that stack slot.
   std::function<bool(Variable *)> TargetVarHook =
       [&VariablesLinkedToSpillSlots](Variable *Var) {
-    if (SpillVariable *SpillVar = llvm::dyn_cast<SpillVariable>(Var)) {
-      assert(Var->getWeight().isZero());
-      if (SpillVar->getLinkedTo() && !SpillVar->getLinkedTo()->hasReg()) {
-        VariablesLinkedToSpillSlots.push_back(Var);
-        return true;
-      }
-    }
-    return false;
-  };
+        if (SpillVariable *SpillVar = llvm::dyn_cast<SpillVariable>(Var)) {
+          assert(Var->getWeight().isZero());
+          if (SpillVar->getLinkedTo() && !SpillVar->getLinkedTo()->hasReg()) {
+            VariablesLinkedToSpillSlots.push_back(Var);
+            return true;
+          }
+        }
+        return false;
+      };
 
   // Compute the list of spilled variables and bounds for GlobalsSize, etc.
   getVarStackSlotParams(SortedSpilledVariables, RegsUsed, &GlobalsSize,
                         &SpillAreaSizeBytes, &SpillAreaAlignmentBytes,
                         &LocalsSlotsAlignmentBytes, TargetVarHook);
   uint32_t LocalsSpillAreaSize = SpillAreaSizeBytes;
   SpillAreaSizeBytes += GlobalsSize;
 
   // Add push instructions for preserved registers.
   uint32_t NumCallee = 0;
@@ skipping 337 matching lines @@
     _and(T, Ctx->getConstantInt32(-Alignment));
     _sub(esp, T);
   }
   _mov(Dest, esp);
 }
 
 void TargetX8632::lowerArithmetic(const InstArithmetic *Inst) {
   Variable *Dest = Inst->getDest();
   Operand *Src0 = legalize(Inst->getSrc(0));
   Operand *Src1 = legalize(Inst->getSrc(1));
+  if (Inst->isCommutative()) {
+    if (!llvm::isa<Variable>(Src0) && llvm::isa<Variable>(Src1))
+      std::swap(Src0, Src1);
+  }
   if (Dest->getType() == IceType_i64) {
     Variable *DestLo = llvm::cast<Variable>(loOperand(Dest));
     Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
     Operand *Src0Lo = loOperand(Src0);
     Operand *Src0Hi = hiOperand(Src0);
     Operand *Src1Lo = loOperand(Src1);
     Operand *Src1Hi = hiOperand(Src1);
     Variable *T_Lo = nullptr, *T_Hi = nullptr;
     switch (Inst->getOp()) {
     case InstArithmetic::_num:
@@ skipping 1701 matching lines @@
     OperandX8632Mem *Loc =
         getMemoryOperandForStackSlot(InVectorElementTy, Slot, Offset);
     _store(legalizeToVar(ElementToInsertNotLegalized), Loc);
 
     Variable *T = makeReg(Ty);
     _movp(T, Slot);
     _movp(Inst->getDest(), T);
   }
 }
 
-namespace {
-
-// Converts a ConstantInteger32 operand into its constant value, or
-// MemoryOrderInvalid if the operand is not a ConstantInteger32.
-uint64_t getConstantMemoryOrder(Operand *Opnd) {
-  if (auto Integer = llvm::dyn_cast<ConstantInteger32>(Opnd))
-    return Integer->getValue();
-  return Intrinsics::MemoryOrderInvalid;
-}
-
-} // end of anonymous namespace
-
 void TargetX8632::lowerIntrinsicCall(const InstIntrinsicCall *Instr) {
   switch (Intrinsics::IntrinsicID ID = Instr->getIntrinsicInfo().ID) {
   case Intrinsics::AtomicCmpxchg: {
     if (!Intrinsics::isMemoryOrderValid(
             ID, getConstantMemoryOrder(Instr->getArg(3)),
             getConstantMemoryOrder(Instr->getArg(4)))) {
       Func->setError("Unexpected memory ordering for AtomicCmpxchg");
       return;
     }
     Variable *DestPrev = Instr->getDest();
@@ skipping 68 matching lines @@
       OperandX8632Mem *Addr = formMemoryOperand(Instr->getArg(0), IceType_f64);
       _movq(T, Addr);
       // Then cast the bits back out of the XMM register to the i64 Dest.
       InstCast *Cast = InstCast::create(Func, InstCast::Bitcast, Dest, T);
       lowerCast(Cast);
       // Make sure that the atomic load isn't elided when unused.
       Context.insert(InstFakeUse::create(Func, Dest->getLo()));
       Context.insert(InstFakeUse::create(Func, Dest->getHi()));
       return;
     }
     InstLoad *Load = InstLoad::create(Func, Dest, Instr->getArg(0));

[jvoung (off chromium), 2015/06/03 21:14:05]

Maybe at some point the load can just be tagged with side-effects, and the
FakeUse can be removed then?

[Jim Stichnoth, 2015/06/03 22:51:36]

This brings up a really good point.  The HasSideEffects flag is great for
preventing DCE in the high level ICE and in the low level instructions, but
there's a disconnect in the lowering phase where the high level side effects
info gets lost/ignored.

I added an issue to track this.
https://code.google.com/p/nativeclient/issues/detail?id=4193

     lowerLoad(Load);
     // Make sure the atomic load isn't elided when unused, by adding a FakeUse.
     // Since lowerLoad may fuse the load w/ an arithmetic instruction,
     // insert the FakeUse on the last-inserted instruction's dest.
     Context.insert(
         InstFakeUse::create(Func, Context.getLastInserted()->getDest()));
     return;
   }
   case Intrinsics::AtomicRMW:
     if (!Intrinsics::isMemoryOrderValid(
             ID, getConstantMemoryOrder(Instr->getArg(3)))) {
       Func->setError("Unexpected memory ordering for AtomicRMW");
       return;
     }
-    lowerAtomicRMW(Instr->getDest(),
-                   static_cast<uint32_t>(llvm::cast<ConstantInteger32>(
-                                             Instr->getArg(0))->getValue()),
-                   Instr->getArg(1), Instr->getArg(2));
+    lowerAtomicRMW(
+        Instr->getDest(),
+        static_cast<uint32_t>(
+            llvm::cast<ConstantInteger32>(Instr->getArg(0))->getValue()),
+        Instr->getArg(1), Instr->getArg(2));
     return;
   case Intrinsics::AtomicStore: {
     if (!Intrinsics::isMemoryOrderValid(
             ID, getConstantMemoryOrder(Instr->getArg(2)))) {
       Func->setError("Unexpected memory ordering for AtomicStore");
       return;
     }
     // We require the memory address to be naturally aligned.
     // Given that is the case, then normal stores are atomic.
     // Add a fence after the store to make it visible.
@@ skipping 822 matching lines @@
 }
 
 } // anonymous namespace
 
 void TargetX8632::lowerLoad(const InstLoad *Load) {
   // A Load instruction can be treated the same as an Assign
   // instruction, after the source operand is transformed into an
   // OperandX8632Mem operand.  Note that the address mode
   // optimization already creates an OperandX8632Mem operand, so it
   // doesn't need another level of transformation.
-  Type Ty = Load->getDest()->getType();
+  Variable *DestLoad = Load->getDest();
+  Type Ty = DestLoad->getType();
   Operand *Src0 = formMemoryOperand(Load->getSourceAddress(), Ty);
-
-  // Fuse this load with a subsequent Arithmetic instruction in the
-  // following situations:
-  //   a=[mem]; c=b+a ==> c=b+[mem] if last use of a and a not in b
-  //   a=[mem]; c=a+b ==> c=b+[mem] if commutative and above is true
-  //
-  // Fuse this load with a subsequent Cast instruction:
-  //   a=[mem]; b=cast(a) ==> b=cast([mem]) if last use of a
-  //
-  // TODO: Clean up and test thoroughly.
-  // (E.g., if there is an mfence-all make sure the load ends up on the
-  // same side of the fence).
-  //
-  // TODO: Why limit to Arithmetic instructions?  This could probably be
-  // applied to most any instruction type.  Look at all source operands
-  // in the following instruction, and if there is one instance of the
-  // load instruction's dest variable, and that instruction ends that
-  // variable's live range, then make the substitution.  Deal with
-  // commutativity optimization in the arithmetic instruction lowering.
-  //
-  // TODO(stichnot): Do load fusing as a separate pass.  Run it before
-  // the bool folding pass.  Modify Ice::Inst to allow src operands to
-  // be replaced, including updating Inst::LiveRangesEnded, to avoid
-  // having to manually mostly clone each instruction type.
-  Inst *NextInst = Context.getNextInst();
-  Variable *DestLoad = Load->getDest();
-  if (NextInst && NextInst->isLastUse(DestLoad)) {
-    if (auto *Arith = llvm::dyn_cast<InstArithmetic>(NextInst)) {
-      InstArithmetic *NewArith = nullptr;
-      Variable *Src0Arith = llvm::dyn_cast<Variable>(Arith->getSrc(0));
-      Variable *Src1Arith = llvm::dyn_cast<Variable>(Arith->getSrc(1));
-      if (Src1Arith == DestLoad && DestLoad != Src0Arith) {
-        NewArith = InstArithmetic::create(
-            Func, Arith->getOp(), Arith->getDest(), Arith->getSrc(0), Src0);
-      } else if (Src0Arith == DestLoad && Arith->isCommutative() &&
-                 DestLoad != Src1Arith) {
-        NewArith = InstArithmetic::create(
-            Func, Arith->getOp(), Arith->getDest(), Arith->getSrc(1), Src0);
-      }
-      if (NewArith) {
-        Arith->setDeleted();
-        Context.advanceNext();
-        lowerArithmetic(NewArith);
-        return;
-      }
-    } else if (auto *Cast = llvm::dyn_cast<InstCast>(NextInst)) {
-      Variable *Src0Cast = llvm::dyn_cast<Variable>(Cast->getSrc(0));
-      if (Src0Cast == DestLoad) {
-        InstCast *NewCast =
-            InstCast::create(Func, Cast->getCastKind(), Cast->getDest(), Src0);
-        Cast->setDeleted();
-        Context.advanceNext();
-        lowerCast(NewCast);
-        return;
-      }
-    }
-  }
-
   InstAssign *Assign = InstAssign::create(Func, DestLoad, Src0);
   lowerAssign(Assign);
 }
 
 void TargetX8632::doAddressOptLoad() {
   Inst *Inst = Context.getCur();
   Variable *Dest = Inst->getDest();
   Operand *Addr = Inst->getSrc(0);
   Variable *Index = nullptr;
   uint16_t Shift = 0;
@@ skipping 707 matching lines @@
   bool IsSrc1ImmOrReg = false;
   if (llvm::isa<Constant>(Src1)) {
     IsSrc1ImmOrReg = true;
   } else if (Variable *Var = llvm::dyn_cast<Variable>(Src1)) {
     if (Var->hasReg())
       IsSrc1ImmOrReg = true;
   }
   return legalize(Src0, IsSrc1ImmOrReg ? (Legal_Reg | Legal_Mem) : Legal_Reg);
 }
 
-OperandX8632Mem *TargetX8632::formMemoryOperand(Operand *Operand, Type Ty) {
+OperandX8632Mem *TargetX8632::formMemoryOperand(Operand *Operand, Type Ty,
+                                                bool DoLegalize) {
   OperandX8632Mem *Mem = llvm::dyn_cast<OperandX8632Mem>(Operand);
   // It may be the case that address mode optimization already creates
   // an OperandX8632Mem, so in that case it wouldn't need another level
   // of transformation.
   if (!Mem) {
     Variable *Base = llvm::dyn_cast<Variable>(Operand);
     Constant *Offset = llvm::dyn_cast<Constant>(Operand);
     assert(Base || Offset);
     if (Offset) {
       // Make sure Offset is not undef.
       Offset = llvm::cast<Constant>(legalize(Offset));
       assert(llvm::isa<ConstantInteger32>(Offset) ||
              llvm::isa<ConstantRelocatable>(Offset));
     }
     Mem = OperandX8632Mem::create(Func, Ty, Base, Offset);
   }
-  return llvm::cast<OperandX8632Mem>(legalize(Mem));
+  return llvm::cast<OperandX8632Mem>(DoLegalize ? legalize(Mem) : Mem);
 }
 
 Variable *TargetX8632::makeReg(Type Type, int32_t RegNum) {
   // There aren't any 64-bit integer registers for x86-32.
   assert(Type != IceType_i64);
   Variable *Reg = Func->makeVariable(Type);
   if (RegNum == Variable::NoRegister)
     Reg->setWeightInfinite();
   else
     Reg->setRegNum(RegNum);
@@ skipping 272 matching lines @@
   case FT_Asm:
   case FT_Iasm: {
     OstreamLocker L(Ctx);
     emitConstantPool<PoolTypeConverter<float>>(Ctx);
     emitConstantPool<PoolTypeConverter<double>>(Ctx);
   } break;
   }
 }
 
 } // end of namespace Ice