Subzero: Transform suitable Load/Arith/Store sequences into RMW ops.

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 443 matching lines @@
       return;
     Func->placePhiStores();
     if (Func->hasError())
       return;
     Func->deletePhis();
     if (Func->hasError())
       return;
     Func->dump("After Phi lowering");
   }
 
+  findRMW();
+
   // Address mode optimization.
   Func->getVMetadata()->init(VMK_SingleDefs);
   Func->doAddressOpt();
 
   // Argument lowering
   Func->doArgLowering();
 
   // Target lowering.  This requires liveness analysis for some parts
   // of the lowering decisions, such as compare/branch fusing.  If
   // non-lightweight liveness analysis is used, the instructions need
@@ skipping 98 matching lines @@
   Func->dump("After stack frame mapping");
 
   // Nop insertion
   if (Ctx->getFlags().shouldDoNopInsertion()) {
     Func->doNopInsertion();
   }
 }
 
 namespace {
 
+bool canRMW(const InstArithmetic *Arith) {
+  Type Ty = Arith->getDest()->getType();
+  bool isI64 = Ty == IceType_i64;
+  bool isVector = isVectorType(Ty);
+
+  switch (Arith->getOp()) {
+  default:
+    return false;
+  case InstArithmetic::Add:
+    return !isI64 && !isVector; // TODO(stichnot): implement

[jvoung (off chromium), 2015/06/16 17:59:22]

not TODO for Add anymore?

[Jim Stichnoth, 2015/06/17 00:15:40]

I meant implement the i64 and vector variants.  Clarified.

+  case InstArithmetic::Sub:
+  case InstArithmetic::And:
+  case InstArithmetic::Or:
+  case InstArithmetic::Xor:
+  case InstArithmetic::Fadd:
+  case InstArithmetic::Fsub:
+  case InstArithmetic::Fmul:
+  case InstArithmetic::Fdiv:
+    return false; // TODO(stichnot): implement
+    return true;
+  case InstArithmetic::Shl:
+  case InstArithmetic::Lshr:
+  case InstArithmetic::Ashr:
+    return false; // TODO(stichnot): implement
+    return !isI64 && !isVector;
+  }
+  // Not handled for lack of simple lowering:
+  //   shift on i64 and vectors

[jvoung (off chromium), 2015/06/16 17:59:22]

Maybe put this earlier, to explain the "return !isI64 && !isVector;" conditions

[Jim Stichnoth, 2015/06/17 00:15:40]

Done.

+  //   mul, udiv, urem, sdiv, srem, frem
+}
+
+} // end of anonymous namespace
+
+void TargetX8632::findRMW() {
+  OstreamLocker L(Func->getContext());
+  Ostream &Str = Func->getContext()->getStrDump();
+  for (CfgNode *Node : Func->getNodes()) {
+    // Walk through the instructions, considering each sequence of 3
+    // instructions, and look for the particular RMW pattern.  Note that this
+    // search can be "broken" (false negatives) if there are intervening deleted
+    // instructions, or intervening instructions that could be safely moved out
+    // of the way to reveal an RMW pattern.
+    auto E = Node->getInsts().end();
+    auto I1 = E, I2 = E, I3 = Node->getInsts().begin();
+    for (; I3 != E; I1 = I2, I2 = I3, ++I3) {
+      if (I1 == E || I2 == E)
+        continue;
+      if (I1->isDeleted() || I2->isDeleted() || I3->isDeleted())
+        continue;
+      if (auto *Load = llvm::dyn_cast<InstLoad>(I1)) {
+        if (auto *Arith = llvm::dyn_cast<InstArithmetic>(I2)) {
+          if (auto *Store = llvm::dyn_cast<InstStore>(I3)) {
+            // Look for:
+            //   a = Load addr
+            //   b = <op> a, other
+            //   Store b, addr
+            // Change to:
+            //   a = Load addr
+            //   b = <op> a, other
+            //   x = FakeDef
+            //   RMW <op>, addr, other, x
+            //   b = Store b, addr, x

[jvoung (off chromium), 2015/06/16 17:59:21]

Is this redefinition of b from " b = Store b, addr, x" okay for liveness because
of inferTwoAddress ?

[Jim Stichnoth, 2015/06/17 00:15:40]

Yes, clarified in the comment.

+            //
+            // With this transformation, the Store instruction acquires a Dest
+            // variable and is now subject to dead code elimination if there are
+            // no more uses of "b".  Variable "x" is a beacon for determining
+            // whether the Store instruction gets dead-code eliminated.  If the
+            // Store instruction is eliminated, then it must be the case that
+            // the RMW instruction ends x's live range, and therefore the RMW
+            // instruction will be retained and later lowered.  On the other
+            // hand, if the RMW instruction does not end x's live range, then
+            // the Store instruction must still be present, and therefore the
+            // RMW instruction is ignored during lowering because it is
+            // redundant with the Store instruction.
+            //
+            // Note that if "a" has further uses, the RMW transformation may
+            // still trigger, resulting in two loads and one store, which is
+            // worse than the original one load and one store.  However, this is
+            // probably rare, and caching probably keeps it just as fast.
+            if (Load->getSourceAddress() != Store->getAddr())
+              continue;
+            if (Arith->getSrc(0) != Load->getDest())
+              continue;
+            if (Arith->getDest() != Store->getData())
+              continue;
+            if (!canRMW(Arith))
+              continue;
+            if (Func->isVerbose(IceV_RMW)) {
+              Str << "Found RMW in " << Func->getFunctionName() << ":\n  ";
+              Load->dump(Func);
+              Str << "\n  ";
+              Arith->dump(Func);
+              Str << "\n  ";
+              Store->dump(Func);
+              Str << "\n";
+            }
+            Variable *Beacon = Func->makeVariable(IceType_i32);
+            Beacon->setWeight(0);
+            Store->setRmwBeacon(Beacon);
+            InstFakeDef *BeaconDef = InstFakeDef::create(Func, Beacon);
+            Node->getInsts().insert(I3, BeaconDef);
+            InstX8632FakeRMW *RMW = InstX8632FakeRMW::create(
+                Func, Arith->getSrc(1), Store->getAddr(), Beacon,
+                Arith->getOp());
+            Node->getInsts().insert(I3, RMW);

[jvoung (off chromium), 2015/06/16 17:59:21]

Just checking: should this be insert(I3, RMW) or insert(BeaconDef, RMW)?

[Jim Stichnoth, 2015/06/17 00:15:40]

This is as intended.  First we insert the BeaconDef before I3 (the store
instruction):
  I1: a = Load addr
  I2: b = <op> a, other
      x = FakeDef
  I3: b = Store b, addr, x

Then we insert the RMW before I3:
  I1: a = Load addr
  I2: b = <op> a, other
      x = FakeDef
      RMW <op>, addr, other, x
  I3: b = Store b, addr, x

+          }
+        }
+      }
+    }
+  }
+}
+
+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
@@ skipping 3776 matching lines @@
     _store(ValueHi, llvm::cast<OperandX8632Mem>(hiOperand(NewAddr)));
     _store(ValueLo, llvm::cast<OperandX8632Mem>(loOperand(NewAddr)));
   } else if (isVectorType(Ty)) {
     _storep(legalizeToVar(Value), NewAddr);
   } else {
     Value = legalize(Value, Legal_Reg | Legal_Imm);
     _store(Value, NewAddr);
   }
 }
 
 void TargetX8632::doAddressOptStore() {

[jvoung (off chromium), 2015/06/16 17:59:22]

At some point, is it worth having a doAddressOptRMW() ?

[Jim Stichnoth, 2015/06/17 00:15:40]

Yikes!  I didn't mean to disable address mode optimization for RMW.

I moved findRMW() to be after address mode optimization, using a deeper test of
whether the Load and Dest addresses are the same.

[jvoung (off chromium), 2015/06/17 16:40:22]

Could add a test case to the .ll that shows address mode optimization still
succeeds from the new pass ordering?

[Jim Stichnoth, 2015/06/18 05:15:12]

Another good catch!  I forgot that the address mode optimization deletes the
original load/store instruction and inserts a new one, so the deleted
instructions need to be skipped over.

Added a new test.

   InstStore *Inst = llvm::cast<InstStore>(Context.getCur());
   Operand *Data = Inst->getData();
   Operand *Addr = Inst->getAddr();
   Variable *Index = nullptr;
   uint16_t Shift = 0;
   int32_t Offset = 0; // TODO: make Constant
   Variable *Base = llvm::dyn_cast<Variable>(Addr);
   // Vanilla ICE store instructions should not use the segment registers,
   // and computeAddressOpt only works at the level of Variables and Constants,
   // not other OperandX8632Mem, so there should be no mention of segment
   // registers there either.
   const OperandX8632Mem::SegmentRegisters SegmentReg =
       OperandX8632Mem::DefaultSegment;
   computeAddressOpt(Func, Inst, Base, Index, Shift, Offset);
   if (Base && Addr != Base) {
     Inst->setDeleted();
     Constant *OffsetOp = Ctx->getConstantInt32(Offset);
     Addr = OperandX8632Mem::create(Func, Data->getType(), Base, OffsetOp, Index,
                                    Shift, SegmentReg);
-    Context.insert(InstStore::create(Func, Data, Addr));
+    InstStore *NewStore = InstStore::create(Func, Data, Addr);
+    if (Inst->getDest())
+      NewStore->setRmwBeacon(Inst->getRmwBeacon());
+    Context.insert(NewStore);
   }
 }
 
 void TargetX8632::lowerSwitch(const InstSwitch *Inst) {
   // This implements the most naive possible lowering.
   // cmp a,val[0]; jeq label[0]; cmp a,val[1]; jeq label[1]; ... jmp default
   Operand *Src0 = Inst->getComparison();
   SizeT NumCases = Inst->getNumCases();
   if (Src0->getType() == IceType_i64) {
     Src0 = legalize(Src0); // get Base/Index into physical registers
@@ skipping 82 matching lines @@
       NextCast->setDeleted();
       _movp(NextCast->getDest(), legalizeToVar(SignExtendedResult));
       // Skip over the instruction.
       Context.advanceNext();
     }
   }
 }
 
 void TargetX8632::lowerUnreachable(const InstUnreachable * /*Inst*/) { _ud2(); }
 
+void TargetX8632::lowerRMW(const InstX8632FakeRMW *RMW) {
+  // If the beacon variable's live range does not end in this
+  // instruction, then it must end in the modified Store instruction
+  // that follows.  This means that the original Store instruction is
+  // still there, either because the value being stored is used beyond
+  // the Store instruction, or because dead code elimination did not
+  // happen.  In either case, we cancel RMW lowering (and the caller
+  // deletes the RMW instruction).
+  if (!RMW->isLastUse(RMW->getBeacon()))
+    return;
+  Operand *Src = RMW->getData();
+  Type Ty = Src->getType();
+  Operand *Addr = formMemoryOperand(RMW->getAddr(), Ty);
+  if (Ty == IceType_i64) {
+    // TODO(stichnot): Implement.
+  } else if (isVectorType(Ty)) {
+    // TODO(stichnot): Implement.
+  } else {
+    // i8, i16, i32, f32, f64
+    switch (RMW->getOp()) {
+    default:
+      // TODO(stichnot): Implement other arithmetic operators.
+      break;
+    case InstArithmetic::Add:
+      Src = legalize(Src, Legal_Reg | Legal_Imm);
+      _add_rmw(Addr, Src);
+      return;
+    }
+  }
+  llvm::report_fatal_error("Couldn't lower RMW instruction");
+}
+
+void TargetX8632::lowerOther(const Inst *Instr) {
+  if (const auto *RMW = llvm::dyn_cast<InstX8632FakeRMW>(Instr)) {
+    lowerRMW(RMW);
+  } else {
+    TargetLowering::lowerOther(Instr);
+  }
+}
+
 // Turn an i64 Phi instruction into a pair of i32 Phi instructions, to
 // preserve integrity of liveness analysis.  Undef values are also
 // turned into zeroes, since loOperand() and hiOperand() don't expect
 // Undef input.
 void TargetX8632::prelowerPhis() {
   CfgNode *Node = Context.getNode();
   for (Inst &I : Node->getPhis()) {
     auto Phi = llvm::dyn_cast<InstPhi>(&I);
     if (Phi->isDeleted())
       continue;
@@ skipping 604 matching lines @@
     emitConstantPool<PoolTypeConverter<float>>(Ctx);
     emitConstantPool<PoolTypeConverter<double>>(Ctx);
   } break;
   }
 }
 
 TargetHeaderX8632::TargetHeaderX8632(GlobalContext *Ctx)
     : TargetHeaderLowering(Ctx) {}
 
 } // end of namespace Ice