From cdd339c568fdd0fa2494745d0f661c4a0647c13c Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Tue, 25 Aug 2020 10:25:34 +0300 Subject: [PATCH] [InstCombine] PHI-of-insertvalues -> insertvalue-of-PHI's MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 believe 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.NumPHIsOfInsertValues | 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% | ``` Reviewed By: spatel Differential Revision: https://reviews.llvm.org/D86306 --- .../Transforms/InstCombine/InstCombineInternal.h | 1 + llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp | 47 ++++++++++++++++++++++ .../phi-aware-aggregate-reconstruction.ll | 12 +----- .../Transforms/InstCombine/phi-of-insertvalues.ll | 21 +++++----- 4 files changed, 59 insertions(+), 22 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h index 5e94ef6..e5fe993 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h @@ -617,6 +617,7 @@ public: /// 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); diff --git a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp index 97cf54e9..269b4d5 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -13,12 +13,14 @@ #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; @@ -28,6 +30,9 @@ static cl::opt 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. @@ -291,6 +296,46 @@ Instruction *InstCombinerImpl::foldIntegerTypedPHI(PHINode &PN) { 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(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(PN.getIncomingValue(i)); + if (!I || !I->hasOneUse() || I->getIndices() != FirstIVI->getIndices()) + return nullptr; + } + + // For each operand of an `insertvalue` + std::array 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(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) { @@ -741,6 +786,8 @@ Instruction *InstCombinerImpl::foldPHIArgOpIntoPHI(PHINode &PN) { return foldPHIArgGEPIntoPHI(PN); if (isa(FirstInst)) return foldPHIArgLoadIntoPHI(PN); + if (isa(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 diff --git a/llvm/test/Transforms/InstCombine/phi-aware-aggregate-reconstruction.ll b/llvm/test/Transforms/InstCombine/phi-aware-aggregate-reconstruction.ll index 78c75c3..b97b408 100644 --- a/llvm/test/Transforms/InstCombine/phi-aware-aggregate-reconstruction.ll +++ b/llvm/test/Transforms/InstCombine/phi-aware-aggregate-reconstruction.ll @@ -484,23 +484,15 @@ define { i32, i32 } @test9({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i1 % ; 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 diff --git a/llvm/test/Transforms/InstCombine/phi-of-insertvalues.ll b/llvm/test/Transforms/InstCombine/phi-of-insertvalues.ll index 787a7e6..00e81ad 100644 --- a/llvm/test/Transforms/InstCombine/phi-of-insertvalues.ll +++ b/llvm/test/Transforms/InstCombine/phi-of-insertvalues.ll @@ -10,13 +10,12 @@ define { i32, i32 } @test0({ i32, i32 } %agg, i32 %val_left, i32 %val_right, i1 ; 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: @@ -138,13 +137,12 @@ define { i32, i32 } @test4({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i32 ; 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: @@ -169,13 +167,13 @@ define { i32, i32 } @test5({ i32, i32 } %agg_left, { i32, i32 } %agg_right, i32 ; 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: @@ -231,13 +229,12 @@ define {{ i32, i32 }, { i32, i32 }} @test7({{ i32, i32 }, { i32, i32 }} %agg, i3 ; 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: -- 2.7.4