Subzero: Add a peephole to fuse cmpxchg w/ later cmp+branch.

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 2574 matching lines @@
     }
     if (!Intrinsics::VerifyMemoryOrder(
              llvm::cast<ConstantInteger>(Instr->getArg(4))->getValue())) {
       Func->setError("Unexpected memory ordering (failure) for AtomicCmpxchg");
       return;
     }
     Variable *DestPrev = Instr->getDest();
     Operand *PtrToMem = Instr->getArg(0);
     Operand *Expected = Instr->getArg(1);
     Operand *Desired = Instr->getArg(2);
+    if (tryOptimizedCmpxchgCmpBr(DestPrev, PtrToMem, Expected, Desired))
+      return;
     lowerAtomicCmpxchg(DestPrev, PtrToMem, Expected, Desired);
-    // TODO(jvoung): If we peek ahead a few instructions and see how
-    // DestPrev is used (typically via another compare and branch),
-    // we may be able to optimize. If the result truly is used by a
-    // compare + branch, and the comparison is for equality, then we can
-    // optimize out the later compare, and fuse with the later branch.
     return;
   }
   case Intrinsics::AtomicFence:
     if (!Intrinsics::VerifyMemoryOrder(
              llvm::cast<ConstantInteger>(Instr->getArg(0))->getValue())) {
       Func->setError("Unexpected memory ordering for AtomicFence");
       return;
     }
     _mfence();
     return;
@@ skipping 295 matching lines @@
   }
   Variable *T_eax = makeReg(Expected->getType(), Reg_eax);
   _mov(T_eax, Expected);
   OperandX8632Mem *Addr = FormMemoryOperand(Ptr, Expected->getType());
   Variable *DesiredReg = legalizeToVar(Desired);
   const bool Locked = true;
   _cmpxchg(Addr, T_eax, DesiredReg, Locked);
   _mov(DestPrev, T_eax);
 }
 
+bool TargetX8632::tryOptimizedCmpxchgCmpBr(Variable *Dest, Operand *PtrToMem,
+                                           Operand *Expected,
+                                           Operand *Desired) {
+  if (Ctx->getOptLevel() == Opt_m1)
+    return false;
+  // Peek ahead a few instructions and see how Dest is used.
+  // It's very common to have:
+  //
+  // %x = call i32 @llvm.nacl.atomic.cmpxchg.i32(i32* ptr, i32 %expected, ...)
+  // [%y_phi = ...] // list of phi stores
+  // %p = icmp eq i32 %x, %expected
+  // br i1 %p, label %l1, label %l2
+  //
+  // which we can optimize into:
+  //
+  // %x = <cmpxchg code>
+  // [%y_phi = ...] // list of phi stores
+  // br eq, %l1, %l2
+  InstList::iterator I = Context.getCur();

[Jim Stichnoth, 2014/07/25 17:27:47]

Try to use LoweringContext instead of directly using InstList::iterator.  The
main thing is you get iteration while automatically ignoring deleted
instructions.

It may be that functionality would need to be added to LoweringContext. :)

[jvoung (off chromium), 2014/07/28 22:55:26]

Good point about the skipping deleted instructions. Done (at least used the
advance() method).

+  // I is currently the InstIntrinsicCall. Peek past that.
+  // This assumes that the atomic cmpxchg has not been lowered yet,
+  // so that the instructions seen in the scan from "Cur" is simple.
+  assert(llvm::isa<InstIntrinsicCall>(*I));
+  if (++I == Context.getEnd())
+    return false;
+  // There might be phi assignments right before the compare+branch, since this

[Jim Stichnoth, 2014/07/25 17:27:46]

I suggest also adding a note in the Phi lowering pass documenting places where
there may be assumptions on how it works, namely here and the scalar icmp/br
fusing code.

Phi lowering is on the list of things to be improved in Subzero.  One
possibility is to split edges and insert Phis along the edges.  (This would only
simplify code like this that tries to account for the assignments.)  Another
possibility is move the assignments around into other valid spots in the basic
block, which might change some other assumptions.

[jvoung (off chromium), 2014/07/28 22:55:26]

Done (added to the existing comment). The splitting sounds nice to avoid these
assumptions. I assume the "finding other valid spots" is more for optimization
or perhaps for code randomization?

[Jim Stichnoth, 2014/07/29 18:08:44]

I was thinking more about possible optimizations.  For example, for certain
kinds of cheap register allocators, we could try to move the Phi assignment
closer to the last use of the Phi source operand so that the source operand is
more likely to be available in a physical register.  But code randomization may
be a good idea.

+  // could be a backward branch for a loop. This placement of assignments is
+  // determined by placePhiStores().
+  std::vector<InstAssign *> PhiAssigns;
+  while (InstAssign *PhiAssign = llvm::dyn_cast<InstAssign>(*I)) {
+    if (PhiAssign->getDest() == Dest)
+      return false;
+    PhiAssigns.push_back(PhiAssign);
+    if (++I == Context.getEnd())
+      return false;
+  }
+  if (InstIcmp *NextCmp = llvm::dyn_cast<InstIcmp>(*I)) {
+    if (!(NextCmp->getCondition() == InstIcmp::Eq &&
+          ((NextCmp->getSrc(0) == Dest && NextCmp->getSrc(1) == Expected) ||
+           (NextCmp->getSrc(1) == Dest && NextCmp->getSrc(0) == Expected)))) {
+      return false;
+    }
+    if (++I == Context.getEnd())
+      return false;
+    if (InstBr *NextBr = llvm::dyn_cast<InstBr>(*I)) {
+      if (!NextBr->isUnconditional() &&
+          NextCmp->getDest() == NextBr->getCondition() &&
+          NextBr->isLastUse(NextCmp->getDest())) {
+        lowerAtomicCmpxchg(Dest, PtrToMem, Expected, Desired);
+        for (size_t i = 0; i < PhiAssigns.size(); ++i) {
+          // Lower the phi assignments now, before the branch (same placement
+          // as before).
+          InstAssign *PhiAssign = PhiAssigns[i];
+          lowerAssign(PhiAssign);
+          PhiAssign->setDeleted();
+          Context.advanceNext();
+        }
+        _br(InstX8632::Br_e, NextBr->getTargetTrue(), NextBr->getTargetFalse());
+        // Skip over the old compare and branch, by deleting them.
+        NextCmp->setDeleted();
+        NextBr->setDeleted();
+        Context.advanceNext();
+        Context.advanceNext();
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
 void TargetX8632::lowerAtomicRMW(Variable *Dest, uint32_t Operation,
                                  Operand *Ptr, Operand *Val) {
   bool NeedsCmpxchg = false;
   LowerBinOp Op_Lo = NULL;
   LowerBinOp Op_Hi = NULL;
   switch (Operation) {
   default:
     Func->setError("Unknown AtomicRMW operation");
     return;
   case Intrinsics::AtomicAdd: {
@@ skipping 1007 matching lines @@
     for (SizeT i = 0; i < Size; ++i) {
       Str << "\t.byte\t" << (((unsigned)Data[i]) & 0xff) << "\n";
     }
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   }
   Str << "\t" << (IsInternal ? ".local" : ".global") << "\t" << MangledName
       << "\n";
 }
 
 } // end of namespace Ice