Subzero: Fix over-aggressive bool folding.

src/IceTargetLoweringX86BaseImpl.h

 //===- subzero/src/IceTargetLoweringX86BaseImpl.h - x86 lowering -*- C++ -*-==//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 133 matching lines @@
   const Inst *getProducerFor(const Operand *Opnd) const;
   void dump(const Cfg *Func) const;
 
 private:
   /// Returns true if Producers contains a valid entry for the given VarNum.
   bool containsValid(SizeT VarNum) const {
     auto Element = Producers.find(VarNum);
     return Element != Producers.end() && Element->second.Instr != nullptr;
   }
   void setInvalid(SizeT VarNum) { Producers[VarNum].Instr = nullptr; }
+  void invalidateProducersOnStore(const Inst *Instr);
   /// Producers maps Variable::Number to a BoolFoldingEntry.
   CfgUnorderedMap<SizeT, BoolFoldingEntry<Traits>> Producers;
 };
 
 template <typename Traits>
 BoolFoldingEntry<Traits>::BoolFoldingEntry(Inst *I)
     : Instr(I), IsComplex(BoolFolding<Traits>::hasComplexLowering(I)) {}
 
 template <typename Traits>
 typename BoolFolding<Traits>::BoolFoldingProducerKind
@@ skipping 81 matching lines @@
   case PK_Fcmp:
     return (ConsumerKind == CK_Br) || (ConsumerKind == CK_Select);
   case PK_Arith:
     return ConsumerKind == CK_Br;
   }
 }
 
 template <typename Traits> void BoolFolding<Traits>::init(CfgNode *Node) {
   Producers.clear();
   for (Inst &Instr : Node->getInsts()) {
+    if (Instr.isDeleted())

[Eric Holk, 2016/04/21 22:09:43]

As a future CL, it would probably be nice to add a non-deleted instructions
iterator (or maybe active or live instructions instead of calling them
non-deleted) so we don't have to remember to do this check.

[Jim Stichnoth, 2016/04/21 22:50:29]

That's a great idea.

+      continue;
+    invalidateProducersOnStore(&Instr);
     // Check whether Instr is a valid producer.
     Variable *Var = Instr.getDest();
-    if (!Instr.isDeleted() // only consider non-deleted instructions
-        && Var             // only instructions with an actual dest var
+    if (Var // only consider instructions with an actual dest var
         && Var->getType() == IceType_i1          // only bool-type dest vars
         && getProducerKind(&Instr) != PK_None) { // white-listed instructions
       Producers[Var->getIndex()] = BoolFoldingEntry<Traits>(&Instr);
     }
     // Check each src variable against the map.
     FOREACH_VAR_IN_INST(Var, Instr) {
       SizeT VarNum = Var->getIndex();
       if (!containsValid(VarNum))
         continue;
       // All valid consumers use Var as the first source operand
@@ skipping 62 matching lines @@
   Ostream &Str = Func->getContext()->getStrDump();
   for (auto &I : Producers) {
     if (I.second.Instr == nullptr)
       continue;
     Str << "Found foldable producer:\n  ";
     I.second.Instr->dump(Func);
     Str << "\n";
   }
 }
 
+/// If the given instruction has potential memory side effects (e.g. store, rmw,
+/// or a call instruction with potential memory side effects), then we must not
+/// allow a pre-store Producer instruction with memory operands to be folded
+/// into a post-store Consumer instruction.  If this is detected, the Producer
+/// is invalidated.
+///
+/// We use the Producer's IsLiveOut field to determine whether any potential
+/// Consumers come after this store instruction.  If IsLiveOut has already been
+/// set to false, then we know the folding is safe from the store instruction.

[John, 2016/04/21 22:50:02]

"If IsLiveOut has already been set to false, then we know the folding is safe
from the store instruction." why?

[Jim Stichnoth, 2016/04/21 23:31:35]

Done, hopefully it's more explanatory now.

+template <typename Traits>
+void BoolFolding<Traits>::invalidateProducersOnStore(const Inst *Instr) {
+  if (!Instr->isMemoryWrite())
+    return;
+  for (auto &ProducerPair : Producers) {
+    if (!ProducerPair.second.IsLiveOut)
+      continue;
+    Inst *PInst = ProducerPair.second.Instr;
+    if (PInst == nullptr)
+      continue;
+    bool HasMemOperand = false;
+    const SizeT SrcSize = PInst->getSrcSize();
+    for (SizeT I = 0; !HasMemOperand && I < SrcSize; ++I) {

[John, 2016/04/21 22:50:02]

why not breaking instead? I would expect llvm to efficiently lower

for (var = init; var < const; ++var)

but I would be surprised if it managed to do anything decent with moar
complicated fors...

[Jim Stichnoth, 2016/04/21 23:31:35]

Done.

+      if (llvm::isa<typename Traits::X86OperandMem>(PInst->getSrc(I))) {
+        HasMemOperand = true;
+      }
+    }
+    if (!HasMemOperand)
+      continue;
+    setInvalid(ProducerPair.first);
+  }
+}
+
 template <typename TraitsType>
 void TargetX86Base<TraitsType>::initNodeForLowering(CfgNode *Node) {
   FoldingInfo.init(Node);
   FoldingInfo.dump(Func);
 }
 
 template <typename TraitsType>
 TargetX86Base<TraitsType>::TargetX86Base(Cfg *Func)
     : TargetLowering(Func), NeedSandboxing(SandboxingType == ST_NaCl) {
   static_assert(
@@ skipping 7088 matching lines @@
         emitGlobal(*Var, SectionSuffix);
       }
     }
   } break;
   }
 }
 } // end of namespace X86NAMESPACE
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGX86BASEIMPL_H