[Reassociate] Group select of constants together with constants

[mgudim]

Summary

If we assign the same rank to select of constants as to constants, we enable InstCombine to absorb constant into the select.

[mgudim]

Posting this as a draft to get some feedback / advice. I am not sure about the following points:

(1) If only one of the arguments of select is constant, putting select next to a constant could be still beneficial.
(2) How should we handle selects on different conditions?
(3) Would it be better to move selects next to constants in ReassociateExpression instead?

[nikic]

llvm/test/Transforms/Reassociate/select-of-constants.ll

19

This test produces the same result before and after your patch (https://llvm.godbolt.org/z/v6oe486Mc).

[mgudim]

llvm/test/Transforms/Reassociate/select-of-constants.ll

19

The output after reassociate is:

define dso_local signext i32 @select_of_constants(i32 noundef signext %a, i1 %c) {
entry:
  %select_ = select i1 %c, i32 8, i32 2
  %add4 = add i32 %select_, 4  ; note that now we add 4 to %select_
  %add_ = add i32 %add4, %a
  ret i32 %add_
}

So basically, the input corresponds to this expression: %select_ + (%a + 4) and output corresponds to this: (%select + 4) + %a. This allows InstCombine to "swallow` addition of 4 into the select. At the end of opt we'll have:

define dso_local signext i32 @select_of_constants(i32 noundef signext %a, i1 %c) local_unnamed_addr #0 {
entry:
  %add4 = select i1 %c, i32 12, i32 6
  %add_ = add i32 %add4, %a
  ret i32 %add_
}

llvm/lib/Transforms/Scalar/Reassociate.cpp

   }
 }
 
+static bool isSelectOfConstants(Instruction &I) {
+  Value *Cond;
+  Constant *TrueC, *FalseC;
+  return match(&I,
+               m_Select(m_Value(Cond), m_Constant(TrueC), m_Constant(FalseC)));
+}
+
 unsigned ReassociatePass::getRank(Value *V) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) {

     return 0;  // Otherwise it's a global or constant, rank 0.
   }
 
+  // TODO: what should we do if we have several selects of constants?
+  // What if conditions of selects are different?
+  if (isSelectOfConstants(*I))
+    // We want to group select of constants with constants, so that
+    // InstCombine can absorb addition of constant into the select.
+    return 0;
+
   if (unsigned Rank = ValueRankMap[I])
     return Rank;    // Rank already known?
 

llvm/test/Transforms/Reassociate/select-of-constants.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=reassociate < %s | FileCheck %s
+
+; Test that reassociation groups select of constants together with constants.
+
+define dso_local signext i32 @select_of_constants(i32 noundef signext %a, i1 %c)  {
+; CHECK-LABEL: @select_of_constants(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SELECT_:%.*]] = select i1 [[C:%.*]], i32 8, i32 2
+; CHECK-NEXT:    [[ADD4:%.*]] = add i32 [[SELECT_]], 4
+; CHECK-NEXT:    [[ADD_:%.*]] = add i32 [[ADD4]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[ADD_]]
+;
+entry:
+  %select_ = select i1 %c, i32 8, i32 2
+  %add4 = add i32 %a, 4
+  %add_ = add i32 %add4, %select_
+  ret i32 %add_
+}