[LogicCombine 1/?] Implement a general way to simplify logical operations.

[bcl5980]

Summary

This patch involves boolean ring to simplify logical operations. We can treat & as ring multiplication and ^ as ring addition.
So we need to canonicalize all other operations to * +. Like:

a & b -> a * b
a ^ b -> a + b
~a -> a + 1
a | b -> a * b + a + b
c ? a : b -> c * a + (c + 1) * b

In the code, we use a mask set to represent an expression. Every value that is not comes from logical operations could be a bit in the mask.
The mask itself is a multiplication chain. The mask set is an addiction chain.
We can calculate two expressions based on boolean algebras.

For now, the initial patch only enabled on and/or/xor, Later we can enhance the code step by step.

Reference: https://en.wikipedia.org/wiki/Boolean_ring

[bcl5980]

variable rename. NFC

[bcl5980]

fix a bug in exprAnd

[bcl5980]

Define LogicalExpr as a class and split it into a new header file.

[bcl5980]

add one more test.

[xbolva00]

This is cool!

[bcl5980]

Fix test failure.

[bcl5980]

Ping.
Anyone can help to review it? Or is this necessary for llvm?
I try to run it on test-suite, it looks only spec2017 502.gcc can trigger this 6 times.

[spatel]

In D142803#4105675, @bcl5980 wrote:

Ping.
Anyone can help to review it? Or is this necessary for llvm?
I try to run it on test-suite, it looks only spec2017 502.gcc can trigger this 6 times.

It seems like a nice improvement. It would be great if it eventually allows removing some of the pattern-specific complex logic reductions that we have in InstCombine/InstSimplify:
https://github.com/llvm/llvm-project/blob/b5ee4f755fcff56243f6ff0cea9e7a722259304a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L1719

I had not seen "boolean ring" before this. Do you know if that is implemented in any other programs/compilers?

[bcl5980]

In D142803#4106685, @spatel wrote:

In D142803#4105675, @bcl5980 wrote:

Ping.
Anyone can help to review it? Or is this necessary for llvm?
I try to run it on test-suite, it looks only spec2017 502.gcc can trigger this 6 times.

It seems like a nice improvement. It would be great if it eventually allows removing some of the pattern-specific complex logic reductions that we have in InstCombine/InstSimplify:
https://github.com/llvm/llvm-project/blob/b5ee4f755fcff56243f6ff0cea9e7a722259304a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L1719

The initial patch can't replace the code in foldComplexAndOrPatterns. I will continue work on it that maybe one day we can replace all patterns in foldComplexAndOrPatterns.
For now, this code only enabled on O3, but the foldComplexAndOrPatterns may work on O2 also. I'm not sure the CPU overhead for this patch. If later we can proof this is not a big overhead we can move it to Instcombine.

I had not seen "boolean ring" before this. Do you know if that is implemented in any other programs/compilers?

I'm sorry I am a beginner on compiler, the only compiler I touch is Clang/LLVM. So I don't know if any other programs/compiler have similar code or not. This patch is written based on my understand of boolean ring.

[bcl5980]

Ping.

[spatel]

I'm still trying to understand how this works, so I only looked at the high-level comments to start.

Is it possible to convert existing logic tests in InstCombien/InstSimplify to use branches, then run those tests with "opt -aggressive-instcombine" and verify that the results are correct?

llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.cpp

14 ↗

(On Diff #494597)

I don't understand the term "unsigned set" in this context. Could this be "bit set"? But this is also what you are calling a "mask" later in this description and in the code itself?

15 ↗

(On Diff #494597)

Word choice:
"Every value that is not comes from logic operation should be the leaf node." ->
"Any value that is not a logic operation is a leaf node." ?

21 ↗

(On Diff #494597)

Now it says "unsigned value", but didn't we just define that as "mask"?
Can we replace "unsigned set" with "set of masks"?

25 ↗

(On Diff #494597)

Is "b * c" -> 6 in this example?

llvm/lib/Transforms/AggressiveInstCombine/LogicalExpr.h

10 ↗

(On Diff #494597)

Is it correct to write it like this:
For source values {a,b,c,d}, we can represent them as a bitmask with 'a' as the least-significant-bit: {dcba}.
?

13 ↗

(On Diff #494597)

Does the multiplication between LHS and RHS mean the top-level logic operation in this example is an "and"?

15 ↗

(On Diff #494597)

I don't understand what happened in these steps. What is the relationship of "*" and "+" to "|" and ","?

43–44 ↗

(On Diff #494597)

If we are using uin64_t as the basic "mask" of values and we have magic constants for the 2 high-bits, does it mean that the "MaxLogicOpLeafsToScan" must be less than 62? Is that enforced with assertions or other logic?

[bcl5980]

llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.cpp

14 ↗

(On Diff #494597)

I will update the comments to set of masks.

25 ↗

(On Diff #494597)

Yeah, thanks for the finding.

llvm/lib/Transforms/AggressiveInstCombine/LogicalExpr.h

13 ↗

(On Diff #494597)

Yes, it means LHS & RHS

15 ↗

(On Diff #494597)

That's a little tricky here. The bitset means and/multiplication chain. So when we do a & b, the bitset should be 1 | 2 to set a and b 's corresponding bits.
"," actually the same to "+", I just want to show the pattern means LHS.
How about I write the comments like:

{0b1111, 0b1001, 0b0010 , 0b1101} * {0b0001, 0b0101}
-->
(0b1111 + 0b1001 + 0b0010 + 0b1101) * (0b0001 + 0b0101)
-->
(0b1111 + 0b1001 + 0b0010 + 0b1101) * 0b0001+ (0b1111 + 0b1001 + 0b0010 + 0b1101) * 0b0101
-->
(0b1111 | 0b0001) + (0b1001| 0b0001) + (0b0010 | 0b0001) + (0b1101 | 0b0001) + (0b1111 | 0b0101) + (0b1001| 0b0101) + (0b0010 + 0b0101) + (0b1101 + 0b0101)
--> 
(0b1111 + 0b1001 + 0b0010 + 0b1101 + 0b1111 + 0b1101 + 0b0111 + 0b1101
-->
0b1001 + 0b0010 + 0b1101 + 0b0111
-->
{0b1001, 0b0010, 0b1101, 0b0111}
-->
a * d + b + a * c * d + a * b * c

43–44 ↗

(On Diff #494597)

Yeah, you are right. We need an assertion here to make sure the max leaf number is less than 62. I will update it later.

[bcl5980]

In D142803#4124135, @spatel wrote:

I'm still trying to understand how this works, so I only looked at the high-level comments to start.

Is it possible to convert existing logic tests in InstCombien/InstSimplify to use branches, then run those tests with "opt -aggressive-instcombine" and verify that the results are correct?

I'm not sure if it is possible, but if we want to test more cases I can try to add an option to make it work on every logical operations. And I can run local to test but I'm not sure how to show the result on the review.

[bcl5980]

Address comments.

[bcl5980]

In D142803#4124135, @spatel wrote:

I'm still trying to understand how this works, so I only looked at the high-level comments to start.

Is it possible to convert existing logic tests in InstCombien/InstSimplify to use branches, then run those tests with "opt -aggressive-instcombine" and verify that the results are correct?

@spatel I try to run all tests of InstCombine and some of current tests can be improved. The detail diff is D144071.

[bcl5980]

Move complex-logic-combine to Analysis

[spatel]

In D142803#4128062, @bcl5980 wrote:

In D142803#4124135, @spatel wrote:

I'm still trying to understand how this works, so I only looked at the high-level comments to start.

Is it possible to convert existing logic tests in InstCombien/InstSimplify to use branches, then run those tests with "opt -aggressive-instcombine" and verify that the results are correct?

@spatel I try to run all tests of InstCombine and some of current tests can be improved. The detail diff is D144071.

Nice! The results look promising. I'm still trying to understand how this works by reading the code (rather than reading the wikipedia reference page).
I'm confused, so it's still just a couple of high-level questions/comments.

llvm/include/llvm/Analysis/LogicalExpr.h

17

I'm still confused by the notation. Each "-->" step needs a comment to describe exactly what is happening. If we are not showing some unique math/logic property with each of the terms in the equation/set, then it would be easier to follow the logic with a smaller example.

In this step, we are splitting the RHS masks to operate over the LHS? But are those "+" and "*" symbols representing real math operations or are they bitwise logical operations?

21

Here we have distributed the RHS mask values over the LHS mask values? Why did "*" become "|"?

25

I don't know what operation was done there. It's not logical-or or multiplication?

llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll

4 ↗

(On Diff #497553)

We're going to need more tests than this. Name each test to suggest what it demonstrates (or add test comments, so that is clear).

We should build up to the complex examples. Start with single value logic to prove that works:

define i32 @x_and_not_x(i32 %x) {
  %notx = xor i32 %x, -1
  %r = and i32 %x, %notx
  ret i32 %r
}

...and more like that. Next, show some 2 value tests. Then, show 3 values and finally 4 values.

[bcl5980]

llvm/include/llvm/Analysis/LogicalExpr.h

17

"+" and "*" representing math operation on the boolean ring.
"+" is the same to xor, "*" is the same to and. And they also follow the distributive laws and commutative law like the normal "*", "+".

21

For example: ab * bd = abd
The expression ab * bd convert to mask will be 0b0011 * 0b1010.
The result abcd convert to mask will become 0b1011.
So for the "*" operation is actually "|" LHS and RHS 's masks.

25

For the "+" operation, we can replace them to xor. So if we find two mask is the same, we can remove both of them.

[bcl5980]

update more tests.

[spatel]

I like the test progression now. You could pre-commit the baseline file.

Can you replace the example in the code comment in LogicalExpr.h with the steps used to solve @leaf3_complex_ret_leaf?

That's a smaller test, but it seems like it covers many interesting reductions. If that's still too big to be a good introduction, then make it smaller.

The first line should be the expression in logical form using the usual C logic operators:

((a & b) | (a ^ c)) ^ (!(b & c) & a)

Next line: show how that is expanded to a logic form suitable for boolean ring - 'or' becomes 'and' and 'xor', so (make sure this is correct):

(((a & b) & (a ^ c)) ^ (a & b) ^ (a ^ c)) ^ (((b & c) ^ -1) & a)

Is convert to ring masks/operators the next step (or is this 2 steps)?

(((001 * 010) * (001 + 100)) + (001 * 010) + (001 + 100)) + (((010 * 100) + ???) * 001

Now go through each distributive, associative, destructive step just like the code would do and describe it.

[bcl5980]

Update comments.
Rebase tests.

[bcl5980]

@spatel , do you think this change can split into a individual pass? It looks the sequence of instruction iterator is reversed but I prefer to call the complex logic combine based on normal sequence.
But I'm not sure if this code is worth to add a new pass. If it is worth, where should this pass been inserted?

[bcl5980]

Treat mask value 0 as ExprZero and remove current ExprZero.

[spatel]

In D142803#4134002, @bcl5980 wrote:

@spatel , do you think this change can split into a individual pass? It looks the sequence of instruction iterator is reversed but I prefer to call the complex logic combine based on normal sequence.
But I'm not sure if this code is worth to add a new pass. If it is worth, where should this pass been inserted?

It would probably be better for all of the transforms if we update AggressiveInstCombine to use a worklist instead of a simple iterator. VectorCombine was updated like that not too long ago.
But we can defer that to a follow-up if there's no concern about correctness.

I was curious if enabling this for all logic ops would cause any compile-time regressions, but it seems like it has almost no cost:
https://llvm-compile-time-tracker.com/compare.php?from=0e90cd7551f2d0b151f7406e8f3848ec54e650bf&to=ae505cb2a674ac4c240c94a74fc04ee274321697&stat=instructions:u

llvm/include/llvm/Analysis/LogicalExpr.h

10–16

This is difficult to parse. We must differentiate the logical ops "or" and "and" from the English words.
Header comments should use "///" to auto-generate doxygen.

See if this is a correct edit (adjust to fit 80-columns as necessary):

/// For a logical expression represented by bitmasks, the "and" logic operator
/// represented by "&" is translated to "*" and is then evaluated as the "or" of 
/// the bitmasks. For example, pattern "a & b" is represented by the logical 
/// expression "01 * 10", and the expression is reduced to "11". So the 
/// operation "&" between two logical expressions (not "xor", only "and" chain)
/// is actually bitwise "or" of the masks. There is one exception: if one of the 
/// operands is constant 0, the entire mask represents 0. We do not "or" the 
/// masks in that case.

18–23

/// The evaluation of a pattern for bitwise "xor" is represented by a "+" math operator. 
/// But it also has one exception to normal math rules: if two masks are identical, we 
/// remove them. For example with "a ^ a", the logical expression is "1 + 1". We eliminate 
/// them from the logical expression rather than "or" the bits.
///
/// We use commutative, associative, and distributive laws of arithmetic multiplication
/// and addition to reduce the expression.

33

How we got to this is still not obvious. Add at least one intermediate line between these two.
IIUC, we are evaluating "*" before "+" regardless of the parentheses?

86

It took me a long time to realize that "multiplication" in this expression is really just "bitwise-or". This could use a comment to make it clearer.

llvm/lib/Analysis/ComplexLogicCombine.cpp

9 ↗

(On Diff #498266)

help to find -> attempts to find

20 ↗

(On Diff #498266)

Use quotes around "and" / "xor" / "or" if we are referring to a logic operation.

22 ↗

(On Diff #498266)

by a unsigned set -> as a chain of bitsets ?

25–26 ↗

(On Diff #498266)

Delete the last line - that's an implementation detail that could change in the future.

[bcl5980]

I was curious if enabling this for all logic ops would cause any compile-time regressions, but it seems like it has almost no cost:
https://llvm-compile-time-tracker.com/compare.php?from=0e90cd7551f2d0b151f7406e8f3848ec54e650bf&to=ae505cb2a674ac4c240c94a74fc04ee274321697&stat=instructions:u

Based on the result, can I just enable it for all logical operations by default and remove the option?

[bcl5980]

some renaming.

[spatel]

In D142803#4137888, @bcl5980 wrote:

I was curious if enabling this for all logic ops would cause any compile-time regressions, but it seems like it has almost no cost:
https://llvm-compile-time-tracker.com/compare.php?from=0e90cd7551f2d0b151f7406e8f3848ec54e650bf&to=ae505cb2a674ac4c240c94a74fc04ee274321697&stat=instructions:u

Based on the result, can I just enable it for all logical operations by default and remove the option?

Yes, let's make the transform more general (and the patch becomes simpler if we remove the option).

[spatel]

llvm/include/llvm/Analysis/LogicalExpr.h

36

The "*" operation with -1 is also a special-case, so we should mention it in the text above here.
If I understand the code, if we have "a * -1", then the result is always "a".

37–39

Spelling: Caculate -> Calculate
Spelling: addiction -> addition

96

When we get here, we know that both LHSMask and RHSMask are not equal to "0".
Can we also assert that if a mask has ExprAllOne set, then no other bit in the mask is set?
So would it be clearer to move this check up and write this as:

// 1 & a -> a
// a & 1 -> a
if (LHSMask == ExprAllOne)
  NewMask = RHSMask;
else if (RHSMask == ExprAllOne)
  NewMask = LHSMask;

[spatel]

This seems close to ready to me. It would be great if other reviewers have a look too. :)

llvm/lib/Analysis/ComplexLogicCombine.cpp

1 ↗

(On Diff #498982)

I think we should remove "Complex" from the name. This can handle all LogicOp combining now (and eventually, it could be part of regular InstCombine).

21 ↗

(On Diff #498982)

We -> we

25 ↗

(On Diff #498982)

Final -> Finally,

45 ↗

(On Diff #498982)

If you agree with the earlier comment about removing "Complex" from the name, then change the "clc" also. It could just be "logic-combine-max-leafs" or something like that.

llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll

12 ↗

(On Diff #498982)

We should have more than i1 types in these tests if we are handling all bitwise logic now.

[spatel]

llvm/lib/Analysis/ComplexLogicCombine.cpp

65 ↗

(On Diff #498982)

Should not need "llvm::" specifier here?

66 ↗

(On Diff #498982)

The "LeafCnt == 0" is redundant. Move the "LeafBits == 0" check above the popcount for efficiency.

76 ↗

(On Diff #498982)

Shouldn't need "llvm::" ?

135–136 ↗

(On Diff #498982)

!BO->isBitwiseLogicOp()

180 ↗

(On Diff #498982)

earsed -> erased

196 ↗

(On Diff #498982)

What does this TODO mean? Either describe the planned follow-up with more details or remove this line.

203 ↗

(On Diff #498982)

"can't be larger"

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

830–831

I.isBitwiseLogicOp()

869–870

What does the "for now" mean? Will it change in the future? What limitation does this imply?

[bcl5980]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

869–870

There are 2 limitations to be trade off. here The higher level the LogicalOpsHelper create, the more logical node cached, which means it can save more cpu timing. But it will maintain more leaf nodes. By default the max of leaf node is 8 , which is not enough for whole function I guess.
So I write the comment here to mention me we can do something here later. Like split the helper based on types to make the code more efficient, adjust the default value of max leaf node number, use APInt to support more bits.

The most headache thing for me is test the cpu overhead. @nikic , can you add my github fork to the llvm-compile-time-tracker.com? This serial patches need a lot of CPU overhead tests I think.

[bcl5980]

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

869–870

My github fork link is: https://github.com/bcl5980/llvm-project

[bcl5980]

Address comments.

[spatel]

Please rename the test file as a preliminary step, so we will again show diffs in this patch. We also need to add negative tests to show current limitations and also that the combining is not making wrong logic reductions.

llvm/include/llvm/Analysis/LogicCombine.h

43

This isn't really a "helper" - this is the main part of the code. Can we name this "LogicCombiner"?

54–55

I don't think we need "LeafSet". If you make "LeafValues" a SmallSetVector, we won't insert duplicate values into the vector. Is that the only job of the LeafSet?

llvm/lib/Analysis/LogicCombine.cpp

134

This comment isn't necessary - I think the code is clear enough now.

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

828

/// Reduce bitwise logic sequences.

869–875

Adjust wording (make sure I understand it correctly):

// TODO: Combining at the function-level would allow more 
// caching of nodes which saves on compile-time, but it may hit the
// max depth or value limits before finding a solution. We could split
// the helper based on types to make the code more efficient, adjust 
// the value of max depth/values, or use APInt to support tracking 
// more than 63 leaf values.

But I doubt that we have a real problem here for the vast majority of programs? We are tracking up to 8 different leaf values with a depth of 8 logic instructions. Maybe add (currently) negative tests with those large number of instructions to show what is needed to hit the limits?

885

Change name: foldComplexLogic -> foldBitwiseLogic

This call should be moved before "foldSqrt()" as the code comment suggests.

[bcl5980]

llvm/include/llvm/Analysis/LogicCombine.h

54–55

I need LeafValues to access value by index. It looks SmallSetVector can't do that.

[bcl5980]

Address comments.

[spatel]

I need LeafValues to access value by index. It looks SmallSetVector can't do that.

SmallSetVector allows indexing. This is the patch I tried after applying this patch (I had to fix line endings first), and no tests fail:

diff --git a/llvm/include/llvm/Analysis/LogicCombine.h b/llvm/include/llvm/Analysis/LogicCombine.h
index 3fdcf7998321..56a3d8f36b16 100644
--- a/llvm/include/llvm/Analysis/LogicCombine.h
+++ b/llvm/include/llvm/Analysis/LogicCombine.h
@@ -8,8 +8,7 @@

 #include "LogicalExpr.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
@@ -50,8 +49,7 @@ private:
   friend class LogicalOpNode;

   SmallDenseMap<Value *, LogicalOpNode *, 16> LogicalOpNodes;
-  SmallPtrSet<Value *, 8> LeafSet;
-  SmallVector<Value *, 8> LeafValues;
+  SmallSetVector<Value *, 8> LeafValues;

   void clear();

diff --git a/llvm/lib/Analysis/LogicCombine.cpp b/llvm/lib/Analysis/LogicCombine.cpp
index 28d9488cab96..3b410cdacd32 100644
--- a/llvm/lib/Analysis/LogicCombine.cpp
+++ b/llvm/lib/Analysis/LogicCombine.cpp
@@ -101,17 +101,16 @@ void LogicCombiner::clear() {
   for (auto node : LogicalOpNodes)
     delete node.second;
   LogicalOpNodes.clear();
-  LeafSet.clear();
   LeafValues.clear();
 }

 LogicalOpNode *LogicCombiner::visitLeafNode(Value *Val, unsigned Depth) {
   // Depth is 0 means the root is not logical operation. We can't
   // do anything for that.
-  if (Depth == 0 || LeafSet.size() >= MaxLogicOpLeafsToScan)
+  if (Depth == 0 || LeafValues.size() >= MaxLogicOpLeafsToScan)
     return nullptr;

-  uint64_t ExprVal = 1ULL << LeafSet.size();
+  uint64_t ExprVal = 1ULL << LeafValues.size();
   // Constant Zero,AllOne are special leaf nodes. They involve
   // LogicalExpr's calculation so we must detect them at first.
   if (auto ConstVal = dyn_cast<ConstantInt>(Val)) {
@@ -120,9 +119,8 @@ LogicalOpNode *LogicCombiner::visitLeafNode(Value *Val, unsigned Depth) {
     else if (ConstVal->isAllOnesValue())
       ExprVal = LogicalExpr::ExprAllOne;
   }
-  if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0 &&
-      LeafSet.insert(Val).second)
-    LeafValues.push_back(Val);
+  if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0)
+    LeafValues.insert(Val);
   LogicalOpNode *Node = new LogicalOpNode(this, Val, LogicalExpr(ExprVal));
   LogicalOpNodes[Val] = Node;
   return Node;

[bcl5980]

Remove leafset.

[bcl5980]

In D142803#4147225, @spatel wrote:

I need LeafValues to access value by index. It looks SmallSetVector can't do that.

SmallSetVector allows indexing. This is the patch I tried after applying this patch (I had to fix line endings first), and no tests fail:

diff --git a/llvm/include/llvm/Analysis/LogicCombine.h b/llvm/include/llvm/Analysis/LogicCombine.h
index 3fdcf7998321..56a3d8f36b16 100644
--- a/llvm/include/llvm/Analysis/LogicCombine.h
+++ b/llvm/include/llvm/Analysis/LogicCombine.h
@@ -8,8 +8,7 @@

 #include "LogicalExpr.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
@@ -50,8 +49,7 @@ private:
   friend class LogicalOpNode;

   SmallDenseMap<Value *, LogicalOpNode *, 16> LogicalOpNodes;
-  SmallPtrSet<Value *, 8> LeafSet;
-  SmallVector<Value *, 8> LeafValues;
+  SmallSetVector<Value *, 8> LeafValues;

   void clear();

diff --git a/llvm/lib/Analysis/LogicCombine.cpp b/llvm/lib/Analysis/LogicCombine.cpp
index 28d9488cab96..3b410cdacd32 100644
--- a/llvm/lib/Analysis/LogicCombine.cpp
+++ b/llvm/lib/Analysis/LogicCombine.cpp
@@ -101,17 +101,16 @@ void LogicCombiner::clear() {
   for (auto node : LogicalOpNodes)
     delete node.second;
   LogicalOpNodes.clear();
-  LeafSet.clear();
   LeafValues.clear();
 }

 LogicalOpNode *LogicCombiner::visitLeafNode(Value *Val, unsigned Depth) {
   // Depth is 0 means the root is not logical operation. We can't
   // do anything for that.
-  if (Depth == 0 || LeafSet.size() >= MaxLogicOpLeafsToScan)
+  if (Depth == 0 || LeafValues.size() >= MaxLogicOpLeafsToScan)
     return nullptr;

-  uint64_t ExprVal = 1ULL << LeafSet.size();
+  uint64_t ExprVal = 1ULL << LeafValues.size();
   // Constant Zero,AllOne are special leaf nodes. They involve
   // LogicalExpr's calculation so we must detect them at first.
   if (auto ConstVal = dyn_cast<ConstantInt>(Val)) {
@@ -120,9 +119,8 @@ LogicalOpNode *LogicCombiner::visitLeafNode(Value *Val, unsigned Depth) {
     else if (ConstVal->isAllOnesValue())
       ExprVal = LogicalExpr::ExprAllOne;
   }
-  if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0 &&
-      LeafSet.insert(Val).second)
-    LeafValues.push_back(Val);
+  if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0)
+    LeafValues.insert(Val);
   LogicalOpNode *Node = new LogicalOpNode(this, Val, LogicalExpr(ExprVal));
   LogicalOpNodes[Val] = Node;
   return Node;

Thanks, I have already update it.

[spatel]

LGTM

llvm/include/llvm/Analysis/LogicalExpr.h

95

spelling: "special"

[nikic]

llvm/include/llvm/Analysis/LogicCombine.h

23

It's weird that LogicalOpNode has a reference back to LogicCombiner. Is this just for printing? Would it be better to pass it to the print method?

35

Why the explicit empty dtor?

llvm/include/llvm/Analysis/LogicalExpr.h

11

bitsets?

28

An example

57

Am I missing something, or is LeafMask never actually used?

59

Unnecessary inline?

87

Hm, can these actually occur? It looks like they should be excluded by a ^ a canonicalization.

95

special

121

insert returns an iterator you can pass to erase.

llvm/lib/Analysis/LogicCombine.cpp

17

18

It would be more helpful to write them in binary form here, e.g. 111.

52

I think you might be looking for Value->printAsOperand() here?

78

You can use ListSeparator and avoid the need to split out the last case.

94

Same here, ListSeparator.

103

Should these be using unique_ptr instead?

Or possibly SpecificBumpPtrAllocator?

[nikic]

I'm concerned about the caching here. It looks like you reuse one LogicCombiner instance for a basic block. However, isn't it possible for some of the instructions that have been inserted into LogicalOpNodes to be deleted, in which case the map may contain dangling pointers. If the pointer is reused by a newly allocated instruction, the cached information will be incorrect.

[bcl5980]

Address comments.

llvm/include/llvm/Analysis/LogicCombine.h

23

I call print in operator "<<" . I can't pass the LogicCombiner into the override operator "<<". Do you have any ideal for that?

llvm/include/llvm/Analysis/LogicalExpr.h

57

The initial patch hasn't use LeafMask. The following up change D143155 will use that.

87

For now it should happen in the case with constant 0 like: %and = and i8 %a, 0.
Constant 0 can be represented by empty set or one element with 0 value. If I canonicalize one element with 0 value to empty set then it won't happen.

[bcl5980]

In D142803#4148486, @nikic wrote:

I'm concerned about the caching here. It looks like you reuse one LogicCombiner instance for a basic block. However, isn't it possible for some of the instructions that have been inserted into LogicalOpNodes to be deleted, in which case the map may contain dangling pointers. If the pointer is reused by a newly allocated instruction, the cached information will be incorrect.

The main reason for caching is saving compile time. The new patch will remove all the instructions already inserted into the caches and I think functional it works now.
@nikic @spatel if possible can we use the llvm-compile-time-track to test how much compile time increase if we enable the LogicCombiner for every single instruction?

[bcl5980]

use SpecificBumpPtrAllocator

[bcl5980]

minor bug fix.

[bcl5980]

code clean

[spatel]

llvm/include/llvm/Analysis/LogicalExpr.h

57

I did not notice that LeafMask is unused. It would be better to remove it from this patch.

If you only add it when it becomes necessary, then we can accurately measure the cost of each enhancement. It also makes the review easier because we can see exactly where/how the new features impact the original code.

[spatel]

In D142803#4149087, @bcl5980 wrote:

In D142803#4148486, @nikic wrote:

I'm concerned about the caching here. It looks like you reuse one LogicCombiner instance for a basic block. However, isn't it possible for some of the instructions that have been inserted into LogicalOpNodes to be deleted, in which case the map may contain dangling pointers. If the pointer is reused by a newly allocated instruction, the cached information will be incorrect.

The main reason for caching is saving compile time. The new patch will remove all the instructions already inserted into the caches and I think functional it works now.
@nikic @spatel if possible can we use the llvm-compile-time-track to test how much compile time increase if we enable the LogicCombiner for every single instruction?

If this -- https://github.com/llvm/llvm-project/commit/efcf6c2b1f8490a9258d40abb90b21da60a15919 -- is the experiment that you wanted to try, it seems to have no significant difference:
https://llvm-compile-time-tracker.com/compare.php?from=3592d05438acc1034905feff7ff555f4fd4c5774&to=efcf6c2b1f8490a9258d40abb90b21da60a15919&stat=instructions:u

[nikic]

llvm/include/llvm/Analysis/LogicCombine.h

23

Right, this would not work with operator<<, one would have to call the print method. If << is used a lot, then this makes sense.

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

869–870

I've added your fork now. Sorry, I didn't notice this request before.

[bcl5980]

remove leafmask

[bcl5980]

In D142803#4150591, @spatel wrote:

In D142803#4149087, @bcl5980 wrote:

In D142803#4148486, @nikic wrote:

I'm concerned about the caching here. It looks like you reuse one LogicCombiner instance for a basic block. However, isn't it possible for some of the instructions that have been inserted into LogicalOpNodes to be deleted, in which case the map may contain dangling pointers. If the pointer is reused by a newly allocated instruction, the cached information will be incorrect.

The main reason for caching is saving compile time. The new patch will remove all the instructions already inserted into the caches and I think functional it works now.
@nikic @spatel if possible can we use the llvm-compile-time-track to test how much compile time increase if we enable the LogicCombiner for every single instruction?

If this -- https://github.com/llvm/llvm-project/commit/efcf6c2b1f8490a9258d40abb90b21da60a15919 -- is the experiment that you wanted to try, it seems to have no significant difference:
https://llvm-compile-time-tracker.com/compare.php?from=3592d05438acc1034905feff7ff555f4fd4c5774&to=efcf6c2b1f8490a9258d40abb90b21da60a15919&stat=instructions:u

For now I send 5 patches for logic combine(D143046, D143155, D144373, D144077, D144373). After more patches involved the compile time also increased.
This is the result I enable LogicCombiner for every instruction after all my patches send to review:
http://llvm-compile-time-tracker.com/compare.php?from=4dd4eb939caef1138c655e22bb4adc8978f16427&to=8556a41a4ad4e8cf48bc316c9b5692b0de8e3d39&stat=instructions%3Au

And later I still need to send more patches to figure out some headache things like avoid undef unsafe pattern, restore "|" from the logical expression. So for now I still prefer to cache the result on basic block level.

[aeubanks]

with this patch, would it possible to remove some similar optimizations from instcombine, those being subsumed by this?

[xbolva00]

In D142803#4156027, @aeubanks wrote:

with this patch, would it possible to remove some similar optimizations from instcombine, those being subsumed by this?

AggressiveInstCombine runs only with -O3, no?

Removing instcombine folds would regress performance with lower levels. This leads me to the question how ofter this fires in llvm test suite / SPEC / clang bootstrap? Is it worth it?

[aeubanks]

In D142803#4156050, @xbolva00 wrote:

In D142803#4156027, @aeubanks wrote:

with this patch, would it possible to remove some similar optimizations from instcombine, those being subsumed by this?

AggressiveInstCombine runs only with -O3, no?

Removing instcombine folds would regress performance with lower levels. This leads me to the question how ofter this fires in llvm test suite / SPEC / clang bootstrap? Is it worth it?

Ah yes you're right. Might be worth considering running it under -O2 as well?

[xbolva00]

In D142803#4156053, @aeubanks wrote:

In D142803#4156050, @xbolva00 wrote:

In D142803#4156027, @aeubanks wrote:

with this patch, would it possible to remove some similar optimizations from instcombine, those being subsumed by this?

AggressiveInstCombine runs only with -O3, no?

Removing instcombine folds would regress performance with lower levels. This leads me to the question how ofter this fires in llvm test suite / SPEC / clang bootstrap? Is it worth it?

Ah yes you're right. Might be worth considering running it under -O2 as well?

Yeah! I believe that last time even the impact on compile times was quite low.

[bcl5980]

In D142803#4156027, @aeubanks wrote:

with this patch, would it possible to remove some similar optimizations from instcombine, those being subsumed by this?

This patch can't replace the normal patterns in instcombine. Because this patch works bad between logical node itself. For example,

define i8 @test(i8 %a, i8 %b, i8 %c, i8 %d) {
   %oab = or i8 %a, %b
   %ocd = or i8 %c, %d
   %and = and i8 %oab, %ocd
   %r = and i8 %and, %and
   ret i8 %r
}

Obviously the %r is the same to %and. But both of them in the logical node is a complicated set of bitsets. For now it's not easy to find %and is the same to %r.

[bcl5980]

any other coments for the initial patch? @nikic

[bulbazord]

This breaks module builds (i.e. LLVM_ENABLE_MODULES=ON):

/Users/alex/llvm-project/llvm/include/llvm/Analysis/LogicalExpr.h:53:7: error: redefinition of 'LogicalExpr'
class LogicalExpr {
      ^
/Users/alex/llvm-project/llvm/include/llvm/Analysis/LogicCombine.h:9:10: note: '/Users/alex/llvm-project/llvm/include/llvm/Analysis/LogicalExpr.h' included multiple times, additional include site in header from module 'LLVM_Analysis.LogicalExpr'
#include "LogicalExpr.h"
         ^
<module-includes>:67:10: note: '/Users/alex/llvm-project/llvm/include/llvm/Analysis/LogicalExpr.h' included multiple times, additional include site in header from module 'LLVM_Analysis.LogicalExpr'
#include "Analysis/LogicalExpr.h"
         ^
/Users/alex/llvm-project/llvm/include/llvm/Analysis/LogicalExpr.h:53:7: note: unguarded header; consider using #ifdef guards or #pragma once
class LogicalExpr {

I've added header guards to llvm/include/llvm/Analysis/LogicalExpr.h and llvm/include/llvm/LogicCombine.h in ff65a586677eb127ea70ca84b91204c0b9940b00.

[xbolva00]

In D142803#4157833, @bcl5980 wrote:

any other coments for the initial patch? @nikic

I think it would be better to have approvals for all patches and commit this all at once. Otherwise we might end up with nontrivial unfinished code.

[xbolva00]

And my question was not answered before commit.

This leads me to the question how ofter this fires in llvm test suite / SPEC / clang bootstrap? Is it worth it?

[bcl5980]

In D142803#4186835, @xbolva00 wrote:

In D142803#4157833, @bcl5980 wrote:

any other coments for the initial patch? @nikic

I think it would be better to have approvals for all patches and commit this all at once. Otherwise we might end up with nontrivial unfinished code.

reverted by 76df706bca14affdcf0dd91561c8e6805035608f

[bcl5980]

In D142803#4186836, @xbolva00 wrote:

And my question was not answered before commit.

This leads me to the question how ofter this fires in llvm test suite / SPEC / clang bootstrap? Is it worth it?

patch until D143155, there are 7 patterns triggered by SPEC 2017. No pattern trigged from llvm test suite. Haven't try bootstrap build yet.

[bcl5980]

If no one have any further comments I will abandon this serial patches. It looks it can't improve too much.

llvm/include/llvm/Analysis/LogicCombine.h

+//===------------------ LogicCombine.h --------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "LogicalExpr.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/Support/Allocator.h"
+
+namespace llvm {
+
+class LogicCombiner;
+
+class LogicalOpNode {
+private:
+  LogicCombiner *Helper;
+  Value *Val;
+  LogicalExpr Expr;
+  // TODO: Add weight to measure cost for more than one use value
+
+  void printAndChain(raw_ostream &OS, uint64_t LeafBits) const;
+
+public:
+  LogicalOpNode(LogicCombiner *OpsHelper, Value *SrcVal,
+                const LogicalExpr &SrcExpr)
+      : Helper(OpsHelper), Val(SrcVal), Expr(SrcExpr) {}
+  ~LogicalOpNode() {}
+
+  Value *getValue() const { return Val; }
+  const LogicalExpr &getExpr() const { return Expr; }
+  void print(raw_ostream &OS) const;
+};
+
+class LogicCombiner {
+public:
+  LogicCombiner() {}
+  ~LogicCombiner() { clear(); }
+
+  Value *simplify(Value *Root);
+
+private:
+  friend class LogicalOpNode;
+
+  SpecificBumpPtrAllocator<LogicalOpNode> Alloc;
+  SmallDenseMap<Value *, LogicalOpNode *, 16> LogicalOpNodes;
+  SmallSetVector<Value *, 8> LeafValues;
+
+  void clear();
+
+  LogicalOpNode *visitLeafNode(Value *Val, unsigned Depth);
+  LogicalOpNode *visitBinOp(BinaryOperator *BO, unsigned Depth);
+  LogicalOpNode *getLogicalOpNode(Value *Val, unsigned Depth = 0);
+  Value *logicalOpToValue(LogicalOpNode *Node);
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const LogicalOpNode &I) {
+  I.print(OS);
+  return OS;
+}
+
+} // namespace llvm

llvm/include/llvm/Analysis/LogicalExpr.h

+//===------------------- LogicalExpr.h --------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file defines LogicalExpr, a class that represent a logical value by
+/// a set of bitsets.
+///
+/// For a logical expression represented by bitset, the "and" logic
+/// operator represented by "&" is translated to "*" and is then evaluated as
+/// the "or" of the bitset. For example, pattern "a & b" is represented by the
+/// logical expression "01 * 10", and the expression is reduced to "11". So the
+/// operation "&" between two logical expressions (not "xor", only "and" chain)
+/// is actually bitwise "or" of the masks. There are two exceptions:
+///    If one of the operands is constant 0, the entire bitset represents 0.
+///    If one of the operands is constant -1, the result is the other one.
+///
+/// The evaluation of a pattern for bitwise "xor" is represented by a "+" math
+/// operator. But it also has one exception to normal math rules: if two masks
+/// are identical, we remove them. For example with "a ^ a", the logical
+/// expression is "1 + 1". We eliminate them from the logical expression.
+///
+/// We use commutative, associative, and distributive laws of arithmetic
+/// multiplication and addition to reduce the expression. An example for the
+/// LogicalExpr caculation:
+///     ((a & b) | (a ^ c)) ^ (!(b & c) & a)
+/// Mask for the leafs are: a --> 001, b --> 010, c -->100
+/// First step is expand the pattern to:
+///      (((a & b) & (a ^ c)) ^ (a & b) ^ (a ^ c)) ^ (((b & c) ^ -1) & a)
+/// Use logical expression to represent the pattern:
+///      001 * 010 * (001 + 100) + 001 * 010 + 001 + 100 + (010 * 100 + -1C) *
+///      001
+/// Expression after distributive laws:
+///      001 * 010 * 001 + 001 * 010 * 100 + 001 * 010 + 001 + 100 + 010 * 100 *
+///      001 + -1C * 001
+/// Calculate multiplication:
+///      011 + 111 + 011 + 001 + 100 + 111 + 001
+/// Calculate addition:
+///      100
+/// Restore to value
+///      c
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseSet.h"
+
+namespace llvm {
+// TODO: can we use APInt define the mask to enlarge the max leaf number?
+typedef SmallDenseSet<uint64_t, 8> ExprAddChain;
+
+class LogicalExpr {
+private:
+  ExprAddChain AddChain;
+
+public:
+  static const uint64_t ExprAllOne = 0x8000000000000000;
+
+  LogicalExpr() {}
+  LogicalExpr(uint64_t BitSet) {
+    if (BitSet != 0)
+      AddChain.insert(BitSet);
+  }
+  LogicalExpr(const ExprAddChain &SrcAddChain) : AddChain(SrcAddChain) {
+  }
+
+  unsigned size() const { return AddChain.size(); }
+  ExprAddChain::iterator begin() { return AddChain.begin(); }
+  ExprAddChain::iterator end() { return AddChain.end(); }
+  ExprAddChain::const_iterator begin() const { return AddChain.begin(); }
+  ExprAddChain::const_iterator end() const { return AddChain.end(); }
+
+  LogicalExpr &operator*=(const LogicalExpr &RHS) {
+    ExprAddChain NewChain;
+    for (auto LHS : AddChain) {
+      for (auto RHS : RHS.AddChain) {
+        uint64_t NewBitSet;
+        // Except the special case one value "*" -1 is just return itself, the
+        // other "*" operation is 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.
+        if (LHS == ExprAllOne)
+          NewBitSet = RHS;
+        else if (RHS == ExprAllOne)
+          NewBitSet = LHS;
+        else
+          NewBitSet = LHS | RHS;
+        assert(NewBitSet == ExprAllOne || (NewBitSet & ExprAllOne) == 0);
+        // a ^ a -> 0
+        auto InsertPair = NewChain.insert(NewBitSet);
+        if (!InsertPair.second)
+          NewChain.erase(InsertPair.first);
+      }
+    }
+
+    AddChain = NewChain;
+    return *this;
+  }
+
+  LogicalExpr &operator+=(const LogicalExpr &RHS) {
+    for (auto RHS : RHS.AddChain) {
+      // a ^ a -> 0
+      auto InsertPair = AddChain.insert(RHS);
+      if (!InsertPair.second)
+        AddChain.erase(InsertPair.first);
+    }
+    return *this;
+  }
+};
+
+inline LogicalExpr operator*(LogicalExpr a, const LogicalExpr &b) {
+  a *= b;
+  return a;
+}
+
+inline LogicalExpr operator+(LogicalExpr a, const LogicalExpr &b) {
+  a += b;
+  return a;
+}
+
+inline LogicalExpr operator&(const LogicalExpr &a, const LogicalExpr &b) {
+  return a * b;
+}
+
+inline LogicalExpr operator^(const LogicalExpr &a, const LogicalExpr &b) {
+  return a + b;
+}
+
+inline LogicalExpr operator|(const LogicalExpr &a, const LogicalExpr &b) {
+  return a * b + a + b;
+}
+
+inline LogicalExpr operator~(const LogicalExpr &a) {
+  LogicalExpr AllOneExpr(LogicalExpr::ExprAllOne);
+  return a + AllOneExpr;
+}
+
+} // namespace llvm

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   LazyBranchProbabilityInfo.cpp
   LazyBlockFrequencyInfo.cpp
   LazyCallGraph.cpp
   LazyValueInfo.cpp
   LegacyDivergenceAnalysis.cpp
   Lint.cpp
   Loads.cpp
   Local.cpp
+  LogicCombine.cpp
   LoopAccessAnalysis.cpp
   LoopAnalysisManager.cpp
   LoopCacheAnalysis.cpp
   LoopNestAnalysis.cpp
   LoopUnrollAnalyzer.cpp
   LoopInfo.cpp
   LoopPass.cpp
   MLInlineAdvisor.cpp

llvm/lib/Analysis/LogicCombine.cpp

+//===--------------------- LogicCombine.cpp -------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file attempts to find the simplest expression for a bitwise logic
+/// operation chain. We canonicalize all other ops to "&"/"^".
+/// For example:
+///    a | b --> (a & b) ^ a ^ b
+///    c ? a : b --> (c & a) ^ ((c ^ true) & b)
+/// We use a set of bitset to represent the expression. Any value that is not a
+/// logic operation is a leaf node. Leaf node is 1 bit in the bitset. For
+/// example, we have source a, b, c. The bit for a is 1, b is 2, c is 4.
+///     a & b & c --> {0b111}
+///     a & b ^ c & a --> {0b011, 0b101}
+///     a & b ^ c & a ^ b --> {0b011, 0b101, 0b010}
+/// Every bitset is an "&" chain. The set of bitset is a "^" chain.
+/// Based on boolean ring, we can treat "&" as ring multiplication and "^" as
+/// ring addition. After that, any logic value can be represented as a chain of
+/// bitsets. For example:
+///     r1 = (a | b) & c -> r1 = (a * b * c) + (a * c) + (b * c) ->
+///     {0b111, 0b101, 0b110}
+/// Finally we need to rebuild the simplest pattern from the expression.
+///
+/// Reference: https://en.wikipedia.org/wiki/Boolean_ring
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LogicCombine.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "logic-combine"
+
+STATISTIC(NumLogicalOpsSimplified, "Number of logical operations simplified");
+
+static cl::opt<unsigned> MaxLogicOpLeafsToScan(
+    "logic-combine-max-leafs", cl::init(8), cl::Hidden,
+    cl::desc("Max leafs of logic ops to scan for logical combine."));
+
+static cl::opt<unsigned> MaxDepthLogicOpsToScan(
+    "logic-combine-max-depth", cl::init(8), cl::Hidden,
+    cl::desc("Max depth of logic ops to scan for logical combine."));
+
+void LogicalOpNode::printAndChain(raw_ostream &OS, uint64_t LeafBits) const {
+  if (LeafBits == LogicalExpr::ExprAllOne) {
+    OS << "-1";
+    return;
+  }
+
+  if (LeafBits == 0)
+    return;
+
+  unsigned LeafCnt = popcount(LeafBits);
+  if (LeafCnt == 1) {
+    Helper->LeafValues[Log2_64(LeafBits)]->printAsOperand(OS, false);
+    return;
+  }
+
+  unsigned LeafIdx;
+  ListSeparator LS(" * ");
+  for (unsigned I = 0; I < LeafCnt; I++) {
+    LeafIdx = countr_zero(LeafBits);
+    OS << LS;
+    Helper->LeafValues[LeafIdx]->printAsOperand(OS, false);
+    LeafBits -= (1ULL << LeafIdx);
+  }
+}
+
+void LogicalOpNode::print(raw_ostream &OS) const {
+  Val->printAsOperand(OS, false);
+  OS << " --> ";
+  if (Expr.size() == 0) {
+    OS << "0\n";
+    return;
+  }
+
+  ListSeparator LS(" + ");
+  for (auto I = Expr.begin(); I != Expr.end(); I++) {
+    OS << LS;
+    printAndChain(OS, *I);
+  }
+
+  OS << "\n";
+}
+
+void LogicCombiner::clear() {
+  LogicalOpNodes.clear();
+  LeafValues.clear();
+}
+
+LogicalOpNode *LogicCombiner::visitLeafNode(Value *Val, unsigned Depth) {
+  // Depth is 0 means the root is not logical operation. We can't
+  // do anything for that.
+  if (Depth == 0 || LeafValues.size() >= MaxLogicOpLeafsToScan)
+    return nullptr;
+
+  uint64_t ExprVal = 1ULL << LeafValues.size();
+  // Constant Zero,AllOne are special leaf nodes. They involve
+  // LogicalExpr's calculation so we must detect them at first.
+  if (auto ConstVal = dyn_cast<ConstantInt>(Val)) {
+    if (ConstVal->isZero())
+      ExprVal = 0;
+    else if (ConstVal->isAllOnesValue())
+      ExprVal = LogicalExpr::ExprAllOne;
+  }
+  if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0)
+    LeafValues.insert(Val);
+  LogicalOpNode *Node =
+      new (Alloc.Allocate()) LogicalOpNode(this, Val, LogicalExpr(ExprVal));
+  LogicalOpNodes[Val] = Node;
+  return Node;
+}
+
+LogicalOpNode *LogicCombiner::visitBinOp(BinaryOperator *BO, unsigned Depth) {
+  if (!BO->isBitwiseLogicOp())
+    return visitLeafNode(BO, Depth);
+
+  LogicalOpNode *LHS = getLogicalOpNode(BO->getOperand(0), Depth + 1);
+  if (LHS == nullptr)
+    return nullptr;
+
+  LogicalOpNode *RHS = getLogicalOpNode(BO->getOperand(1), Depth + 1);
+  if (RHS == nullptr)
+    return nullptr;
+
+  LogicalOpNode *Node;
+  if (BO->getOpcode() == Instruction::And)
+    Node = new (Alloc.Allocate())
+        LogicalOpNode(this, BO, LHS->getExpr() & RHS->getExpr());
+  else if (BO->getOpcode() == Instruction::Or)
+    Node = new (Alloc.Allocate())
+        LogicalOpNode(this, BO, LHS->getExpr() | RHS->getExpr());
+  else
+    Node = new (Alloc.Allocate())
+        LogicalOpNode(this, BO, LHS->getExpr() ^ RHS->getExpr());
+  LogicalOpNodes[BO] = Node;
+  return Node;
+}
+
+LogicalOpNode *LogicCombiner::getLogicalOpNode(Value *Val, unsigned Depth) {
+  if (Depth == MaxDepthLogicOpsToScan)
+    return nullptr;
+
+  if (LogicalOpNodes.find(Val) == LogicalOpNodes.end()) {
+    LogicalOpNode *Node;
+
+    // TODO: add select instruction support
+    if (auto *BO = dyn_cast<BinaryOperator>(Val))
+      Node = visitBinOp(BO, Depth);
+    else
+      Node = visitLeafNode(Val, Depth);
+
+    if (!Node)
+      return nullptr;
+    LLVM_DEBUG(dbgs() << *Node);
+  }
+  return LogicalOpNodes[Val];
+}
+
+Value *LogicCombiner::logicalOpToValue(LogicalOpNode *Node) {
+  const LogicalExpr &Expr = Node->getExpr();
+  // Empty when all leaf bits are erased from the set because a ^ a = 0.
+  if (Expr.size() == 0)
+    return Constant::getNullValue(Node->getValue()->getType());
+
+  if (Expr.size() == 1) {
+    uint64_t LeafBits = *Expr.begin();
+    if (LeafBits == 0)
+      return Constant::getNullValue(Node->getValue()->getType());
+    // ExprAllOne is not in the LeafValues
+    if (LeafBits == LogicalExpr::ExprAllOne)
+      return Constant::getAllOnesValue(Node->getValue()->getType());
+
+    if (popcount(LeafBits) == 1)
+      return LeafValues[Log2_64(LeafBits)];
+  }
+
+  // TODO: find the simplest form from logical expression when it is not
+  // only an "and" chain.
+
+  return nullptr;
+}
+
+Value *LogicCombiner::simplify(Value *Root) {
+  assert(MaxLogicOpLeafsToScan <= 63 &&
+         "Logical leaf node can't be larger than 63.");
+  LogicalOpNode *RootNode = getLogicalOpNode(Root);
+  if (RootNode == nullptr)
+    return nullptr;
+
+  Value *NewRoot = logicalOpToValue(RootNode);
+  if (NewRoot == nullptr || NewRoot == Root)
+    return nullptr;
+
+  LogicalOpNodes.erase(Root);
+  NumLogicalOpsSimplified++;
+  return NewRoot;
+}

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp

 
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
 #include "AggressiveInstCombineInternal.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/LogicCombine.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/PatternMatch.h"
static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL,
   // shift if not zero.
   if (LOps.Shift)
     NewOp = Builder.CreateShl(NewOp, LOps.Shift);
   I.replaceAllUsesWith(NewOp);
 
   return true;
 }
 
+/// Reduce bitwise logic sequences.
+static bool foldBitwiseLogic(Function &F, DominatorTree &DT) {
+  bool MadeChange = false;
+  for (BasicBlock &BB : F) {
+    // Ignore unreachable basic blocks.
+    if (!DT.isReachableFromEntry(&BB))
+      continue;
+
+    // TODO: Combining at the function-level would allow more caching of nodes
+    // which saves on compile-time, but it may hit the max value limits before
+    // finding a solution. We could split the combiner based on types to make
+    // the code more efficient, adjust the value of max depth/values, or use
+    // APInt to support tracking more than 63 leaf values.
+    LogicCombiner LC;
+    for (Instruction &I : BB) {
+      if (I.isBitwiseLogicOp()) {
+        Value *NewV = LC.simplify(&I);
+        if (NewV) {
+          MadeChange = true;
+          I.replaceAllUsesWith(NewV);
+        }
+      }
+    }
+  }
+  return MadeChange;
+}
+
 /// This is the entry point for folds that could be implemented in regular
 /// InstCombine, but they are separated because they are not expected to
 /// occur frequently and/or have more than a constant-length pattern match.
 static bool foldUnusualPatterns(Function &F, DominatorTree &DT,
                                 TargetTransformInfo &TTI,
                                 TargetLibraryInfo &TLI, AliasAnalysis &AA) {
-  bool MadeChange = false;
+  bool MadeChange = foldBitwiseLogic(F, DT);
   for (BasicBlock &BB : F) {
     // Ignore unreachable basic blocks.
     if (!DT.isReachableFromEntry(&BB))
       continue;
 
     const DataLayout &DL = F.getParent()->getDataLayout();
 
     // Walk the block backwards for efficiency. We're matching a chain of
     // use->defs, so we're more likely to succeed by starting from the bottom.
     // Also, we want to avoid matching partial patterns.
     // TODO: It would be more efficient if we removed dead instructions
     // iteratively in this loop rather than waiting until the end.
     for (Instruction &I : make_early_inc_range(llvm::reverse(BB))) {
       MadeChange |= foldAnyOrAllBitsSet(I);
       MadeChange |= foldGuardedFunnelShift(I, DT);
       MadeChange |= tryToRecognizePopCount(I);
       MadeChange |= tryToFPToSat(I, TTI);
       MadeChange |= tryToRecognizeTableBasedCttz(I);
       MadeChange |= foldConsecutiveLoads(I, DL, TTI, AA);
       // NOTE: This function introduces erasing of the instruction `I`, so it
       // needs to be called at the end of this sequence, otherwise we may make
       // bugs.
       MadeChange |= foldSqrt(I, TTI, TLI);
     }
   }
 
   // We're done with transforms, so remove dead instructions.
   if (MadeChange)
     for (BasicBlock &BB : F)
       SimplifyInstructionsInBlock(&BB);
 
   return MadeChange;

llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s
+; RUN: opt < %s -passes=aggressive-instcombine -logic-combine-max-depth=6 -S | FileCheck %s
 
 define i8 @leaf1_and_aa(i8 %a)  {
 ; CHECK-LABEL: @leaf1_and_aa(
-; CHECK-NEXT:    [[AND_AA:%.*]] = and i8 [[A:%.*]], [[A]]
-; CHECK-NEXT:    ret i8 [[AND_AA]]
+; CHECK-NEXT:    ret i8 [[A:%.*]]
 ;
   %and.aa = and i8 %a, %a
   ret i8 %and.aa
 }
 
 define i8 @leaf1_and_a_false(i8 %a)  {
 ; CHECK-LABEL: @leaf1_and_a_false(
-; CHECK-NEXT:    [[AND_AA:%.*]] = and i8 [[A:%.*]], 0
-; CHECK-NEXT:    ret i8 [[AND_AA]]
+; CHECK-NEXT:    ret i8 0
 ;
   %and.aa = and i8 %a, 0
   ret i8 %and.aa
 }
 
 define i8 @leaf1_xor_aa(i8 %a)  {
 ; CHECK-LABEL: @leaf1_xor_aa(
-; CHECK-NEXT:    [[XOR_AA:%.*]] = xor i8 [[A:%.*]], [[A]]
-; CHECK-NEXT:    ret i8 [[XOR_AA]]
+; CHECK-NEXT:    ret i8 0
 ;
   %xor.aa = xor i8 %a, %a
   ret i8 %xor.aa
 }
 
 define i8 @leaf1_and_not(i8 %a)  {
 ; CHECK-LABEL: @leaf1_and_not(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i8 [[A:%.*]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A]], [[NOT_A]]
-; CHECK-NEXT:    ret i8 [[AND]]
+; CHECK-NEXT:    ret i8 0
 ;
   %not.a = xor i8 %a, -1
   %and = and i8 %a, %not.a
   ret i8 %and
 }
 
 define i8 @leaf1_or_not(i8 %a)  {
 ; CHECK-LABEL: @leaf1_or_not(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i8 [[A:%.*]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[A]], [[NOT_A]]
-; CHECK-NEXT:    ret i8 [[OR]]
+; CHECK-NEXT:    ret i8 -1
 ;
   %not.a = xor i8 %a, -1
   %or = or i8 %a, %not.a
   ret i8 %or
 }
 
 define i8 @leaf2_xor(i8 %a, i8 %b)  {
 ; CHECK-LABEL: @leaf2_xor(
-; CHECK-NEXT:    [[AB:%.*]] = xor i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[XOR_AB_A:%.*]] = xor i8 [[AB]], [[A]]
-; CHECK-NEXT:    ret i8 [[XOR_AB_A]]
+; CHECK-NEXT:    ret i8 [[B:%.*]]
 ;
   %ab = xor i8 %a, %b
   %xor.ab.a = xor i8 %ab, %a
   ret i8 %xor.ab.a
 }
 
 define i8 @leaf2_xor_ret_const_false(i8 %a, i8 %b)  {
 ; CHECK-LABEL: @leaf2_xor_ret_const_false(
-; CHECK-NEXT:    [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[XOR_AB_A:%.*]] = xor i8 [[XOR_AB]], [[A]]
-; CHECK-NEXT:    [[XOR_AB_A_B:%.*]] = xor i8 [[XOR_AB_A]], [[B]]
-; CHECK-NEXT:    ret i8 [[XOR_AB_A_B]]
+; CHECK-NEXT:    ret i8 0
 ;
   %xor.ab = xor i8 %a, %b
   %xor.ab.a = xor i8 %xor.ab, %a
   %xor.ab.a.b = xor i8 %xor.ab.a, %b
   ret i8 %xor.ab.a.b
 }
 
 define i8 @leaf2_or_ret_leaf(i8 %a, i8 %b)  {
 ; CHECK-LABEL: @leaf2_or_ret_leaf(
-; CHECK-NEXT:    [[OR_AB:%.*]] = or i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[AND_AB:%.*]] = and i8 [[A]], [[B]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i8 [[OR_AB]], [[AND_AB]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i8 [[XOR1]], [[A]]
-; CHECK-NEXT:    ret i8 [[XOR2]]
+; CHECK-NEXT:    ret i8 [[B:%.*]]
 ;
   %or.ab = or i8 %a, %b
   %and.ab = and i8 %a, %b
   %xor1 = xor i8 %or.ab, %and.ab
   %xor2 = xor i8 %xor1, %a
   ret i8 %xor2
 }
 
 define i8 @leaf2_or_ret_const_false(i8 %a, i8 %b)  {
 ; CHECK-LABEL: @leaf2_or_ret_const_false(
-; CHECK-NEXT:    [[OR_AB:%.*]] = or i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[AND_AB:%.*]] = and i8 [[A]], [[B]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i8 [[OR_AB]], [[AND_AB]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i8 [[XOR1]], [[A]]
-; CHECK-NEXT:    [[XOR3:%.*]] = xor i8 [[XOR1]], [[B]]
-; CHECK-NEXT:    ret i8 [[XOR3]]
+; CHECK-NEXT:    ret i8 0
 ;
   %or.ab = or i8 %a, %b
   %and.ab = and i8 %a, %b
   %xor1 = xor i8 %or.ab, %and.ab
   %xor2 = xor i8 %xor1, %a
-  %xor3 = xor i8 %xor1, %b
+  %xor3 = xor i8 %xor2, %b
   ret i8 %xor3
 }
 
 define i1 @leaf2_type_is_i1(i1 %a, i1 %b) {
 ; CHECK-LABEL: @leaf2_type_is_i1(
-; CHECK-NEXT:    [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A]], true
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i1 [[NOT_A]], [[B]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[XOR2]], [[XOR_AB]]
-; CHECK-NEXT:    ret i1 [[OR]]
+; CHECK-NEXT:    ret i1 true
 ;
   %xor.ab = xor i1 %a, %b
   %not.a = xor i1 %a, true
   %xor2 = xor i1 %not.a, %b
   %or = or i1 %xor2, %xor.ab
   ret i1 %or
 }
 
 define i8 @leaf3_complex_ret_const_false(i8 %a, i8 %b, i8 %c)  {
 ; CHECK-LABEL: @leaf3_complex_ret_const_false(
-; CHECK-NEXT:    [[AB:%.*]] = or i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ABC:%.*]] = or i8 [[AB]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT_ABC:%.*]] = xor i8 [[ABC]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[NOT_ABC]], [[A]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %ab = or i8 %a, %b
   %abc = or i8 %ab, %c
   %not.abc = xor i8 %abc, -1
   %r = and i8 %not.abc, %a
   ret i8 %r
 }
 
 define i8 @leaf3_complex_ret_leaf(i8 %a, i8 %b, i8 %c) {
 ; CHECK-LABEL: @leaf3_complex_ret_leaf(
-; CHECK-NEXT:    [[AB:%.*]] = and i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[BC:%.*]] = and i8 [[B]], [[C:%.*]]
-; CHECK-NEXT:    [[XOR_AC:%.*]] = xor i8 [[A]], [[C]]
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[AB]], [[XOR_AC]]
-; CHECK-NEXT:    [[NOT_BC:%.*]] = xor i8 [[BC]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[NOT_BC]], [[A]]
-; CHECK-NEXT:    [[COND:%.*]] = xor i8 [[AND]], [[OR]]
-; CHECK-NEXT:    ret i8 [[COND]]
+; CHECK-NEXT:    ret i8 [[C:%.*]]
 ;
   %ab = and i8 %a, %b
   %bc = and i8 %b, %c
   %xor.ac = xor i8 %a, %c
   %or = or i8 %ab, %xor.ac
   %not.bc = xor i8 %bc, -1
   %and = and i8 %not.bc, %a
   %cond = xor i8 %and, %or
   ret i8 %cond
 }
 
 define i8 @leaf4_ret_const_true(i8 %a, i8 %b, i8 %c, i8 %d)  {
 ; CHECK-LABEL: @leaf4_ret_const_true(
-; CHECK-NEXT:    [[BD:%.*]] = and i8 [[B:%.*]], [[D:%.*]]
-; CHECK-NEXT:    [[NOT_BD:%.*]] = xor i8 [[BD]], -1
-; CHECK-NEXT:    [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i8 [[XOR_AB]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[OR1]], [[NOT_BD]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i8 [[OR2]], [[A]]
-; CHECK-NEXT:    ret i8 [[OR3]]
+; CHECK-NEXT:    ret i8 -1
 ;
   %bd = and i8 %b, %d
   %not.bd = xor i8 %bd, -1
   %xor.ab = xor i8 %a, %b
   %or1 = or i8 %xor.ab, %c
   %or2 = or i8 %or1, %not.bd
   %or3 = or i8 %or2, %a
   ret i8 %or3
 }
 
 define i8 @leaf4_ret_leaf(i8 %a, i8 %b, i8 %c, i8 %d)  {
 ; CHECK-LABEL: @leaf4_ret_leaf(
-; CHECK-NEXT:    [[BD:%.*]] = and i8 [[B:%.*]], [[D:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[BD]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT_BD:%.*]] = xor i8 [[XOR]], -1
-; CHECK-NEXT:    [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i8 [[XOR_AB]], [[C]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[OR1]], [[NOT_BD]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i8 [[OR2]], [[A]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[OR3]], [[B]]
-; CHECK-NEXT:    ret i8 [[AND]]
+; CHECK-NEXT:    ret i8 [[B:%.*]]
 ;
   %bd = and i8 %b, %d
   %xor = xor i8 %bd, %c
   %not.bd = xor i8 %xor, -1
   %xor.ab = xor i8 %a, %b
   %or1 = or i8 %xor.ab, %c
   %or2 = or i8 %or1, %not.bd
   %or3 = or i8 %or2, %a
   %and = and i8 %or3, %b
   ret i8 %and
 }
 
 define i8 @leaf4_ret_leaf2(i8 %a, i8 %b, i8 %c, i8 %d)  {
 ; CHECK-LABEL: @leaf4_ret_leaf2(
-; CHECK-NEXT:    [[BD:%.*]] = and i8 [[B:%.*]], [[D:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[BD]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT_BD:%.*]] = xor i8 [[XOR]], -1
-; CHECK-NEXT:    [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B]]
-; CHECK-NEXT:    [[OR1:%.*]] = or i8 [[XOR_AB]], [[C]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i8 [[OR1]], [[NOT_BD]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i8 [[OR2]], [[A]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[OR3]], [[B]]
-; CHECK-NEXT:    ret i8 [[AND]]
+; CHECK-NEXT:    ret i8 [[B:%.*]]
 ;
   %bd = and i8 %b, %d
   %xor = xor i8 %bd, %c
   %not.bd = xor i8 %xor, -1
   %xor.ab = xor i8 %a, %b
   %or1 = or i8 %xor.ab, %c
   %or2 = or i8 %or1, %not.bd
   %or3 = or i8 %or2, %a
   %and = and i8 %or3, %b
   ret i8 %and
 }
+
+; Negative test case 1 for max leaf number:
+; This case's max leaf number is 9, if we adjust max depth limitation
+; to larger than 8, it will return %a1
+
+define i8 @leaf8_negative_leafnum(i8 %a1, i8 %a2, i8 %a3, i8 %a4, i8 %a5, i8 %a6, i8 %a7, i8 %a8, i8 %a9)  {
+; CHECK-LABEL: @leaf8_negative_leafnum(
+; CHECK-NEXT:    [[A12:%.*]] = xor i8 [[A1:%.*]], [[A2:%.*]]
+; CHECK-NEXT:    [[A34:%.*]] = xor i8 [[A3:%.*]], [[A4:%.*]]
+; CHECK-NEXT:    [[A56:%.*]] = xor i8 [[A5:%.*]], [[A6:%.*]]
+; CHECK-NEXT:    [[A78:%.*]] = xor i8 [[A7:%.*]], [[A8:%.*]]
+; CHECK-NEXT:    [[A14:%.*]] = xor i8 [[A12]], [[A34]]
+; CHECK-NEXT:    [[A58:%.*]] = xor i8 [[A56]], [[A78]]
+; CHECK-NEXT:    [[A18:%.*]] = xor i8 [[A14]], [[A58]]
+; CHECK-NEXT:    [[A19:%.*]] = xor i8 [[A18]], [[A9:%.*]]
+; CHECK-NEXT:    [[A23:%.*]] = xor i8 [[A2]], [[A3]]
+; CHECK-NEXT:    [[A45:%.*]] = xor i8 [[A4]], [[A5]]
+; CHECK-NEXT:    [[A67:%.*]] = xor i8 [[A6]], [[A7]]
+; CHECK-NEXT:    [[A89:%.*]] = xor i8 [[A8]], [[A9]]
+; CHECK-NEXT:    [[A25:%.*]] = xor i8 [[A23]], [[A45]]
+; CHECK-NEXT:    [[A69:%.*]] = xor i8 [[A67]], [[A89]]
+; CHECK-NEXT:    [[A29:%.*]] = xor i8 [[A25]], [[A69]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A19]], [[A29]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %a12 = xor i8 %a1, %a2
+  %a34 = xor i8 %a3, %a4
+  %a56 = xor i8 %a5, %a6
+  %a78 = xor i8 %a7, %a8
+  %a14 = xor i8 %a12, %a34
+  %a58 = xor i8 %a56, %a78
+  %a18 = xor i8 %a14, %a58
+  %a19 = xor i8 %a18, %a9
+  %a23 = xor i8 %a2, %a3
+  %a45 = xor i8 %a4, %a5
+  %a67 = xor i8 %a6, %a7
+  %a89 = xor i8 %a8, %a9
+  %a25 = xor i8 %a23, %a45
+  %a69 = xor i8 %a67, %a89
+  %a29 = xor i8 %a25, %a69
+  %r = xor i8 %a19, %a29
+  ret i8 %r
+}
+
+; Negative test case 2 for max leaf number:
+; Constant value is also a leaf node.
+
+define i8 @leaf8_negative_leafnum_const(i8 %a1, i8 %a2)  {
+; CHECK-LABEL: @leaf8_negative_leafnum_const(
+; CHECK-NEXT:    [[AND1:%.*]] = and i8 [[A1:%.*]], 1
+; CHECK-NEXT:    call void @use8(i8 [[AND1]])
+; CHECK-NEXT:    [[AND2:%.*]] = and i8 [[A1]], 2
+; CHECK-NEXT:    call void @use8(i8 [[AND2]])
+; CHECK-NEXT:    [[AND3:%.*]] = and i8 [[A1]], 3
+; CHECK-NEXT:    call void @use8(i8 [[AND3]])
+; CHECK-NEXT:    [[AND4:%.*]] = and i8 [[A1]], 4
+; CHECK-NEXT:    call void @use8(i8 [[AND4]])
+; CHECK-NEXT:    [[AND5:%.*]] = and i8 [[A1]], 5
+; CHECK-NEXT:    call void @use8(i8 [[AND5]])
+; CHECK-NEXT:    [[AND6:%.*]] = and i8 [[A1]], 6
+; CHECK-NEXT:    call void @use8(i8 [[AND6]])
+; CHECK-NEXT:    [[AND7:%.*]] = and i8 [[A1]], 7
+; CHECK-NEXT:    call void @use8(i8 [[AND7]])
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A2:%.*]], [[A2]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %and1 = and i8 %a1, 1
+  call void @use8(i8 %and1)
+  %and2 = and i8 %a1, 2
+  call void @use8(i8 %and2)
+  %and3 = and i8 %a1, 3
+  call void @use8(i8 %and3)
+  %and4 = and i8 %a1, 4
+  call void @use8(i8 %and4)
+  %and5 = and i8 %a1, 5
+  call void @use8(i8 %and5)
+  %and6 = and i8 %a1, 6
+  call void @use8(i8 %and6)
+  %and7 = and i8 %a1, 7
+  call void @use8(i8 %and7)
+  %r = xor i8 %a2, %a2
+  ret i8 %r
+}
+
+declare void @use8(i8)