Index: lib/Transforms/InstCombine/InstCombineInternal.h =================================================================== --- lib/Transforms/InstCombine/InstCombineInternal.h +++ lib/Transforms/InstCombine/InstCombineInternal.h @@ -701,6 +701,7 @@ Instruction *FoldPHIArgGEPIntoPHI(PHINode &PN); Instruction *FoldPHIArgLoadIntoPHI(PHINode &PN); Instruction *FoldPHIArgZextsIntoPHI(PHINode &PN); + Instruction *FoldPHIArgOrIntoPHI(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 Index: lib/Transforms/InstCombine/InstCombinePHI.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombinePHI.cpp +++ lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -635,6 +635,87 @@ return NewLI; } +// FoldPHIArgOrIntoPHI finds a phi node, which has OR instruction +// as an incoming value and AND instruction as its use. +// If the OR and AND instructions take the same operand +// as (%A OR %B) AND %B then replace the incoming value by %B. +// For example, +// BB1: +// %or = or i64 %val, 1 +// br %BB2 +// BB2: +// %phi = phi i64 [ %or, %BB1 ], ... # -> phi i64 [ 1, %BB1 ], ... +// %and = and i64 %phi, 1 +// This optimization allows jump threading pass to find the opportunity +// in method call whose return value is std::pair. +Instruction *InstCombiner::FoldPHIArgOrIntoPHI(PHINode &Phi) { + if (!Phi.getType()->isIntegerTy() || + Phi.getType()->getPrimitiveSizeInBits() != 64) + return nullptr; + + Instruction *rc = nullptr; + for (User *User : Phi.users()) { + // Try to find ((%A OR %B) AND %B) code sequence over Phi. + Value *UserVal = nullptr; + if (!match(User, m_And(m_Specific(&Phi), m_Value(UserVal)))) + continue; + + auto IsEligible = [&](Value *V) { + return match(V, m_Or(m_Value(), m_Specific(UserVal))); + }; + if (llvm::none_of(Phi.incoming_values(), IsEligible)) + continue; + + PHINode* NewPhi = Φ + if (!Phi.hasOneUse()) { + // When Phi is used by other instruction, we need to create a new phi + // node for this AND instruction. To avoid increasing total code size, + // we create a new phi if the AND can be eliminated. + // So far, we do this when all incoming OR are used to mix two 32-bit + // integers, e.g. (Shl(x, 32) OR ZExt(y)), and AND have a constant mask + // to extract bits only from one of the mixed integers. For such case, + // the AND instruction can be eliminated later by SimplifyDemandedBits. + if (!isa(UserVal)) continue; + + // If the mask for the AND instruction has one in both high and low + // 32-bit, we cannot guarantee that the AND can be eliminated. + uint64_t Imm = dyn_cast(UserVal)->getZExtValue(); + if ((Imm & 0xFFFFFFFFuL) != 0 && (Imm >> 32) != 0) continue; + + const Constant *CI32 = ConstantInt::get(User->getType(), 32); + // Return true if V mixes two 32 bit values by (Shl(x, 32) OR ZExt(y)) + auto IsConcat = [&](Value *V) { + Value *LowVal = nullptr; + return match(V, m_Or(m_Shl(m_Value(), m_Specific(CI32)), + m_ZExt(m_Value(LowVal)))) && + LowVal->getType()->getPrimitiveSizeInBits() == 32; + }; + auto IsEligibleOrConcat = [&](Value *V) { + return IsEligible(V) || IsConcat(V); + }; + if (!llvm::all_of(Phi.incoming_values(), IsEligibleOrConcat)) + continue; + + // If there is another use of the phi node, we create a new one + // for this AND instruction by cloning the original phi node. + NewPhi = cast(Phi.clone()); + InsertNewInstBefore(NewPhi, Phi); + cast(User)->setOperand(0, NewPhi); + } + + // We replace the incoming OR with UserVal. + for (unsigned Idx = 0; Idx < NewPhi->getNumIncomingValues(); Idx++) { + Value *V = NewPhi->getIncomingValue(Idx); + if (match(V, m_Or(m_Value(), m_Specific(UserVal)))) + NewPhi->setIncomingValue(Idx, UserVal); + } + + // Because we updated an operand, we return Phi. + rc = Φ + } + return rc; +} + /// 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. @@ -1130,6 +1211,9 @@ if (Instruction *Result = FoldPHIArgOpIntoPHI(PN)) return Result; + if (Instruction *Result = FoldPHIArgOrIntoPHI(PN)) + return Result; + // If this is a trivial cycle in the PHI node graph, remove it. Basically, if // this PHI only has a single use (a PHI), and if that PHI only has one use (a // PHI)... break the cycle. Index: test/Transforms/InstCombine/fold-or-phi.ll =================================================================== --- /dev/null +++ test/Transforms/InstCombine/fold-or-phi.ll @@ -0,0 +1,146 @@ +; RUN: opt < %s -instcombine -S | FileCheck %s + +define signext i64 @test1(i1 %f, i64 signext %a, i64 signext %b) { +; CHECK-LABEL: @test1 +; CHECK-LABEL: BB2 +; CHECK: [[PHI:%.*]] = phi i64 [ %a, %entry ], [ %b, %BB1 ] +; CHECK: and i64 [[PHI]], %b +entry: + br i1 %f, label %BB1, label %BB2 + +BB1: + %or = or i64 %a, %b + br label %BB2 + +BB2: + %phi = phi i64 [ %a, %entry ], [ %or, %BB1 ] + %and = and i64 %phi, %b + ret i64 %and +} + +define signext i64 @test2(i1 %f, i64 signext %a, i64 signext %b) { +; a test case for not creating a clone phi node to avoid code size bloat +; CHECK-LABEL: @test2 +; CHECK-LABEL: BB2 +; CHECK: [[NewPHI:%.*]] = phi i64 [ %b, %entry ], [ %or, %BB1 ] +entry: + br i1 %f, label %BB1, label %BB2 + +BB1: + %or = or i64 %a, 1 + br label %BB2 + +BB2: + %phi = phi i64 [ %b, %entry ], [ %or, %BB1 ] + %and = and i64 %phi, 1 + %add = add i64 %and, %phi + ret i64 %add +} + +define signext i32 @testBI(i32 signext %v) { +; Test with std::pair +; based on the following C++ code +; std::pair callee(int v) { +; int a = dummy(v); +; if (a) return std::make_pair(true, dummy(a)); +; else return std::make_pair(v < 0, v); +; } +; int func(int v) { +; std::pair rc = callee(v); +; if (rc.first) dummy(0); +; return rc.second; +; } + +; CHECK-LABEL: @testBI +; CHECK-LABEL: _ZL6calleei.exit +; CHECK: [[PHI:%.*]] = phi i1 [ false, %if.then.i ], [ [[V:%.*]], %if.else.i ] +; CHECK: br i1 [[PHI]], label %if.end, label %if.then +entry: + %call.i = call signext i32 @dummy(i32 signext %v) + %tobool.i = icmp eq i32 %call.i, 0 + br i1 %tobool.i, label %if.else.i, label %if.then.i + +if.then.i: ; preds = %entry + %call2.i = call signext i32 @dummy(i32 signext %call.i) + %retval.sroa.22.0.insert.ext.i.i = zext i32 %call2.i to i64 + %retval.sroa.22.0.insert.shift.i.i = shl nuw i64 %retval.sroa.22.0.insert.ext.i.i, 32 + %retval.sroa.0.0.insert.insert.i.i = or i64 %retval.sroa.22.0.insert.shift.i.i, 1 + br label %_ZL6calleei.exit + +if.else.i: ; preds = %entry + %.lobit.i = lshr i32 %v, 31 + %0 = zext i32 %.lobit.i to i64 + %retval.sroa.22.0.insert.ext.i8.i = zext i32 %v to i64 + %retval.sroa.22.0.insert.shift.i9.i = shl nuw i64 %retval.sroa.22.0.insert.ext.i8.i, 32 + %retval.sroa.0.0.insert.insert.i11.i = or i64 %retval.sroa.22.0.insert.shift.i9.i, %0 + br label %_ZL6calleei.exit + +_ZL6calleei.exit: ; preds = %if.then.i, %if.else.i + %retval.sroa.0.0.i = phi i64 [ %retval.sroa.0.0.insert.insert.i.i, %if.then.i ], [ %retval.sroa.0.0.insert.insert.i11.i, %if.else.i ] + %rc.sroa.43.0.extract.shift = lshr i64 %retval.sroa.0.0.i, 32 + %rc.sroa.43.0.extract.trunc = trunc i64 %rc.sroa.43.0.extract.shift to i32 + %1 = and i64 %retval.sroa.0.0.i, 1 + %tobool = icmp eq i64 %1, 0 + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %_ZL6calleei.exit + %call1 = call signext i32 @dummy(i32 signext 0) + br label %if.end + +if.end: ; preds = %_ZL6calleei.exit, %if.then + ret i32 %rc.sroa.43.0.extract.trunc +} + +define signext i32 @testIB(i32 signext %v) { +; Test with std::pair +; based on the following C++ code +; std::pair callee(int v) { +; int a = dummy(v); +; if (a) return std::make_pair(dummy(v), true); +; else return std::make_pair(v, v < 0); +; } +; int func(int v) { +; std::pair rc = callee(v); +; if (rc.second) dummy(0); +; return rc.first; +; } + +; CHECK-LABEL: @testIB +; CHECK-LABEL: _ZL6calleei.exit +; CHECK: [[PHI:%.*]] = phi i1 [ false, %if.then.i ], [ [[V:%.*]], %if.else.i ] +; CHECK: br i1 [[PHI]], label %if.end, label %if.then +entry: + %call.i = call signext i32 @dummy(i32 signext %v) + %tobool.i = icmp eq i32 %call.i, 0 + br i1 %tobool.i, label %if.else.i, label %if.then.i + +if.then.i: ; preds = %entry + %call1.i = call signext i32 @dummy(i32 signext %v) + %retval.sroa.0.0.insert.ext.i.i = zext i32 %call1.i to i64 + %retval.sroa.0.0.insert.insert.i.i = or i64 %retval.sroa.0.0.insert.ext.i.i, 4294967296 + br label %_ZL6calleei.exit + +if.else.i: ; preds = %entry + %.lobit.i = lshr i32 %v, 31 + %0 = zext i32 %.lobit.i to i64 + %retval.sroa.2.0.insert.shift.i8.i = shl nuw nsw i64 %0, 32 + %retval.sroa.0.0.insert.ext.i9.i = zext i32 %v to i64 + %retval.sroa.0.0.insert.insert.i10.i = or i64 %retval.sroa.2.0.insert.shift.i8.i, %retval.sroa.0.0.insert.ext.i9.i + br label %_ZL6calleei.exit + +_ZL6calleei.exit: ; preds = %if.then.i, %if.else.i + %retval.sroa.0.0.i = phi i64 [ %retval.sroa.0.0.insert.insert.i.i, %if.then.i ], [ %retval.sroa.0.0.insert.insert.i10.i, %if.else.i ] + %rc.sroa.0.0.extract.trunc = trunc i64 %retval.sroa.0.0.i to i32 + %1 = and i64 %retval.sroa.0.0.i, 4294967296 + %tobool = icmp eq i64 %1, 0 + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %_ZL6calleei.exit + %call1 = call signext i32 @dummy(i32 signext 0) + br label %if.end + +if.end: ; preds = %_ZL6calleei.exit, %if.then + ret i32 %rc.sroa.0.0.extract.trunc +} + +declare signext i32 @dummy(i32 signext %v)