184 lines · plain
1; RUN: opt -passes=loop-idiom < %s -mtriple=x86_64-apple-darwin -mcpu=corei7 -S | FileCheck %s2 3target triple = "x86_64-apple-macosx10.8.0"4 5;To recognize this pattern:6;int popcount(unsigned long long a) {7; int c = 0;8; while (a) {9; c++;10; a &= a - 1;11; }12; return c;13;}14;15; CHECK: entry16; CHECK: llvm.ctpop.i6417; CHECK: ret18define i32 @popcount(i64 %a) nounwind uwtable readnone ssp {19entry:20 %tobool3 = icmp eq i64 %a, 021 br i1 %tobool3, label %while.end, label %while.body22 23while.body: ; preds = %entry, %while.body24 %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]25 %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]26 %inc = add nsw i32 %c.05, 127 %sub = add i64 %a.addr.04, -128 %and = and i64 %sub, %a.addr.0429 %tobool = icmp eq i64 %and, 030 br i1 %tobool, label %while.end, label %while.body31 32while.end: ; preds = %while.body, %entry33 %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]34 ret i32 %c.0.lcssa35}36 37; To recognize this pattern:38;int popcount(unsigned long long a, int mydata1, int mydata2) {39; int c = 0;40; while (a) {41; c++;42; a &= a - 1;43; mydata1 *= c;44; mydata2 *= (int)a;45; }46; return c + mydata1 + mydata2;47;}48; CHECK: entry49; CHECK: llvm.ctpop.i6450; CHECK: ret51define i32 @popcount2(i64 %a, i32 %mydata1, i32 %mydata2) nounwind uwtable readnone ssp {52entry:53 %tobool9 = icmp eq i64 %a, 054 br i1 %tobool9, label %while.end, label %while.body55 56while.body: ; preds = %entry, %while.body57 %c.013 = phi i32 [ %inc, %while.body ], [ 0, %entry ]58 %mydata2.addr.012 = phi i32 [ %mul1, %while.body ], [ %mydata2, %entry ]59 %mydata1.addr.011 = phi i32 [ %mul, %while.body ], [ %mydata1, %entry ]60 %a.addr.010 = phi i64 [ %and, %while.body ], [ %a, %entry ]61 %inc = add nsw i32 %c.013, 162 %sub = add i64 %a.addr.010, -163 %and = and i64 %sub, %a.addr.01064 %mul = mul nsw i32 %inc, %mydata1.addr.01165 %conv = trunc i64 %and to i3266 %mul1 = mul nsw i32 %conv, %mydata2.addr.01267 %tobool = icmp eq i64 %and, 068 br i1 %tobool, label %while.end, label %while.body69 70while.end: ; preds = %while.body, %entry71 %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]72 %mydata2.addr.0.lcssa = phi i32 [ %mydata2, %entry ], [ %mul1, %while.body ]73 %mydata1.addr.0.lcssa = phi i32 [ %mydata1, %entry ], [ %mul, %while.body ]74 %add = add i32 %mydata2.addr.0.lcssa, %mydata1.addr.0.lcssa75 %add2 = add i32 %add, %c.0.lcssa76 ret i32 %add277}78 79; Some variants once cause crash80 81define i32 @PopCntCrash1(i64 %a) nounwind uwtable readnone ssp {82entry:83 %tobool3 = icmp eq i64 %a, 084 br i1 %tobool3, label %while.end, label %while.body85 86while.body: ; preds = %entry, %while.body87 %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]88 %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]89 %t = add i32 %c.05, %c.0590 %inc = add nsw i32 %t, 191 %sub = add i64 %a.addr.04, -192 %and = and i64 %sub, %a.addr.0493 %tobool = icmp eq i64 %and, 094 br i1 %tobool, label %while.end, label %while.body95 96while.end: ; preds = %while.body, %entry97 %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]98 ret i32 %c.0.lcssa99 100; CHECK: entry101; CHECK: ret102}103 104define i32 @PopCntCrash2(i64 %a, i32 %b) nounwind uwtable readnone ssp {105entry:106 %tobool3 = icmp eq i64 %a, 0107 br i1 %tobool3, label %while.end, label %while.body108 109while.body: ; preds = %entry, %while.body110 %c.05 = phi i32 [ %inc, %while.body ], [ %b, %entry ]111 %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]112 %inc = add nsw i32 %c.05, 1113 %sub = add i64 %a.addr.04, -1114 %and = and i64 %sub, %a.addr.04115 %tobool = icmp eq i64 %and, 0116 br i1 %tobool, label %while.end, label %while.body117 118while.end: ; preds = %while.body, %entry119 %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]120 ret i32 %c.0.lcssa121}122 123define i32 @PopCntCrash3(i64 %a, i32 %x) {124entry:125 %tobool3 = icmp eq i64 %a, 0126 %cmp = icmp eq i32 %x, 0127 br i1 %tobool3, label %while.end, label %while.body128 129while.body: ; preds = %entry, %while.body130 %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]131 %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]132 %inc = add nsw i32 %c.05, 1133 %sub = add i64 %a.addr.04, -1134 %and = and i64 %sub, %a.addr.04135 %tobool = icmp eq i64 %and, 0136 br i1 %cmp, label %while.end, label %while.body137 138while.end: ; preds = %while.body, %entry139 %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]140 ret i32 %c.0.lcssa141}142 143; The a & (a - 1) in the loop is a & (b - 1) in this code. Make sure we don't144; convert it.145define i32 @popcount_bad(i64 %a, i64 %b) nounwind uwtable readnone ssp {146; CHECK-LABEL: @popcount_bad(147; CHECK-NEXT: entry:148; CHECK-NEXT: [[TOBOOL3:%.*]] = icmp eq i64 [[A:%.*]], 0149; CHECK-NEXT: br i1 [[TOBOOL3]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]150; CHECK: while.body.preheader:151; CHECK-NEXT: br label [[WHILE_BODY:%.*]]152; CHECK: while.body:153; CHECK-NEXT: [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]154; CHECK-NEXT: [[A_ADDR_04:%.*]] = phi i64 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]155; CHECK-NEXT: [[INC]] = add nsw i32 [[C_05]], 1156; CHECK-NEXT: [[SUB:%.*]] = add i64 [[B:%.*]], -1157; CHECK-NEXT: [[AND]] = and i64 [[SUB]], [[A_ADDR_04]]158; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i64 [[AND]], 0159; CHECK-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]160; CHECK: while.end.loopexit:161; CHECK-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]162; CHECK-NEXT: br label [[WHILE_END]]163; CHECK: while.end:164; CHECK-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]165; CHECK-NEXT: ret i32 [[C_0_LCSSA]]166;167entry:168 %tobool3 = icmp eq i64 %a, 0169 br i1 %tobool3, label %while.end, label %while.body170 171while.body: ; preds = %entry, %while.body172 %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]173 %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]174 %inc = add nsw i32 %c.05, 1175 %sub = add i64 %b, -1176 %and = and i64 %sub, %a.addr.04177 %tobool = icmp eq i64 %and, 0178 br i1 %tobool, label %while.end, label %while.body179 180while.end: ; preds = %while.body, %entry181 %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]182 ret i32 %c.0.lcssa183}184