I'm sorry I have no time to continue this work. So I will abandon this. Anyone who want to continue work on this is fine.

address comments.

update test result.

In D148463#4281590, @rampitec wrote:

Did you find what DAG transformation undoes this? It might be better to tweak that one instead.

This is a general solution for regression of D148463.

Ping.

rebase the code

I have already revert it on rG9356097206a17
Can someone help to review the new patch?

limit the optimization to non-constant value to workaround dead loop.

rebase precommit tests.

rebase code

We can extend it to and also:

How about this pattern ?
https://alive2.llvm.org/ce/z/Y-Po8g
Also reduce one usage but it works for any minuend.

Maybe we need two more tests here:

1. Not one-use test .
2. Vector test with poison constant.

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

In D145772#4184090, @nikic wrote:

I think it's long overdue to canonicalize three-way comparisons in some way. Looking at asm for different backends, it does look like this representation is pretty much universally better than the select form. I'm less sure whether this is ideal for middle-end optimization.

Something I'm wondering is whether it might make sense to recognize this as a first-class pattern and actually introduce an iN @llvm.compare.iN.iM(iM %a, iM %b) intrinsic for this purpose.

In D145772#4192188, @nikic wrote:

Was this abandoned because it breaks some of the existing optimizations? For the record, this is how the compare-3way.ll test diff looks like: https://gist.github.com/nikic/056516a0d621f9ca69059d05eef7e7b2

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?

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.

rebase

Ping.

any other coments for the initial patch? @nikic

In D142803#4156027, @aeubanks wrote:

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

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

remove leafmask

rebase

rebase

rebase

code clean

minor bug fix.

use SpecificBumpPtrAllocator

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.

Address comments.

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;

Remove leafset.

Address comments.