1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2 ; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info -S | FileCheck %s 3 4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 5 target triple = "x86_64-unknown-linux-gnu" 6 7 @A = common global [100 x [100 x i64]] zeroinitializer 8 @B = common global [100 x i64] zeroinitializer 9 10 ;; for(int i=0;i<100;i++) 11 ;; for(int j=0;j<100;j++) 12 ;; A[j][i] = A[j][i]+k; 13 14 define void @interchange_01(i64 %k, i64 %N) { 15 ; CHECK-LABEL: @interchange_01( 16 ; CHECK-NEXT: entry: 17 ; CHECK-NEXT: br label [[FOR2_PREHEADER:%.*]] 18 ; CHECK: for1.header.preheader: 19 ; CHECK-NEXT: br label [[FOR1_HEADER:%.*]] 20 ; CHECK: for1.header: 21 ; CHECK-NEXT: [[INDVARS_IV23:%.*]] = phi i64 [ [[INDVARS_IV_NEXT24:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ] 22 ; CHECK-NEXT: br label [[FOR2_SPLIT1:%.*]] 23 ; CHECK: for2.preheader: 24 ; CHECK-NEXT: br label [[FOR2:%.*]] 25 ; CHECK: for2: 26 ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR2_SPLIT:%.*]] ], [ 0, [[FOR2_PREHEADER]] ] 27 ; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]] 28 ; CHECK: for2.split1: 29 ; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV23]] 30 ; CHECK-NEXT: [[LV:%.*]] = load i64, i64* [[ARRAYIDX5]] 31 ; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[LV]], [[K:%.*]] 32 ; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]] 33 ; CHECK-NEXT: br label [[FOR1_INC10]] 34 ; CHECK: for2.split: 35 ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1 36 ; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 99 37 ; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_END12:%.*]], label [[FOR2]] 38 ; CHECK: for1.inc10: 39 ; CHECK-NEXT: [[INDVARS_IV_NEXT24]] = add nuw nsw i64 [[INDVARS_IV23]], 1 40 ; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[INDVARS_IV23]], 99 41 ; CHECK-NEXT: br i1 [[EXITCOND26]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]] 42 ; CHECK: for.end12: 43 ; CHECK-NEXT: ret void 44 ; 45 entry: 46 br label %for1.header 47 48 for1.header: 49 %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ] 50 br label %for2 51 52 for2: 53 %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ] 54 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23 55 %lv = load i64, i64* %arrayidx5 56 %add = add nsw i64 %lv, %k 57 store i64 %add, i64* %arrayidx5 58 %j.next = add nuw nsw i64 %j, 1 59 %exitcond = icmp eq i64 %j, 99 60 br i1 %exitcond, label %for1.inc10, label %for2 61 62 for1.inc10: 63 %j.next24 = add nuw nsw i64 %j23, 1 64 %exitcond26 = icmp eq i64 %j23, 99 65 br i1 %exitcond26, label %for.end12, label %for1.header 66 67 for.end12: 68 ret void 69 } 70 71 ;; for(int i=0;i<100;i++) 72 ;; for(int j=100;j>=0;j--) 73 ;; A[j][i] = A[j][i]+k; 74 75 define void @interchange_02(i64 %k) { 76 ; CHECK-LABEL: @interchange_02( 77 ; CHECK-NEXT: entry: 78 ; CHECK-NEXT: br label [[FOR3_PREHEADER:%.*]] 79 ; CHECK: for1.header.preheader: 80 ; CHECK-NEXT: br label [[FOR1_HEADER:%.*]] 81 ; CHECK: for1.header: 82 ; CHECK-NEXT: [[INDVARS_IV19:%.*]] = phi i64 [ [[INDVARS_IV_NEXT20:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ] 83 ; CHECK-NEXT: br label [[FOR3_SPLIT1:%.*]] 84 ; CHECK: for3.preheader: 85 ; CHECK-NEXT: br label [[FOR3:%.*]] 86 ; CHECK: for3: 87 ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR3_SPLIT:%.*]] ], [ 100, [[FOR3_PREHEADER]] ] 88 ; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]] 89 ; CHECK: for3.split1: 90 ; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV19]] 91 ; CHECK-NEXT: [[TMP0:%.*]] = load i64, i64* [[ARRAYIDX5]] 92 ; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[TMP0]], [[K:%.*]] 93 ; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]] 94 ; CHECK-NEXT: br label [[FOR1_INC10]] 95 ; CHECK: for3.split: 96 ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 97 ; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i64 [[INDVARS_IV]], 0 98 ; CHECK-NEXT: br i1 [[CMP2]], label [[FOR3]], label [[FOR_END11:%.*]] 99 ; CHECK: for1.inc10: 100 ; CHECK-NEXT: [[INDVARS_IV_NEXT20]] = add nuw nsw i64 [[INDVARS_IV19]], 1 101 ; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT20]], 100 102 ; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR3_SPLIT]], label [[FOR1_HEADER]] 103 ; CHECK: for.end11: 104 ; CHECK-NEXT: ret void 105 ; 106 entry: 107 br label %for1.header 108 109 for1.header: 110 %j19 = phi i64 [ 0, %entry ], [ %j.next20, %for1.inc10 ] 111 br label %for3 112 113 for3: 114 %j = phi i64 [ 100, %for1.header ], [ %j.next, %for3 ] 115 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j19 116 %0 = load i64, i64* %arrayidx5 117 %add = add nsw i64 %0, %k 118 store i64 %add, i64* %arrayidx5 119 %j.next = add nsw i64 %j, -1 120 %cmp2 = icmp sgt i64 %j, 0 121 br i1 %cmp2, label %for3, label %for1.inc10 122 123 for1.inc10: 124 %j.next20 = add nuw nsw i64 %j19, 1 125 %exitcond = icmp eq i64 %j.next20, 100 126 br i1 %exitcond, label %for.end11, label %for1.header 127 128 for.end11: 129 ret void 130 } 131 132 ;; Test to make sure we can handle output dependencies. 133 ;; 134 ;; for (int i = 1; i < 100; ++i) 135 ;; for(int j = 1; j < 99; ++j) { 136 ;; A[j][i] = i; 137 ;; A[j][i+1] = j; 138 ;; } 139 ;; FIXME: DA misses this case after D35430 140 141 define void @interchange_10() { 142 entry: 143 br label %for1.header 144 145 for1.header: 146 %j23 = phi i64 [ 1, %entry ], [ %j.next24, %for1.inc10 ] 147 %j.next24 = add nuw nsw i64 %j23, 1 148 br label %for2 149 150 for2: 151 %j = phi i64 [ %j.next, %for2 ], [ 1, %for1.header ] 152 %j.next = add nuw nsw i64 %j, 1 153 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23 154 store i64 %j, i64* %arrayidx5 155 %arrayidx10 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j.next24 156 store i64 %j23, i64* %arrayidx10 157 %exitcond = icmp eq i64 %j, 99 158 br i1 %exitcond, label %for1.inc10, label %for2 159 160 for1.inc10: 161 %exitcond26 = icmp eq i64 %j23, 98 162 br i1 %exitcond26, label %for.end12, label %for1.header 163 164 for.end12: 165 ret void 166 167 } 168
