Index: llvm/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/lib/Transforms/Utils/Local.cpp +++ llvm/lib/Transforms/Utils/Local.cpp @@ -3053,31 +3053,26 @@ if (match(Condition, m_Not(m_Value(NotCondition)))) return NotCondition; - if (Instruction *Inst = dyn_cast(Condition)) { - // Third: Check all the users for an invert - BasicBlock *Parent = Inst->getParent(); - for (User *U : Condition->users()) - if (Instruction *I = dyn_cast(U)) - if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) - return I; - - // Last option: Create a new instruction - auto Inverted = BinaryOperator::CreateNot(Inst, ""); - if (isa(Inst)) { - // FIXME: This fails if the inversion is to be used in a - // subsequent PHINode in the same basic block. - Inverted->insertBefore(&*Parent->getFirstInsertionPt()); - } else { - Inverted->insertAfter(Inst); - } - return Inverted; - } - - if (Argument *Arg = dyn_cast(Condition)) { - BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock(); - return BinaryOperator::CreateNot(Condition, Arg->getName() + ".inv", - &*EntryBlock.getFirstInsertionPt()); - } - - llvm_unreachable("Unhandled condition to invert"); + BasicBlock *Parent = nullptr; + Instruction *Inst = dyn_cast(Condition); + if (Inst) + Parent = Inst->getParent(); + else if (Argument *Arg = dyn_cast(Condition)) + Parent = &Arg->getParent()->getEntryBlock(); + assert(Parent && "Unsupported condition to invert"); + + // Third: Check all the users for an invert + for (User *U : Condition->users()) + if (Instruction *I = dyn_cast(U)) + if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) + return I; + + // Last option: Create a new instruction + auto *Inverted = + BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv"); + if (Inst && !isa(Inst)) + Inverted->insertAfter(Inst); + else + Inverted->insertBefore(&*Parent->getFirstInsertionPt()); + return Inverted; } Index: llvm/test/Transforms/StructurizeCFG/bug36015.ll =================================================================== --- llvm/test/Transforms/StructurizeCFG/bug36015.ll +++ llvm/test/Transforms/StructurizeCFG/bug36015.ll @@ -18,7 +18,7 @@ br i1 %cond.inner, label %if, label %else ; CHECK: if: -; CHECK: %0 = xor i1 %cond.if, true +; CHECK: %cond.if.inv = xor i1 %cond.if, true ; CHECK: br label %Flow if: %ctr.if = add i32 %ctr.loop.inner, 1 @@ -27,12 +27,12 @@ br i1 %cond.if, label %loop.inner, label %exit ; CHECK: Flow: -; CHECK: %2 = phi i1 [ %0, %if ], [ true, %loop.inner ] -; CHECK: %3 = phi i1 [ false, %if ], [ true, %loop.inner ] -; CHECK: br i1 %2, label %Flow1, label %loop.inner +; CHECK: %1 = phi i1 [ %cond.if.inv, %if ], [ true, %loop.inner ] +; CHECK: %2 = phi i1 [ false, %if ], [ true, %loop.inner ] +; CHECK: br i1 %1, label %Flow1, label %loop.inner ; CHECK: Flow1: -; CHECK: br i1 %3, label %else, label %Flow2 +; CHECK: br i1 %2, label %else, label %Flow2 ; CHECK: else: ; CHECK: br label %Flow2 @@ -43,8 +43,8 @@ br i1 %cond.else, label %loop.outer, label %exit ; CHECK: Flow2: -; CHECK: %6 = phi i1 [ %4, %else ], [ true, %Flow1 ] -; CHECK: br i1 %6, label %exit, label %loop.outer +; CHECK: %4 = phi i1 [ %cond.else.inv, %else ], [ true, %Flow1 ] +; CHECK: br i1 %4, label %exit, label %loop.outer exit: ret void Index: llvm/test/Transforms/StructurizeCFG/loop-multiple-exits.ll =================================================================== --- llvm/test/Transforms/StructurizeCFG/loop-multiple-exits.ll +++ llvm/test/Transforms/StructurizeCFG/loop-multiple-exits.ll @@ -26,11 +26,11 @@ %arrayidx = getelementptr inbounds i32, i32 addrspace(1)* %out, i32 %i.0 store i32 %i.0, i32 addrspace(1)* %arrayidx, align 4 %cmp1 = icmp ugt i32 %i.0, %cond_b -; CHECK: br i1 %{{[0-9a-zA-Z_]+}}, label %for.inc, label %[[FLOW1:[0-9a-zA-Z_]+]] +; CHECK: br i1 %{{[0-9a-zA-Z_.]+}}, label %for.inc, label %[[FLOW1:[0-9a-zA-Z_]+]] br i1 %cmp1, label %for.end, label %for.inc ; CHECK: [[FLOW:[0-9a-zA-Z]+]]: -; CHECK: br i1 %{{[0-9a-zA-Z_]+}}, label %for.end, label %for.cond +; CHECK: br i1 %{{[0-9a-zA-Z_.]+}}, label %for.end, label %for.cond ; CHECK: for.inc: ; CHECK: br label %[[FLOW1]] Index: llvm/test/Transforms/StructurizeCFG/one-loop-multiple-backedges.ll =================================================================== --- llvm/test/Transforms/StructurizeCFG/one-loop-multiple-backedges.ll +++ llvm/test/Transforms/StructurizeCFG/one-loop-multiple-backedges.ll @@ -8,23 +8,23 @@ br label %bb3 ; CHECK: bb3: -; CHECK: %0 = xor i1 %tmp4, true -; CHECK: br i1 %0, label %bb5, label %Flow +; CHECK: %tmp4.inv = xor i1 %tmp4, true +; CHECK: br i1 %tmp4.inv, label %bb5, label %Flow bb3: ; preds = %bb7, %bb %tmp = phi i64 [ 0, %bb ], [ %tmp8, %bb7 ] %tmp4 = fcmp ult float %arg1, 3.500000e+00 br i1 %tmp4, label %bb7, label %bb5 ; CHECK: bb5: -; CHECK: %1 = xor i1 %tmp6, true +; CHECK: %tmp6.inv = xor i1 %tmp6, true ; CHECK: br label %Flow bb5: ; preds = %bb3 %tmp6 = fcmp olt float 0.000000e+00, %arg2 br i1 %tmp6, label %bb10, label %bb7 ; CHECK: Flow: -; CHECK: %2 = phi i1 [ %1, %bb5 ], [ %tmp4, %bb3 ] -; CHECK: br i1 %2, label %bb7, label %Flow1 +; CHECK: %0 = phi i1 [ %tmp6.inv, %bb5 ], [ %tmp4, %bb3 ] +; CHECK: br i1 %0, label %bb7, label %Flow1 ; CHECK: bb7: ; CHECK: br label %Flow1 @@ -34,8 +34,8 @@ br i1 %tmp9, label %bb3, label %bb10 ; CHECK: Flow1: -; CHECK: %6 = phi i1 [ %3, %bb7 ], [ true, %Flow ] -; CHECK: br i1 %6, label %bb10, label %bb3 +; CHECK: %3 = phi i1 [ %tmp9.inv, %bb7 ], [ true, %Flow ] +; CHECK: br i1 %3, label %bb10, label %bb3 ; CHECK: bb10: bb10: ; preds = %bb7, %bb5 Index: llvm/test/Transforms/StructurizeCFG/post-order-traversal-bug.ll =================================================================== --- llvm/test/Transforms/StructurizeCFG/post-order-traversal-bug.ll +++ llvm/test/Transforms/StructurizeCFG/post-order-traversal-bug.ll @@ -15,7 +15,7 @@ br label %for.body ; CHECK: for.body: -; CHECK: br i1 %{{[0-9]+}}, label %lor.lhs.false, label %Flow +; CHECK: br i1 %cmp1.inv, label %lor.lhs.false, label %Flow for.body: ; preds = %for.body.backedge, %entry %indvars.iv = phi i64 [ %indvars.iv.be, %for.body.backedge ], [ 1, %entry ] %best_val.027 = phi float [ %best_val.027.be, %for.body.backedge ], [ 5.000000e+01, %entry ] @@ -59,7 +59,7 @@ ; CHECK: br i1 %{{[0-9]}}, label %for.body.1, label %Flow2 ; CHECK: for.body.1: -; CHECK: br i1 %{{[0-9]+}}, label %for.body.6, label %Flow3 +; CHECK: br i1 %cmp1.5.inv, label %for.body.6, label %Flow3 for.body.1: ; preds = %if.then, %lor.lhs.false %best_val.233 = phi float [ %tmp5, %if.then ], [ %best_val.027, %lor.lhs.false ] %best_count.231 = phi i32 [ %sub4, %if.then ], [ %best_count.025, %lor.lhs.false ] Index: llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll =================================================================== --- llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll +++ llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll @@ -13,32 +13,32 @@ ; CHECK-NEXT: [[PRED11_INV:%.*]] = xor i1 [[PRED11:%.*]], true ; CHECK-NEXT: [[PRED12_INV:%.*]] = xor i1 [[PRED12:%.*]], true ; CHECK-NEXT: [[PRED13_INV:%.*]] = xor i1 [[PRED13:%.*]], true -; CHECK-NEXT: br i1 [[PRED0_INV]], label [[IF_THEN:%.*]], label [[FLOW18:%.*]] -; CHECK: Flow18: +; CHECK-NEXT: br i1 [[PRED0_INV]], label [[IF_THEN:%.*]], label [[FLOW19:%.*]] +; CHECK: Flow19: ; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ false, [[FLOW3:%.*]] ], [ true, [[ENTRY:%.*]] ] -; CHECK-NEXT: br i1 [[TMP0]], label [[IF_END:%.*]], label [[FLOW19:%.*]] +; CHECK-NEXT: br i1 [[TMP0]], label [[IF_END:%.*]], label [[FLOW20:%.*]] ; CHECK: if.end: -; CHECK-NEXT: br i1 [[PRED1_INV]], label [[IF_ELSE:%.*]], label [[FLOW17:%.*]] -; CHECK: Flow17: +; CHECK-NEXT: br i1 [[PRED1_INV]], label [[IF_ELSE:%.*]], label [[FLOW18:%.*]] +; CHECK: Flow18: ; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ false, [[IF_ELSE]] ], [ true, [[IF_END]] ] ; CHECK-NEXT: br i1 [[TMP1]], label [[IF_THEN7:%.*]], label [[IF_END16:%.*]] ; CHECK: if.then7: ; CHECK-NEXT: br label [[IF_END16]] ; CHECK: if.else: -; CHECK-NEXT: br label [[FLOW17]] -; CHECK: Flow19: +; CHECK-NEXT: br label [[FLOW18]] +; CHECK: Flow20: ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: if.end16: -; CHECK-NEXT: br i1 [[PRED2_INV]], label [[IF_THEN39:%.*]], label [[FLOW15:%.*]] -; CHECK: Flow15: +; CHECK-NEXT: br i1 [[PRED2_INV]], label [[IF_THEN39:%.*]], label [[FLOW16:%.*]] +; CHECK: Flow16: ; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ true, [[IF_END16]] ] -; CHECK-NEXT: br i1 [[TMP2]], label [[WHILE_COND_PREHEADER:%.*]], label [[FLOW16:%.*]] +; CHECK-NEXT: br i1 [[TMP2]], label [[WHILE_COND_PREHEADER:%.*]], label [[FLOW17:%.*]] ; CHECK: while.cond.preheader: ; CHECK-NEXT: br label [[WHILE_COND:%.*]] -; CHECK: Flow16: -; CHECK-NEXT: br label [[FLOW19]] +; CHECK: Flow17: +; CHECK-NEXT: br label [[FLOW20]] ; CHECK: while.cond: -; CHECK-NEXT: br i1 [[PRED3_INV]], label [[LOR_RHS:%.*]], label [[FLOW11:%.*]] +; CHECK-NEXT: br i1 [[PRED3_INV]], label [[LOR_RHS:%.*]], label [[FLOW12:%.*]] ; CHECK: Flow7: ; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ [[PRED7:%.*]], [[COND_END61:%.*]] ], [ false, [[IRR_GUARD:%.*]] ] ; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ false, [[COND_END61]] ], [ true, [[IRR_GUARD]] ] @@ -54,22 +54,22 @@ ; CHECK: Flow9: ; CHECK-NEXT: [[TMP7:%.*]] = phi i1 [ true, [[FLOW10]] ], [ false, [[FLOW8]] ] ; CHECK-NEXT: [[TMP8:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP5]], [[FLOW8]] ] -; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ [[TMP18:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ] -; CHECK-NEXT: [[TMP10:%.*]] = xor i1 [[TMP7]], true -; CHECK-NEXT: [[TMP11:%.*]] = xor i1 [[TMP8]], true +; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ [[TMP15:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ] +; CHECK-NEXT: [[DOTINV11:%.*]] = xor i1 [[TMP7]], true +; CHECK-NEXT: [[DOTINV:%.*]] = xor i1 [[TMP8]], true ; CHECK-NEXT: br i1 [[TMP9]], label [[LOOP_EXIT_GUARD1:%.*]], label [[IRR_GUARD]] ; CHECK: while.cond47: ; CHECK-NEXT: br label [[FLOW10]] ; CHECK: cond.end61: ; CHECK-NEXT: br label [[FLOW7]] -; CHECK: Flow13: -; CHECK-NEXT: [[TMP12:%.*]] = phi i1 [ false, [[FLOW14:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ] -; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ [[TMP17:%.*]], [[FLOW14]] ], [ [[TMP11]], [[LOOP_EXIT_GUARD1]] ] -; CHECK-NEXT: br label [[FLOW12:%.*]] +; CHECK: Flow14: +; CHECK-NEXT: [[TMP10:%.*]] = phi i1 [ false, [[FLOW15:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ] +; CHECK-NEXT: [[TMP11:%.*]] = phi i1 [ [[TMP14:%.*]], [[FLOW15]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD1]] ] +; CHECK-NEXT: br label [[FLOW13:%.*]] ; CHECK: if.then69: -; CHECK-NEXT: br label [[FLOW14]] +; CHECK-NEXT: br label [[FLOW15]] ; CHECK: lor.rhs: -; CHECK-NEXT: br label [[FLOW11]] +; CHECK-NEXT: br label [[FLOW12]] ; CHECK: while.end76: ; CHECK-NEXT: br label [[FLOW6:%.*]] ; CHECK: if.then39: @@ -87,39 +87,39 @@ ; CHECK: Flow: ; CHECK-NEXT: br label [[FLOW3]] ; CHECK: Flow3: -; CHECK-NEXT: br label [[FLOW18]] +; CHECK-NEXT: br label [[FLOW19]] ; CHECK: Flow4: ; CHECK-NEXT: br label [[FLOW5]] ; CHECK: Flow5: -; CHECK-NEXT: br label [[FLOW15]] -; CHECK: Flow6: ; CHECK-NEXT: br label [[FLOW16]] +; CHECK: Flow6: +; CHECK-NEXT: br label [[FLOW17]] ; CHECK: exit: ; CHECK-NEXT: ret void -; CHECK: Flow11: -; CHECK-NEXT: [[TMP14:%.*]] = phi i1 [ false, [[LOR_RHS]] ], [ true, [[WHILE_COND]] ] -; CHECK-NEXT: [[TMP15:%.*]] = phi i1 [ [[PRED9:%.*]], [[LOR_RHS]] ], [ [[PRED3]], [[WHILE_COND]] ] -; CHECK-NEXT: br i1 [[TMP15]], label [[IRR_GUARD]], label [[FLOW12]] +; CHECK: Flow12: +; CHECK-NEXT: [[TMP12:%.*]] = phi i1 [ false, [[LOR_RHS]] ], [ true, [[WHILE_COND]] ] +; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ [[PRED9:%.*]], [[LOR_RHS]] ], [ [[PRED3]], [[WHILE_COND]] ] +; CHECK-NEXT: br i1 [[TMP13]], label [[IRR_GUARD]], label [[FLOW13]] ; CHECK: irr.guard: -; CHECK-NEXT: [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[FLOW9]] ], [ [[TMP14]], [[FLOW11]] ] -; CHECK-NEXT: [[TMP16:%.*]] = xor i1 [[GUARD_COND_TRUE49]], true -; CHECK-NEXT: br i1 [[TMP16]], label [[COND_END61]], label [[FLOW7]] -; CHECK: Flow14: -; CHECK-NEXT: [[TMP17]] = phi i1 [ [[PRED8:%.*]], [[IF_THEN69:%.*]] ], [ [[TMP11]], [[LOOP_EXIT_GUARD2:%.*]] ] -; CHECK-NEXT: br label [[FLOW13:%.*]] +; CHECK-NEXT: [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[FLOW9]] ], [ [[TMP12]], [[FLOW12]] ] +; CHECK-NEXT: [[GUARD_COND_TRUE49_INV:%.*]] = xor i1 [[GUARD_COND_TRUE49]], true +; CHECK-NEXT: br i1 [[GUARD_COND_TRUE49_INV]], label [[COND_END61]], label [[FLOW7]] +; CHECK: Flow15: +; CHECK-NEXT: [[TMP14]] = phi i1 [ [[PRED8:%.*]], [[IF_THEN69:%.*]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD2:%.*]] ] +; CHECK-NEXT: br label [[FLOW14:%.*]] ; CHECK: loop.exit.guard: -; CHECK-NEXT: br i1 [[TMP19:%.*]], label [[WHILE_END76:%.*]], label [[FLOW6]] +; CHECK-NEXT: br i1 [[TMP16:%.*]], label [[WHILE_END76:%.*]], label [[FLOW6]] ; CHECK: Flow10: -; CHECK-NEXT: [[TMP18]] = phi i1 [ false, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ] +; CHECK-NEXT: [[TMP15]] = phi i1 [ false, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ] ; CHECK-NEXT: br label [[FLOW9]] -; CHECK: Flow12: -; CHECK-NEXT: [[TMP19]] = phi i1 [ [[TMP12]], [[FLOW13]] ], [ true, [[FLOW11]] ] -; CHECK-NEXT: [[TMP20:%.*]] = phi i1 [ [[TMP13]], [[FLOW13]] ], [ true, [[FLOW11]] ] -; CHECK-NEXT: br i1 [[TMP20]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]] +; CHECK: Flow13: +; CHECK-NEXT: [[TMP16]] = phi i1 [ [[TMP10]], [[FLOW14]] ], [ true, [[FLOW12]] ] +; CHECK-NEXT: [[TMP17:%.*]] = phi i1 [ [[TMP11]], [[FLOW14]] ], [ true, [[FLOW12]] ] +; CHECK-NEXT: br i1 [[TMP17]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]] ; CHECK: loop.exit.guard1: -; CHECK-NEXT: br i1 [[TMP11]], label [[LOOP_EXIT_GUARD2]], label [[FLOW13]] +; CHECK-NEXT: br i1 [[DOTINV]], label [[LOOP_EXIT_GUARD2]], label [[FLOW14]] ; CHECK: loop.exit.guard2: -; CHECK-NEXT: br i1 [[TMP10]], label [[IF_THEN69]], label [[FLOW14]] +; CHECK-NEXT: br i1 [[DOTINV11]], label [[IF_THEN69]], label [[FLOW15]] ; entry: br i1 %Pred0, label %if.end, label %if.then