240 lines · plain
1; RUN: llc < %s -block-placement-exit-block-bias=20 -no-phi-elim-live-out-early-exit | FileCheck %s2target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"3target triple = "x86_64-apple-macosx10.9.0"4 5; This is longest_match, the hot function from zlib's deflate implementation.6 7%struct.internal_state = type { ptr, i32, ptr, i64, ptr, i32, i32, ptr, i32, i8, i32, i32, i32, i32, ptr, i64, ptr, ptr, i32, i32, i32, i32, i32, i64, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, [573 x %struct.ct_data_s], [61 x %struct.ct_data_s], [39 x %struct.ct_data_s], %struct.tree_desc_s, %struct.tree_desc_s, %struct.tree_desc_s, [16 x i16], [573 x i32], i32, i32, [573 x i8], ptr, i32, i32, ptr, i64, i64, i32, i32, i16, i32, i64 }8%struct.z_stream_s = type { ptr, i32, i64, ptr, i32, i64, ptr, ptr, ptr, ptr, ptr, i32, i64, i64 }9%struct.gz_header_s = type { i32, i64, i32, i32, ptr, i32, i32, ptr, i32, ptr, i32, i32, i32 }10%struct.ct_data_s = type { %union.anon, %union.anon.0 }11%union.anon = type { i16 }12%union.anon.0 = type { i16 }13%struct.tree_desc_s = type { ptr, i32, ptr }14%struct.static_tree_desc_s = type { i32 }15 16; CHECK-LABEL: longest_match:17 18; Verify that there are no spills or reloads in the loop exit block. This loop19; is mostly cold, only %do.cond125 and %land.rhs131 are hot.20; CHECK: %do.cond12521; CHECK-NOT: {{Spill|Reload}}22; CHECK: jbe23 24; Verify that block placement doesn't destroy source order. It's important that25; the two hot blocks are laid out close to each other.26; CHECK-NEXT: %land.rhs13127; CHECK: jne28define i32 @longest_match(ptr nocapture %s, i32 %cur_match) nounwind {29entry:30 %max_chain_length = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 3131 %0 = load i32, ptr %max_chain_length, align 432 %window = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 1433 %1 = load ptr, ptr %window, align 834 %strstart = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 2735 %2 = load i32, ptr %strstart, align 436 %idx.ext = zext i32 %2 to i6437 %add.ptr = getelementptr inbounds i8, ptr %1, i64 %idx.ext38 %prev_length = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 3039 %3 = load i32, ptr %prev_length, align 440 %nice_match1 = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 3641 %4 = load i32, ptr %nice_match1, align 442 %w_size = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 1143 %5 = load i32, ptr %w_size, align 444 %sub = add i32 %5, -26245 %cmp = icmp ugt i32 %2, %sub46 %sub6 = sub i32 %2, %sub47 %sub6. = select i1 %cmp, i32 %sub6, i32 048 %prev7 = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 1649 %6 = load ptr, ptr %prev7, align 850 %w_mask = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 1351 %7 = load i32, ptr %w_mask, align 452 %add.ptr11.sum = add i64 %idx.ext, 25853 %add.ptr12 = getelementptr inbounds i8, ptr %1, i64 %add.ptr11.sum54 %sub13 = add nsw i32 %3, -155 %idxprom = sext i32 %sub13 to i6456 %add.ptr.sum = add i64 %idxprom, %idx.ext57 %arrayidx = getelementptr inbounds i8, ptr %1, i64 %add.ptr.sum58 %8 = load i8, ptr %arrayidx, align 159 %idxprom14 = sext i32 %3 to i6460 %add.ptr.sum213 = add i64 %idxprom14, %idx.ext61 %arrayidx15 = getelementptr inbounds i8, ptr %1, i64 %add.ptr.sum21362 %9 = load i8, ptr %arrayidx15, align 163 %good_match = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 3564 %10 = load i32, ptr %good_match, align 465 %cmp17 = icmp ult i32 %3, %1066 %shr = lshr i32 %0, 267 %chain_length.0 = select i1 %cmp17, i32 %0, i32 %shr68 %lookahead = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 2969 %11 = load i32, ptr %lookahead, align 470 %cmp18 = icmp ugt i32 %4, %1171 %. = select i1 %cmp18, i32 %11, i32 %472 %match_start = getelementptr inbounds %struct.internal_state, ptr %s, i64 0, i32 2873 %add.ptr.sum217 = add i64 %idx.ext, 174 %arrayidx44 = getelementptr inbounds i8, ptr %1, i64 %add.ptr.sum21775 %add.ptr.sum218 = add i64 %idx.ext, 276 %add.ptr50 = getelementptr inbounds i8, ptr %1, i64 %add.ptr.sum21877 %sub.ptr.lhs.cast = ptrtoint ptr %add.ptr12 to i6478 br label %do.body79 80do.body: ; preds = %land.rhs131, %entry81 %best_len.0 = phi i32 [ %best_len.1, %land.rhs131 ], [ %3, %entry ]82 %chain_length.1 = phi i32 [ %dec, %land.rhs131 ], [ %chain_length.0, %entry ]83 %cur_match.addr.0 = phi i32 [ %conv128, %land.rhs131 ], [ %cur_match, %entry ]84 %scan_end1.0 = phi i8 [ %scan_end1.1, %land.rhs131 ], [ %8, %entry ]85 %scan_end.0 = phi i8 [ %scan_end.1, %land.rhs131 ], [ %9, %entry ]86 %idx.ext23 = zext i32 %cur_match.addr.0 to i6487 %add.ptr24 = getelementptr inbounds i8, ptr %1, i64 %idx.ext2388 %idxprom25 = sext i32 %best_len.0 to i6489 %add.ptr24.sum = add i64 %idx.ext23, %idxprom2590 %arrayidx26 = getelementptr inbounds i8, ptr %1, i64 %add.ptr24.sum91 %12 = load i8, ptr %arrayidx26, align 192 %cmp28 = icmp eq i8 %12, %scan_end.093 br i1 %cmp28, label %lor.lhs.false, label %do.cond12594 95lor.lhs.false: ; preds = %do.body96 %sub30 = add nsw i32 %best_len.0, -197 %idxprom31 = sext i32 %sub30 to i6498 %add.ptr24.sum214 = add i64 %idx.ext23, %idxprom3199 %arrayidx32 = getelementptr inbounds i8, ptr %1, i64 %add.ptr24.sum214100 %13 = load i8, ptr %arrayidx32, align 1101 %cmp35 = icmp eq i8 %13, %scan_end1.0102 br i1 %cmp35, label %lor.lhs.false37, label %do.cond125103 104lor.lhs.false37: ; preds = %lor.lhs.false105 %14 = load i8, ptr %add.ptr24, align 1106 %15 = load i8, ptr %add.ptr, align 1107 %cmp40 = icmp eq i8 %14, %15108 br i1 %cmp40, label %lor.lhs.false42, label %do.cond125109 110lor.lhs.false42: ; preds = %lor.lhs.false37111 %add.ptr24.sum215 = add i64 %idx.ext23, 1112 %incdec.ptr = getelementptr inbounds i8, ptr %1, i64 %add.ptr24.sum215113 %16 = load i8, ptr %incdec.ptr, align 1114 %17 = load i8, ptr %arrayidx44, align 1115 %cmp46 = icmp eq i8 %16, %17116 br i1 %cmp46, label %if.end49, label %do.cond125117 118if.end49: ; preds = %lor.lhs.false42119 %incdec.ptr.sum = add i64 %idx.ext23, 2120 %incdec.ptr51 = getelementptr inbounds i8, ptr %1, i64 %incdec.ptr.sum121 br label %do.cond122 123do.cond: ; preds = %land.lhs.true100, %if.end49124 %match.0 = phi ptr [ %incdec.ptr51, %if.end49 ], [ %incdec.ptr103, %land.lhs.true100 ]125 %scan.1 = phi ptr [ %add.ptr50, %if.end49 ], [ %incdec.ptr101, %land.lhs.true100 ]126 %incdec.ptr53 = getelementptr inbounds i8, ptr %scan.1, i64 1127 %18 = load i8, ptr %incdec.ptr53, align 1128 %incdec.ptr55 = getelementptr inbounds i8, ptr %match.0, i64 1129 %19 = load i8, ptr %incdec.ptr55, align 1130 %cmp57 = icmp eq i8 %18, %19131 br i1 %cmp57, label %land.lhs.true, label %do.end132 133land.lhs.true: ; preds = %do.cond134 %incdec.ptr59 = getelementptr inbounds i8, ptr %scan.1, i64 2135 %20 = load i8, ptr %incdec.ptr59, align 1136 %incdec.ptr61 = getelementptr inbounds i8, ptr %match.0, i64 2137 %21 = load i8, ptr %incdec.ptr61, align 1138 %cmp63 = icmp eq i8 %20, %21139 br i1 %cmp63, label %land.lhs.true65, label %do.end140 141land.lhs.true65: ; preds = %land.lhs.true142 %incdec.ptr66 = getelementptr inbounds i8, ptr %scan.1, i64 3143 %22 = load i8, ptr %incdec.ptr66, align 1144 %incdec.ptr68 = getelementptr inbounds i8, ptr %match.0, i64 3145 %23 = load i8, ptr %incdec.ptr68, align 1146 %cmp70 = icmp eq i8 %22, %23147 br i1 %cmp70, label %land.lhs.true72, label %do.end148 149land.lhs.true72: ; preds = %land.lhs.true65150 %incdec.ptr73 = getelementptr inbounds i8, ptr %scan.1, i64 4151 %24 = load i8, ptr %incdec.ptr73, align 1152 %incdec.ptr75 = getelementptr inbounds i8, ptr %match.0, i64 4153 %25 = load i8, ptr %incdec.ptr75, align 1154 %cmp77 = icmp eq i8 %24, %25155 br i1 %cmp77, label %land.lhs.true79, label %do.end156 157land.lhs.true79: ; preds = %land.lhs.true72158 %incdec.ptr80 = getelementptr inbounds i8, ptr %scan.1, i64 5159 %26 = load i8, ptr %incdec.ptr80, align 1160 %incdec.ptr82 = getelementptr inbounds i8, ptr %match.0, i64 5161 %27 = load i8, ptr %incdec.ptr82, align 1162 %cmp84 = icmp eq i8 %26, %27163 br i1 %cmp84, label %land.lhs.true86, label %do.end164 165land.lhs.true86: ; preds = %land.lhs.true79166 %incdec.ptr87 = getelementptr inbounds i8, ptr %scan.1, i64 6167 %28 = load i8, ptr %incdec.ptr87, align 1168 %incdec.ptr89 = getelementptr inbounds i8, ptr %match.0, i64 6169 %29 = load i8, ptr %incdec.ptr89, align 1170 %cmp91 = icmp eq i8 %28, %29171 br i1 %cmp91, label %land.lhs.true93, label %do.end172 173land.lhs.true93: ; preds = %land.lhs.true86174 %incdec.ptr94 = getelementptr inbounds i8, ptr %scan.1, i64 7175 %30 = load i8, ptr %incdec.ptr94, align 1176 %incdec.ptr96 = getelementptr inbounds i8, ptr %match.0, i64 7177 %31 = load i8, ptr %incdec.ptr96, align 1178 %cmp98 = icmp eq i8 %30, %31179 br i1 %cmp98, label %land.lhs.true100, label %do.end180 181land.lhs.true100: ; preds = %land.lhs.true93182 %incdec.ptr101 = getelementptr inbounds i8, ptr %scan.1, i64 8183 %32 = load i8, ptr %incdec.ptr101, align 1184 %incdec.ptr103 = getelementptr inbounds i8, ptr %match.0, i64 8185 %33 = load i8, ptr %incdec.ptr103, align 1186 %cmp105 = icmp eq i8 %32, %33187 %cmp107 = icmp ult ptr %incdec.ptr101, %add.ptr12188 %or.cond = and i1 %cmp105, %cmp107189 br i1 %or.cond, label %do.cond, label %do.end190 191do.end: ; preds = %land.lhs.true100, %land.lhs.true93, %land.lhs.true86, %land.lhs.true79, %land.lhs.true72, %land.lhs.true65, %land.lhs.true, %do.cond192 %scan.2 = phi ptr [ %incdec.ptr101, %land.lhs.true100 ], [ %incdec.ptr94, %land.lhs.true93 ], [ %incdec.ptr87, %land.lhs.true86 ], [ %incdec.ptr80, %land.lhs.true79 ], [ %incdec.ptr73, %land.lhs.true72 ], [ %incdec.ptr66, %land.lhs.true65 ], [ %incdec.ptr59, %land.lhs.true ], [ %incdec.ptr53, %do.cond ]193 %sub.ptr.rhs.cast = ptrtoint ptr %scan.2 to i64194 %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast195 %conv109 = trunc i64 %sub.ptr.sub to i32196 %sub110 = sub nsw i32 258, %conv109197 %cmp112 = icmp sgt i32 %sub110, %best_len.0198 br i1 %cmp112, label %if.then114, label %do.cond125199 200if.then114: ; preds = %do.end201 store i32 %cur_match.addr.0, ptr %match_start, align 4202 %cmp115 = icmp slt i32 %sub110, %.203 br i1 %cmp115, label %if.end118, label %do.end135204 205if.end118: ; preds = %if.then114206 %sub119 = add nsw i32 %sub110, -1207 %idxprom120 = sext i32 %sub119 to i64208 %add.ptr111.sum = add i64 %idxprom120, %idx.ext209 %arrayidx121 = getelementptr inbounds i8, ptr %1, i64 %add.ptr111.sum210 %34 = load i8, ptr %arrayidx121, align 1211 %idxprom122 = sext i32 %sub110 to i64212 %add.ptr111.sum216 = add i64 %idxprom122, %idx.ext213 %arrayidx123 = getelementptr inbounds i8, ptr %1, i64 %add.ptr111.sum216214 %35 = load i8, ptr %arrayidx123, align 1215 br label %do.cond125216 217do.cond125: ; preds = %if.end118, %do.end, %lor.lhs.false42, %lor.lhs.false37, %lor.lhs.false, %do.body218 %best_len.1 = phi i32 [ %best_len.0, %do.body ], [ %best_len.0, %lor.lhs.false ], [ %best_len.0, %lor.lhs.false37 ], [ %best_len.0, %lor.lhs.false42 ], [ %sub110, %if.end118 ], [ %best_len.0, %do.end ]219 %scan_end1.1 = phi i8 [ %scan_end1.0, %do.body ], [ %scan_end1.0, %lor.lhs.false ], [ %scan_end1.0, %lor.lhs.false37 ], [ %scan_end1.0, %lor.lhs.false42 ], [ %34, %if.end118 ], [ %scan_end1.0, %do.end ]220 %scan_end.1 = phi i8 [ %scan_end.0, %do.body ], [ %scan_end.0, %lor.lhs.false ], [ %scan_end.0, %lor.lhs.false37 ], [ %scan_end.0, %lor.lhs.false42 ], [ %35, %if.end118 ], [ %scan_end.0, %do.end ]221 %and = and i32 %cur_match.addr.0, %7222 %idxprom126 = zext i32 %and to i64223 %arrayidx127 = getelementptr inbounds i16, ptr %6, i64 %idxprom126224 %36 = load i16, ptr %arrayidx127, align 2225 %conv128 = zext i16 %36 to i32226 %cmp129 = icmp ugt i32 %conv128, %sub6.227 br i1 %cmp129, label %land.rhs131, label %do.end135228 229land.rhs131: ; preds = %do.cond125230 %dec = add i32 %chain_length.1, -1231 %cmp132 = icmp eq i32 %dec, 0232 br i1 %cmp132, label %do.end135, label %do.body233 234do.end135: ; preds = %land.rhs131, %do.cond125, %if.then114235 %best_len.2 = phi i32 [ %best_len.1, %land.rhs131 ], [ %best_len.1, %do.cond125 ], [ %sub110, %if.then114 ]236 %cmp137 = icmp ugt i32 %best_len.2, %11237 %.best_len.2 = select i1 %cmp137, i32 %11, i32 %best_len.2238 ret i32 %.best_len.2239}240