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
 /// \brief Implements the Cfg class.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 
 #include "IceAssembler.h"
 #include "IceBitVector.h"
 #include "IceCfgNode.h"
 #include "IceClFlags.h"
 #include "IceDefs.h"
 #include "IceELFObjectWriter.h"
 #include "IceGlobalInits.h"
 #include "IceInst.h"
 #include "IceInstVarIter.h"
 #include "IceLiveness.h"
 #include "IceLoopAnalyzer.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
-

[Jim Stichnoth, 2016/05/19 01:35:50]

don't remove this separator blank line

[manasijm, 2016/05/19 17:50:16]

Done.

 #include <memory>
 #include <utility>
 
 namespace Ice {
 
 Cfg::Cfg(GlobalContext *Ctx, uint32_t SequenceNumber)
     : Ctx(Ctx), SequenceNumber(SequenceNumber), VMask(getFlags().getVerbose()),
       FunctionName(), NextInstNumber(Inst::NumberInitial), Live(nullptr) {
   Allocator.reset(new ArenaAllocator());
   NodeStrings.reset(new StringPool);
@@ skipping 459 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/19 01:35:49]

(putting this comment here for lack of a better place)

This CL definitely needs tests.  I think you should construct a new .ll test
file and demonstrate expected behavior for x86-32 and x86-64.

[manasijm, 2016/05/19 02:01:52]

I have not managed to isolate a small example yet unfortunately.
None of the convoluted field access constructs I produced on my own generated
anything similar to what 188.ammp had. 

+  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 (unsigned int i = 0; i < Instr->getSrcSize(); ++i) {

[Jim Stichnoth, 2016/05/19 01:35:50]

SizeT instead of unsigned int

+        Operand *Opr = Instr->getSrc(i);

[Jim Stichnoth, 2016/05/19 01:35:49]

I would name it not "Opr", but "Op" or "Opnd" to follow other existing
conventions.  (Unfortunately the most popular name for an Operand* variable is
"Operand", which isn't good...)

+        if (Variable *Var = llvm::dyn_cast<Variable>(Opr)) {

[Jim Stichnoth, 2016/05/19 01:35:49]

auto *Var
because the type is already clear from the dyn_cast<>

[manasijm, 2016/05/19 17:50:16]

Done.

+          Result ^= std::hash<uint32_t>()(Var->getIndex());

[Jim Stichnoth, 2016/05/19 01:35:49]

Can you use SizeT instead of uint32_t, to match the getIndex() declaration?

[manasijm, 2016/05/19 17:50:16]

Done.

+        } else if (Constant *Cst = llvm::dyn_cast<Constant>(Opr)) {

[Jim Stichnoth, 2016/05/19 01:35:49]

Name it "Const" instead of "Cst" for consistency.

And use "auto *Const = ..."

[manasijm, 2016/05/19 02:01:53]

Ok, didn't do that in the first place because const being a keyword, Const might
look confusing.

+          Result ^= std::hash<Constant *>()(
+              Cst); // TODO : get Value ConstantPrimitive

[Jim Stichnoth, 2016/05/19 01:35:49]

TODO(manasijm): get ...

Also, probably put the TODO comment on a separate line so that clang-format
doesn't do this horrible thing.

+        } else
+          Result ^= std::hash<Operand *>()(Opr);
+      }
+      return Result;

[Jim Stichnoth, 2016/05/19 01:35:49]

Use early returns more aggressively, per
http://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-sim...
.

E.g.:
  if (auto *Var = llvm::dyn_cast<Variable>) {
    return ...;
  }
  if (auto *Const = ...) {
    return ...;
  }
etc.

[manasijm, 2016/05/19 17:50:16]

Not applicable here, all the sources has to be incorporated in the hash.
Will do this for InstEq.

+    }
+  };
+  struct InstEq {
+    bool operator()(Inst *const InstrA, Inst *const InstrB) const {

[Jim Stichnoth, 2016/05/19 01:35:48]

Shouldn't this be "const Inst *InstrA"?  Those are two different meanings.

[manasijm, 2016/05/19 02:01:53]

I had some const correctness trouble with that. Will recheck.

[manasijm, 2016/05/19 17:50:16]

Done.

+      bool Result = (InstrA->getKind() == InstrB->getKind()) &&
+                    (InstrA->getSrcSize() == InstrB->getSrcSize());

[Jim Stichnoth, 2016/05/19 01:35:48]

I think this can be made clearer and more efficient through early returns.

The way this is structured, if Result every becomes false, it will always remain
false.  So why not early-return false when any of the intermediate conditions
are false, and then return true at the end after everything is checked.

+
+      if (llvm::isa<InstArithmetic>(InstrA)) {

[Jim Stichnoth, 2016/05/19 01:35:49]

if (auto *A = llvm::dyn_cast<InstArithmetic>(InstrA)) {

+        auto A = llvm::dyn_cast<InstArithmetic>(InstrA);

[Jim Stichnoth, 2016/05/19 01:35:49]

auto *A
auto *B

+        auto B = llvm::dyn_cast<InstArithmetic>(InstrB);

[Jim Stichnoth, 2016/05/19 01:35:50]

use llvm::cast<> instead of llvm::dyn_cast<> here.

+        Result = Result && (A->getOp() == B->getOp());
+      }
+      // Does not enter loop if different kind or number of operands
+      for (unsigned int i = 0; i < InstrA->getSrcSize() && Result; ++i) {

[Jim Stichnoth, 2016/05/19 01:35:49]

SizeT i

+        Result = Result && (InstrA->getSrc(i) == InstrB->getSrc(i));

[Jim Stichnoth, 2016/05/19 01:35:48]

Be aware that Operand* pointer equality is fine with Constant* and Variable*,
but not necessarily for a target-specific operand type, e.g. X86OperandMem. 
It's not a problem now since this pass is very early, before any target-specific
operands are created, but it would be nice to make it more future-proof.

For example, create a virtual method in the Operand base class, where the
default implementation does a llvm::report_fatal_error(), and then Variable and
Constant override it with a simple pointer comparison.

[manasijm, 2016/05/19 02:01:52]

Or just returning false if they are not Constant* or Variable* should work.
Why should it be a fatal error ?

+      }
+      return Result;
+    }
+  };
+  struct VariableHash {
+    size_t operator()(Variable *Var) const {

[Jim Stichnoth, 2016/05/19 01:35:49]

const Variable *
?

+      return std::hash<uint32_t>()(Var->getIndex());

[Jim Stichnoth, 2016/05/19 01:35:49]

Can this be SizeT instead of uint32_t?

+    }
+  };
+  for (CfgNode *Node : getNodes()) {
+    std::unordered_map<Inst *, Variable *, InstHash, InstEq,

[Jim Stichnoth, 2016/05/19 01:35:49]

You should be able to do:

CfgUnorderedMap<Inst *, Variable *, InstHash, InstEq> Seen;

+                       CfgLocalAllocator<std::pair<Inst *const, Variable *>>>
+        Seen;
+    // This could be converted to an unordered_set without much effort.

[Jim Stichnoth, 2016/05/19 01:35:48]

If that's true, and reasonable, then just do it?
You also have CfgUnorderedSet<> available.

+    std::unordered_map<
+        Variable *, Variable *, VariableHash, std::equal_to<Variable *>,
+        CfgLocalAllocator<std::pair<Variable *const, Variable *>>> Replacements;
+    // Combining the above two into a single data structure

[Jim Stichnoth, 2016/05/19 01:35:50]

Reflow comment to 80-col

+    // might consume less memory but will be slower
+    // i.e map of Instruction -> Vector/Set of Variables
+    std::unordered_map<
+        Variable *, std::vector<Inst *>, VariableHash,
+        std::equal_to<Variable *>,
+        CfgLocalAllocator<std::pair<Variable *const, std::vector<Inst *>>>>
+        Dependency;
+    // Not necessary for SSA, still keeping it in case this pass is

[Jim Stichnoth, 2016/05/19 01:35:50]

reflow comment

+    // not run at the beginning. Remove to improve performace.
+
+    for (Inst &Instr : Node->getInsts()) {
+      if (Instr.isDeleted() || !llvm::isa<InstArithmetic>(&Instr))
+        continue;
+
+      auto Iter = Replacements.find(Instr.getDest());
+      if (Iter != Replacements.end()) {
+        Replacements.erase(Iter);
+      }
+
+      auto DIter = Dependency.find(Instr.getDest());
+      if (DIter != Dependency.end()) {
+        for (auto Dep : DIter->second) {
+          Seen.erase(Dep);
+        }
+      }
+
+      // replace - doing this before checking for repitions

[Jim Stichnoth, 2016/05/19 01:35:49]

repetitions
and reflow to 80-col

+      // might enable more optimizations
+      for (unsigned int i = 0; i < Instr.getSrcSize(); ++i) {

[Jim Stichnoth, 2016/05/19 01:35:48]

SizeT

+        Operand *Opr = Instr.getSrc(i);
+        if (Variable *const Var = llvm::dyn_cast<Variable>(Opr)) {

[Jim Stichnoth, 2016/05/19 01:35:48]

auto *

+          if (Replacements.find(Var) != Replacements.end()) {
+            Instr.replaceSource(i, Replacements[Var]);
+          }
+        }
+      }
+
+      // check for repititions

[Jim Stichnoth, 2016/05/19 01:35:48]

repetitions

[manasijm, 2016/05/19 02:01:53]

typo, will update on next patchset.

[manasijm, 2016/05/19 17:50:16]

Done.

+
+      if (Seen.find(&Instr) != Seen.end()) { // seen before
+        Replacements[Instr.getDest()] = Seen[&Instr];
+        // Instr.setDeleted();

[Jim Stichnoth, 2016/05/19 01:35:49]

remove commented-out line

[manasijm, 2016/05/19 17:50:16]

Done.

+      } else { // new
+        Seen[&Instr] = Instr.getDest();
+
+        for (unsigned int i = 0; i < Instr.getSrcSize(); ++i) {

[Jim Stichnoth, 2016/05/19 01:35:49]

SizeT

[manasijm, 2016/05/19 17:50:16]

Done.

+          Operand *Opr = Instr.getSrc(i);
+          if (Variable *Var = llvm::dyn_cast<Variable>(Opr)) {

[Jim Stichnoth, 2016/05/19 01:35:49]

auto *Var

[manasijm, 2016/05/19 17:50:16]

Done.

+            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