[WebAssembly] Enable loop unrolling

[samparker]

Summary

I've started looking into the performance of wasm vs native code using a small selection of the LLVM test suite, focusing on kernels and the basic stuff that could be expected in algorithms. The performance of tight kernels was particularly bad in V8 due to the inserted stack guard checks to enable any loop iteration to be interrupted. Loop unrolling seemed like the sensible thing to do to reduce this overhead, but this benefit would need to overcome the added binary size and associated compilation time. The results for wasmtime and node, using wasi-sdk, are shown below:

AdobeC++

Polybench

TSVC

This patch enables loop unrolling by default for wasm, using a threshold of 30 as the results suggest the gains generally tail off after this, as the binary size also increases. Polybench on the Raspberry Pi via wasmtime doesn't share the performance uplift like the other benchmarks on the other platforms, but I'm not sure why.

[tlively]

cc @kripken what do you think about the size-performance trade off here?

llvm/lib/Target/WebAssembly/WebAssemblyTargetTransformInfo.cpp

108

Is this because loops with calls are presumed to not be hot enough to be worth unrolling?

[kripken]

Very interesting perf data!

Overall it seems like a speedup of around 10% for a size cost of 10% (with much more on one case, showing outliers are possible). That is significant and would support enabling it when not optimizing for size.

However, wasm VMs may eventually do loop unrolling themselves, so the speedup here may evaporate over time, while the code size cost will not. That, and the possibility of outliers on code size, worry me. So personally I would suggest considering not doing this for now, and approaching the VM people with the data, as motivation for them to do it.

Overall my personal philosophy is that anything that regresses code size should preferably be done in the wasm VM. But there are exceptions of course, like inlining, and maybe this is another.

[samparker]

Thanks for taking a look!

While I agree that we should be wary of code size increases, it would seem a shame to me to move the burden into all the runtimes when LLVM is the shared resource and a very good place to do unrolling and the subsequent simplifications that it enables. I liken this to vectorization, but this can give performance to targets even when they haven't spent the time implementing their SIMD code generators in the various runtimes. I've had a quick look at how vectorization stacks up against unrolling on my ryzen machine:

TSVC is a great example of the worst case scenario in unrolling code size increases, it's a single file consisting of 100+ loops that iterate through fixed sized arrays. For vectorization, I suspect that many of vectorized loops neither require a scalar remainder or runtime pointer checks and so hide most of the code size increases that usually come with vectorization.

llvm/lib/Target/WebAssembly/WebAssemblyTargetTransformInfo.cpp

108

I think the general reason is because a call will be a scheduling barrier so can limit the ILP gains of the unroll, this implementation is basically copied from BasicTTI. But from my basic understanding of V8, calls can also be used as interrupt points and so that extra logic doesn't have to be inserted into loops with calls either.

[tlively]

@dschuff, do you have an opinion about this?

I'm inclined to merge this and leave it to users for whom the code size increase is unacceptable to use -Os/-Oz/-fno-unroll-loops to disable it. I'd be curious to see the code size and perf impacts are on the Emscripten benchmark suite, too.

[kripken]

In D95125#2516677, @tlively wrote:

I'm inclined to merge this and leave it to users for whom the code size increase is unacceptable to use -Os/-Oz/-fno-unroll-loops to disable it.

Is it possible to do this in -O3 but not -O2 or -O1?

I'd be curious to see the code size and perf impacts are on the Emscripten benchmark suite, too.

Good idea! Several real-world codebases there that are easy to measure for size and speed. Let me know if I can help.

[samparker]

I'm inclined to merge this and leave it to users for whom the code size increase is unacceptable to use -Os/-Oz/-fno-unroll-loops to disable it.

The unrolling would be disabled at -Os and -Oz, see

// Avoid unrolling when optimizing for size.
UP.OptSizeThreshold = 0;
UP.PartialOptSizeThreshold = 0;

Is it possible to do this in -O3 but not -O2 or -O1?

AFAIK, loop unrolling is disabled at -O1 for all targets. I don't think there's currently a backend mechanism to make a decision on the opt level, but the loop unroller uses them to adjust thresholds to be more aggressive in some situations.

[kripken]

In D95125#2519248, @samparker wrote:

The unrolling would be disabled at -Os and -Oz, see

AFAIK, loop unrolling is disabled at -O1 for all targets. I don't think there's currently a backend mechanism to make a decision on the opt level, but the loop unroller uses them to adjust thresholds to be more aggressive in some situations.

I see, thanks samparker.

What concerns me is that some existing users will definitely be harmed by this, if the default for -O2 changes. That's the default in many build systems, so we will be getting bug reports on "why is my code larger", I bet.

With that said, if I am the only holdout, then I won't stand in the way. But if we do this I'd recommend we at least update changelogs and docs in preparation, to try to minimize the annoyance for users.

[samparker]

But if we do this I'd recommend we at least update changelogs and docs in preparation, to try to minimize the annoyance for users.

Sure and users should definitely be recommended to compile at -Os if code size is their most important metric. From my, admittedly limited, benchmarking the difference between the optimisation levels is quite negligible, yet -Os can reduce size without suffering the performance impact often associated with -Oz.

[SjoerdMeijer]

Webassembly and runtimes is not my field, just saying so you can take my remarks with a bit (or a lot) of salt, but I do have a few opinions on loop-unrolling. :-)
I look at this problem slightly differently:

What concerns me is that some existing users will definitely be harmed by this, if the default for -O2 changes.

I.e., the way I look at this is that we deliver on of its promises:

WebAssembly aims to execute at native speed by taking advantage of common hardware capabilities available on a wide range of platforms.

If this is the goal, if we want parity with native execution, that means we would have to apply the same tricks as ahead of time compiled code, otherwise we would never achieve this. Loop-unrolling is known to greatly improve performance, and also to be an enabler for other optimisations. Thus, without loop-unrolling I don't think near native execution speeds will be feasible.

I agree that a speedup of around 10% for a size cost of 10% is a good trade-off. But it doesn't mean users will get this. I.e., the perf data is shown for a few selected, compute intensive loops, but may not be representative for existing code (not yet). One possibility is that people see minor code-size increases, but large perf gains, another is that there is no increase in code size or improvement in performance, it all depends. One way to find out and quantify this, if necessary, is to check an existing and representative code-base.

So this sounds like a good proposal to me, but I would turn it in something positive:

But if we do this I'd recommend we at least update changelogs and docs in preparation, to try to minimize the annoyance for users.

I.e., some good changes and good performance improvements are coming! :-) If people would like to opt-out, then are a few possibilities:

• Use optimisation level -Os for that makes a more sensitive decision about the performance vs. code-size trade-off.
• Use a compiler flag -fno-unroll-loops, but I don't know how to set that in this environment. Probably that could be set with some environment of make variable?

If deployment is the issue, then are a few other strategies. A switch can be made, with a possibility to opt-out, see above.
Or people can buy into out, if they e.g. set a EXPERIMENTAL_OPTIMIZATIONS flag/value/option, thus get a taste of the perf uplifts if they are curious, and setting out the clear expectations that this will become the default at some point.

Just my 2 cents.

[kripken]

In D95125#2522493, @SjoerdMeijer wrote:

Webassembly and runtimes is not my field, just saying so you can take my remarks with a bit (or a lot) of salt, but I do have a few opinions on loop-unrolling. :-)
I look at this problem slightly differently:

What concerns me is that some existing users will definitely be harmed by this, if the default for -O2 changes.

I.e., the way I look at this is that we deliver on of its promises:

WebAssembly aims to execute at native speed by taking advantage of common hardware capabilities available on a wide range of platforms.

If this is the goal, if we want parity with native execution, that means we would have to apply the same tricks as ahead of time compiled code, otherwise we would never achieve this. Loop-unrolling is known to greatly improve performance, and also to be an enabler for other optimisations. Thus, without loop-unrolling I don't think near native execution speeds will be feasible.

Well said, I agree.

But I think the question is where loop unrolling is done: on the wasm producer (LLVM) or the wasm consumer (the VM that runs it). As mentioned earlier VMs are working on this, and the benefit of them doing it is that code size matters quite a bit on wasm, and doing it there would be better.

[SjoerdMeijer]

In D95125#2522699, @kripken wrote:

But I think the question is where loop unrolling is done: on the wasm producer (LLVM) or the wasm consumer (the VM that runs it).

Ok, thanks, fair enough.

As mentioned earlier VMs are working on this, and the benefit of them doing it is that code size matters quite a bit on wasm, and doing it there would be better.

Like I said, I am not from this field, but I don't see according to which criteria this is better:

• In terms of implementation, I guess letting the LLVM based producer do the loop-unrolling is better as loop-unrolling is a non-trivial optimisation (to do this properly) to (re)implement, this is leveraging the existing LLVM infrastructure, and enabling this is a few lines of code which much beat reimplementing loop-unrolling in a consumer.
• Generated code-quality: assuming 2 loop-unrollers do their job equally well, there shouldn't be any performance difference. Unless the runtime uses profile information that is fed back or has more target information.
• Code-size: this should be the same in the end? I.e., for people interested in maximum performance, doing unrolling in the producer shouldn't increase code-size compared to when this done at the consumer side. For folks that want better code-size, there are different knobs to steer this.
• Compile times: doing loop-unrolling at the consumer side will impact start-up or install times?
• Availability of loop-unrolling. Doing the transformation in the wasm consumer (once) avoids needing it in the different producers and would thus be better. That is, if there is 1 consumer. If there are multiple consumer implementations, then there is no difference?

[kripken]

In D95125#2522915, @SjoerdMeijer wrote:

In D95125#2522699, @kripken wrote:

As mentioned earlier VMs are working on this, and the benefit of them doing it is that code size matters quite a bit on wasm, and doing it there would be better.

Like I said, I am not from this field, but I don't see according to which criteria this is better:

• In terms of implementation, I guess letting the LLVM based producer do the loop-unrolling is better as loop-unrolling is a non-trivial optimisation (to do this properly) to (re)implement, this is leveraging the existing LLVM infrastructure, and enabling this is a few lines of code which much beat reimplementing loop-unrolling in a consumer.

Fair point. Note however that LLVM is not the only producer, and some do not do loop unrolling. But as you said lower down, some VMs might not do it, etc. so definitely there are tradeoffs here.

• Code-size: this should be the same in the end? I.e., for people interested in maximum performance, doing unrolling in the producer shouldn't increase code-size compared to when this done at the consumer side. For folks that want better code-size, there are different knobs to steer this.

Are you thinking of machine code size? That matters too, but the bigger concern is wasm binary size, which is what is downloaded. Doing unrolling after the download is better for that.

• Compile times: doing loop-unrolling at the consumer side will impact start-up or install times?

Yes, that is a definitely a downside, and it is why we usually prefer to optimize in the producer. Optimizations that increase code size, however, are where the tradeoffs become more interesting, like here.

[SjoerdMeijer]

Are you thinking of machine code size? That matters too, but the bigger concern is wasm binary size, which is what is downloaded. Doing unrolling after the download is better for that.

Yep, I was thinking about the transformed/unrolled wasm, or the machine code, that has to be the same similar. But yes, agreed of course that the input, the downloaded wasm, will be smaller compared to unrolling by the producer.

Thanks for clarifying and elaborating on this. It wasn't clear to me from previous comments what exactly was meant with "regressing code-size", and that it is not only about the code-size/perf ratio (the 10% code for 10% speed) and whether that is good enough, but also that it is about the download size. That's clear now.

I will now leave the rest of this discussion to the wasm professionals. :-) Cheers.

[samparker]

Gentle ping... and I'd like to clarify my point about code size: Wasm is actually no different to any other backend in that respect, where the user will can dictate whether it is the most important factor through optimisation levels. The ARM backend is a good example of this where we spend a considerable amount of time tuning our microcontrollers for both -Oz and -O3. The usage of optimisation levels nearly always requires some education, but I think this is easier than re-implementing loop unrolling elsewhere and/or letting users figure out how to enable sensible unrolling via the command line.

[tlively]

I ran Emscripten's larger benchmarks with this patch applied and these are the results:

The results are great on coremark but more modest on the other benchmarks. Interestingly, loop unrolling has no effect at all on lzma or poppler. It's also good to see that the increases in the compressed sizes are uniformly smaller than the increases in the uncompressed sizes.

[samparker]

Thanks @tlively. I just took a look at lzma and yes, it looks like it should benefit from unrolling... What runtime are you running on? I've just done a few runs on wasmtime and, frankly, the benchmark looks far too noisey to be useful: my execution times are varying between ~6.5-8 seconds!

[samparker]

And to qualify that, native execution runs vary by 10s of msec and -fno-unroll-loops is ~9% slower.

[samparker]

My node results are far more stable than wasmtime, on both x86_64 and aarch64 with and without liftoff. Those results correlate with yours and show no benefit of loop unrolling, but I'm seeing ~4% binary size increase too. So I'm surprised and confused and I guess I will investigate further.

[samparker]

I've spent the day looking at lzma and my conclusions are that some loops are vectorized and/or unrolled but they're not on the hot path, and now I believe the improvement I saw on native was purely from secondary side effects. Loop unrolled code is ~4% larger and -msimd128 enabled is ~2.5%, so I'm still surprised you're not seeing change there.

[tlively]

Sorry to leave you hanging on this, @samparker! This LGTM, but in case V8 or other engines land loop unrolling in the future, we might want to re-evaluate this.

[samparker]

Thanks! Yes, agreed. I've also added a couple of tests before committing, just to check that unrolling is indeed disabled at -Os and -Oz.

llvm/lib/Target/WebAssembly/WebAssemblyTargetTransformInfo.h

public:
 
   /// \name Scalar TTI Implementations
   /// @{
 
   // TODO: Implement more Scalar TTI for WebAssembly
 
   TTI::PopcntSupportKind getPopcntSupport(unsigned TyWidth) const;
 
+  void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
+                               TTI::UnrollingPreferences &UP) const;
+
   /// @}
 
   /// \name Vector TTI Implementations
   /// @{
 
   unsigned getNumberOfRegisters(unsigned ClassID) const;
   unsigned getRegisterBitWidth(bool Vector) const;
   unsigned getArithmeticInstrCost(

llvm/lib/Target/WebAssembly/WebAssemblyTargetTransformInfo.cpp

bool WebAssemblyTTIImpl::areInlineCompatible(const Function *Caller,
 
   const FeatureBitset &CallerBits =
       TM.getSubtargetImpl(*Caller)->getFeatureBits();
   const FeatureBitset &CalleeBits =
       TM.getSubtargetImpl(*Callee)->getFeatureBits();
 
   return (CallerBits & CalleeBits) == CalleeBits;
 }
+
+void WebAssemblyTTIImpl::getUnrollingPreferences(
+  Loop *L, ScalarEvolution &SE, TTI::UnrollingPreferences &UP) const {
+  // Scan the loop: don't unroll loops with calls.
+  for (BasicBlock *BB : L->blocks())
+    for (Instruction &I : *BB)
+      if (isa<CallInst>(I) || isa<InvokeInst>(I))
+        if (const Function *F = cast<CallBase>(I).getCalledFunction())
+          if (isLoweredToCall(F))
+            return;
+
+  // The chosen threshold is within the range of 'LoopMicroOpBufferSize' of
+  // the various microarchitectures that use the BasicTTI implementation and
+  // has been selected through heuristics across multiple cores and runtimes. 
+  UP.Partial = UP.Runtime = UP.UpperBound = true;
+  UP.PartialThreshold = 30;
+
+  // Avoid unrolling when optimizing for size.
+  UP.OptSizeThreshold = 0;
+  UP.PartialOptSizeThreshold = 0;
+
+  // Set number of instructions optimized when "back edge"
+  // becomes "fall through" to default value of 2.
+  UP.BEInsns = 2;
+}

llvm/test/Transforms/LoopUnroll/WebAssembly/basic-unrolling.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -mtriple=wasm32-unknown-unknown -loop-unroll -simplifycfg -instcombine -S %s -o - | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+
+define hidden void @compile_time_full(i8* nocapture %a, i8* nocapture readonly %b) {
+; CHECK-LABEL: @compile_time_full(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[I:%.*]] = load i8, i8* [[B:%.*]], align 1
+; CHECK-NEXT:    store i8 [[I]], i8* [[A:%.*]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_1:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 1
+; CHECK-NEXT:    [[I_1:%.*]] = load i8, i8* [[ARRAYIDX_1]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_1:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 1
+; CHECK-NEXT:    store i8 [[I_1]], i8* [[ARRAYIDX1_1]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_2:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 2
+; CHECK-NEXT:    [[I_2:%.*]] = load i8, i8* [[ARRAYIDX_2]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_2:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 2
+; CHECK-NEXT:    store i8 [[I_2]], i8* [[ARRAYIDX1_2]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_3:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 3
+; CHECK-NEXT:    [[I_3:%.*]] = load i8, i8* [[ARRAYIDX_3]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_3:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 3
+; CHECK-NEXT:    store i8 [[I_3]], i8* [[ARRAYIDX1_3]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_4:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 4
+; CHECK-NEXT:    [[I_4:%.*]] = load i8, i8* [[ARRAYIDX_4]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_4:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 4
+; CHECK-NEXT:    store i8 [[I_4]], i8* [[ARRAYIDX1_4]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_5:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 5
+; CHECK-NEXT:    [[I_5:%.*]] = load i8, i8* [[ARRAYIDX_5]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_5:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 5
+; CHECK-NEXT:    store i8 [[I_5]], i8* [[ARRAYIDX1_5]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_6:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 6
+; CHECK-NEXT:    [[I_6:%.*]] = load i8, i8* [[ARRAYIDX_6]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_6:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 6
+; CHECK-NEXT:    store i8 [[I_6]], i8* [[ARRAYIDX1_6]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_7:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 7
+; CHECK-NEXT:    [[I_7:%.*]] = load i8, i8* [[ARRAYIDX_7]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_7:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 7
+; CHECK-NEXT:    store i8 [[I_7]], i8* [[ARRAYIDX1_7]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_8:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 8
+; CHECK-NEXT:    [[I_8:%.*]] = load i8, i8* [[ARRAYIDX_8]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_8:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 8
+; CHECK-NEXT:    store i8 [[I_8]], i8* [[ARRAYIDX1_8]], align 1
+; CHECK-NEXT:    [[ARRAYIDX_9:%.*]] = getelementptr inbounds i8, i8* [[B]], i32 9
+; CHECK-NEXT:    [[I_9:%.*]] = load i8, i8* [[ARRAYIDX_9]], align 1
+; CHECK-NEXT:    [[ARRAYIDX1_9:%.*]] = getelementptr inbounds i8, i8* [[A]], i32 9
+; CHECK-NEXT:    store i8 [[I_9]], i8* [[ARRAYIDX1_9]], align 1
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %b, i32 %i.06
+  %i = load i8, i8* %arrayidx, align 1
+  %arrayidx1 = getelementptr inbounds i8, i8* %a, i32 %i.06
+  store i8 %i, i8* %arrayidx1, align 1
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond.not = icmp eq i32 %inc, 10
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+define hidden void @compile_time_partial(i16* nocapture %a, i16* nocapture readonly %b) {
+; CHECK-LABEL: @compile_time_partial(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I_07:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_3:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i16, i16* [[B:%.*]], i32 [[I_07]]
+; CHECK-NEXT:    [[I:%.*]] = load i16, i16* [[ARRAYIDX]], align 2
+; CHECK-NEXT:    [[ADD:%.*]] = add i16 [[I]], 1
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i16, i16* [[A:%.*]], i32 [[I_07]]
+; CHECK-NEXT:    store i16 [[ADD]], i16* [[ARRAYIDX2]], align 2
+; CHECK-NEXT:    [[INC:%.*]] = or i32 [[I_07]], 1
+; CHECK-NEXT:    [[ARRAYIDX_1:%.*]] = getelementptr inbounds i16, i16* [[B]], i32 [[INC]]
+; CHECK-NEXT:    [[I_1:%.*]] = load i16, i16* [[ARRAYIDX_1]], align 2
+; CHECK-NEXT:    [[ADD_1:%.*]] = add i16 [[I_1]], 1
+; CHECK-NEXT:    [[ARRAYIDX2_1:%.*]] = getelementptr inbounds i16, i16* [[A]], i32 [[INC]]
+; CHECK-NEXT:    store i16 [[ADD_1]], i16* [[ARRAYIDX2_1]], align 2
+; CHECK-NEXT:    [[INC_1:%.*]] = or i32 [[I_07]], 2
+; CHECK-NEXT:    [[ARRAYIDX_2:%.*]] = getelementptr inbounds i16, i16* [[B]], i32 [[INC_1]]
+; CHECK-NEXT:    [[I_2:%.*]] = load i16, i16* [[ARRAYIDX_2]], align 2
+; CHECK-NEXT:    [[ADD_2:%.*]] = add i16 [[I_2]], 1
+; CHECK-NEXT:    [[ARRAYIDX2_2:%.*]] = getelementptr inbounds i16, i16* [[A]], i32 [[INC_1]]
+; CHECK-NEXT:    store i16 [[ADD_2]], i16* [[ARRAYIDX2_2]], align 2
+; CHECK-NEXT:    [[INC_2:%.*]] = or i32 [[I_07]], 3
+; CHECK-NEXT:    [[ARRAYIDX_3:%.*]] = getelementptr inbounds i16, i16* [[B]], i32 [[INC_2]]
+; CHECK-NEXT:    [[I_3:%.*]] = load i16, i16* [[ARRAYIDX_3]], align 2
+; CHECK-NEXT:    [[ADD_3:%.*]] = add i16 [[I_3]], 1
+; CHECK-NEXT:    [[ARRAYIDX2_3:%.*]] = getelementptr inbounds i16, i16* [[A]], i32 [[INC_2]]
+; CHECK-NEXT:    store i16 [[ADD_3]], i16* [[ARRAYIDX2_3]], align 2
+; CHECK-NEXT:    [[INC_3]] = add nuw nsw i32 [[I_07]], 4
+; CHECK-NEXT:    [[EXITCOND_NOT_3:%.*]] = icmp eq i32 [[INC_3]], 1000
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT_3]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.07 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i16, i16* %b, i32 %i.07
+  %i = load i16, i16* %arrayidx, align 2
+  %add = add i16 %i, 1
+  %arrayidx2 = getelementptr inbounds i16, i16* %a, i32 %i.07
+  store i16 %add, i16* %arrayidx2, align 2
+  %inc = add nuw nsw i32 %i.07, 1
+  %exitcond.not = icmp eq i32 %inc, 1000
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+define hidden void @runtime(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
+; CHECK-LABEL: @runtime(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP8_NOT:%.*]] = icmp eq i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP8_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
+; CHECK:       for.body.preheader:
+; CHECK-NEXT:    [[XTRAITER:%.*]] = and i32 [[N]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[N]], 1
+; CHECK-NEXT:    br i1 [[TMP0]], label [[FOR_COND_CLEANUP_LOOPEXIT_UNR_LCSSA:%.*]], label [[FOR_BODY_PREHEADER_NEW:%.*]]
+; CHECK:       for.body.preheader.new:
+; CHECK-NEXT:    [[UNROLL_ITER:%.*]] = and i32 [[N]], -2
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup.loopexit.unr-lcssa:
+; CHECK-NEXT:    [[I_09_UNR:%.*]] = phi i32 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INC_1:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[LCMP_MOD_NOT:%.*]] = icmp eq i32 [[XTRAITER]], 0
+; CHECK-NEXT:    br i1 [[LCMP_MOD_NOT]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY_EPIL:%.*]]
+; CHECK:       for.body.epil:
+; CHECK-NEXT:    [[ARRAYIDX_EPIL:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[I_09_UNR]]
+; CHECK-NEXT:    [[I_EPIL:%.*]] = load i32, i32* [[ARRAYIDX_EPIL]], align 4
+; CHECK-NEXT:    [[ARRAYIDX1_EPIL:%.*]] = getelementptr inbounds i32, i32* [[C:%.*]], i32 [[I_09_UNR]]
+; CHECK-NEXT:    [[I1_EPIL:%.*]] = load i32, i32* [[ARRAYIDX1_EPIL]], align 4
+; CHECK-NEXT:    [[MUL_EPIL:%.*]] = mul nsw i32 [[I1_EPIL]], [[I_EPIL]]
+; CHECK-NEXT:    [[ARRAYIDX2_EPIL:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[I_09_UNR]]
+; CHECK-NEXT:    store i32 [[MUL_EPIL]], i32* [[ARRAYIDX2_EPIL]], align 4
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I_09:%.*]] = phi i32 [ 0, [[FOR_BODY_PREHEADER_NEW]] ], [ [[INC_1]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[NITER:%.*]] = phi i32 [ [[UNROLL_ITER]], [[FOR_BODY_PREHEADER_NEW]] ], [ [[NITER_NSUB_1:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B]], i32 [[I_09]]
+; CHECK-NEXT:    [[I:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[C]], i32 [[I_09]]
+; CHECK-NEXT:    [[I1:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I1]], [[I]]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[A]], i32 [[I_09]]
+; CHECK-NEXT:    store i32 [[MUL]], i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    [[INC:%.*]] = or i32 [[I_09]], 1
+; CHECK-NEXT:    [[ARRAYIDX_1:%.*]] = getelementptr inbounds i32, i32* [[B]], i32 [[INC]]
+; CHECK-NEXT:    [[I_1:%.*]] = load i32, i32* [[ARRAYIDX_1]], align 4
+; CHECK-NEXT:    [[ARRAYIDX1_1:%.*]] = getelementptr inbounds i32, i32* [[C]], i32 [[INC]]
+; CHECK-NEXT:    [[I1_1:%.*]] = load i32, i32* [[ARRAYIDX1_1]], align 4
+; CHECK-NEXT:    [[MUL_1:%.*]] = mul nsw i32 [[I1_1]], [[I_1]]
+; CHECK-NEXT:    [[ARRAYIDX2_1:%.*]] = getelementptr inbounds i32, i32* [[A]], i32 [[INC]]
+; CHECK-NEXT:    store i32 [[MUL_1]], i32* [[ARRAYIDX2_1]], align 4
+; CHECK-NEXT:    [[INC_1]] = add nuw i32 [[I_09]], 2
+; CHECK-NEXT:    [[NITER_NSUB_1]] = add i32 [[NITER]], -2
+; CHECK-NEXT:    [[NITER_NCMP_1:%.*]] = icmp eq i32 [[NITER_NSUB_1]], 0
+; CHECK-NEXT:    br i1 [[NITER_NCMP_1]], label [[FOR_COND_CLEANUP_LOOPEXIT_UNR_LCSSA]], label [[FOR_BODY]]
+;
+entry:
+  %cmp8.not = icmp eq i32 %N, 0
+  br i1 %cmp8.not, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.09 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.09
+  %i = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %c, i32 %i.09
+  %i1 = load i32, i32* %arrayidx1, align 4
+  %mul = mul nsw i32 %i1, %i
+  %arrayidx2 = getelementptr inbounds i32, i32* %a, i32 %i.09
+  store i32 %mul, i32* %arrayidx2, align 4
+  %inc = add nuw i32 %i.09, 1
+  %exitcond.not = icmp eq i32 %inc, %N
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+define hidden void @dont_unroll_call(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
+; CHECK-LABEL: @dont_unroll_call(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP12_NOT:%.*]] = icmp eq i32 [[N:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP12_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I_013:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[I_013]]
+; CHECK-NEXT:    [[I:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[C:%.*]], i32 [[I_013]]
+; CHECK-NEXT:    [[I1:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I1]], [[I]]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[I_013]]
+; CHECK-NEXT:    store i32 [[MUL]], i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    call void (i8*, ...) @printf(i8* nonnull dereferenceable(1) getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i32 0, i32 0), i32 [[I_013]], i32 [[MUL]])
+; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_013]], 1
+; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], [[N]]
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP]], label [[FOR_BODY]]
+;
+entry:
+  %cmp12.not = icmp eq i32 %N, 0
+  br i1 %cmp12.not, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %i.013 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.013
+  %i = load i32, i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %c, i32 %i.013
+  %i1 = load i32, i32* %arrayidx1, align 4
+  %mul = mul nsw i32 %i1, %i
+  %arrayidx2 = getelementptr inbounds i32, i32* %a, i32 %i.013
+  store i32 %mul, i32* %arrayidx2, align 4
+  call void (i8*, ...) @printf(i8* nonnull dereferenceable(1) getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i32 0, i32 0), i32 %i.013, i32 %mul)
+  %inc = add nuw i32 %i.013, 1
+  %exitcond.not = icmp eq i32 %inc, %N
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+@.str = private unnamed_addr constant [12 x i8] c"a[%d] = %d\0A\00", align 1
+declare void @printf(i8* nocapture readonly, ...)