[SROA] Handle PHI with multiple duplicate predecessors

[bjope]

Summary

The verifier accepts PHI nodes with multiple entries for the
same basic block, as long as the value is the same.

As seen in PR37203, SROA did not handle such PHI nodes properly
when speculating loads over the PHI, since it inserted multiple
loads in the predecessor block and changed the PHI into having
multiple entries for the same basic block, but with different
values.

This patch teaches SROA to reuse the same speculated load for
each PHI duplicate entry in such situations.

Resolves: https://bugs.llvm.org/show_bug.cgi?id=37203

[uabelho]

At least the fix solves the problem I saw but I don't know SROA enough to say if the fix is good or not.

[bjope]

ping!

[bjope]

So the patch has been confirmed to solve the PR (thanks @uabelho).
But still no ready-to-land. Well I think that I'll land this anyway tomorrow, to get rid of the bug.

[efriedma]

But still no ready-to-land. Well I think that I'll land this anyway tomorrow, to get rid of the bug.

This is not how the review process works; we expect pre-commit review for non-trivial patches.

lib/Transforms/Scalar/SROA.cpp

1263 ↗

(On Diff #145178)

We generally use DenseMap in LLVM code, not unordered_map (see http://llvm.org/docs/ProgrammersManual.html#map-like-containers-std-map-densemap-etc ).

I don't think it's a good idea to make the rest of the code more complicated for the sake of the "PHI node has multiple entries" assertion.

1273 ↗

(On Diff #145178)

DenseMap has a method "lookup" you can use to avoid the iterator.

[• dberlin]

1. If this is common enough, should we just have a unique_predecessors iterator?

(unfortunately, std::unique won't work here because preds are not sorted)

2. I don't think it's worth issuing an assert here if the verifier already verifies it.

If we don't add a unique_processor, can you just use SmallPtrSet<BasicBlock *> HandledPreds, and insert/check whether the pred has been handled?

[• dberlin]

Oh looks like Eli beat me by a few minutes :)

[efriedma]

Not sure unique_predecessors would help here; we have to call PHINode::addIncoming once for each predecessor, whether or not it's unique.

[• dberlin]

Ugh, yes, i was focused on the error issuing part and not the hey you have to create real phi nodes part.

[bjope]

lib/Transforms/Scalar/SROA.cpp

1273 ↗

(On Diff #145178)

So if I have a

DenseMap<BasicBlock*, Value*> Map;

can I do

Value* V = Map.lookup(Pred);

and expect to get a null pointer in case Pred isn't found?

[bjope]

Replaced the unordered_map by a DenseMap.

[bjope]

Thanks Eli. Definitely a cleaner solution when using a DenseMap.

[efriedma]

LGTM

lib/Transforms/Scalar/SROA.cpp

1273 ↗

(On Diff #145178)

Yes, lookup() returns null if the key isn't in the map.

llvm/trunk/lib/Transforms/Scalar/SROA.cpp

static void speculatePHINodeLoads(PHINode &PN) {
   // Rewrite all loads of the PN to use the new PHI.
   while (!PN.use_empty()) {
     LoadInst *LI = cast<LoadInst>(PN.user_back());
     LI->replaceAllUsesWith(NewPN);
     LI->eraseFromParent();
   }
 
   // Inject loads into all of the pred blocks.
+  DenseMap<BasicBlock*, Value*> InjectedLoads;
   for (unsigned Idx = 0, Num = PN.getNumIncomingValues(); Idx != Num; ++Idx) {
     BasicBlock *Pred = PN.getIncomingBlock(Idx);
-    TerminatorInst *TI = Pred->getTerminator();
     Value *InVal = PN.getIncomingValue(Idx);
+
+    // A PHI node is allowed to have multiple (duplicated) entries for the same
+    // basic block, as long as the value is the same. So if we already injected
+    // a load in the predecessor, then we should reuse the same load for all
+    // duplicated entries.
+    if (Value* V = InjectedLoads.lookup(Pred)) {
+      NewPN->addIncoming(V, Pred);
+      continue;
+    }
+
+    TerminatorInst *TI = Pred->getTerminator();
     IRBuilderTy PredBuilder(TI);
 
     LoadInst *Load = PredBuilder.CreateLoad(
         InVal, (PN.getName() + ".sroa.speculate.load." + Pred->getName()));
     ++NumLoadsSpeculated;
     Load->setAlignment(Align);
     if (AATags)
       Load->setAAMetadata(AATags);
     NewPN->addIncoming(Load, Pred);
+    InjectedLoads[Pred] = Load;
   }
 
   LLVM_DEBUG(dbgs() << "          speculated to: " << *NewPN << "\n");
   PN.eraseFromParent();
 }
 
 /// Select instructions that use an alloca and are subsequently loaded can be
 /// rewritten to load both input pointers and then select between the result,

llvm/trunk/test/Transforms/SROA/phi-with-duplicate-pred.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -sroa -S | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-n8:16:32:64"
+
+@a = external global i16, align 1
+
+define void @f2() {
+; CHECK-LABEL: @f2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 undef, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[G_0_SROA_SPECULATE_LOAD_CLEANUP:%.*]] = load i16, i16* @a, align 1
+; CHECK-NEXT:    switch i32 2, label [[CLEANUP7:%.*]] [
+; CHECK-NEXT:    i32 0, label [[LBL1:%.*]]
+; CHECK-NEXT:    i32 2, label [[LBL1]]
+; CHECK-NEXT:    ]
+; CHECK:       if.else:
+; CHECK-NEXT:    br label [[LBL1]]
+; CHECK:       lbl1:
+; CHECK-NEXT:    [[G_0_SROA_SPECULATED:%.*]] = phi i16 [ [[G_0_SROA_SPECULATE_LOAD_CLEANUP]], [[CLEANUP]] ], [ [[G_0_SROA_SPECULATE_LOAD_CLEANUP]], [[CLEANUP]] ], [ undef, [[IF_ELSE]] ]
+; CHECK-NEXT:    unreachable
+; CHECK:       cleanup7:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %e = alloca i16, align 1
+  br i1 undef, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  br label %cleanup
+
+cleanup:                                          ; preds = %if.then
+  switch i32 2, label %cleanup7 [
+  i32 0, label %lbl1
+  i32 2, label %lbl1
+  ]
+
+if.else:                                          ; preds = %entry
+  br label %lbl1
+
+lbl1:                                             ; preds = %if.else, %cleanup, %cleanup
+  %g.0 = phi i16* [ @a, %cleanup ], [ @a, %cleanup ], [ %e, %if.else ]
+  %0 = load i16, i16* %g.0, align 1
+  unreachable
+
+cleanup7:                                         ; preds = %cleanup
+  ret void
+}
+