Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineInternal.h @@ -545,6 +545,7 @@ 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); Index: llvm/trunk/lib/Transforms/InstCombine/InstCombinePHI.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -394,7 +394,73 @@ 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 @@ 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)) && Index: llvm/trunk/test/Transforms/InstCombine/phi.ll =================================================================== --- llvm/trunk/test/Transforms/InstCombine/phi.ll +++ llvm/trunk/test/Transforms/InstCombine/phi.ll @@ -630,3 +630,133 @@ %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]] +} +