CodeGenPrepare: Avoid and/or i1 in select conditions.

[MatzeB]

Summary

This transforms:
select((C0 & C1), a, b) -> select(C0, select(C1, a, b), b)
select((C0 | C1), a, b) -> select(C0, a, select(C1, a, b))

The result is better on most targets as C0 and C1 do not need to be
materialized into an integer register but can stay flags.

[hfinkel]

In my early tests the transformation was benficial on arm, aarch64, x86 but of course not on powerpc. Either the powerpc target should normalize into the other direction or we add another TargetTransformInfo flag that tells InstCombine which is the preferred form. I am not sure which to pick.

This is fine for PPC too. LLVM's PPC backend stores boolean values in CR bit registers, and on modern cores with isel, this transformation seems fairly neutral. Your first example goes from:

.L.test_select_and:
cmpw 0, 3, 6
cmpw 1, 3, 7
crandc 20, 4, 0
isel 3, 4, 5, 20
blr

to:

.L.test_select_andr:
cmpw 0, 3, 7
cmpw 7, 3, 6
isel 4, 4, 5, 0
isel 3, 5, 4, 28
blr

On a P7/P8, this seems pretty neutral (both the crandc and the isel are cracked). On the A2, you've increased the critical path length by 1 cycle (isel takes two cycles, but crandc only takes one). Nevertheless, I think that I can adjust for that during isel fairly easily.

The real question, as far as InstCombine goes, is does this make the most-useful canonical form? I'd tend to think that the answer is no, because the logical operators seem more likely to be amenable to further simplification than chains of selects. I could certainly be wrong, however. Also, not all cores have conditional moves (although many now do). Another option is to put this in DAGCombine (or CodeGenPrep), and there you might as well make it target customizable (I'd likely disable it for the PPC A2).

[MatzeB]

New Version: This expects the middleend to have selects normalized to selects with and/or conditions (see http://reviews.llvm.org/D7450). The Code to break it into a sequence of multiple selects is now in the CodeGenPrepare pass and relies on a TargetLowering hook to test whether the transformation is useful.

[MatzeB]

On a side note: Ahmed just mentioned a snipped from SelectionDAGBuilder to me that has pretty much the same logic I do for selects implemented for branches:

// If this is a series of conditions that are or'd or and'd together, emit

// this as a sequence of branches instead of setcc's with and/or operations.
// As long as jumps are not expensive, this should improve performance.
// For example, instead of something like:
//     cmp A, B
//     C = seteq
//     cmp D, E
//     F = setle
//     or C, F
//     jnz foo
// Emit:
//     cmp A, B
//     je foo
//     cmp D, E
//     jle foo
//

...

no idea why that is in SelectionDAGBuilder, it also doesn't seem strictly beneficial to all targets to me...

[hfinkel]

In D7399#119931, @MatzeB wrote:

On a side note: Ahmed just mentioned a snipped from SelectionDAGBuilder to me that has pretty much the same logic I do for selects implemented for branches:

// If this is a series of conditions that are or'd or and'd together, emit

// this as a sequence of branches instead of setcc's with and/or operations.
// As long as jumps are not expensive, this should improve performance.
// For example, instead of something like:
//     cmp A, B
//     C = seteq
//     cmp D, E
//     F = setle
//     or C, F
//     jnz foo
// Emit:
//     cmp A, B
//     je foo
//     cmp D, E
//     jle foo
//

...

no idea why that is in SelectionDAGBuilder, it also doesn't seem strictly beneficial to all targets to me...

It's not (and it was pointed out to me in a different thread a couple of months ago); which function does this again? I keep forgetting to fix this... (my current plan is to turn it off when TLI->hasMultipleConditionRegisters() is true, which is only the case on PPC AFAIK).

[MatzeB]

SelectionDAGBuilder::visitBr

[MatzeB]

ping

[hfinkel]

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

1195 ↗

(On Diff #19492)

I think that you want to explicitly add And to the worklist here (assuming that the builder has not constant-folded it).

if (Instruction *AndI = dyn_cast<Instruction>(And))
  Worklist.Add(AndI);

otherwise we might not actually revisit it until the next main outer instcombine iteration.

include/llvm/Target/TargetLowering.h

   virtual LoadInst *lowerIdempotentRMWIntoFencedLoad(AtomicRMWInst *RMWI) const {
     return nullptr;
   }
+
+  /// Returns true if we should normalize
+  /// select(N0&N1, X, Y) => select(N0, select(N1, X, Y), Y) and
+  /// select(N0|N1, X, Y) => select(N0, select(N1, X, Y, Y)) if it is likely
+  /// that it saves us from materializing N0 and N1 in an integer register.
+  /// Targets that are able to perform and/or on flags should return false here.
+  virtual bool shouldNormalizeToSelectSequence(const SelectInst &SI) const {
+    (void)SI;
+    // If SELECTs are expensive then we should not do this.
+    return !isSelectExpensive();
+  }
+
   //===--------------------------------------------------------------------===//
   // TargetLowering Configuration Methods - These methods should be invoked by
   // the derived class constructor to configure this object for the target.

lib/CodeGen/CodeGenPrepare.cpp

     bool OptimizeCallInst(CallInst *CI, bool& ModifiedDT);
     bool MoveExtToFormExtLoad(Instruction *&I);
     bool OptimizeExtUses(Instruction *I);
+    bool OptimizeSelectAndOr(SelectInst &SI);
     bool OptimizeSelectInst(SelectInst *SI);
     bool OptimizeShuffleVectorInst(ShuffleVectorInst *SI);
     bool OptimizeExtractElementInst(Instruction *Inst);

           (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
 }
 
+/// Test whether @p CondVal is a tree of And/Or/Compare instructions. If it is
+/// not then it is hard to decide whether breaking selects apart is helpful.
+static bool isTreeOfAndOrCompare(const Value &CondVal) {
+  // Be conservative and restrict ourself ot 1 user. The other uses may force
+  // putting the value into an int register.
+  if (!CondVal.hasOneUse())
+    return false;
+
+  // Additional And/Or instructions will all be broken down.
+  const Instruction *CondInstr = dyn_cast<const Instruction>(&CondVal);
+  if (CondInstr == nullptr)
+    return false;
+  switch (CondInstr->getOpcode()) {
+  case Instruction::ICmp:
+  case Instruction::FCmp:
+    return true;
+  case Instruction::And:
+  case Instruction::Or: {
+    const Value *Op0 = CondInstr->getOperand(0);
+    const Value *Op1 = CondInstr->getOperand(1);
+    return isTreeOfAndOrCompare(*Op0) && isTreeOfAndOrCompare(*Op1);
+  }
+  default:
+    return false;
+  }
+}
+
+bool CodeGenPrepare::OptimizeSelectAndOr(SelectInst &SI) {
+  Value *Condition = SI.getCondition();
+  Instruction *CondI = dyn_cast<Instruction>(Condition);
+  if (CondI == nullptr)
+    return false;
+  unsigned Opcode = CondI->getOpcode();
+  if (Opcode != Instruction::And && Opcode != Instruction::Or)
+    return false;
+  if (!TLI->shouldNormalizeToSelectSequence(SI))
+    return false;
+
+  // Conservative estimation on whether we can save materializing the condition
+  // in an integer register when expanding the select.
+  // If condition only constis of and/or i1 or Compare predecessors and
+  // all other users are such and/ors/selects as well we are fine.
+  if (!isTreeOfAndOrCompare(*CondI))
+    return false;
+
+  // select((N0 & N1), a, b) => select(N0, select(N1, a, b), b)
+  // select((N0 | N1), a, b) => select(N0, a, select(N1, a, b))
+  IRBuilder<> Builder(SI.getContext());
+  Builder.SetInsertPoint(&SI);
+  Value *N0 = CondI->getOperand(0);
+  Value *N1 = CondI->getOperand(1);
+  Value *TrueVal = SI.getTrueValue();
+  Value *FalseVal = SI.getFalseValue();
+  Value *InnerSelect = Builder.CreateSelect(N1, TrueVal, FalseVal,
+                                            SI.getName()+".0");
+  SI.setOperand(0, N0);
+  unsigned SelectOp = Opcode == Instruction::And ? 1 : 2;
+  SI.setOperand(SelectOp, InnerSelect);
+
+  // SI was the only user of CondI, we can remove it.
+  CondI->eraseFromParent();
+
+  // Optimzie the new/changed select instructions.
+  if (SelectInst *InnerSelectSI = dyn_cast<SelectInst>(InnerSelect))
+    OptimizeSelectAndOr(*InnerSelectSI);
+  OptimizeSelectAndOr(SI);
+  return true;
+}
 
 /// If we have a SelectInst that will likely profit from branch prediction,
 /// turn it into a branch.
 bool CodeGenPrepare::OptimizeSelectInst(SelectInst *SI) {
+  bool Changed = OptimizeSelectAndOr(*SI);
+
   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
 
   // Can we convert the 'select' to CF ?
   if (DisableSelectToBranch || OptSize || !TLI || VectorCond)
-    return false;
+    return Changed;
 
   TargetLowering::SelectSupportKind SelectKind;
   if (VectorCond)

     // Check if it is profitable to keep this 'select'.
     if (!TLI->isPredictableSelectExpensive() ||
         !isFormingBranchFromSelectProfitable(SI))
-      return false;
+      return Changed;
   }
 
   ModifiedDT = true;

   // Instruct OptimizeBlock to skip to the next block.
   CurInstIterator = StartBlock->end();
   ++NumSelectsExpanded;
-  return true;
+  Changed = true;
+  return Changed;
 }
 
 static bool isBroadcastShuffle(ShuffleVectorInst *SVI) {

lib/Target/PowerPC/PPCISelLowering.h

       return Ty->isArrayTy();
     }
 
+    /// No gain in select sequences as we can natively perform and/or on flag
+    /// registers.
+    bool shouldNormalizeToSelectSequence(const SelectInst &SI) const override {
+      return false;
+    }
+
   private:
 
     struct ReuseLoadInfo {

test/CodeGen/R600/or.ll

 ; EG: OR_INT {{\** *}}T{{[0-9]+\.[XYZW], PV\.[XYZW], PS}}
 
 ; SI: s_or_b64 s[{{[0-9]+:[0-9]+}}], s[{{[0-9]+:[0-9]+}}], s[{{[0-9]+:[0-9]+}}]
-define void @or_i1(float addrspace(1)* %out, float addrspace(1)* %in0, float addrspace(1)* %in1) {
+define void @or_i1(i32 addrspace(1)* %out, float addrspace(1)* %in0, float addrspace(1)* %in1) {
   %a = load float addrspace(1)* %in0
   %b = load float addrspace(1)* %in1
   %acmp = fcmp oge float %a, 0.000000e+00
   %bcmp = fcmp oge float %b, 0.000000e+00
   %or = or i1 %acmp, %bcmp
-  %result = select i1 %or, float %a, float %b
-  store float %result, float addrspace(1)* %out
+  %result = zext i1 %or to i32
+  store i32 %result, i32 addrspace(1)* %out
   ret void
 }
 

test/CodeGen/X86/jump_sign.ll

 ; PR13475
 ; If we have sub a, b and cmp b, a and the result of cmp is used
 ; by sbb, we should not optimize cmp away.
-define i32 @func_q(i32 %j.4, i32 %w, i32 %el) {
+define i32 @func_q(i32 %a0, i32 %a1, i32 %a2) {
 ; CHECK-LABEL: func_q:
 ; CHECK: cmp
 ; CHECK-NEXT: sbb
-  %tmp532 = add i32 %j.4, %w
-  %tmp533 = icmp ugt i32 %tmp532, %el
-  %tmp534 = icmp ult i32 %w, %el
-  %or.cond = and i1 %tmp533, %tmp534
-  %tmp535 = sub i32 %el, %w
-  %j.5 = select i1 %or.cond, i32 %tmp535, i32 %j.4
-  ret i32 %j.5
+  %1 = icmp ult i32 %a0, %a1
+  %2 = sub i32 %a1, %a0
+  %3 = select i1 %1, i32 -1, i32 0
+  %4 = xor i32 %2, %3
+  ret i32 %4
 }
 ; rdar://11873276
 define i8* @func_r(i8* %base, i32* nocapture %offset, i32 %size) nounwind {

test/CodeGen/X86/zext-sext.ll

   %tmp12 = add i64 %tmp11, 5089792279245435153
 
 ; CHECK:      addl  $2138875574, %e[[REGISTER_zext:[a-z0-9]+]]
-; CHECK:      movslq  %e[[REGISTER_zext]], [[REGISTER_sext:%r[a-z0-9]+]]
 ; CHECK:      cmpl  $-8608074, %e[[REGISTER_zext]]
+; CHECK:      movslq  %e[[REGISTER_zext]], [[REGISTER_sext:%r[a-z0-9]+]]
 ; CHECK-NOT:  [[REGISTER_zext]]
-; CHECK-DAG:  testl     %e[[REGISTER_zext]]
-; CHECK:      subq  %r[[REGISTER_zext]], [[REGISTER_sext]]
+; CHECK-DAG:  cmpl  $2138875573, %e[[REGISTER_zext]]
+; CHECK:      movq  [[REGISTER_sext]], [[REGISTER_sext2:%[a-z0-9]+]]
+; CHECK:      subq  %r[[REGISTER_zext]], [[REGISTER_sext2]]
 
   %tmp13 = sub i64 %tmp12, 2138875574
   %tmp14 = zext i32 %tmp4 to i64

test/Transforms/CodeGenPrepare/select_and_or.ll

+; RUN: opt -mtriple=x86_64-unknown-unknown -codegenprepare -S -o - %s | FileCheck %s
+; RUN: opt -mtriple=aarch64-unknown-unknown -codegenprepare -S -o - %s | FileCheck %s
+; RUN: opt -mtriple=powerpc-unknown-unknown -codegenprepare -S -o - %s | not FileCheck %s
+
+define i32 @select_or(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+@var32 = global i32 0
+
+define i32 @select_or2(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or2
+; CHECK: or
+; CHECK: select
+; CHECK-NOT: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %zero_one = zext i1 %or to i32
+  store volatile i32 %zero_one, i32* @var32
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+define i32 @select_and(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_and
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = fcmp uge float %a2, %a3
+  %or = and i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+define i32 @select_multi(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_multi
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp uge i32 %a4, %a1
+  %cmp2 = fcmp uge float %a2, %a3
+  %or = or i1 %cmp0, %cmp1
+  %and = and i1 %or, %cmp2
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}