Index: llvm/include/llvm/IR/Dominators.h =================================================================== --- llvm/include/llvm/IR/Dominators.h +++ llvm/include/llvm/IR/Dominators.h @@ -172,6 +172,8 @@ /// never dominate the use. bool dominates(const BasicBlockEdge &BBE, const Use &U) const; bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; + /// Returns true if edge \p BBE1 dominates edge \p BBE2. + bool dominates(const BasicBlockEdge &BBE1, const BasicBlockEdge &BBE2) const; // Ensure base class overloads are visible. using Base::isReachableFromEntry; Index: llvm/lib/IR/Dominators.cpp =================================================================== --- llvm/lib/IR/Dominators.cpp +++ llvm/lib/IR/Dominators.cpp @@ -316,6 +316,14 @@ return isReachableFromEntry(I->getParent()); } +// Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2. +bool DominatorTree::dominates(const BasicBlockEdge &BBE1, + const BasicBlockEdge &BBE2) const { + if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd()) + return true; + return dominates(BBE1, BBE2.getStart()); +} + //===----------------------------------------------------------------------===// // DominatorTreeAnalysis and related pass implementations //===----------------------------------------------------------------------===// Index: llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -1129,6 +1129,76 @@ return replaceInstUsesWith(FirstPhi, Undef); } +static Value *SimplifyUsingControlFlow(InstCombiner &Self, PHINode &PN, + const DominatorTree &DT) { + // Simplify the following patterns: + // if (cond) + // / \ + // ... ... + // \ / + // phi [true] [false] + if (!PN.getType()->isIntegerTy(1)) + return nullptr; + + // TODO: This can be generalized for more than 2 inputs, but it will take + // more sophisticated dominance checks. + if (PN.getNumOperands() != 2) + return nullptr; + + // Make sure all inputs are constants. + if (!all_of(PN.operands(), [](Value *V) { return isa(V); })) + return nullptr; + + assert(PN.getOperand(0) != PN.getOperand(1) && + "Should have been simplified away!"); + + BasicBlock *BB = PN.getParent(); + // Do not bother with unreachable instructions. + if (!DT.isReachableFromEntry(BB)) + return nullptr; + + BasicBlock *TruePred = nullptr, *FalsePred = nullptr; + for (auto *Pred : predecessors(BB)) { + auto *Input = cast(PN.getIncomingValueForBlock(Pred)); + if (Input->isAllOnesValue()) + TruePred = Pred; + else + FalsePred = Pred; + } + assert(TruePred && FalsePred && "Must be!"); + + // Check which edge of the dominator dominates the true input. If it is the + // false edge, we should invert the condition. + auto *IDom = DT.getNode(BB)->getIDom()->getBlock(); + auto *BI = dyn_cast(IDom->getTerminator()); + if (!BI || BI->isUnconditional()) + return nullptr; + + // Check that edges outgoing from the idom's terminators dominate respective + // inputs of the Phi. + BasicBlockEdge TrueOutEdge(IDom, BI->getSuccessor(0)); + BasicBlockEdge FalseOutEdge(IDom, BI->getSuccessor(1)); + + BasicBlockEdge TrueIncEdge(TruePred, BB); + BasicBlockEdge FalseIncEdge(FalsePred, BB); + + auto *Cond = BI->getCondition(); + if (DT.dominates(TrueOutEdge, TrueIncEdge) && + DT.dominates(FalseOutEdge, FalseIncEdge)) + // This Phi is actually equivalent to branching condition of IDom. + return Cond; + else if (DT.dominates(TrueOutEdge, FalseIncEdge) && + DT.dominates(FalseOutEdge, TrueIncEdge)) { + // This Phi is actually opposite to branching condition of IDom. We invert + // the condition that will potentially open up some opportunities for + // sinking. + Self.Builder.SetInsertPoint(BB->getFirstNonPHI()); + return Self.Builder.CreateNot(Cond); + } + + return nullptr; +} + // PHINode simplification // Instruction *InstCombiner::visitPHINode(PHINode &PN) { @@ -1276,5 +1346,9 @@ if (Instruction *Res = SliceUpIllegalIntegerPHI(PN)) return Res; + // Try to simplify this Phi using knowledge of control flow. + if (Value *V = SimplifyUsingControlFlow(*this, PN, DT)) + return replaceInstUsesWith(PN, V); + return nullptr; } Index: llvm/test/Transforms/CallSiteSplitting/callsite-split.ll =================================================================== --- llvm/test/Transforms/CallSiteSplitting/callsite-split.ll +++ llvm/test/Transforms/CallSiteSplitting/callsite-split.ll @@ -73,9 +73,9 @@ ;CHECK: call void @dummy4() ;CHECK-LABEL: NextCond.split: ;CHECK: call void @dummy3() -;CheCK-LABEL: CallSiteBB: -;CHECK: %phi.call = phi i1 [ true, %NextCond.split ], [ false, %Top.split ] -;CHECK: call void @foo(i1 %phi.call) +;CHECK-LABEL: CallSiteBB: +;CHECK: [[NEG:%.*]] = xor i1 %tobool1, true +;CHECK: call void @foo(i1 [[NEG]]) define void @caller2(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt, %struct.bitmap* %c_elt) { entry: br label %Top Index: llvm/test/Transforms/InstCombine/icmp-constant-phi.ll =================================================================== --- llvm/test/Transforms/InstCombine/icmp-constant-phi.ll +++ llvm/test/Transforms/InstCombine/icmp-constant-phi.ll @@ -11,10 +11,10 @@ ; CHECK: if.false: ; CHECK-NEXT: br label [[MERGE]] ; CHECK: merge: -; CHECK-NEXT: [[COMPARE:%.*]] = phi i1 [ true, [[IF_FALSE]] ], [ false, [[IF_TRUE]] ] ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: ret i1 [[COMPARE]] +; CHECK-NEXT: [[TMP0:%.*]] = xor i1 [[COND]], true +; CHECK-NEXT: ret i1 [[TMP0]] ; entry: br i1 %cond, label %if.true, label %if.false @@ -43,10 +43,9 @@ ; CHECK: if.false: ; CHECK-NEXT: br label [[MERGE]] ; CHECK: merge: -; CHECK-NEXT: [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ] ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: ret i1 [[COMPARE]] +; CHECK-NEXT: ret i1 [[COND]] ; entry: br i1 %cond, label %if.true, label %if.false @@ -106,10 +105,9 @@ ; CHECK: if.false: ; CHECK-NEXT: br label [[MERGE]] ; CHECK: merge: -; CHECK-NEXT: [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ] ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: ret i1 [[COMPARE]] +; CHECK-NEXT: ret i1 [[COND]] ; entry: br i1 %cond, label %if.true, label %if.false Index: llvm/test/Transforms/InstCombine/phi.ll =================================================================== --- llvm/test/Transforms/InstCombine/phi.ll +++ llvm/test/Transforms/InstCombine/phi.ll @@ -416,10 +416,13 @@ bb2: ; preds = %bb1, %entry %cond = phi i1 [ true, %bb1 ], [ false, %entry ] ; [#uses=1] -; CHECK-NOT: %val = phi i32 [ %0, %bb1 ], [ 0, %entry ] +; TODO: Can be further optimized by removing select. +; CHECK-NOT: %cond +; CHECK: %val = phi i32 [ %0, %bb1 ], [ 0, %entry ] +; CHECK: %res = select i1 %a, i32 %val, i32 0 %val = phi i32 [ %0, %bb1 ], [ 0, %entry ] ; [#uses=1] %res = select i1 %cond, i32 %val, i32 0 ; [#uses=1] -; CHECK: ret i32 %cond +; CHECK: ret i32 %res ret i32 %res } Index: llvm/test/Transforms/InstCombine/select.ll =================================================================== --- llvm/test/Transforms/InstCombine/select.ll +++ llvm/test/Transforms/InstCombine/select.ll @@ -448,8 +448,8 @@ ; CHECK: jump: ; CHECK-NEXT: br label [[RET]] ; CHECK: ret: -; CHECK-NEXT: [[A:%.*]] = phi i32 [ 10, [[JUMP]] ], [ 20, [[ENTRY:%.*]] ] -; CHECK-NEXT: ret i32 [[A]] +; CHECK-NEXT: [[B:%.*]] = select i1 [[C]], i32 10, i32 20 +; CHECK-NEXT: ret i32 [[B]] ; entry: br i1 %c, label %jump, label %ret @@ -468,8 +468,8 @@ ; CHECK: jump: ; CHECK-NEXT: br label [[RET]] ; CHECK: ret: -; CHECK-NEXT: [[A:%.*]] = phi i32 [ 20, [[ENTRY:%.*]] ], [ 10, [[JUMP]] ] -; CHECK-NEXT: ret i32 [[A]] +; CHECK-NEXT: [[B:%.*]] = select i1 [[COND]], i32 10, i32 20 +; CHECK-NEXT: ret i32 [[B]] ; entry: br i1 %cond, label %jump, label %ret @@ -489,8 +489,8 @@ ; CHECK: jump: ; CHECK-NEXT: br label [[RET]] ; CHECK: ret: -; CHECK-NEXT: [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: ret i32 [[P]] +; CHECK-NEXT: [[S:%.*]] = select i1 [[C]], i32 [[A:%.*]], i32 [[B:%.*]] +; CHECK-NEXT: ret i32 [[S]] ; entry: br i1 %c, label %jump, label %ret @@ -509,8 +509,9 @@ ; CHECK: jump: ; CHECK-NEXT: br label [[RET]] ; CHECK: ret: -; CHECK-NEXT: [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: ret i32 [[P]] +; CHECK-NEXT: [[C:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ] +; CHECK-NEXT: [[S:%.*]] = select i1 [[COND]], i32 [[A]], i32 [[C]] +; CHECK-NEXT: ret i32 [[S]] ; entry: br i1 %cond, label %jump, label %ret @@ -530,10 +531,11 @@ ; CHECK: jump: ; CHECK-NEXT: br label [[RET]] ; CHECK: ret: -; CHECK-NEXT: [[P:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ] +; CHECK-NEXT: [[C:%.*]] = phi i32 [ [[A:%.*]], [[JUMP]] ], [ [[B:%.*]], [[ENTRY:%.*]] ] ; CHECK-NEXT: br label [[NEXT:%.*]] ; CHECK: next: -; CHECK-NEXT: ret i32 [[P]] +; CHECK-NEXT: [[S:%.*]] = select i1 [[COND]], i32 [[A]], i32 [[C]] +; CHECK-NEXT: ret i32 [[S]] ; entry: br i1 %cond, label %jump, label %ret Index: llvm/test/Transforms/InstCombine/simple_phi_condition.ll =================================================================== --- llvm/test/Transforms/InstCombine/simple_phi_condition.ll +++ llvm/test/Transforms/InstCombine/simple_phi_condition.ll @@ -12,8 +12,7 @@ ; CHECK: if.false: ; CHECK-NEXT: br label [[MERGE]] ; CHECK: merge: -; CHECK-NEXT: [[RET:%.*]] = phi i1 [ true, [[IF_TRUE]] ], [ false, [[IF_FALSE]] ] -; CHECK-NEXT: ret i1 [[RET]] +; CHECK-NEXT: ret i1 [[COND]] ; entry: br i1 %cond, label %if.true, label %if.false @@ -39,8 +38,8 @@ ; CHECK: if.false: ; CHECK-NEXT: br label [[MERGE]] ; CHECK: merge: -; CHECK-NEXT: [[RET:%.*]] = phi i1 [ false, [[IF_TRUE]] ], [ true, [[IF_FALSE]] ] -; CHECK-NEXT: ret i1 [[RET]] +; CHECK-NEXT: [[TMP0:%.*]] = xor i1 [[COND]], true +; CHECK-NEXT: ret i1 [[TMP0]] ; entry: br i1 %cond, label %if.true, label %if.false @@ -73,8 +72,7 @@ ; CHECK: if.false: ; CHECK-NEXT: br label [[MERGE]] ; CHECK: merge: -; CHECK-NEXT: [[RET:%.*]] = phi i1 [ true, [[IF_TRUE_END]] ], [ false, [[IF_FALSE]] ] -; CHECK-NEXT: ret i1 [[RET]] +; CHECK-NEXT: ret i1 [[COND]] ; entry: br i1 %cond, label %if.true, label %if.false @@ -116,8 +114,8 @@ ; CHECK: if.false: ; CHECK-NEXT: br label [[MERGE]] ; CHECK: merge: -; CHECK-NEXT: [[RET:%.*]] = phi i1 [ false, [[IF_TRUE_END]] ], [ true, [[IF_FALSE]] ] -; CHECK-NEXT: ret i1 [[RET]] +; CHECK-NEXT: [[TMP0:%.*]] = xor i1 [[COND]], true +; CHECK-NEXT: ret i1 [[TMP0]] ; entry: br i1 %cond, label %if.true, label %if.false Index: llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll =================================================================== --- llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll +++ llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll @@ -40,7 +40,7 @@ ; ASSUMPTIONS-ON-LABEL: @caller1( ; ASSUMPTIONS-ON-NEXT: br i1 [[C:%.*]], label [[TRUE1:%.*]], label [[FALSE1:%.*]] ; ASSUMPTIONS-ON: true1: -; ASSUMPTIONS-ON-NEXT: [[C_PR:%.*]] = phi i1 [ false, [[FALSE1]] ], [ true, [[TMP0:%.*]] ] +; ASSUMPTIONS-ON-NEXT: [[C_PR:%.*]] = phi i1 [ [[C]], [[FALSE1]] ], [ true, [[TMP0:%.*]] ] ; ASSUMPTIONS-ON-NEXT: [[PTRINT:%.*]] = ptrtoint i64* [[PTR:%.*]] to i64 ; ASSUMPTIONS-ON-NEXT: [[MASKEDPTR:%.*]] = and i64 [[PTRINT]], 7 ; ASSUMPTIONS-ON-NEXT: [[MASKCOND:%.*]] = icmp eq i64 [[MASKEDPTR]], 0 Index: llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll =================================================================== --- llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll +++ llvm/test/Transforms/PhaseOrdering/simplifycfg-options.ll @@ -18,16 +18,16 @@ ; ALL-NEXT: call void @foo() ; ALL-NEXT: br label [[IF_END]] ; ALL: if.end: -; ALL-NEXT: [[CHANGED_1_OFF0:%.*]] = phi i1 [ true, [[IF_THEN]] ], [ false, [[ENTRY:%.*]] ] -; ALL-NEXT: [[TMP1:%.*]] = load i32, i32* [[C]], align 4 -; ALL-NEXT: [[CMP_1:%.*]] = icmp eq i32 [[OR]], [[TMP1]] +; ALL-NEXT: [[TMP1:%.*]] = xor i1 [[CMP]], true +; ALL-NEXT: [[TMP2:%.*]] = load i32, i32* [[C]], align 4 +; ALL-NEXT: [[CMP_1:%.*]] = icmp eq i32 [[OR]], [[TMP2]] ; ALL-NEXT: br i1 [[CMP_1]], label [[IF_END_1:%.*]], label [[IF_THEN_1:%.*]] ; ALL: if.then.1: ; ALL-NEXT: store i32 [[OR]], i32* [[C]], align 4 ; ALL-NEXT: call void @foo() ; ALL-NEXT: br label [[IF_END_1]] ; ALL: if.end.1: -; ALL-NEXT: [[CHANGED_1_OFF0_1:%.*]] = phi i1 [ true, [[IF_THEN_1]] ], [ [[CHANGED_1_OFF0]], [[IF_END]] ] +; ALL-NEXT: [[CHANGED_1_OFF0_1:%.*]] = phi i1 [ true, [[IF_THEN_1]] ], [ [[TMP1]], [[IF_END]] ] ; ALL-NEXT: ret i1 [[CHANGED_1_OFF0_1]] ; entry: