[IRSim] Removing check that caused early matching of commutative instructions

[AndrewLitteken]

Summary

When the first commutative instruction in a region using the same value in both positions was compared to a corresponding instruction with two different values, there was an early check that determined that since the values were new, it was true that these values acted in the same way structurally. If this was not contradicted later in the program, the regions were marked as similar. This removes that check, so that it is clear that the same value cannot be mapped to two different values.

[paquette]

I think this is fine. I have a couple nits on the comments, but I won't hold up review over them.

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

2622

I think this comment would be clearer if you said "ensure that <instruction in test> is not mapped the same as <other instruction in test>"; it's not clear to me what's going on here right now.

2629

This is minor, but it would be really useful to have names for the variables here which describe what they're doing if possible.

E.g.

%commutative_inst = mul i64 undef, undef
...

[uabelho]

Hi,

This seems to solve the crash I reported in
https://github.com/llvm/llvm-project/issues/55131

Do you think it actually fixed the problem so that issue should be closed or is it just hidden?

[AndrewLitteken]

Yes, this was written to fix that crash. Should have noted it in the commit message.

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

static bool checkNumberingAndReplaceCommutative(
 
   // Iterate over the operands in the source IRSimilarityCandidate to determine
   // whether there exists an operand in the other IRSimilarityCandidate that
   // creates a valid mapping of Value to Value between the
   // IRSimilarityCaniddates.
   for (Value *V : SourceOperands) {
     ArgVal = SourceValueToNumberMapping.find(V)->second;
 
+    // Instead of finding a current mapping, we attempt to insert a set.
     std::tie(ValueMappingIt, WasInserted) = CurrentSrcTgtNumberMapping.insert(
         std::make_pair(ArgVal, TargetValueNumbers));
 
-    // Instead of finding a current mapping, we inserted a set.  This means a
-    // mapping did not exist for the source Instruction operand, it has no
-    // current constraints we need to check.
-    if (WasInserted)
-      continue;
-
-    // If a mapping already exists for the source operand to the values in the
-    // other IRSimilarityCandidate we need to iterate over the items in other
-    // IRSimilarityCandidate's Instruction to determine whether there is a valid
-    // mapping of Value to Value.
+    // We need to iterate over the items in other IRSimilarityCandidate's
+    // Instruction to determine whether there is a valid mapping of
+    // Value to Value.
     DenseSet<unsigned> NewSet;
     for (unsigned &Curr : ValueMappingIt->second)
       // If we can find the value in the mapping, we add it to the new set.
       if (TargetValueNumbers.contains(Curr))
         NewSet.insert(Curr);
 
     // If we could not find a Value, return 0.
     if (NewSet.empty())
       return false;
     
     // Otherwise replace the old mapping with the newly constructed one.
     if (NewSet.size() != ValueMappingIt->second.size())
       ValueMappingIt->second.swap(NewSet);
 
     // We have reached no conclusions about the mapping, and cannot remove
     // any items from the other operands, so we move to check the next operand.
     if (ValueMappingIt->second.size() != 1)
       continue;
 
-
     unsigned ValToRemove = *ValueMappingIt->second.begin();
     // When there is only one item left in the mapping for and operand, remove
     // the value from the other operands.  If it results in there being no
     // mapping, return false, it means the mapping is wrong
     for (Value *InnerV : SourceOperands) {
       if (V == InnerV)
         continue;
 

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
     unsigned InstIdx = 0;
     for (IRSimilarityCandidate &Cand : Cands) {
       ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
       InstIdx += 3;
     }
   }
 }
 
+// This test ensures that when the first instruction in a sequence is
+// a commutative instruction with the same value (mcomm_inst_same_val), but the
+// corresponding instruction (comm_inst_diff_val) is not, we mark the regions
+// and not similar.
+TEST(IRSimilarityIdentifier, CommutativeSameValueFirstMisMatch) {
+  StringRef ModuleString = R"(
+                          define void @v_1_0(i64 %v_33) {
+                            entry:
+                              %comm_inst_same_val = mul i64 undef, undef
+                              %add = add i64 %comm_inst_same_val, %v_33
+                              %comm_inst_diff_val = mul i64 0, undef
+                              %mul.i = add i64 %comm_inst_diff_val, %comm_inst_diff_val
+                              unreachable
+                            })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
+  getSimilarities(*M, SimilarityCandidates);
+
+  ASSERT_TRUE(SimilarityCandidates.size() == 0);
+}
+
 // This test makes sure that intrinsic functions that are marked commutative
 // are still treated as non-commutative since they are function calls.
 TEST(IRSimilarityIdentifier, IntrinsicCommutative) {
   // If treated as commutative, we will fail to find a valid mapping, causing
   // an assertion error.
   StringRef ModuleString = R"(
   define void @foo() {
     entry: