[CodeGenPrepare] Move Extension Instructions Through Logical And Shift Instructions

[Carrot]

Summary

CodeGenPrepare pass move extension instructions close to load instructions in different BB, so they can be combined later. But the extension instructions can't move through logical and shift instructions in current implementation. This patch enables this enhancement, so we can eliminate more extension instructions.

[Carrot]

ping

[dblaikie]

Not really my area of expertise - just skimming the commit history for the file it looks like Quentin did a bunch of nearby work, so perhaps he can help?

[qcolombet]

Hi,

High level comment to help me dive into your changes.
See inlined.

Cheers,
Q

lib/CodeGen/CodeGenPrepare.cpp

3254 ↗

(On Diff #142076)

Could you add comments explaining what the new parameters are and their use?

test/Transforms/CodeGenPrepare/X86/ext-logicop.ll

1 ↗

(On Diff #142076)

Could you run opt instnamer on the input file first?
(To get rid of the implicit variable (%[0-9]+)

[Carrot]

lib/CodeGen/CodeGenPrepare.cpp

3254 ↗

(On Diff #142076)

The new parameters are used to check:

1. if the extension is free.
2. if the following transformation is doable
   
   and(ext(shl(opnd, cst)), cst) --> and(shl(ext(opnd), ext(cst)), cst)

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

3246 ↗

(On Diff #143654)

typo: instruction

3257 ↗

(On Diff #143654)

Both IsSExt and ConsideredExtType can be derived from ExtInst now.
We should get rid of those parameters.

3370 ↗

(On Diff #143654)

I believe this check does not belong here.
All the cost checks are done later.
Here we are just checking if it is semantically correct to move the extension up.

[Carrot]

lib/CodeGen/CodeGenPrepare.cpp

3246 ↗

(On Diff #143654)

deleted.

3257 ↗

(On Diff #143654)

Parameter ExtInst is deleted.

3370 ↗

(On Diff #143654)

Removed. It directly makes parameter TLI unnecessary. Another use of ExtInst in pattern and(ext(shl(opnd, cst)), cst) can be found through its user since it must be the only user. So we can keep the interface unchanged.

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

3369 ↗

(On Diff #143806)

Do we need to restrict this to constants?

3382 ↗

(On Diff #143806)

Same question as And and Or, do we need to restrict to constant?
More generally, I am not an expert on how we are dealing with poisioned value, but we probably want to call out (in a comment) that given we don't have the nuw flag, we may change a poisioned value into a regular value (eg., zext i32(shrl i8 %val, 12) => gives poison, but shrl i32 (zext i8 %val), 12 is totally fine. I believe this is okay because undef also covers valid value.

3386 ↗

(On Diff #143806)

Same comment as the previous one.

[Carrot]

lib/CodeGen/CodeGenPrepare.cpp

3369 ↗

(On Diff #143806)

It is same as DAGCombiner::visitZERO_EXTEND. Extension of constant doesn't cause extra cost at run time, it makes sure moving extension across this instruction doesn't bring another extension on the other operand. Only in rare case the extension on the other operand can also be combined with another load.

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

3369 ↗

(On Diff #143806)

Agreed. However, the check of the profitability of creating more than one extension is done later. Here we focus on answering, is it possible to extend?
So constant or not, the answer should be yes (true).

My point is, unless you see a problem with the existing cost model used later, we shouldn't prevent the promotion to get evaluated.

[Carrot]

lib/CodeGen/CodeGenPrepare.cpp

3369 ↗

(On Diff #143806)

Sounds reasonable.
I tried removing the constant check, there is only one failure test/CodeGen/X86/zext-logicop-shift-load.ll.

The source code is:

; Don't do the folding if the other operand isn't a constant.
define i64 @test7(i8* %data, i8 %logop) {
; CHECK-LABEL: test7:
; CHECK: movb
; CHECK-NEXT: shrb
; CHECK-NEXT: orb
; CHECK-NEXT: movzbl
; CHECK-NEXT: retq
entry:

%bf.load = load i8, i8* %data, align 4
%bf.clear = lshr i8 %bf.load, 2
%0 = or i8 %bf.clear, %logop
%1 = zext i8 %0 to i64 
ret i64 %1

}

Original result is:

movb    (%rdi), %al 
shrb    $2, %al 
orb     %sil, %al 
movzbl  %al, %eax
retq

Now the result is:

movzbl  (%rdi), %ecx
shrq    $2, %rcx
movzbl  %sil, %eax
orq     %rcx, %rax
retq

The new result isn't better than old result, neither worse. Do you think we should do transformation on this test case?

[qcolombet]

The new result isn't better than old result, neither worse. Do you think we should do transformation on this test case?

Yes. As long as it isn't worse, that means the cost model works the way we want.

[Carrot]

Removed constant restriction.

[qcolombet]

Thanks for your patience, LGTM.

[craig.topper]

I think this may have caused PR38125

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
   // We can get through binary operator, if it is legal. In other words, the
   // binary operator must have a nuw or nsw flag.
   const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
   if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
       ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
        (IsSExt && BinOp->hasNoSignedWrap())))
     return true;
 
+  // ext(and(opnd, cst)) --> and(ext(opnd), ext(cst))
+  if ((Inst->getOpcode() == Instruction::And ||
+       Inst->getOpcode() == Instruction::Or))
+    return true;
+
+  // ext(xor(opnd, cst)) --> xor(ext(opnd), ext(cst))
+  if (Inst->getOpcode() == Instruction::Xor) {
+    const ConstantInt *Cst = dyn_cast<ConstantInt>(Inst->getOperand(1));
+    // Make sure it is not a NOT.
+    if (Cst && !Cst->getValue().isAllOnesValue())
+      return true;
+  }
+
+  // zext(shrl(opnd, cst)) --> shrl(zext(opnd), zext(cst))
+  // It may change a poisoned value into a regular value, like
+  //     zext i32 (shrl i8 %val, 12)  -->  shrl i32 (zext i8 %val), 12
+  //          poisoned value                    regular value
+  // It should be OK since undef covers valid value.
+  if (Inst->getOpcode() == Instruction::LShr && !IsSExt)
+    return true;
+
+  // and(ext(shl(opnd, cst)), cst) --> and(shl(ext(opnd), ext(cst)), cst)
+  // It may change a poisoned value into a regular value, like
+  //     zext i32 (shl i8 %val, 12)  -->  shl i32 (zext i8 %val), 12
+  //          poisoned value                    regular value
+  // It should be OK since undef covers valid value.
+  if (Inst->getOpcode() == Instruction::Shl && Inst->hasOneUse()) {
+    const Instruction *ExtInst =
+        dyn_cast<const Instruction>(*Inst->user_begin());
+    if (ExtInst->hasOneUse()) {
+      const Instruction *AndInst =
+          dyn_cast<const Instruction>(*ExtInst->user_begin());
+      if (AndInst && AndInst->getOpcode() == Instruction::And) {
+        const ConstantInt *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
+        if (Cst &&
+            Cst->getValue().isIntN(Inst->getType()->getIntegerBitWidth()))
+          return true;
+      }
+    }
+  }
+
   // Check if we can do the following simplification.
   // ext(trunc(opnd)) --> ext(opnd)
   if (!isa<TruncInst>(Inst))
     return false;
 
   Value *OpndVal = Inst->getOperand(0);
   // Check if we can use this operand in the extension.
   // If the type is larger than the result type of the extension, we cannot.

llvm/trunk/test/CodeGen/X86/cmov.ll

 @g_96 = external global i8
 @g_100 = external global i8
 @_2E_str = external constant [15 x i8], align 1
 
 define i1 @test4() nounwind {
 ; CHECK-LABEL: test4:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movsbl {{.*}}(%rip), %edx
-; CHECK-NEXT:    movl %edx, %eax
-; CHECK-NEXT:    shrb $7, %al
-; CHECK-NEXT:    movzbl %al, %ecx
+; CHECK-NEXT:    movzbl %dl, %ecx
+; CHECK-NEXT:    shrl $7, %ecx
 ; CHECK-NEXT:    xorl $1, %ecx
 ; CHECK-NEXT:    # kill: def $cl killed $cl killed $ecx
 ; CHECK-NEXT:    sarl %cl, %edx
 ; CHECK-NEXT:    movb {{.*}}(%rip), %al
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    je .LBB3_2
 ; CHECK-NEXT:  # %bb.1: # %bb.i.i.i
 ; CHECK-NEXT:    movb {{.*}}(%rip), %cl

llvm/trunk/test/CodeGen/X86/ins_subreg_coalesce-1.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-- -mattr=-bmi | FileCheck %s
 
 define fastcc i32 @t() nounwind  {
 ; CHECK-LABEL: t:
 ; CHECK:       # %bb.0: # %walkExprTree.exit
-; CHECK-NEXT:    movl 0, %eax
+; CHECK-NEXT:    movzwl 0, %eax
 ; CHECK-NEXT:    orl $2, %eax
 ; CHECK-NEXT:    movw %ax, 0
 ; CHECK-NEXT:    shrl $3, %eax
 ; CHECK-NEXT:    andl $1, %eax
 ; CHECK-NEXT:    retl
 entry:
   br i1 false, label %UnifiedReturnBlock, label %bb4
 bb4:    ; preds = %entry

llvm/trunk/test/CodeGen/X86/zext-logicop-shift-load.ll

 entry:
   %bf.load = load i8, i8* %data, align 4
   %bf.clear = lshr i8 %bf.load, 2
   %0 = or i8 %bf.clear, 60
   %1 = zext i8 %0 to i64
   ret i64 %1
 }
 
-; Don't do the folding if the other operand isn't a constant.
-define i64 @test7(i8* %data, i8 %logop) {
-; CHECK-LABEL: test7:
-; CHECK:       movb
-; CHECK-NEXT:  shrb
-; CHECK-NEXT:  orb
-; CHECK-NEXT:  movzbl
-; CHECK-NEXT:  retq
-entry:
-  %bf.load = load i8, i8* %data, align 4
-  %bf.clear = lshr i8 %bf.load, 2
-  %0 = or i8 %bf.clear, %logop
-  %1 = zext i8 %0 to i64
-  ret i64 %1
-}
-
 ; Load is folded with sext.
 define i64 @test8(i8* %data) {
 ; CHECK-LABEL: test8:
 ; CHECK:       movsbl
 ; CHECK-NEXT:  movzwl
 ; CHECK-NEXT:  shrl
 ; CHECK-NEXT:  orl
 entry:
   %bf.load = load i8, i8* %data, align 4
   %ext = sext i8 %bf.load to i16
   %bf.clear = lshr i16 %ext, 2
   %0 = or i16 %bf.clear, 60
   %1 = zext i16 %0 to i64
   ret i64 %1
 }
 

llvm/trunk/test/Transforms/CodeGenPrepare/X86/ext-logicop.ll

+; RUN: opt < %s -codegenprepare -S -mtriple=x86_64-unknown-unknown    | FileCheck %s
+
+
+@a = global [10 x i8] zeroinitializer, align 1
+declare void @foo()
+
+; ext(and(ld, cst)) -> and(ext(ld), ext(cst))
+define void @test1(i32* %p, i32 %ll) {
+; CHECK-LABEL: @test1
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    load
+; CHECK-NEXT:    zext
+; CHECK-NEXT:    and
+entry:
+  %tmp = load i8, i8* getelementptr inbounds ([10 x i8], [10 x i8]* @a, i64 0, i64 0), align 1
+  %and = and i8 %tmp, 60
+  %cmp = icmp ugt i8 %and, 20
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %conv2 = zext i8 %and to i32
+  %add = add nsw i32 %conv2, %ll
+  store i32 %add, i32* %p, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  tail call void @foo()
+  ret void
+}
+
+; ext(or(ld, cst)) -> or(ext(ld), ext(cst))
+define void @test2(i32* %p, i32 %ll) {
+; CHECK-LABEL: @test2
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    load
+; CHECK-NEXT:    zext
+; CHECK-NEXT:    or
+entry:
+  %tmp = load i8, i8* getelementptr inbounds ([10 x i8], [10 x i8]* @a, i64 0, i64 0), align 1
+  %or = or i8 %tmp, 60
+  %cmp = icmp ugt i8 %or, 20
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %conv2 = zext i8 %or to i32
+  %add = add nsw i32 %conv2, %ll
+  store i32 %add, i32* %p, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  tail call void @foo()
+  ret void
+}
+
+; ext(and(shl(ld, cst), cst)) -> and(shl(ext(ld), ext(cst)), ext(cst))
+define void @test3(i32* %p, i32 %ll) {
+; CHECK-LABEL: @test3
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    load
+; CHECK-NEXT:    zext
+; CHECK-NEXT:    shl
+; CHECK-NEXT:    and
+entry:
+  %tmp = load i8, i8* getelementptr inbounds ([10 x i8], [10 x i8]* @a, i64 0, i64 0), align 1
+  %shl = shl i8 %tmp, 2
+  %and = and i8 %shl, 60
+  %cmp = icmp ugt i8 %and, 20
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %conv2 = zext i8 %and to i32
+  %add = add nsw i32 %conv2, %ll
+  store i32 %add, i32* %p, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  tail call void @foo()
+  ret void
+}
+
+; zext(shrl(ld, cst)) -> shrl(zext(ld), zext(cst))
+define void @test4(i32* %p, i32 %ll) {
+; CHECK-LABEL: @test4
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    load
+; CHECK-NEXT:    zext
+; CHECK-NEXT:    lshr
+entry:
+  %tmp = load i8, i8* getelementptr inbounds ([10 x i8], [10 x i8]* @a, i64 0, i64 0), align 1
+  %lshr = lshr i8 %tmp, 2
+  %cmp = icmp ugt i8 %lshr, 20
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %conv2 = zext i8 %lshr to i32
+  %add = add nsw i32 %conv2, %ll
+  store i32 %add, i32* %p, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  tail call void @foo()
+  ret void
+}
+
+; ext(xor(ld, cst)) -> xor(ext(ld), ext(cst))
+define void @test5(i32* %p, i32 %ll) {
+; CHECK-LABEL: @test5
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    load
+; CHECK-NEXT:    zext
+; CHECK-NEXT:    xor
+entry:
+  %tmp = load i8, i8* getelementptr inbounds ([10 x i8], [10 x i8]* @a, i64 0, i64 0), align 1
+  %xor = xor i8 %tmp, 60
+  %cmp = icmp ugt i8 %xor, 20
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %conv2 = zext i8 %xor to i32
+  %add = add nsw i32 %conv2, %ll
+  store i32 %add, i32* %p, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  tail call void @foo()
+  ret void
+}
+