212 lines · plain
1; RUN: opt < %s -passes=nary-reassociate -S | FileCheck %s2 3target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"4 5declare void @foo(i32)6 7; foo(a + c);8; foo((a + (b + c));9; =>10; t = a + c;11; foo(t);12; foo(t + b);13define void @left_reassociate(i32 %a, i32 %b, i32 %c) {14; CHECK-LABEL: @left_reassociate(15 %1 = add i32 %a, %c16; CHECK: [[BASE:%[a-zA-Z0-9]+]] = add i32 %a, %c17 call void @foo(i32 %1)18 %2 = add i32 %b, %c19 %3 = add i32 %a, %220; CHECK: [[RESULT:%[a-zA-Z0-9]+]] = add i32 [[BASE]], %b21 call void @foo(i32 %3)22; CHECK-NEXT: call void @foo(i32 [[RESULT]])23 ret void24}25 26; foo(a + c);27; foo((a + b) + c);28; =>29; t = a + c;30; foo(t);31; foo(t + b);32define void @right_reassociate(i32 %a, i32 %b, i32 %c) {33; CHECK-LABEL: @right_reassociate(34 %1 = add i32 %a, %c35; CHECK: [[BASE:%[a-zA-Z0-9]+]] = add i32 %a, %c36 call void @foo(i32 %1)37 %2 = add i32 %a, %b38 %3 = add i32 %2, %c39; CHECK: [[RESULT:%[a-zA-Z0-9]+]] = add i32 [[BASE]], %b40 call void @foo(i32 %3)41; CHECK-NEXT: call void @foo(i32 [[RESULT]])42 ret void43}44 45; t1 = a + c;46; foo(t1);47; t2 = a + b;48; foo(t2);49; t3 = t2 + c;50; foo(t3);51;52; Do not rewrite t3 into t1 + b because t2 is used elsewhere and is likely free.53define void @no_reassociate(i32 %a, i32 %b, i32 %c) {54; CHECK-LABEL: @no_reassociate(55 %1 = add i32 %a, %c56; CHECK: add i32 %a, %c57 call void @foo(i32 %1)58 %2 = add i32 %a, %b59; CHECK: add i32 %a, %b60 call void @foo(i32 %2)61 %3 = add i32 %2, %c62; CHECK: add i32 %2, %c63 call void @foo(i32 %3)64 ret void65}66 67; if (p1)68; foo(a + c);69; if (p2)70; foo(a + c);71; if (p3)72; foo((a + b) + c);73;74; No action because (a + c) does not dominate ((a + b) + c).75define void @conditional(i1 %p1, i1 %p2, i1 %p3, i32 %a, i32 %b, i32 %c) {76; CHECK-LABEL: @conditional(77entry:78 br i1 %p1, label %then1, label %branch179 80then1:81 %0 = add i32 %a, %c82; CHECK: add i32 %a, %c83 call void @foo(i32 %0)84 br label %branch185 86branch1:87 br i1 %p2, label %then2, label %branch288 89then2:90 %1 = add i32 %a, %c91; CHECK: add i32 %a, %c92 call void @foo(i32 %1)93 br label %branch294 95branch2:96 br i1 %p3, label %then3, label %return97 98then3:99 %2 = add i32 %a, %b100; CHECK: %2 = add i32 %a, %b101 %3 = add i32 %2, %c102; CHECK: add i32 %2, %c103 call void @foo(i32 %3)104 br label %return105 106return:107 ret void108}109 110; This test involves more conditional reassociation candidates. It exercises111; the stack optimization in tryReassociatedAdd that pops the candidates that112; do not dominate the current instruction.113;114; def1115; cond1116; / \117; / \118; cond2 use2119; / \120; / \121; def2 def3122; cond3123; / \124; / \125; def4 use1126;127; NaryReassociate should match use1 with def3, and use2 with def1.128define void @conditional2(i32 %a, i32 %b, i32 %c, i1 %cond1, i1 %cond2, i1 %cond3) {129entry:130 %def1 = add i32 %a, %b131 br i1 %cond1, label %bb1, label %bb6132bb1:133 br i1 %cond2, label %bb2, label %bb3134bb2:135 %def2 = add i32 %a, %b136 call void @foo(i32 %def2)137 ret void138bb3:139 %def3 = add i32 %a, %b140 br i1 %cond3, label %bb4, label %bb5141bb4:142 %def4 = add i32 %a, %b143 call void @foo(i32 %def4)144 ret void145bb5:146 %0 = add i32 %a, %c147 %1 = add i32 %0, %b148; CHECK: [[t1:%[0-9]+]] = add i32 %def3, %c149 call void @foo(i32 %1) ; foo((a + c) + b);150; CHECK-NEXT: call void @foo(i32 [[t1]])151 ret void152bb6:153 %2 = add i32 %a, %c154 %3 = add i32 %2, %b155; CHECK: [[t2:%[0-9]+]] = add i32 %def1, %c156 call void @foo(i32 %3) ; foo((a + c) + b);157; CHECK-NEXT: call void @foo(i32 [[t2]])158 ret void159}160 161; foo((a + b) + c)162; foo(((a + d) + b) + c)163; =>164; t = (a + b) + c;165; foo(t);166; foo(t + d);167define void @quaternary(i32 %a, i32 %b, i32 %c, i32 %d) {168; CHECK-LABEL: @quaternary(169 %1 = add i32 %a, %b170 %2 = add i32 %1, %c171 call void @foo(i32 %2)172; CHECK: call void @foo(i32 [[TMP1:%[a-zA-Z0-9]]])173 %3 = add i32 %a, %d174 %4 = add i32 %3, %b175 %5 = add i32 %4, %c176; CHECK: [[TMP2:%[a-zA-Z0-9]]] = add i32 [[TMP1]], %d177 call void @foo(i32 %5)178; CHECK: call void @foo(i32 [[TMP2]]179 ret void180}181 182define void @iterative(i32 %a, i32 %b, i32 %c) {183 %ab = add i32 %a, %b184 %abc = add i32 %ab, %c185 call void @foo(i32 %abc)186 187 %ab2 = add i32 %ab, %b188 %ab2c = add i32 %ab2, %c189; CHECK: %ab2c = add i32 %abc, %b190 call void @foo(i32 %ab2c)191; CHECK-NEXT: call void @foo(i32 %ab2c)192 193 %ab3 = add i32 %ab2, %b194 %ab3c = add i32 %ab3, %c195; CHECK-NEXT: %ab3c = add i32 %ab2c, %b196 call void @foo(i32 %ab3c)197; CHECK-NEXT: call void @foo(i32 %ab3c)198 199 ret void200}201 202define void @avoid_infinite_loop(i32 %a, i32 %b) {203; CHECK-LABEL: @avoid_infinite_loop204 %ab = add i32 %a, %b205; CHECK-NEXT: %ab206 %ab2 = add i32 %ab, %b207; CHECK-NEXT: %ab2208 call void @foo(i32 %ab2)209; CHECK-NEXT: @foo(i32 %ab2)210 ret void211}212