[InstCombine] PHI-of-extractvalues -> extractvalue-of-PHI, aka invokes are bad

[lebedev.ri]

Summary

While since D86306 we do it's sibling fold for insertvalue,
we should also do this for extractvalue's.

And unlike that one, the results here are, quite honestly, shocking,
as it can be observed here on vanilla llvm test-suite + RawSpeed results:

| statistic name                                     | baseline  | proposed  |       Δ |       % |    |%| |
|----------------------------------------------------|-----------|-----------|--------:|--------:|-------:|
| asm-printer.EmittedInsts                           | 7945095   | 7942507   |   -2588 |  -0.03% |  0.03% |
| assembler.ObjectBytes                              | 273209920 | 273069800 | -140120 |  -0.05% |  0.05% |
| early-cse.NumCSE                                   | 2183363   | 2183398   |      35 |   0.00% |  0.00% |
| early-cse.NumSimplify                              | 541847    | 550017    |    8170 |   1.51% |  1.51% |
| instcombine.NumAggregateReconstructionsSimplified  | 2139      | 108       |   -2031 | -94.95% | 94.95% |
| instcombine.NumCombined                            | 3601364   | 3635448   |   34084 |   0.95% |  0.95% |
| instcombine.NumConstProp                           | 27153     | 27157     |       4 |   0.01% |  0.01% |
| instcombine.NumDeadInst                            | 1694521   | 1765022   |   70501 |   4.16% |  4.16% |
| instcombine.NumPHIsOfExtractValues                 | 0         | 37546     |   37546 |   0.00% |  0.00% |
| instcombine.NumSunkInst                            | 63158     | 63686     |     528 |   0.84% |  0.84% |
| instcount.NumBrInst                                | 874304    | 871857    |   -2447 |  -0.28% |  0.28% |
| instcount.NumCallInst                              | 1757657   | 1758402   |     745 |   0.04% |  0.04% |
| instcount.NumExtractValueInst                      | 45623     | 11483     |  -34140 | -74.83% | 74.83% |
| instcount.NumInsertValueInst                       | 4983      | 580       |   -4403 | -88.36% | 88.36% |
| instcount.NumInvokeInst                            | 61018     | 59478     |   -1540 |  -2.52% |  2.52% |
| instcount.NumLandingPadInst                        | 35334     | 34215     |   -1119 |  -3.17% |  3.17% |
| instcount.NumPHIInst                               | 344428    | 331116    |  -13312 |  -3.86% |  3.86% |
| instcount.NumRetInst                               | 100773    | 100772    |      -1 |   0.00% |  0.00% |
| instcount.TotalBlocks                              | 1081154   | 1077166   |   -3988 |  -0.37% |  0.37% |
| instcount.TotalFuncs                               | 101443    | 101442    |      -1 |   0.00% |  0.00% |
| instcount.TotalInsts                               | 8890201   | 8833747   |  -56454 |  -0.64% |  0.64% |
| instsimplify.NumSimplified                         | 75822     | 75707     |    -115 |  -0.15% |  0.15% |
| simplifycfg.NumHoistCommonCode                     | 24203     | 24197     |      -6 |  -0.02% |  0.02% |
| simplifycfg.NumHoistCommonInstrs                   | 48201     | 48195     |      -6 |  -0.01% |  0.01% |
| simplifycfg.NumInvokes                             | 2785      | 4298      |    1513 |  54.33% | 54.33% |
| simplifycfg.NumSimpl                               | 997332    | 1018189   |   20857 |   2.09% |  2.09% |
| simplifycfg.NumSinkCommonCode                      | 7088      | 6464      |    -624 |  -8.80% |  8.80% |
| simplifycfg.NumSinkCommonInstrs                    | 15117     | 14021     |   -1096 |  -7.25% |  7.25% |

... which tells us that this new fold fires whopping 38k times,
increasing the amount of SimplifyCFG's invoke->call transforms by +54% (+1513) (again, D85787 did that last time),
decreasing total instruction count by -0.64% (-56454),
and sharply decreasing count of insertvalue's (-88.36%, i.e. 9 times less)
and extractvalue's (-74.83%, i.e. four times less).

This causes geomean -0.01% binary size decrease
http://llvm-compile-time-tracker.com/compare.php?from=4d5ca22b8adfb6643466e4e9f48ba14bb48938bc&to=97dacca0111cb2ae678204e52a3cee00e3a69208&stat=size-text
and, ignoring O0-g, is a geomean -0.01%..-0.05% compile-time improvement
http://llvm-compile-time-tracker.com/compare.php?from=4d5ca22b8adfb6643466e4e9f48ba14bb48938bc&to=97dacca0111cb2ae678204e52a3cee00e3a69208&stat=instructions

The other thing that tells is, is that while this is a massive win for invoke->call transform
InstCombinerImpl::foldAggregateConstructionIntoAggregateReuse() fold,
which is supposed to be dealing with such aggregate reconstructions,
fires a lot less now. There are two reasons why:

1. After this fold, as it can be seen in tests, we may (will) end up with trivially redundant PHI nodes. We don't CSE them in InstCombine presently, which means that EarlyCSE needs to run and then InstCombine rerun.
2. But then, EarlyCSE not only manages to fold such redundant PHI's, it also sees that the extract-insert chain recreates the original aggregate, and replaces it with the original aggregate.

The take-aways are

1. We maybe should do most trivial, same-BB PHI CSE in InstCombine
2. I need to check if what other patterns remain, and how they can be resolved. (i.e. i wonder if foldAggregateConstructionIntoAggregateReuse() might go away)

[nikic]

Nice results :)

[spatel]

Seems like a logical extension of the earlier patch, and overall results are good. LGTM.

[lebedev.ri]

In D86530#2237315, @spatel wrote:

Seems like a logical extension of the earlier patch, and overall results are good. LGTM.

Thank you for the review.

[lebedev.ri]

@spatel

Ok, so

There are two reasons why:

1. After this fold, as it can be seen in tests, we may (will) end up with trivially redundant PHI nodes. We don't CSE them in InstCombine presently, which means that EarlyCSE needs to run and then InstCombine rerun.
2. But then, EarlyCSE not only manages to fold such redundant PHI's, it also sees that the extract-insert chain recreates the original aggregate, and replaces it with the original aggregate.

The take-aways are

1. We maybe should do most trivial, same-BB PHI CSE in InstCombine
2. I need to check if what other patterns remain, and how they can be resolved. (i.e. i wonder if foldAggregateConstructionIntoAggregateReuse() might go away)

I looked at remaining interesting patterns, and i believe this sinking won't be able to deal with everything.
there may be genuine extra uses of extracts, namely __cxa_begin_catch().

So before i look into foldAggregateConstructionIntoAggregateReuse() further,
what are your thoughts about teaching InstSimplify to do most basic CSE for PHI nodes?
(purely by comparing that the incoming values match)

This will ease some phase ordering issues, since then we won't need to run earlycse and rerun instcombine.

Effect on vanilla test-suite + RawSpeed:

| statistic name                                     | baseline  | proposed  |      Δ |        % |    \|%\| |
|----------------------------------------------------|-----------|-----------|-------:|---------:|---------:|
| asm-printer.EmittedInsts                           | 7942505   | 7942558   |     53 |    0.00% |    0.00% |
| assembler.ObjectBytes                              | 273069800 | 273085376 |  15576 |    0.01% |    0.01% |
| correlated-value-propagation.NumPhis               | 18825     | 18958     |    133 |    0.71% |    0.71% |
| early-cse.NumCSE                                   | 2183398   | 2183342   |    -56 |    0.00% |    0.00% |
| early-cse.NumCSELoad                               | 317796    | 317801    |      5 |    0.00% |    0.00% |
| early-cse.NumSimplify                              | 550017    | 542090    |  -7927 |   -1.44% |    1.44% |
| instcombine.NumAggregateReconstructionsSimplified  | 108       | 4502      |   4394 | 4068.52% | 4068.52% |
| instcombine.NumCombined                            | 3635533   | 3659879   |  24346 |    0.67% |    0.67% |
| instcombine.NumDeadInst                            | 1765202   | 1770173   |   4971 |    0.28% |    0.28% |
| instcombine.NumPHIsOfExtractValues                 | 37546     | 37521     |    -25 |   -0.07% |    0.07% |
| instcount.NumBrInst                                | 871857    | 871838    |    -19 |    0.00% |    0.00% |
| instcount.NumCallInst                              | 1758402   | 1758818   |    416 |    0.02% |    0.02% |
| instcount.NumExtractValueInst                      | 11483     | 11477     |     -6 |   -0.05% |    0.05% |
| instcount.NumInsertValueInst                       | 580       | 578       |     -2 |   -0.34% |    0.34% |
| instcount.NumInvokeInst                            | 59478     | 59502     |     24 |    0.04% |    0.04% |
| instcount.NumLandingPadInst                        | 34215     | 34214     |     -1 |    0.00% |    0.00% |
| instcount.NumPHIInst                               | 331116    | 331086    |    -30 |   -0.01% |    0.01% |
| instcount.NumResumeInst                            | 8062      | 8061      |     -1 |   -0.01% |    0.01% |
| instcount.NumRetInst                               | 100772    | 100770    |     -2 |    0.00% |    0.00% |
| instcount.TotalBlocks                              | 1077166   | 1077168   |      2 |    0.00% |    0.00% |
| instcount.TotalFuncs                               | 101442    | 101441    |     -1 |    0.00% |    0.00% |
| instcount.TotalInsts                               | 8833575   | 8833896   |    321 |    0.00% |    0.00% |
| simplifycfg.NumInvokes                             | 4298      | 4406      |    108 |    2.51% |    2.51% |
| simplifycfg.NumSimpl                               | 1018189   | 998050    | -20139 |   -1.98% |    1.98% |

... so it again results in improvements in invoke->call fold.

[spatel]

In D86530#2238460, @lebedev.ri wrote:

So before i look into foldAggregateConstructionIntoAggregateReuse() further,
what are your thoughts about teaching InstSimplify to do most basic CSE for PHI nodes?
(purely by comparing that the incoming values match)

Instruction::isIdenticalTo()? I see one use of that via visitStoreInst, so there's possible precedent. Start a llvm-dev thread to get other opinions?

[lebedev.ri]

In D86530#2238463, @spatel wrote:

In D86530#2238460, @lebedev.ri wrote:

So before i look into foldAggregateConstructionIntoAggregateReuse() further,
what are your thoughts about teaching InstSimplify to do most basic CSE for PHI nodes?
(purely by comparing that the incoming values match)

Instruction::isIdenticalTo()?

Hm, i guess, although that one is broken QoI-wise for PHI's - it assumes identical incoming block order, which isn't something that should be depended upon.

I see one use of that via visitStoreInst, so there's possible precedent. Start a llvm-dev thread to get other opinions?

[lebedev.ri]

In D86530#2238580, @lebedev.ri wrote:

In D86530#2238463, @spatel wrote:

In D86530#2238460, @lebedev.ri wrote:

So before i look into foldAggregateConstructionIntoAggregateReuse() further,
what are your thoughts about teaching InstSimplify to do most basic CSE for PHI nodes?
(purely by comparing that the incoming values match)

Instruction::isIdenticalTo()?

Hm, i guess, although that one is broken QoI-wise for PHI's - it assumes identical incoming block order, which isn't something that should be depended upon.

I see one use of that via visitStoreInst, so there's possible precedent. Start a llvm-dev thread to get other opinions?

Actually, apparently we don't even do PHI CSE in EarlyCSE,
so i consider my question to be dumb,
and directly proceeded with the fix, rG6102310d814ad73eab60a88b21dd70874f7a056f.

[lebedev.ri]

In D86530#2242350, @lebedev.ri wrote:

In D86530#2238580, @lebedev.ri wrote:

In D86530#2238463, @spatel wrote:

In D86530#2238460, @lebedev.ri wrote:

So before i look into foldAggregateConstructionIntoAggregateReuse() further,
what are your thoughts about teaching InstSimplify to do most basic CSE for PHI nodes?
(purely by comparing that the incoming values match)

Instruction::isIdenticalTo()?

Hm, i guess, although that one is broken QoI-wise for PHI's - it assumes identical incoming block order, which isn't something that should be depended upon.

I see one use of that via visitStoreInst, so there's possible precedent. Start a llvm-dev thread to get other opinions?

Actually, apparently we don't even do PHI CSE in EarlyCSE,
so i consider my question to be dumb,
and directly proceeded with the fix, rG6102310d814ad73eab60a88b21dd70874f7a056f.

Yikes, that could've/should've gone smoother.

But with that done, i've taken some time to analyze next step.
As of right now, in vanilla llvm test-suite + RawSpeed, there are 41 motivational patterns remain
(resume of something that isn't either a landingpad or a PHI of landingpads).

All those cases require multiple levels of PHI's,
and in all of those cases at least one extractvalue has an extra use,
which goes against the current legality checking for these transforms.

But even if we relax it to "all PHIs must go away, and at least one extractvalue must go away",
while that does finally catch all the remaining motivational cases,
it causes geomean +0.10% compile time increase (regression),
mainly because of, i believe, use-count checking, and it's "greedy" approach
D86882, http://llvm-compile-time-tracker.com/compare.php?from=1d01fc100bb5bef5f5eaf92520b2e52f64ee1d6e&to=d07a30a216f640c26c08771e2f7ecba783f5e44e&stat=instructions

So it would appear i will indeed have to enhance foldAggregateConstructionIntoAggregateReuse() :/

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
 
   Instruction *foldAddWithConstant(BinaryOperator &Add);
 
   /// Try to rotate an operation below a PHI node, using PHI nodes for
   /// its operands.
   Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
+  Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
   Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
   Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
   Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
 
   /// If an integer typed PHI has only one use which is an IntToPtr operation,
   /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
   /// insert a new pointer typed PHI and replace the original one.
   Instruction *foldIntegerTypedPHI(PHINode &PN);

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

 #define DEBUG_TYPE "instcombine"
 
 static cl::opt<unsigned>
 MaxNumPhis("instcombine-max-num-phis", cl::init(512),
            cl::desc("Maximum number phis to handle in intptr/ptrint folding"));
 
 STATISTIC(NumPHIsOfInsertValues,
           "Number of phi-of-insertvalue turned into insertvalue-of-phis");
+STATISTIC(NumPHIsOfExtractValues,
+          "Number of phi-of-extractvalue turned into extractvalue-of-phi");
 
 /// The PHI arguments will be folded into a single operation with a PHI node
 /// as input. The debug location of the single operation will be the merged
 /// locations of the original PHI node arguments.
 void InstCombinerImpl::PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN) {
   auto *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
   Inst->setDebugLoc(FirstInst->getDebugLoc());
   // We do not expect a CallInst here, otherwise, N-way merging of DebugLoc
InstCombinerImpl::foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN) {
   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.
+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->hasOneUse() || I->getIndices() != FirstEVI->getIndices())
+      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);
+
+  // And finally, create `extractvalue` over the newly-formed PHI nodes.
+  auto *NewEVI = ExtractValueInst::Create(NewAggregateOperand,
+                                          FirstEVI->getIndices(), PN.getName());
+
+  PHIArgMergedDebugLoc(NewEVI, PN);
+  ++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 use, turn this into a phi and a single binop.
 Instruction *InstCombinerImpl::foldPHIArgBinOpIntoPHI(PHINode &PN) {
   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
   assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst));
   unsigned Opc = FirstInst->getOpcode();
   Value *LHSVal = FirstInst->getOperand(0);
   Value *RHSVal = FirstInst->getOperand(1);
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;
 

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:    [[I8_MERGED:%.*]] = phi { i32, i32 } [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_LEFT:%.*]], [[LEFT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN1:%.*]] = phi { i32, i32 } [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I6:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN1]], 1
+; CHECK-NEXT:    [[I5:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN]], 0
 ; CHECK-NEXT:    call void @baz()
-; CHECK-NEXT:    ret { i32, i32 } [[I8_MERGED]]
+; 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:
   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()

 }
 
 ; Second element is coming from wrong aggregate
 define { i32, i32 } @negative_test1({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i1 %c) {
 ; CHECK-LABEL: @negative_test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
-; CHECK-NEXT:    [[I4:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT:%.*]], 1
-; CHECK-NEXT:    [[I0:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT:%.*]], 0
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I3:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT]], 0
-; CHECK-NEXT:    [[I2:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT]], 1
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[I5:%.*]] = phi i32 [ [[I0]], [[LEFT]] ], [ [[I3]], [[RIGHT]] ]
-; CHECK-NEXT:    [[I6:%.*]] = phi i32 [ [[I4]], [[LEFT]] ], [ [[I2]], [[RIGHT]] ]
+; 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:    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

 ; FIXME: we should probably be able to handle multiple levels of PHI indirection
 define { i32, i32 } @test3({ i32, i32 } %agg_00, { i32, i32 } %agg_01, { i32, i32 } %agg_10, i1 %c0, i1 %c1) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; 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:    [[I0:%.*]] = extractvalue { i32, i32 } [[AGG_00:%.*]], 0
-; CHECK-NEXT:    [[I1:%.*]] = extractvalue { i32, i32 } [[AGG_00]], 1
 ; CHECK-NEXT:    br label [[BB0_MERGE:%.*]]
 ; CHECK:       bb01:
-; CHECK-NEXT:    [[I2:%.*]] = extractvalue { i32, i32 } [[AGG_01:%.*]], 0
-; CHECK-NEXT:    [[I3:%.*]] = extractvalue { i32, i32 } [[AGG_01]], 1
 ; CHECK-NEXT:    br label [[BB0_MERGE]]
 ; CHECK:       bb0.merge:
-; CHECK-NEXT:    [[I4:%.*]] = phi i32 [ [[I0]], [[BB00]] ], [ [[I2]], [[BB01]] ]
-; CHECK-NEXT:    [[I5:%.*]] = phi i32 [ [[I1]], [[BB00]] ], [ [[I3]], [[BB01]] ]
+; CHECK-NEXT:    [[AGG_00_PN:%.*]] = phi { i32, i32 } [ [[AGG_00:%.*]], [[BB00]] ], [ [[AGG_01:%.*]], [[BB01]] ]
+; CHECK-NEXT:    [[AGG_00_PN1:%.*]] = phi { i32, i32 } [ [[AGG_00]], [[BB00]] ], [ [[AGG_01]], [[BB01]] ]
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       bb10:
-; CHECK-NEXT:    [[I6:%.*]] = extractvalue { i32, i32 } [[AGG_10:%.*]], 0
-; CHECK-NEXT:    [[I7:%.*]] = extractvalue { i32, i32 } [[AGG_10]], 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[I8:%.*]] = phi i32 [ [[I4]], [[BB0_MERGE]] ], [ [[I6]], [[BB10]] ]
-; CHECK-NEXT:    [[I9:%.*]] = phi i32 [ [[I5]], [[BB0_MERGE]] ], [ [[I7]], [[BB10]] ]
+; CHECK-NEXT:    [[AGG_00_PN_PN:%.*]] = phi { i32, i32 } [ [[AGG_00_PN]], [[BB0_MERGE]] ], [ [[AGG_10:%.*]], [[BB10]] ]
+; CHECK-NEXT:    [[AGG_00_PN1_PN:%.*]] = phi { i32, i32 } [ [[AGG_00_PN1]], [[BB0_MERGE]] ], [ [[AGG_10]], [[BB10]] ]
+; CHECK-NEXT:    [[I9:%.*]] = extractvalue { i32, i32 } [[AGG_00_PN1_PN]], 1
+; CHECK-NEXT:    [[I8:%.*]] = extractvalue { i32, i32 } [[AGG_00_PN_PN]], 0
 ; CHECK-NEXT:    call void @baz()
 ; CHECK-NEXT:    [[I10:%.*]] = insertvalue { i32, i32 } undef, i32 [[I8]], 0
 ; CHECK-NEXT:    [[I11:%.*]] = insertvalue { i32, i32 } [[I10]], i32 [[I9]], 1
 ; CHECK-NEXT:    ret { i32, i32 } [[I11]]
 ;
 entry:
   br i1 %c0, label %bb0.dispatch, label %bb10
 

 ; 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:    [[I8_MERGED:%.*]] = phi { i32, i32 } [ [[I8_MERGED]], [[MIDDLE]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_LEFT:%.*]], [[LEFT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[I8:%.*]], [[MIDDLE]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN1:%.*]] = phi { i32, i32 } [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT]], [[RIGHT]] ], [ [[I8]], [[MIDDLE]] ]
+; CHECK-NEXT:    [[I6:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN1]], 1
+; CHECK-NEXT:    [[I5:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN]], 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:    [[C1:%.*]] = call i1 @geni1()
 ; CHECK-NEXT:    br i1 [[C1]], label [[END:%.*]], label [[MIDDLE]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret { i32, i32 } [[I8_MERGED]]
+; CHECK-NEXT:    ret { i32, i32 } [[I8]]
 ;
 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:    [[I8_MERGED:%.*]] = phi { i32, i32 } [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_LEFT:%.*]], [[LEFT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN1:%.*]] = 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:    [[I6:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN1]], 1
+; CHECK-NEXT:    [[I5:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN]], 0
 ; CHECK-NEXT:    call void @quux()
-; CHECK-NEXT:    ret { i32, i32 } [[I8_MERGED]]
+; 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:
   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 [[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:    [[I8_MERGED:%.*]] = phi { i32, i32 } [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_LEFT:%.*]], [[LEFT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN1:%.*]] = phi { i32, i32 } [ [[AGG_LEFT]], [[LEFT]] ], [ [[AGG_RIGHT]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I7:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN1]], 1
+; CHECK-NEXT:    [[I0_PN:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT_PN]], 0
+; CHECK-NEXT:    [[I6:%.*]] = insertvalue { i32, i32 } undef, i32 [[I0_PN]], 0
 ; CHECK-NEXT:    call void @baz()
-; CHECK-NEXT:    ret { i32, i32 } [[I8_MERGED]]
+; CHECK-NEXT:    [[I8:%.*]] = insertvalue { i32, i32 } [[I6]], i32 [[I7]], 1
+; CHECK-NEXT:    ret { i32, i32 } [[I8]]
 ;
 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:    [[I0:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT:%.*]], 0
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I1:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT:%.*]], 0
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[I0]], [[LEFT]] ], [ [[I1]], [[RIGHT]] ]
+; 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:    ret i32 [[R]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = extractvalue { i32, i32 } %agg_left, 0
   br label %end

 }
 
 ; More complex aggregates are fine, too, as long as indicies match.
 define i32 @test5({{ i32, i32 }, { i32, i32 }} %agg_left, {{ i32, i32 }, { i32, i32 }} %agg_right, i1 %c) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
-; CHECK-NEXT:    [[I0:%.*]] = extractvalue { { i32, i32 }, { i32, i32 } } [[AGG_LEFT:%.*]], 0, 0
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I1:%.*]] = extractvalue { { i32, i32 }, { i32, i32 } } [[AGG_RIGHT:%.*]], 0, 0
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[I0]], [[LEFT]] ], [ [[I1]], [[RIGHT]] ]
+; 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:    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