[CGP] Fix the crash for combining address mode when having cyclic dependency

[wwei]

Summary

In the combination of addressing modes, when replacing the matched phi nodes, sometimes the phi node to be replaced has been modified.
For example, there’s Matcher set [A, B] and [C, A], which will have cyclic dependency: A is replaced by B and C will be replaced by A . So we need to update the second phi node in matcher set when the phi node is already replaced.

[skatkov]

It seems that correct fix should be something different.
The underlying idea of implementation is as follows:
We built phi nodes to get, for example, base address in a point of usage. (in you example it is an offset).
Now we try to find whether there are already existing phi nodes which provide us with the base.
So we try to match all new phi nodes to already existed.
The bug you found actually happened due to we tried to match new phi node to another new phi node and at the end it results in the bug.

So I guess the better fix would be to just ignore new phi nodes when we try to map new phi node to old one.

llvm/lib/CodeGen/CodeGenPrepare.cpp

3731

I guess the change of this comparison to if (PhiNodesToMatch.count(&P)) should fix your problem.

[wwei]

In D108635#2964494, @skatkov wrote:

It seems that correct fix should be something different.
The underlying idea of implementation is as follows:
We built phi nodes to get, for example, base address in a point of usage. (in you example it is an offset).
Now we try to find whether there are already existing phi nodes which provide us with the base.
So we try to match all new phi nodes to already existed.
The bug you found actually happened due to we tried to match new phi node to another new phi node and at the end it results in the bug.

So I guess the better fix would be to just ignore new phi nodes when we try to map new phi node to old one.

@skatkov Thank you for the explanation，I have updated the patch.

[skatkov]

llvm/lib/CodeGen/CodeGenPrepare.cpp

3731

Please add a comment, like:
Skip new phi nodes.

llvm/lib/CodeGen/CodeGenPrepare.cpp

private:
   /// Try to match PHI node to Candidate.
   /// Matcher tracks the matched Phi nodes.
   bool MatchPhiNode(PHINode *PHI, PHINode *Candidate,
                     SmallSetVector<PHIPair, 8> &Matcher,
                     PhiNodeSet &PhiNodesToMatch) {
     SmallVector<PHIPair, 8> WorkList;
     Matcher.insert({ PHI, Candidate });
     SmallSet<PHINode *, 8> MatchedPHIs;
+    // This map is used to record the Phi node and the replaced value.
+    DenseMap<PHINode *, PHINode *> HasMatched;
     MatchedPHIs.insert(PHI);
+    HasMatched[PHI] = Candidate;
     WorkList.push_back({ PHI, Candidate });
     SmallSet<PHIPair, 8> Visited;
     while (!WorkList.empty()) {
       auto Item = WorkList.pop_back_val();
       if (!Visited.insert(Item).second)
         continue;
       // We iterate over all incoming values to Phi to compare them.
       // If values are different and both of them Phi and the first one is a
while (!WorkList.empty()) {
           return false;
 
         // If we already matched them then continue.
         if (Matcher.count({ FirstPhi, SecondPhi }))
           continue;
         // So the values are different and does not match. So we need them to
         // match. (But we register no more than one match per PHI node, so that
         // we won't later try to replace them twice.)
-        if (MatchedPHIs.insert(FirstPhi).second)
+        if (MatchedPHIs.insert(FirstPhi).second) {
+          // If the value to be replaced has been modified, then use the
+          // modified value.
+          if (HasMatched.find(SecondPhi) != HasMatched.end())
+            SecondPhi = HasMatched[SecondPhi];
           Matcher.insert({ FirstPhi, SecondPhi });
+          // Record the Phi node and the replaced value.
+          HasMatched[FirstPhi] = SecondPhi;
+        }
         // But me must check it.
         WorkList.push_back({ FirstPhi, SecondPhi });
       }
     }
     return true;
   }
 
   /// For the given set of PHI nodes (in the SimplificationTracker) try
while (PhiNodesToMatch.size()) {
 
       // Add us, if no Phi nodes in the basic block we do not match.
       WillNotMatch.clear();
       WillNotMatch.insert(PHI);
 
       // Traverse all Phis until we found equivalent or fail to do that.
       bool IsMatched = false;
       for (auto &P : PHI->getParent()->phis()) {
         if (&P == PHI)
           continue;
         if ((IsMatched = MatchPhiNode(PHI, &P, Matched, PhiNodesToMatch)))
           break;
         // If it does not match, collect all Phi nodes from matcher.
         // if we end up with no match, them all these Phi nodes will not match
         // later.
         for (auto M : Matched)
           WillNotMatch.insert(M.first);

llvm/test/Transforms/CodeGenPrepare/AArch64/combine-address-mode.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -codegenprepare -mtriple=aarch64-none-linux-gnu < %s | FileCheck %s
+
+@_MergedGlobals = external dso_local global <{ i32, i32 }>, align 4
+
+define dso_local i32 @f(i1 %a, i8 %b) local_unnamed_addr {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:    br label [[TMP6:%.*]]
+; CHECK:       1:
+; CHECK-NEXT:    br i1 [[A:%.*]], label [[TMP2:%.*]], label [[TMP6]]
+; CHECK:       2:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), [[TMP1:%.*]] ], [ [[TMP16:%.*]], [[TMP14:%.*]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), [[TMP1]] ], [ [[TMP15:%.*]], [[TMP14]] ]
+; CHECK-NEXT:    ret i32 0
+; CHECK:       5:
+; CHECK-NEXT:    br label [[TMP6]]
+; CHECK:       6:
+; CHECK-NEXT:    [[TMP7:%.*]] = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 0), [[TMP0:%.*]] ], [ [[TMP3]], [[TMP5:%.*]] ], [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), [[TMP1]] ]
+; CHECK-NEXT:    [[TMP8:%.*]] = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 0), [[TMP0]] ], [ [[TMP4]], [[TMP5]] ], [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), [[TMP1]] ]
+; CHECK-NEXT:    br label [[TMP9:%.*]]
+; CHECK:       9:
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i32* [ [[TMP16]], [[TMP14]] ], [ [[TMP7]], [[TMP6]] ]
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i32* [ [[TMP16]], [[TMP14]] ], [ [[TMP8]], [[TMP6]] ]
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i32* [ [[TMP15]], [[TMP14]] ], [ [[TMP8]], [[TMP6]] ]
+; CHECK-NEXT:    br i1 [[A]], label [[TMP14]], label [[TMP13:%.*]]
+; CHECK:       13:
+; CHECK-NEXT:    store i32 5, i32* [[TMP11]], align 4
+; CHECK-NEXT:    br label [[TMP14]]
+; CHECK:       14:
+; CHECK-NEXT:    [[TMP15]] = phi i32* [ [[TMP12]], [[TMP13]] ], [ [[TMP10]], [[TMP9]] ]
+; CHECK-NEXT:    [[TMP16]] = phi i32* [ [[TMP11]], [[TMP13]] ], [ [[TMP10]], [[TMP9]] ]
+; CHECK-NEXT:    br i1 [[A]], label [[TMP2]], label [[TMP9]]
+;
+  br label %11
+
+1:                                                ; No predecessors!
+  br i1 %a, label %2, label %10
+
+2:                                                ; preds = %22, %1
+  %3 = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), %1 ], [ %21, %22 ]
+  %4 = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), %1 ], [ %20, %22 ]
+  ret i32 0
+
+5:                                                ; No predecessors!
+  %6 = icmp ugt i8 %b, 50
+  br label %7
+
+7:                                                ; preds = %10, %5
+  %8 = phi i32* [ %3, %5 ], [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), %10 ]
+  %9 = phi i32* [ %4, %5 ], [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 1), %10 ]
+  br label %11
+
+10:                                               ; preds = %1
+  br label %7
+
+11:                                               ; preds = %7, %0
+  %12 = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 0), %0 ], [ %8, %7 ]
+  %13 = phi i32* [ getelementptr inbounds (<{ i32, i32 }>, <{ i32, i32 }>* @_MergedGlobals, i32 0, i32 0), %0 ], [ %9, %7 ]
+  br label %14
+
+14:                                               ; preds = %19, %11
+  %15 = phi i32* [ %21, %19 ], [ %12, %11 ]
+  %16 = phi i32* [ %21, %19 ], [ %13, %11 ]
+  %17 = phi i32* [ %20, %19 ], [ %13, %11 ]
+  br i1 %a, label %19, label %18
+
+18:                                               ; preds = %14
+  store i32 5, i32* %16, align 4
+  br label %19
+
+19:                                               ; preds = %18, %14
+  %20 = phi i32* [ %17, %18 ], [ %15, %14 ]
+  %21 = phi i32* [ %16, %18 ], [ %15, %14 ]
+  br i1 %a, label %22, label %14
+
+22:                                               ; preds = %19
+  br label %2
+}