From fa2392de5f49336bcc93bc2f45f7ab3c3b5b54f0 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Sun, 27 Sep 2015 20:34:31 +0000 Subject: [PATCH] [InstCombine] fold zexts and constants into a phi (PR24766) This is one step towards solving PR24766: https://llvm.org/bugs/show_bug.cgi?id=24766 We were not producing the same IR for these two C functions because the store to the temp bool causes extra zexts: #include bool switchy(char x1, char x2, char condition) { bool conditionMet = false; switch (condition) { case 0: conditionMet = (x1 == x2); break; case 1: conditionMet = (x1 <= x2); break; } return conditionMet; } bool switchy2(char x1, char x2, char condition) { switch (condition) { case 0: return (x1 == x2); case 1: return (x1 <= x2); } return false; } As noted in the code comments, this test case manages to avoid the more general existing phi optimizations where there are only 2 phi inputs or where there are no constant phi args mixed in with the casts ops. It seems like a corner case, but if we don't catch it, then I don't think we can get SimplifyCFG to further optimize towards the canonical form for this function shown in the bug report. Differential Revision: http://reviews.llvm.org/D12866 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@248689 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineInternal.h | 1 + lib/Transforms/InstCombine/InstCombinePHI.cpp | 69 ++++++++++ test/Transforms/InstCombine/phi.ll | 130 ++++++++++++++++++ 3 files changed, 200 insertions(+) diff --git a/lib/Transforms/InstCombine/InstCombineInternal.h b/lib/Transforms/InstCombine/InstCombineInternal.h index dbaa5a88ee3..9e58c7428bd 100644 --- a/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/lib/Transforms/InstCombine/InstCombineInternal.h @@ -545,6 +545,7 @@ private: Instruction *FoldPHIArgBinOpIntoPHI(PHINode &PN); Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN); Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN); + Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN); Instruction *OptAndOp(Instruction *Op, ConstantInt *OpRHS, ConstantInt *AndRHS, BinaryOperator &TheAnd); diff --git a/lib/Transforms/InstCombine/InstCombinePHI.cpp b/lib/Transforms/InstCombine/InstCombinePHI.cpp index 86d5f03f532..b035dd605aa 100644 --- a/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ b/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -394,7 +394,73 @@ Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) { return NewLI; } +/// TODO: This function could handle other cast types, but then it might +/// require special-casing a cast from the 'i1' type. See the comment in +/// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types. +Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) { + // Early exit for the common case of a phi with two operands. These are + // handled elsewhere. See the comment below where we check the count of zexts + // and constants for more details. + unsigned NumIncomingValues = Phi.getNumIncomingValues(); + if (NumIncomingValues < 3) + return nullptr; + // Find the narrower type specified by the first zext. + Type *NarrowType = nullptr; + for (Value *V : Phi.incoming_values()) { + if (auto *Zext = dyn_cast(V)) { + NarrowType = Zext->getSrcTy(); + break; + } + } + if (!NarrowType) + return nullptr; + + // Walk the phi operands checking that we only have zexts or constants that + // we can shrink for free. Store the new operands for the new phi. + SmallVector NewIncoming; + unsigned NumZexts = 0; + unsigned NumConsts = 0; + for (Value *V : Phi.incoming_values()) { + if (auto *Zext = dyn_cast(V)) { + // All zexts must be identical and have one use. + if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUse()) + return nullptr; + NewIncoming.push_back(Zext->getOperand(0)); + NumZexts++; + } else if (auto *C = dyn_cast(V)) { + // Make sure that constants can fit in the new type. + Constant *Trunc = ConstantExpr::getTrunc(C, NarrowType); + if (ConstantExpr::getZExt(Trunc, C->getType()) != C) + return nullptr; + NewIncoming.push_back(Trunc); + NumConsts++; + } else { + // If it's not a cast or a constant, bail out. + return nullptr; + } + } + + // The more common cases of a phi with no constant operands or just one + // variable operand are handled by FoldPHIArgOpIntoPHI() and FoldOpIntoPhi() + // respectively. FoldOpIntoPhi() wants to do the opposite transform that is + // performed here. It tries to replicate a cast in the phi operand's basic + // block to expose other folding opportunities. Thus, InstCombine will + // infinite loop without this check. + if (NumConsts == 0 || NumZexts < 2) + return nullptr; + + // All incoming values are zexts or constants that are safe to truncate. + // Create a new phi node of the narrow type, phi together all of the new + // operands, and zext the result back to the original type. + PHINode *NewPhi = PHINode::Create(NarrowType, NumIncomingValues, + Phi.getName() + ".shrunk"); + for (unsigned i = 0; i != NumIncomingValues; ++i) + NewPhi->addIncoming(NewIncoming[i], Phi.getIncomingBlock(i)); + + InsertNewInstBefore(NewPhi, Phi); + return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType()); +} /// If all operands to a PHI node are the same "unary" operator and they all are /// only used by the PHI, PHI together their inputs, and do the operation once, @@ -800,6 +866,9 @@ Instruction *InstCombiner::visitPHINode(PHINode &PN) { if (Value *V = SimplifyInstruction(&PN, DL, TLI, DT, AC)) return ReplaceInstUsesWith(PN, V); + if (Instruction *Result = FoldPHIArgZextsIntoPHI(PN)) + return Result; + // If all PHI operands are the same operation, pull them through the PHI, // reducing code size. if (isa(PN.getIncomingValue(0)) && diff --git a/test/Transforms/InstCombine/phi.ll b/test/Transforms/InstCombine/phi.ll index 54cc4cfe459..d0441d76d39 100644 --- a/test/Transforms/InstCombine/phi.ll +++ b/test/Transforms/InstCombine/phi.ll @@ -630,3 +630,133 @@ done: %y = phi i32 [ undef, %entry ] ret i32 %y } + +; We should be able to fold the zexts to the other side of the phi +; even though there's a constant value input to the phi. This is +; because we can shrink that constant to the smaller phi type. + +define i1 @PR24766(i8 %x1, i8 %x2, i8 %condition) { +entry: + %conv = sext i8 %condition to i32 + switch i32 %conv, label %epilog [ + i32 0, label %sw1 + i32 1, label %sw2 + ] + +sw1: + %cmp1 = icmp eq i8 %x1, %x2 + %frombool1 = zext i1 %cmp1 to i8 + br label %epilog + +sw2: + %cmp2 = icmp sle i8 %x1, %x2 + %frombool2 = zext i1 %cmp2 to i8 + br label %epilog + +epilog: + %conditionMet = phi i8 [ 0, %entry ], [ %frombool2, %sw2 ], [ %frombool1, %sw1 ] + %tobool = icmp ne i8 %conditionMet, 0 + ret i1 %tobool + +; CHECK-LABEL: @PR24766( +; CHECK: %[[RES:.*]] = phi i1 [ false, %entry ], [ %cmp2, %sw2 ], [ %cmp1, %sw1 ] +; CHECK-NEXT: ret i1 %[[RES]] +} + +; Same as above (a phi with more than 2 operands), but no constants + +define i1 @PR24766_no_constants(i8 %x1, i8 %x2, i8 %condition, i1 %another_condition) { +entry: + %frombool0 = zext i1 %another_condition to i8 + %conv = sext i8 %condition to i32 + switch i32 %conv, label %epilog [ + i32 0, label %sw1 + i32 1, label %sw2 + ] + +sw1: + %cmp1 = icmp eq i8 %x1, %x2 + %frombool1 = zext i1 %cmp1 to i8 + br label %epilog + +sw2: + %cmp2 = icmp sle i8 %x1, %x2 + %frombool2 = zext i1 %cmp2 to i8 + br label %epilog + +epilog: + %conditionMet = phi i8 [ %frombool0, %entry ], [ %frombool2, %sw2 ], [ %frombool1, %sw1 ] + %tobool = icmp ne i8 %conditionMet, 0 + ret i1 %tobool + +; CHECK-LABEL: @PR24766_no_constants( +; CHECK: %[[RES:.*]] = phi i1 [ %another_condition, %entry ], [ %cmp2, %sw2 ], [ %cmp1, %sw1 ] +; CHECK-NEXT: ret i1 %[[RES]] +} + +; Same as above (a phi with more than 2 operands), but two constants + +define i1 @PR24766_two_constants(i8 %x1, i8 %x2, i8 %condition) { +entry: + %conv = sext i8 %condition to i32 + switch i32 %conv, label %epilog [ + i32 0, label %sw1 + i32 1, label %sw2 + ] + +sw1: + %cmp1 = icmp eq i8 %x1, %x2 + %frombool1 = zext i1 %cmp1 to i8 + br label %epilog + +sw2: + %cmp2 = icmp sle i8 %x1, %x2 + %frombool2 = zext i1 %cmp2 to i8 + br label %epilog + +epilog: + %conditionMet = phi i8 [ 0, %entry ], [ 1, %sw2 ], [ %frombool1, %sw1 ] + %tobool = icmp ne i8 %conditionMet, 0 + ret i1 %tobool + +; CHECK-LABEL: @PR24766_two_constants( +; CHECK: %[[RES:.*]] = phi i1 [ false, %entry ], [ true, %sw2 ], [ %cmp1, %sw1 ] +; CHECK-NEXT: ret i1 %[[RES]] +} + +; Same as above (a phi with more than 2 operands), but two constants and two variables + +define i1 @PR24766_two_constants_two_var(i8 %x1, i8 %x2, i8 %condition) { +entry: + %conv = sext i8 %condition to i32 + switch i32 %conv, label %epilog [ + i32 0, label %sw1 + i32 1, label %sw2 + i32 2, label %sw3 + ] + +sw1: + %cmp1 = icmp eq i8 %x1, %x2 + %frombool1 = zext i1 %cmp1 to i8 + br label %epilog + +sw2: + %cmp2 = icmp sle i8 %x1, %x2 + %frombool2 = zext i1 %cmp2 to i8 + br label %epilog + +sw3: + %cmp3 = icmp sge i8 %x1, %x2 + %frombool3 = zext i1 %cmp3 to i8 + br label %epilog + +epilog: + %conditionMet = phi i8 [ 0, %entry ], [ %frombool2, %sw2 ], [ %frombool1, %sw1 ], [ 1, %sw3 ] + %tobool = icmp ne i8 %conditionMet, 0 + ret i1 %tobool + +; CHECK-LABEL: @PR24766_two_constants_two_var( +; CHECK: %[[RES:.*]] = phi i1 [ false, %entry ], [ %cmp2, %sw2 ], [ %cmp1, %sw1 ], [ true, %sw3 ] +; CHECK-NEXT: ret i1 %[[RES]] +} + -- 2.34.1