[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

576

Maybe mention how one is supposed to determine this precondition.

598

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.

601

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.

605

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

632

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

639

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

645

else "None".

653

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

672

"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

193

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

219

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

223

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?

256

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

266

[IMPORTANT] How do we know or enforce this?

287

-"where"
+"if"

289

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

305

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.

317

if (!GuardBB) return nullptr

318

GuardBI is overwritten before used.

335

The comment is outdated (ExitBlock)

339

We often use the pattern:

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

355

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.

358

I'm always for newlines to mark control condition changes

359

This is the general version (see above) again.

368

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

576

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?

601

It is enforced by getCmpInst().

605

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.

653

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

193

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

219

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.

223

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.

355

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)

359

see above reply.

368

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

590

"which update" -> "that updates"

592

instrucion -> instruction

596

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

598

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

601

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

605

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?

619

Can IndVar be made const?

622

"which update" -> "that updates"

623

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?

627

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

633

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

651

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.

652

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

654

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

663

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?

664

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.

667

varaible -> variable

675

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.

677

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

225

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

225

Do you handle the ULE/SLE case anywhere?

288

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

330

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.

369

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.

374

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?

452

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

467

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

470

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?

522

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 ↗

(On Diff #196634)

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

llvm/include/llvm/Analysis/LoopInfo.h

576

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.

601

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

605

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

193

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

219

Probably/Hopefully, correct.

355

You are obviously right here, ...

I should not do code reviews at night...

368

No strong feeling, keep it.

374

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

605

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.

651

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.

652

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.

654

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

663

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

675

Right, that's the intensional behaviour

677

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

llvm/lib/Analysis/LoopInfo.cpp

225

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.

288

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

330

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

369

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

374

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.

470

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

619

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

llvm/lib/Analysis/LoopInfo.cpp

289

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

415

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.

421

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.

573

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.

605

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?

663

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.

680

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

llvm/lib/Analysis/LoopInfo.cpp

225

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?

235

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?

250

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

343

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.

350

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

413

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?

418

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

483

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

413

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

573

Tried this with doxygen, looks as expected.

llvm/lib/Analysis/LoopInfo.cpp

250

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

483

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

415

changed.

421

Added comment to clarify that.

605

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

663

an instruction is a value as well.

680

moved.

llvm/lib/Analysis/LoopInfo.cpp

225

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.

235

added.

343

Updated the comment.

350

done.

413

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.

418

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

579

a -> an

678

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

llvm/lib/Analysis/LoopInfo.cpp

250

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.

289

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.

306

Similarly, this is typically written as:

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

523

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

[Whitney]

llvm/lib/Analysis/LoopInfo.cpp

289

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

541

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

llvm/lib/Analysis/LoopInfo.cpp

191

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

289

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

59

Unused?

642

This is basically the same as InductionDescriptor::getConsecutiveDirection

663

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

313

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

313

at leas conceptually

[Whitney]

llvm/include/llvm/Analysis/LoopInfo.h

59

right, will remove.

642

I believe getConsecutiveDirection only work for constant step.

663

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

llvm/lib/Analysis/LoopInfo.cpp

313

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

 
 namespace llvm {
 
 class DominatorTree;
 class LoopInfo;
 class Loop;
 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;
 
+  /// Derived classes can override this method using static template
+  /// polymorphism.
+  BranchInst *getGuard(ScalarEvolution &SE) const { return nullptr; }
+
+  /// Derived classes can override this method using static template
+  /// polymorphism.
+  PHINode *getInductionVariable(ScalarEvolution &SE,
+                                bool CheckStepInvariant = false) 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;
 
+  /// 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
+  /// getGuard             --> if (guardcmp) goto loop; else goto afterloop
+  /// getInductionVariable          --> i1
+  /// getAuxiliaryInductionVariable --> {i1}
+  /// isCanonical                   --> false
+  struct LoopBounds {
+    /// LoopBounds can only be created if an induction variable can be
+    /// identified.
+    LoopBounds(const Loop &Loop, Value &I, Instruction &S, ICmpInst &C,
+               ScalarEvolution &SE)
+        : L(Loop), Init(I), StepInst(S), CmpInst(C), SE(SE) {}
+    /// Get the initial value of the loop induction variable.
+    Value &getInitialIVValue() const { return Init; }
+    /// Get the instruction which update the loop induction variable.
+    Instruction &getStepInst() const { return StepInst; }
+    /// Get the step that the loop induction variable get updated for each loop
+    /// iteration.
+    Value &getStepValue() const { return *StepInst.getOperand(1); }
+    /// Get the final value of the loop induction variable.
+    Value &getFinalIVValue() const { return *CmpInst.getOperand(1); }
+    /// Return the predicate for the latch comparison when
+    /// - the first successor of the latch branch is the loop header
+    /// - the LHS of the latch comparison is StepInst
+    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:
+    /// Get the direction of the loop using loop bounds. This only works for
+    /// constant bounds.
+    Direction getDirectionFromConstantBounds() const;
+
+    const Loop &L;
+    // the initial value of the loop induction variable
+    Value &Init;
+    // the instruction which update the induction variable
+    Instruction &StepInst;
+    // the latch condition instruction
+    ICmpInst &CmpInst;
+
+    ScalarEvolution &SE;
+  };
+
+  /// Return the struct LoopBounds collected if all struct members are found,
+  /// else return nullptr.
+  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 loop initial value satisfy the latch
+  ///   condition
+  BranchInst *getGuard(ScalarEvolution &SE) const;
+
+  /// Return the loop induction variable if found, else return nullptr.
+  /// An instruction is considered as induction variable if
+  /// - it is a phi node in the loop header
+  /// - it is used in the LHS of the conditional branch in the loop latch
+  /// If CheckStepInvariant, only return the induction variable if Step is loop
+  /// invariant.
+  PHINode *getInductionVariable(ScalarEvolution &SE,
+                                bool CheckStepInvariant = false) const;
+
+  /// Return true if the given PHINode \p AuxIndVar is
+  /// - in 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.
+  bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
+                                    ScalarEvolution *SE = nullptr) const;
+
+  /// Return true if the induction variable starts at 0 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.
   bool isLoopSimplifyForm() const;
 
   /// Return true if the loop body is safe to clone in practice.
   bool isSafeToClone() const;
 
   /// Returns true if the loop is annotated parallel.
   ///
   /// A parallel loop can be assumed to not contain any dependencies between
   /// iterations by the compiler. That is, any loop-carried dependency checking
   /// can be skipped completely when parallelizing the loop on the target
   /// machine. Thus, if the parallel loop information originates from the
   /// programmer, e.g. via the OpenMP parallel for pragma, it is the
   /// programmer's responsibility to ensure there are no loop-carried
   /// dependencies. The final execution order of the instructions across
   /// iterations is not guaranteed, thus, the end result might or might not
   /// implement actual concurrent execution of instructions across multiple
   /// iterations.
   bool isAnnotatedParallel() const;
 
   /// Return the llvm.loop loop id metadata node for this loop if it is present.
   ///
   /// If this loop contains the same llvm.loop metadata on each branch to the
   /// header then the node is returned. If any latch instruction does not
   /// contain llvm.loop or if multiple latches contain different nodes then
   /// 0 is returned.
   MDNode *getLoopID() const;
   /// Set the llvm.loop loop id metadata for this loop.
   ///
   /// The LoopID metadata node will be added to each terminator instruction in
   /// the loop that branches to the loop header.
   ///
   /// The LoopID metadata node should have one or more operands and the first

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/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfoImpl.h"
 #include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Analysis/ScalarEvolution.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
+static bool isEqual(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
+static bool diffOne(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();
+}
+
+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");
+
+  // Need to inverse the predicate when first successor is not the loop
+  // header
+  ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())
+                                 ? CmpInst.getPredicate()
+                                 : CmpInst.getInversePredicate();
+
+  // Need to flip strictness of the predicate when the LHS is not the
+  // StepInst
+  if (CmpInst.getOperand(0) != &StepInst) {
+    // Cannot flip strictness of NE and EQ
+    if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
+      return ICmpInst::getFlippedStrictnessPredicate(Pred);
+    Direction D = getDirectionFromConstantBounds();
+    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;
+  }
+
+  return Pred;
+}
+
+Direction Loop::LoopBounds::getDirectionFromConstantBounds() 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;
+}
+
+Direction Loop::LoopBounds::getDirection() const {
+  // Use getUnsignedPredicate to eliminate the number of cases needed.
+  switch (ICmpInst::getUnsignedPredicate(getCanonicalPredicate())) {
+  // i > FinalValue --> Decreasing
+  case ICmpInst::ICMP_UGT:
+  case ICmpInst::ICMP_UGE:
+    return Direction::Decreasing;
+  // i < FinalValue --> Increasing
+  case ICmpInst::ICMP_ULT:
+  case ICmpInst::ICMP_ULE:
+    return Direction::Increasing;
+  case ICmpInst::ICMP_EQ:
+  case ICmpInst::ICMP_NE:
+    break;
+  default:
+    assert(false && "Unexpected predicate");
+  }
+
+  // Try to find the direction using loop bounds. This only works for
+  // constant bounds.
+  return getDirectionFromConstantBounds();
+}
+
+/// Get loop initial value
+static Value *getInit(const Loop &L, const PHINode &IndVar) {
+  BasicBlock *Preheader = L.getLoopPreheader();
+  assert(Preheader && "Expecting valid preheader");
+
+  return IndVar.getIncomingValueForBlock(Preheader);
+}
+
+/// Get the instruction which update the induction variable
+static Instruction *getStepInst(const Loop &L, const PHINode &IndVar,
+                                ScalarEvolution &SE) {
+  BasicBlock *Latch = L.getLoopLatch();
+  assert(Latch && "Expecting valid latch");
+
+  Instruction *StepInst =
+      dyn_cast<Instruction>(IndVar.getIncomingValueForBlock(Latch));
+  if (!StepInst)
+    return nullptr;
+
+  assert(
+      isEqual(*StepInst->getOperand(0), const_cast<PHINode &>(IndVar), SE) &&
+      "Expecting the first operand of the step instruction to be the induction "
+      "variable");
+
+  return StepInst;
+}
+
+/// Get the latch condition instruction
+static ICmpInst *getCmpInst(const Loop &L) {
+  BasicBlock *Latch = L.getLoopLatch();
+  assert(Latch && "Expecting valid latch");
+
+  BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
+  if (!BI || !BI->isConditional())
+    return nullptr;
+
+  ICmpInst *CI = dyn_cast<ICmpInst>(BI->getCondition());
+  if (!CI)
+    return nullptr;
+
+  // First operand of CI should be the StepInst
+  if (isa<Instruction>(CI->getOperand(0)))
+    return CI;
+
+  return nullptr;
+}
+
+Optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
+  PHINode *IndVar = getInductionVariable(SE);
+  if (!IndVar)
+    return None;
+
+  if (Value *Init = getInit(*this, *IndVar))
+    if (Instruction *StepInst = getStepInst(*this, *IndVar, SE))
+      if (ICmpInst *CmpInst = getCmpInst(*this))
+        return LoopBounds(*this, *Init, *StepInst, *CmpInst, SE);
+
+  return None;
+}
+
+/// Return the closest conditional branch before loop L, where
+/// one successor dominates the loop preheader,
+/// and a loop exit block dominates the other successor.
+/// Example:
+/// 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:
+/// 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();
+  BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
+  if (!GuardBB || !GuardBI)
+    return nullptr;
+
+  // Search backward from preheader to find a basic block which has conditional
+  // branch. Notice that loop preheader branch is definitely not conditional.
+  BasicBlock *Succ =
+      nullptr; // The successor of GuardBB which 'flows' into the loop preheader
+  SmallPtrSet<BasicBlock *, 4> Visited;
+  do {
+    Succ = GuardBB;
+    GuardBB = GuardBB->getSinglePredecessor();
+    if (!GuardBB)
+      return nullptr;
+
+    // A Visited set is needed to records blocks already visited, to avoid
+    // infinite loop when ExitBlock single successor loops back to itself.
+    if (Visited.count(GuardBB) != 0)
+      return nullptr;
+
+    Visited.insert(GuardBB);
+    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 single successor loops back to itself.
+    SmallPtrSet<BasicBlock *, 4> Visited;
+    while (ExitBlock && ExitBlock != SkipToBlock &&
+           Visited.count(ExitBlock) == 0) {
+      Visited.insert(ExitBlock);
+      ExitBlock = ExitBlock->getSingleSuccessor();
+    }
+    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 (isEqual(*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 (!isEqual(*GuardInitialValue, LatchInitialValue, SE))
+    return nullptr;
+
+  if (isEqual(*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' iff 'lb <= ub + 1' and 'ub > lb' iff 'ub >= lb - 1'.
+  if ((GuardPred == ICmpInst::ICMP_SLE && LatchPred == ICmpInst::ICMP_SLT &&
+       diffOne(LatchFinalValue, *GuardFinalValue, SE)) ||
+      (GuardPred == ICmpInst::ICMP_SGE && LatchPred == ICmpInst::ICMP_SGT &&
+       diffOne(*GuardFinalValue, LatchFinalValue, SE)))
+    return Guard;
+
+  return nullptr;
+}
+
+PHINode *Loop::getInductionVariable(ScalarEvolution &SE,
+                                    bool CheckStepInvariant) const {
+  if (!isLoopSimplifyForm())
+    return nullptr;
+
+  BasicBlock *Header = getHeader();
+  BasicBlock *Latch = getLoopLatch();
+  ICmpInst *CmpInst = getCmpInst(*this);
+  if (!CmpInst)
+    return nullptr;
+
+  // the loop induction variable should not be loop invariant
+  if (isLoopInvariant(CmpInst->getOperand(0)))
+    return nullptr;
+
+  // case 1:
+  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
+  // StepInst = IndVar + step
+  // cmp = StepInst < FinalValue
+  Instruction *StepInst = dyn_cast<Instruction>(CmpInst->getOperand(0));
+  assert(StepInst &&
+         "Expecting the first operand of CmpInst is an instruction");
+
+  // Loop over all of the PHI nodes in loop header, store the PHI node that has
+  // incoming value from latch equals to the StepInst
+  PHINode *IndVar = nullptr;
+  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
+    PHINode *PN = cast<PHINode>(I);
+    Value *IncomingValue = PN->getIncomingValueForBlock(Latch);
+    assert(IncomingValue && "Expecting valid incoming value from latch");
+    if (StepInst == IncomingValue) {
+      IndVar = PN;
+      break;
+    }
+  }
+  if (IndVar && isEqual(*StepInst->getOperand(0), *IndVar, SE))
+    if (!CheckStepInvariant || isLoopInvariant(StepInst->getOperand(1)))
+      return IndVar;
+
+  // case 2:
+  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
+  // StepInst = IndVar + step
+  // cmp = IndVar < FinalValue
+  IndVar = dyn_cast<PHINode>(CmpInst->getOperand(0));
+  if (!IndVar)
+    return nullptr;
+
+  if (IndVar->getParent() != Header)
+    return nullptr;
+
+  Value *IncomingValue = IndVar->getIncomingValueForBlock(Latch);
+  assert(IncomingValue && "Expecting valid incoming value from latch");
+  StepInst = dyn_cast<Instruction>(IncomingValue);
+  if (StepInst && StepInst->getOperand(0) == IndVar)
+    if (!CheckStepInvariant || isLoopInvariant(StepInst->getOperand(1)))
+      return IndVar;
+
+  return nullptr;
+}
+
+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;
+
+  // incremented by a loop invariant step fpr each loop iteration
+  // and the step instruction opcode should be add or sub.
+  BasicBlock *Latch = getLoopLatch();
+  if (!Latch)
+    return false;
+
+  Instruction *StepInst =
+      dyn_cast<Instruction>(AuxIndVar.getIncomingValueForBlock(Latch));
+  if (!StepInst || StepInst->getNumOperands() != 2 ||
+      (StepInst->getOpcode() != Instruction::Add &&
+       StepInst->getOpcode() != Instruction::Sub))
+    return false;
+
+  if (SE != nullptr)
+    return isa<SCEVAddRecExpr>(SE->getSCEV(StepInst));
+
+  if (StepInst->getOperand(0) == &AuxIndVar)
+    if (isLoopInvariant(StepInst->getOperand(1)))
+      return true;
+
+  if (StepInst->getOperand(1) == &AuxIndVar)
+    if (isLoopInvariant(StepInst->getOperand(0)))
+      return true;
+
+  return false;
+}
+
+bool Loop::isCanonical(ScalarEvolution &SE) const {
+  const Optional<LoopBounds> Bound = getBounds(SE);
+  if (!Bound)
+    return false;
+
+  ConstantInt *Init = dyn_cast<ConstantInt>(&Bound->getInitialIVValue());
+  if (!Init || !Init->isZero())
+    return false;
+
+  if (Bound->getStepInst().getOpcode() != Instruction::Add)
+    return false;
+
+  ConstantInt *Step = dyn_cast<ConstantInt>(&Bound->getStepValue());
+  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 (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;
 }
 
 void Loop::setLoopID(MDNode *LoopID) const {
   assert((!LoopID || LoopID->getNumOperands() > 0) &&
          "Loop ID needs at least one operand");

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));
+      });
+}