[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

578

Maybe mention how one is supposed to determine this precondition.

600

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.

603

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.

607

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

634

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

641

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

647

else "None".

655

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

674

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

llvm/lib/Analysis/IVDescriptors.cpp

1057

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

192

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

218

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

222

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?

255

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

265

[IMPORTANT] How do we know or enforce this?

286

-"where"
+"if"

288

"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."

304

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.

316

if (!GuardBB) return nullptr

317

GuardBI is overwritten before used.

334

The comment is outdated (ExitBlock)

338

We often use the pattern:

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

354

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.

357

I'm always for newlines to mark control condition changes

358

This is the general version (see above) again.

367

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

[Whitney]

llvm/include/llvm/Analysis/IVDescriptors.h

319

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

same as above

llvm/include/llvm/Analysis/LoopInfo.h

578

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?

603

It is enforced by getCmpInst().

607

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.

655

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

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

192

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

218

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.

222

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.

354

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)

358

see above reply.

367

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

592

"which update" -> "that updates"

594

instrucion -> instruction

598

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

600

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).

603

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

607

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?

621

Can IndVar be made const?

624

"which update" -> "that updates"

625

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?

629

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

635

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

653

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.

654

"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.

656

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).

665

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?

666

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.

669

varaible -> variable

677

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.

679

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

224

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

224

Do you handle the ULE/SLE case anywhere?

287

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

329

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.

368

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.

373

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?

451

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

466

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

469

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?

521

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

llvm/unittests/Analysis/LoopInfoTest.cpp

33

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

[jdoerfert]

llvm/include/llvm/Analysis/IVDescriptors.h

319

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

llvm/include/llvm/Analysis/LoopInfo.h

578

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.

603

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

607

OK.

llvm/lib/Analysis/IVDescriptors.cpp

1057

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

192

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

218

Probably/Hopefully, correct.

354

You are obviously right here, ...

I should not do code reviews at night...

367

No strong feeling, keep it.

373

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

[Whitney]

llvm/include/llvm/Analysis/IVDescriptors.h

319

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

llvm/include/llvm/Analysis/LoopInfo.h

607

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.

653

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.

654

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.

656

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

665

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

677

Right, that's the intensional behaviour

679

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

llvm/lib/Analysis/LoopInfo.cpp

224

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.

287

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

329

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

368

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

373

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.

469

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

33

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

621

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

llvm/lib/Analysis/LoopInfo.cpp

288

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

416

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.

422

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.

575

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.

607

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?

665

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.

682

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

llvm/lib/Analysis/LoopInfo.cpp

224

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?

234

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?

249

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

342

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.

349

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

412

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?

417

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

482

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

llvm/unittests/Analysis/LoopInfoTest.cpp

752

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

412

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

575

Tried this with doxygen, looks as expected.

llvm/lib/Analysis/LoopInfo.cpp

249

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

482

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

416

changed.

422

Added comment to clarify that.

607

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

665

an instruction is a value as well.

682

moved.

llvm/lib/Analysis/LoopInfo.cpp

224

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.

234

added.

342

Updated the comment.

349

done.

412

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.

417

done

[Whitney]

llvm/unittests/Analysis/LoopInfoTest.cpp

752

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

581

a -> an

680

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

llvm/lib/Analysis/LoopInfo.cpp

249

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.

288

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.

305

Similarly, this is typically written as:

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

522

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

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

288

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

543

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

llvm/lib/Analysis/LoopInfo.cpp

190

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

288

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

60

Unused?

644

This is basically the same as InductionDescriptor::getConsecutiveDirection

665

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

312

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

312

at leas conceptually

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

60

right, will remove.

644

I believe getConsecutiveDirection only work for constant step.

665

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

llvm/lib/Analysis/LoopInfo.cpp

312

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/IVDescriptors.h

public:
   static bool isInductionPHI(PHINode *Phi, const Loop *L,
                              PredicatedScalarEvolution &PSE,
                              InductionDescriptor &D, bool Assume = false);
 
   /// Returns true if the induction type is FP and the binary operator does
   /// not have the "fast-math" property. Such operation requires a relaxed FP
   /// mode.
   bool hasUnsafeAlgebra() {
-    return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
+    return IK == IK_FpInduction && InductionBinOp &&
+           !cast<FPMathOperator>(InductionBinOp)->isFast();
   }
 
   /// Returns induction operator that does not have "fast-math" property
   /// and requires FP unsafe mode.
   Instruction *getUnsafeAlgebraInst() {
+    if (IK != IK_FpInduction)
+      return nullptr;
+
     if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
       return nullptr;
     return InductionBinOp;
   }
 
   /// Returns binary opcode of the induction operator.
   Instruction::BinaryOps getInductionOpcode() const {
     return InductionBinOp ? InductionBinOp->getOpcode()

llvm/include/llvm/Analysis/LoopInfo.h

 #include <algorithm>
 #include <utility>
 
 namespace llvm {
 
 class DominatorTree;
 class LoopInfo;
 class Loop;
+class InductionDescriptor;
 class MDNode;
 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 the guard branch of the loop if found.
+  ///
+  /// Derived classes can override this method using static template
+  /// polymorphism.
+  BranchInst *getGuard(ScalarEvolution &SE) const { return nullptr; }
+
+  /// Returns the induction variable of the loop if found.
+  ///
+  /// Derived classes can override this method using static template
+  /// polymorphism.
+  PHINode *getInductionVariable(ScalarEvolution &SE) const { return nullptr; }
+
   /// 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;
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, guard branch, 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
+  /// getGuard             --> if (guardcmp) goto loop; else goto afterloop
+  /// getInductionVariable          --> i_1
+  /// isAuxiliaryInductionVariable(x) --> true if x == i_1
+  /// isCanonical                   --> false
+  struct LoopBounds {
+    /// Return the LoopBounds object if
+    /// - the given \p IndVar is a 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.
+    Value *getStepValue() const { return StepValue; }
+
+    /// Get the final value of the loop induction variable.
+    Value &getFinalIVValue() const { return FinalIVValue; }
+
+    /// Return the predicate for the latch comparison when
+    /// - the first successor of the latch branch is the loop header
+    /// - the first operand of the latch comparison is StepInst
+    /// Example:
+    /// \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
+    /// 1. The second successor of the latch branch is the loop header instead
+    ///    of the first successor (slt -> sge)
+    /// 2. The operand(0) of the latch comparison (%cmp) is the IndVar (%iv)
+    ///    instead of the StepInst (%inc) (sge -> sgt)
+    /// getCanonicalPredicate() --> sgt
+    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 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 guard branch if exists, else return nullptr.
+  /// A branch instruction is considered as a guard if
+  /// - it is the closest conditional branch before the loop
+  /// - one successor dominates the loop preheader
+  /// - a loop exit block dominates the other successor
+  /// - the condition is to verify the loop initial induction variable value
+  ///   satisfy the latch condition (i.e. the loop body should be executed at
+  ///   least once)
+  BranchInst *getGuard(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
+  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/IVDescriptors.cpp

if (AR->getLoop() != TheLoop) {
     // don't currently know how to handled uniform PHIs.
     LLVM_DEBUG(
         dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
     return false;
   }
 
   Value *StartValue =
       Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
+
+  BasicBlock *Latch = AR->getLoop()->getLoopLatch();
+  if (!Latch)
+    return false;
+  BinaryOperator *BOp =
+      dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));
+
   const SCEV *Step = AR->getStepRecurrence(*SE);
   // Calculate the pointer stride and check if it is consecutive.
   // The stride may be a constant or a loop invariant integer value.
   const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
   if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
     return false;
 
   if (PhiTy->isIntegerTy()) {
-    D = InductionDescriptor(StartValue, IK_IntInduction, Step, /*BOp=*/nullptr,
+    D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp,
                             CastsToIgnore);
     return true;
   }
 
   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");
   // Pointer induction should be a constant.
   if (!ConstStep)
     return false;
bool InductionDescriptor::isInductionPHI(
   if (!Size)
     return false;
 
   int64_t CVSize = CV->getSExtValue();
   if (CVSize % Size)
     return false;
   auto *StepValue =
       SE->getConstant(CV->getType(), CVSize / Size, true /* signed */);
-  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
+  D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp);
   return true;
 }

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/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;
 }
 
+/// Return true if V1 and V2 have the same value ignoring bit width.
+static bool isEqualIgnoreBitwidth(Value &V1, Value &V2, ScalarEvolution &SE) {
+  const SCEV *S1 = SE.getSCEV(&V1);
+  const SCEV *S2 = SE.getSCEV(&V2);
+  Type *WiderType = SE.getWiderType(S1->getType(), S2->getType());
+  S1 = SE.getNoopOrAnyExtend(S1, WiderType);
+  S2 = SE.getNoopOrAnyExtend(S2, WiderType);
+  return SE.getMinusSCEV(S1, S2)->isZero();
+}
+
+/// Return true if V1 == V2 + 1 ignoring bit width.
+static bool diffOneIgnoreBitwidth(Value &V1, Value &V2, ScalarEvolution &SE) {
+  const SCEV *S1 = SE.getSCEV(&V1);
+  const SCEV *S2 = SE.getSCEV(&V2);
+  Type *WiderType = SE.getWiderType(S1->getType(), S2->getType());
+  S1 = SE.getNoopOrAnyExtend(S1, WiderType);
+  S2 = SE.getNoopOrAnyExtend(S2, WiderType);
+  return SE.getMinusSCEV(S1, S2)->isOne();
+}
+
+/// Get the latch condition instruction.
+static ICmpInst *getLatchCmpInst(const Loop &L) {
+  BasicBlock *Latch = L.getLoopLatch();
+  if (!Latch)
+    return nullptr;
+
+  BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
+  if (!BI || !BI->isConditional())
+    return nullptr;
+
+  return dyn_cast<ICmpInst>(BI->getCondition());
+}
+
+/// 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<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 {
+  const SCEVAddRecExpr *StepAddRecExpr =
+      dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst()));
+
+  if (!StepAddRecExpr)
+    return Direction::Unknown;
+
+  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 {
+  PHINode *IndVar = getInductionVariable(SE);
+  if (!IndVar)
+    return None;
+
+  return LoopBounds::getBounds(*this, *IndVar, SE);
+}
+
+/// This is a helper function called by getGuard(). It searches backward from
+/// the loop preheader to find the first basic block that has a conditional
+/// branch. As the branch instruction is conditional, it should have two
+/// successors. Because it is the first basic block with conditional branch
+/// searched backward from the loop preheader, we know that one of the two
+/// successors dominates the loop preheader. If we can verify that a loop exit
+/// block of the same loop dominates the other successor, then it means the
+/// condition of the conditional branch is used to determine if that loop is
+/// being executed.
+///
+/// Return the closest conditional branch before loop L, if
+/// one successor dominates the loop preheader,
+/// and a loop exit block dominates the other successor.
+/// Example:
+/// \code
+/// 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
+///
+/// getPotentialGuard --> if (guardcmp) goto preheader; else goto afterloop
+/// GuardBB --> beforeloop, Succ --> preheader
+/// SkipIndex --> 1, SkipToBlock --> afterloop
+///    - beforeloop has two successor, preheader and afterloop
+///    - preheader dominates preheader
+///    - exit dominates afterloop
+static BranchInst *getPotentialGuard(const Loop &L,
+                                     ICmpInst::Predicate &GuardPred) {
+  // Initialize GuardBB with the loop preheader and GuardBI with the branch in
+  // the loop preheader.
+  BasicBlock *GuardBB = L.getLoopPreheader();
+  if (!GuardBB)
+    return nullptr;
+
+  // Search backward from preheader to find a basic block which has conditional
+  // branch. Notice that loop preheader branch is definitely not conditional.
+
+  // Succ: the successor of GuardBB which 'flows' into the loop preheader
+  BasicBlock *Succ = nullptr;
+  BranchInst *GuardBI = nullptr;
+  SmallPtrSet<BasicBlock *, 4> Visited;
+  do {
+    Succ = GuardBB;
+    GuardBB = GuardBB->getUniquePredecessor();
+    if (!GuardBB)
+      return nullptr;
+
+    // A Visited set is needed to records blocks already visited, to avoid
+    // infinite loop when GuardBB single successor loops back to itself.
+    if (!Visited.insert(GuardBB).second)
+      return nullptr;
+
+    GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
+  } while (GuardBI && !GuardBI->isConditional());
+
+  if (!GuardBI || !GuardBI->isConditional())
+    return nullptr;
+
+  assert(GuardBI->getNumSuccessors() == 2 &&
+         "Expecting potential guard branch instruction to have 2 successors");
+
+  // Now we have the first conditional branch before loop L, we need to check if
+  // the other successor 'flows' from a loop exit block, i.e. skipping the loop.
+
+  // Get the successor index of GuardBI which may skip the loop L, i.e. the
+  // index of the successor which is not Succ.
+  unsigned SkipIndex = (GuardBI->getSuccessor(0) == Succ) ? 1 : 0;
+  assert((SkipIndex == 1 || GuardBI->getSuccessor(1) == Succ) &&
+         "Expecting one of GuardBI successor to be Succ");
+  ICmpInst *Cond = dyn_cast<ICmpInst>(GuardBI->getCondition());
+  if (!Cond)
+    return nullptr;
+
+  GuardPred =
+      (SkipIndex == 1) ? Cond->getPredicate() : Cond->getInversePredicate();
+  BasicBlock *SkipToBlock = GuardBI->getSuccessor(SkipIndex);
+
+  SmallVector<BasicBlock *, 8> ExitBlocks;
+  L.getUniqueExitBlocks(ExitBlocks);
+  for (BasicBlock *ExitBlock : ExitBlocks) {
+    // A Visited set is needed to records blocks already visited, to avoid
+    // infinite loop when ExitBlock unique successor loops back to itself.
+    SmallPtrSet<BasicBlock *, 4> Visited;
+    while (ExitBlock && ExitBlock != SkipToBlock &&
+           Visited.insert(ExitBlock).second) {
+      ExitBlock = ExitBlock->getUniqueSuccessor();
+    }
+    if (ExitBlock == SkipToBlock)
+      return GuardBI;
+  }
+
+  return nullptr;
+}
+
+BranchInst *Loop::getGuard(ScalarEvolution &SE) const {
+  if (!isLoopSimplifyForm())
+    return nullptr;
+
+  ICmpInst::Predicate GuardPred;
+  BranchInst *Guard = getPotentialGuard(*this, GuardPred);
+  if (!Guard)
+    return nullptr;
+
+  ICmpInst *Cond = dyn_cast<ICmpInst>(Guard->getCondition());
+  if (!Cond)
+    return nullptr;
+
+  const Optional<LoopBounds> Bound = getBounds(SE);
+  if (!Bound)
+    return nullptr;
+
+  Value &LatchInitialValue = Bound->getInitialIVValue();
+  Value &LatchFinalValue = Bound->getFinalIVValue();
+  ICmpInst::Predicate LatchPred = Bound->getCanonicalPredicate();
+  if (LatchPred == ICmpInst::BAD_ICMP_PREDICATE)
+    return nullptr;
+
+  LatchPred = ICmpInst::getSignedPredicate(LatchPred);
+
+  Value *GuardInitialValue = Cond->getOperand(0);
+  Value *GuardFinalValue = Cond->getOperand(1);
+  if (isEqualIgnoreBitwidth(*Cond->getOperand(1), LatchInitialValue, SE)) {
+    GuardPred = ICmpInst::getSwappedPredicate(GuardPred);
+    GuardInitialValue = Cond->getOperand(1);
+    GuardFinalValue = Cond->getOperand(0);
+  }
+  GuardPred = ICmpInst::getSignedPredicate(GuardPred);
+
+  if (LatchPred != GuardPred && LatchPred == ICmpInst::ICMP_NE) {
+    if (Bound->getDirection() == LoopBounds::Direction::Increasing)
+      LatchPred = ICmpInst::ICMP_SLT;
+    else if (Bound->getDirection() == LoopBounds::Direction::Decreasing)
+      LatchPred = ICmpInst::ICMP_SGT;
+  }
+
+  if (!isEqualIgnoreBitwidth(*GuardInitialValue, LatchInitialValue, SE))
+    return nullptr;
+
+  if (isEqualIgnoreBitwidth(*GuardFinalValue, LatchFinalValue, SE) &&
+      GuardPred == LatchPred)
+    return Guard;
+
+  // Instruction combine transforms '<=' and '>=' to '<' and '>' respectively,
+  // which may cause the GuardPred and LatchPred to be different.
+  // 'lb < ub + 1' iff 'lb <= ub' and 'ub > lb' iff 'ub >= lb + 1'.
+  if ((GuardPred == ICmpInst::ICMP_SLE && LatchPred == ICmpInst::ICMP_SLT &&
+       diffOneIgnoreBitwidth(LatchFinalValue, *GuardFinalValue, SE)) ||
+      (GuardPred == ICmpInst::ICMP_SGE && LatchPred == ICmpInst::ICMP_SGT &&
+       diffOneIgnoreBitwidth(*GuardFinalValue, LatchFinalValue, SE)))
+    return Guard;
+
+  return nullptr;
+}
+
+PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const {
+  if (!isLoopSimplifyForm())
+    return nullptr;
+
+  BasicBlock *Header = getHeader();
+  BasicBlock *Latch = getLoopLatch();
+  ICmpInst *CmpInst = getLatchCmpInst(*this);
+  if (!CmpInst)
+    return nullptr;
+
+  // case 1:
+  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
+  // StepInst = IndVar + step
+  // cmp = StepInst < FinalValue
+  Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
+  Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1));
+  // Loop over all of the PHI nodes in loop header, store the PHI node that has
+  // incoming value from latch equals to the StepInst
+  Instruction *StepInst = nullptr;
+  PHINode *IndVar = nullptr;
+  for (PHINode &PN : Header->phis()) {
+    Value *IncomingValue = PN.getIncomingValueForBlock(Latch);
+    assert(IncomingValue && "Expecting valid incoming value from latch");
+    if (IncomingValue == LatchCmpOp0 || IncomingValue == LatchCmpOp1) {
+      IndVar = &PN;
+      StepInst = dyn_cast<Instruction>(IncomingValue);
+      break;
+    }
+  }
+  if (IndVar)
+    if (isEqualIgnoreBitwidth(*StepInst->getOperand(0), *IndVar, SE) ||
+        isEqualIgnoreBitwidth(*StepInst->getOperand(1), *IndVar, SE))
+      return IndVar;
+
+  // case 2:
+  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
+  // StepInst = IndVar + step
+  // cmp = IndVar < FinalValue
+  for (Value *Op : CmpInst->operands()) {
+    PHINode *IndVar = dyn_cast<PHINode>(Op);
+    if (!IndVar)
+      continue;
+
+    if (IndVar->getParent() != Header)
+      continue;
+
+    Value *IncomingValue = IndVar->getIncomingValueForBlock(Latch);
+    assert(IncomingValue && "Expecting valid incoming value from latch");
+    StepInst = dyn_cast<Instruction>(IncomingValue);
+    if (StepInst)
+      if (StepInst->getOperand(0) == IndVar ||
+          StepInst->getOperand(1) == IndVar)
+        return IndVar;
+  }
+
+  return nullptr;
+}
+
+bool Loop::getInductionDescriptor(ScalarEvolution &SE,
+                                  InductionDescriptor &IndDesc) const {
+  PHINode *IndVar = getInductionVariable(SE);
+  if (!IndVar)
+    return false;
+
+  return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
+}
+
+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())
for (BasicBlock *BB : this->blocks()) {
     if (isa<IndirectBrInst>(BB->getTerminator()))
       return false;
 
     for (Instruction &I : *BB)
       if (auto CS = CallSite(&I))
         if (CS.cannotDuplicate())
           return false;
   }
   return true;
 }
 
 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;
 }

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

while (!Vec->empty()) {
     LoopList.push_back(CurrentLoop);
     CurrentLoop = Vec->front();
     Vec = &CurrentLoop->getSubLoops();
   }
   LoopList.push_back(CurrentLoop);
   return LoopList;
 }
 
-static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
-  PHINode *InnerIndexVar = L->getCanonicalInductionVariable();
-  if (InnerIndexVar)
-    return InnerIndexVar;
-  if (L->getLoopLatch() == nullptr || L->getLoopPredecessor() == nullptr)
-    return nullptr;
-  for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
-    PHINode *PhiVar = cast<PHINode>(I);
-    Type *PhiTy = PhiVar->getType();
-    if (!PhiTy->isIntegerTy() && !PhiTy->isFloatingPointTy() &&
-        !PhiTy->isPointerTy())
-      return nullptr;
-    const SCEVAddRecExpr *AddRec =
-        dyn_cast<SCEVAddRecExpr>(SE->getSCEV(PhiVar));
-    if (!AddRec || !AddRec->isAffine())
-      continue;
-    const SCEV *Step = AddRec->getStepRecurrence(*SE);
-    if (!isa<SCEVConstant>(Step))
-      continue;
-    // Found the induction variable.
-    // FIXME: Handle loops with more than one induction variable. Note that,
-    // currently, legality makes sure we have only one induction variable.
-    return PhiVar;
-  }
-  return nullptr;
-}
-
 namespace {
 
 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
 class LoopInterchangeLegality {
 public:
   LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                           OptimizationRemarkEmitter *ORE)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}

 
 bool LoopInterchangeTransform::transform() {
   bool Transformed = false;
   Instruction *InnerIndexVar;
 
   if (InnerLoop->getSubLoops().empty()) {
     BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
     LLVM_DEBUG(dbgs() << "Calling Split Inner Loop\n");
-    PHINode *InductionPHI = getInductionVariable(InnerLoop, SE);
+    PHINode *InductionPHI = InnerLoop->getInductionVariable(*SE);
     if (!InductionPHI) {
       LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
       return false;
     }
 
     if (InductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
       InnerIndexVar = dyn_cast<Instruction>(InductionPHI->getIncomingValue(1));
     else

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/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 runWithLoopInfoAndSE(
+    Module &M, StringRef FuncName,
+    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);
+
+  Test(*F, LI, SE);
+}
+
 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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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);
+
+  runWithLoopInfoAndSE(*M, "foo",
+                       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+                         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);
+
+                         EXPECT_EQ(L->getGuard(SE), nullptr);
+                         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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv");
+      });
+}
+
+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);
+
+  runWithLoopInfoAndSE(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        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);
+
+        EXPECT_EQ(L->getGuard(SE)->getParent()->getName(), "entry");
+        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));
+      });
+}