Index: llvm/lib/Transforms/Scalar/EarlyCSE.cpp =================================================================== --- llvm/lib/Transforms/Scalar/EarlyCSE.cpp +++ llvm/lib/Transforms/Scalar/EarlyCSE.cpp @@ -171,6 +171,31 @@ return hash_combine(Inst->getOpcode(), SPF, A, B); } + // Hash general selects to allow matching commuted true/false operands. + Value *Cond, *TVal, *FVal; + if (match(Inst, m_Select(m_Value(Cond), m_Value(TVal), m_Value(FVal)))) { + // Similar to cmp normalization (above) - canonicalize the predicate value: + // select (icmp Pred, ?, ?), T, F --> select (icmp InvPred, ?, ?), F, T + CmpInst::Predicate Pred; + if (match(Cond, m_Cmp(Pred, m_Value(), m_Value()))) { + if (CmpInst::getInversePredicate(Pred) < Pred) { + Pred = CmpInst::getInversePredicate(Pred); + std::swap(TVal, FVal); + } + return hash_combine(Inst->getOpcode(), Pred, TVal, FVal); + } + + // If the select has an inverted condition, look through the 'not' and swap + // the true and false operands: + // select (not Cond), T, F --> select Cond, F, T + Value *CondNot; + if (match(Cond, m_Not(m_Value(CondNot)))) { + Cond = CondNot; + std::swap(TVal, FVal); + } + return hash_combine(Inst->getOpcode(), Cond, TVal, FVal); + } + if (CastInst *CI = dyn_cast(Inst)) return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0)); @@ -183,8 +208,7 @@ IVI->getOperand(1), hash_combine_range(IVI->idx_begin(), IVI->idx_end())); - assert((isa(Inst) || isa(Inst) || - isa(Inst) || isa(Inst) || + assert((isa(Inst) || isa(Inst) || isa(Inst) || isa(Inst) || isa(Inst)) && "Invalid/unknown instruction"); @@ -248,6 +272,27 @@ } } + // Handle regular selects (not select pattern flavors) with swapped + // true/false operands. + Value *CondL, *CondR, *T, *F; + if (match(LHSI, m_Select(m_Value(CondL), m_Value(T), m_Value(F))) && + match(RHSI, m_Select(m_Value(CondR), m_Specific(F), m_Specific(T)))) { + // If the conditions are inverted compares, the selects are equal: + // select (icmp Pred, X, Y), T, F <--> select (icmp InvPred, X, Y), F, T + CmpInst::Predicate PredL, PredR; + Value *X, *Y; + if (match(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) && + match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) && + CmpInst::getInversePredicate(PredL) == PredR) + return true; + + // If the conditions are inverted using a 'not', the selects are equal: + // select Cond, T, F <--> select not(Cond), F, T + if (match(CondL, m_Not(m_Specific(CondR))) || + match(CondR, m_Not(m_Specific(CondL)))) + return true; + } + return false; } Index: llvm/test/Transforms/EarlyCSE/commute.ll =================================================================== --- llvm/test/Transforms/EarlyCSE/commute.ll +++ llvm/test/Transforms/EarlyCSE/commute.ll @@ -290,15 +290,13 @@ } ; https://bugs.llvm.org/show_bug.cgi?id=41101 -; TODO: Detect equivalence of selects with commuted operands: 'not' cond. +; Detect equivalence of selects with commuted operands: 'not' cond. define i32 @select_not_cond(i1 %cond, i32 %t, i32 %f) { ; CHECK-LABEL: @select_not_cond( ; CHECK-NEXT: [[NOT:%.*]] = xor i1 [[COND:%.*]], true ; CHECK-NEXT: [[M1:%.*]] = select i1 [[COND]], i32 [[T:%.*]], i32 [[F:%.*]] -; CHECK-NEXT: [[M2:%.*]] = select i1 [[NOT]], i32 [[F]], i32 [[T]] -; CHECK-NEXT: [[R:%.*]] = xor i32 [[M2]], [[M1]] -; CHECK-NEXT: ret i32 [[R]] +; CHECK-NEXT: ret i32 0 ; %not = xor i1 %cond, -1 %m1 = select i1 %cond, i32 %t, i32 %f @@ -307,15 +305,13 @@ ret i32 %r } -; TODO: Detect equivalence of selects with commuted operands: 'not' cond with vector select. +; Detect equivalence of selects with commuted operands: 'not' cond with vector select. define <2 x double> @select_not_cond_commute_vec(<2 x i1> %cond, <2 x double> %t, <2 x double> %f) { ; CHECK-LABEL: @select_not_cond_commute_vec( ; CHECK-NEXT: [[NOT:%.*]] = xor <2 x i1> [[COND:%.*]], ; CHECK-NEXT: [[M1:%.*]] = select <2 x i1> [[COND]], <2 x double> [[T:%.*]], <2 x double> [[F:%.*]] -; CHECK-NEXT: [[M2:%.*]] = select <2 x i1> [[NOT]], <2 x double> [[F]], <2 x double> [[T]] -; CHECK-NEXT: [[R:%.*]] = fdiv nnan <2 x double> [[M1]], [[M2]] -; CHECK-NEXT: ret <2 x double> [[R]] +; CHECK-NEXT: ret <2 x double> ; %not = xor <2 x i1> %cond, %m1 = select <2 x i1> %cond, <2 x double> %t, <2 x double> %f @@ -357,16 +353,14 @@ ret i32 %r } -; TODO: Detect equivalence of selects with commuted operands: inverted pred with fcmps. +; Detect equivalence of selects with commuted operands: inverted pred with fcmps. define i32 @select_invert_pred_cond(float %x, i32 %t, i32 %f) { ; CHECK-LABEL: @select_invert_pred_cond( ; CHECK-NEXT: [[COND:%.*]] = fcmp ueq float [[X:%.*]], 4.200000e+01 ; CHECK-NEXT: [[INVCOND:%.*]] = fcmp one float [[X]], 4.200000e+01 ; CHECK-NEXT: [[M1:%.*]] = select i1 [[COND]], i32 [[T:%.*]], i32 [[F:%.*]] -; CHECK-NEXT: [[M2:%.*]] = select i1 [[INVCOND]], i32 [[F]], i32 [[T]] -; CHECK-NEXT: [[R:%.*]] = xor i32 [[M2]], [[M1]] -; CHECK-NEXT: ret i32 [[R]] +; CHECK-NEXT: ret i32 0 ; %cond = fcmp ueq float %x, 42.0 %invcond = fcmp one float %x, 42.0 @@ -376,16 +370,14 @@ ret i32 %r } -; TODO: Detect equivalence of selects with commuted operands: inverted pred with icmps and vectors. +; Detect equivalence of selects with commuted operands: inverted pred with icmps and vectors. define <2 x i32> @select_invert_pred_cond_commute_vec(<2 x i8> %x, <2 x i32> %t, <2 x i32> %f) { ; CHECK-LABEL: @select_invert_pred_cond_commute_vec( ; CHECK-NEXT: [[COND:%.*]] = icmp sgt <2 x i8> [[X:%.*]], ; CHECK-NEXT: [[INVCOND:%.*]] = icmp sle <2 x i8> [[X]], ; CHECK-NEXT: [[M1:%.*]] = select <2 x i1> [[COND]], <2 x i32> [[T:%.*]], <2 x i32> [[F:%.*]] -; CHECK-NEXT: [[M2:%.*]] = select <2 x i1> [[INVCOND]], <2 x i32> [[F]], <2 x i32> [[T]] -; CHECK-NEXT: [[R:%.*]] = xor <2 x i32> [[M1]], [[M2]] -; CHECK-NEXT: ret <2 x i32> [[R]] +; CHECK-NEXT: ret <2 x i32> zeroinitializer ; %cond = icmp sgt <2 x i8> %x, %invcond = icmp sle <2 x i8> %x,