Subzero: Initial implementation of BB Local CSE

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 489 matching lines @@
   for (CfgNode *Node : reverse_range(ReversedReachable))
     Shuffled.push_back(Node);
   for (CfgNode *Node : Unreachable)
     Shuffled.push_back(Node);
   assert(Nodes.size() == Shuffled.size());
   swapNodes(Shuffled);
 
   dump("After basic block shuffling");
 }
 
+void Cfg::localCSE() {

[Jim Stichnoth, 2016/05/23 16:52:56]

I'd like to have a comment here briefly describing the assumptions and scope of
the analysis/transformation.  E.g., block-local; target common subexpressions
left by GEP simplification pass; allow for this to be done on non-SSA form such
as after simple Phi lowering.

[manasijm, 2016/05/23 23:13:30]

Done.

+  TimerMarker T(TimerStack::TT_localCse, this);
+  struct InstHash {
+    size_t operator()(const Inst *Instr) const {
+      auto Kind = Instr->getKind();
+      auto Result =
+          std::hash<typename std::underlying_type<Inst::InstKind>::type>()(
+              Kind);
+      for (SizeT i = 0; i < Instr->getSrcSize(); ++i) {
+        auto *Opnd = Instr->getSrc(i);
+        if (auto *Var = llvm::dyn_cast<Variable>(Opnd)) {
+          Result ^= std::hash<SizeT>()(Var->getIndex());

[Jim Stichnoth, 2016/05/23 16:52:57]

This is a repetition of the VariableHash implementation below, hopefully the
duplication can be avoided.

[manasijm, 2016/05/23 23:13:30]

Done.

+        } else if (Constant *Const = llvm::dyn_cast<Constant>(Opnd)) {
+          Result ^= std::hash<Constant *>()(Const);
+          // TODO : get Value of ConstantPrimitive

[Jim Stichnoth, 2016/05/23 16:52:57]

If I understand this correctly, your hash function is based on the pointer
value.  Please hash on contents instead, otherwise you risk non-deterministic
execution.  Perhaps it wouldn't affect the output directly, but it might affect
bucketing performance?  And it's just not a good path to start down.

Suggestion: add a virtual hash method to Operand.

[manasijm, 2016/05/23 23:13:30]

Done.

+        } else
+          Result ^= std::hash<Operand *>()(Opnd);
+      }
+      return Result;
+    }
+  };
+  struct InstEq {
+    bool srcEq(const Operand *A, const Operand *B) const {
+      if (!(llvm::isa<Variable>(A) || (llvm::isa<Constant>(A))) ||

[Jim Stichnoth, 2016/05/23 16:52:56]

This is really hard to read/understand.  How about something more like:

  if (llvm::isa<Variable>(A))
    return (A == B);
  if (llvm::isa<Constant>(A))
    return (A == B);
  return false;

[manasijm, 2016/05/23 23:13:30]

Done.

+          !(llvm::isa<Variable>(B) || (llvm::isa<Constant>(B))))
+        return false;
+      // No reason this has to an error. Returning false just disables the cse

[Jim Stichnoth, 2016/05/23 16:52:57]

"has to an error" ==> "has to be an error" ?

And no reason for *what* to be an error?  I don't see any errors being signaled.

+      // optimization for this particular case
+      return (A == B);
+    }
+    bool operator()(const Inst *InstrA, const Inst *InstrB) const {
+      if ((InstrA->getKind() != InstrB->getKind()) ||
+          (InstrA->getSrcSize() != InstrB->getSrcSize()))
+        return false;
+
+      if (auto *A = llvm::dyn_cast<InstArithmetic>(InstrA)) {
+        auto B = llvm::cast<InstArithmetic>(InstrB);

[Jim Stichnoth, 2016/05/23 16:52:56]

auto *

[manasijm, 2016/05/23 23:13:30]

Done.

+        // A, B are guranteed to be of the same 'kind' at this point

[Jim Stichnoth, 2016/05/23 16:52:57]

guaranteed

[manasijm, 2016/05/23 23:13:30]

Done.

+        // So, dyn_Cast is not needed

[Jim Stichnoth, 2016/05/23 16:52:57]

dyn_cast

[manasijm, 2016/05/23 23:13:30]

Done.

+        if (A->getOp() != B->getOp())
+          return false;
+      }
+      // Does not enter loop if different kind or number of operands
+      for (SizeT i = 0; i < InstrA->getSrcSize(); ++i) {
+        if (!srcEq(InstrA->getSrc(i), InstrB->getSrc(i)))
+          return false;
+      }
+      return true;
+    }
+  };
+  struct VariableHash {
+    size_t operator()(const Variable *Var) const {
+      return std::hash<SizeT>()(Var->getIndex());
+    }
+  };
+  for (CfgNode *Node : getNodes()) {
+    CfgUnorderedSet<Inst *, InstHash, InstEq> Seen;
+
+    CfgUnorderedMap<Variable *, Variable *, VariableHash> Replacements;
+    // Combining the above two into a single data structure might consume less
+    // memory but will be slower i.e map of Instruction -> Set of Variables
+
+    CfgUnorderedMap<Variable *, std::vector<Inst *>, VariableHash> Dependency;
+    // Not necessary for SSA, still keeping it in case this pass is not run at
+    // the beginning. Remove to improve performace.
+
+    for (Inst &Instr : Node->getInsts()) {
+      if (Instr.isDeleted() || !llvm::isa<InstArithmetic>(&Instr))
+        continue;
+
+      // Invalidate replacements
+      auto Iter = Replacements.find(Instr.getDest());
+      if (Iter != Replacements.end()) {
+        Replacements.erase(Iter);
+      }
+
+      // Invalidate 'seen' instructions whose operands were just updated.
+      auto DepIter = Dependency.find(Instr.getDest());
+      if (DepIter != Dependency.end()) {
+        for (auto Dep : DepIter->second) {

[Jim Stichnoth, 2016/05/23 16:52:57]

I think this use of "auto" is getting too deep for easy comprehension.  Can you
do something like one of these?

  for (auto *DepInst : DepIter->second) { ... }

  for (Inst *Dep : DepIter->second) { ... }

(assuming I managed to work out the types correctly)

[manasijm, 2016/05/23 23:13:30]

Done.

+          Seen.erase(Dep);
+        }
+      }
+      // The above two can be removed if SSA is assumed.
+
+      // Replace - doing this before checking for repetitions might enable more
+      // optimizations
+      for (SizeT i = 0; i < Instr.getSrcSize(); ++i) {
+        auto *Opnd = Instr.getSrc(i);
+        if (Variable *const Var = llvm::dyn_cast<Variable>(Opnd)) {

[Jim Stichnoth, 2016/05/23 16:52:57]

"Variable *const Var" just means that the value of the Var pointer won't change.
 It doesn't prevent Var->SomeField from being changed.  What if any const do you
really want here?

[manasijm, 2016/05/23 23:13:30]

Artifact from first patch set.

+          if (Replacements.find(Var) != Replacements.end()) {
+            Instr.replaceSource(i, Replacements[Var]);
+          }
+        }
+      }
+
+      // Check for repetitions
+      auto SeenIter = Seen.find(&Instr);
+      if (SeenIter != Seen.end()) { // seen before
+        const Inst *Found = *SeenIter;
+        Replacements[Instr.getDest()] = Found->getDest();
+      } else { // new
+        Seen.insert(&Instr);
+
+        // Update dependencies
+        for (SizeT i = 0; i < Instr.getSrcSize(); ++i) {
+          auto *Opnd = Instr.getSrc(i);
+          if (auto *Var = llvm::dyn_cast<Variable>(Opnd)) {
+            Dependency[Var].push_back(&Instr);
+          }
+        }
+      }
+    }
+  }
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();
 }
 
 void Cfg::sortAndCombineAllocas(CfgVector<Inst *> &Allocas,
                                 uint32_t CombinedAlignment, InstList &Insts,
                                 AllocaBaseVariableType BaseVariableType) {
   if (Allocas.empty())
     return;
@@ skipping 958 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice