Implement join for definite bits number value

Bug: b/196017578
Change-Id: I409deb46c3043d86cd29cc4bc49334900b8aaf9b
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java
index fccb291..f657c65 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValue.java
@@ -74,6 +74,10 @@
     return null;
   }
 
+  public boolean hasDefinitelySetAndUnsetBitsInformation() {
+    return false;
+  }
+
   public boolean hasKnownArrayLength() {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueFactory.java b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueFactory.java
index bab5e75..bc50262 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueFactory.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueFactory.java
@@ -23,6 +23,14 @@
   private ConcurrentHashMap<Integer, KnownLengthArrayState> knownArrayLengthStates =
       new ConcurrentHashMap<>();
 
+  public AbstractValue createDefiniteBitsNumberValue(
+      int definitelySetBits, int definitelyUnsetBits) {
+    if (definitelySetBits != 0 && definitelyUnsetBits != 0) {
+      return new DefiniteBitsNumberValue(definitelySetBits, definitelyUnsetBits);
+    }
+    return AbstractValue.unknown();
+  }
+
   public SingleConstClassValue createSingleConstClassValue(DexType type) {
     return singleConstClassValues.computeIfAbsent(type, SingleConstClassValue::new);
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueJoiner.java b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueJoiner.java
index 836ccd5..0c49fca 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueJoiner.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/value/AbstractValueJoiner.java
@@ -20,6 +20,10 @@
     this.appView = appView;
   }
 
+  private AbstractValueFactory factory() {
+    return appView.abstractValueFactory();
+  }
+
   final AbstractValue internalJoin(
       AbstractValue abstractValue,
       AbstractValue otherAbstractValue,
@@ -35,22 +39,17 @@
     }
     return type.isReferenceType()
         ? joinReference(abstractValue, otherAbstractValue)
-        : joinPrimitive(abstractValue, otherAbstractValue, config);
+        : joinPrimitive(abstractValue, otherAbstractValue, config, type);
   }
 
   private AbstractValue joinPrimitive(
       AbstractValue abstractValue,
       AbstractValue otherAbstractValue,
-      AbstractValueJoinerConfig config) {
+      AbstractValueJoinerConfig config,
+      DexType type) {
     assert !abstractValue.isNullOrAbstractValue();
     assert !otherAbstractValue.isNullOrAbstractValue();
 
-    if (config.canUseDefiniteBitsAbstraction()
-        && abstractValue.isConstantOrNonConstantNumberValue()
-        && otherAbstractValue.isConstantOrNonConstantNumberValue()) {
-      // TODO(b/196017578): Implement join.
-    }
-
     if (config.canUseNumberIntervalAndNumberSetAbstraction()
         && abstractValue.isConstantOrNonConstantNumberValue()
         && otherAbstractValue.isConstantOrNonConstantNumberValue()) {
@@ -67,12 +66,56 @@
         assert otherAbstractValue.isNumberFromSetValue();
         numberFromSetValueBuilder.addInts(otherAbstractValue.asNumberFromSetValue());
       }
-      return numberFromSetValueBuilder.build(appView.abstractValueFactory());
+      return numberFromSetValueBuilder.build(factory());
+    }
+
+    if (config.canUseDefiniteBitsAbstraction()) {
+      return joinPrimitiveToDefiniteBitsNumberValue(abstractValue, otherAbstractValue, type);
     }
 
     return unknown();
   }
 
+  private AbstractValue joinPrimitiveToDefiniteBitsNumberValue(
+      AbstractValue abstractValue, AbstractValue otherAbstractValue, DexType type) {
+    assert type.isIntType();
+    if (!abstractValue.hasDefinitelySetAndUnsetBitsInformation()
+        || !otherAbstractValue.hasDefinitelySetAndUnsetBitsInformation()) {
+      return unknown();
+    }
+    // Normalize order.
+    if (!abstractValue.isSingleNumberValue() && otherAbstractValue.isSingleNumberValue()) {
+      AbstractValue tmp = abstractValue;
+      abstractValue = otherAbstractValue;
+      otherAbstractValue = tmp;
+    }
+    if (abstractValue.isSingleNumberValue()) {
+      SingleNumberValue singleNumberValue = abstractValue.asSingleNumberValue();
+      if (otherAbstractValue.isSingleNumberValue()) {
+        SingleNumberValue otherSingleNumberValue = otherAbstractValue.asSingleNumberValue();
+        return factory()
+            .createDefiniteBitsNumberValue(
+                singleNumberValue.getDefinitelySetIntBits()
+                    & otherSingleNumberValue.getDefinitelySetIntBits(),
+                singleNumberValue.getDefinitelyUnsetIntBits()
+                    & otherSingleNumberValue.getDefinitelyUnsetIntBits());
+      } else {
+        assert otherAbstractValue.isDefiniteBitsNumberValue();
+        DefiniteBitsNumberValue otherDefiniteBitsNumberValue =
+            otherAbstractValue.asDefiniteBitsNumberValue();
+        return otherDefiniteBitsNumberValue.join(factory(), singleNumberValue);
+      }
+    } else {
+      // Both are guaranteed to be non-const due to normalization.
+      assert abstractValue.isDefiniteBitsNumberValue();
+      assert otherAbstractValue.isDefiniteBitsNumberValue();
+      DefiniteBitsNumberValue definiteBitsNumberValue = abstractValue.asDefiniteBitsNumberValue();
+      DefiniteBitsNumberValue otherDefiniteBitsNumberValue =
+          otherAbstractValue.asDefiniteBitsNumberValue();
+      return definiteBitsNumberValue.join(factory(), otherDefiniteBitsNumberValue);
+    }
+  }
+
   private AbstractValue joinReference(
       AbstractValue abstractValue, AbstractValue otherAbstractValue) {
     if (abstractValue.isNull()) {
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/value/DefiniteBitsNumberValue.java b/src/main/java/com/android/tools/r8/ir/analysis/value/DefiniteBitsNumberValue.java
index b713cef..b081050 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/value/DefiniteBitsNumberValue.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/value/DefiniteBitsNumberValue.java
@@ -32,6 +32,11 @@
   }
 
   @Override
+  public boolean hasDefinitelySetAndUnsetBitsInformation() {
+    return true;
+  }
+
+  @Override
   public boolean isDefiniteBitsNumberValue() {
     return true;
   }
@@ -51,6 +56,34 @@
     return OptionalBool.unknown();
   }
 
+  public AbstractValue join(
+      AbstractValueFactory abstractValueFactory, DefiniteBitsNumberValue definiteBitsNumberValue) {
+    return join(
+        abstractValueFactory,
+        definiteBitsNumberValue.definitelySetBits,
+        definiteBitsNumberValue.definitelyUnsetBits);
+  }
+
+  public AbstractValue join(
+      AbstractValueFactory abstractValueFactory, SingleNumberValue singleNumberValue) {
+    return join(
+        abstractValueFactory,
+        singleNumberValue.getDefinitelySetIntBits(),
+        singleNumberValue.getDefinitelyUnsetIntBits());
+  }
+
+  public AbstractValue join(
+      AbstractValueFactory abstractValueFactory,
+      int otherDefinitelySetBits,
+      int otherDefinitelyUnsetBits) {
+    if (definitelySetBits == otherDefinitelySetBits
+        && definitelyUnsetBits == otherDefinitelyUnsetBits) {
+      return this;
+    }
+    return abstractValueFactory.createDefiniteBitsNumberValue(
+        definitelySetBits & otherDefinitelySetBits, definitelyUnsetBits & otherDefinitelyUnsetBits);
+  }
+
   @Override
   public boolean mayOverlapWith(ConstantOrNonConstantNumberValue other) {
     return true;
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/value/SingleNumberValue.java b/src/main/java/com/android/tools/r8/ir/analysis/value/SingleNumberValue.java
index 5327427..e29e468 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/value/SingleNumberValue.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/value/SingleNumberValue.java
@@ -37,6 +37,11 @@
   }
 
   @Override
+  public boolean hasDefinitelySetAndUnsetBitsInformation() {
+    return true;
+  }
+
+  @Override
   public OptionalBool isSubsetOf(int[] values) {
     return OptionalBool.of(ArrayUtils.containsInt(values, getIntValue()));
   }
@@ -81,6 +86,14 @@
     return value != 0;
   }
 
+  public int getDefinitelySetIntBits() {
+    return getIntValue();
+  }
+
+  public int getDefinitelyUnsetIntBits() {
+    return ~getDefinitelySetIntBits();
+  }
+
   public double getDoubleValue() {
     return Double.longBitsToDouble(value);
   }