[LOOPINFO] Introduce the loop guard API.

[Whitney]

Summary

This is the first patch for the loop guard. We introduced getLoopGuardBranch() and isGuarded().

For rotated loops, the guard branch determines if the loop executes at least one iteration.
That is, a rotated loop with a guard branch will execute 0 or more times, depending on the evaluation of the guard.
On the other hand, a rotated loop with no guard branch will execute 1 or more times.
This currently only works on simplified loop, as it requires a preheader and a latch to identify the guard.
It will work on loops of the form:

/// GuardBB:
///   br cond1, Preheader, ExitSucc <== GuardBranch
/// Preheader:
///   br Header
/// Header:
///  ...
///   br Latch
/// Latch:
///   br cond2, Header, ExitBlock
/// ExitBlock:
///   br ExitSucc
/// ExitSucc:

Prior discussions leading upto the decision to introduce the loop guard API:
http://lists.llvm.org/pipermail/llvm-dev/2019-May/132607.html

[Whitney]

clang-format

[reames]

I'm not sure an API this general is the most relevant. I would have expected something more tightly tied to the loop itself instead of the region of code which contains the loop. Thinking about how transforms might want to use this, I suspect a much tighter definition would be useful.

Consider a transform which figures out a condition C under which loop L is a noop. Modifying the guard (as defined here) would not be valid, but a guard which controls the preheader directly w/no side effects possible inside the guarded region, but outside the loop would be exactly what was needed. Not sure what other transforms need off the top of my head, but I think that needs to be explored.

llvm/include/llvm/Analysis/LoopInfo.h

732 ↗

(On Diff #206881)

PostDom is not widely available in the optimizer. I strongly suspect that a narrower, but more widely usable, API would be better in practice.

737 ↗

(On Diff #206881)

Your definition would seem to disallow:
if (C) return;
for (...) {}

That is C wouldn't be considered a guard condition. Intentional?

llvm/lib/Analysis/LoopInfo.cpp

372 ↗

(On Diff #206881)

Your skipping over arbitrary throws here. Is that intended?
if (C) {

foo(); //may throw
for (...) {}

}

392 ↗

(On Diff #206881)

A quick version of this which doesn't need PDT would be to check if the second successor was one of the loops exit blocks.

[Whitney]

@reames Thanks for the review! I agree that there are still much more to consider for how we want to define a loop guard, to make the most use of it.

What's others opinion on disallow instructions with side effects in between the loop guard block and the loop header?

llvm/include/llvm/Analysis/LoopInfo.h

732 ↗

(On Diff #206881)

I heard that there is an intension to make PostDom more widely available, and I think that's the right thing to do. What do you think?

737 ↗

(On Diff #206881)

I think this is fine, in most cases, LLVM tries to common the return blocks, so if (C) will jump to the common exit block, and this algorithm will work. Although we can intensionally write LLVMIR with multiple return blocks, I don't think it will be the common case.

llvm/lib/Analysis/LoopInfo.cpp

372 ↗

(On Diff #206881)

This is a good point to discuss, what basic blocks are allowed between loop guard block and the loop header...If we decide to disallow basic blocks that may throw, we can use isGuaranteedToTransferExecutionToSuccessor() to check.

392 ↗

(On Diff #206881)

This will almost never work if the loop is in simplified form, as it needs to have dedicated exits. We could check if the second successor one of the loops exit blocks's successor, but this will only work for the most simple cases, e.g. doesn't allow any basic block between the exit block to the 'second successor'. I think instead of not using PDT, we should consider making PDT more widely available. What do you think?

[etiotto]

This comment was removed by etiotto.

[etiotto]

In D63885#1563442, @Whitney wrote:

@reames Thanks for the review! I agree that there are still much more to consider for how we want to define a loop guard, to make the most use of it.

What's others opinion on disallow instructions with side effects in between the loop guard block and the loop header?

My opinion is that we should extend the proposed API to identify 'proper' loop guards in addition to weak loop guards. A proper loop guard would protect the execution of the loop and nothing else. So it would not allow any instruction with side effects between the guard and the loop header, or other weak guards.

[Whitney]

Strengthen the definition of loop guard by disallowing non safe instructions guarded by the branch but not in the loop.

[reames]

In D63885#1563469, @etiotto wrote:

My opinion is that we should extend the proposed API to identify 'proper' loop guards in addition to weak loop guards.

I like your distinction between weak and proper guards. We probably need better terminology, but both are useful. For the moment, I'd suggest we start with the stronger form and add the weaker one later if needed.

llvm/include/llvm/Analysis/LoopInfo.h

732 ↗

(On Diff #206881)

It has "been the intention" for years. Unless someone has committed to doing the work in the next six months, I'd advice not relying on it.

737 ↗

(On Diff #206881)

Put two calls on the return paths to different targets and we don't merge them.

[Whitney]

I like your distinction between weak and proper guards. We probably need better terminology, but both are useful. For the moment, I'd suggest we start with the stronger form and add the weaker one later if needed.

For the moment, I strengthened the definition of loop guard by disallowing non safe instructions guarded by the branch but not in the loop, so there is only the stronger form. I agree that we should add the weaker form later only when needed.

llvm/include/llvm/Analysis/LoopInfo.h

732 ↗

(On Diff #206881)

@Meinersbur @jdoerfert @kbarton Do you know if there is anyone working / plan to work on it?

737 ↗

(On Diff #206881)

Do you mind giving me an example? I tried the code below, and that doesn't work.

void bar1();
void bar2();
int foo(bool cond, int *A) {
  if (cond) return 1;
  for (long i = 0; i < 100; ++i) {
    A[i] = 0;
  }
  bar1();
  bar2();
  return 0;
}

[etiotto]

In D63885#1563560, @Whitney wrote:

Strengthen the definition of loop guard by disallowing non safe instructions guarded by the branch but not in the loop.

OK, that works for me.

[reames]

llvm/include/llvm/Analysis/LoopInfo.h

737 ↗

(On Diff #206881)

void bar1();
void bar2();
int foo(bool cond, int *A) {

if (cond) { bar1(); return 1; }
for (long i = 0; i < 100; ++i) {
  A[i] = 0;
}
bar2();
return 0;

}

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

737 ↗

(On Diff #206881)

With the code above, I ran it through clang (noopt), and got:

  br i1 %tobool, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  call void @_Z4bar1v()
  store i32 1, i32* %retval, align 4
  br label %return

if.end:                                           ; preds = %entry
  store i64 0, i64* %i, align 8
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %if.end
  %1 = load i64, i64* %i, align 8
  %cmp = icmp slt i64 %1, 100
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %2 = load i32*, i32** %A.addr, align 8
  %3 = load i64, i64* %i, align 8
  %arrayidx = getelementptr inbounds i32, i32* %2, i64 %3
  store i32 0, i32* %arrayidx, align 4
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %4 = load i64, i64* %i, align 8
  %inc = add nsw i64 %4, 1
  store i64 %inc, i64* %i, align 8
  br label %for.cond

for.end:                                          ; preds = %for.cond
  call void @_Z4bar2v()
  store i32 0, i32* %retval, align 4
  br label %return

return:                                           ; preds = %for.end, %if.then
  %5 = load i32, i32* %retval, align 4
  ret i32 %5

Looks like the two returns are common into one return block.

[Meinersbur]

llvm/include/llvm/Analysis/LoopInfo.h

735–737 ↗

(On Diff #207211)

Format each enumeration item on its own line?

Apart from the conditions tested here, what is your informal definition/purpose of a loop guard?
With these conditions, anything that skips the loop without executing any additional code could be a loop guard. Imagine two blocks dominating the header; this definition would make the 'closest' the loop guard. Let's say the compiler is smart and optimizes it away. Now the other is the loop guard? Also, if was the loop guard of another loop, now it is the loops guard of both?

What is an 'unsafe' instruction and why does it stop a block being a loop guard?

Do you intend to refine the conditions of a loop guards over time?

732 ↗

(On Diff #206881)

I don't know anyone currently working on it.

However, if you intend to go into the direction of a loop-guard normal form, why not assuming that the loop guard can only be the block branching to the loop header. Not (Post-)dominator tree needed.

llvm/lib/Analysis/LoopInfo.cpp

400–401 ↗

(On Diff #207211)

What if BeginBB is (not) the header? If not, it's never added to the worklist. If it is, we are exploring the blocks inside the loop.

405–406 ↗

(On Diff #207211)

Early exit? Couldn't it be possible that there are unsafe instructions in the blocks still in the worklist?

415 ↗

(On Diff #207211)

If you want to disallow throwing instructions, how did you conclude that isGuaranteedToTransferExecutionToSuccessor is what you want and not ->mayThrow?

There might be dynamically endless loops as well that isGuaranteedToTransferExecutionToSuccessor does not check (that is, only if the endless loop was inside a call).

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

735–737 ↗

(On Diff #207211)

Format each enumeration item on its own line?

Will do.

Now the other is the loop guard?

Yes, getLoopGuardBranch() returns the 'closest' loop guard. But both branches are consider loop guards to begin with, isLoopGuardBranch() returns true for both branches if they both satisfy the requirements.

Also, if was the loop guard of another loop, now it is the loops guard of both?

hmm...only if there is no unsafe instructions guarded by that branch and outside of the loop in consideration.

What is an 'unsafe' instruction and why does it stop a block being a loop guard?

For example, instructions that may throw. In general, I would like to make sure if entered the guard region, then the loop is definitely going to be executed.

Do you intend to refine the conditions of a loop guards over time?

Yes, depending on the use cases. We will like to refine the conditions to benefit more users.

732 ↗

(On Diff #206881)

I asked in the last loop group meeting. People mentioned that with the DomTreeUpdater, making PostDom more widely available should be easier than before.

Loop-guard normal form may not be the direction we want to go, we are still trying to explore what makes the most sense.

llvm/lib/Analysis/LoopInfo.cpp

400–401 ↗

(On Diff #207211)

I should assert that BeginBB dominate Header, and EndBB post dominate Header. And right, I was only thinking of the case when there is a preheader, I should also consider when there is no preheader, which means BeginBB can be Header.

405–406 ↗

(On Diff #207211)

Good catch! Will fix it.

415 ↗

(On Diff #207211)

I chose isGuaranteedToTransferExecutionToSuccessor instead of ->mayThrow is because it consider more cases, for example it checks if memory operation trap. isGuaranteedToTransferExecutionToSuccessor is a superset of ->mayThrow.

What is dynamically endless loops?

[Whitney]

Addressed code review comments from @Meinersbur

[Meinersbur]

llvm/lib/Analysis/LoopInfo.cpp

415 ↗

(On Diff #207211)

What is dynamically endless loops?

header:
  %cmp = icmp ule i32 0, %a ; anything that always returns true but LLVM cannot figure out
  br i1 %cmp, label %header, label %exit

exit:

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

737 ↗

(On Diff #206881)

Put two calls on the return paths to different targets and we don't merge them.

@reames Do you have another example which I should pay attention on?

llvm/lib/Analysis/LoopInfo.cpp

415 ↗

(On Diff #207211)

I would like to make sure I understand the concern correctly. Is the concern that the guard guards an dynamically endless loops before the loop of interested?

[Meinersbur]

llvm/lib/Analysis/LoopInfo.cpp

415 ↗

(On Diff #207211)

Previously, you mentioned:

In general, I would like to make sure if entered the guard region, then the loop is definitely going to be executed.

isGuaranteedToTransferExecutionToSuccessor is not sufficient for this goal:

1. There might be such an endless loop between the guard's branch target and the loop of interest.

2. There can be other branches between, including, but not limited to, other loop guards.

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

415 ↗

(On Diff #207211)

Thanks for the explanation. That's true. Thinking to disallow conditional branches in the guarded region but not in the loop. Not sure if that's the best way of solving this problem. What do you think?

[Meinersbur]

llvm/lib/Analysis/LoopInfo.cpp

415 ↗

(On Diff #207211)

Following the idea to first provide a narrow but meaningful definition, I'd disallow these things at the start. When we have users of loop guards, we can discuss how much we could relax the definition.

[Whitney]

Disallow blocks with non unique successors in the guarded region but outside of the loop of interest.

[Whitney]

@Meinersbur As discussed, I strengthened the definition of the loop guard which disallow conditional terminator instructions inside the guarded region outside of the loop of interest.
@Meinersbur @reames @etiotto Do you think this patch is now good enough to land as the first patch? We can loosen or strengthen the definition of the loop guard in later patches when applicable.

[Meinersbur]

llvm/lib/Analysis/LoopInfo.cpp

418–419 ↗

(On Diff #209390)

With this added, we don't need a DominatorTree anymore. Any guard will directly branch into the header (or a series of unconditional branches such as the preheader).

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

418–419 ↗

(On Diff #209390)

Without DominatorTree, how can we know a given branch will directly/indirectly branch into the header? It could be a branch after the loop. Did I miss something?

[Meinersbur]

llvm/lib/Analysis/LoopInfo.cpp

418–419 ↗

(On Diff #209390)

By following the loop header's predecessors until there is a non-unconditional branch. With the restriction of not allowing conditional branches between guard and header, it's the only candidate for a loop guard.

[Whitney]

Removed the use of Dominator Tree, and removed isLoopGuardBranch() as the loop guard definition is now the same as getLoopGuardBranch().

[kbarton]

In D63885#1563245, @reames wrote:

I'm not sure an API this general is the most relevant. I would have expected something more tightly tied to the loop itself instead of the region of code which contains the loop. Thinking about how transforms might want to use this, I suspect a much tighter definition would be useful.

Consider a transform which figures out a condition C under which loop L is a noop. Modifying the guard (as defined here) would not be valid, but a guard which controls the preheader directly w/no side effects possible inside the guarded region, but outside the loop would be exactly what was needed. Not sure what other transforms need off the top of my head, but I think that needs to be explored.

@reames Could you expand a bit more on what you mean by "a guard which controls the preheader directly"? At first I took that to mean the guard should be the immediate dominator of the preheader, but now I'm not sure if that is what you meant.
There have been a lot of changes since this comment to check for side effects, but nothing that addresses the "controls the preheader directly".

I'm also not convinced that checking for side effects at the same time as trying to identify the guard is a good idea. To me they are very separate concepts, and combining them ends up confusing things.

[reames]

In D63885#1587492, @kbarton wrote:

In D63885#1563245, @reames wrote:

I'm not sure an API this general is the most relevant. I would have expected something more tightly tied to the loop itself instead of the region of code which contains the loop. Thinking about how transforms might want to use this, I suspect a much tighter definition would be useful.

Consider a transform which figures out a condition C under which loop L is a noop. Modifying the guard (as defined here) would not be valid, but a guard which controls the preheader directly w/no side effects possible inside the guarded region, but outside the loop would be exactly what was needed. Not sure what other transforms need off the top of my head, but I think that needs to be explored.

@reames Could you expand a bit more on what you mean by "a guard which controls the preheader directly"? At first I took that to mean the guard should be the immediate dominator of the preheader, but now I'm not sure if that is what you meant.

I meant that we should focus on finding a guarding branch which directly controls entry into the loop preheader, not some arbitrary earlier branch which happens to avoid the whole section of the CFG. I believe from the discussion, that the patch has evolved in this direction.

I'm also not convinced that checking for side effects at the same time as trying to identify the guard is a good idea. To me they are very separate concepts, and combining them ends up confusing things.

I find the opposite very confusing, so we're even.

I'm about to do a run through the patch and review "fresh". I have not been following all of the discussion, so it's possible I'll miss something which has already been discussed, but that way it's approachable without having to catch up on a bunch of back and forth.

[reames]

Took a fresh look at the patch. The currently posted revision still uses PostDominatorTree. As previously described, I feel doing so is a very bad idea. As I will not LGTM the patch with this present, I stopped reading there and did not bother to review further.

To be clear here, I am not *objecting* to *someone else* reviewing the patch. I'm simply stating that *I* will not sign off on this patch in the current form as it doesn't achieve an objective I find useful. (i.e. It doesn't result in something I can use or build upon in existing transforms passes.)

[Whitney]

@reames @Meinersbur As discussed in the loop group meeting, I changed PDT to optionally require. The functions will work for the more general form if PDT is given.

[Meinersbur]

So far, we have the following guarantees of a loop guard:

1. If branching into the direction of the loop, the loop will be executed
2. If branching to the other direction, the loop will not be executed.
3. If branching to the other direction, no code will be executed that would not be executed if going to the direction of the loop.
4. Loop guard and the post-dominating 'other' block form a Single-Entry-Single-Exit region. [edit: not true; there can be edges from the outside to a loop exit block]

What purpose does checking for unsafe instructions after the loop serve? Do we also need to exclude possible infinite loops after the loop exit(s)? [branches out of the region including unreachable, ret are already ruled out be the postdominator construction].

For 2., if that's the goal, could there be an alternative formulation, such as the loop exit block dominates the "other direction block"?

[reames]

Please, please, please, reduce the complexity of this patch. Start with the simplest possible implementation which handles one trivial case. Get that in with the interface, then incrementally build on top of that. You are stuck in a review cycle where there's enough different aspects of this patch that we will keep finding problems for many more iterations. You best (and possibly only) way out of that is to reduce scope until there's nothing left that anyone can possibly object to, then build incrementally off the agreed baseline!

llvm/lib/Analysis/LoopInfo.cpp

409 ↗

(On Diff #210383)

This code is overly general and confusingly so. Walking arbitrary successors is exploring an overly large portion of the CFG, even for the PDT case!

It's possible there's something about the way it's called which makes this not so, but a quick skim of the code doesn't make that obvious, so there's a readability problem here at least.

417 ↗

(On Diff #210383)

This appears to be trying to handle the case where a loop has multiple predecessors outside of a loop. DONT. Use getPredecessor and let this all simplify.

432 ↗

(On Diff #210383)

Loops frequently have more than one exit block, at least an early return is needed here.

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

409 ↗

(On Diff #210383)

I will think about how to simplified this further at least for the first patch.

417 ↗

(On Diff #210383)

I am trying to handle the case where there doesn't exists a preheader. I can modified the function to only allow loop with preheader.

432 ↗

(On Diff #210383)

I thought nullptr is allowed in comparison. I still want to continue when ExitBlock is nullptr, as it maybe able to use PDT (if given) for multi exit blocks loop.

[Whitney]

Changed this patch to only work on the simplest form.

[reames]

LGTM w/required changes before submit.

p.s. Your next step after this lands needs to be finding a consumer. I'm willing to approve this speculatively, but if it sits in tree unused for long, it will be deleted.

llvm/include/llvm/Analysis/LoopInfo.h

734 ↗

(On Diff #210960)

Before submit, remove the text about number of times the loop executes. This is confusing as you don't define which portion of the loop you mean, and the terminology needs word smithed. This can be added in a follow on patch.

llvm/lib/Analysis/LoopInfo.cpp

363 ↗

(On Diff #210960)

In a follow on patch, these restrictions should be converted to early returns. (i.e. there's no need to have this be a strict precondition)

386 ↗

(On Diff #210960)

Branches only have 2 successors, so remove that check.
And replace the dyn_cast_or_null with a dyn_cast. getTerminator can never return null on properly constructed IR.

[Whitney]

Next step after this lands is modifying Loop Fusion to use the loop guard. @kbarton

llvm/lib/Analysis/LoopInfo.cpp

386 ↗

(On Diff #210960)

A branch instruction can have 1 successor if it is not conditional. This function is a utility function, so it can be called anywhere, which include basic block in the middle of construction, so it is possible that getTerminator return nullptr.

[reames]

llvm/lib/Analysis/LoopInfo.cpp

386 ↗

(On Diff #210960)

It's idiomatic to use isConditional for the former, and no to the later. Utilities assume well constructed IR unless there is a dang good motivating example not to. Please fix.

[kbarton]

In D63885#1595954, @reames wrote:

LGTM w/required changes before submit.

p.s. Your next step after this lands needs to be finding a consumer. I'm willing to approve this speculatively, but if it sits in tree unused for long, it will be deleted.

As @Whitney mentioned below, I'm working on a patch for LoopFusion to use these interfaces. I will hopefully have it posted by the end of this week.

llvm/trunk/include/llvm/Analysis/LoopInfo.h

public:
   ///
   PHINode *getCanonicalInductionVariable() const;
 
   /// Obtain the unique incoming and back edge. Return false if they are
   /// non-unique or the loop is dead; otherwise, return true.
   bool getIncomingAndBackEdge(BasicBlock *&Incoming,
                               BasicBlock *&Backedge) const;
 
-  /// Below are some utilities to get loop bounds and induction variable, and
-  /// check if a given phinode is an auxiliary induction variable, as well as
-  /// checking if the loop is canonical.
+  /// Below are some utilities to get the loop guard, loop bounds and induction
+  /// variable, and to check if a given phinode is an auxiliary induction
+  /// variable, if the loop is guarded, and if the loop is canonical.
   ///
   /// Here is an example:
   /// \code
   /// for (int i = lb; i < ub; i+=step)
   ///   <loop body>
   /// --- pseudo LLVMIR ---
   /// beforeloop:
   ///   guardcmp = (lb < ub)
public:
   ///   - getStepInst            --> i_2 = i_1 + step
   ///   - getStepValue           --> step
   ///   - getFinalIVValue        --> ub
   ///   - getCanonicalPredicate  --> '<'
   ///   - getDirection           --> Increasing
   ///
   /// - getInductionVariable            --> i_1
   /// - isAuxiliaryInductionVariable(x) --> true if x == i_1
+  /// - getLoopGuardBranch()
+  ///                 --> `if (guardcmp) goto preheader; else goto afterloop`
+  /// - isGuarded()                     --> true
   /// - isCanonical                     --> false
   struct LoopBounds {
     /// Return the LoopBounds object if
     /// - the given \p IndVar is an induction variable
     /// - the initial value of the induction variable can be found
     /// - the step instruction of the induction variable can be found
     /// - the final value of the induction variable can be found
     ///
public:
   /// - not used outside of the loop
   /// - incremented by a loop invariant step for each loop iteration
   /// - step instruction opcode should be add or sub
   /// Note: auxiliary induction variable is not required to be used in the
   ///       conditional branch in the loop latch. (but it can be)
   bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
                                     ScalarEvolution &SE) const;
 
+  /// Return the loop guard branch, if it exists.
+  ///
+  /// This currently only works on simplified loop, as it requires a preheader
+  /// and a latch to identify the guard. It will work on loops of the form:
+  /// \code
+  /// GuardBB:
+  ///   br cond1, Preheader, ExitSucc <== GuardBranch
+  /// Preheader:
+  ///   br Header
+  /// Header:
+  ///  ...
+  ///   br Latch
+  /// Latch:
+  ///   br cond2, Header, ExitBlock
+  /// ExitBlock:
+  ///   br ExitSucc
+  /// ExitSucc:
+  /// \endcode
+  BranchInst *getLoopGuardBranch() const;
+
+  /// Return true iff the loop is
+  /// - in simplify rotated form, and
+  /// - guarded by a loop guard branch.
+  bool isGuarded() const { return (getLoopGuardBranch() != nullptr); }
+
   /// Return true if the loop induction variable starts at zero and increments
   /// by one each time through the loop.
   bool isCanonical(ScalarEvolution &SE) const;
 
   /// Return true if the Loop is in LCSSA form.
   bool isLCSSAForm(DominatorTree &DT) const;
 
   /// Return true if this Loop and all inner subloops are in LCSSA form.

llvm/trunk/lib/Analysis/LoopInfo.cpp

bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
   if (IndDesc.getInductionOpcode() != Instruction::Add &&
       IndDesc.getInductionOpcode() != Instruction::Sub)
     return false;
 
   // Incremented by a loop invariant step for each loop iteration
   return SE.isLoopInvariant(IndDesc.getStep(), this);
 }
 
+BranchInst *Loop::getLoopGuardBranch() const {
+  assert(isLoopSimplifyForm() && "Only valid for loop in simplify form");
+  BasicBlock *Preheader = getLoopPreheader();
+  BasicBlock *Latch = getLoopLatch();
+  assert(Preheader && Latch &&
+         "Expecting a loop with valid preheader and latch");
+  assert(isLoopExiting(Latch) && "Only valid for rotated loop");
+
+  Instruction *LatchTI = Latch->getTerminator();
+  if (!LatchTI || LatchTI->getNumSuccessors() != 2)
+    return nullptr;
+
+  BasicBlock *ExitFromLatch = (LatchTI->getSuccessor(0) == getHeader())
+                                  ? LatchTI->getSuccessor(1)
+                                  : LatchTI->getSuccessor(0);
+  BasicBlock *ExitFromLatchSucc = ExitFromLatch->getUniqueSuccessor();
+  if (!ExitFromLatchSucc)
+    return nullptr;
+
+  BasicBlock *GuardBB = Preheader->getUniquePredecessor();
+  if (!GuardBB)
+    return nullptr;
+
+  assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
+
+  BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
+  if (!GuardBI || GuardBI->isUnconditional())
+    return nullptr;
+
+  BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
+                                   ? GuardBI->getSuccessor(1)
+                                   : GuardBI->getSuccessor(0);
+  return (GuardOtherSucc == ExitFromLatchSucc) ? GuardBI : nullptr;
+}
+
 bool Loop::isCanonical(ScalarEvolution &SE) const {
   InductionDescriptor IndDesc;
   if (!getInductionDescriptor(SE, IndDesc))
     return false;
 
   ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
   if (!Init || !Init->isZero())
     return false;

llvm/trunk/unittests/Analysis/LoopInfoTest.cpp

 //===- LoopInfoTest.cpp - LoopInfo unit tests -----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 /// Build the loop info for the function and run the Test.
 static void
 runWithLoopInfo(Module &M, StringRef FuncName,
                 function_ref<void(Function &F, LoopInfo &LI)> Test) {
   auto *F = M.getFunction(FuncName);
   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
   // Compute the dominator tree and the loop info for the function.
   DominatorTree DT(*F);
   LoopInfo LI(DT);
   Test(*F, LI);
 }
 
 /// Build the loop info and scalar evolution for the function and run the Test.
 static void runWithLoopInfoPlus(
     Module &M, StringRef FuncName,
-    function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE,
-                      PostDominatorTree &PDT)>
-        Test) {
+    function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
   auto *F = M.getFunction(FuncName);
   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
 
   TargetLibraryInfoImpl TLII;
   TargetLibraryInfo TLI(TLII);
   AssumptionCache AC(*F);
   DominatorTree DT(*F);
   LoopInfo LI(DT);
   ScalarEvolution SE(*F, TLI, AC, DT, LI);
-
-  PostDominatorTree PDT(*F);
-  Test(*F, LI, SE, PDT);
+  Test(*F, LI, SE);
 }
 
 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
                                               const char *ModuleStr) {
   SMDiagnostic Err;
   return parseAssemblyString(ModuleStr, Err, Context);
 }
 
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopWithInverseGuardSuccs) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp sge i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopWithSwappedGuardCmp) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp sgt i32 %ub, 0\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopWithInverseLatchSuccs) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopWithLatchCmpNE) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopWithGuardCmpSLE) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %ubPlusOne = add i32 %ub, 1\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ubPlusOne");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopNonConstantStep) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopUnsignedBounds) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp ult i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_ULT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, DecreasingLoop) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         EXPECT_EQ(Bounds->getInitialIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_EQ(StepValue, nullptr);
         ConstantInt *FinalIVValue =
             dyn_cast<ConstantInt>(&Bounds->getFinalIVValue());
         EXPECT_TRUE(FinalIVValue && FinalIVValue->isZero());
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SGT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Decreasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, CannotFindDirection) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
const char *ModuleStr =
       "for.end:\n"
       "  ret void\n"
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
-  runWithLoopInfoPlus(*M, "foo",
-                      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-                          PostDominatorTree &PDT) {
-                        Function::iterator FI = F.begin();
-                        // First two basic block are entry and for.preheader
-                        // - skip them.
-                        ++FI;
-                        BasicBlock *Header = &*(++FI);
-                        assert(Header->getName() == "for.body");
-                        Loop *L = LI.getLoopFor(Header);
-                        EXPECT_NE(L, nullptr);
+  runWithLoopInfoPlus(
+      *M, "foo",
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 
-                        Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
-                        EXPECT_NE(Bounds, None);
-                        ConstantInt *InitialIVValue =
-                            dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
-                        EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
-                        EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
-                        EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
-                        EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
-                        EXPECT_EQ(Bounds->getCanonicalPredicate(),
-                                  ICmpInst::BAD_ICMP_PREDICATE);
-                        EXPECT_EQ(Bounds->getDirection(),
-                                  Loop::LoopBounds::Direction::Unknown);
-                        EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
-                      });
+        EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
 }
 
 TEST(LoopInfoTest, ZextIndVar) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "indvars.iv.next");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "wide.trip.count");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_NE);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, UnguardedLoop) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  br label %for.body\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
         // First basic block is entry - skip it.
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
+        EXPECT_FALSE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
       "entry:\n"
       "  br i1 %cond, label %for.preheader, label %for.end\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, LoopNest) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.outer.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.outer");
+        BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator());
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
         EXPECT_NE(Bounds, None);
         ConstantInt *InitialIVValue =
             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer");
         ConstantInt *StepValue =
             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(Bounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j");
+        EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard);
+        EXPECT_TRUE(L->isGuarded());
 
         // Next two basic blocks are for.outer and for.inner.preheader - skip
         // them.
         ++FI;
         Header = &*(++FI);
         assert(Header->getName() == "for.inner");
         L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE);
         EXPECT_NE(InnerBounds, None);
         InitialIVValue =
             dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue());
         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
         EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc");
         StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue());
         EXPECT_TRUE(StepValue && StepValue->isOne());
         EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub");
         EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
         EXPECT_EQ(InnerBounds->getDirection(),
                   Loop::LoopBounds::Direction::Increasing);
         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
+        EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 TEST(LoopInfoTest, AuxiliaryIV) {
   const char *ModuleStr =
       "define void @foo(i32* %A, i32 %ub) {\n"
       "entry:\n"
       "  %guardcmp = icmp slt i32 0, %ub\n"
const char *ModuleStr =
       "}\n";
 
   // Parse the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 
   runWithLoopInfoPlus(
       *M, "foo",
-      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE,
-          PostDominatorTree &PDT) {
+      [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
         Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI);
+        BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
         // First two basic block are entry and for.preheader - skip them.
         ++FI;
         BasicBlock *Header = &*(++FI);
         assert(Header->getName() == "for.body");
         Loop *L = LI.getLoopFor(Header);
         EXPECT_NE(L, nullptr);
 
         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
runWithLoopInfoPlus(
         EXPECT_FALSE(
             L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE));
         PHINode &Instruction_usedoutside = cast<PHINode>(*(++II));
         EXPECT_FALSE(
             L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE));
         PHINode &Instruction_mulopcode = cast<PHINode>(*(++II));
         EXPECT_FALSE(
             L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE));
+        EXPECT_EQ(L->getLoopGuardBranch(), Guard);
+        EXPECT_TRUE(L->isGuarded());
       });
 }
 
 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions.
 TEST(LoopInfoTest, LoopUniqueExitBlocks) {
   const char *ModuleStr =
       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
       "define void @foo(i32 %n, i1 %cond) {\n"