From 7f8d7ac89bd916f2fcbec2e14b40f653139ce5b6 Mon Sep 17 00:00:00 2001
From: Alon Zakai <azakai@google.com>
Date: Wed, 24 Nov 2021 14:27:14 -0800
Subject: CoalesceLocals: Use ValueNumbering (#4355)

This removes the old hardcoded value numbering in that pass and makes
it use the new code that was split into helper code. The immediate benefit
of this is to make the code aware of identical constants: if two locals have
the same constant then they do not interfere. Future improvements to
numbering will also automatically help here.

This changes some constants in existing tests so that they keep testing
what they were testing before, and adds new tests for the new benefit here.

This implements a proposed TODO from #4314
---
 src/passes/CoalesceLocals.cpp | 34 ++++++++++++++++++++--------------
 1 file changed, 20 insertions(+), 14 deletions(-)

(limited to 'src')

diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp
index f9ded9c92..42296b5bf 100644
--- a/src/passes/CoalesceLocals.cpp
+++ b/src/passes/CoalesceLocals.cpp
@@ -30,6 +30,7 @@
 #include <unordered_set>
 
 #include "cfg/liveness-traversal.h"
+#include "ir/numbering.h"
 #include "ir/utils.h"
 #include "pass.h"
 #include "support/learning.h"
@@ -155,6 +156,10 @@ void CoalesceLocals::calculateInterferences() {
   // loop.
   std::vector<Index> values(numLocals);
 
+  ValueNumbering valueNumbering;
+
+  auto* func = getFunction();
+
   for (auto& curr : basicBlocks) {
     if (liveBlocks.count(curr.get()) == 0) {
       continue; // ignore dead blocks
@@ -196,21 +201,22 @@ void CoalesceLocals::calculateInterferences() {
     // around through copies between sets we can see when sets are guaranteed to
     // be equal.
 
-    // Give all default values the same value ID, regardless of their type. This
-    // is valid since we only coalesce locals of the same type anyhow.
-    auto zeroInit = 0;
-    Index nextValue = 1;
-
     if (curr.get() == entry) {
       // Each parameter is assumed to have a different value on entry.
-      for (Index i = 0; i < getFunction()->getNumParams(); i++) {
-        values[i] = nextValue++;
+      for (Index i = 0; i < func->getNumParams(); i++) {
+        values[i] = valueNumbering.getUniqueValue();
       }
 
-      for (Index i = getFunction()->getNumParams();
-           i < getFunction()->getNumLocals();
-           i++) {
-        values[i] = zeroInit;
+      for (Index i = func->getNumParams(); i < func->getNumLocals(); i++) {
+        auto type = func->getLocalType(i);
+        if (type.isNonNullable()) {
+          // A non-nullable value cannot be used anyhow, but we must give it
+          // some value. A unique one seems least likely to result in surprise
+          // during debugging.
+          values[i] = valueNumbering.getUniqueValue();
+        } else {
+          values[i] = valueNumbering.getValue(Literal::makeZeros(type));
+        }
       }
     } else {
       // In any block but the entry, assume that each live local might have a
@@ -218,7 +224,7 @@ void CoalesceLocals::calculateInterferences() {
       // TODO: Propagating value IDs across blocks could identify more copies,
       //       however, it would also be nonlinear.
       for (auto index : curr->contents.start) {
-        values[index] = nextValue++;
+        values[index] = valueNumbering.getUniqueValue();
       }
     }
 
@@ -246,8 +252,8 @@ void CoalesceLocals::calculateInterferences() {
         assert(i > 0 && set->value == *actions[i - 1].origin);
         newValue = values[actions[i - 1].index];
       } else {
-        // This is not a copy; assign a new unique value.
-        newValue = nextValue++;
+        // This is not a copy.
+        newValue = valueNumbering.getValue(set->value);
       }
       values[index] = newValue;
 
-- 
cgit v1.2.3