[LOOPINFO] Extend Loop object to add utilities to get the loop bounds, step, and loop induction variable.

[Whitney]

Summary

This PR extends the loop object with more utilities to get loop bounds, step, and loop induction variable. There already exists passes which try to obtain the loop induction variable in their own pass, e.g. loop interchange. It would be useful to have a common area to get these information.

/// Example:
/// for (int i = lb; i < ub; i+=step)
///   <loop body>
/// --- pseudo LLVMIR ---
/// beforeloop:
///   guardcmp = (lb < ub)
///   if (guardcmp) goto preheader; else goto afterloop
/// preheader:
/// loop:
///   i1 = phi[{lb, preheader}, {i2, latch}]
///   <loop body>
///   i2 = i1 + step
/// latch:
///   cmp = (i2 < ub)
///   if (cmp) goto loop
/// exit:
/// afterloop:
///
/// getBounds
///   getInitialIVValue      --> lb
///   getStepInst            --> i2 = i1 + step
///   getStepValue           --> step
///   getFinalIVValue        --> ub
///   getCanonicalPredicate  --> '<'
///   getDirection           --> Increasing
/// getInductionVariable          --> i1
/// getAuxiliaryInductionVariable --> {i1}
/// isCanonical                   --> false

[jdoerfert]

llvm/include/llvm/Analysis/LoopInfo.h

569

Maybe mention how one is supposed to determine this precondition.

591

Do you check, or enforce, that the Step is "canonical", e.g., the step is on the right?
I tried to find this below but I couldn't.

594

Do you check, or enforce, that the ICmpInst is "canonical", e.g., the bound is on the right?
I tried to find this below but I couldn't.

598

Doesn't this contradict the getStepInst().getOperand(1); in line 599?

625

I'd start comments with an upper case letter, again below. (sorry for the nitpicking).

632

Please rename if it is "the latch condition" to sth like "LatchCmpInst".

638

else "None".

646

Do you really test that? The initial loop fusion patch did not.

665

"in a" or "in the", but I might be wrong here.

llvm/lib/Analysis/IVDescriptors.cpp

1057 ↗

(On Diff #196634)

Does this work if there is no loop latch? I have the feeling Phi->getIncomingValueForBlock might choke on a nullptr. I might be wrong though.

I feel the changes in this file are unrelated and can go before the rest. If you agree, open a new patch for them, maybe with a test, and I'll accept it as it is pretty straight forward.

llvm/lib/Analysis/LoopInfo.cpp

198

[I don't care too much but I'm interested:] Any reason you separated setIniitalIVValue and setStepInst?

224

I am not sure this is in sync with the constant getOperand(1) in one of the headers.

228

Why do you have the non-SE path above for certain special cases e.g.,. non-equality conditions, before you have a, what seems to be, general SE based handling?

261

Couldn't we return nullptr here as well? It seems nullptr is a valid return value here anyway.

271

[IMPORTANT] How do we know or enforce this?

292

-"where"
+"if"

294

"and a definite successor of a loop exit block (trivially) post-dominates the other successor.
The second condition ensures the branch is a control dependence of the loop."

310

Maybe we need a more general picture here as the example shows the simple case. I can imagine some "ascii-art" or a more elaborate description.

322

if (!GuardBB) return nullptr

323

GuardBI is overwritten before used.

340

The comment is outdated (ExitBlock)

344

We often use the pattern:

if (!Visited.insert(GuardBB).second) 
  return nullptr;

360

Why do we "compute" the index of the Successor if we assert it is 1 anyway? This seems like a specialization of a more general scheme.

363

I'm always for newlines to mark control condition changes

364

This is the general version (see above) again.

373

You could instead call Visited.clear() here but I don't mind a new object.

[Whitney]

llvm/include/llvm/Analysis/IVDescriptors.h

319 ↗

(On Diff #196634)

I added the check IK == IK_FpInduction which is required in the comment the induction type is FP. Originally we don't need to check that, because InductionBinOp is not set for non FP inductions, my change below will set it for cases that are not FP.

327 ↗

(On Diff #196634)

same as above

llvm/include/llvm/Analysis/LoopInfo.h

569

As LoopBounds take a reference of IndVar, meaning that LoopBounds can only be created if an induction variable. Is it better if I remove the comment?

594

It is enforced by getCmpInst().

598

in line 599, we are looking at the instruction which update the induction variable, and getting the step. While here we are talking about the latch compare instruction, and checking if operand(1) is the step instruction.

646

I may not have understand the question correctly. getGuard() checks if the condition satisfy the latch condition by comparing the operands and the predicate of the branch instruction with the bounds of the loop.

llvm/lib/Analysis/IVDescriptors.cpp

1057 ↗

(On Diff #196634)

I was trying to follow the similar semantic as the line above. However, I agree that it is a good idea to check if the latch is nullptr first.

I will open a new patch with the changes on IVDescriptors.

llvm/lib/Analysis/LoopInfo.cpp

198

The reason is there are getInitialIVValue() and getStepInst(). I don't have strong feeling either ways.

224

I think you are talking about the getOperand(1) in getStepInst(), which is looking at the StepInst, and here we are looking at the LatchCmpInst.

228

when the predicate is not ne and not eq, then there is no need to use SE, we can simply flip the strictness of the predicate.

360

There is not just asserting the index of the successor is 1, it is asserting either the successor which skip the loop is 1 or Succ is index 1 (i.e. the successor which skip the loop is 0)

364

see above reply.

373

I prefer a new object, because we don't need to keep track if the live range of the other Visited. If you don't have a strong feeling, I will keep it as is.

[kbarton]

llvm/include/llvm/Analysis/LoopInfo.h

583

"which update" -> "that updates"

585

instrucion -> instruction

589

"get updated for" -> "gets updated by in"

591

This is assuming the step instruction has a very specific form. Is it safe to assume this all the time (it may be and I just haven't got to that part of the code yet).

594

Same - this is assuming a very specific format for the compare. Is it guaranteed to be true in all cases?

598

Can you clarify this comment?
Does this method assume:

1. The first successor of the latch branch is the loop header
2. The LHS of the latch comparison is the StepInst?

and if both of these conditions are not met, then what does it return?

612

Can IndVar be made const?

615

"which update" -> "that updates"

616

Is it strictly necessary that the IV be the LHS?
What if you write:

(for i=0; N>i; i++)

Does LLVM switch it back to always be on the LHS?

620

Can you clarify this comment?
If the bounds are not constant, it should return Unknown right?

626

This is minor, but I think a more descriptive variable name would be useful here. Something like InitialIVValue, or even InitialValue.

644

I would have expected the guard to dominate the preheader, and not have another block between the guard and the preheader. Or maybe I misunderstand this point.

645

"a" loop exit block, or "the" loop exit block?
Do these methods work on loops that have multiple exit blocks?
If they do work on loops with multiple exit blocks, then I would think that all loop exit blocks need to dominate the other successor.

647

What do you mean the loop initial value?

I think what you're trying to say is guard condition guarantees the loop body should be executed at least once. The only way I can think to say that using the current terminology is the lower bound of the loop is less than the upper bound (although that may not cover all possible conditions).

656

I find this very confusing.
I would have expected the getInductionVariable to return a Value, not an instruction. Strictly speaking, I don't think a PHINode is considered a variable.

What is the utility of returning the PHINode here instead of the actual Value?

657

I'm not a big fan of boolean parameters. They're generally an indication that you're doing too much in the method and it should be split up into two separate methods.

660

varaible -> variable

668

This seems to be more restrictive then the check for induction variable.
Specifically, not being used outside the loop and the step instruction being an add or sub.

670

The auxiliary induction variable is not required to be used or cannot be used?
What happens if it is used in the conditional branch? Can that happen?

llvm/lib/Analysis/LoopInfo.cpp

230

How do you know to use the signed version, instead of the unsigned version?

230

Do you handle the ULE/SLE case anywhere?

293

I'm confused why one successor of the guard should dominate the preheader, not be the preheader itself.

335

This will miss the case where a basic block has multiple predecessors, but all of the predecessors are to the same block.
I don't think this is a big deal, just pointing it out. I think if you've run simplifycfg prior to this, that should get cleaned up.

374

Is it possible for getUniqueExitBlocks to add null pointers into the ExitBlocks?
I would have thought this is not possible (i.e., something is wrong if that's happening). Maybe it would be better to assert(ExitBlock && "Expecting valid ExitBlock") before the while loop to catch this if it happens.

379

This is just checking that one of the exit blocks goes to the "other" successor of the guard.
Do you not need to check that all of the exit blocks go to that block?

457

How do you know the induction variable is always operand 0 of CmpInst?

472

Can you use a phi iterator here instead?
for (PHINode &PN : Header->phis()) { ... }

475

Doesn't this assert mean the only phis you expect to find in the header are from the latch block?
Is that always going to be true?

527

fpr -> for ?
If not, what does fpr stand for?

llvm/unittests/Analysis/LoopInfoTest.cpp

34

Did clang-format format this for you?
The formatting is different then the formatting above.

[jdoerfert]

llvm/include/llvm/Analysis/IVDescriptors.h

319 ↗

(On Diff #196634)

Is this unrelated to the main part as the changes wrt setting the InductionBinOp below?

llvm/include/llvm/Analysis/LoopInfo.h

569

No, keep it.

However, later, e.g., in setStepInst, you assert(isInductionPHI(IndVar)) or something similar. The comment states this assertion in words but it could mention the isInductionPHI function which allows to verify the precondition outside of the LoopBounds.

594

getCmpInst() looks for an instruction on the LHS, that does not mean anything on its own.

598

OK.

llvm/lib/Analysis/IVDescriptors.cpp

1057 ↗

(On Diff #196634)

I was trying to follow the similar semantic as the line above. However, I agree that it is a good idea to check if the latch is nullptr first.

You are right, it should work, no need to check for nullptr but you can.

I will open a new patch with the changes on IVDescriptors.

Thanks.

llvm/lib/Analysis/LoopInfo.cpp

198

If that is the only reason I'd merge them into an initialize method or sth.

224

Probably/Hopefully, correct.

360

You are obviously right here, ...

I should not do code reviews at night...

373

No strong feeling, keep it.

379

That is a good point, it should for sure be stated clearly what is computed here.

[Whitney]

llvm/include/llvm/Analysis/IVDescriptors.h

319 ↗

(On Diff #196634)

Created https://reviews.llvm.org/D61329 for changes in IVDescriptors.

llvm/include/llvm/Analysis/LoopInfo.h

598

It returns the predicate when the two points are satisfied.
e.g. if the second successor of the latch latch is the loop header instead of the first, then it returns the inverse predicate.
I will modify the comment to clarify that.

644

It is possible to have blocks in between the guard and the preheader, the simplest example would be empty blocks. one successor dominates the loop preheader ensures that the guard dominate the preheader.

645

It should work on loops that have multiple exit blocks as well. Why do all loop exit blocks need to dominate the other successor? The guard should just skip the loop, and all loop exit blocks are outside of the loop, as long as one of them dominate the other successor, then it proves the guard skip the entire loop (given that one successor dominate the preheader which is the only entry point to the loop). Please correct me if I am wrong.

647

The reason I use the term loop initial value instead of lower bound is the loop maybe decreasing.

656

An existing function getCanonicalInductionVariable() also return PHINode *. Which value do you mean by the actual Value?

668

Right, that's the intensional behaviour

670

It can be used, it is not *required* to be used.

llvm/lib/Analysis/LoopInfo.cpp

230

getCanonicalPredicate() is used by getGuard() which get the Signed Predicate for both the latch and the potential guard to compare, so it doesn't matter if SLE or ULE is returned.

293

because it may not be the case, simplest example would be empty blocks

335

hmmm....in that case, maybe I should use getUniquePredecessor() instead of getSinglePredecessor().

374

ExitBlock is overriden in the loop ExitBlock = ExitBlock->getSingleSuccessor();, so ExitBlock can be nullptr.

379

The purpose of the guard should just skip the entire loop, given that one successor dominates the loop preheader, which is the only entry point to the loop, then any loop exit block dominates other successor should be enough to prove that it skips the loop, as loop exit blocks are not part of the loop. Please correct me if I am wrong.

475

this assert means any phis in the header should have an incoming value from the latch block. This should always be true, because by definition the exists a branch from the latch to the header if latch exists.

llvm/unittests/Analysis/LoopInfoTest.cpp

34

That's from clang-format, I guess is because of the longer function name.

[Meinersbur]

Generally, I'd prefer to use ScalarEvolution over inspecting (and expecting specific) instructions in a loop, whenever possible. Some canonicalization passes are designed for this. In particular, IndVarSimplify used to make canonical loops (i.e. start at zero, increment by one). r133502 introduced -disable-iv-rewrite to rely more on ScalarEvolution instead of "opcode/pattern matching" (cite from the commit message). -enable-iv-rewrite=false was made the default in r139579 after finding that it slows down many benchmarks. It was completely removed in r153260.

That is, such pattern matching will miss many loops that could have detected with ScalarEvolution or induction-variable rewriting. We could either re-introduce iv-rewrite or make the pattern matching more general (but also more complex) when needed. IMHO, both are less preferable.

ScalarEvolution might not cover all use cases and the LoopInterchange implementation currently is based on finding the induction variable. However, IMHO we should reduced direct uses of the induction variable instead of promoting it to an API.

[Whitney]

Addressed all the easier review comments first.

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

612

No, because isInductionPHI() takes a non const IndVar.

llvm/lib/Analysis/LoopInfo.cpp

294

exit block -> ....-> the other successor
exit block dominates the other successor...
why should it change to successor of loop exit block (trivially) post dominates the other successor?

[kbarton]

llvm/include/llvm/Analysis/LoopInfo.h

417

Minor comment, but I think it's better to make the names as specific as possible. So, this could be getGuardBranch, instead of just getGuard, to distinguish between getGuardBlock for example.

423

How is this method different from getCanonicalInductionVariable?
If these are fundamentally different, then the comments need to be clear what the differences are and when one should be used over the other.

566

This is minor, but have you tried running this through doxygen to see what the output looks like?
It may come out looking much different in the doxygen pages then it does here.

598

I think this comment needs to be clarified further as I find it confusing the way it is written.
In particular, the mixing of itemization (before the example) and enumeration (after the example) . Can you rewrite it to make it more clear?

656

Yes, I saw that now. Perhaps I'm just being too pedantic on the terminology that is being used.
I would have expected a method that returns a "Variable" to be a Value, not a PHINode (an instruction). However, you can get to the Value from the PHINode, so it's probably OK.

If others have strong feelings about this on way or another, please comment.

673

Minor comment -the parenthetical should be before the period, not after.

llvm/lib/Analysis/LoopInfo.cpp

230

Can you make it explicit in the comments for getCanonicalPredicate that it will always return the signed predicate, even if the latch uses the unsigned version?

240

If neither of these conditions are true, LoopBounds will be initialized with a null StepValue. I'm assuming this is intended behaviour.

Can you please add a comment to the getStepValue method that says it will return nullptr if the StepValue cannot be determined?

255

Should this be dyn_cast_or_null instead, to account for the possibility that getTerminator could returns nullptr?

348

I don't understand the comments below, specifically what the --> is meant to indicate.
I think it should be sufficient to say the method returns a branch instruction that branches around the specified loop.
Also, the GuardBB, SkipIndex, SkipToBlock, etc., are all local variables that don't escape this method, so they are typically not documented in the function comments.

355

Can you rename this method to indicate you are returning a branch instruction (e.g., getPotentialGuardBranch).

418

In the comments you describe the guard in terms of dominance, but you don't use dominance anywhere in the function.

I would suggest trying to refactor this as follows:

Change this method to getPotentialGuardBlock, that returns the basic block that (potentially) guards the loop body.
I think you can determine the guard block using dominators and post-dominators. Specifically, the guard block should be the closest predecessor that dominates the loop preheader. And the "other" successor of the potential guard block should post-dominate all of the blocks inside the loop. I believe that should be sufficient to guarantee the block is a potential guard.

Then you can get the branch from the guard block in the getGuard method, and do the necessary analysis on the branch itself to verify it conforms with the requirements for a guard branch. Does this make sense?

423

Again, try to make it clear in the name what you are specifically getting - in this case the guard branch.

488

It's probably reasonable here to assert that Header and Latch are not nullptr.

llvm/unittests/Analysis/LoopInfoTest.cpp

756

These tests look good. I don't see any tests for the following - could you add some:

1. Loop Bounds and associated methods you have added
2. Unguarded loops (i.e., loops with constant upper bounds should not get a guard).
3. Loop nests
4. Functions with control flow that do not "guard" the loop.

[jdoerfert]

llvm/lib/Analysis/LoopInfo.cpp

418

And the "other" successor of the potential guard block should post-dominate all of the blocks inside the loop.

Not all blocks but just the header I think. That should allow multi-exit loops (if it matters).

I believe that should be sufficient to guarantee the block is a potential guard.

Agreed.

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

566

Tried this with doxygen, looks as expected.

llvm/lib/Analysis/LoopInfo.cpp

255

Can a basic block not have a terminator? I thought it must have one.

488

This will definitely be true, because it just checked that the loop is in isLoopSimplifyForm()..I can add asserts.

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

417

changed.

423

Added comment to clarify that.

598

I updated the comment again, hopefully is more clear this time.

656

an instruction is a value as well.

673

moved.

llvm/lib/Analysis/LoopInfo.cpp

230

That's not totally true, it returns the signed predicate for ne or eq which doesn't have a sign. Updated the comment to reflect that.

240

added.

348

Updated the comment.

355

done.

418

I changed the code to use the post dominator, but there is no need to use the dominator, as by finding the closest conditional branch, we know it dominates the loop.

423

done

[Whitney]

llvm/unittests/Analysis/LoopInfoTest.cpp

756

Added more test cases

[Whitney]

rebase

[kbarton]

I discussed this with @Whitney and I think at this point it makes sense to remove the getGuard and getPotentialGuard methods as there still seems to be some discussions about the right approach for that.
Aside from that, I think everything else looks pretty good, aside from some specific style-related comments.

llvm/include/llvm/Analysis/LoopInfo.h

572

a -> an

671

I think this condition needs to be reworded to:
The other successor post-dominates all nodes in the loop.

llvm/lib/Analysis/LoopInfo.cpp

255

From: http://llvm.org/doxygen/classllvm_1_1BasicBlock.html

A well formed basic block is formed of a list of non-terminating instructions followed by a single terminator instruction. Terminator instructions may not occur in the middle of basic blocks, and must terminate the blocks. The BasicBlock class allows malformed basic blocks to occur because it may be useful in the intermediate stage of constructing or modifying a program. However, the verifier will ensure that basic blocks are "well formed".

So, while I agree it is unlikely to happen, it is still possible, depending on when this is called wrt other optimizations.

294

From what I have seen, a more common way to write this method in LLVM-style would be:

if (SCEVAddRecExpr *StepAddRecExpr = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst()))) 
  if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
    if (SE.isKnownPositive(StepRecur))
      return Direction::Increasing;
    if (SE.isKnownNegative(StepRecur))
      return Direction::Decreasing;
  }
return Direction::Unknown;

That said, I don't know if this is explicitly documented anywhere.

311

Similarly, this is typically written as:

if (PHINode *IndVar = getInductionVariable(SE))
  return LoopBounds::getBounds(*this, *IndVar, SE);
return None;

528

Same as above. This can be rewritten by initializing IndVar in the if condition and then calling isInductionPHI.

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

294

I thought they prefer early exit. https://llvm.org/docs/CodingStandards.html#use-early-exits-and-continue-to-simplify-code

[kbarton]

Aside from a few minor comments, this LGTM.

llvm/include/llvm/Analysis/LoopInfo.h

534

Need to remove guard branch from the comments, as that is not included in this patch anymore.

llvm/lib/Analysis/LoopInfo.cpp

196

This should also be dyn_cast_or_null, since Latch->getTerminator() can return nullptr in some cases.

294

Yes, that's true. But that is dealing more with large bodies of code and/or complicated conditionals where many things need to be satisfied. I think the purpose of that is it is very hard to keep all of the logic straight in your head while reading the code, so separating out common conditions or early exits makes the code easier to read. These functions, on the other hand, are very small and do not have a lot of conditions or context that needs to be remembered.

I agree this is somewhat subjective, and I don't have a strong preference either way. However, after looking at a lot of code in LLVM, I find the more compact style easier to read for small functions.

[fhahn]

I still think there is some duplication with InductionDescriptor that could be unified, which would also make it easier to use this new utility in places that currently use InductionDescriptor.

Some comments inline, also InductionDescriptor already stores & provides accessors for InitialIVValue, StepValue (although just the SCEV/ConstantInt - is the generic value actually what you need?) and StepInst. With my earlier comment, I was going more in the direction of using IVDescriptor, instead of duplicating the fields here and using the existing functions to detect induction PHIs.

llvm/include/llvm/Analysis/LoopInfo.h

61

Unused?

635

This is basically the same as InductionDescriptor::getConsecutiveDirection

656

I am not sure what this means exactly. Do you have checks to exclude loops with multiple exit blocks?

Also, I am not sure what you intend on using this value for. Wouldn't it be less fragile to use SCEV to reason about the number of iterations? You can also evaluate the AddRec expression of the induction PHI at the final loop iteration.

llvm/lib/Analysis/LoopInfo.cpp

318

Isn't the main part of this function the same as InductionDescriptor::isInductionPHI() ? http://llvm.org/doxygen/classllvm_1_1InductionDescriptor.html#a1974b8e8a8bae482a772ebfab1e9c794

[fhahn]

llvm/lib/Analysis/LoopInfo.cpp

318

at leas conceptually

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

61

right, will remove.

635

I believe getConsecutiveDirection only work for constant step.

656

This is the focus on the loop latch as the exiting block.

llvm/lib/Analysis/LoopInfo.cpp

318

getInductionVariable() should return an induction phi, but an induction variable may not be a loop induction variable. A loop induction variable is used direct/indirectly in loop latch to determine if the loop continues.
I will look into if I can further simplify this function.

[Whitney]

@fhahn Thanks for your review. Do you think this is better now? Is there some areas you would like me to look into more?

[Whitney]

If there are no further comments or concerns, I will commit this patch on this Wed.

[fhahn]

In D60565#1527843, @Whitney wrote:

If there are no further comments or concerns, I will commit this patch on this Wed.

Sorry for holding this up, I'll try to take another look today.

[fhahn]

LGTM, thanks! Let's get this in and iterate on it as we get more places to use it.

llvm/include/llvm/Analysis/LoopInfo.h

 #include <algorithm>
 #include <utility>
 
 namespace llvm {
 
 class DominatorTree;
 class LoopInfo;
 class Loop;
+class InductionDescriptor;
 class MDNode;
 class MemorySSAUpdater;
 class PHINode;
+class ScalarEvolution;
 class raw_ostream;
 template <class N, bool IsPostDom> class DominatorTreeBase;
 template <class N, class M> class LoopInfoBase;
 template <class N, class M> class LoopBase;
 
 //===----------------------------------------------------------------------===//
 /// Instances of this class are used to represent loops that are detected in the
 /// flow graph.
#endif
 
   /// Verify loop structure
   void verifyLoop() const;
 
   /// Verify loop structure of this loop and all nested loops.
   void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;
 
   /// Returns true if the loop is annotated parallel.
   ///
   /// Derived classes can override this method using static template
   /// polymorphism.
   bool isAnnotatedParallel() const { return false; }
 
   /// Print loop with all the BBs inside it.
   void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const;
 
 protected:
   friend class LoopInfoBase<BlockT, LoopT>;
 
   /// This creates an empty loop.
   LoopBase() : ParentLoop(nullptr) {}
 
   explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
     Blocks.push_back(BB);
     DenseBlockSet.insert(BB);
   }
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.
+  ///
+  /// Here is an example:
+  /// \code
+  /// for (int i = lb; i < ub; i+=step)
+  ///   <loop body>
+  /// --- pseudo LLVMIR ---
+  /// beforeloop:
+  ///   guardcmp = (lb < ub)
+  ///   if (guardcmp) goto preheader; else goto afterloop
+  /// preheader:
+  /// loop:
+  ///   i_1 = phi[{lb, preheader}, {i_2, latch}]
+  ///   <loop body>
+  ///   i_2 = i_1 + step
+  /// latch:
+  ///   cmp = (i_2 < ub)
+  ///   if (cmp) goto loop
+  /// exit:
+  /// afterloop:
+  /// \endcode
+  ///
+  /// - getBounds
+  ///   - getInitialIVValue      --> lb
+  ///   - getStepInst            --> i_2 = i_1 + step
+  ///   - getStepValue           --> step
+  ///   - getFinalIVValue        --> ub
+  ///   - getCanonicalPredicate  --> '<'
+  ///   - getDirection           --> Increasing
+  ///
+  /// - getInductionVariable            --> i_1
+  /// - isAuxiliaryInductionVariable(x) --> true if x == i_1
+  /// - 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
+    ///
+    /// Else None.
+    static Optional<Loop::LoopBounds> getBounds(const Loop &L, PHINode &IndVar,
+                                                ScalarEvolution &SE);
+
+    /// Get the initial value of the loop induction variable.
+    Value &getInitialIVValue() const { return InitialIVValue; }
+
+    /// Get the instruction that updates the loop induction variable.
+    Instruction &getStepInst() const { return StepInst; }
+
+    /// Get the step that the loop induction variable gets updated by in each
+    /// loop iteration. Return nullptr if not found.
+    Value *getStepValue() const { return StepValue; }
+
+    /// Get the final value of the loop induction variable.
+    Value &getFinalIVValue() const { return FinalIVValue; }
+
+    /// Return the canonical predicate for the latch compare instruction, if
+    /// able to be calcuated. Else BAD_ICMP_PREDICATE.
+    ///
+    /// A predicate is considered as canonical if requirements below are all
+    /// satisfied:
+    /// 1. The first successor of the latch branch is the loop header
+    ///    If not, inverse the predicate.
+    /// 2. One of the operands of the latch comparison is StepInst
+    ///    If not, and
+    ///    - if the current calcuated predicate is not ne or eq, flip the
+    ///      predicate.
+    ///    - else if the loop is increasing, return slt
+    ///      (notice that it is safe to change from ne or eq to sign compare)
+    ///    - else if the loop is decreasing, return sgt
+    ///      (notice that it is safe to change from ne or eq to sign compare)
+    ///
+    /// Here is an example when both (1) and (2) are not satisfied:
+    /// \code
+    /// loop.header:
+    ///  %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header]
+    ///  %inc = add %iv, %step
+    ///  %cmp = slt %iv, %finaliv
+    ///  br %cmp, %loop.exit, %loop.header
+    /// loop.exit:
+    /// \endcode
+    /// - The second successor of the latch branch is the loop header instead
+    ///   of the first successor (slt -> sge)
+    /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv)
+    ///   instead of the StepInst (%inc) (sge -> sgt)
+    ///
+    /// The predicate would be sgt if both (1) and (2) are satisfied.
+    /// getCanonicalPredicate() returns sgt for this example.
+    /// Note: The IR is not changed.
+    ICmpInst::Predicate getCanonicalPredicate() const;
+
+    /// An enum for the direction of the loop
+    /// - for (int i = 0; i < ub; ++i)  --> Increasing
+    /// - for (int i = ub; i > 0; --i)  --> Descresing
+    /// - for (int i = x; i != y; i+=z) --> Unknown
+    enum class Direction { Increasing, Decreasing, Unknown };
+
+    /// Get the direction of the loop.
+    Direction getDirection() const;
+
+  private:
+    LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F,
+               ScalarEvolution &SE)
+        : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV),
+          FinalIVValue(F), SE(SE) {}
+
+    const Loop &L;
+
+    // The initial value of the loop induction variable
+    Value &InitialIVValue;
+
+    // The instruction that updates the loop induction variable
+    Instruction &StepInst;
+
+    // The value that the loop induction variable gets updated by in each loop
+    // iteration
+    Value *StepValue;
+
+    // The final value of the loop induction variable
+    Value &FinalIVValue;
+
+    ScalarEvolution &SE;
+  };
+
+  /// Return the struct LoopBounds collected if all struct members are found,
+  /// else None.
+  Optional<LoopBounds> getBounds(ScalarEvolution &SE) const;
+
+  /// Return the loop induction variable if found, else return nullptr.
+  /// An instruction is considered as the loop induction variable if
+  /// - it is an induction variable of the loop; and
+  /// - it is used to determine the condition of the branch in the loop latch
+  ///
+  /// Note: the induction variable doesn't need to be canonical, i.e. starts at
+  /// zero and increments by one each time through the loop (but it can be).
+  PHINode *getInductionVariable(ScalarEvolution &SE) const;
+
+  /// Get the loop induction descriptor for the loop induction variable. Return
+  /// true if the loop induction variable is found.
+  bool getInductionDescriptor(ScalarEvolution &SE,
+                              InductionDescriptor &IndDesc) const;
+
+  /// Return true if the given PHINode \p AuxIndVar is
+  /// - in the loop header
+  /// - 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 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.
   bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const;
 
   /// Return true if the Loop is in the form that the LoopSimplify form
   /// transforms loops to, which is sometimes called normal form.

llvm/lib/Analysis/LoopInfo.cpp

 // header node... not just a single natural loop.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/IVDescriptors.h"
 #include "llvm/Analysis/LoopInfoImpl.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/Instructions.h"
if (ConstantInt *CI =
           if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
             if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
               if (CI->isOne())
                 return PN;
   }
   return nullptr;
 }
 
+/// Get the latch condition instruction.
+static ICmpInst *getLatchCmpInst(const Loop &L) {
+  if (BasicBlock *Latch = L.getLoopLatch())
+    if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()))
+      if (BI->isConditional())
+        return dyn_cast<ICmpInst>(BI->getCondition());
+
+  return nullptr;
+}
+
+/// Return the final value of the loop induction variable if found.
+static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
+                               const Instruction &StepInst) {
+  ICmpInst *LatchCmpInst = getLatchCmpInst(L);
+  if (!LatchCmpInst)
+    return nullptr;
+
+  Value *Op0 = LatchCmpInst->getOperand(0);
+  Value *Op1 = LatchCmpInst->getOperand(1);
+  if (Op0 == &IndVar || Op0 == &StepInst)
+    return Op1;
+
+  if (Op1 == &IndVar || Op1 == &StepInst)
+    return Op0;
+
+  return nullptr;
+}
+
+Optional<Loop::LoopBounds> Loop::LoopBounds::getBounds(const Loop &L,
+                                                       PHINode &IndVar,
+                                                       ScalarEvolution &SE) {
+  InductionDescriptor IndDesc;
+  if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))
+    return None;
+
+  Value *InitialIVValue = IndDesc.getStartValue();
+  Instruction *StepInst = IndDesc.getInductionBinOp();
+  if (!InitialIVValue || !StepInst)
+    return None;
+
+  const SCEV *Step = IndDesc.getStep();
+  Value *StepInstOp1 = StepInst->getOperand(1);
+  Value *StepInstOp0 = StepInst->getOperand(0);
+  Value *StepValue = nullptr;
+  if (SE.getSCEV(StepInstOp1) == Step)
+    StepValue = StepInstOp1;
+  else if (SE.getSCEV(StepInstOp0) == Step)
+    StepValue = StepInstOp0;
+
+  Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst);
+  if (!FinalIVValue)
+    return None;
+
+  return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,
+                    SE);
+}
+
+using Direction = Loop::LoopBounds::Direction;
+
+ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const {
+  BasicBlock *Latch = L.getLoopLatch();
+  assert(Latch && "Expecting valid latch");
+
+  BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator());
+  assert(BI && BI->isConditional() && "Expecting conditional latch branch");
+
+  ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition());
+  assert(LatchCmpInst &&
+         "Expecting the latch compare instruction to be a CmpInst");
+
+  // Need to inverse the predicate when first successor is not the loop
+  // header
+  ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())
+                                 ? LatchCmpInst->getPredicate()
+                                 : LatchCmpInst->getInversePredicate();
+
+  if (LatchCmpInst->getOperand(0) == &getFinalIVValue())
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+
+  // Need to flip strictness of the predicate when the latch compare instruction
+  // is not using StepInst
+  if (LatchCmpInst->getOperand(0) == &getStepInst() ||
+      LatchCmpInst->getOperand(1) == &getStepInst())
+    return Pred;
+
+  // Cannot flip strictness of NE and EQ
+  if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
+    return ICmpInst::getFlippedStrictnessPredicate(Pred);
+
+  Direction D = getDirection();
+  if (D == Direction::Increasing)
+    return ICmpInst::ICMP_SLT;
+
+  if (D == Direction::Decreasing)
+    return ICmpInst::ICMP_SGT;
+
+  // If cannot determine the direction, then unable to find the canonical
+  // predicate
+  return ICmpInst::BAD_ICMP_PREDICATE;
+}
+
+Direction Loop::LoopBounds::getDirection() const {
+  if (const SCEVAddRecExpr *StepAddRecExpr =
+          dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst())))
+    if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
+      if (SE.isKnownPositive(StepRecur))
+        return Direction::Increasing;
+      if (SE.isKnownNegative(StepRecur))
+        return Direction::Decreasing;
+    }
+
+  return Direction::Unknown;
+}
+
+Optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
+  if (PHINode *IndVar = getInductionVariable(SE))
+    return LoopBounds::getBounds(*this, *IndVar, SE);
+
+  return None;
+}
+
+PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const {
+  if (!isLoopSimplifyForm())
+    return nullptr;
+
+  BasicBlock *Header = getHeader();
+  assert(Header && "Expected a valid loop header");
+  BasicBlock *Latch = getLoopLatch();
+  assert(Latch && "Expected a valid loop latch");
+  ICmpInst *CmpInst = getLatchCmpInst(*this);
+  if (!CmpInst)
+    return nullptr;
+
+  Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
+  Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1));
+
+  for (PHINode &IndVar : Header->phis()) {
+    InductionDescriptor IndDesc;
+    if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc))
+      continue;
+
+    Instruction *StepInst = IndDesc.getInductionBinOp();
+
+    // case 1:
+    // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
+    // StepInst = IndVar + step
+    // cmp = StepInst < FinalValue
+    if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
+      return &IndVar;
+
+    // case 2:
+    // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
+    // StepInst = IndVar + step
+    // cmp = IndVar < FinalValue
+    if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
+      return &IndVar;
+  }
+
+  return nullptr;
+}
+
+bool Loop::getInductionDescriptor(ScalarEvolution &SE,
+                                  InductionDescriptor &IndDesc) const {
+  if (PHINode *IndVar = getInductionVariable(SE))
+    return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
+
+  return false;
+}
+
+bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
+                                        ScalarEvolution &SE) const {
+  // Located in the loop header
+  BasicBlock *Header = getHeader();
+  if (AuxIndVar.getParent() != Header)
+    return false;
+
+  // No uses outside of the loop
+  for (User *U : AuxIndVar.users())
+    if (const Instruction *I = dyn_cast<Instruction>(U))
+      if (!contains(I))
+        return false;
+
+  InductionDescriptor IndDesc;
+  if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
+    return false;
+
+  // The step instruction opcode should be add or sub.
+  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);
+}
+
+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;
+
+  if (IndDesc.getInductionOpcode() != Instruction::Add)
+    return false;
+
+  ConstantInt *Step = IndDesc.getConstIntStepValue();
+  if (!Step || !Step->isOne())
+    return false;
+
+  return true;
+}
+
 // Check that 'BB' doesn't have any uses outside of the 'L'
 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
                                DominatorTree &DT) {
   for (const Instruction &I : BB) {
     // Tokens can't be used in PHI nodes and live-out tokens prevent loop
     // optimizations, so for the purposes of considered LCSSA form, we
     // can ignore them.
     if (I.getType()->isTokenTy())
       continue;
 
     for (const Use &U : I.uses()) {
       const Instruction *UI = cast<Instruction>(U.getUser());
       const BasicBlock *UserBB = UI->getParent();
       if (const PHINode *P = dyn_cast<PHINode>(UI))
         UserBB = P->getIncomingBlock(U);
 
       // Check the current block, as a fast-path, before checking whether
       // the use is anywhere in the loop.  Most values are used in the same
       // block they are defined in.  Also, blocks not reachable from the
       // entry are special; uses in them don't need to go through PHIs.
       if (UserBB != &BB && !L.contains(UserBB) &&
           DT.isReachableFromEntry(UserBB))
         return false;
     }
   }
   return true;
 }
 
 bool Loop::isLCSSAForm(DominatorTree &DT) const {
   // For each block we check that it doesn't have any uses outside of this loop.
   return all_of(this->blocks(), [&](const BasicBlock *BB) {
     return isBlockInLCSSAForm(*this, *BB, DT);
   });
 }
 
 bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const {
   // For each block we check that it doesn't have any uses outside of its
   // innermost loop. This process will transitively guarantee that the current
   // loop and all of the nested loops are in LCSSA form.
   return all_of(this->blocks(), [&](const BasicBlock *BB) {
     return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
   });
 }
 
 bool Loop::isLoopSimplifyForm() const {
   // Normal-form loops have a preheader, a single backedge, and all of their
   // exits have all their predecessors inside the loop.
   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
 }
 
 // Routines that reform the loop CFG and split edges often fail on indirectbr.

 MDNode *Loop::getLoopID() const {
   MDNode *LoopID = nullptr;
 
   // Go through the latch blocks and check the terminator for the metadata.
   SmallVector<BasicBlock *, 4> LatchesBlocks;
   getLoopLatches(LatchesBlocks);
   for (BasicBlock *BB : LatchesBlocks) {
     Instruction *TI = BB->getTerminator();
     MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
 
     if (!MD)
       return nullptr;
 
     if (!LoopID)
       LoopID = MD;
     else if (MD != LoopID)
       return nullptr;
   }
   if (!LoopID || LoopID->getNumOperands() == 0 ||
       LoopID->getOperand(0) != LoopID)
     return nullptr;
   return LoopID;
 }
 
 void Loop::setLoopID(MDNode *LoopID) const {
   assert((!LoopID || LoopID->getNumOperands() > 0) &&
          "Loop ID needs at least one operand");
   assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
          "Loop ID should refer to itself");
 
   SmallVector<BasicBlock *, 4> LoopLatches;
   getLoopLatches(LoopLatches);
   for (BasicBlock *BB : LoopLatches)
     BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
 }
 
 void Loop::setLoopAlreadyUnrolled() {
   LLVMContext &Context = getHeader()->getContext();
 
   MDNode *DisableUnrollMD =
       MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
   MDNode *LoopID = getLoopID();
   MDNode *NewLoopID = makePostTransformationMetadata(
       Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
   setLoopID(NewLoopID);
 }
 
 bool Loop::isAnnotatedParallel() const {
bool Loop::isAnnotatedParallel() const {
   // is parallel to this loop.
   for (BasicBlock *BB : this->blocks()) {
     for (Instruction &I : *BB) {
       if (!I.mayReadOrWriteMemory())
         continue;
 
       if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
         auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
           if (AG->getNumOperands() == 0) {
             assert(isValidAsAccessGroup(AG) && "Item must be an access group");
             return ParallelAccessGroups.count(AG);
           }
 
           for (const MDOperand &AccessListItem : AG->operands()) {
             MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
             assert(isValidAsAccessGroup(AccGroup) &&
                    "List item must be an access group");
             if (ParallelAccessGroups.count(AccGroup))

 };
 } // end anonymous namespace
 
 /// Update the parent loop for all blocks that are directly contained within the
 /// original "unloop".
 void UnloopUpdater::updateBlockParents() {
   if (Unloop.getNumBlocks()) {
     // Perform a post order CFG traversal of all blocks within this loop,
     // propagating the nearest loop from successors to predecessors.
     LoopBlocksTraversal Traversal(DFS, LI);
     for (BasicBlock *POI : Traversal) {
 
       Loop *L = LI->getLoopFor(POI);
       Loop *NL = getNearestLoop(POI, L);
 
       if (NL != L) {
         // For reducible loops, NL is now an ancestor of Unloop.
         assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
                "uninitialized successor");
         LI->changeLoopFor(POI, NL);
       } else {
         // Or the current block is part of a subloop, in which case its parent
         // is unchanged.
         assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
       }
     }
   }
   // Each irreducible loop within the unloop induces a round of iteration using
   // the DFS result cached by Traversal.
   bool Changed = FoundIB;
   for (unsigned NIters = 0; Changed; ++NIters) {
     assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
 
     // Iterate over the postorder list of blocks, propagating the nearest loop

llvm/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) {
+  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);
+}
+
 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
                                               const char *ModuleStr) {
   SMDiagnostic Err;
   return parseAssemblyString(ModuleStr, Err, Context);
 }
 
 // This tests that for a loop with a single latch, we get the loop id from
 // its only latch, even in case the loop may not be in a simplified form.
TEST(LoopInfoTest, PreorderTraversals) {
   EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]);
   EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]);
   EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]);
   EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]);
   EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]);
   EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]);
   EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]);
 }
+
+TEST(LoopInfoTest, CanonicalLoop) {
+  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"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, LoopWithInverseGuardSuccs) {
+  const char *ModuleStr =
+      "define void @foo(i32* %A, i32 %ub) {\n"
+      "entry:\n"
+      "  %guardcmp = icmp sge i32 0, %ub\n"
+      "  br i1 %guardcmp, label %for.end, label %for.preheader\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, LoopWithSwappedGuardCmp) {
+  const char *ModuleStr =
+      "define void @foo(i32* %A, i32 %ub) {\n"
+      "entry:\n"
+      "  %guardcmp = icmp sgt i32 %ub, 0\n"
+      "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp sge i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.exit, label %for.body\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, LoopWithInverseLatchSuccs) {
+  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"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp sge i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.exit, label %for.body\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, LoopWithLatchCmpNE) {
+  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"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp ne i32 %i, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, LoopWithGuardCmpSLE) {
+  const char *ModuleStr =
+      "define void @foo(i32* %A, i32 %ub) {\n"
+      "entry:\n"
+      "  %ubPlusOne = add i32 %ub, 1\n"
+      "  %guardcmp = icmp sle i32 0, %ub\n"
+      "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp ne i32 %i, %ubPlusOne\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+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"
+      "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = zext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, %step\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, LoopUnsignedBounds) {
+  const char *ModuleStr =
+      "define void @foo(i32* %A, i32 %ub) {\n"
+      "entry:\n"
+      "  %guardcmp = icmp ult i32 0, %ub\n"
+      "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = zext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add i32 %i, 1\n"
+      "  %cmp = icmp ult i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, DecreasingLoop) {
+  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"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ %ub, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = sub nsw i32 %i, 1\n"
+      "  %cmp = icmp sgt i32 %inc, 0\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+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"
+      "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, %step\n"
+      "  %cmp = icmp ne i32 %i, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+                        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");
+                      });
+}
+
+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"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %for.body ]\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %wide.trip.count = zext i32 %ub to i64\n"
+      "  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n"
+      "  br i1 %exitcond, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, UnguardedLoop) {
+  const char *ModuleStr =
+      "define void @foo(i32* %A, i32 %ub) {\n"
+      "entry:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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 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");
+      });
+}
+
+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"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+      });
+}
+
+TEST(LoopInfoTest, LoopNest) {
+  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.outer.preheader, label %for.end\n"
+      "for.outer.preheader:\n"
+      "  br label %for.outer\n"
+      "for.outer:\n"
+      "  %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n"
+      "  br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n"
+      "for.inner.preheader:\n"
+      "  br label %for.inner\n"
+      "for.inner:\n"
+      "  %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.inner, label %for.inner.exit\n"
+      "for.inner.exit:\n"
+      "  br label %for.outer.latch\n"
+      "for.outer.latch:\n"
+      "  %inc.outer = add nsw i32 %j, 1\n"
+      "  %cmp.outer = icmp slt i32 %inc.outer, %ub\n"
+      "  br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n"
+      "for.outer.exit:\n"
+      "  br label %for.end\n"
+      "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.outer.preheader - skip them.
+        ++FI;
+        BasicBlock *Header = &*(++FI);
+        assert(Header->getName() == "for.outer");
+        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");
+
+        // 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");
+      });
+}
+
+TEST(LoopInfoTest, AuxiliaryIV) {
+  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"
+      "for.preheader:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
+      "  %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n"
+      "  %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n"
+      "  %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n"
+      "  %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n"
+      "  %idxprom = sext i32 %i to i64\n"
+      "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
+      "  store i32 %i, i32* %arrayidx, align 4\n"
+      "  %mulopcodeinc = mul nsw i32 %mulopcode, 5\n"
+      "  %usedoutsideinc = add nsw i32 %usedoutside, 5\n"
+      "  %loopvariantinc = add nsw i32 %loopvariant, %i\n"
+      "  %auxinc = add nsw i32 %aux, 5\n"
+      "  %inc = add nsw i32 %i, 1\n"
+      "  %cmp = icmp slt i32 %inc, %ub\n"
+      "  br i1 %cmp, label %for.body, label %for.exit\n"
+      "for.exit:\n"
+      "  %lcssa = phi i32 [ %usedoutside, %for.body ]\n"
+      "  br label %for.end\n"
+      "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);
+
+        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");
+        BasicBlock::iterator II = Header->begin();
+        PHINode &Instruction_i = cast<PHINode>(*(II));
+        EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE));
+        PHINode &Instruction_aux = cast<PHINode>(*(++II));
+        EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE));
+        PHINode &Instruction_loopvariant = cast<PHINode>(*(++II));
+        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));
+      });
+}