[InstCombine] PHI-of-insertvalues -> insertvalue-of-PHI's

[lebedev.ri]

Summary

As per statistic, this happens pretty exceedingly rare,
but i have seen it in exactly the situations the
Phi-aware aggregate reconstruction would have handled,
eventually, and allowed invoke -> call fold later on.

So while this might be something that other fold
will have to learn about, i wonder if we should be
doing this transform in general?

Here, we are okay with adding two PHI's to get both the base aggregate,
and the inserted value. I'm not sure it makes much sense to restrict
it to a single phi (to just the inserted value?), because originally
we'd be receiving the final aggregate already..

llvm test-suite + RawSpeed:

| statistic name                             | baseline  | proposed  |    Δ |      % | \|%\| |
|--------------------------------------------|-----------|-----------|-----:|-------:|------:|
| instcombine.InsertValueOfPHIs              | 0         | 12        |  12  |  0.00% | 0.00% |
| asm-printer.EmittedInsts                   | 8926643   | 8926595   | -48  |  0.00% | 0.00% |
| instcombine.NumCombined                    | 3846614   | 3846640   |  26  |  0.00% | 0.00% |
| instcombine.NumConstProp                   | 24302     | 24293     |  -9  | -0.04% | 0.04% |
| instcombine.NumDeadInst                    | 1620140   | 1620112   | -28  |  0.00% | 0.00% |
| instcount.NumBrInst                        | 898466    | 898464    |  -2  |  0.00% | 0.00% |
| instcount.NumCallInst                      | 1760819   | 1760875   |  56  |  0.00% | 0.00% |
| instcount.NumExtractValueInst              | 45659     | 45649     | -10  | -0.02% | 0.02% |
| instcount.NumInsertValueInst               | 4991      | 4981      | -10  | -0.20% | 0.20% |
| instcount.NumIntToPtrInst                  | 27084     | 27087     |   3  |  0.01% | 0.01% |
| instcount.NumPHIInst                       | 371435    | 371429    |  -6  |  0.00% | 0.00% |
| instcount.NumStoreInst                     | 906011    | 906019    |   8  |  0.00% | 0.00% |
| instcount.TotalBlocks                      | 1105520   | 1105518   |  -2  |  0.00% | 0.00% |
| instcount.TotalInsts                       | 9795737   | 9795776   |  39  |  0.00% | 0.00% |
| simplifycfg.NumInvokes                     | 2784      | 2786      |   2  |  0.07% | 0.07% |
| simplifycfg.NumSimpl                       | 1001840   | 1001850   |  10  |  0.00% | 0.00% |
| simplifycfg.NumSinkCommonInstrs            | 15174     | 15170     |  -4  | -0.03% | 0.03% |

[lebedev.ri]

Up

[spatel]

This seems ok to me, but I haven't looked at insertvalue/extractvalue patterns very much, so you might want to get a 2nd opinion.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

618

I view it is an opportunity to update formatting of related code if we are adding similar but new functionality.
Otherwise, we are going to be stuck with those capital letters forever. :)

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

309

We are allowing multi-index aggregates, right? If so, we should have at least 1 test to verify that pattern is working as expected.

315

Testing my limits of C++... is seq() better/different than just listing the values as {0, 1}?

317

typo: receive

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

315

Right, in this case it's not, will change.

[lebedev.ri]

@spatel thank you for taking a look!
Addressing review comments.
I don't believe there are any sharp edges under the water in this case, it really should be that simple.

[lebedev.ri]

Hmm, i will follow-up with the same for extractvalue, i have an inkling suspicion
that it might just be enough to catch (some?) remaining interesting cases, and maybe spare me
from having to make InstCombinerImpl::foldAggregateConstructionIntoAggregateReuse() more recursive.

[spatel]

LGTM

[lebedev.ri]

In D86306#2234540, @spatel wrote:

LGTM

Thank you for review!

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
 
   /// This is a convenience wrapper function for the above two functions.
   Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
 
   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 *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

 //===- 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/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"
 #include "llvm/Transforms/Utils/Local.h"
+
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #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");
+
 /// 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
   // will be inefficient.
#endif
     NewPtrPHI->addIncoming(CI, IncomingBB);
   }
 
   // The PtrToCast + IntToPtr will be simplified later
   return CastInst::CreateBitOrPointerCast(NewPtrPHI,
                                           IntToPtr->getOperand(0)->getType());
 }
 
+/// If we have something like phi [insertvalue(a,b,0), insertvalue(c,d,0)],
+/// turn this into a phi[a,c] and phi[b,d] and a single insertvalue.
+Instruction *
+InstCombinerImpl::foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN) {
+  auto *FirstIVI = cast<InsertValueInst>(PN.getIncomingValue(0));
+
+  // Scan to see if all operands are `insertvalue`'s with the same indicies,
+  // and all have a single use.
+  for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
+    auto *I = dyn_cast<InsertValueInst>(PN.getIncomingValue(i));
+    if (!I || !I->hasOneUse() || I->getIndices() != FirstIVI->getIndices())
+      return nullptr;
+  }
+
+  // For each operand of an `insertvalue`
+  std::array<PHINode *, 2> NewOperands;
+  for (int OpIdx : {0, 1}) {
+    auto *&NewOperand = NewOperands[OpIdx];
+    // Create a new PHI node to receive the values the operand has in each
+    // incoming basic block.
+    NewOperand = PHINode::Create(
+        FirstIVI->getOperand(OpIdx)->getType(), PN.getNumIncomingValues(),
+        FirstIVI->getOperand(OpIdx)->getName() + ".pn");
+    // And populate each operand's PHI with said values.
+    for (auto Incoming : zip(PN.blocks(), PN.incoming_values()))
+      NewOperand->addIncoming(
+          cast<InsertValueInst>(std::get<1>(Incoming))->getOperand(OpIdx),
+          std::get<0>(Incoming));
+    InsertNewInstBefore(NewOperand, PN);
+  }
+
+  // And finally, create `insertvalue` over the newly-formed PHI nodes.
+  auto *NewIVI = InsertValueInst::Create(NewOperands[0], NewOperands[1],
+                                         FirstIVI->getIndices(), PN.getName());
+
+  PHIArgMergedDebugLoc(NewIVI, PN);
+  ++NumPHIsOfInsertValues;
+  return NewIVI;
+}
+
 /// 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);
if (TI->isEHPad())
       return nullptr;
 
   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);
 
   // 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

 }
 
 ; The insertion of first element could have been split/hoisted into the predecessors.
 define { i32, i32 } @test9({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i1 %c) {
 ; CHECK-LABEL: @test9(
 ; 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:    [[I1:%.*]] = extractvalue { i32, i32 } [[AGG_LEFT]], 1
-; CHECK-NEXT:    [[I2:%.*]] = insertvalue { i32, i32 } undef, i32 [[I0]], 0
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I3:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT:%.*]], 0
-; CHECK-NEXT:    [[I4:%.*]] = extractvalue { i32, i32 } [[AGG_RIGHT]], 1
-; CHECK-NEXT:    [[I5:%.*]] = insertvalue { i32, i32 } undef, i32 [[I3]], 0
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[I6:%.*]] = phi { i32, i32 } [ [[I2]], [[LEFT]] ], [ [[I5]], [[RIGHT]] ]
-; CHECK-NEXT:    [[I7:%.*]] = phi i32 [ [[I1]], [[LEFT]] ], [ [[I4]], [[RIGHT]] ]
+; CHECK-NEXT:    [[I8_MERGED:%.*]] = phi { i32, i32 } [ [[AGG_RIGHT:%.*]], [[RIGHT]] ], [ [[AGG_LEFT:%.*]], [[LEFT]] ]
 ; CHECK-NEXT:    call void @baz()
-; CHECK-NEXT:    [[I8:%.*]] = insertvalue { i32, i32 } [[I6]], i32 [[I7]], 1
-; CHECK-NEXT:    ret { i32, i32 } [[I8]]
+; CHECK-NEXT:    ret { i32, i32 } [[I8_MERGED]]
 ;
 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-insertvalues.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 declare void @usei32i32agg({ i32, i32 })
 
 ; If we have a phi of insertvalues, we can sink it,
 ; Here, we only need a PHI for inserted values.
 define { i32, i32 } @test0({ i32, i32 } %agg, i32 %val_left, i32 %val_right, i1 %c) {
 ; CHECK-LABEL: @test0(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
-; CHECK-NEXT:    [[I0:%.*]] = insertvalue { i32, i32 } [[AGG:%.*]], i32 [[VAL_LEFT:%.*]], 0
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I1:%.*]] = insertvalue { i32, i32 } [[AGG]], i32 [[VAL_RIGHT:%.*]], 0
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[R:%.*]] = phi { i32, i32 } [ [[I0]], [[LEFT]] ], [ [[I1]], [[RIGHT]] ]
+; CHECK-NEXT:    [[VAL_LEFT_PN:%.*]] = phi i32 [ [[VAL_LEFT:%.*]], [[LEFT]] ], [ [[VAL_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[R:%.*]] = insertvalue { i32, i32 } [[AGG:%.*]], i32 [[VAL_LEFT_PN]], 0
 ; CHECK-NEXT:    ret { i32, i32 } [[R]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = insertvalue { i32, i32 } %agg, i32 %val_left, 0
   br label %end

 }
 
 ; Here, we only need a PHI for base aggregate
 define { i32, i32 } @test4({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i32 %val, i1 %c) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
-; CHECK-NEXT:    [[I0:%.*]] = insertvalue { i32, i32 } [[AGG_LEFT:%.*]], i32 [[VAL:%.*]], 0
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I1:%.*]] = insertvalue { i32, i32 } [[AGG_RIGHT:%.*]], i32 [[VAL]], 0
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[R:%.*]] = phi { i32, i32 } [ [[I0]], [[LEFT]] ], [ [[I1]], [[RIGHT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[R:%.*]] = insertvalue { i32, i32 } [[AGG_LEFT_PN]], i32 [[VAL:%.*]], 0
 ; CHECK-NEXT:    ret { i32, i32 } [[R]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = insertvalue { i32, i32 } %agg_left, i32 %val, 0
   br label %end
 
 right:
   %i1 = insertvalue { i32, i32 } %agg_right, i32 %val, 0
   br label %end
 
 end:
   %r = phi { i32, i32 } [ %i0, %left ], [ %i1, %right ]
   ret { i32, i32 } %r
 }
 
 ; Here, we need a PHI for both the base and the inserted value
 define { i32, i32 } @test5({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i32 %val_left, i32 %val_right, i1 %c) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
-; CHECK-NEXT:    [[I0:%.*]] = insertvalue { i32, i32 } [[AGG_LEFT:%.*]], i32 [[VAL_LEFT:%.*]], 0
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I1:%.*]] = insertvalue { i32, i32 } [[AGG_RIGHT:%.*]], i32 [[VAL_RIGHT:%.*]], 0
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[R:%.*]] = phi { i32, i32 } [ [[I0]], [[LEFT]] ], [ [[I1]], [[RIGHT]] ]
+; CHECK-NEXT:    [[AGG_LEFT_PN:%.*]] = phi { i32, i32 } [ [[AGG_LEFT:%.*]], [[LEFT]] ], [ [[AGG_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[VAL_LEFT_PN:%.*]] = phi i32 [ [[VAL_LEFT:%.*]], [[LEFT]] ], [ [[VAL_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[R:%.*]] = insertvalue { i32, i32 } [[AGG_LEFT_PN]], i32 [[VAL_LEFT_PN]], 0
 ; CHECK-NEXT:    ret { i32, i32 } [[R]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = insertvalue { i32, i32 } %agg_left, i32 %val_left, 0
   br label %end

 }
 
 ; More complex aggregates are fine, too, as long as indicies match.
 define {{ i32, i32 }, { i32, i32 }} @test7({{ i32, i32 }, { i32, i32 }} %agg, i32 %val_left, i32 %val_right, i1 %c) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LEFT:%.*]], label [[RIGHT:%.*]]
 ; CHECK:       left:
-; CHECK-NEXT:    [[I0:%.*]] = insertvalue { { i32, i32 }, { i32, i32 } } [[AGG:%.*]], i32 [[VAL_LEFT:%.*]], 0, 0
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       right:
-; CHECK-NEXT:    [[I1:%.*]] = insertvalue { { i32, i32 }, { i32, i32 } } [[AGG]], i32 [[VAL_RIGHT:%.*]], 0, 0
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[R:%.*]] = phi { { i32, i32 }, { i32, i32 } } [ [[I0]], [[LEFT]] ], [ [[I1]], [[RIGHT]] ]
+; CHECK-NEXT:    [[VAL_LEFT_PN:%.*]] = phi i32 [ [[VAL_LEFT:%.*]], [[LEFT]] ], [ [[VAL_RIGHT:%.*]], [[RIGHT]] ]
+; CHECK-NEXT:    [[R:%.*]] = insertvalue { { i32, i32 }, { i32, i32 } } [[AGG:%.*]], i32 [[VAL_LEFT_PN]], 0, 0
 ; CHECK-NEXT:    ret { { i32, i32 }, { i32, i32 } } [[R]]
 ;
 entry:
   br i1 %c, label %left, label %right
 
 left:
   %i0 = insertvalue {{ i32, i32 }, { i32, i32 }} %agg, i32 %val_left, 0, 0
   br label %end