X86/TargetTransformInfo: Report div/rem constant immediate costs as TCC_Free

[MatzeB]

Summary

DIV/REM by constants should always be expanded into mul/shift/etc.
patterns. Unfortunately the ConstantHoisting pass runs too early at a
point where the pattern isn't expanded yet. However after
ConstantHoisting hoisted some immediate the result may not expand
anymore. Also the hoisting typically doesn't make sense because it
operates on immediates that will change completely during the expansion.

Report DIV/REM as TCC_Free so ConstantHoisting will not touch them.

[MatzeB]

This is currently not motivated by a benchmark but preparation for an upcoming commit of mine where I don't want ConstantHoisting to screw with dev/rem and mess up testcases.

However it does make sense in general and speeds up this microbenchmark by 10x on my measurements:

#include <stdint.h>

#define SIZE 100000

void __attribute__((noinline)) divfoo(int64_t *signed_arr, uint64_t *unsigned_arr) {
    for (unsigned i = 0; i < SIZE; ++i) {
        signed_arr[i] /= 0xcafebabe5;
        unsigned_arr[i] /= 0xcafebabe5;
    }
}

int main(void) {
    static int64_t signed_arr[SIZE];
    static uint64_t unsigned_arr[SIZE];
    for (unsigned i = 0; i < 1000; ++i)
        divfoo(signed_arr, unsigned_arr);
}

[craig.topper]

This totally makes sense, but why is ConstantHoisting pulling those constants out of the only block that uses them? I thought it tried to keep constants in the nearest dominator of the uses?

[craig.topper]

Or is moving them because its a loop and we don't want to reload it every iteration and don't trust LICM?

[MatzeB]

In D53174#1262762, @craig.topper wrote:

Or is moving them because its a loop and we don't want to reload it every iteration and don't trust LICM?

I'm not completely sure. I see the code operating with block frequencies so it probably sees a lower block frequency in front of the loop.

The pass itself currently runs relatively close to SelectionDAG so there is no LICM happening anymore. Though IMO it really should be implemented in SelectionDAG after everything is expanded and actually all constants are visible and not play all the games with hoisting constants between blocks.

[MatzeB]

In D53174#1262775, @MatzeB wrote:

In D53174#1262762, @craig.topper wrote:

Or is moving them because its a loop and we don't want to reload it every iteration and don't trust LICM?

I'm not completely sure. I see the code operating with block frequencies so it probably sees a lower block frequency in front of the loop.

The pass itself currently runs relatively close to SelectionDAG so there is no LICM happening anymore. Though IMO it really should be implemented in SelectionDAG after everything is expanded and actually all constants are visible and not play all the games with hoisting constants between blocks.

Also with ConstantHoisting being a late SelectionDAG pass we could get rid of the terrible OpaqueConstant concept in SelectionDAG/DAGCombiner. (I'm not signing up to actually change this at this time though)

[MatzeB]

noticed that the test needs to operate on i64 to have any effect (as all i32 values are reported as TCC_Free anyway)

[craig.topper]

LGTM

lib/Target/X86/X86TargetTransformInfo.cpp

case Instruction::And:
     break;
   case Instruction::Add:
   case Instruction::Sub:
     // For add/sub, we can use the opposite instruction for INT32_MIN.
     if (Idx == 1 && Imm.getBitWidth() == 64 && Imm.getZExtValue() == 0x80000000)
       return TTI::TCC_Free;
     ImmIdx = 1;
     break;
-  case Instruction::Mul:
   case Instruction::UDiv:
   case Instruction::SDiv:
   case Instruction::URem:
   case Instruction::SRem:
+    // Division by constant is typically expanded later into a different
+    // instruction sequence. This completely changes the constants.
+    // Report them as "free" to stop ConstantHoist from marking them as opaque.
+    return TTI::TCC_Free;
+  case Instruction::Mul:
   case Instruction::Or:
   case Instruction::Xor:
     ImmIdx = 1;
     break;
   // Always return TCC_Free for the shift value of a shift instruction.
   case Instruction::Shl:
   case Instruction::LShr:
   case Instruction::AShr:

test/Transforms/ConstantHoisting/X86/bad-cases.ll

+; RUN: opt -consthoist -S < %s | FileCheck %s
+target triple = "x86_64--"
+
+; We don't want to convert constant divides because the benefit from converting
+; them to a mul in the backend is larget than constant materialization savings.
+define void @signed_const_division(i32 %in1, i32 %in2, i32* %addr) {
+; CHECK-LABEL: @signed_const_division
+; CHECK: %res1 = sdiv i32 %l1, 1000000000
+; CHECK: %res2 = srem i32 %l2, 1000000000
+entry:
+  br label %loop
+
+loop:
+  %l1 = phi i32 [%res1, %loop], [%in1, %entry]
+  %l2 = phi i32 [%res2, %loop], [%in2, %entry]
+  %res1 = sdiv i32 %l1, 1000000000
+  store volatile i32 %res1, i32* %addr
+  %res2 = srem i32 %l2, 1000000000
+  store volatile i32 %res2, i32* %addr
+  %again = icmp eq i32 %res1, %res2
+  br i1 %again, label %loop, label %end
+
+end:
+  ret void
+}
+
+define void @unsigned_const_division(i32 %in1, i32 %in2, i32* %addr) {
+; CHECK-LABEL: @unsigned_const_division
+; CHECK: %res1 = udiv i32 %l1, 1000000000
+; CHECK: %res2 = urem i32 %l2, 1000000000
+
+entry:
+  br label %loop
+
+loop:
+  %l1 = phi i32 [%res1, %loop], [%in1, %entry]
+  %l2 = phi i32 [%res2, %loop], [%in2, %entry]
+  %res1 = udiv i32 %l1, 1000000000
+  store volatile i32 %res1, i32* %addr
+  %res2 = urem i32 %l2, 1000000000
+  store volatile i32 %res2, i32* %addr
+  %again = icmp eq i32 %res1, %res2
+  br i1 %again, label %loop, label %end
+
+end:
+  ret void
+}