[LoopDeletion] Insert an early exit from dead path in loop

[jonpa]

Summary

This is applied on top of https://reviews.llvm.org/D86844 "[LoopDeletion] Allows deletion of possibly infinite side-effect free loops".

This patch handles the case where the whole loop is not dead, but only a certain constant path through it. If this path is entered, the loop is in fact dead and an early exit could be made.

Before finalizing the patch by adding tests and also handling the new PM, I would like to get some feedback as to if this is looking to be the right approach. I have seen that this handles the omnetpp function printAddressTable() the same way as GCC does, which gives a nice improvement on the benchmark (SystemZ, output disabled).

[jdoerfert]

The idea is that we have

H:
  %c = ... ; invariant wrt H and L
  br %c, L, B
B: 
  side_effects
  br L
L:
  br %x, H, Exit

Exit:
  ...

right?

One of my problems is that this is too tied to the syntax.
Another is that we are not deleting a loop. The former can be addressed later I guess.

Isn't this more related to LoopUnswitch?
We want to "unswitch the paths that are side-effect free", or something like that.

We could also make it generic by collecting the blocks that are allowed on such a path
in order to allow different CFGs. But that can be done later as well.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

149

Nit: Unrelated and misses documentation. A useful helper though, could be added to D86844 directly (if you don't mind).

296

that reminds me, we really need to make llvm.assume side-effect free... D89054

[jonpa]

In D93734#2469137, @jdoerfert wrote:

The idea is that we have

H:
  %c = ... ; invariant wrt H and L
  br %c, L, B
B: 
  side_effects
  br L
L:
  br %x, H, Exit

Exit:
  ...

right?

Yes, exactly (could be more blocks than 3, though, of course).

One of my problems is that this is too tied to the syntax.

How do you mean, exactly?

Another is that we are not deleting a loop. The former can be addressed later I guess.

Isn't this more related to LoopUnswitch?
We want to "unswitch the paths that are side-effect free", or something like that.

I thought that if we cannot delete the whole loop we can effectively delete a part of it with an early exit.

LoopUnswitching only works if the condition is loop invariant currently as far as I can see, so I am not sure how simple that would be...

We could also make it generic by collecting the blocks that are allowed on such a path
in order to allow different CFGs. But that can be done later as well.

Might be worth a try...

[jdoerfert]

In D93734#2469162, @jonpa wrote:

In D93734#2469137, @jdoerfert wrote:

The idea is that we have

H:
  %c = ... ; invariant wrt H and L
  br %c, L, B
B: 
  side_effects
  br L
L:
  br %x, H, Exit

Exit:
  ...

right?

Yes, exactly (could be more blocks than 3, though, of course).

One of my problems is that this is too tied to the syntax.

How do you mean, exactly?

H:
  %c1 = ... ; invariant wrt H, LazyEval, and L
  br %c1, LazyEval, B
LazyEval:  
  %c2 = ... ; invariant wrt H, LazyEval, and L
  br %c2, L, B
B: 
  side_effects
  br L
L:
  br %x, H, Exit
Exit:
   ...

I mean the above breaks the matching even though the same logic applies. I would argue that is not what we want.
(And given that %c1 and %c2 can have loads, we might not be able to undo short circuit evaluation here to reduce
it to your initial pattern.)

Isn't this more related to LoopUnswitch?
We want to "unswitch the paths that are side-effect free", or something like that.

I thought that if we cannot delete the whole loop we can effectively delete a part of it with an early exit.

We delete parts, agreed, but not a loop. Unsure if this is the right place conceptually.

LoopUnswitching only works if the condition is loop invariant currently as far as I can see, so I am not sure how simple that would be...

With that argumentation you could say LoopDeletion doesn't do this either (right now) ;)
I mean, you can simply copy this code there and it should work, right?

We could also make it generic by collecting the blocks that are allowed on such a path
in order to allow different CFGs. But that can be done later as well.

Might be worth a try...

FWIW, I my goal is to make it something driven by a generic analysis, not another pattern we match.

[reames]

As implemented, this is a bit too specific to one particular pattern to be commitable, but I think you've got the seed of a good idea here.

I think you can generalize this as follows:

• If all conditions contributing to control flow along the path from header to exit block are loop invariant (use SCEVs definition), then the exit is either taken or not taken equally on all iterations.
• If all exit blocks meet the previous criteria, then the loop must either execute once or be infinite. If we can prove it's not infinite, it must execute once.
• For a loop which executes exactly once, the backedge is dead. We can break the backedge, leave the rest of the loop unchanged, and get the result you're looking for.

As a special case of the above (which is probably all we should implement), if all loop exits dominate the backedge, SCEV will be able to compute the backedge taken count as zero. You can simply check the backedge taken count and break the backedge.

Note that my phrasing doesn't involve reasoning about side effects.

[fhahn]

Thanks for sharing the patch Jonas!

In D93734#2469173, @jdoerfert wrote:

In D93734#2469162, @jonpa wrote:

In D93734#2469137, @jdoerfert wrote:

Isn't this more related to LoopUnswitch?
We want to "unswitch the paths that are side-effect free", or something like that.

I thought that if we cannot delete the whole loop we can effectively delete a part of it with an early exit.

We delete parts, agreed, but not a loop. Unsure if this is the right place conceptually.

LoopUnswitching only works if the condition is loop invariant currently as far as I can see, so I am not sure how simple that would be...

As mentioned already, I think framing this as extension to unswitching could be interesting. In a way, it is some kind of 'partial' unswitching, where only the condition of the no-sideeffect version becomes known after unswitching.

I put together an early version of that idea in D93764. It focuses primarily on conditions as in omnetpp's MACRelayUnitBase::printAddressTable, where the condition is a load of a loaded address and one the path from the false successor to header/exits has no side effects. It still an early version(not ready for review yet) which needs more tests and comments, but from looking at the impact on the test-suite (increase in number of branches unswitched), it seems that this could be viable in general.

[jdoerfert]

In D93734#2469399, @reames wrote:

Note that my phrasing doesn't involve reasoning about side effects.

I think the side effect part is still needed (at some point) as the use case they want to tackle has loads in the condition that might be modified by the "main body" (which is potentially never executed).

[jonpa]

With the motto of pushing things forward even if only by aiding the other related patches, I have continued to improve my patch to use as some kind of baseline for "early exit" insertions. Perhaps it can be used during development of the partial loop-unswitching to find cases to handle, or perhaps it could be used for some cases if it would reduce the burden on the other algorithm. It would be very nice if partial unswitching could handle all this instead, of course :-)

Instead of just handling the header->latch edge, now any edge from the "Header region" to the "Latch region" can be handled. The requirements are that in the header region, all conditions must be loop invariant, and there can only be one reachable exit block in the latch region from the branch target block back to header. If there is no exit block on the dead path but the loop has a unique exit block, that exit block is used for the early exit, given the mustprogress attribute.

Interestingly enough, there are now cases where this patch manages to "delete" (or "eliminate") a loop which has multiple exits. The loop structure is removed while the BBs remain, which should hopefullyl be removed later by CFG-opt. I think this is rare on benchmarks though... (see below)

I found out quickly that perhaps the hardest part of this was to update datastructures after changing the CFG in a loop... I have barely been able to build the benchmarks as it is, so I am in need of some good advice on how to update things after a loop change, for this patch to be usable. Currently I have changed things temporarily so that LI, DT, etc are recomputed after loop deletion (BTW, I found that only recomputing those analyses on master after LoopDeletion was not NFC, which surprised me... Is that a bug or expected with the aim to save compile time?)

Statistics on SPEC-17 on SystemZ:

master (patched to not preserve analyses after LoopDeletion for a fair comparison):

      7276                    loop-delete - Number of loops deleted

Only Header/Latch (like first simple version aimed to do):
      1414                    loop-delete - Number of early exits inserted
      7498                    loop-delete - Number of loops deleted
         8                    loop-delete - Number of loops eliminated (no remaining blocks)
       462                    loop-delete - Number of skipped loops (SCEV 0)

Top/Bot regions (current patch):
      2353                    loop-delete - Number of early exits inserted
      7397                    loop-delete - Number of loops deleted
         6                    loop-delete - Number of loops eliminated (no remaining blocks)
       462                    loop-delete - Number of skipped loops (SCEV 0)

A rise from ~1400 to ~2350 is a fairly nice improvement in number of early exits inserted compared to initial patch. There seem to be some difference also in number of loops deleted as reported by deleteLoopIfDead(), which I have not investigated. It seems that somehow must relate to a parent loop now not having a subloop..?

@reames: I am not quite sure how the SE->isZero() case directly relates to the detection of dead paths per my patch... I have here tried a statistic for that case, which showed that some loops could be handled by your patch, while there are still many more that can not... (see above).

@jdoerfert:

FWIW, I my goal is to make it something driven by a generic analysis, not another pattern we match.

I agree with that, I have now made the patch more general.

[fhahn]

In D93734#2478272, @jonpa wrote:

I found out quickly that perhaps the hardest part of this was to update datastructures after changing the CFG in a loop... I have barely been able to build the benchmarks as it is, so I am in need of some good advice on how to update things after a loop change, for this patch to be usable. Currently I have changed things temporarily so that LI, DT, etc are recomputed after loop deletion (BTW, I found that only recomputing those analyses on master after LoopDeletion was not NFC, which surprised me... Is that a bug or expected with the aim to save compile time?)

Statistics on SPEC-17 on SystemZ:

Thanks for the update Jonas! It looks like the patch includes some required changes that still landed (D86844), which might impact the number of removed loops. It might be good to re-collect the statistics. I tried to collect stats with this patch on SPEC2000/SPEC2006/MultiSource for X86 with LTO, but unfortunately there have been a few crashes.

@jdoerfert:

FWIW, I my goal is to make it something driven by a generic analysis, not another pattern we match.

I agree with that, I have now made the patch more general.

I think both this patch and D93764 require very similar analysis to find 'no-op' paths through loops (with the difference that partial unswitching can allow stores to memory that does not clobber the condition). Do you think it would be worth unifying the analysis code?

[jonpa]

In D93734#2486760, @fhahn wrote:

In D93734#2478272, @jonpa wrote:

I found out quickly that perhaps the hardest part of this was to update datastructures after changing the CFG in a loop... I have barely been able to build the benchmarks as it is, so I am in need of some good advice on how to update things after a loop change, for this patch to be usable. Currently I have changed things temporarily so that LI, DT, etc are recomputed after loop deletion (BTW, I found that only recomputing those analyses on master after LoopDeletion was not NFC, which surprised me... Is that a bug or expected with the aim to save compile time?)

Statistics on SPEC-17 on SystemZ:

Thanks for the update Jonas! It looks like the patch includes some required changes that still landed (D86844), which might impact the number of removed loops. It might be good to re-collect the statistics. I tried to collect stats with this patch on SPEC2000/SPEC2006/MultiSource for X86 with LTO, but unfortunately there have been a few crashes.

Sorry to hear about the crashes, hopefully it can all be fixed... I rebased the patch and did a new run:

master (patched to not preserve analyses after LoopDeletion for a fair comparison):

      7557                    loop-delete - Number of loops deleted

current patch:
      2352                    loop-delete - Number of early exits inserted
      7420                    loop-delete - Number of loops deleted
         6                    loop-delete - Number of loops eliminated (no remaining blocks)
       439                    loop-delete - Number of skipped loops (SCEV 0)

@jdoerfert:

FWIW, I my goal is to make it something driven by a generic analysis, not another pattern we match.

I agree with that, I have now made the patch more general.

I think both this patch and D93764 require very similar analysis to find 'no-op' paths through loops (with the difference that partial unswitching can allow stores to memory that does not clobber the condition). Do you think it would be worth unifying the analysis code?

To me it depends on what your goal is with the partial unswitching - do you mean to extend your patch to include multiple partially invariant conditions in the header region? (Or is that already a side-effect of revisiting the new loop? If so, there is no need to compute the "Top-region" like this patch does.). I guess we could perhaps have a common function that finds a unique exit block from SuccBB back to header and collect the memory references as well on that path...

Do you think partial unswitching will be able eventually to handle all the early-exit cases? I haven't tried this patch yet on top of your patch, but that will be interesting :-)

[jonpa]

patch rebased

[jdoerfert]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

110

DriveBy:

This hurts. I know it was there before but auto &I is BasicBlock *... argh.
Could we please change that if we commit this to a auto * at least with a sensible variable name.

[jonpa]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

110

I think it's better in that case perhaps to just commit such an NFC change separately beforehand?

[jdoerfert]

What is left after we merged the loop unswitch solution?

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

110

Yeah, stuff like that can be committed directly as NFC.

[fhahn]

In D93734#2512432, @jdoerfert wrote:

What is left after we merged the loop unswitch solution?

I realized that the for the SECP2017 version, loop-unswitching does not happen by default, due to cost-modeling. (It does happen for the SPEC2006 version). So I tried to extend the logic to check if the candidate path is a no-op: D95468. That should also handle the SPEC2017 case.

[jonpa]

Patch rebased.

What is left after we merged the loop unswitch solution?

I did a rerun today on top of 302432f, which should include both Florians and Philips patches:

trunk:
      8201                    loop-delete - Number of loops deleted

patch:

      2624                    loop-delete - Number of early exits inserted
      8006                    loop-delete - Number of loops deleted
         6                    loop-delete - Number of loops eliminated (no remaining blocks)
       279                    loop-delete - Number of skipped loops (SCEV 0)

patch + D95468

      2617                    loop-delete - Number of early exits inserted
      7798                    loop-delete - Number of loops deleted
         6                    loop-delete - Number of loops eliminated (no remaining blocks)
       279                    loop-delete - Number of skipped loops (SCEV 0)

I realized that the for the SECP2017 version, loop-unswitching does not happen by default, due to cost-modeling. (It does happen for the SPEC2006 version). So I tried to extend the logic to check if the candidate path is a no-op: D95468. That should also handle the SPEC2017 case.

I may be doing something wrong, but D95468 did not help very much looking at these numbers it seems...

[jdoerfert]

I may be doing something wrong, but D95468 did not help very much looking at these numbers it seems...

Maybe outer loops have been skipped and therefore you avoided duplication of outer and inner loops (with D95468). The statistics we have are too coarse grained to exactly pinpoint what happened.

[jonpa]

In D93734#2524218, @jdoerfert wrote:

I may be doing something wrong, but D95468 did not help very much looking at these numbers it seems...

Maybe outer loops have been skipped and therefore you avoided duplication of outer and inner loops (with D95468). The statistics we have are too coarse grained to exactly pinpoint what happened.

I wonder what loops are those which where "partially unrolled", and which were not. Do the partially unrolled ones get some recognizable name maybe in the header blocks?

[fhahn]

In D93734#2529365, @jonpa wrote:

In D93734#2524218, @jdoerfert wrote:

I may be doing something wrong, but D95468 did not help very much looking at these numbers it seems...

Maybe outer loops have been skipped and therefore you avoided duplication of outer and inner loops (with D95468). The statistics we have are too coarse grained to exactly pinpoint what happened.

I wonder what loops are those which where "partially unrolled", and which were not. Do the partially unrolled ones get some recognizable name maybe in the header blocks?

Do you mean partially unswitched or partially unrolled? I don't think so unfortunately. But I think most cases where already caught with D95468 and only in a few cases we now skip duplication. Also note that D95468 adds the shortcut outside the loop, so loop-deletion will still insert an early exit as before (long term I think we could also just turn the branch in the loop into an early exit).

[jonpa]

Patch updated to also run with the new pass manager.

This now gives a ~9% improvement on Omnetpp - just like it was with the legacy pass manager (before but not after Florians patch, I believe).

@fhahn : are you going to port your improvement to loop unswitching to newpm?

[fhahn]

In D93734#2618081, @jonpa wrote:

Patch updated to also run with the new pass manager.

This now gives a ~9% improvement on Omnetpp - just like it was with the legacy pass manager (before but not after Florians patch, I believe).

@fhahn : are you going to port your improvement to loop unswitching to newpm?

Yes I am planning to, but we are seeing several other regressions with the new pass manager that I'll probably need to investigate first. So if anyone wants to port the loop-unswitching changes before I get a chance, I'd be more than happy.

[jonpa]

I again saw a regression on omnetpp against gcc so I decided to revisit this patch as it previously handled that benchmar. In doing so I have updated/revisited with some more comments as well. It now only runs on the new pass manager.

It seems however that this time it was not the loop in PrintAddressTable that was the issue, so I still can't say what the omnetpp regression is about this time. However, I reran SPEC-17 and found that a few benchmarks seemed to improve just slighty (~1%). Statistics report that still ~1400 loops get optimized with this patch (~2400 edges redirected). So at least in theory, this patch might still be of interest, even if just to give hints on missed optimizations by other loop passes.

I checked if the extra work of finding Top/Bot regions and handling multiple exits where still worthwhile (compared to a very simple approach). I found that the Top/Bot search about doubled the effectiveness (relative just checking edges from Header to Latch), where the multiple exit loops were about 10% of the cases (I now made multiple-exit handling fall under an experimental option "-early-exit-extra".).

f510.parest_r seemed to improve ~1.5% on both z14 and z15, and I made a reduced test case for one of the files changed (sparsity_pattern.ii, picked randomly). I see three less BBs in the output and an outer loop removed.

opt -mtriple=systemz-unknown -march=z14 -O3 ./tc_earlex.ll -debug-only=loop-delete

Analyzing Loop for deletion: Loop at depth 1 containing: %bb5.preheader<header>,%bb8,%bb1.loopexit<latch><exiting>,%bb8.preheader,%bb1.loopexit.loopexit
    Loop at depth 2 containing: %bb8<header><latch><exiting>
Loop is not invariant, cannot delete.
Trying to insert early exits:
Top region: bb5.preheader, bb8.preheader, 
Bot region: bb1.loopexit, bb1.loopexit.loopexit, 
Inserting early exit in bb5.preheader:
  br i1 %i7.not3, label %bb1.loopexit, label %bb8.preheader
  =>
  br i1 %i7.not3, label %bb9.loopexit, label %bb8.preheader

tc_earlex.ll3 KBDownload

Thoughts anyone? Maybe somebody would like to try the patch on some other platform?

[jonpa]

@fhahn : I reran this today and found that there are no real benchmark performance improvements anymore. However, there are still +2000 early exits insertions reported, It seems you have managed to handle the important cases, so I guess this still isn't really interesting. It would be however interesting to hear your thoughts on this: I remember you did a handling for this and I guess you must have covered the important cases already..?

[jonpa]

I have derived two reduced test cases where this patch improve the loop branching from SPEC. These were the first two files I looked at out of many, and it seems that in both cases LoopDeletion fails in deleting the loop as it is found to be not variant. In both of these cases it was a matter of breaking the outer loop if the inner loop was never visited.

On SPEC, I still see 2185 of these early exits inserted. This is kind of interesting, although it may be that this is not going to improve any benchmarks. Maybe it relates to outer loops with inner loops that always are executed. Maybe the overhead of the outer loop isn't that great in other cases...

// Derived from gcc / tree-vect-slp.c                                                                                                                                                                                                                                             

int VEC_gimple_base_iterate_vec_;

void build_vector();

unsigned VEC_gimple_base_length();

int VEC_gimple_base_iterate() {
  if (VEC_gimple_base_iterate_vec_)
    return 1;
  return 0;
}

void vect_get_constant_vectors() {
  int j = VEC_gimple_base_length();
  for (; j; j++)                            **// No Loop deletion, but early exit if inner loop never visited.  **                                                                                                                                                                                              
    for (; VEC_gimple_base_iterate();)
      build_vector();
}

clang -c -o tree-vect-slp.s -S -O3 -march=arch13  tree-vect-slp.i -w -mllvm -debug-only=loop-delete

Analyzing Loop for deletion: Loop at depth 1 containing: %for.cond1.preheader<header>,%for.body4,%for.inc<latch><exiting>,%for.body4.preheader,%for.inc.loopexit
    Loop at depth 2 containing: %for.body4<header><latch><exiting>
Loop is not invariant, cannot delete.
Trying to insert early exits:
Top region: for.cond1.preheader, for.body4.preheader, 
Bot region: for.inc, for.inc.loopexit, 
Inserting early exit in for.cond1.preheader:
  br i1 %tobool.not.i.not7, label %for.inc, label %for.body4.preheader
  =>
  br i1 %tobool.not.i.not7, label %for.end5.loopexit10, label %for.body4.preheader

// Derived from cactus / FlatBoundary.c                                                                                                                                                                                                                                           

void memcpy();
int CCTK_GroupDimI();

typedef struct {
  int *cctk_lsh
} cGH;

int Glob_A, Glob_B, Glob_C;

void BndFlatDirVIApplyBndFlat(cGH *GH) {
  int i = 0, j = 0, k = 0, ash[3] = {0, 0, 0}, lsh[3] = {0, 0, 0};
  int vtypesize = CCTK_GroupDimI();

  for (; Glob_A;) {
    for (i = 0; i < Glob_B; i++)
      ash[i] = lsh[i] = GH->cctk_lsh[i];

    for (k = 0; k < Glob_C; k++)
      for (; j < 1;)
        for (; lsh[0];)
          ;

    for (; k < 100000; k++) {               // No Loop deletion, but early exit if inner loop(s) never visited.                                                                                                                                                                               
      for (j = 0; j < lsh[1]; j++) {
        for (i = 0; i < lsh[0]; i++) {
          int _index_to = ash[0] * ash[1] * (k - 1) * vtypesize;
          memcpy(GH + _index_to);
        }
      }
    }
  }

}



Analyzing Loop for deletion: Loop at depth 2 containing: %for.cond25.preheader.us<header>,%for.cond29.preheader.us.us,%for.body32.us.us,%for.cond29.for.inc40_crit_edge.us.us,%for.cond25.for.inc43_crit_edge.us<latch><exiting>,%for.cond29.preheader.us.us.preheader,%for.cond25.for.inc43_crit_edge.us.loopexit
    Loop at depth 3 containing: %for.cond29.preheader.us.us<header>,%for.body32.us.us,%for.cond29.for.inc40_crit_edge.us.us<latch><exiting>
        Loop at depth 4 containing: %for.body32.us.us<header><latch><exiting>
Loop is not invariant, cannot delete.
Trying to insert early exits:
Top region: for.cond25.preheader.us, for.cond29.preheader.us.us.preheader, 
Bot region: for.cond25.for.inc43_crit_edge.us, for.cond25.for.inc43_crit_edge.us.loopexit, 
Inserting early exit in for.cond25.preheader.us:
  br i1 %cmp3165, label %for.cond29.preheader.us.us.preheader, label %for.cond25.for.inc43_crit_edge.us
  =>
  br i1 %cmp3165, label %for.cond29.preheader.us.us.preheader, label %for.cond.loopexit.loopexit

[jonpa]

@fhahn Any comments on the C test cases I derived..?

[jonpa]

ping

@fhahn : I am still curious why this is not an improvement. I realize that you have your reasoning that makes this patch less likely beneficial, and as I spent some time on it, I would be very happy to also understand why :-)

llvm/include/llvm/Transforms/Utils/LoopUtils.h

makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
                    bool AlwaysNew = false);
 
 /// Look for the loop attribute that disables all transformation heuristic.
 bool hasDisableAllTransformsHint(const Loop *L);
 
 /// Look for the loop attribute that disables the LICM transformation heuristics.
 bool hasDisableLICMTransformsHint(const Loop *L);
 
+/// Look for the loop attribute that requires progress within the loop.
+bool hasMustProgress(const Loop *L);
+
 /// The mode sets how eager a transformation should be applied.
 enum TransformationMode {
   /// The pass can use heuristics to determine whether a transformation should
   /// be applied.
   TM_Unspecified,
 
   /// The transformation should be applied without considering a cost model.
   TM_Enable,

 /// true.
 bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE);
 
 /// Helper to consistently add the set of standard passes to a loop pass's \c
 /// AnalysisUsage.
 ///
 /// All loop passes should call this as part of implementing their \c
 /// getAnalysisUsage.
-void getLoopAnalysisUsage(AnalysisUsage &AU);
+void getLoopAnalysisUsage(AnalysisUsage &AU, bool Preserve = true);
 
 /// Returns true if is legal to hoist or sink this instruction disregarding the
 /// possible introduction of faults.  Reasoning about potential faulting
 /// instructions is the responsibility of the caller since it is challenging to
 /// do efficiently from within this routine.
 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
 /// target executes at most once per execution of the loop body.  This is used
 /// to assess the legality of duplicating atomic loads.  Generally, this is

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-delete"
 
 STATISTIC(NumDeleted, "Number of loops deleted");
+STATISTIC(NumEarlyExits, "Number of early exits inserted");
+STATISTIC(NumLoopsElim, "Number of loops eliminated (no remaining blocks)");
+STATISTIC(NumSCEV0Skipped, "Number of skipped loops (SCEV 0)");
 
 enum class LoopDeletionResult {
   Unmodified,
   Modified,
   Deleted,
 };
 
+
+static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) {
+  if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted)
+    return LoopDeletionResult::Deleted;
+  if (A == LoopDeletionResult::Modified || B == LoopDeletionResult::Modified)
+    return LoopDeletionResult::Modified;
+  return LoopDeletionResult::Unmodified;
+}
+
+static bool BBHasSideEffects(const BasicBlock *BB) {
+  if (any_of(*BB, [](const Instruction &I) {
+                    return I.mayHaveSideEffects() && !I.isDroppable();
+                  }))
+    return true;
+  return false;
+}
+
 /// Determines if a loop is dead.
 ///
 /// This assumes that we've already checked for unique exit and exiting blocks,
 /// and that the code is in LCSSA form.
 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
                        SmallVectorImpl<BasicBlock *> &ExitingBlocks,
                        BasicBlock *ExitBlock, bool &Changed,
                        BasicBlock *Preheader) {
static bool isLoopDead(Loop *L, ScalarEvolution &SE,
 
   if (!AllEntriesInvariant || !AllOutgoingValuesSame)
     return false;
 
   // Make sure that no instructions in the block have potential side-effects.
   // This includes instructions that could write to memory, and loads that are
   // marked volatile.
   for (auto &I : L->blocks())
-    if (any_of(*I, [](Instruction &I) {
-          return I.mayHaveSideEffects() && !I.isDroppable();
-        }))
+    if (BBHasSideEffects(I))
       return false;
   return true;
 }
 
 /// This function returns true if there is no viable path from the
 /// entry block to the header of \p L. Right now, it only does
 /// a local search to save compile time.
 static bool isLoopNeverExecuted(Loop *L) {
if (Taken == Preheader)
       return false;
   }
   assert(!pred_empty(Preheader) &&
          "Preheader should have predecessors at this point!");
   // All the predecessors have the loop preheader as not-taken target.
   return true;
 }
 
+static bool loopMustProgress(Loop *L) {
+  return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
+}
+
 /// Remove a loop if it is dead.
 ///
 /// A loop is considered dead if it does not impact the observable behavior of
 /// the program other than finite running time. This never removes a loop that
 /// might be infinite (unless it is never executed), as doing so could change
 /// the halting/non-halting nature of a program.
 ///
 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
     LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   // Don't remove loops for which we can't solve the trip count.
   // They could be infinite, in which case we'd be changing program behavior.
   const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
-  if (isa<SCEVCouldNotCompute>(S)) {
-    LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
+  if (isa<SCEVCouldNotCompute>(S) && !loopMustProgress(L)) {
+    LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
+                         "not required to make progress.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
   ORE.emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
                               L->getHeader())
            << "Loop deleted because it is invariant";
   });
   deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
   ++NumDeleted;
 
   return LoopDeletionResult::Deleted;
 }
 
+static bool usesLoopPHI(const Instruction *I, const Loop *L) {
+  if (!L->contains(I->getParent()))
+    return false;
+  if (isa<PHINode>(I))
+    return true;
+  for (auto &Op : I->operands())
+    if (const Instruction *OpI = dyn_cast<Instruction>(&Op))
+      if (usesLoopPHI(OpI, L))
+        return true;
+  return false;
+}
+
+static bool BBHasLIVCondOnDeadPath(const BasicBlock *BB, Loop *L) {
+  // Check if the condition might change after an iteration across a dead
+  // path.  TODO: worth checking if incoming value from preheader/latch are
+  // the same and allow that case?
+  const Instruction *TI = BB->getTerminator();
+  const Instruction *Cond = nullptr;
+  if (const BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+    if (BI->isConditional())
+      Cond = dyn_cast<Instruction>(BI->getCondition());
+  } else if (const SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+    Cond = dyn_cast<Instruction>(SI->getCondition());
+  } else
+    return false;
+  return (Cond == nullptr || !usesLoopPHI(Cond, L));
+}
+
+static bool hasPredecessorInLoop(const BasicBlock *BB, Loop *L) {
+  for (auto *Pred: predecessors(BB))
+    if (L->contains(Pred))
+      return true;
+  return false;
+}
+
+static bool hasSuccessorInLoop(const BasicBlock *BB, Loop *L) {
+  for (auto *Succ: successors(BB))
+    if (L->contains(Succ))
+      return true;
+  return false;
+}
+
+static void findNoSEBlocks(SmallPtrSet<BasicBlock *, 4> &NoSEBBs,
+                           Loop *L, bool Forward) {
+  auto takeBlock = [&L, &Forward](BasicBlock *BB) -> bool {
+    return !BBHasSideEffects(BB) && (!Forward || BBHasLIVCondOnDeadPath(BB, L));
+  };
+
+  BasicBlock *Header = L->getHeader();
+  BasicBlock *Latch = L->getLoopLatch();
+  BasicBlock *Start = Forward ? Header : Latch;
+  if (!takeBlock(Start))
+    return;
+  NoSEBBs.insert(Start);
+
+  bool Change = true;
+  while (Change) {
+    Change = false;
+    for (auto BB : L->getBlocks()) {
+      if (NoSEBBs.count(BB) || !takeBlock(BB))
+        continue;
+
+      bool All = true;
+      if (Forward) {
+        for (auto *Pred: predecessors(BB))
+          if (!NoSEBBs.count(Pred)) {
+            All = false;
+            break;
+          }
+      } else {
+        for (auto *Succ: successors(BB))
+          if (L->contains(Succ) && !NoSEBBs.count(Succ)) {
+            All = false;
+            break;
+          }
+      }
+      if (All) {
+        NoSEBBs.insert(BB);
+        Change = true;
+      }
+    }
+  }
+}
+
+// Return the exit block on the path from BB to the backedge. If there is
+// none, return the unique exit block if it exists. If there are more than
+// one, return null.  Make sure there are no live-out values.
+static BasicBlock *findExitBlock(const BasicBlock *BB, Loop *L) {
+  BasicBlock *ExitBB = L->getUniqueExitBlock();
+
+  if (!ExitBB) {
+    SmallVector<const BasicBlock *, 4> WorkList;
+    WorkList.push_back(BB);
+    SmallPtrSet<const BasicBlock *, 4> Visited;
+    while (!WorkList.empty()) {
+      const BasicBlock *CurrBB = WorkList.pop_back_val();
+      if (!Visited.insert(CurrBB).second)
+        continue;
+
+      const Instruction *TI = CurrBB->getTerminator();
+      for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i)
+        if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(TI->getOperand(i))) {
+          if (!L->contains(SuccBB)) {
+            if (ExitBB != nullptr && ExitBB != SuccBB)
+              return nullptr;
+            ExitBB = SuccBB;
+          } else if (SuccBB != L->getHeader()){
+            WorkList.push_back(SuccBB);
+          }
+        }
+    }
+  }
+
+ return (ExitBB && !isa<PHINode>(ExitBB->begin())) ? ExitBB : nullptr;
+}
+
+#ifndef NDEBUG
+static void dumpBBSet(std::string Msg, SmallPtrSet<BasicBlock *, 4> &S) {
+  dbgs() << Msg << ": ";
+  for (const BasicBlock *BB : S)
+    dbgs() << BB->getName() << ", ";
+  dbgs() << "\n";
+}
+#endif
+
+static LoopDeletionResult tryInsertEarlyExit(Loop *L, DominatorTree &DT,
+                                             ScalarEvolution &SE, LoopInfo &LI,
+                                             MemorySSA *MSSA,
+                                             OptimizationRemarkEmitter &ORE) {
+  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
+  BasicBlock *LatchBB = L->getLoopLatch();
+  if (!LatchBB || L->getNumBlocks() == 1)
+    return LoopDeletionResult::Unmodified;
+
+  // Check for a known trip count or a forward progress gurantee.
+  const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
+  if (isa<SCEVCouldNotCompute>(S) && !loopMustProgress(L))
+    return LoopDeletionResult::Unmodified;
+
+  if (S->isZero()) {
+    // This should be handled by D93906 "Break backedge of loops when known
+    // not taken".
+    NumSCEV0Skipped++;
+    return LoopDeletionResult::Unmodified;
+  }
+
+  // Compute two sets of blocks which are free of side-effets. Top starts
+  // from header, and Bot starts from latch.
+  SmallPtrSet<BasicBlock *, 4> NoSEBBsTop, NoSEBBsBot;
+  findNoSEBlocks(NoSEBBsTop, L, true  /*Forward*/);
+  findNoSEBlocks(NoSEBBsBot, L, false /*Forward*/);
+  LLVM_DEBUG(dbgs() << "Trying to insert early exits:\n";
+             dumpBBSet("Top region", NoSEBBsTop);
+             dumpBBSet("Bot region", NoSEBBsBot););
+
+  bool Change = false;
+  for (auto BB : NoSEBBsTop) {
+    Instruction *TI = BB->getTerminator();
+    // We can replace an edge if the conditions will always evaluate the same
+    // on the dead path from header to BB, with only one possible exit block
+    // from the target BB in the bottom region.
+    for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i)
+      if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(TI->getOperand(i)))
+        if (NoSEBBsBot.count(SuccBB))
+          if (BasicBlock *ExitBB = findExitBlock(SuccBB, L)) {
+            LLVM_DEBUG(dbgs() << "Inserting early exit in " << BB->getName() << ":\n";);
+            LLVM_DEBUG(TI->dump(); dbgs() << "  =>\n";);
+            TI->setOperand(i, ExitBB);
+            for (PHINode &Phi : SuccBB->phis())
+              Phi.removeIncomingValue(BB);
+            LLVM_DEBUG(TI->dump(););
+            Change = true;
+            NumEarlyExits++;
+          }
+  }
+
+  if (!Change)
+    return LoopDeletionResult::Unmodified;
+  
+  // Update data structures.
+  // NB! Did not yet manage to update everything correctly, so relying on
+  // recomputation of the analyses (see getAnalysisUsage()).
+  SE.forgetLoop(L);
+  DT.recalculate(*const_cast<Function *>(LatchBB->getParent()));
+  Loop *CurrLoop = L;
+  while (CurrLoop != nullptr) {
+    // Iteratively remove disconnected blocks from CurrLoop.
+    Change = true;
+    while (Change) {
+      Change = false;
+      std::vector<BasicBlock*> LoopBlocks(CurrLoop->block_begin(),
+                                          CurrLoop->block_end());
+      for (auto BB : LoopBlocks)
+        if (!hasPredecessorInLoop(BB, CurrLoop) ||
+            !hasSuccessorInLoop(BB, CurrLoop)) {
+          CurrLoop->removeBlockFromLoop(BB);
+          Change = true;
+        }
+    }
+    CurrLoop = CurrLoop->getParentLoop();
+  }
+
+  // If all blocks have been removed, return 'Deleted', or LoopPass will try
+  // to dump it which doesn't work with an emtpy loop.
+  LoopDeletionResult Result = L->getNumBlocks() ? LoopDeletionResult::Modified
+                                                : LoopDeletionResult::Deleted;
+  if (Result == LoopDeletionResult::Deleted) {
+    LI.erase(L);
+    NumLoopsElim++;
+    LLVM_DEBUG(dbgs() << "Loop eliminated: all blocks removed.\n"; );
+  }
+  return Result;
+}
+
 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
                                         LoopStandardAnalysisResults &AR,
                                         LPMUpdater &Updater) {
 
   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
   LLVM_DEBUG(L.dump());
   std::string LoopName = std::string(L.getName());
   // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
LoopDeletionLegacyPass() : LoopPass(ID) {
     initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   // Possibly eliminate loop L if it is dead.
   bool runOnLoop(Loop *L, LPPassManager &) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<MemorySSAWrapperPass>();
-    getLoopAnalysisUsage(AU);
+    getLoopAnalysisUsage(AU, false/*Preserve: Experimental*/);
   }
 };
 }
 
 char LoopDeletionLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
                       "Delete dead loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
   // pass.  Function analyses need to be preserved across loop transformations
   // but ORE cannot be preserved (see comment before the pass definition).
   OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
 
   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
   LLVM_DEBUG(L->dump());
 
   LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);
+  if (Result != LoopDeletionResult::Deleted)
+    Result = merge(Result, tryInsertEarlyExit(L, DT, SE, LI, MSSA, ORE));
 
   if (Result == LoopDeletionResult::Deleted)
     LPM.markLoopAsDeleted(*L);
 
   return Result != LoopDeletionResult::Unmodified;
 }

llvm/lib/Transforms/Utils/LoopUtils.cpp

static cl::opt<bool> ForceReductionIntrinsic(
     "force-reduction-intrinsics", cl::Hidden,
     cl::desc("Force creating reduction intrinsics for testing."),
     cl::init(false));
 
 #define DEBUG_TYPE "loop-utils"
 
 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
 static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
+static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
 
 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                    MemorySSAUpdater *MSSAU,
                                    bool PreserveLCSSA) {
   bool Changed = false;
 
   // We re-use a vector for the in-loop predecesosrs.
   SmallVector<BasicBlock *, 4> InLoopPredecessors;
for (auto &Inst : *Block) {
             return !L->contains(Use->getParent());
           }))
         UsedOutside.push_back(&Inst);
     }
 
   return UsedOutside;
 }
 
-void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
+void llvm::getLoopAnalysisUsage(AnalysisUsage &AU, bool Preserve) {
   // By definition, all loop passes need the LoopInfo analysis and the
   // Dominator tree it depends on. Because they all participate in the loop
   // pass manager, they must also preserve these.
   AU.addRequired<DominatorTreeWrapperPass>();
+  if (Preserve)
     AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addRequired<LoopInfoWrapperPass>();
+  if (Preserve)
     AU.addPreserved<LoopInfoWrapperPass>();
 
   // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
   // here because users shouldn't directly get them from this header.
   extern char &LoopSimplifyID;
   extern char &LCSSAID;
   AU.addRequiredID(LoopSimplifyID);
+  if (Preserve)
     AU.addPreservedID(LoopSimplifyID);
   AU.addRequiredID(LCSSAID);
+  if (Preserve)
     AU.addPreservedID(LCSSAID);
   // This is used in the LPPassManager to perform LCSSA verification on passes
   // which preserve lcssa form
   AU.addRequired<LCSSAVerificationPass>();
+  if (Preserve)
     AU.addPreserved<LCSSAVerificationPass>();
 
   // Loop passes are designed to run inside of a loop pass manager which means
   // that any function analyses they require must be required by the first loop
   // pass in the manager (so that it is computed before the loop pass manager
   // runs) and preserved by all loop pasess in the manager. To make this
   // reasonably robust, the set needed for most loop passes is maintained here.
   // If your loop pass requires an analysis not listed here, you will need to
   // carefully audit the loop pass manager nesting structure that results.
   AU.addRequired<AAResultsWrapperPass>();
   AU.addPreserved<AAResultsWrapperPass>();
   AU.addPreserved<BasicAAWrapperPass>();
   AU.addPreserved<GlobalsAAWrapperPass>();
+  if (Preserve)
     AU.addPreserved<SCEVAAWrapperPass>();
   AU.addRequired<ScalarEvolutionWrapperPass>();
+  if (Preserve)
     AU.addPreserved<ScalarEvolutionWrapperPass>();
   // FIXME: When all loop passes preserve MemorySSA, it can be required and
   // preserved here instead of the individual handling in each pass.
 }
 
 /// Manually defined generic "LoopPass" dependency initialization. This is used
 /// to initialize the exact set of passes from above in \c
 /// getLoopAnalysisUsage. It can be used within a loop pass's initialization
 /// with:

 bool llvm::hasDisableAllTransformsHint(const Loop *L) {
   return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
 }
 
 bool llvm::hasDisableLICMTransformsHint(const Loop *L) {
   return getBooleanLoopAttribute(L, LLVMLoopDisableLICM);
 }
 
+bool llvm::hasMustProgress(const Loop *L) {
+  return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
+}
+
 TransformationMode llvm::hasUnrollTransformation(Loop *L) {
   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
     return TM_SuppressedByUser;
 
   Optional<int> Count =
       getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
   if (Count.hasValue())
     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
if (DT) {
         MSSAU->removeBlocks(DeadBlockSet);
         if (VerifyMemorySSA)
           MSSA->verifyMemorySSA();
       }
     }
   } else {
     assert(L->hasNoExitBlocks() &&
            "Loop should have either zero or one exit blocks.");
+    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+
     Builder.SetInsertPoint(OldBr);
     Builder.CreateUnreachable();
     Preheader->getTerminator()->eraseFromParent();
+
+    if (DT) {
+      DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}});
+      if (MSSA) {
+        MSSAU->applyUpdates(
+            {{DominatorTree::Delete, Preheader, L->getHeader()}}, *DT);
+        SmallSetVector<BasicBlock *, 8> DeadBlockSet(L->block_begin(),
+                                                     L->block_end());
+        MSSAU->removeBlocks(DeadBlockSet);
+        if (VerifyMemorySSA)
+          MSSA->verifyMemorySSA();
+      }
+    }
   }
 
   // Use a map to unique and a vector to guarantee deterministic ordering.
   llvm::SmallDenseSet<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet;
   llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
 
   if (ExitBlock) {
     // Given LCSSA form is satisfied, we should not have users of instructions

llvm/test/Transforms/LoopDeletion/early-exits.ll

+; RUN: opt < %s -loop-deletion -S | FileCheck %s
+;
+; Test insertion of early exits from dead paths.
+
+@g = external global i8
+
+; Known trip count. If %loop branches to %latch, the loop is dead.
+define void @f0() {
+; CHECK-LABEL: @f0(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %exit
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %latch
+           
+body:
+  call void @foo()        
+  br label %latch
+
+latch:
+  %next = add i64 %IV, 1
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Loop has mustprogress attribute and @Rb_tree_increment is readonly.
+; If %loop branches to %latch, the loop is dead.
+%0 = type { i32, %0*, %0*, %0* }
+define void @f1() {
+; CHECK-LABEL: @f1(
+entry:
+  br label %loop
+
+loop:                                              ; preds = %entry, %latch
+; CHECK-LABEL: loop:
+; CHECK: br i1 %i3.i3.not, label %body, label %exit
+  %i2.i2 = load i8, i8* inttoptr (i64 8 to i8*)
+  %0 = and i8 %i2.i2, 1
+  %i3.i3.not = icmp eq i8 %0, 0
+  br i1 %i3.i3.not, label %body, label %latch
+
+body:                                              ; preds = %loop
+  tail call void @foo()
+  br label %latch
+
+latch:                                              ; preds = %body, %loop
+  %i2.i = tail call %0* @Rb_tree_increment() #0
+  %i5.i.not = icmp eq %0* %i2.i, null
+  br i1 %i5.i.not, label %exit, label %loop, !llvm.loop !1
+
+exit:                                              ; preds = %latch
+  ret void
+}
+
+; Header has side-effects
+define void @f2() {
+; CHECK-LABEL: @f2(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %latch
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load volatile i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %latch
+           
+body:
+  call void @foo()        
+  br label %latch
+
+latch:
+  %next = add i64 %IV, 1
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Latch has side-effects
+define void @f3(i64* %dst) {
+; CHECK-LABEL: @f3(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %latch
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %latch
+           
+body:
+  call void @foo()        
+  br label %latch
+
+latch:
+  %next = add i64 %IV, 1
+  store volatile i64 0, i64* %dst
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Condition is not loop-invariant
+define void @f4(i64 %src) {
+; CHECK-LABEL: @f4(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %latch
+  %IV = phi i64 [ %src, %entry ], [ %next, %latch ]
+  %cmp = icmp eq i64 %IV, 0
+  br i1 %cmp, label %body, label %latch
+           
+body:
+  call void @foo()        
+  br label %latch
+
+latch:
+  %next = add i64 %IV, 1
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Header successors: one has side-effects.
+define void @f5(i64 %src) {
+; CHECK-LABEL: @f5(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %exit, label %body1
+  %IV = phi i64 [ %src, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp eq i8 %b, 0
+  br i1 %cmp, label %body0, label %body1
+           
+body0:
+; CHECK-LABEL: body0:
+; CHECK: br label %exit
+  br label %latch
+
+body1:
+; CHECK-LABEL: body1:
+; CHECK: br i1 %cmp1, label %body2, label %latch
+  call void @foo()        
+  %cmp1 = icmp ne i8 %b, 2
+  br i1 %cmp1, label %body2, label %latch
+
+body2:
+; CHECK-LABEL: body2:
+; CHECK: br label %latch
+  call void @foo()        
+  br label %latch
+
+latch:
+  %next = add i64 %IV, 1
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Switch instruction and multiple latches: only early-exit from those with no
+; side-effects.
+define void @f6(i64 %src) mustprogress {
+; CHECK-LABEL: @f6(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: switch i64 %src, label %exit [
+; CHECK-NEXT: i64 2, label %latch2
+; CHECK-NEXT: i64 4, label %exit
+  %IV = phi i64 [ %src, %entry ], [ %next1, %latch1 ],
+                [ %next2, %latch2 ], [ %next4, %latch4 ]
+  switch i64 %src, label %latch1 [ i64 2, label %latch2
+                                   i64 4, label %latch4 ]
+
+latch1:
+  %next1 = add i64 %IV, 1
+  %cmp1 = icmp ne i64 %IV, 128
+  br i1 %cmp1, label %loop, label %exit
+
+latch2:
+  call void @foo()        
+  %next2 = add i64 %IV, 2
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+latch4:
+  %next4 = add i64 %IV, 4
+  %cmp4 = icmp ne i64 %IV, 128
+  br i1 %cmp4, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; This loop has two exits which means deleteLoopIfDead() will bail. The loop
+; will however be eliminated after inserting an early exit.
+define void @f7(i1 %arg, i1 %arg2) mustprogress {
+; CHECK-LABEL: @f7(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %arg, label %exit1, label %exit0
+  br i1 %arg, label %exit1, label %body
+
+body:                                              ; preds = %bb1
+  br i1 %arg2, label %exit0, label %latch
+
+exit0:                                              ; preds = %bb2
+  unreachable
+
+latch:                                              ; preds = %bb2
+  br label %loop
+
+exit1:                                              ; preds = %bb1
+  ret void
+}
+
+; Another loop with two exits, containing just two dead blocks.
+define void @f8() {
+; CHECK-LABEL: @f8(
+entry:
+  br label %header
+
+header:
+; CHECK-LABEL: header:
+; CHECK: br i1 false, label %exit1, label %exit0
+  %i4 = phi i32 [ 0, %entry ], [ %i5, %latch ]
+  %i5 = add nuw i32 %i4, 1
+  br i1 false, label %exit1, label %latch
+
+exit1:
+  unreachable
+
+latch:
+  %i = icmp ult i32 %i5, undef
+  br i1 %i, label %header, label %exit0
+
+exit0:
+  unreachable
+
+}
+
+; Exiting block with an edge to a no-side-effects latch
+define void @f9(i64* %dst) {
+; CHECK-LABEL: @f9(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %body2
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %body2
+
+body:
+  call void @foo()
+  br label %latch
+
+body2:
+; CHECK-LABEL: body2:
+; CHECK: br i1 false, label %latch, label %exit
+  br i1 false, label %latch, label %exit
+
+latch:
+  %next = add i64 %IV, 1
+  store volatile i64 0, i64* %dst
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Branch from Top (not header) to a Bot (not latch)
+define void @f10() {
+; CHECK-LABEL: @f10(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %body2
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %body2
+
+body:
+  call void @foo()
+  br label %latch
+
+body2:
+; CHECK-LABEL: body2:
+; CHECK: br i1 false, label %body, label %exit
+  br i1 false, label %body, label %bot
+
+bot:
+; CHECK-LABEL: bot:
+; CHECK: br label %exit
+  br label %latch
+
+latch:
+  %next = add i64 %IV, 1
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Multiple exits, but only one on dead path.
+define void @f11() {
+; CHECK-LABEL: @f11(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %exit
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %bot1
+
+body:
+  call void @foo()
+  br label %latch
+
+bot0:
+  br i1 false, label %bot1, label %bot2
+
+bot1:
+; CHECK-LABEL: bot1:
+; CHECK: br i1 false, label %exit, label %exit
+  br i1 false, label %latch, label %exit
+
+bot2:
+  br i1 false, label %latch, label %exit2
+
+latch:
+  %next = add i64 %IV, 1
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop, label %exit
+
+exit:
+  ret void
+
+exit2:
+  ret void
+}
+
+; Branches to two different blocks in Bot, two different and usable exit blocks.
+define void @f12() mustprogress {
+; CHECK-LABEL: @f12(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %top1
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %top1
+
+body:
+  call void @foo()
+  br label %latch
+
+top1:
+; CHECK-LABEL: top1:
+; CHECK: br i1 false, label %exit, label %exit2
+  br i1 false, label %bot1, label %bot2
+
+bot1:
+  br i1 false, label %latch, label %exit
+
+bot2:
+  br i1 false, label %latch, label %exit2
+
+latch:
+  %next = add i64 %IV, 1
+  br label %loop
+
+exit:
+  ret void
+
+exit2:
+  ret void
+}
+
+; %loop branches to %bot1, but not a single exit block. %bot1 branches to %bot2,
+; from wich there is only one exit block.
+define void @f13() mustprogress {
+; CHECK-LABEL: @f13(
+entry:
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: br i1 %cmp, label %body, label %bot1
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %body, label %bot1
+
+body:
+  call void @foo()
+  br label %latch
+
+bot1:
+; CHECK-LABEL: bot1:
+; CHECK: br i1 false, label %exit2, label %exit
+  br i1 false, label %bot2, label %exit
+
+bot2:
+  br i1 false, label %latch, label %exit2
+
+latch:
+  %next = add i64 %IV, 1
+  br label %loop
+
+exit:
+  ret void
+
+exit2:
+  ret void
+}
+
+; Loop nest
+define void @f14() mustprogress {
+; CHECK-LABEL: @f14(
+entry:
+  br label %loop1
+
+loop1:
+; CHECK-LABEL: loop1:
+; CHECK: br i1 %cmp, label %loop2.preheader, label %exit1
+  %IV = phi i64 [ 0, %entry ], [ %next, %latch1 ]
+  %b = load i8, i8* @g
+  %cmp = icmp ne i8 %b, 0
+  br i1 %cmp, label %loop2.preheader, label %latch1
+
+loop2.preheader:
+  br label %loop2
+
+loop2:
+; CHECK-LABEL: loop2:
+; CHECK: br i1 false, label %body2, label %exit2
+  br i1 false, label %body2, label %latch2
+
+body2:
+  call void @foo()
+  br label %latch2
+
+latch2:
+  br i1 true, label %loop2, label %exit2
+
+exit2:
+  br label %latch1
+
+latch1:
+  %next = add i64 %IV, 1
+  %cmp2 = icmp ne i64 %IV, 128
+  br i1 %cmp2, label %loop1, label %exit1
+
+exit1:
+  ret void
+}
+
+declare void @foo()
+declare %0* @Rb_tree_increment()
+attributes #0 = { nounwind readonly }
+!1 = distinct !{!1, !2, !3}
+!2 = !{!"llvm.loop.mustprogress"}
+!3 = !{!"llvm.loop.unroll.disable"}