Hi, <div><br></div><div>I noticed a significant performance regression (up to 40%) on some internal CUDA benchmarks (a reduced example presented below). The root cause of this regression seems that IndVarSimpilfy widens induction variables assuming arithmetics on wider integer types are as cheap as those on narrower ones. However, this assumption is wrong at least for the NVPTX64 target. </div><div><br></div><div>Although the NVPTX64 target supports 64-bit arithmetics, since the actual NVIDIA GPU typically has only 32-bit integer registers, one 64-bit arithmetic typically ends up with two machine instructions taking care of the low 32 bits and the high 32 bits respectively. I haven't looked at other GPU targets such as R600, but I suspect this problem is not restricted to the NVPTX64 target. </div><div><br></div><div>Below is a reduced example:</div><div><div>__attribute__((global)) void foo(int n, int *output) {</div><div>  for (int i = 0; i < n; i += 3) {</div><div>    output[i] = i * i;</div><div>  }</div><div>}</div></div><div><br></div><div>Without widening, the loop body in the PTX (a low-level assembly-like language generated by NVPTX64) is:</div><div><div>BB0_2:                                  // =>This Inner Loop Header: Depth=1        </div><div>        mul.lo.s32      %r5, %r6, %r6;                                              </div><div>        st.u32  [%rd4], %r5;                                                        </div><div>        add.s32         %r6, %r6, 3;                                                </div><div>        add.s64         %rd4, %rd4, 12;                                              </div><div>        setp.lt.s32     %p2, %r6, %r3;</div><div>        @%p2 bra        BB0_2;</div></div><div>in which %r6 is the induction variable i. </div><div><br></div><div>With widening, the loop body becomes:</div><div><div>BB0_2:                                  // =>This Inner Loop Header: Depth=1        </div><div>        mul.lo.s64      %rd8, %rd10, %rd10;                                         </div><div>        st.u32  [%rd9], %rd8;                                                         </div><div>        add.s64         %rd10, %rd10, 3;                                            </div><div>        add.s64         %rd9, %rd9, 12;                                             </div><div>        setp.lt.s64     %p2, %rd10, %rd1;                                           </div><div>        @%p2 bra        BB0_2;</div></div><div><br></div><div>Although the number of PTX instructions in both versions are the same, the version with widening uses more mul.lo.s64, add.s64, and setp.lt.s64 instructions which are more expensive than their 32-bit counterparts. Indeed, the SASS code (disassembly of the actual machine code running on GPUs) of the version with widening looks significantly longer. </div><div><br></div><div>Without widening (7 instructions): </div><div><div>.L_1:                                                                               </div><div>        /*0048*/                IMUL R2, R0, R0;                                      </div><div>        /*0050*/                IADD R0, R0, 0x1;                                   </div><div>        /*0058*/                ST.E [R4], R2;                                      </div><div>        /*0060*/                ISETP.NE.AND P0, PT, R0, c[0x0][0x140], PT;             /*0068*/                IADD R4.CC, R4, 0x4;                                </div><div>        /*0070*/                IADD.X R5, R5, RZ;                                  </div><div>        /*0078*/            @P0 BRA `(.L_1);</div></div><div><br></div><div>With widening (12 instructions):</div><div><div>.L_1:                                                                            </div><div>        /*0050*/                IMUL.U32.U32 R6.CC, R4, R4;                      </div><div>        /*0058*/                IADD R0, R0, -0x1;                                    </div><div>        /*0060*/                IMAD.U32.U32.HI.X R8.CC, R4, R4, RZ;             </div><div>        /*0068*/                IMAD.U32.U32.X R8, R5, R4, R8;                   </div><div>        /*0070*/                IMAD.U32.U32 R7, R4, R5, R8;                     </div><div>        /*0078*/                IADD R4.CC, R4, 0x1;                             </div><div>        /*0088*/                ST.E [R2], R6;                                   </div><div>        /*0090*/                IADD.X R5, R5, RZ;                               </div><div>        /*0098*/                ISETP.NE.AND P0, PT, R0, RZ, PT;                 </div><div>        /*00a0*/                IADD R2.CC, R2, 0x4;                             </div><div>        /*00a8*/                IADD.X R3, R3, RZ;                                  </div><div>        /*00b0*/            @P0 BRA `(.L_1);</div></div><div><br></div><div>I hope the issue is clear up to this point. So what's a good solution to fix this issue? I am thinking of having IndVarSimplify consult TargetTransformInfo about the cost of integer arithmetics of different types. If operations on wider integer types are more expensive, IndVarSimplify should disable the widening. </div><div><br></div><div>Another thing I am concerned about: are there other optimizations that make similar assumptions about integer widening? Those might cause performance regression too just as IndVarSimplify does. </div><div><br></div><div>Jingyue</div>