Index: llvm/include/llvm/Analysis/ComplexLogicCombine.h =================================================================== --- llvm/include/llvm/Analysis/ComplexLogicCombine.h +++ llvm/include/llvm/Analysis/ComplexLogicCombine.h @@ -52,7 +52,8 @@ class LogicalOpsHelper { public: LogicalOpsHelper() - : LogicalOpNodes(), LeafSet(), LeafValues(), LeafsMayPoison() {} + : LogicalOpNodes(), LeafSet(), LeafValues(), LeafsMayPoison(), + ConstantLeafs() {} ~LogicalOpsHelper() { clear(); } Value *simplify(Value *Root); @@ -64,6 +65,9 @@ SmallPtrSet LeafSet; SmallVector LeafValues; uint64_t LeafsMayPoison; + uint64_t ConstantLeafs; + Constant *ConstAllOne; + Constant *ConstZero; void clear(); Index: llvm/include/llvm/Analysis/LogicalExpr.h =================================================================== --- llvm/include/llvm/Analysis/LogicalExpr.h +++ llvm/include/llvm/Analysis/LogicalExpr.h @@ -52,7 +52,7 @@ class LogicalExpr { private: ExprAddChain AddChain; - // TODO: can we use APInt define the mask to enlarge the max leaf number? + // TODO: can we use APInt define the bitset to enlarge the max leaf number? uint64_t LeafMask; inline void updateLeafMask() { @@ -93,9 +93,8 @@ continue; uint64_t NewBitSet; - // Except the speical case one value "*" -1 is just return itself, the - // other "*" operation is actually "|" LHS and RHS 's bitset. For + // other "*" operations are actually "|" LHS and RHS 's bitset. For // example: ab * bd = abd The expression ab * bd convert to bitset will // be 0b0011 * 0b1010. The result abd convert to bitset will become // 0b1011. Index: llvm/lib/Analysis/ComplexLogicCombine.cpp =================================================================== --- llvm/lib/Analysis/ComplexLogicCombine.cpp +++ llvm/lib/Analysis/ComplexLogicCombine.cpp @@ -107,6 +107,7 @@ for (auto node : LogicalOpNodes) delete node.second; LeafsMayPoison = 0; + ConstantLeafs = 0; LogicalOpNodes.clear(); LeafSet.clear(); LeafValues.clear(); @@ -131,6 +132,8 @@ LeafSet.insert(Val).second) { if (!isGuaranteedNotToBeUndefOrPoison(Val)) LeafsMayPoison |= ExprVal; + if (isa(Val)) + ConstantLeafs |= ExprVal; LeafValues.push_back(Val); } LogicalOpNode *Node = @@ -154,7 +157,7 @@ if (RHS == nullptr) return nullptr; - // TODO: We can reduce the weight if th node can be simplified even if + // TODO: We can reduce the weight if the node can be simplified even if // it is not the root node. unsigned Weight = LHS->getWeight() + RHS->getWeight() + 1; unsigned OneUseWeight = Weight; @@ -253,12 +256,17 @@ Instruction *I = cast(Node->getValue()); Type *Ty = I->getType(); IRBuilder<> Builder(I); + auto GetInstCnt = [this](uint64_t LeafBits) { + uint64_t ConstLeafCnt = llvm::popcount(LeafBits & ConstantLeafs); + uint64_t ConstFoldedCnt = ConstLeafCnt > 1 ? ConstLeafCnt - 1 : 0; + return llvm::popcount(LeafBits) - 1 - ConstFoldedCnt; + }; + if (Expr.size() == 1) { uint64_t LeafBits = *Expr.begin(); - unsigned InstCnt = llvm::popcount(LeafBits) - 1; // TODO: For now we assume we can't reuse any node from old instruction. // Later we can search if we can reuse the node is not one use. - if (Node->worthToCombine(InstCnt)) + if (Node->worthToCombine(GetInstCnt(LeafBits))) return buildAndChain(Builder, Ty, LeafBits); } @@ -274,8 +282,8 @@ if (RHS == 0) RHS = LogicalExpr::ExprAllOne; } - unsigned InstCnt = llvm::popcount(CommonAnd) + llvm::popcount(LHS) + - llvm::popcount(RHS) - 1; + unsigned InstCnt = + GetInstCnt(CommonAnd) + GetInstCnt(LHS) + GetInstCnt(RHS) + 2; if (Node->worthToCombine(InstCnt)) { Value *LHSV = buildAndChain(Builder, Ty, LHS); Value *RHSV = buildAndChain(Builder, Ty, RHS); @@ -294,24 +302,34 @@ Value *LogicalOpsHelper::buildAndChain(IRBuilder<> &Builder, Type *Ty, uint64_t LeafBits) { if (LeafBits == 0) - return Constant::getNullValue(Ty); + return ConstZero; // ExprAllOne is not in the LeafValues if (LeafBits == LogicalExpr::ExprAllOne) - return Constant::getAllOnesValue(Ty); + return ConstAllOne; unsigned LeafCnt = llvm::popcount(LeafBits); if (LeafCnt == 1) return LeafValues[llvm::Log2_64(LeafBits)]; - unsigned LeafIdx = llvm::countr_zero(LeafBits); - Value *AndChain = LeafValues[LeafIdx]; - LeafBits -= (1ULL << LeafIdx); - for (unsigned I = 1; I < LeafCnt; I++) { - LeafIdx = llvm::countr_zero(LeafBits); - AndChain = Builder.CreateAnd(AndChain, LeafValues[LeafIdx]); - LeafBits -= (1ULL << LeafIdx); - } + Value *AndChain = ConstAllOne; + auto CreateAndChain = [this, &Builder, LeafCnt](Value *AndChain, + uint64_t LeafBits, + bool BuildConst) { + unsigned LeafIdx; + for (unsigned I = 0; I < LeafCnt; I++) { + LeafIdx = llvm::countr_zero(LeafBits); + Value *LeafVal = LeafValues[LeafIdx]; + if (BuildConst == isa(LeafVal)) + AndChain = Builder.CreateAnd(LeafVal, AndChain); + LeafBits -= (1ULL << LeafIdx); + } + return AndChain; + }; + + if (llvm::popcount(ConstantLeafs) > 1) + AndChain = CreateAndChain(AndChain, LeafBits, true); + AndChain = CreateAndChain(AndChain, LeafBits, false); return AndChain; } @@ -322,6 +340,9 @@ if (RootNode == nullptr) return nullptr; + ConstAllOne = Constant::getAllOnesValue(Root->getType()); + ConstZero = Constant::getNullValue(Root->getType()); + Value *NewRoot = logicalOpToValue(RootNode); if (NewRoot == Root) return nullptr; Index: llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll =================================================================== --- llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll +++ llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll @@ -43,6 +43,16 @@ ret i1 %or } +define i8 @leaf1_and_const_fold(i8 %a) { +; CHECK-LABEL: @leaf1_and_const_fold( +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[A:%.*]], 15 +; CHECK-NEXT: ret i8 [[TMP1]] +; + %and1 = and i8 %a, 111 + %and2 = and i8 %and1, 31 + ret i8 %and2 +} + define i1 @leaf2_xor(i1 %a, i1 %b) { ; CHECK-LABEL: @leaf2_xor( ; CHECK-NEXT: ret i1 [[B:%.*]] @@ -98,7 +108,7 @@ define i1 @leaf2_ret_and(i1 %a, i1 %b) { ; CHECK-LABEL: @leaf2_ret_and( -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[B:%.*]], [[A:%.*]] ; CHECK-NEXT: ret i1 [[TMP1]] ; %ab = and i1 %a, %b @@ -117,6 +127,21 @@ ret i1 %xor } +define i8 @leaf2_ret_const_fold(i8 %a, i8 %b) { +; CHECK-LABEL: @leaf2_ret_const_fold( +; CHECK-NEXT: [[TMP1:%.*]] = xor i8 [[B:%.*]], -1 +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[A:%.*]], 18 +; CHECK-NEXT: [[TMP3:%.*]] = and i8 [[TMP1]], [[TMP2]] +; CHECK-NEXT: ret i8 [[TMP3]] +; + %and1 = and i8 %a, 122 + %or = or i8 %and1, %b + %and2 = and i8 %or, 23 + %and3 = and i8 %b, 23 + %r = xor i8 %and2, %and3 + ret i8 %r +} + define i1 @leaf3_complex_ret_const_false(i1 %a, i1 %b, i1 %c) { ; CHECK-LABEL: @leaf3_complex_ret_const_false( ; CHECK-NEXT: ret i1 false @@ -144,8 +169,8 @@ define i1 @leaf3_ret_and_chain(i1 %a, i1 %b, i1 %c) { ; CHECK-LABEL: @leaf3_ret_and_chain( -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[TMP2:%.*]] = and i1 [[TMP1]], [[C:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[B:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i1 [[C:%.*]], [[TMP1]] ; CHECK-NEXT: ret i1 [[TMP2]] ; %ab = and i1 %a, %b @@ -174,7 +199,7 @@ define i1 @leaf3_select_ret_and(i1 %a, i1 %b, i1 noundef %c) { ; CHECK-LABEL: @leaf3_select_ret_and( -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[A:%.*]], [[C:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[C:%.*]], [[A:%.*]] ; CHECK-NEXT: ret i1 [[TMP1]] ; %ab = and i1 %a, %b @@ -186,7 +211,7 @@ define i1 @leaf3_select_ret_and2(i1 %a, i1 %b, i1 %c) { ; CHECK-LABEL: @leaf3_select_ret_and2( -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[B:%.*]], [[A:%.*]] ; CHECK-NEXT: ret i1 [[TMP1]] ; %ac = and i1 %a, %c @@ -270,7 +295,7 @@ define i1 @leaf4_complex_ret_and_chain(i1 %a, i1 %b, i1 %c, i1 %d) { ; CHECK-LABEL: @leaf4_complex_ret_and_chain( -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[B:%.*]], [[D:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[D:%.*]], [[B:%.*]] ; CHECK-NEXT: ret i1 [[TMP1]] ; %bd = and i1 %b, %d @@ -293,7 +318,7 @@ ; CHECK-NEXT: [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B]] ; CHECK-NEXT: [[OR1:%.*]] = or i1 [[XOR_AB]], [[C]] ; CHECK-NEXT: [[OR2:%.*]] = or i1 [[OR1]], [[NOT_BD]] -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[B]], [[D]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[D]], [[B]] ; CHECK-NEXT: call void @use1(i1 [[OR2]]) ; CHECK-NEXT: ret i1 [[TMP1]] ; @@ -327,7 +352,7 @@ define i1 @leaf4_select_noundef_complex_ret_and(i1 %a, i1 %b, i1 %c, i1 noundef %d) { ; CHECK-LABEL: @leaf4_select_noundef_complex_ret_and( -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[B:%.*]], [[D:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[D:%.*]], [[B:%.*]] ; CHECK-NEXT: ret i1 [[TMP1]] ; %ab = and i1 %a, %b @@ -411,7 +436,7 @@ define i1 @leaf4_complex_ret_xor_both_and(i1 %a, i1 %b, i1 %c, i1 %d) { ; CHECK-LABEL: @leaf4_complex_ret_xor_both_and( ; CHECK-NEXT: [[AND2:%.*]] = and i1 [[A:%.*]], [[C:%.*]] -; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[B:%.*]], [[D:%.*]] ; CHECK-NEXT: [[XOR_BD:%.*]] = xor i1 [[AND2]], [[TMP1]] ; CHECK-NEXT: ret i1 [[XOR_BD]] ;