test/Transforms/LoopInterchange/profitability.ll

   1 ; RUN: opt < %s -loop-interchange -pass-remarks-output=%t -verify-dom-info -verify-loop-info \
   2 ; RUN:     -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange
   3 ; RUN: FileCheck -input-file %t %s
   4
   5 ;; We test profitability model in these test cases.
   6
   7 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   8 target triple = "x86_64-unknown-linux-gnu"
   9
  10 @A = common global [100 x [100 x i32]] zeroinitializer
  11 @B = common global [100 x [100 x i32]] zeroinitializer
  12
  13 ;;---------------------------------------Test case 01---------------------------------
  14 ;; Loops interchange will result in code vectorization and hence profitable. Check for interchange.
  15 ;;   for(int i=1;i<100;i++)
  16 ;;     for(int j=1;j<100;j++)
  17 ;;       A[j][i] = A[j - 1][i] + B[j][i];
  18 ;; FIXME: DA misses this case after D35430
  19
  20 ; CHECK:      Name:            Dependence
  21 ; CHECK-NEXT: Function:        interchange_01
  22 define void @interchange_01() {
  23 entry:
  24   br label %for2.preheader
  25
  26 for2.preheader:
  27   %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]
  28   br label %for2
  29
  30 for2:
  31   %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]
  32   %j.prev = add nsw i64 %j,  -1
  33   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j.prev, i64 %i30
  34   %lv1 = load i32, i32* %arrayidx5
  35   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %j,  i64 %i30
  36   %lv2 = load i32, i32* %arrayidx9
  37   %add = add nsw i32 %lv1, %lv2
  38   %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j,  i64 %i30
  39   store i32 %add, i32* %arrayidx13
  40   %i.next = add nuw nsw i64 %j,  1
  41   %exitcond = icmp eq i64 %j,  99
  42   br i1 %exitcond, label %for1.inc14, label %for2
  43
  44 for1.inc14:
  45   %i.next31 = add nuw nsw i64 %i30, 1
  46   %exitcond33 = icmp eq i64 %i30, 99
  47   br i1 %exitcond33, label %for.end16, label %for2.preheader
  48
  49 for.end16:
  50   ret void
  51 }
  52
  53 ;; ---------------------------------------Test case 02---------------------------------
  54 ;; Check loop interchange profitability model.
  55 ;; This tests profitability model when operands of getelementpointer and not exactly the induction variable but some
  56 ;; arithmetic operation on them.
  57 ;;   for(int i=1;i<N;i++)
  58 ;;    for(int j=1;j<N;j++)
  59 ;;       A[j-1][i-1] = A[j - 1][i-1] + B[j-1][i-1];
  60
  61 ; CHECK:      Name:            Interchanged
  62 ; CHECK-NEXT: Function:        interchange_02
  63 define void @interchange_02() {
  64 entry:
  65   br label %for1.header
  66
  67 for1.header:
  68   %i35 = phi i64 [ 1, %entry ], [ %i.next36, %for1.inc19 ]
  69   %i.prev = add nsw i64 %i35, -1
  70   br label %for2
  71
  72 for2:
  73   %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
  74   %j.prev = add nsw i64 %j,  -1
  75   %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j.prev, i64 %i.prev
  76   %lv1 = load i32, i32* %arrayidx6
  77   %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %j.prev, i64 %i.prev
  78   %lv2 = load i32, i32* %arrayidx12
  79   %add = add nsw i32 %lv1, %lv2
  80   store i32 %add, i32* %arrayidx6
  81   %i.next = add nuw nsw i64 %j,  1
  82   %exitcond = icmp eq i64 %j,  99
  83   br i1 %exitcond, label %for1.inc19, label %for2
  84
  85 for1.inc19:
  86   %i.next36 = add nuw nsw i64 %i35, 1
  87   %exitcond39 = icmp eq i64 %i35, 99
  88   br i1 %exitcond39, label %for.end21, label %for1.header
  89
  90 for.end21:
  91   ret void
  92 }
  93
  94 ;;---------------------------------------Test case 03---------------------------------
  95 ;; Loops interchange is not profitable.
  96 ;;   for(int i=1;i<100;i++)
  97 ;;     for(int j=1;j<100;j++)
  98 ;;       A[i-1][j-1] = A[i - 1][j-1] + B[i][j];
  99
 100 ; CHECK:      Name:            InterchangeNotProfitable
 101 ; CHECK-NEXT: Function:        interchange_03
 102 define void @interchange_03(){
 103 entry:
 104   br label %for1.header
 105
 106 for1.header:
 107   %i34 = phi i64 [ 1, %entry ], [ %i.next35, %for1.inc17 ]
 108   %i.prev = add nsw i64 %i34, -1
 109   br label %for2
 110
 111 for2:
 112   %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
 113   %j.prev = add nsw i64 %j, -1
 114   %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %i.prev, i64 %j.prev
 115   %lv1 = load i32, i32* %arrayidx6
 116   %arrayidx10 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %i34, i64 %j
 117   %lv2 = load i32, i32* %arrayidx10
 118   %add = add nsw i32 %lv1, %lv2
 119   store i32 %add, i32* %arrayidx6
 120   %i.next = add nuw nsw i64 %j,  1
 121   %exitcond = icmp eq i64 %j,  99
 122   br i1 %exitcond, label %for1.inc17, label %for2
 123
 124 for1.inc17:
 125   %i.next35 = add nuw nsw i64 %i34, 1
 126   %exitcond38 = icmp eq i64 %i34, 99
 127   br i1 %exitcond38, label %for.end19, label %for1.header
 128
 129 for.end19:
 130   ret void
 131 }
 132
 133 ;; Loops should not be interchanged in this case as it is not profitable.
 134 ;;  for(int i=0;i<100;i++)
 135 ;;    for(int j=0;j<100;j++)
 136 ;;      A[i][j] = A[i][j]+k;
 137
 138 ; CHECK:      Name:            InterchangeNotProfitable
 139 ; CHECK-NEXT: Function:        interchange_04
 140 define void @interchange_04(i32 %k) {
 141 entry:
 142   br label %for.cond1.preheader
 143
 144 for.cond1.preheader:
 145   %indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ]
 146   br label %for.body3
 147
 148 for.body3:
 149   %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]
 150   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv
 151   %0 = load i32, i32* %arrayidx5
 152   %add = add nsw i32 %0, %k
 153   store i32 %add, i32* %arrayidx5
 154   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 155   %exitcond = icmp eq i64 %indvars.iv.next, 100
 156   br i1 %exitcond, label %for.inc10, label %for.body3
 157
 158 for.inc10:
 159   %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
 160   %exitcond23 = icmp eq i64 %indvars.iv.next22, 100
 161   br i1 %exitcond23, label %for.end12, label %for.cond1.preheader
 162
 163 for.end12:
 164   ret void
 165 }