[Transforms] Adding a WeakReassociate pass

[opaparo]

Summary

A discussion that started at D38037 raised the need for a new reassociation pass, in addition to the existing one.

The existing pass takes a tree of a reassociable operator, and transforms it into a "linear tree", e.g. for addition a_0 + (a_1 + (a_2 + ... (a_n-1 + a_n))...). The tree is built such that the latter operands have lower "ranks". The ranking is such that, for example, constants have rank of zero which means they will be at the end of the tree which will cause them to eventually fold.
The new pass implements another kind of reassociation, something of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3), which is not supported by the existing pass.
The new pass also limited in numerous ways (hence "Weak"): it will only reassociate a tree compound of two kinds of leaves by putting all the leaves of one kind ("LeafClass") in one subtree and the leaves from the other kind at the second subtree. It will also never change the topography of the tree (unlike the existing reassociate pass which aggressively dictates a new topography). That means, amongst the rest, that this pass never creates new instructions.

[opaparo]

Now using the constant's value rather than its pointer value for enforcing total order on LeafClasses. This is needed in order to ensure deterministic output of the compiler (I actually got different results when running with different OSs before this change).

[davide]

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

[opaparo]

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

[davide]

In D41574#964111, @opaparo wrote:

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

(Only trying to understand) From what I see the main consumers of reassociation are Global Value Numbering to discover more equivalences and instruction combining.
The former can probably embed reassociation while performing equivalence finding (in fact, there are algorithms where this happens), the latter already performs a fair amount of "canonicalization" (sometimes, too much). I wonder where your pass fits/what's the use case? Do you plan to enable it as part of the default pipeline?

Thanks,

Davide

[opaparo]

In D41574#964124, @davide wrote:

In D41574#964111, @opaparo wrote:

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

(Only trying to understand) From what I see the main consumers of reassociation are Global Value Numbering to discover more equivalences and instruction combining.
The former can probably embed reassociation while performing equivalence finding (in fact, there are algorithms where this happens), the latter already performs a fair amount of "canonicalization" (sometimes, too much). I wonder where your pass fits/what's the use case? Do you plan to enable it as part of the default pipeline?

Thanks,

Davide

The new pass is a kind of preparation pass for InstCombine. It complements changes introduced at D39421, as well as other InstCombine transformations. Checkout my lit tests, they illustrate several scenarios.
I believe that this pass will open a gate to other reassociations required by InstCombine transformations, reassociations that can't be expressed in means of the existing Reassociate pass.

[opaparo]

In D41574#964524, @opaparo wrote:

In D41574#964124, @davide wrote:

In D41574#964111, @opaparo wrote:

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

(Only trying to understand) From what I see the main consumers of reassociation are Global Value Numbering to discover more equivalences and instruction combining.
The former can probably embed reassociation while performing equivalence finding (in fact, there are algorithms where this happens), the latter already performs a fair amount of "canonicalization" (sometimes, too much). I wonder where your pass fits/what's the use case? Do you plan to enable it as part of the default pipeline?

Thanks,

Davide

The new pass is a kind of preparation pass for InstCombine. It complements changes introduced at D39421, as well as other InstCombine transformations. Checkout my lit tests, they illustrate several scenarios.
I believe that this pass will open a gate to other reassociations required by InstCombine transformations, reassociations that can't be expressed in means of the existing Reassociate pass.

@davide, does that answer your questions? Do you have any additional concerns?

[opaparo]

Ping

[opaparo]

Following this discussion, rebasing the patch to trunk.

[lebedev.ri]

lib/Transforms/Scalar/WeakReassociate.cpp

136

Consider passing SmallVectorImpl<unsigned> to avoid adding noise in form of size.

139

I think you may want to suffix that one with U https://godbolt.org/g/FDQPax
Or maybe there is some helper function to do that?

155–156

Consider passing SmallVectorImpl<> to avoid adding noise in form of size.

210

You could do std::stack<BinaryOperator *, SmallVector<BinaryOperator *, 4>> to still make use of SSO

240

Do you actually need to specify the type here?

249–250

I *think* this is the only use of i?
wouldn't

for (Value *Operand : PrevDepthNode->operands())

work?

264

Wouldn't just NonLeaves.push_back({}); work?

284

Humm, have you considered [[ https://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h | llvm::DenseMap<> ]]?

286

Couldn't this be range-for loop?

[lebedev.ri]

lib/Transforms/Scalar/WeakReassociate.cpp

104

It is hopefully nothing, but what if they compare equal?
I'm basically thinking about the llvm::sort() being intentionally unstable kind of things.

[hjyamauchi]

lib/Transforms/IPO/PassManagerBuilder.cpp

413

If we add it here, should we also add it in the corresponding location in PassBuilder::buildFunctionSimplificationPipeline (lib/Passes/PassBuilder.cpp) for the new pass manager?

[mzolotukhin]

What are benchmarks results with this pass (compile-time/performance)? Do we really need it at all optlevels, or can we only include it at -O3?

[opaparo]

Several changes in this revision:

1. The pass now extends PassInfoMixin<> instead of FunctionPass. A wrapper legacy pass that extends FunctionPass was also added.
2. The pass is now also used in the PassBuilder::buildFunctionSimplificationPipeline flow.
3. Style:
   • Using SmallVectorImpl instead of SmallVector when possible, in order to avoid explicitly stating its size.
   • Using SmallVectorImpl instead of SmallVector when possible, in order to avoid explicitly stating its size.
   • Other miscellaneous small fixes following code review comments.

[opaparo]

In D41574#1110465, @mzolotukhin wrote:

What are benchmarks results with this pass (compile-time/performance)? Do we really need it at all optlevels, or can we only include it at -O3?

I've got some minor compile time regressions on my benchmarks, but nothing significant.
Judging by this ongoing discussion, this pass can potentially become a complimentary pass to InstCombine. If that will be the case, it should be active in all opt levels.

lib/Transforms/Scalar/WeakReassociate.cpp

104

If they compare equal then they are the same LeafClass, and should correspond to the same cell in the map.
I've indeed had some trouble with stable sorting in the past, and that's exactly why the Op1s of the two sides are compared by value and not by pointer (which may lead to different outcomes on different platforms or even consecutive runs on the same machine).

210

Done, but just so I'm sure - what does SSO stand for?

284

I've tried it.
The thing is that llvm::DenseMap does not guarantee the order of the elements, unlike std::map. It of course guarantees that two different key types will be mapped to two different cells in the map, but when iterating over it (as I do later on) you can get any order. When experimenting with it, I got two different iterating orders in two different runs, which resulted in different code in each run.
Technically I could use llvm::sort after I'm done filling the map, but I find it strange to do that instead of using a data structure that already keeps the elements sorted.

[opaparo]

Ping.

[xbolva00]

Please rebase + more tests

[opaparo]

Rebased and added lit tests

[opaparo]

In D41574#972358, @opaparo wrote:

In D41574#964524, @opaparo wrote:

In D41574#964124, @davide wrote:

In D41574#964111, @opaparo wrote:

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

(Only trying to understand) From what I see the main consumers of reassociation are Global Value Numbering to discover more equivalences and instruction combining.
The former can probably embed reassociation while performing equivalence finding (in fact, there are algorithms where this happens), the latter already performs a fair amount of "canonicalization" (sometimes, too much). I wonder where your pass fits/what's the use case? Do you plan to enable it as part of the default pipeline?

Thanks,

Davide

The new pass is a kind of preparation pass for InstCombine. It complements changes introduced at D39421, as well as other InstCombine transformations. Checkout my lit tests, they illustrate several scenarios.
I believe that this pass will open a gate to other reassociations required by InstCombine transformations, reassociations that can't be expressed in means of the existing Reassociate pass.

@davide, does that answer your questions? Do you have any additional concerns?

@davide, unless you have any additional concerns, do you mind removing the "needs revision" mark in order to avoid discouraging others from reviewing this change?

[lebedev.ri]

Some remarks:

1. It currently runs *after* instcombine. Is that intentional? Didn't you say it is a preparation pass?
2. local_unnamed_addr and #0 in tests isn't needed.
3. Please run -instnamer on the tests, i.e. s/%/%t/ (name all variables.).
4. It is not ideal to test anything more than just the -weak-reassociate in the test/Transforms/WeakReassociate/ (i.e. would be best to drop -instcombine from run lines)

include/llvm/InitializePasses.h

 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);
 void initializeUnifyFunctionExitNodesPass(PassRegistry&);
 void initializeUnpackMachineBundlesPass(PassRegistry&);
 void initializeUnreachableBlockElimLegacyPassPass(PassRegistry&);
 void initializeUnreachableMachineBlockElimPass(PassRegistry&);
 void initializeVerifierLegacyPassPass(PassRegistry&);
 void initializeVirtRegMapPass(PassRegistry&);
 void initializeVirtRegRewriterPass(PassRegistry&);
+void initializeWeakReassociateLegacyPassPass(PassRegistry&);
 void initializeWasmEHPreparePass(PassRegistry&);
 void initializeWholeProgramDevirtPass(PassRegistry&);
 void initializeWinEHPreparePass(PassRegistry&);
 void initializeWriteBitcodePassPass(PassRegistry&);
 void initializeWriteThinLTOBitcodePass(PassRegistry&);
 void initializeXRayInstrumentationPass(PassRegistry&);
 
 } // end namespace llvm
 
 #endif // LLVM_INITIALIZEPASSES_H

include/llvm/Transforms/Scalar.h

 // is designed to promote better constant propagation, GCSE, LICM, PRE...
 //
 // For example:  4 + (x + 5)  ->  x + (4 + 5)
 //
 FunctionPass *createReassociatePass();
 
 //===----------------------------------------------------------------------===//
 //
+// WeakReassociate - This pass reassociates commutative expressions in an order
+// that is designed to promote better instruction combining.
+//
+// For example: (x << 6 | y >> 1) | (z << 6 | w >> 1) ->
+//              (x << 6 | z << 6) | (y >> 1 | w >> 1)
+//
+// This pass will not change the topography of the tree. That means, amongst the
+// rest, that this pass never creates new instructions.
+//
+FunctionPass *createWeakReassociatePass();
+
+//===----------------------------------------------------------------------===//
+//
 // JumpThreading - Thread control through mult-pred/multi-succ blocks where some
 // preds always go to some succ. Thresholds other than minus one override the
 // internal BB duplication default threshold.
 //
 FunctionPass *createJumpThreadingPass(int Threshold = -1);
 
 //===----------------------------------------------------------------------===//
 //

include/llvm/Transforms/Scalar/WeakReassociate.h

+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Pass.h"
+
+#define DEBUG_TYPE "weak-reassociate"
+
+namespace llvm {
+/// Reassociate commutative expressions.
+class WeakReassociatePass
+    : public PassInfoMixin<WeakReassociatePass> {
+  /// Tries to optimizae an instruction by re-associating its operands.
+  /// This function will succeed only if:
+  /// 1. The instruction's type is not i1.
+  /// 2. The instruction is associative.
+  /// 3. The instruction is the root of its opcode tree.
+  /// If all of the above hold, a call to WeakReassociatePass::RewriteExprTree
+  /// will be made.
+  ///
+  /// \param I The instruction to optimize
+  ///
+  /// \returns true iff successfuly optimized \p I
+  bool OptimizeInst(Instruction *I);
+  /// Rewrite an expression tree for an associative instructions tree root
+  /// instruction.
+  /// This function tried to partition the leaves of this tree into two sets, a
+  /// blue set and a red set, according to their opcodes and used constants. If
+  /// it succeeds it will re-arrange the tree such that all of the blue operands
+  /// will be in one side of the tree, and all of the red operands will be in
+  /// the other side of the tree.
+  ///
+  /// \param I An associative instructions tree root instruction.
+  ///
+  /// \returns true iff rewriting of the expression tree succeeded.
+  bool RewriteExprTree(BinaryOperator *I);
+  /// Given an associative instructions tree root instruction, this function
+  /// will return all the nodes of the tree. It may fail if the depth of the
+  /// tree is too big or there are too many leaves.
+  ///
+  /// \param I An associative instructions tree root instruction.
+  /// \param[out] NonLeaves All of the inner nodes of the tree.
+  /// \param[out] Leaves All of the leaves of the tree.
+  ///
+  /// \return true iff successfully got all of the nodes of the tree.
+  bool getTreeNodes(BinaryOperator *I,
+                    SmallVectorImpl<SmallVector<BinaryOperator *, 8>> &NonLeaves,
+                    SmallVectorImpl<Value *> &Leaves);
+
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
+};
+} // namespace llvm

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Scalar/SROA.h"
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/Sink.h"
 #include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
+#include "llvm/Transforms/Scalar/WeakReassociate.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LowerInvoke.h"
 #include "llvm/Transforms/Utils/Mem2Reg.h"
PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
   for (auto &C : ScalarOptimizerLateEPCallbacks)
     C(FPM, Level);
 
   // Finally, do an expensive DCE pass to catch all the dead code exposed by
   // the simplifications and basic cleanup after all the simplifications.
   FPM.addPass(ADCEPass());
   FPM.addPass(SimplifyCFGPass());
   FPM.addPass(InstCombinePass());
+  FPM.addPass(WeakReassociatePass());
   invokePeepholeEPCallbacks(FPM, Level);
 
   return FPM;
 }
 
 void PassBuilder::addPGOInstrPasses(ModulePassManager &MPM, bool DebugLogging,
                                     PassBuilder::OptimizationLevel Level,
                                     bool RunProfileGen,

lib/Transforms/IPO/PassManagerBuilder.cpp

if (RerollLoops)
     MPM.add(createLoopRerollPass());
   if (!RunSLPAfterLoopVectorization && SLPVectorize)
     MPM.add(createSLPVectorizerPass()); // Vectorize parallel scalar chains.
 
   MPM.add(createAggressiveDCEPass());         // Delete dead instructions
   MPM.add(createCFGSimplificationPass()); // Merge & remove BBs
   // Clean up after everything.
   addInstructionCombiningPass(MPM);
+  MPM.add(createWeakReassociatePass());           // Reassociate expressions
   addExtensionsToPM(EP_Peephole, MPM);
 }
 
 void PassManagerBuilder::populateModulePassManager(
     legacy::PassManagerBase &MPM) {
   if (!PGOSampleUse.empty()) {
     MPM.add(createPruneEHPass());
     MPM.add(createSampleProfileLoaderPass(PGOSampleUse));

lib/Transforms/Scalar/CMakeLists.txt

add_llvm_library(LLVMScalarOpts
   SimpleLoopUnswitch.cpp
   SimplifyCFGPass.cpp
   Sink.cpp
   SpeculativeExecution.cpp
   SpeculateAroundPHIs.cpp
   StraightLineStrengthReduce.cpp
   StructurizeCFG.cpp
   TailRecursionElimination.cpp
+  WeakReassociate.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Scalar
 
   DEPENDS
   intrinsics_gen
   )

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializePlaceSafepointsPass(Registry);
   initializeFloat2IntLegacyPassPass(Registry);
   initializeLoopDistributeLegacyPass(Registry);
   initializeLoopLoadEliminationPass(Registry);
   initializeLoopSimplifyCFGLegacyPassPass(Registry);
   initializeLoopVersioningPassPass(Registry);
   initializeEntryExitInstrumenterPass(Registry);
   initializePostInlineEntryExitInstrumenterPass(Registry);
+  initializeWeakReassociateLegacyPassPass(Registry);
 }
 
 void LLVMAddLoopSimplifyCFGPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createLoopSimplifyCFGPass());
 }
 
 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));

lib/Transforms/Scalar/WeakReassociate.cpp

+//===-------- WeakReassociate.cpp - Reassociate binary expressions --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass reassociates commutative expressions in an order that is designed
+// to promote better instruction combining.
+//
+// For example: (x << 6 | y >> 1) | (z << 6 | w >> 1) ->
+//              (x << 6 | z << 6) | (y >> 1 | w >> 1)
+//
+// In the implementation of this algorithm, all leafs are divided into leaf
+// classes according to their opcodes and constants (if applicable), and iff
+// there are exactly two leaf classes ("Blue" and "Red"), the tree will be
+// reassociated such that one side will contain only Blue leaves and the other
+// will contain only Red leaves.
+// This pass will not change the topography of the tree. That means, amongst the
+// rest, that this pass never creates new instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/WeakReassociate.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include <map>
+#include <stack>
+using namespace llvm;
+
+#define DEBUG_TYPE "weak-reassociate"
+
+/// An associative instructions tree leaf class. A class of a leaf will
+/// represent its new position in the tree after the optimization.
+struct LeafClass {
+  Instruction::BinaryOps Opcode;
+  ConstantInt *Op1;
+};
+
+inline bool operator<(const LeafClass &LHS, const LeafClass &RHS) {
+  if (LHS.Opcode < RHS.Opcode)
+    return true;
+  else if (LHS.Opcode > RHS.Opcode)
+    return false;
+  return LHS.Op1->getValue().slt(RHS.Op1->getValue());
+}
+
+/// Given a leaf, this function tries to return its appropriate LeafClass.
+///
+/// \param V  An associative instructions tree leaf.
+/// \param[out] OpClass \p V 's LeafClass.
+///
+/// \return true iff successfuly found \p V 's LeafClass.
+static bool getLeafClass(Value *V, LeafClass &OpClass) {
+  if (!V)
+    return false;
+  BinaryOperator *BO = dyn_cast<BinaryOperator>(V);
+  if (!BO)
+    return false;
+  ConstantInt *Op1 = dyn_cast<ConstantInt>(BO->getOperand(1));
+  if (!Op1)
+    return false;
+  OpClass.Opcode = BO->getOpcode();
+  OpClass.Op1 = Op1;
+  return true;
+}
+
+/// Computes and returns the number of non-leaves (inner nodes) required in an
+/// associative instructions tree in order to support a given number of leaves.
+///
+/// \param LeafNo The required number of leaves.
+/// \param[out] DepthToNodesNum The number of required non-leaves (inner nodes)
+/// by depth. i.e. DepthToNodesNum[i] will hold the number of required
+/// non-leaves (inner nodes) at depth i.
+static void
+nonLeafNodesNeededForTree(unsigned LeafNo,
+                          SmallVectorImpl<unsigned> &DepthToNodesNum) {
+  unsigned TotalRemainingNodes = LeafNo - 1;
+  for (unsigned i = 0; TotalRemainingNodes > 0; ++i) {
+    unsigned MaxNodesForDepth = 1U << i;
+    if (TotalRemainingNodes <= MaxNodesForDepth)
+      DepthToNodesNum.push_back(TotalRemainingNodes);
+    else
+      DepthToNodesNum.push_back(MaxNodesForDepth);
+    TotalRemainingNodes -= DepthToNodesNum[i];
+  }
+}
+
+/// Updates an associative instructions tree with new operands as leaves.
+///
+/// \param TreeNonLeaves The non-leaves (inner nodes) of the associative
+/// instructions tree. TreeNonLeaves[i] will hold the non-leaves (inner nodes)
+/// at depth i.
+/// \param Leaves The new leaves for the tree.
+static void updateTree(
+    const SmallVectorImpl<SmallVector<BinaryOperator *, 8>> &TreeNonLeaves,
+    const SmallVectorImpl<Value *> &Leaves) {
+  unsigned i = 0; // iterator over the leaves
+  for (unsigned Depth = 0; Depth < TreeNonLeaves.size(); ++Depth) {
+    const SmallVector<BinaryOperator *, 8> &CurrDepthNodes =
+        TreeNonLeaves[Depth];
+    const SmallVector<BinaryOperator *, 8> *NextDepthNodes =
+        Depth + 1 < TreeNonLeaves.size() ? &TreeNonLeaves[Depth + 1] : nullptr;
+    unsigned j = 0; // iterator over NextDepthNodes
+    for (BinaryOperator *CurrDepthNode : CurrDepthNodes) {
+      for (unsigned k = 0; k < 2; k++) {
+        Value *NewOperand = nullptr;
+        if (NextDepthNodes != nullptr && j < NextDepthNodes->size()) {
+          // First set all the nodes from the next depth, leave the leaves for
+          // the end
+          NewOperand = (*NextDepthNodes)[j];
+          ++j;
+        } else {
+          assert(i < Leaves.size());
+          NewOperand = Leaves[i];
+          ++i;
+        }
+        CurrDepthNode->setOperand(k, NewOperand);
+      }
+    }
+  }
+  assert(i == Leaves.size() && "Not all the leaves were inserted to the tree");
+}
+
+PreservedAnalyses WeakReassociatePass::run(Function &F,
+                                           FunctionAnalysisManager &) {
+  bool MadeChange = false;
+  for (Instruction &I : instructions(F)) {
+    if (!isInstructionTriviallyDead(&I))
+      MadeChange |= OptimizeInst(&I);
+  }
+
+  if (MadeChange) {
+    PreservedAnalyses PA;
+    PA.preserveSet<CFGAnalyses>();
+    PA.preserve<GlobalsAA>();
+    return PA;
+  }
+
+  return PreservedAnalyses::all();
+}
+
+bool WeakReassociatePass::OptimizeInst(Instruction *I) {
+  if (I->getType()->isIntegerTy(1))
+    return false;
+  if (!I->isAssociative())
+    return false;
+  BinaryOperator *BO = cast<BinaryOperator>(I);
+
+  // If this is an interior node of a reassociable tree, ignore it until we
+  // get to the root of the tree, to avoid N^2 analysis.
+  unsigned Opcode = BO->getOpcode();
+  if (BO->hasOneUse() && BO->user_back()->getOpcode() == Opcode)
+    return false;
+
+  SmallVector<Value *, 8> Ops;
+  std::stack<BinaryOperator *, SmallVector<BinaryOperator *, 4>> S;
+  S.push(BO);
+  while (!S.empty()) {
+    BinaryOperator *CurrBO = S.top();
+    S.pop();
+    for (unsigned i = 0; i < 2; ++i) {
+      Value *Operand = CurrBO->getOperand(i);
+      BinaryOperator *OperandBO = dyn_cast<BinaryOperator>(Operand);
+      if (!OperandBO || !OperandBO->hasOneUse() ||
+          OperandBO->getOpcode() != Opcode) {
+        // This is a leaf
+        Ops.push_back(Operand);
+        if (Ops.size() >= 10)
+          return false;
+      } else
+        // not a leaf, needs to examine it too.
+        S.push(OperandBO);
+    }
+  }
+  if (Ops.size() <= 2)
+    return false;
+  return RewriteExprTree(BO);
+}
+
+bool WeakReassociatePass::getTreeNodes(
+    BinaryOperator *I,
+    SmallVectorImpl<SmallVector<BinaryOperator *, 8>> &NonLeaves,
+    SmallVectorImpl<Value *> &Leaves) {
+  unsigned Opcode = I->getOpcode();
+  BasicBlock *BB = I->getParent();
+  NonLeaves.push_back({I});
+  for (unsigned Depth = 1;; ++Depth) {
+    if (Depth >= 4)
+      return false;
+    const SmallVector<BinaryOperator *, 8> &PrevDepthNodes =
+        NonLeaves[Depth - 1];
+    SmallVector<BinaryOperator *, 8> *CurrDepthNodes = nullptr;
+    // The operands of PrevDepthNodes are either CurrDepthNodes or leaves.
+    for (BinaryOperator *PrevDepthNode : PrevDepthNodes) {
+      for (Value *Operand : PrevDepthNode->operands()) {
+        BinaryOperator *OperandBO = dyn_cast<BinaryOperator>(Operand);
+        if (!OperandBO || !OperandBO->hasOneUse() ||
+            OperandBO->getOpcode() != Opcode) {
+          // If the operand is not a BinaryOperator with the same opcode of the
+          // root and one use then it is a leaf.
+          Leaves.push_back(Operand);
+          if (Leaves.size() >= 10)
+            return false;
+        } else {
+          if (OperandBO->getParent() != BB)
+            // All non-leaves (inner nodes) must belong to the same basic block.
+            return false;
+          if (CurrDepthNodes == nullptr) {
+            NonLeaves.push_back({});
+            CurrDepthNodes = &NonLeaves[Depth];
+          }
+          CurrDepthNodes->push_back(OperandBO);
+        }
+      }
+    }
+    if (CurrDepthNodes == nullptr)
+      // No new inner nodes, this was the last level of the tree.
+      break;
+  }
+  return true;
+}
+
+bool WeakReassociatePass::RewriteExprTree(BinaryOperator *I) {
+  SmallVector<SmallVector<BinaryOperator *, 8>, 8> NonLeaves;
+  SmallVector<Value *, 8> Leaves;
+  if (!getTreeNodes(I, NonLeaves, Leaves))
+    return false;
+
+  std::map<LeafClass, SmallVector<Value *, 8>> LeavesSets;
+  // Dividing the leaves into sets according to their LeafClass.
+  for (Value *Leaf : Leaves) {
+    LeafClass OpClass;
+    if (!getLeafClass(Leaf, OpClass))
+      return false;
+    auto LeavesSetLocation = LeavesSets.find(OpClass);
+    if (LeavesSetLocation == LeavesSets.end()) {
+      if (LeavesSets.size() == 2)
+        return false;
+      std::tie(LeavesSetLocation, std::ignore) =
+          LeavesSets.insert(std::make_pair(OpClass, SmallVector<Value *, 8>()));
+    }
+    LeavesSetLocation->second.push_back(Leaf);
+  }
+  // Must have exactly two sets, each with at least two elements.
+  if (std::find_if(
+          LeavesSets.begin(), LeavesSets.end(),
+          [](const std::pair<LeafClass, SmallVector<Value *, 8>> &KeyValPair)
+              -> bool { return KeyValPair.second.size() == 1; }) !=
+      LeavesSets.end())
+    return false;
+  if (LeavesSets.size() != 2)
+    return false;
+  const SmallVector<Value *, 8> &BlueLeaves = LeavesSets.begin()->second;
+  const SmallVector<Value *, 8> &RedLeaves = (++LeavesSets.begin())->second;
+
+  SmallVector<unsigned, 8> BlueDepthToNodesNum, RedDepthToNodesNum;
+  nonLeafNodesNeededForTree(BlueLeaves.size(), BlueDepthToNodesNum);
+  assert(BlueDepthToNodesNum.size() <= NonLeaves.size());
+  nonLeafNodesNeededForTree(RedLeaves.size(), RedDepthToNodesNum);
+  assert(RedDepthToNodesNum.size() <= NonLeaves.size());
+
+  // <color>NonLeaves[i] will hold the none leaves (inner nodes) at depth i of
+  // the <color> tree.
+  SmallVector<SmallVector<BinaryOperator *, 8>, 8> BlueNonLeaves, RedNonLeaves;
+  for (unsigned Depth = 1; Depth < NonLeaves.size(); ++Depth) {
+    // The two <color> trees, being the immediate children of the tree, have
+    // depth of one less (e.g. their root is at depth 1 of the big tree).
+    unsigned ChildDepth = Depth - 1;
+    unsigned CurrDepthBlueNodesNum = ChildDepth < BlueDepthToNodesNum.size()
+                                         ? BlueDepthToNodesNum[ChildDepth]
+                                         : 0;
+    unsigned CurrDepthRedNodesNum = ChildDepth < RedDepthToNodesNum.size()
+                                        ? RedDepthToNodesNum[ChildDepth]
+                                        : 0;
+    SmallVector<BinaryOperator *, 8> &CurrDepthNonLeaves = NonLeaves[Depth];
+    if (CurrDepthBlueNodesNum + CurrDepthRedNodesNum >
+        CurrDepthNonLeaves.size())
+      // If not enough nodes, stop with a failure. Note that this pass is not
+      // allowed to create new instructions.
+      return false;
+
+    SmallVector<BinaryOperator *, 8> CurrDepthBlueNodes, CurrDepthRedNodes;
+    // Splitting CurrDepthNonLeaves between CurrDepthBlueNodes and
+    // CurrDepthRedNodes.
+    unsigned i = 0;
+    for (unsigned j = 0; j < CurrDepthBlueNodesNum; ++j) {
+      CurrDepthBlueNodes.push_back(CurrDepthNonLeaves[i]);
+      ++i;
+    }
+    if (!CurrDepthBlueNodes.empty())
+      BlueNonLeaves.push_back(CurrDepthBlueNodes);
+    for (unsigned j = 0; j < CurrDepthRedNodesNum; ++j) {
+      CurrDepthRedNodes.push_back(CurrDepthNonLeaves[i]);
+      ++i;
+    }
+    if (!CurrDepthRedNodes.empty())
+      RedNonLeaves.push_back(CurrDepthRedNodes);
+  }
+
+  // Rearranging the inner nodes such that nodes of depth i will necessarily
+  // appear before nodes of depth i+1.
+  BinaryOperator *Top = I;
+  for (unsigned Depth = 1; Depth < NonLeaves.size(); ++Depth) {
+    SmallVector<BinaryOperator *, 8> &DepthNodes = NonLeaves[Depth];
+    for (BinaryOperator *DepthNode : DepthNodes) {
+      DepthNode->moveBefore(Top);
+      Top = DepthNode;
+    }
+  }
+
+  // Updating the two sub trees with the new leaves.
+  updateTree(BlueNonLeaves, BlueLeaves);
+  updateTree(RedNonLeaves, RedLeaves);
+  return true;
+}
+
+namespace {
+
+class WeakReassociateLegacyPass : public FunctionPass {
+  WeakReassociatePass Impl;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  WeakReassociateLegacyPass() : FunctionPass(ID) {
+    initializeWeakReassociateLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+
+    FunctionAnalysisManager DummyFAM;
+    auto PA = Impl.run(F, DummyFAM);
+    return !PA.areAllPreserved();
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+  }
+};
+
+} // end anonymous namespace
+
+char WeakReassociateLegacyPass::ID = 0;
+INITIALIZE_PASS(WeakReassociateLegacyPass, "weak-reassociate",
+                "Weak Reassociate expressions", false, false)
+
+// Public interface to the Reassociate pass
+FunctionPass *llvm::createWeakReassociatePass() {
+  return new WeakReassociateLegacyPass();
+}

test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-EP-SCALAR-LATE-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O-NEXT: Running pass: ADCEPass
 ; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
+; CHECK-O-NEXT: Running pass: WeakReassociatePass
 ; CHECK-EP-PEEPHOLE-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-EP-CGSCC-LATE-NEXT: Running pass: NoOpCGSCCPass
 ; CHECK-O-NEXT: Finished CGSCC pass manager run.
 ; CHECK-O-NEXT: Finished llvm::Module pass manager run.
 ; CHECK-O-NEXT: Running pass: PassManager<{{.*}}Module{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Module pass manager run.
 ; CHECK-O-NEXT: Running pass: GlobalOptPass

test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Starting llvm::Function pass manager run
 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run
 ; CHECK-O-NEXT: Running pass: ADCEPass
 ; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
+; CHECK-O-NEXT: Running pass: WeakReassociatePass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O-NEXT: Finished CGSCC pass manager run.
 ; CHECK-O-NEXT: Finished llvm::Module pass manager run.
 ; CHECK-PRELINK-O-NEXT: Running pass: GlobalOptPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: PassManager<{{.*}}Module{{.*}}>
 ; CHECK-POSTLINK-O-NEXT: Starting llvm::Module pass manager run.
 ; CHECK-POSTLINK-O-NEXT: Running pass: GlobalOptPass
 ; CHECK-POSTLINK-O-NEXT: Running pass: GlobalDCEPass

test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
+; CHECK-NEXT:         Weak Reassociate expressions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction

test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
+; CHECK-NEXT:         Weak Reassociate expressions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction

test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
+; CHECK-NEXT:         Weak Reassociate expressions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction

test/Transforms/WeakReassociate/add_bitwise.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -weak-reassociate -instcombine -S | FileCheck %s
+
+define i32 @func1(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @func1(
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[X]], 4
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP6:%.*]] = shl i32 [[TMP5]], 6
+; CHECK-NEXT:    [[TMP7:%.*]] = or i32 [[TMP6]], [[TMP4]]
+; CHECK-NEXT:    ret i32 [[TMP7]]
+;
+  %1 = add i32 %x, 2
+  %2 = add i32 %x, 4
+  %3 = shl nuw nsw i32 %1, 6
+  %4 = lshr exact i32 %1, 1
+  %5 = or i32 %3, %4
+  %6 = shl nuw nsw i32 %2, 6
+  %7 = lshr exact i32 %2, 1
+  %8 = or i32 %6, %7
+  %9 = or i32 %5, %8
+  ret i32 %9
+}
+
+define i32 @func2(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @func2(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 12
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[X]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i32 [[TMP2]], 3
+; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP1]], [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP4]], 19
+; CHECK-NEXT:    ret i32 [[TMP5]]
+;
+
+  %1 = and i32 %x, 12
+  %2 = and i32 %x, 1
+  %3 = add i32 %1, 3
+  %4 = add i32 %1, 17
+  %5 = or i32 %3, %4
+  %6 = add i32 %2, 3
+  %7 = add i32 %2, 17
+  %8 = or i32 %6, %7
+  %9 = or i32 %5, %8
+  ret i32 %9
+}
+
+define i32 @func3(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @func3(
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], 6
+; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[X]], 24
+; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[X]], 96
+; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    [[TMP6:%.*]] = or i32 [[TMP4]], [[TMP3]]
+; CHECK-NEXT:    [[TMP7:%.*]] = shl i32 [[TMP6]], 8
+; CHECK-NEXT:    [[TMP8:%.*]] = or i32 [[TMP5]], [[TMP3]]
+; CHECK-NEXT:    [[TMP9:%.*]] = shl i32 [[TMP8]], 1
+; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP9]], [[TMP7]]
+; CHECK-NEXT:    ret i32 [[TMP10]]
+;
+  %1 = add i32 %x, 6
+  %2 = shl nuw nsw i32 %1, 8
+  %3 = shl nuw nsw i32 %1, 1
+  %4 = or i32 %2, %3
+  %5 = add i32 %x, 24
+  %6 = shl nuw nsw i32 %5, 8
+  %7 = shl nuw nsw i32 %5, 1
+  %8 = or i32 %6, %7
+  %9 = or i32 %8, %4
+  %10 = add i32 %x, 96
+  %11 = shl nuw nsw i32 %10, 8
+  %12 = shl nuw nsw i32 %10, 1
+  %13 = or i32 %11, %12
+  %14 = or i32 %13, %9
+  ret i32 %14
+}

test/Transforms/WeakReassociate/or_or_shift.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -weak-reassociate -instcombine -S | FileCheck %s
+
+; (((A & 2) >> 1) | ((A & 2) << 6)) | (((A & 4) >> 1) | ((A & 4) << 6))
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | (((A & 2) << 6) | ((A & 4) << 6))
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | (((A & 2) | (A & 4)) << 6)
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | ((A & 6) << 6)
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | ((A << 6) & 384)
+; --> (((A & 2) | (A & 4)) >> 1) | ((A << 6) & 384)
+; --> ((A & 6) >> 1) | ((A << 6) & 384)
+; --> ((A >> 1) & 3) | ((A << 6) & 384)
+; --> ((A & 6) >> 1) | ((A & 6) << 6)
+
+define i32 @func1(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @func1(
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[X]], 6
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 384
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP4]], [[TMP2]]
+; CHECK-NEXT:    ret i32 [[TMP5]]
+;
+  %1 = and i32 %x, 2
+  %2 = and i32 %x, 4
+  %3 = shl nuw nsw i32 %1, 6
+  %4 = lshr exact i32 %1, 1
+  %5 = or i32 %3, %4
+  %6 = shl nuw nsw i32 %2, 6
+  %7 = lshr exact i32 %2, 1
+  %8 = or i32 %6, %7
+  %9 = or i32 %5, %8
+  ret i32 %9
+}
+
+define i32 @func2(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @func2(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 96
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 8
+; CHECK-NEXT:    [[TMP3:%.*]] = shl nuw nsw i32 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 [[X]], 8
+; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], 7680
+; CHECK-NEXT:    [[TMP6:%.*]] = shl i32 [[X]], 1
+; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[TMP6]], 60
+; CHECK-NEXT:    [[TMP8:%.*]] = or i32 [[TMP5]], [[TMP2]]
+; CHECK-NEXT:    [[TMP9:%.*]] = or i32 [[TMP7]], [[TMP3]]
+; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP9]], [[TMP8]]
+; CHECK-NEXT:    ret i32 [[TMP10]]
+;
+  %1 = and i32 %x, 6
+  %2 = shl nuw nsw i32 %1, 8
+  %3 = shl nuw nsw i32 %1, 1
+  %4 = or i32 %2, %3
+  %5 = and i32 %x, 24
+  %6 = shl nuw nsw i32 %5, 8
+  %7 = shl nuw nsw i32 %5, 1
+  %8 = or i32 %6, %7
+  %9 = or i32 %8, %4
+  %10 = and i32 %x, 96
+  %11 = shl nuw nsw i32 %10, 8
+  %12 = shl nuw nsw i32 %10, 1
+  %13 = or i32 %11, %12
+  %14 = or i32 %13, %9
+  ret i32 %14
+}

test/Transforms/WeakReassociate/or_or_xor_and.ll

+; RUN: opt < %s -weak-reassociate -instcombine -S | FileCheck %s
+
+; (((x ^ C1) | (x & C2)) | ((y ^ C1) | (y & C2))) ->
+; (((x | y) & C2) | ((x ^ C1) | (y ^ C1)))
+define i32 @or_or_xor_and(i32 %x, i32 %y) local_unnamed_addr #0  {
+; CHECK-LABEL: @or_or_xor_and(
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 %x, 15
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 %y, 15
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = or i32 %x, %y
+; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], 38
+; CHECK-NEXT:    [[TMP6:%.*]] = or i32 [[TMP5]], [[TMP3]]
+; CHECK-NEXT:    ret i32 [[TMP6]]
+;
+  %1 = xor i32 %x, 15
+  %2 = and i32 %x, 38
+  %3 = or i32 %1, %2
+  %4 = xor i32 %y, 15
+  %5 = and i32 %y, 38
+  %6 = or i32 %4, %5
+  %7 = or i32 %3, %6
+  ret i32 %7
+}