Factor out UnrollAnalyzer to Analysis, and add unit tests for it.

[mzolotukhin]

Summary

Unrolling Analyzer is already pretty complicated, and it becomes harder and harder to exercise it with usual IR tests, as with them we can only check the final decision: whether the loop is unrolled or not. This change factors this framework out from LoopUnrollPass to analyses, which allows to use unit tests.
The change itself is supposed to be NFC, except adding a couple of tests.

I plan to add more tests as I add new functionality and find/fix bugs.

[sanjoy]

I think this change requires some reorganization before it can go in. Please take a look at http://llvm.org/docs/CodingStandards.html

include/llvm/Analysis/LoopUnrollAnalyzer.h

6 ↗

(On Diff #46098)

This is very unlike headers in the rest of LLVM -- have you looked at other headers in this directory? For instance:

• Headers should not open namespaces
• License header is missing
• Function bodies (e.g. visitBinaryOperator) should be in the cpp file

25 ↗

(On Diff #46098)

This should be in namespace llvm.

I'd say it is better to not even expose this as an InstVisitor but keep that an implementation detail; but that's debatable.

[mzolotukhin]

Thanks for the feedback, Sanjoy! Yep, I haven't done such refactorings in llvm before, so I really appreciate such feedback.
I'll update the patch shortly.

Thanks,
Michael

[mzolotukhin]

• Better follow coding standards.

[mzolotukhin]

Hi Sanjoy,

I updated the patch, please take a look. As for not exposing it as InstVisitor: my intention to move this functionality out is just to enable unit-testing for it. And unit-testing in this case is much easier, as we can actually pin-point interesting cases (e.g. given just two instructions A and B, if we know that A is simplified to C, do we simplify B?). However, I'm happy to reconsider this if there are arguments against it.

Thanks,
Michael

[mzolotukhin]

Ping!

[sanjoy]

LGTM with minor suggestions, sorry for the delay. I only casually skimmed through the logic, since this is supposed to be an NFC.

lib/Analysis/LoopUnrollAnalyzer.cpp

19 ↗

(On Diff #46331)

Minor: usually .cpp files tend to using namespace llvm; instead of this.

unittests/Analysis/UnrollAnalyzer.cpp

22 ↗

(On Diff #46331)

Minor: I'd just make these static and remove the anonymous namespace. Instead, the anonymous namespace needs to be around struct UnrollAnalyzerTest.

llvm/trunk/include/llvm/Analysis/LoopUnrollAnalyzer.h

+//===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements UnrolledInstAnalyzer class. It's used for predicting
+// potential effects that loop unrolling might have, such as enabling constant
+// propagation and other optimizations.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
+#define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
+
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/IR/InstVisitor.h"
+
+// This class is used to get an estimate of the optimization effects that we
+// could get from complete loop unrolling. It comes from the fact that some
+// loads might be replaced with concrete constant values and that could trigger
+// a chain of instruction simplifications.
+//
+// E.g. we might have:
+//   int a[] = {0, 1, 0};
+//   v = 0;
+//   for (i = 0; i < 3; i ++)
+//     v += b[i]*a[i];
+// If we completely unroll the loop, we would get:
+//   v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
+// Which then will be simplified to:
+//   v = b[0]* 0 + b[1]* 1 + b[2]* 0
+// And finally:
+//   v = b[1]
+namespace llvm {
+class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
+  typedef InstVisitor<UnrolledInstAnalyzer, bool> Base;
+  friend class InstVisitor<UnrolledInstAnalyzer, bool>;
+  struct SimplifiedAddress {
+    Value *Base = nullptr;
+    ConstantInt *Offset = nullptr;
+  };
+
+public:
+  UnrolledInstAnalyzer(unsigned Iteration,
+                       DenseMap<Value *, Constant *> &SimplifiedValues,
+                       ScalarEvolution &SE)
+      : SimplifiedValues(SimplifiedValues), SE(SE) {
+      IterationNumber = SE.getConstant(APInt(64, Iteration));
+  }
+
+  // Allow access to the initial visit method.
+  using Base::visit;
+
+private:
+  /// \brief A cache of pointer bases and constant-folded offsets corresponding
+  /// to GEP (or derived from GEP) instructions.
+  ///
+  /// In order to find the base pointer one needs to perform non-trivial
+  /// traversal of the corresponding SCEV expression, so it's good to have the
+  /// results saved.
+  DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
+
+  /// \brief SCEV expression corresponding to number of currently simulated
+  /// iteration.
+  const SCEV *IterationNumber;
+
+  /// \brief A Value->Constant map for keeping values that we managed to
+  /// constant-fold on the given iteration.
+  ///
+  /// While we walk the loop instructions, we build up and maintain a mapping
+  /// of simplified values specific to this iteration.  The idea is to propagate
+  /// any special information we have about loads that can be replaced with
+  /// constants after complete unrolling, and account for likely simplifications
+  /// post-unrolling.
+  DenseMap<Value *, Constant *> &SimplifiedValues;
+
+  ScalarEvolution &SE;
+
+  bool simplifyInstWithSCEV(Instruction *I);
+
+  bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); }
+  bool visitBinaryOperator(BinaryOperator &I);
+  bool visitLoad(LoadInst &I);
+  bool visitCastInst(CastInst &I);
+  bool visitCmpInst(CmpInst &I);
+};
+}
+#endif

llvm/trunk/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   Interval.cpp
   IntervalPartition.cpp
   IteratedDominanceFrontier.cpp
   LazyCallGraph.cpp
   LazyValueInfo.cpp
   Lint.cpp
   Loads.cpp
   LoopAccessAnalysis.cpp
+  LoopUnrollAnalyzer.cpp
   LoopInfo.cpp
   LoopPass.cpp
   MemDepPrinter.cpp
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp
   MemoryLocation.cpp
   ModuleDebugInfoPrinter.cpp

llvm/trunk/lib/Analysis/LoopUnrollAnalyzer.cpp

+//===- LoopUnrollAnalyzer.cpp - Unrolling Effect Estimation -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements UnrolledInstAnalyzer class. It's used for predicting
+// potential effects that loop unrolling might have, such as enabling constant
+// propagation and other optimizations.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopUnrollAnalyzer.h"
+#include "llvm/IR/Dominators.h"
+
+using namespace llvm;
+
+/// \brief Try to simplify instruction \param I using its SCEV expression.
+///
+/// The idea is that some AddRec expressions become constants, which then
+/// could trigger folding of other instructions. However, that only happens
+/// for expressions whose start value is also constant, which isn't always the
+/// case. In another common and important case the start value is just some
+/// address (i.e. SCEVUnknown) - in this case we compute the offset and save
+/// it along with the base address instead.
+bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
+  if (!SE.isSCEVable(I->getType()))
+    return false;
+
+  const SCEV *S = SE.getSCEV(I);
+  if (auto *SC = dyn_cast<SCEVConstant>(S)) {
+    SimplifiedValues[I] = SC->getValue();
+    return true;
+  }
+
+  auto *AR = dyn_cast<SCEVAddRecExpr>(S);
+  if (!AR)
+    return false;
+
+  const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
+  // Check if the AddRec expression becomes a constant.
+  if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
+    SimplifiedValues[I] = SC->getValue();
+    return true;
+  }
+
+  // Check if the offset from the base address becomes a constant.
+  auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
+  if (!Base)
+    return false;
+  auto *Offset =
+      dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
+  if (!Offset)
+    return false;
+  SimplifiedAddress Address;
+  Address.Base = Base->getValue();
+  Address.Offset = Offset->getValue();
+  SimplifiedAddresses[I] = Address;
+  return true;
+}
+
+/// Try to simplify binary operator I.
+///
+/// TODO: Probably it's worth to hoist the code for estimating the
+/// simplifications effects to a separate class, since we have a very similar
+/// code in InlineCost already.
+bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+  if (!isa<Constant>(LHS))
+    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
+      LHS = SimpleLHS;
+  if (!isa<Constant>(RHS))
+    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
+      RHS = SimpleRHS;
+
+  Value *SimpleV = nullptr;
+  const DataLayout &DL = I.getModule()->getDataLayout();
+  if (auto FI = dyn_cast<FPMathOperator>(&I))
+    SimpleV =
+        SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
+  else
+    SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
+
+  if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
+    SimplifiedValues[&I] = C;
+
+  if (SimpleV)
+    return true;
+  return Base::visitBinaryOperator(I);
+}
+
+/// Try to fold load I.
+bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
+  Value *AddrOp = I.getPointerOperand();
+
+  auto AddressIt = SimplifiedAddresses.find(AddrOp);
+  if (AddressIt == SimplifiedAddresses.end())
+    return false;
+  ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
+
+  auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
+  // We're only interested in loads that can be completely folded to a
+  // constant.
+  if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
+    return false;
+
+  ConstantDataSequential *CDS =
+      dyn_cast<ConstantDataSequential>(GV->getInitializer());
+  if (!CDS)
+    return false;
+
+  // We might have a vector load from an array. FIXME: for now we just bail
+  // out in this case, but we should be able to resolve and simplify such
+  // loads.
+  if(!CDS->isElementTypeCompatible(I.getType()))
+    return false;
+
+  int ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
+  assert(SimplifiedAddrOp->getValue().getActiveBits() < 64 &&
+         "Unexpectedly large index value.");
+  int64_t Index = SimplifiedAddrOp->getSExtValue() / ElemSize;
+  if (Index >= CDS->getNumElements()) {
+    // FIXME: For now we conservatively ignore out of bound accesses, but
+    // we're allowed to perform the optimization in this case.
+    return false;
+  }
+
+  Constant *CV = CDS->getElementAsConstant(Index);
+  assert(CV && "Constant expected.");
+  SimplifiedValues[&I] = CV;
+
+  return true;
+}
+
+/// Try to simplify cast instruction.
+bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
+  // Propagate constants through casts.
+  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
+  if (!COp)
+    COp = SimplifiedValues.lookup(I.getOperand(0));
+  if (COp)
+    if (Constant *C =
+            ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
+      SimplifiedValues[&I] = C;
+      return true;
+    }
+
+  return Base::visitCastInst(I);
+}
+
+/// Try to simplify cmp instruction.
+bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+
+  // First try to handle simplified comparisons.
+  if (!isa<Constant>(LHS))
+    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
+      LHS = SimpleLHS;
+  if (!isa<Constant>(RHS))
+    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
+      RHS = SimpleRHS;
+
+  if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
+    auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
+    if (SimplifiedLHS != SimplifiedAddresses.end()) {
+      auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
+      if (SimplifiedRHS != SimplifiedAddresses.end()) {
+        SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
+        SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
+        if (LHSAddr.Base == RHSAddr.Base) {
+          LHS = LHSAddr.Offset;
+          RHS = RHSAddr.Offset;
+        }
+      }
+    }
+  }
+
+  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
+    if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
+      if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
+        SimplifiedValues[&I] = C;
+        return true;
+      }
+    }
+  }
+
+  return Base::visitCmpInst(I);
+}

llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp

 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/LoopUnrollAnalyzer.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/IntrinsicInst.h"
if (UP.PartialThreshold != NoThreshold)
       UP.PartialThreshold =
           std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
   }
 
   return UP;
 }
 
 namespace {
-// This class is used to get an estimate of the optimization effects that we
-// could get from complete loop unrolling. It comes from the fact that some
-// loads might be replaced with concrete constant values and that could trigger
-// a chain of instruction simplifications.
-//
-// E.g. we might have:
-//   int a[] = {0, 1, 0};
-//   v = 0;
-//   for (i = 0; i < 3; i ++)
-//     v += b[i]*a[i];
-// If we completely unroll the loop, we would get:
-//   v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
-// Which then will be simplified to:
-//   v = b[0]* 0 + b[1]* 1 + b[2]* 0
-// And finally:
-//   v = b[1]
-class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
-  typedef InstVisitor<UnrolledInstAnalyzer, bool> Base;
-  friend class InstVisitor<UnrolledInstAnalyzer, bool>;
-  struct SimplifiedAddress {
-    Value *Base = nullptr;
-    ConstantInt *Offset = nullptr;
-  };
-
-public:
-  UnrolledInstAnalyzer(unsigned Iteration,
-                       DenseMap<Value *, Constant *> &SimplifiedValues,
-                       ScalarEvolution &SE)
-      : SimplifiedValues(SimplifiedValues), SE(SE) {
-      IterationNumber = SE.getConstant(APInt(64, Iteration));
-  }
-
-  // Allow access to the initial visit method.
-  using Base::visit;
-
-private:
-  /// \brief A cache of pointer bases and constant-folded offsets corresponding
-  /// to GEP (or derived from GEP) instructions.
-  ///
-  /// In order to find the base pointer one needs to perform non-trivial
-  /// traversal of the corresponding SCEV expression, so it's good to have the
-  /// results saved.
-  DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
-
-  /// \brief SCEV expression corresponding to number of currently simulated
-  /// iteration.
-  const SCEV *IterationNumber;
-
-  /// \brief A Value->Constant map for keeping values that we managed to
-  /// constant-fold on the given iteration.
-  ///
-  /// While we walk the loop instructions, we build up and maintain a mapping
-  /// of simplified values specific to this iteration.  The idea is to propagate
-  /// any special information we have about loads that can be replaced with
-  /// constants after complete unrolling, and account for likely simplifications
-  /// post-unrolling.
-  DenseMap<Value *, Constant *> &SimplifiedValues;
-
-  ScalarEvolution &SE;
-
-  /// \brief Try to simplify instruction \param I using its SCEV expression.
-  ///
-  /// The idea is that some AddRec expressions become constants, which then
-  /// could trigger folding of other instructions. However, that only happens
-  /// for expressions whose start value is also constant, which isn't always the
-  /// case. In another common and important case the start value is just some
-  /// address (i.e. SCEVUnknown) - in this case we compute the offset and save
-  /// it along with the base address instead.
-  bool simplifyInstWithSCEV(Instruction *I) {
-    if (!SE.isSCEVable(I->getType()))
-      return false;
-
-    const SCEV *S = SE.getSCEV(I);
-    if (auto *SC = dyn_cast<SCEVConstant>(S)) {
-      SimplifiedValues[I] = SC->getValue();
-      return true;
-    }
-
-    auto *AR = dyn_cast<SCEVAddRecExpr>(S);
-    if (!AR)
-      return false;
-
-    const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
-    // Check if the AddRec expression becomes a constant.
-    if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
-      SimplifiedValues[I] = SC->getValue();
-      return true;
-    }
-
-    // Check if the offset from the base address becomes a constant.
-    auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
-    if (!Base)
-      return false;
-    auto *Offset =
-        dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
-    if (!Offset)
-      return false;
-    SimplifiedAddress Address;
-    Address.Base = Base->getValue();
-    Address.Offset = Offset->getValue();
-    SimplifiedAddresses[I] = Address;
-    return true;
-  }
-
-  /// Base case for the instruction visitor.
-  bool visitInstruction(Instruction &I) {
-    return simplifyInstWithSCEV(&I);
-  }
-
-  /// Try to simplify binary operator I.
-  ///
-  /// TODO: Probably it's worth to hoist the code for estimating the
-  /// simplifications effects to a separate class, since we have a very similar
-  /// code in InlineCost already.
-  bool visitBinaryOperator(BinaryOperator &I) {
-    Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
-    if (!isa<Constant>(LHS))
-      if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
-        LHS = SimpleLHS;
-    if (!isa<Constant>(RHS))
-      if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
-        RHS = SimpleRHS;
-
-    Value *SimpleV = nullptr;
-    const DataLayout &DL = I.getModule()->getDataLayout();
-    if (auto FI = dyn_cast<FPMathOperator>(&I))
-      SimpleV =
-          SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
-    else
-      SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
-
-    if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
-      SimplifiedValues[&I] = C;
-
-    if (SimpleV)
-      return true;
-    return Base::visitBinaryOperator(I);
-  }
-
-  /// Try to fold load I.
-  bool visitLoad(LoadInst &I) {
-    Value *AddrOp = I.getPointerOperand();
-
-    auto AddressIt = SimplifiedAddresses.find(AddrOp);
-    if (AddressIt == SimplifiedAddresses.end())
-      return false;
-    ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
-
-    auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
-    // We're only interested in loads that can be completely folded to a
-    // constant.
-    if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
-      return false;
-
-    ConstantDataSequential *CDS =
-        dyn_cast<ConstantDataSequential>(GV->getInitializer());
-    if (!CDS)
-      return false;
-
-    // We might have a vector load from an array. FIXME: for now we just bail
-    // out in this case, but we should be able to resolve and simplify such
-    // loads.
-    if(!CDS->isElementTypeCompatible(I.getType()))
-      return false;
-
-    int ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
-    assert(SimplifiedAddrOp->getValue().getActiveBits() < 64 &&
-           "Unexpectedly large index value.");
-    int64_t Index = SimplifiedAddrOp->getSExtValue() / ElemSize;
-    if (Index >= CDS->getNumElements()) {
-      // FIXME: For now we conservatively ignore out of bound accesses, but
-      // we're allowed to perform the optimization in this case.
-      return false;
-    }
-
-    Constant *CV = CDS->getElementAsConstant(Index);
-    assert(CV && "Constant expected.");
-    SimplifiedValues[&I] = CV;
-
-    return true;
-  }
-
-  bool visitCastInst(CastInst &I) {
-    // Propagate constants through casts.
-    Constant *COp = dyn_cast<Constant>(I.getOperand(0));
-    if (!COp)
-      COp = SimplifiedValues.lookup(I.getOperand(0));
-    if (COp)
-      if (Constant *C =
-              ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
-        SimplifiedValues[&I] = C;
-        return true;
-      }
-
-    return Base::visitCastInst(I);
-  }
-
-  bool visitCmpInst(CmpInst &I) {
-    Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
-
-    // First try to handle simplified comparisons.
-    if (!isa<Constant>(LHS))
-      if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
-        LHS = SimpleLHS;
-    if (!isa<Constant>(RHS))
-      if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
-        RHS = SimpleRHS;
-
-    if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
-      auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
-      if (SimplifiedLHS != SimplifiedAddresses.end()) {
-        auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
-        if (SimplifiedRHS != SimplifiedAddresses.end()) {
-          SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
-          SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
-          if (LHSAddr.Base == RHSAddr.Base) {
-            LHS = LHSAddr.Offset;
-            RHS = RHSAddr.Offset;
-          }
-        }
-      }
-    }
-
-    if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
-      if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
-        if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
-          SimplifiedValues[&I] = C;
-          return true;
-        }
-      }
-    }
-
-    return Base::visitCmpInst(I);
-  }
-};
-} // namespace
-
-
-namespace {
 struct EstimatedUnrollCost {
   /// \brief The estimated cost after unrolling.
   int UnrolledCost;
 
   /// \brief The estimated dynamic cost of executing the instructions in the
   /// rolled form.
   int RolledDynamicCost;
 };

llvm/trunk/unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   )
 
 add_llvm_unittest(AnalysisTests
   AliasAnalysisTest.cpp
   CallGraphTest.cpp
   CFGTest.cpp
   LazyCallGraphTest.cpp
   ScalarEvolutionTest.cpp
   MixedTBAATest.cpp
   ValueTrackingTest.cpp
+  UnrollAnalyzer.cpp
   )

llvm/trunk/unittests/Analysis/UnrollAnalyzer.cpp

+//===- UnrollAnalyzerTest.cpp - UnrollAnalyzer unit tests -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Analysis/LoopUnrollAnalyzer.h"
+#include "llvm/IR/Dominators.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+namespace llvm {
+void initializeUnrollAnalyzerTestPass(PassRegistry &);
+
+static SmallVector<DenseMap<Value *, Constant *>, 16> SimplifiedValuesVector;
+static unsigned TripCount = 0;
+
+namespace {
+struct UnrollAnalyzerTest : public FunctionPass {
+  static char ID;
+  bool runOnFunction(Function &F) override {
+    LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+
+    Function::iterator FI = F.begin();
+    FI++; // First basic block is entry - skip it.
+    BasicBlock *Header = &*FI++;
+    Loop *L = LI->getLoopFor(Header);
+
+    SimplifiedValuesVector.clear();
+    TripCount = SE->getSmallConstantTripCount(L, Header);
+    for (unsigned Iteration = 0; Iteration < TripCount; Iteration++) {
+      DenseMap<Value *, Constant *> SimplifiedValues;
+      UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE);
+      for (Instruction &I : *Header)
+        Analyzer.visit(I);
+      SimplifiedValuesVector.push_back(SimplifiedValues);
+    }
+    return false;
+  }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+    AU.addRequired<ScalarEvolutionWrapperPass>();
+    AU.setPreservesAll();
+  }
+  UnrollAnalyzerTest() : FunctionPass(ID) {
+    initializeUnrollAnalyzerTestPass(*PassRegistry::getPassRegistry());
+  }
+};
+}
+
+char UnrollAnalyzerTest::ID = 0;
+
+std::unique_ptr<Module> makeLLVMModule(UnrollAnalyzerTest *P,
+                                       const char *ModuleStr) {
+  LLVMContext &C = getGlobalContext();
+  SMDiagnostic Err;
+  return parseAssemblyString(ModuleStr, Err, C);
+}
+
+TEST(UnrollAnalyzerTest, BasicSimplifications) {
+  const char *ModuleStr =
+      "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
+      "define i64 @propagate_loop_phis() {\n"
+      "entry:\n"
+      "  br label %loop\n"
+      "loop:\n"
+      "  %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]\n"
+      "  %x0 = phi i64 [ 0, %entry ], [ %x2, %loop ]\n"
+      "  %x1 = or i64 %x0, 1\n"
+      "  %x2 = or i64 %x1, 2\n"
+      "  %inc = add nuw nsw i64 %iv, 1\n"
+      "  %cond = icmp sge i64 %inc, 8\n"
+      "  br i1 %cond, label %loop.end, label %loop\n"
+      "loop.end:\n"
+      "  %x.lcssa = phi i64 [ %x2, %loop ]\n"
+      "  ret i64 %x.lcssa\n"
+      "}\n";
+  UnrollAnalyzerTest *P = new UnrollAnalyzerTest();
+  std::unique_ptr<Module> M = makeLLVMModule(P, ModuleStr);
+  legacy::PassManager Passes;
+  Passes.add(P);
+  Passes.run(*M);
+
+  // Perform checks
+  Module::iterator MI = M->begin();
+  Function *F = &*MI++;
+  Function::iterator FI = F->begin();
+  FI++; // First basic block is entry - skip it.
+  BasicBlock *Header = &*FI++;
+
+  BasicBlock::iterator BBI = Header->begin();
+  std::advance(BBI, 4);
+  Instruction *Y1 = &*BBI++;
+  Instruction *Y2 = &*BBI++;
+  // Check simplification expected on the 1st iteration.
+  // Check that "%inc = add nuw nsw i64 %iv, 1" is simplified to 1
+  auto I1 = SimplifiedValuesVector[0].find(Y1);
+  EXPECT_TRUE(I1 != SimplifiedValuesVector[0].end());
+  EXPECT_EQ(dyn_cast<ConstantInt>((*I1).second)->getZExtValue(), 1U);
+
+  // Check that "%cond = icmp sge i64 %inc, 10" is simplified to false
+  auto I2 = SimplifiedValuesVector[0].find(Y2);
+  EXPECT_TRUE(I2 != SimplifiedValuesVector[0].end());
+  EXPECT_FALSE(dyn_cast<ConstantInt>((*I2).second)->getZExtValue());
+
+  // Check simplification expected on the last iteration.
+  // Check that "%inc = add nuw nsw i64 %iv, 1" is simplified to 8
+  I1 = SimplifiedValuesVector[TripCount - 1].find(Y1);
+  EXPECT_TRUE(I1 != SimplifiedValuesVector[TripCount - 1].end());
+  EXPECT_EQ(dyn_cast<ConstantInt>((*I1).second)->getZExtValue(), TripCount);
+
+  // Check that "%cond = icmp sge i64 %inc, 10" is simplified to false
+  I2 = SimplifiedValuesVector[TripCount - 1].find(Y2);
+  EXPECT_TRUE(I2 != SimplifiedValuesVector[TripCount - 1].end());
+  EXPECT_TRUE(dyn_cast<ConstantInt>((*I2).second)->getZExtValue());
+}
+} // end namespace llvm
+
+INITIALIZE_PASS_BEGIN(UnrollAnalyzerTest, "unrollanalyzertestpass",
+                      "unrollanalyzertestpass", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_END(UnrollAnalyzerTest, "unrollanalyzertestpass",
+                    "unrollanalyzertestpass", false, false)