Unroll for uncountable loops

[evstupac]

Summary

The patch introduces 1st heuristic to unroll uncountable loops.
The heuristics targeted on loops working with list structures.

make check passed
spec2000 has unchanged performance
There are several improvements on applications working with list structures.

[mzolotukhin]

Hi Evgeny,

I haven't looked into the details of the patch yet, but (at least from the function name) it looks like this is very similar to what LoopUnrollAnalyzer does (see lib/Analysis/LoopUnrollAnalyzer.cpp). Have you considered adding this functionality there (and what's missing there to catch this)?

Michael

[evstupac]

Hi Michael,

The new function is more about a decision if we need unroll or not. lib/Transforms/Scalar/LoopUnrollPass.cpp looks like a good place for it.

Thanks,
Evgeny

[evstupac]

PING.

[mzolotukhin]

Hi Evgeny,

Why functionality from lib/Analysis/LoopUnrollAnalyzer.cpp isn't enough for your case? It should be able to predict that phis would be removed after unrolling (possibly along with other instructions).

Michael

[evstupac]

Add recurrent xor case.
Move calculations to cost estimation function.

[evstupac]

1. Set "disable unroll" for loops unrolled by "force unroll". The reason is that on LTO unroll pass could be called multiple times and we will try to unroll unless exceed threshold. This is not critical, but makes unroll behavior dependent on LTO.
2. Add missed unit tests.
3. Fix calculations for phis used outside of the loop only.

[evstupac]

PING.

[evstupac]

PING 2.

[evstupac]

PING 3.

[mzolotukhin]

lib/Transforms/Scalar/LoopUnrollPass.cpp

430–434

This look very hacky. What is the motivation of this change? How often do we see such loops?

If we do want to handle such cases (which I'm not convinced now), then we should do it in a general way. That is, the logic should be in instruction visitors, and we should automagically deduce that these instructions are free. There are more cases than just xor - we can multiply by -1, and we should be able to handle in a similar way. In the current form the code is not easily extensible to handle new cases.

[evstupac]

lib/Transforms/Scalar/LoopUnrollPass.cpp

430–434

What is the motivation of this change? How often do we see such loops?

Not each test looks like this, but there are couple where we switch states:

state = st[s^=1];

which becomes invariant with some other calculations after unroll.

If we do want to handle such cases (which I'm not convinced now), then we should do it in a general way. That is, the logic should be in instruction visitors, and we should automagically deduce that these instructions are free.

The same is valid for the code above where complete unroll simplify phi. Why phi is simplified here?
I just did the same for XOR.
And yes we can multiply by -1, do i&1, i/2,... but we need a start point which depends on unroll factor and iteration.
The other solution is to pass, unroll factor in addition to iteration number and move simplification there.
Do you think this is better?

[mzolotukhin]

What is the motivation of this change? How often do we see such loops?

Not each test looks like this, but there are couple where we switch states:

state = st[s^=1];
which becomes invariant with some other calculations after unroll.

I realize that it's possible to write such a test. My question was how frequent are such cases in real programs. Can you provide statistics from SPEC/llvm-testsuite that would justify the change?

If we do want to handle such cases (which I'm not convinced now), then we should do it in a general way. That is, the logic should be in instruction visitors, and we should automagically deduce that these instructions are free.

The same is valid for the code above where complete unroll simplify phi. Why phi is simplified here?

PHIs are present in every loop, in contrast to XORs.

The other solution is to pass, unroll factor in addition to iteration number and move simplification there.
Do you think this is better?

I haven't put much thought to this yet, because I'm still not convinced in the need of this change. It's possible though that if we decide to go this way, we'll need to do some prep-work first to make the code look nice. The main part of simplification code is already there (with PHI-nodes getting an extra attention due to their special and very important nature).

[evstupac]

(was unable to answer in phabricator previously, so just put this from mail thread here)

I realize that it's possible to write such a test. My question was how frequent are such cases in real programs. Can you provide statistics from SPEC/llvm-testsuite that would justify the change?

I'll get the results for llvm test-suite. There is not much difference
on spec2000. There are gains on eembc benhmarks.

PHIs are present in every loop, in contrast to XORs.

The patch touches only recursive XORs which also go through PHI.
PHIs for optimization after complete unroll are in countable loops. My
patch deals with uncountable (a list loop for example).

[evstupac]

I'm not sure I can share all the cases, but I've found good public example of "xor" in the loop from jpeg (h2v1_downsample and h2v2_downsample):
https://github.com/cloudflare/jpegtran/blob/master/jcsample.c

For the case above runtime unroll should work fine, but there are cases where loop upper bound is structure field load. If so loop becomes uncountable and we are unable to apply runtime unroll.
Generally there multiple cases when runtime unroll can fail, so why not to force unroll if we can prove profitability?

[evstupac]

Add phi cycle function to explain phi simplification.

[evstupac]

Regarding performance data.
Initially I want unroll only loops where previous iteration value is reused. Just with this change I get the following.
197.parser up to 5% depending on CPU and 10% to 30% on set of internal benchmarks.
With xor and sub enabled most of benchmarks the results got buildsame or no performance change. However I still believe this fits to current functionality.

One thing I noticed, adding cost to regular unroll (not complete). All loops which counts something got unrolled:

while(smth)

n++;

Use(n);

And unroll safes at least 1 instruction for such loops.

[evstupac]

PING.
Let's come to a conclusion if this is acceptable or not.
The cases that covered here:

1. Uncountable loops where previous value is reused (save one+ instruction for each value)
2. uncountable loops, that counts smth:

while(smth) {
  body();
  n++;
}

to:

while(smth) {
  body();
  if (!smth) goto exit2;
  body();
  n+=2;
}
exit2:
n++;
loop exit:

Saves one+ "add" in the loop.

3. Uncountable loops switching states (not that frequent):

while(smth) {
  body();
  s ^= n;
}
while(smth) {
  body();
  s = -s;
}

Potentially saves a lot (as constant values could simplify several instructions).

[mzolotukhin]

Hi,

I'm still not convinced that we need this functionality. The loops that you mentioned can easily be handled by using unroll pragma if users really care about their performance. The patch might introduce no performance/compile-time regressions, but we shouldn't forget about the increased source code complexity.

Michael

[evstupac]

Hi Michael,

but we shouldn't forget about the increased source code complexity.

The patch mostly reuse existing code for full unroll.

Regarding PHI Cycle it even improve current heuristic, as full unroll consider
"s^=1;" is constant "1" at all iterations >0. However it is 0 on even and 1 on odd.
And I'm ok to drop this part to make code shorter.

Maybe we can add uncountable loops unroll under -O3?

Thanks,
Evgeny

[hfinkel]

In D21720#691221, @evstupac wrote:

Hi Michael,

but we shouldn't forget about the increased source code complexity.

The patch mostly reuse existing code for full unroll.

Regarding PHI Cycle it even improve current heuristic, as full unroll consider
"s^=1;" is constant "1" at all iterations >0. However it is 0 on even and 1 on odd.
And I'm ok to drop this part to make code shorter.

Maybe we can add uncountable loops unroll under -O3?

I agree. -O3 would be the right place for this.

Thanks,
Evgeny

In D21720#691193, @mzolotukhin wrote:

Hi,

I'm still not convinced that we need this functionality. The loops that you mentioned can easily be handled by using unroll pragma if users really care about their performance. The patch might introduce no performance/compile-time regressions, but we shouldn't forget about the increased source code complexity.

Michael

I don't think that "easily be handled by using unroll pragma" is the right standard here. The same argument can be made for anything. We should only really require a pragma when we cannot design a reasonable heuristic (at this stage in the pipeline). This patch does not seem that large. I can review next week.

[mzolotukhin]

full unroll consider "s^=1;" is constant "1" at all iterations >0. However it is 0 on even and 1 on odd.

If that's the case, I'd be happy to review a separate patch that just fixes that.

I don't think that "easily be handled by using unroll pragma" is the right standard here. The same argument can be made for anything. We should only really require a pragma when we cannot design a reasonable heuristic (at this stage in the pipeline). This patch does not seem that large. I can review next week.

My biggest concern about this patch is that it doesn't solve the problem in a general way, but instead only catches two cases: s ^= 1 and s = -s. While it looks kind of generic, I can see no way how it can be extended in future. E.g. it doesn't seem to be able to support another way to write the same idiom: s = i%2 or s = i&1, and if we'd like to support it, we'll need yet another approach.

Your point about using pragma is generally valid, but here is my view on it. While in general we do need to try to cover as many cases without pragmas as possible, we need to provide a general implementation that potentially can help other cases as well. Patching the compiler here and there just to cover cases one by one would lead to unmaintainable and inefficient code in the end. Also, unlike many other loops in a loop with s ^=1 the user would more likely correctly guess a favorable unroll factor (2), just by the nature of the computation. In more complicated loops a help from the compiler is needed much more, because it might be hard to guess the best unroll factor.

IMHO, a general approach here would be to teach unroller (or maybe SCEV) to analyze N sequential iterations. E.g. for the xor case and for 2 sequential iterations starting at the i-th iteration, we'd get something like S_i_plus_2 = S_i_plus_1 ^ 1 = (S_i ^ 1) ^ 1 = S_i. Honestly, I don't know how hard it would be to implement this, and maybe the efforts and complexity won't be worth the gain, but that's what I'd call a general approach, rather than targeting a single case.

Michael

[evstupac]

My biggest concern about this patch is that it doesn't solve the problem in a general way, but instead only catches two cases: s ^= 1 and s = -s.

Why PhiCycle is not general? That could be InstCycle instead (for i&3, i&7, i%N,....).
"i%2", "i&1" are convertible to "s^=1".

IMHO, a general approach here would be to teach unroller (or maybe SCEV) to analyze N sequential iterations. E.g. for the xor case and for 2 sequential iterations starting at the i-th iteration, we'd get something like S_i_plus_2 = S_i_plus_1 ^ 1 = (S_i ^ 1) ^ 1 = S_i.

Current approach do this, but starting from 0 iteration (taking in account that some instruction are cycle).

Suppose we skip this, what about:

1. Uncountable loops where previous value is reused (save one+ instruction for each value)?
2. Uncountable loops, that counts smth?

[hfinkel]

In D21720#696992, @evstupac wrote:

My biggest concern about this patch is that it doesn't solve the problem in a general way, but instead only catches two cases: s ^= 1 and s = -s.

Why PhiCycle is not general? That could be InstCycle instead (for i&3, i&7, i%N,....).
"i%2", "i&1" are convertible to "s^=1".

Sure, but "are convertible to" is not helpful if they're not. Whether that's a useful canonical form might be a separate discussion (maybe it is if that's the only use of the induction variable). In any case, I agree that we should have something that is insensitive to how this is written.

However, we still need to make sure we're doing this in a way that is profitable. The point of making sure to unroll by an even factor for these cycle-2 recurrences is that it allows us to completely remove the PHI. It is not clear to me that the more-general case shares this property without additional work (by which I mean canonicalization work).

IMHO, a general approach here would be to teach unroller (or maybe SCEV) to analyze N sequential iterations. E.g. for the xor case and for 2 sequential iterations starting at the i-th iteration, we'd get something like S_i_plus_2 = S_i_plus_1 ^ 1 = (S_i ^ 1) ^ 1 = S_i.

But you need more than this. You need to know how the intermediate iterations are related so that you can eliminate the PHI. This is especially true for the remainder case (because remainders are expensive compared to &, for example).

I suspect that SCEV would have a hard time doing this because the relations are not algebraic (although it might be able to do something interesting with the remainder case).

In any case, there is definitely a more-general case we can handle here, but it is the following: there needs to either be a cycle PHI, or a use of an otherwise-unused instruction variable that repeats in a fixed pattern, such that unrolling the loop by the length of that pattern allows us to eliminate the PHI. i&C and i%C have that property. Is there anything else?

Current approach do this, but starting from 0 iteration (taking in account that some instruction are cycle).

Suppose we skip this, what about:

1. Uncountable loops where previous value is reused (save one+ instruction for each value)?
2. Uncountable loops, that counts smth?

[evstupac]

In any case, there is definitely a more-general case we can handle here, but it is the following: there needs to either be a cycle PHI, or a use of an otherwise-unused instruction variable that repeats in a fixed pattern, such that unrolling the loop by the length of that pattern allows us to eliminate the PHI. i&C and i%C have that property. Is there anything else?

"i/C" could also be optimized when "i" starts from "k*C". However we'll need to lower it (replace with new IV) in later optimizations (for example LSR).

What about cases 1. and 2. ?

[hfinkel]

In D21720#697188, @evstupac wrote:

In any case, there is definitely a more-general case we can handle here, but it is the following: there needs to either be a cycle PHI, or a use of an otherwise-unused instruction variable that repeats in a fixed pattern, such that unrolling the loop by the length of that pattern allows us to eliminate the PHI. i&C and i%C have that property. Is there anything else?

"i/C" could also be optimized when "i" starts from "k*C". However we'll need to lower it (replace with new IV) in later optimizations (for example LSR).

What about cases 1. and 2. ?

Case 1 sounds good, but maybe our existing heuristic should get it? I don't understand what you mean in case 2.

[evstupac]

Case 1 sounds good, but maybe our existing heuristic should get it? I don't understand what you mean in case 2.

Actually case 1 is the most simple and profitable. Maybe we shall start with it only?
Regarding case 2:

It covers loops which counts how long some condition is true. For example (how many elements in the list):
while (curr) {

len++;
curr = curr->next;

}

After unroll by 2:

while(curr) {

curr1 = curr->next;
if (!curr1) goto exit1;
curr = curr1->next;
len+=2;

}
exit1:
len++;
loop exit:

[evstupac]

but maybe our existing heuristic should get it?

No. We don't do unroll of uncountable loops at all.

[zzheng]

lib/Transforms/Scalar/LoopUnrollPass.cpp

93

Is this description copied from above flag?

allow-force sounds like forced unrolling... how about name it UnrollAllowUncountable (unroll-allow-uncountable)?

test/Transforms/LoopUnroll/unroll-force.ll

2

Maybe name this file 'unroll-uncountable.ll'?

[mzolotukhin]

What is the case 1?

For loops with unknown trip count (that's the case 2, right?) I don't see why we need to add any additional analyzers (analyzeLoopUnrollCost). Removing one instruction by unrolling by 2 is not better than the worst case for partial unroll of a loop with a known trip count:

for (i = 0; i < N; i++) {
  ...
}

But since we sometimes partially unroll such loops, I don't currently see a reason why we can't do this for loops with unknown trip-count as well. However, we don't need additional thresholds/knobs for it, thresholds for partial unroll should do it already.

[evstupac]

What is the case 1?

Uncountable loops where previous value is reused (save one+ instruction for each value)
The example is in lit test (motivation comes from list loops).

For loops with unknown trip count (that's the case 2, right?)

No. All cases are about uncountable loops.

I don't see why we need to add any additional analyzers (analyzeLoopUnrollCost). Removing one instruction by unrolling by 2 is not better than the worst case for partial unroll of a loop with a known trip count:

We can skip this and do like in my initial patch (just run a function that return unroll count if it is profitable to unroll). That way cases 2 and 3 are skipped. I change the patch to call `analyzeLoopUnrollCost' to make more general.

But since we sometimes partially unroll such loops, I don't currently see a reason why we can't do this for loops with unknown trip-count as well. However, we don't need additional thresholds/knobs for it, thresholds for partial unroll should do it already.

The patch do not introduce a new threshold. If we enable unroll for all uncountable loops it will result in dramatic code size increase (for most cases without performance value).

[evstupac]

lib/Transforms/Scalar/LoopUnrollPass.cpp

93

Right. Thanks for catching this. Will fix. "unroll-allow-uncountable" looks good.

test/Transforms/LoopUnroll/unroll-force.ll

2

Yes. Make sense.

[mzolotukhin]

Uncountable loops where previous value is reused (save one+ instruction for each value)

What do you mean by uncountable? How is it different from a loop with unknown trip count?
What is a previous value? Is it a value from a previous iteration? If that's the case, any induction variable satisfies that condition.

No. All cases are about uncountable loops.

What's the difference between these two cases? I've gotten totally confused now.

We can skip this and do like in my initial patch (just run a function that return unroll count if it is profitable to unroll). That way cases 2 and 3 are skipped. I change the patch to call `analyzeLoopUnrollCost' to make more general.

What is the case 3?

The patch do not introduce a new threshold. If we enable unroll for all uncountable loops it will result in dramatic code size increase (for most cases without performance value).

Exactly. And unroll of any loop that has at least one IV will save at least one instruction, because we'll have a phi for the IV and we can fold this phi in between unrolled iterations. So, my point was that "saving one instruction" should not be enough to unroll a loop.

[evstupac]

What do you mean by uncountable? How is it different from a loop with unknown trip count?

L is uncountble <=> isa<SCEVCouldNotCompute>(SE->getBackedgeTakenCount(L)) is true.
For unknown trip isa<SCEVCouldNotCompute>(SE->getBackedgeTakenCount(L)) is false.

What's the difference between these two cases? I've gotten totally confused now.
What is the case 3?

The cases that covered here:

1. Uncountable loops where previous value is reused (save one+ instruction for each value)
2. uncountable loops, that counts smth:

while(smth) {
  body();
  n++;
}

to:

while(smth) {
  body();
  if (!smth) goto exit2;
  body();
  n+=2;
}
exit2:
n++;
loop exit:

Saves one+ "add" in the loop.

3. Uncountable loops switching states (not that frequent):

while(smth) {
  body();
  s ^= n;
}
while(smth) {
  body();
  s = -s;
}

Potentially saves a lot (as constant values could simplify several instructions).

[efriedma]

Currently, there's a profitability check hidden in llvm::UnrollLoop: if the "Force" parameter is false, it will refuse to unroll any loop unless it can make the loop latch in the unrolled iterations an unconditional branch. (See the debug message "Wont unroll; remainder loop could not be generated" in lib/Transforms/Utils/LoopUnroll.cpp.) This prevents the unroll pass from going crazy unrolling every loop in the program, but it's also not a very good way to measure profitability.

Ideally, we want to tie unrolling to a dynamic cost discount. If the unrolled loop is substantially cheaper than the original, we should unroll, whether or not the savings come from eliminating the conditional branch in the latch. Conversely, unrolling a large loop just to eliminate one branch is probably a bad idea.

This patch is trying to solve the problem for certain cases... but the approach is kind of awkward: rather than actually moving the profitability check, it adds a special case to set the "Force" bit for certain loops.

[evstupac]

Conversely, unrolling a large loop just to eliminate one branch is probably a bad idea.

That is bounded by thresholds.

This patch is trying to solve the problem for certain cases... but the approach is kind of awkward: rather than actually moving the profitability check,
it adds a special case to set the "Force" bit for certain loops.

Isn't it the same for Runtime, Partial? Setting count means almost the same. Count of 1 or 0 means we'll act in the same way if Runtime is false. I can rewrite this and set Force to true by default (but set count to 0 or 1 for uncountable loops, that do not meet some conditions).
And yes you are right we need to move all profitability checks from Utils/LoopUnrollRuntime.cpp to Scalar/LoopUnrollPass.cpp (I plan to do this in another patch).,

[efriedma]

Conversely, unrolling a large loop just to eliminate one branch is probably a bad idea.

That is bounded by thresholds.

Not really... I mean, we have PartialThreshold as a maximum size for the whole unrolled loop, but that isn't sensitive to the dynamic cost savings. (Compare to getFullUnrollBoostingFactor for complete unrolling.)

[evstupac]

Not really... I mean, we have PartialThreshold as a maximum size for the whole unrolled loop, but that isn't sensitive to the dynamic cost savings. (Compare to getFullUnrollBoostingFactor for complete unrolling.)

Right. But full unroll is the only exception.
And yes this threshold is not that accurate, but it bounds loop unrolling. And it will bound uncountable loops unroll as well.

[hfinkel]

In D21720#698373, @evstupac wrote:

Not really... I mean, we have PartialThreshold as a maximum size for the whole unrolled loop, but that isn't sensitive to the dynamic cost savings. (Compare to getFullUnrollBoostingFactor for complete unrolling.)

Right. But full unroll is the only exception.
And yes this threshold is not that accurate, but it bounds loop unrolling. And it will bound uncountable loops unroll as well.

Okay, so is the general plan here to?

1. Generally allow unrolling of uncountable loops
2. Adjust the profitability heuristic to account for the cost of the branches for the uncountable case
3. Include, as necessary, in our general profitability heuristic (if we don't get this naturally), savings from phi-derived values which are cyclic with a small cycle length (like the s = -s case).

[mzolotukhin]

Okay, so is the general plan here to?

1. Generally allow unrolling of uncountable loops
2. Adjust the profitability heuristic to account for the cost of the branches for the uncountable case
3. Include, as necessary, in our general profitability heuristic (if we don't get this naturally), savings from phi-derived values which are cyclic with a small cycle length (like the s = -s case).

I agree that we should start from (1). But I don't understand, why (2) (and (3) ) is considered special for the uncountable case. AFAIU, the current heuristic aims at simulating these savings (removed branches) already - even though we do not try to accurately predict cost of rolled and unrolled version of the loop. Am I missing something?

Michael

[evstupac]

Okay, so is the general plan here to?

1. Generally allow unrolling of uncountable loops

That seems reasonable. I'll enable this at O3.

2. Adjust the profitability heuristic to account for the cost of the branches for the uncountable case

In most cases we can not remove branches in uncountable (isa<SCEVCouldNotCompute>(SE->getBackedgeTakenCount(L)) is true) loops. And it is hard to detect cases when we can.
To be able to reduce IVs (if there are such) we'll need to count them and do some basic analysis. A lot of uncountable loops don't have IVs at all.
So the heuristic we have for Runtime unrolling (with unknown trip count) is not ok here.

3. Include, as necessary, in our general profitability heuristic (if we don't get this naturally), savings from phi-derived values which are cyclic with a small cycle length (like the s = -s case).

Right now this is the only way to see if unroll for uncountable loop is profitable or not.

I agree that we should start from (1). But I don't understand, why (2) (and (3) ) is considered special for the uncountable case. AFAIU, the current heuristic aims at simulating these savings (removed branches) already - even though we do not try to accurately predict cost of rolled and unrolled version of the loop. Am I missing something?

Current heuristic works for loops with unknown trip count (when we are able to calculate it, but runtime only). It is not applicable for uncountable loops.

[evstupac]

Enabled uncountable (unable to calculate trip count) unroll by default at O3 and higher.
Renamed test (according to inline comments).

[evstupac]

PING

[efriedma]

The use of the "Force" bit here is still really confusing... we need a better way of expressing the profitability of unrolling.

include/llvm/CodeGen/BasicTTIImpl.h

332 ↗

(On Diff #98867)

What effect does this have on performance?

[evstupac]

In D21720#766168, @efriedma wrote:

The use of the "Force" bit here is still really confusing... we need a better way of expressing the profitability of unrolling.

The naming was introduced earlier. Changing it in this patch would be considered as "unrelated change".
"Force" mean we'll unroll loop anyway. For example if user set "pragma unroll(2)" we need to force unrolling (no matter: countable loop or not, it is expensive to calculate tripcount or not...).

include/llvm/CodeGen/BasicTTIImpl.h

332 ↗

(On Diff #98867)

spec performance is unchanged.
However I see performance gain on small loops working with list structures (that is the main reason I'm trying to apply this).
Generally I don't see why we are missing unroll of uncountable loops now. When we are able to prove profitability we should do this.

[evstupac]

PING.

[efriedma]

Changing it in this patch would be considered as "unrelated change".

It's still messy, and still needs to change before this lands. Changing it in a separate patch is fine, if that makes sense.

---

This change needs testcases, including a couple examples of loops where the unrolling is profitable.

lib/Transforms/Scalar/LoopUnrollPass.cpp

368

Indentation. And I'm not sure why you're adding an instruction to the worklist that might not even be in the loop.

413

Maybe this would be more clear if it returned a boolean? I'm not sure the rest of this code makes sense if PhiCycle isn't either 0 or 2.

566

What is this change doing? (Please put comments in the code.)

973

"Cost->UnrolledCost >= Cost->RolledDynamicCost" is the profitability check? Needs a comment to explain what that means.

Do we care how large the improvement is vs. the size of the loop?

976

Maybe rearrange this? UP.Force is only true on one codepath out of the previous if statement.

include/llvm/Analysis/LoopUnrollAnalyzer.h

class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
   struct SimplifiedAddress {
     Value *Base = nullptr;
     ConstantInt *Offset = nullptr;
   };
 
 public:
   UnrolledInstAnalyzer(unsigned Iteration,
                        DenseMap<Value *, Constant *> &SimplifiedValues,
-                       ScalarEvolution &SE, const Loop *L)
-      : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
+                       ScalarEvolution &SE, const Loop *L, bool CompleteUnroll)
+      : SimplifiedValues(SimplifiedValues), SE(SE),
+        L(L), CompleteUnroll(CompleteUnroll) {
       IterationNumber = SE.getConstant(APInt(64, Iteration));
   }
 
   // Allow access to the initial visit method.
   using Base::visit;
 
 private:
   /// \brief A cache of pointer bases and constant-folded offsets corresponding
private:
   /// of simplified values specific to this iteration.  The idea is to propagate
   /// any special information we have about loads that can be replaced with
   /// constants after complete unrolling, and account for likely simplifications
   /// post-unrolling.
   DenseMap<Value *, Constant *> &SimplifiedValues;
 
   ScalarEvolution &SE;
   const Loop *L;
+  bool CompleteUnroll;
 
   bool simplifyInstWithSCEV(Instruction *I);
 
   bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); }
   bool visitBinaryOperator(BinaryOperator &I);
   bool visitLoad(LoadInst &I);
   bool visitCastInst(CastInst &I);
   bool visitCmpInst(CmpInst &I);
   bool visitPHINode(PHINode &PN);
 };
 }
 #endif

lib/Analysis/LoopUnrollAnalyzer.cpp

bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
   if (!SE.isSCEVable(I->getType()))
     return false;
 
   const SCEV *S = SE.getSCEV(I);
   if (auto *SC = dyn_cast<SCEVConstant>(S)) {
     SimplifiedValues[I] = SC->getValue();
     return true;
   }
+  if (!CompleteUnroll)
+    return false;
 
   auto *AR = dyn_cast<SCEVAddRecExpr>(S);
   if (!AR || AR->getLoop() != L)
     return false;
 
   const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
   // Check if the AddRec expression becomes a constant.
   if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {

 }
 
 bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
   // Run base visitor first. This way we can gather some useful for later
   // analysis information.
   if (Base::visitPHINode(PN))
     return true;
 
+  // Consider PHI is foldable only after complete unroll.
+  if (!CompleteUnroll)
+    return false;
+
   // The loop induction PHI nodes are definitionally free.
   return PN.getParent() == L->getHeader();
 }

lib/Transforms/Scalar/LoopUnrollPass.cpp

 
 static cl::opt<bool> UnrollAllowRemainder(
     "unroll-allow-remainder", cl::Hidden,
     cl::desc("Allow generation of a loop remainder (extra iterations) "
              "when unrolling a loop."));
 
 static cl::opt<bool>
     UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden,
                   cl::desc("Unroll loops with run-time trip counts"));
 
 static cl::opt<unsigned> UnrollMaxUpperBound(
     "unroll-max-upperbound", cl::init(8), cl::Hidden,
     cl::desc(
         "The max of trip count upper bound that is considered in unrolling"));
 
 static cl::opt<unsigned> PragmaUnrollThreshold(
     "pragma-unroll-threshold", cl::init(16 * 1024), cl::Hidden,

 /// given iteration its condition would be resolved to true, we won't add up the
 /// cost of the 'false'-block).
 /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
 /// the analysis failed (no benefits expected from the unrolling, or the loop is
 /// too big to analyze), the returned value is None.
 static Optional<EstimatedUnrollCost>
 analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT,
                       ScalarEvolution &SE, const TargetTransformInfo &TTI,
-                      int MaxUnrolledLoopSize) {
+                      int MaxUnrolledLoopSize, bool CompleteUnroll = true) {
   // We want to be able to scale offsets by the trip count and add more offsets
   // to them without checking for overflows, and we already don't want to
   // analyze *massive* trip counts, so we force the max to be reasonably small.
   assert(UnrollMaxIterationsCountToAnalyze < (INT_MAX / 2) &&
          "The unroll iterations max is too large!");
 
   // Only analyze inner loops. We can't properly estimate cost of nested loops
   // and we won't visit inner loops again anyway.
for (;; --Iteration) {
           continue;
 
         // Mark that we are counting the cost of this instruction now.
         Cost.IsCounted = true;
 
         // If this is a PHI node in the loop header, just add it to the PHI set.
         if (auto *PhiI = dyn_cast<PHINode>(I))
           if (PhiI->getParent() == L->getHeader()) {
+            if (CompleteUnroll)
               assert(Cost.IsFree && "Loop PHIs shouldn't be evaluated as they "
                                     "inherently simplify during unrolling.");
             if (Iteration == 0)
               continue;
 
             // Push the incoming value from the backedge into the PHI used list
             // if it is an in-loop instruction. We'll use this to populate the
             // cost worklist for the next iteration (as we count backwards).
             if (auto *OpI = dyn_cast<Instruction>(
                     PhiI->getIncomingValueForBlock(L->getLoopLatch())))
for (;; --Iteration) {
             continue;
 
           // Otherwise accumulate its cost.
           CostWorklist.push_back(OpI);
         }
       } while (!CostWorklist.empty());
 
       if (PHIUsedList.empty())
         // We've exhausted the search.
         break;
 
       assert(Iteration > 0 &&
              "Cannot track PHI-used values past the first iteration!");
       CostWorklist.append(PHIUsedList.begin(), PHIUsedList.end());
       PHIUsedList.clear();
     }
   };
for (Instruction &I : *L->getHeader()) {
         break;
 
       // The loop header PHI nodes must have exactly two input: one from the
       // loop preheader and one from the loop latch.
       assert(
           PHI->getNumIncomingValues() == 2 &&
           "Must have an incoming value only for the preheader and the latch.");
 
-      Value *V = PHI->getIncomingValueForBlock(
-          Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
+      Value *VP = PHI->getIncomingValueForBlock(L->getLoopPreheader());
+      Value *VL = PHI->getIncomingValueForBlock(L->getLoopLatch());
+      if (CompleteUnroll) {
+        Value *V = Iteration == 0 ? VP : VL;
         Constant *C = dyn_cast<Constant>(V);
         if (Iteration != 0 && !C)
           C = SimplifiedValues.lookup(V);
         if (C)
           SimplifiedInputValues.push_back({PHI, C});
       }
+      // If incoming value for PHI is another PHI, that means we need to
+      // store previous value.
+      Instruction *IL = dyn_cast<Instruction>(VL);
+      if (Iteration != 0 && isa<PHINode>(VL) && IL && L->contains(IL))
+        RolledDynamicCost++;
+      // Simplify recurent XOR:
+      // I = PHI [VP, VL]
+      // VL = I ^ X
+      //
+      // To:
+      // I1 = VP
+      // VL1 = VP ^ X
+      // I2 = VP ^ X
+      // VL2 = VP
+      if ((TripCount & 1) == 0) {
+        if (IL && IL->getOpcode() == Instruction::Xor &&
+            IL->getOperand(0) == PHI && L->isLoopInvariant(IL->getOperand(1))) {
+          Constant *CP = dyn_cast<Constant>(VP);
+          if (Iteration & 1)
+            CP = SimplifiedValues.lookup(VL);
+          if (CP)
+            SimplifiedInputValues.push_back({PHI, CP});
+        }
+      }
+    }
 
     // Now clear and re-populate the map for the next iteration.
     SimplifiedValues.clear();
     while (!SimplifiedInputValues.empty())
       SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
+    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues,
+                                  SE, L, CompleteUnroll);
 
-    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
 
     BBWorklist.clear();
     BBWorklist.insert(L->getHeader());
     // Note that we *must not* cache the size, this loop grows the worklist.
     for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
       BasicBlock *BB = BBWorklist[Idx];
 
       // Visit all instructions in the given basic block and try to simplify
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
           BBWorklist.insert(Succ);
         else
           ExitWorklist.insert({BB, Succ});
       AddCostRecursively(*TI, Iteration);
     }
 
     // If we found no optimization opportunities on the first iteration, we
     // won't find them on later ones too.
-    if (UnrolledCost == RolledDynamicCost) {
+    if (CompleteUnroll && UnrolledCost == RolledDynamicCost) {
       DEBUG(dbgs() << "  No opportunities found.. exiting.\n"
                    << "  UnrolledCost: " << UnrolledCost << "\n");
       return None;
     }
   }
 
   while (!ExitWorklist.empty()) {
     BasicBlock *ExitingBB, *ExitBB;
     std::tie(ExitingBB, ExitBB) = ExitWorklist.pop_back_val();
 
     for (Instruction &I : *ExitBB) {
       auto *PN = dyn_cast<PHINode>(&I);
       if (!PN)
         break;
 
       Value *Op = PN->getIncomingValueForBlock(ExitingBB);
+      if (auto *OpPN = dyn_cast<PHINode>(Op))
+        if (OpPN->getParent() == L->getHeader())
+          Op = OpPN->getIncomingValueForBlock(L->getLoopLatch());
       if (auto *OpI = dyn_cast<Instruction>(Op))
         if (L->contains(OpI))
           AddCostRecursively(*OpI, TripCount - 1);
     }
   }
 
   DEBUG(dbgs() << "Analysis finished:\n"
                << "UnrolledCost: " << UnrolledCost << ", "
if (PragmaCount > 0 && !UP.AllowRemainder)
              "unroll_count pragma because remainder loop is restricted "
              "(that could architecture specific or because the loop "
              "contains a convergent instruction) and so must have an unroll "
              "count that divides the loop trip multiple of "
           << NV("TripMultiple", TripMultiple) << ".  Unrolling instead "
           << NV("UnrollCount", UP.Count) << " time(s).");
   }
 
+  // Estimate if Force unroll could be profitable.
+  // Currently try only 2 times unroll.
+  // Do it only for innermost loops with unknown trip count.
+  // For know trip count Runtime unroll is more profitable.
+  if (!ExplicitUnroll &&
+      isa<SCEVCouldNotCompute>(SE->getBackedgeTakenCount(L))) {
+    Optional<EstimatedUnrollCost> Cost =
+        analyzeLoopUnrollCost(L, 2, DT, *SE, TTI,
+                              UP.PartialThreshold, false);
+    if (Cost && Cost->UnrolledCost < Cost->RolledDynamicCost) {
+      UP.Force = true;
+      UP.Count = 2;
+      // Unroll uncountable loops only once.
+      DEBUG(dbgs() << "  unrolling with count: " << UP.Count << "\n");
+      return true;
+    }
+  }
+
   if (UP.Count > UP.MaxCount)
     UP.Count = UP.MaxCount;
   DEBUG(dbgs() << "  partially unrolling with count: " << UP.Count << "\n");
   if (UP.Count < 2)
     UP.Count = 0;
   return ExplicitUnroll;
 }
 

test/Transforms/LoopUnroll/unroll-force.ll

+; RUN: opt < %s -S -unroll-runtime -loop-unroll | FileCheck %s
+; The test checks unroll for uncountable loop, when previous value is stored.
+
+; CHECK: loop.body.if:
+; CHECK: loop.body.if.1:
+
+%struct.list = type { %struct.list*, i32 }
+
+@head = global %struct.list { %struct.list* null, i32 1 }, align 8
+
+; Function Attrs: norecurse nounwind uwtable
+define i32 @main(i32 %argc, i8** nocapture readnone %argv) {
+entry:
+  %0 = load i32, i32* getelementptr inbounds (%struct.list, %struct.list* @head, i64 0, i32 1), align 8
+  br label %loop.body
+
+loop.body:                                          ; preds = %entry, %loop.body.if
+  %prev = phi %struct.list* [ @head, %entry ], [ %cur, %loop.body.if ]
+  %cur = phi %struct.list* [ @head, %entry ], [ %2, %loop.body.if ]
+  %1 = phi i32 [ %0, %entry ], [ %3, %loop.body.if ]
+  %next.cur = getelementptr inbounds %struct.list, %struct.list* %cur, i64 0, i32 0
+  %2 = load %struct.list*, %struct.list** %next.cur, align 8
+  %tobool = icmp eq %struct.list* %2, null
+  br i1 %tobool, label %if.else, label %loop.body.if
+
+loop.body.if:                       ; preds = %loop.body
+  %val = getelementptr inbounds %struct.list, %struct.list* %cur, i64 0, i32 1
+  %3 = load i32, i32* %val, align 8
+  %cmp = icmp sgt i32 %3, %0
+  br i1 %cmp, label %loopexit, label %loop.body
+
+if.else:                                          ; preds = %if.then
+  %next.prev = getelementptr inbounds %struct.list, %struct.list* %prev, i64 0, i32 0
+  store %struct.list* null, %struct.list** %next.prev, align 8
+  br label %end
+
+loopexit:                                 ; preds = %loop.body.if
+  br label %end
+
+end:                                          ; preds = %loopexit, %if.else
+  %4 = phi i32 [ %1, %if.else ], [ %3, %loopexit ]
+  ret i32 %4
+}
+
+; The test checks unroll for uncountable loop, when XOR is simplified.
+
+; CHECK: while.body:
+; CHECK: while.body.1:
+
+; Function Attrs: norecurse nounwind uwtable
+define void @xor(i32* nocapture %a) local_unnamed_addr #0 {
+entry:
+  %0 = load i32, i32* %a, align 4
+  %entry.cmp = icmp eq i32 %0, -1
+  br i1 %entry.cmp, label %while.end, label %while.body
+
+while.body:                                       ; preds = %entry, %while.body
+  %1 = phi i32 [ %2, %while.body ], [ %0, %entry ]
+  %arrayidx12 = phi i32* [ %arrayidx, %while.body ], [ %a, %entry ]
+  %s = phi i32 [ %xor, %while.body ], [ 0, %entry ]
+  %i = phi i32 [ %inc, %while.body ], [ undef, %entry ]
+  %add = add nsw i32 %1, %s
+  store i32 %add, i32* %arrayidx12, align 4
+  %xor = xor i32 %s, 1
+  %inc = add nsw i32 %i, 1
+  %arrayidx = getelementptr inbounds i32, i32* %a, i32 %inc
+  %2 = load i32, i32* %arrayidx, align 4
+  %cmp = icmp eq i32 %2, -1
+  br i1 %cmp, label %while.end, label %while.body
+
+while.end:                                        ; preds = %while.body, %entry
+  ret void
+}
+

unittests/Analysis/UnrollAnalyzer.cpp

bool runOnFunction(Function &F) override {
     BasicBlock *Header = &*FI++;
     Loop *L = LI->getLoopFor(Header);
     BasicBlock *Exiting = L->getExitingBlock();
 
     SimplifiedValuesVector.clear();
     TripCount = SE->getSmallConstantTripCount(L, Exiting);
     for (unsigned Iteration = 0; Iteration < TripCount; Iteration++) {
       DenseMap<Value *, Constant *> SimplifiedValues;
-      UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L);
+      UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L, true);
       for (auto *BB : L->getBlocks())
         for (Instruction &I : *BB)
           Analyzer.visit(I);
       SimplifiedValuesVector.push_back(SimplifiedValues);
     }
     return false;
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override {