[NOT FOR REVIEW][InstCombine] Graph-aware PHI-of-extractvalues -> extractvalue-of-PHIs

[lebedev.ri]

Summary

See https://reviews.llvm.org/D86530#2247674

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

 //===- InstCombinePHI.cpp -------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitPHINode function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
auto *NewIVI = InsertValueInst::Create(NewOperands[0], NewOperands[1],
                                          FirstIVI->getIndices(), PN.getName());
 
   PHIArgMergedDebugLoc(NewIVI, PN);
   ++NumPHIsOfInsertValues;
   return NewIVI;
 }
 
 /// If we have something like phi [extractvalue(a,0), extractvalue(b,0)],
-/// turn this into a phi[a,b] and a single extractvalue.
+/// or phi [phi [extractvalue(a,0), extractvalue(b,0)], extractvalue(c,0)]
+/// turn this into a phi[a,b] / phi[phi[a,b],c] and a single extractvalue.
 Instruction *
-InstCombinerImpl::foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN) {
-  auto *FirstEVI = cast<ExtractValueInst>(PN.getIncomingValue(0));
-
-  // Scan to see if all operands are `extractvalue`'s with the same indicies,
-  // and all have a single use.
-  for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
-    auto *I = dyn_cast<ExtractValueInst>(PN.getIncomingValue(i));
-    if (!I || !I->hasOneUser() || I->getIndices() != FirstEVI->getIndices() ||
-        I->getAggregateOperand()->getType() !=
-            FirstEVI->getAggregateOperand()->getType())
+InstCombinerImpl::foldPHIArgExtractValueInstructionIntoPHI(PHINode &RootPN) {
+  // We cannot create a new instruction after the PHI if the terminator is an
+  // EHPad because there is no valid insertion point.
+  if (Instruction *TI = RootPN.getParent()->getTerminator())
+    if (TI->isEHPad())
       return nullptr;
-  }
 
-  // Create a new PHI node to receive the values the aggregate operand has
-  // in each incoming basic block.
-  auto *NewAggregateOperand = PHINode::Create(
-      FirstEVI->getAggregateOperand()->getType(), PN.getNumIncomingValues(),
-      FirstEVI->getAggregateOperand()->getName() + ".pn");
-  // And populate the PHI with said values.
-  for (auto Incoming : zip(PN.blocks(), PN.incoming_values()))
-    NewAggregateOperand->addIncoming(
-        cast<ExtractValueInst>(std::get<1>(Incoming))->getAggregateOperand(),
-        std::get<0>(Incoming));
-  InsertNewInstBefore(NewAggregateOperand, PN);
+  // The reference def. All other defs must be compatible with this one,
+  // else we won't be able to perform the transformation.
+  Optional<ExtractValueInst *> FirstEVI;
+
+  struct NodeDsc {
+    // How many uses does this node has within the graph?
+    // Note that there may be out-of-graph uses!
+    unsigned NumUsesSeen = 0;
+    // After remapping, what new value shall be used instead of this one?
+    Value *NewV = nullptr;
+  };
 
-  // And finally, create `extractvalue` over the newly-formed PHI nodes.
-  auto *NewEVI = ExtractValueInst::Create(NewAggregateOperand,
-                                          FirstEVI->getIndices(), PN.getName());
+  // A map of all the graph nodes.
+  // WARNING: this must have stable iteration order!
+  constexpr unsigned NodeCountSmallSize = 64; // 94'th percentile
+  SmallMapVector<Value *, NodeDsc, NodeCountSmallSize> Graph;
+
+  // Potentially record the node in a map, and bump it's observed use count.
+  // Returns whether or not this node is encountered for the first time.
+  auto RecordNode = [&Graph](Value *V) {
+    // See if we've already seen this Value or record a new encountered Value.
+    std::pair<decltype(Graph)::iterator, bool /*Inserted*/> I =
+        Graph.insert({V, {}});
+    // Regardless, record that we have reached the node it from a new use.
+    ++I.first->second.NumUsesSeen;
+    return I.second; // Is this the first time we've seen this node?
+  };
+
+  // A data structure to keep track of which nodes we still need to visit,
+  // during initial graph prospection. The order in which we'll process the
+  // nodes doesn't really matter, but let's do a classic depth-first traversal.
+  constexpr unsigned WorklistSmallSize = 8; // 98'th percentile
+  SmallVector<PHINode *, WorklistSmallSize> Worklist;
+
+  // Given this PHI, potentially enqueue it for further analysis.
+  // NOTE: we don't/can't do any use-checking here!
+  //       We must first process the entire graph!
+  auto EnqueuePHI = [&RecordNode, &Worklist](PHINode *PN) {
+    // See if this Value was seen already and/or record a new encountered Value.
+    if (!RecordNode(PN))
+      return; // Node previously seen. No further action needed.
+    // Otherwise, actually enqueue it for analysis.
+    Worklist.emplace_back(PN);
+  };
 
-  PHIArgMergedDebugLoc(NewEVI, PN);
+  // Can we PHI together operands of (all the) extractvalue`s?
+  auto DefsAreCompatible = [](ExtractValueInst *A, ExtractValueInst *B) {
+    return A->getAggregateOperand()->getType() ==
+               B->getAggregateOperand()->getType() &&
+           A->getIndices() == B->getIndices();
+  };
+
+  // Given this value, which is not a PHI and therefore must be a def,
+  // potentially  record it as a new graph node, and see if it's an
+  // extractvalue that is compatible with previous defs we've reached.
+  // NOTE: we don't/can't do any use-checking here!
+  //       We must first process the entire graph!
+  auto RecordDef = [&RecordNode, &FirstEVI,
+                    &DefsAreCompatible](Value *V) -> bool /*IsCompatibleDef*/ {
+    auto *EVI = dyn_cast<ExtractValueInst>(V);
+    if (!EVI)
+      return false; // Not an extractvalue instruction. Give up.
+
+    // See if this Value was seen already and/or record a new encountered Value.
+    if (!RecordNode(EVI))
+      return true; // First time seeing. All good, no further checking needed.
+
+    // Is this the first extractvalue we've found?
+    if (!FirstEVI) {
+      FirstEVI = EVI;
+      return true; // All good, no further checking possible.
+    }
+
+    // Otherwise, if this is the first time we're seeing this extractvalue,
+    // but not the first extractvalue we're seeing, we actually do need to
+    // check that they're compatible.
+    return DefsAreCompatible(EVI, *FirstEVI);
+  };
+
+  // Traverse this PHI recursively, and for each incoming value,
+  // either recurse into the new PHI, or record the defs,
+  // all of which must be compatible extractvalue's.
+  EnqueuePHI(&RootPN);
+  while (!Worklist.empty()) {
+    PHINode *PN = Worklist.pop_back_val();
+
+    // Now, let's see what this PHI consists of, what are it's incoming values.
+    for (Value *V : PN->incoming_values()) {
+      // Enqueue each PHI node to be visited in later iteration of the loop.
+      if (auto *PN = dyn_cast<PHINode>(V)) {
+        EnqueuePHI(PN); // Updates Worklist.
+        continue;       // Onto next incoming value.
+      }
+
+      // Otherwise, if it's not a PHI node, it must be a def. Is it a good def?
+      if (!RecordDef(V))
+        return nullptr; // Bad def, abort.
+      // Onto next yet-unexplored graph node.
+    }
+  }
+  assert(Graph.size() >= 2 &&
+         "Should have mapped a graph with at least two nodes.");
+  assert(FirstEVI && "Should've found at least one extractvalue instruction.");
+
+  // Okay! The original PHI RootPN, recursively, consists only of other PHI's
+  // and intercompatible extractvalue`s! So we can pull them through the PHI's.
+
+  // One thing though, we need to ensure that the transform does not increase
+  // instruction count. Reminder: we have N PHI nodes and M extractvalue`s,
+  // we'll need to produce N PHI nodes, and a single extractvalue.
+  // Therefore, all old PHI nodes and at least one extractvalue must go away.
+
+  auto GraphNodeHasNoOutOfGraphUses = [&RootPN, &Graph](
+                                          std::pair<Value *, NodeDsc> Node) {
+    assert(Node.first != &RootPN && "We shouldn't use-check the root PHI node");
+
+    // We've counted how many times each graph node is used by other graph nodes
+    // so to check that the node has no out-of-graph uses we only need to check
+    // that the Value use count matches the number of in-graph uses.
+    bool AllUsesSeen = Node.first->hasNUses(Node.second.NumUsesSeen);
+
+    (void)Graph;
+    assert(all_of(Node.first->users(),
+                  [&Graph](User *U) {
+                    return isa<PHINode>(U) && Graph.count(U);
+                  }) == AllUsesSeen &&
+           "Sanity check: checking whether or not the node has uses that are "
+           "not recorded in the Graph map should be identical to checking the "
+           "recorded numer of times we've reached the value with use count of "
+           "the value.");
+
+    return AllUsesSeen;
+  };
+
+  // At least one extractvalue must only have in-graph uses, and go away.
+  if (none_of(make_filter_range(Graph,
+                                [](std::pair<Value *, NodeDsc> Node) {
+                                  return !isa<PHINode>(Node.first);
+                                }),
+              GraphNodeHasNoOutOfGraphUses))
+    return nullptr;
+
+  // And all the PHI nodes must only have in-graph ses and thus go away.
+  assert(Graph.front().first == &RootPN &&
+         "Expected the root PHI to be the first element in Graph mapvector.");
+  if (!all_of(make_filter_range(ArrayRef<std::pair<Value *, NodeDsc>>(
+                                    Graph.begin(), Graph.end())
+                                    .drop_front(),
+                                [](std::pair<Value *, NodeDsc> Node) {
+                                  return isa<PHINode>(Node.first);
+                                }),
+              GraphNodeHasNoOutOfGraphUses))
+    return nullptr;
+
+  // Awesome. We are committed to a rewrite now.
+  // The actual rewrite consists of three separate steps.
+
+  // Rewrite step 1: remap each graph node, separately, but don't recreate graph
+  // just yet (because we are not visiting nodes for remapping in def-use order,
+  // so it is not guaranteed that all defs were remapped already).
+  // NOTE: the iteration order *IS* (and must be) stable.
+  Type *AggTy = (*FirstEVI)->getAggregateOperand()->getType();
+  for (std::pair<Value *, NodeDsc> &Node : Graph) {
+    Value *OldV = Node.first;
+    Value *&NewV = Node.second.NewV;
+
+    if (auto *OldPN = dyn_cast<PHINode>(OldV)) {
+      NewV = PHINode::Create(AggTy, OldPN->getNumIncomingValues(),
+                             OldPN->getName() + ".agg");
+      InsertNewInstBefore(cast<Instruction>(NewV), *OldPN);
+    } else
+      NewV = cast<ExtractValueInst>(OldV)->getAggregateOperand();
+  }
+
+  auto GetRemappedValue = [&Graph](Value *OldV) {
+    auto I = Graph.find(OldV);
+    assert(I != Graph.end() && "Not a graph node?");
+    Value *NewV = I->second.NewV;
+    assert(NewV && "Node should have been remaped by now.");
+    return NewV;
+  };
+
+  // Rewrite step 2: actually recreate the def-use graph.
+  // Now that all the nodes were remapped in step 1, we can actually populate
+  // PHI nodes with proper remapped values.
+  // NOTE: the iteration order is not externally obserable, but is stable.
+  for (const std::pair<Value *, NodeDsc> &Node : Graph) {
+    auto *OldPN = dyn_cast<PHINode>(Node.first);
+    if (!OldPN)
+      continue; // Only have to operate on PHI's now.
+    auto *NewPN = cast<PHINode>(Node.second.NewV);
+    // Populate this new PHI node with remapped incoming values.
+    for (auto Operands : zip(OldPN->incoming_values(), OldPN->blocks()))
+      NewPN->addIncoming(GetRemappedValue(std::get<0>(Operands)),
+                         std::get<1>(Operands));
+  }
+
+  // Rewrite step 3: create the extractvalue over the remapped root PHI node.
+  auto *NewEVI = ExtractValueInst::Create(
+      GetRemappedValue(&RootPN), (*FirstEVI)->getIndices(), RootPN.getName());
+
+  PHIArgMergedDebugLoc(NewEVI, RootPN);
   ++NumPHIsOfExtractValues;
   return NewEVI;
 }
 
 /// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the
 /// adds all have a single user, turn this into a phi and a single binop.
 Instruction *InstCombinerImpl::foldPHIArgBinOpIntoPHI(PHINode &PN) {
   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
Instruction *InstCombinerImpl::foldPHIArgOpIntoPHI(PHINode &PN) {
   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
 
   if (isa<GetElementPtrInst>(FirstInst))
     return foldPHIArgGEPIntoPHI(PN);
   if (isa<LoadInst>(FirstInst))
     return foldPHIArgLoadIntoPHI(PN);
   if (isa<InsertValueInst>(FirstInst))
     return foldPHIArgInsertValueInstructionIntoPHI(PN);
-  if (isa<ExtractValueInst>(FirstInst))
-    return foldPHIArgExtractValueInstructionIntoPHI(PN);
 
   // Scan the instruction, looking for input operations that can be folded away.
   // If all input operands to the phi are the same instruction (e.g. a cast from
   // the same type or "+42") we can pull the operation through the PHI, reducing
   // code size and simplifying code.
   Constant *ConstantOp = nullptr;
   Type *CastSrcTy = nullptr;
 
Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) {
   if (isa<Instruction>(PN.getIncomingValue(0)) &&
       isa<Instruction>(PN.getIncomingValue(1)) &&
       cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
           cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
       PN.getIncomingValue(0)->hasOneUser())
     if (Instruction *Result = foldPHIArgOpIntoPHI(PN))
       return Result;
 
+  // If all non-PHI PHI operands are extractvalues, pull them through the PHI's.
+  if (Instruction *Result = foldPHIArgExtractValueInstructionIntoPHI(PN))
+    return Result;
+
   // If this is a trivial cycle in the PHI node graph, remove it.  Basically, if
   // this PHI only has a single use (a PHI), and if that PHI only has one use (a
   // PHI)... break the cycle.
   if (PN.hasOneUse()) {
     if (Instruction *Result = foldIntegerTypedPHI(PN))
       return Result;
 
     Instruction *PHIUser = cast<Instruction>(PN.user_back());

llvm/test/Transforms/InstCombine/phi-aware-aggregate-reconstruction.ll

 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I5_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
 ; CHECK-NEXT:    call void @baz()
-; CHECK-NEXT:    ret { i32, i32 } [[AGG_LEFT_PN]]
+; CHECK-NEXT:    ret { i32, i32 } [[I5_AGG]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   %i2 = extractvalue { i32, i32 } %agg_left, 1
   call void @foo()

 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
-; CHECK-NEXT:    [[AGG_RIGHT_PN:%.*]] = phi { i32, i32 } [ [[AGG_RIGHT]], [[LEFT]] ], [ [[AGG_LEFT]], [[RIGHT]] ]
-; CHECK-NEXT:    [[I6:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT_PN]], 1
-; CHECK-NEXT:    [[I5:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN]], 0
+; CHECK-NEXT:    [[I5_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I6_AGG:%.*]] = phi { i32, i32 } [ [[AGG_RIGHT]], [[LEFT]] ], [ [[AGG_LEFT]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I6:%.*]] = extractvalue { i32, i32 } [[I6_AGG]], 1
+; CHECK-NEXT:    [[I5:%.*]] = extractvalue { i32, i32 } [[I5_AGG]], 0
 ; CHECK-NEXT:    call void @baz()
 ; CHECK-NEXT:    [[I7:%.*]] = insertvalue { i32, i32 } undef, i32 [[I5]], 0
 ; CHECK-NEXT:    [[I8:%.*]] = insertvalue { i32, i32 } [[I7]], i32 [[I6]], 1
 ; CHECK-NEXT:    ret { i32, i32 } [[I8]]
 ;
 entry:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   %i2 = extractvalue { i32, i32 } %agg_left, 1

 ; CHECK-NEXT:    br i1 [[C0:%.*]], label [[BB0_DISPATCH:%.*]], label [[BB10:%.*]]
 ; CHECK:       bb0.dispatch:
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB00:%.*]], label [[BB01:%.*]]
 ; CHECK:       bb00:
 ; CHECK-NEXT:    br label [[BB0_MERGE:%.*]]
 ; CHECK:       bb01:
 ; CHECK-NEXT:    br label [[BB0_MERGE]]
 ; CHECK:       bb0.merge:
-; CHECK-NEXT:    [[AGG_00_PN:%.*]] = phi { i32, i32 } [ [[AGG_00:%.*]], [[BB00]] ], [ [[AGG_01:%.*]], [[BB01]] ]
+; CHECK-NEXT:    [[I4_AGG:%.*]] = phi { i32, i32 } [ [[AGG_00:%.*]], [[BB00]] ], [ [[AGG_01:%.*]], [[BB01]] ]
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_00_PN_PN:%.*]] = phi { i32, i32 } [ [[AGG_00_PN]], [[BB0_MERGE]] ], [ [[AGG_10:%.*]], [[BB10]] ]
+; CHECK-NEXT:    [[I8_AGG:%.*]] = phi { i32, i32 } [ [[I4_AGG]], [[BB0_MERGE]] ], [ [[AGG_10:%.*]], [[BB10]] ]
 ; CHECK-NEXT:    call void @baz()
-; CHECK-NEXT:    ret { i32, i32 } [[AGG_00_PN_PN]]
+; CHECK-NEXT:    ret { i32, i32 } [[I8_AGG]]
 ;
 entry:
   br i1 %c0, label %bb0.dispatch, label %bb10
 
 bb0.dispatch:
   br i1 %c1, label %bb00, label %bb01
 
 bb00:

 }
 
 ; Not sure what should happen for cycles.
 define { i32, i32 } @test4({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i1 %c0) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C0:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
-; CHECK-NEXT:    [[I0:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT:%.*]], 0
-; CHECK-NEXT:    [[I2:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT]], 1
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[MIDDLE:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I3:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT:%.*]], 0
-; CHECK-NEXT:    [[I4:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT]], 1
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[MIDDLE]]
 ; CHECK:       middle:
-; CHECK-NEXT:    [[I5:%.*]] = phi i32 [ [[I0]], [[LEFT]] ], [ [[I3]], [[RIGHT]] ], [ [[I5]], [[MIDDLE]] ]
-; CHECK-NEXT:    [[I6:%.*]] = phi i32 [ [[I2]], [[LEFT]] ], [ [[I4]], [[RIGHT]] ], [ [[I6]], [[MIDDLE]] ]
+; CHECK-NEXT:    [[I5_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[I5_AGG]], [[MIDDLE]] ]
+; CHECK-NEXT:    [[I6_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT]], [[RIGHT]] ], [ [[I6_AGG]], [[MIDDLE]] ]
 ; CHECK-NEXT:    call void @baz()
 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @geni1()
 ; CHECK-NEXT:    br i1 [[C1]], label [[END:%.*]], label [[MIDDLE]]
 ; CHECK:       end:
+; CHECK-NEXT:    [[I5:%.*]] = extractvalue { i32, i32 } [[I5_AGG]], 0
 ; CHECK-NEXT:    [[I7:%.*]] = insertvalue { i32, i32 } undef, i32 [[I5]], 0
+; CHECK-NEXT:    [[I6:%.*]] = extractvalue { i32, i32 } [[I6_AGG]], 1
 ; CHECK-NEXT:    [[I8:%.*]] = insertvalue { i32, i32 } [[I7]], i32 [[I6]], 1
 ; CHECK-NEXT:    ret { i32, i32 } [[I8]]
 ;
 entry:
   br i1 %c0, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0

 ; CHECK-NEXT:    br i1 [[C0:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[MIDDLE:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[MIDDLE]]
 ; CHECK:       middle:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_LEFT_PN]], [[MIDDLE]] ]
+; CHECK-NEXT:    [[I5_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[I5_AGG]], [[MIDDLE]] ]
 ; CHECK-NEXT:    call void @baz()
 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @geni1()
 ; CHECK-NEXT:    br i1 [[C1]], label [[END:%.*]], label [[MIDDLE]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret { i32, i32 } [[AGG_LEFT_PN]]
+; CHECK-NEXT:    ret { i32, i32 } [[I5_AGG]]
 ;
 entry:
   br i1 %c0, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   %i2 = extractvalue { i32, i32 } %agg_left, 1
   call void @foo()

 ; CHECK-NEXT:    br i1 [[C0:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I5_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
 ; CHECK-NEXT:    call void @baz()
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[END:%.*]], label [[PASSTHROUGH:%.*]]
 ; CHECK:       passthrough:
 ; CHECK-NEXT:    call void @qux()
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    call void @quux()
-; CHECK-NEXT:    ret { i32, i32 } [[AGG_LEFT_PN]]
+; CHECK-NEXT:    ret { i32, i32 } [[I5_AGG]]
 ;
 entry:
   br i1 %c0, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   %i2 = extractvalue { i32, i32 } %agg_left, 1
   call void @foo()

 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    switch i32 [[VAL_RIGHT:%.*]], label [[IMPOSSIBLE]] [
 ; CHECK-NEXT:    i32 42, label [[END]]
 ; CHECK-NEXT:    i32 -42, label [[END]]
 ; CHECK-NEXT:    ]
 ; CHECK:       impossible:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_RIGHT]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I5_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_RIGHT]], [[RIGHT]] ]
 ; CHECK-NEXT:    call void @baz()
-; CHECK-NEXT:    ret { i32, i32 } [[AGG_LEFT_PN]]
+; CHECK-NEXT:    ret { i32, i32 } [[I5_AGG]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   %i2 = extractvalue { i32, i32 } %agg_left, 1
   call void @foo()

 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I0_PN_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
 ; CHECK-NEXT:    call void @baz()
-; CHECK-NEXT:    ret { i32, i32 } [[AGG_LEFT_PN]]
+; CHECK-NEXT:    ret { i32, i32 } [[I0_PN_AGG]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   %i1 = extractvalue { i32, i32 } %agg_left, 1
   %i2 = insertvalue { i32, i32 } undef, i32 %i0, 0

llvm/test/Transforms/InstCombine/phi-of-extractvalues.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 declare void @usei32(i32)
 
 ; If we have a phi of extractvalues, we can sink it,
 ; Here, we only need a PHI for extracted values.
 define i32 @test0({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i1 %c) {
 ; CHECK-LABEL: @test0(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
-; CHECK-NEXT:    [[R:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN]], 0
+; CHECK-NEXT:    [[R_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[R:%.*]] = extractvalue { i32, i32 } [[R_AGG]], 0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   br label %end

 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { { i32, i32 }, { i32, i32 } } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
-; CHECK-NEXT:    [[R:%.*]] = extractvalue { { i32, i32 }, { i32, i32 } } [[AGG_LEFT_PN]], 0, 0
+; CHECK-NEXT:    [[R_AGG:%.*]] = phi { { i32, i32 }, { i32, i32 } } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[R:%.*]] = extractvalue { { i32, i32 }, { i32, i32 } } [[R_AGG]], 0, 0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = extractvalue {{ i32, i32 }, { i32, i32 }} %agg_left, 0, 0
   br label %end

 ; CHECK-NEXT:    br i1 [[C0:%.*]], label [[END:%.*]], label [[DISPATCH:%.*]]
 ; CHECK:       dispatch:
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       right:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[ENTRY:%.*]] ], [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
-; CHECK-NEXT:    [[R:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN]], 0
+; CHECK-NEXT:    [[R_AGG:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[ENTRY:%.*]] ], [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[R:%.*]] = extractvalue { i32, i32 } [[R_AGG]], 0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   %i1 = extractvalue { i32, i32 } %agg_right, 0
   br i1 %c0, label %end, label %dispatch
 
 dispatch: