Float Constant CSE

src/IceCfg.cpp

Index: src/IceCfg.cpp
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index b6ab31e7c3bf09e726e84f862fd93a0fc458cd30..140bfecc391bd3204501d58a55a1ce819383834e 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -798,6 +798,89 @@ void Cfg::shortCircuitJumps() {
   Nodes = NewList;
 }
 
+void Cfg::floatConstantCSE() {
+  // Load multiple uses of a floating point constant (between two call

[Jim Stichnoth, 2016/08/03 04:43:02]

Here is the big comment.

It seems to me that the cleanest, simplest approach would be to replace all uses
of a given pooled constant with a new Variable, assign the constant to the
Variable at the appropriate point (such as before its first use), link the
Variable to the constant, and then let local variable splitting do its work.

This would mean modifying Variable::LinkedTo to be an Operand instead of
Variable, and plumbing that through.  For example, getLinkedToStackRoot() is
renamed to getLinkedToMemRoot and has to check for a little bit more than just
whether something is a Variable with actual uses and without a register
assignment.

[manasijm, 2016/08/03 16:32:25]

Acknowledged.

+  // instructions or block start/end) into a variable before its first use.
+  //   t1 = b + 1.0
+  //   t2 = c + 1.0
+  // Gets transformed to:
+  //   t0 = 1.0
+  //   t0_1 = t0
+  //   t1 = b + t0_1
+  //   t2 = c + t0_1
+  // Call instructions reset the procedure, but uses the same variable, just

[Jim Stichnoth, 2016/08/03 04:43:02]

s/uses/use/

Then reflow to 80-col (i.e. "in" should fit at the end of this line).

[manasijm, 2016/08/03 16:32:25]

Done.

+  // in case it got a register. We are assuming floating point registers are
+  // not calee saved in general. Example, continuing from before:

[Jim Stichnoth, 2016/08/03 04:43:02]

callee

[manasijm, 2016/08/03 16:32:25]

Done.

+  //   result = call <some function>
+  //   t3 = d + 1.0
+  // Gets transformed to:
+  //   result = call <some function>
+  //   t0_2 = t0
+  //   t3 = d + 0_2

[Jim Stichnoth, 2016/08/03 04:43:02]

t0_2

[manasijm, 2016/08/03 16:32:26]

Done.

+  // TODO(manasijm, stichnot): Figure out how to 'link' t0 to the stack slot of

[Jim Stichnoth, 2016/08/03 04:43:01]

Pooled constants like 1.0 don't get a stack slot.  They get a global memory
location.  (That doesn't change the fact that t0's LinkedTo field would need to
be an arbitrary Operand that could end up being a Variable or some kind of
MemOperand.)

[manasijm, 2016/08/03 16:32:26]

Acknowledged.

+  // 1.0. When t0 does not get a register, introducing an extra assignment
+  // statement does not make sense. The relevant portion is marked below.
+
+  TimerMarker T(TimerStack::TT_floatConstantCse, this);

[Jim Stichnoth, 2016/08/03 04:43:02]

TimerMarker _(...);

[manasijm, 2016/08/03 16:32:26]

Done.

+  for (CfgNode *Node : getNodes()) {
+
+    CfgUnorderedMap<Constant *, Variable *> ConstCache;
+    llvm::ilist_iterator<Inst> Current = Node->getInsts().begin();
+    auto End = Node->getInsts().end();
+    while (Current != End) {
+      CfgUnorderedMap<Constant *, CfgVector<Inst *>> FloatUses;
+      if (llvm::isa<InstCall>(*Current)) {
+        Current++;
+        assert(Current);
+      }
+      while (Current != End && !llvm::isa<InstCall>(*Current)) {
+        for (SizeT i = 0; i < Current->getSrcSize(); ++i) {
+          if (auto *Const = llvm::dyn_cast<Constant>(Current->getSrc(i))) {
+            if (Const->getType() == IceType_f32 ||
+                Const->getType() == IceType_f64) {
+              FloatUses[Const].push_back(Current);
+            }
+          }
+        }
+        Current++;
+      }
+      for (auto &Pair : FloatUses) {
+        static constexpr SizeT MinUseThreshold = 3;
+        if (Pair.second.size() < MinUseThreshold)
+          continue;
+        // Only consider constants with at least `MinUseThreshold` uses
+        auto &Insts = Node->getInsts();
+
+        if (ConstCache.find(Pair.first) == ConstCache.end()) {
+          // Saw a constant (which is used at least twice) for the first time
+          auto NewVar = makeVariable(Pair.first->getType());

[Jim Stichnoth, 2016/08/03 04:43:02]

auto *

[manasijm, 2016/08/03 16:32:26]

Done.

+          //NewVar->setLinkedTo(Pair.first);
+          // TODO: This is not possible yet.

[Jim Stichnoth, 2016/08/03 04:43:02]

TODO needs owner.

[manasijm, 2016/08/03 16:32:26]

Done.

+          auto Assign = InstAssign::create(Node->getCfg(), NewVar, Pair.first);

[Jim Stichnoth, 2016/08/03 04:43:02]

auto *

[manasijm, 2016/08/03 16:32:26]

Done.

+          Insts.insert(Pair.second[0], Assign);
+          ConstCache[Pair.first] = NewVar;
+        }
+
+        auto NewVar = makeVariable(Pair.first->getType());

[Jim Stichnoth, 2016/08/03 04:43:02]

auto *

[manasijm, 2016/08/03 16:32:26]

Done.

+        NewVar->setLinkedTo(ConstCache[Pair.first]);
+        auto Assign =

[Jim Stichnoth, 2016/08/03 04:43:02]

auto *

[manasijm, 2016/08/03 16:32:26]

Done.

+            InstAssign::create(Node->getCfg(), NewVar, ConstCache[Pair.first]);
+
+        Insts.insert(Pair.second[0], Assign);
+        for (auto *InstUse : Pair.second) {
+          for (SizeT i = 0; i < InstUse->getSrcSize(); ++i) {
+            if (auto *Const = llvm::dyn_cast<Constant>(InstUse->getSrc(i))) {
+              if (Const == Pair.first) {
+                InstUse->replaceSource(i, NewVar);
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();