[WIP] Polyhedral Value Analysis

[jdoerfert]

Summary

This is a _draft_ version for a polyhedral value analysis.

The goal of this analysis is a Scalar Evolution like experience with a
polyhedral-model-based backend. The analysis results are piece-wise
defined polyhedral expressions (PEXP). A PEXP is a loop-iteration
dependent, flow sensitive value description. See the class description
in PolyhedralValueInfo.h for more information and examples.

This patch includes isl, the integer set library. It is separated from
the analysis through the use of polyhedral values (PValue), a custom C++
abstraction layer. Once the interface is stable we can think about an
own implementation that does not depend on isl.

[bollu]

@jdoerfert: Thanks for putting this up. I'm trying to read and understand the ideas behind this. I've left a few questions, could you please clarify them for me?

include/llvm/Analysis/PolyhedralValueInfo.h

40

Should this have been i++? Otherwise, the explanation confuses me.

65

I want to clarify that I understand this representation correctly:

1. in the j-loop case, because the j is external to the body of the loop S(i, j), j is a free parameter.

2. in the i-loop case, j = base + niters where niters begins from 0? So, plugging in the actual values, we get j = i + l1, where l1 represents the number of iterations of j?

3. Outside both the i and the j loop, the same logic of base + niters holds. But in this case, since neither i nor j is part of our "scope", they cannot be parameters anymore, and are this just input values to the map: l0 and l1.

Am I correct so far?

Now, a slightly more complex example:

for (i = 10; i < N; i++)
   for(j = 2 * i; j < M; j += 4)
      S(i, j)

I assume the breakdown would be:

1. j-loop: [j] -> { [] -> [(j)] }
2. i-loop: [i] -> { [l1] -> [(2 * i + 4 * l1)]
3. max/none: [] -> { [l0, l1] -> [(2 * l0 + 4 * l1)]

I find the notation of induction-variables-outside-your-scope-is-parametric a little confusing, but I assume you have a rationale for this.

69

What does (fixed) value mean?

[jdoerfert]

I forgot to include a softlink of the isl include folder. In the llvm src directory the following should be sufficent:

ln -s ../lib/Analysis/isl/include/isl include

I would have updated the revision but there is a problem with Phabricator that prevents me from doing so.

[bollu]

@jdoerfert: Thanks for putting this up. I'm trying to read and understand the ideas behind this. I've left a few questions, could you please clarify them for me?

[jdoerfert]

include/llvm/Analysis/PolyhedralValueInfo.h

40

Yes, this is a typo. It should be i++.

65

Your breakdown looks (almost) good. After renaming of the actual result I get:

[j] -> { [] -> [(j)] }
[i] -> { [l0] -> [(2i + 4l0)] }
[]  -> { [l0, l1] -> [(20 + 2l0 + 4l1)] }

Which is the same for the first two cases but you forgot the initial value for i (here 10) which is multiplied by 2 for the start value of j.

---

I find the notation of induction-variables-outside-your-scope-is-parametric a little confusing, but I assume you have a rationale for this.

Notations are not perfect yet and I appreciate better ones.

69

Since I reuse the affine functions for domains I need a "value" but domains don't have a "value". So it will be the fixed value (1).

[grosser]

Hi Johannes,

thanks for posting the patch. Obviously it misses comments, and unittests for the C++ interface, but it already gives a very good idea where you are heading. I also feel this patch covers a couple of areas:

1. A new C++ interface which seems to serve multiple purposes
   • Automatic memory management
   • Add some additional math functionality not available in isl at the moment
   • Rename a couple of functions to provide a better interface to LLVM
   • Add a couple of helpers / convenience features on top of isl (e.g. automatic space adjustment)
   • Add some functionality that is directly needed for the domain/range modeling, but not necessarily belongs to the core properties of an isl set.

All of these ideas make a lot of sense. I am however slightly worried regarding the large amount of hand-written interfacing code -- which is often replicated across different classes. How much of isl are you planning to cover?
Will you also introduce callbacks and stuff? I wonder if there would be a way to avoid a lot of this duplication and possibly make the separation between the parts that are just isl interfaces and the parts that are indeed LLVM additions more clear. We also have a larger set of isl extensions in Polly -- including corresponding unit tests. I think sharing these would indeed make a lot of sense.

2. The polyhedral value analysis

The general interface makes a lot of sense - I played with this myself (after having introduced islpp), but waited for your proposal to come out. It is a clear extension of the LLVM-IR modeling we discussed together in Polly and you nicely mixed it with the ScalarEvolution design of LLVM. Cool! The code is currently a little too large to comment on specific items. Some of the things you do are already things we did in Polly but unfortunately missing most comments, others are clearly new and I need to read through them in detail. As I said on the mailing list thread, I feel that this analysis generally makes a lot of sense -- assuming we agree -- I would like to help getting it into LLVM. If you would like to do this incrementally -- the RISC-V model would make a lot of sense here. Do you believe there is a way to split this into smaller pieces? Maybe this can be split into:

• Basic Interface
• Analysis of scalar values without control flow
• Simple loops
• Wrapping

I am especially interested in understanding (and having documented well) how integer wrapping is modeled.

• Specifically, I would like this analysis to speculate the wrapping introduced by casts as they commonly arise e.g. in OpenCL code get_global_id / get_local_id. Not sure if this is currently possibly / optional.

• Also, did you consider multi-dimensional output spaces. I discussed with Siddharth and we might be able to model certain polynomial expressions this way. Most interestingly, we might be able to do delinearization on this model, which would allow us to effectively delinearize even in the presence of integer casts.

• Can you make wrapping optional -- meaning can you potentially model precise wrapping?

Also, do you happen to have a design description why all this works? If not, I wonder if we should create this together when building up the code incrementally in LLVM.

I also have a random set of comments, but these are clearly by far not complete but just passby comments.

include/llvm/Analysis/PValue.h

10

generation

11

backend

19

therefore

54

Is this needed?

include/llvm/Analysis/PolyhedralValueInfo.h

160

Why do you need a special InvalidDomain / KnownDomain? isl provides piecewise affs that can map to nans. Can this information not be directly modeled as part of the pwaff?

lib/Analysis/PValue.cpp

72

I feel this would be a lot cleaner if written with the isl++ bindings.

147

Again, islpp would make this so much clearer.

234

We have the very same functions in Polly. I feel that this is code-duplication that we should certainly find a solution to avoid.

259

Leftover comments?

829

isl++ would allow you to use proper lambdas.

914

Interesting. Are you planning to do this dimension adjustment on all binary operations?

If we would model loop dimensions also as parameters this adjustment would happen automatically. Not sure if this makes things easier though.

1046

Leftover?!

1067

This function would look so much nicer with islpp.

lib/Analysis/PolyhedralValueInfo.cpp

449

As isComplex always returns "false", I assume this is all dead code and likely will explode in some cases.

523

This function certainly needs a comment. ;-)

At best it is split in smaller pieces! ;-)

1079

I think LLVM suggest to not use auto, except in obvious cases.

[jdoerfert]

In D38255#880989, @grosser wrote:

Hi Johannes,

thanks for posting the patch. Obviously it misses comments, and unittests for the C++ interface, but it already gives a very good idea where you are heading. I also feel this patch covers a couple of areas:

1. A new C++ interface which seems to serve multiple purposes
   • Automatic memory management
   • Add some additional math functionality not available in isl at the moment
   • Rename a couple of functions to provide a better interface to LLVM
   • Add a couple of helpers / convenience features on top of isl (e.g. automatic space adjustment)
   • Add some functionality that is directly needed for the domain/range modeling, but not necessarily belongs to the core properties of an isl set.

All of these ideas make a lot of sense. I am however slightly worried regarding the large amount of hand-written interfacing code -- which is often replicated across different classes. How much of isl are you planning to cover?
Will you also introduce callbacks and stuff? I wonder if there would be a way to avoid a lot of this duplication and possibly make the separation between the parts that are just isl interfaces and the parts that are indeed LLVM additions more clear. We also have a larger set of isl extensions in Polly -- including corresponding unit tests. I think sharing these would indeed make a lot of sense.

2. The polyhedral value analysis

The general interface makes a lot of sense - I played with this myself (after having introduced islpp), but waited for your proposal to come out. It is a clear extension of the LLVM-IR modeling we discussed together in Polly and you nicely mixed it with the ScalarEvolution design of LLVM. Cool! The code is currently a little too large to comment on specific items. Some of the things you do are already things we did in Polly but unfortunately missing most comments, others are clearly new and I need to read through them in detail. As I said on the mailing list thread, I feel that this analysis generally makes a lot of sense -- assuming we agree -- I would like to help getting it into LLVM. If you would like to do this incrementally -- the RISC-V model would make a lot of sense here. Do you believe there is a way to split this into smaller pieces? Maybe this can be split into:

• Basic Interface
• Analysis of scalar values without control flow
• Simple loops
• Wrapping

I am especially interested in understanding (and having documented well) how integer wrapping is modeled.

• Specifically, I would like this analysis to speculate the wrapping introduced by casts as they commonly arise e.g. in OpenCL code get_global_id / get_local_id. Not sure if this is currently possibly / optional.

• Also, did you consider multi-dimensional output spaces. I discussed with Siddharth and we might be able to model certain polynomial expressions this way. Most interestingly, we might be able to do delinearization on this model, which would allow us to effectively delinearize even in the presence of integer casts.

• Can you make wrapping optional -- meaning can you potentially model precise wrapping?

Also, do you happen to have a design description why all this works? If not, I wonder if we should create this together when building up the code incrementally in LLVM.

I also have a random set of comments, but these are clearly by far not complete but just passby comments.

These are all very good but also very detailed questions. I would like to postpone them till this patch is in a form that should be reviewed. Right now I'd like to focus on the general idea, query interface and early results. Specific design choices (such as optional wrapping) can be discussed and added on top of a first implementation.

Just as a remark to the multi-dimentional spaces: Creating a multi-dimensional memory view (aka. "deliniarization") is already happening (for simple cases) in the memory analysis (which I did not yet publish). Conceptually that should be the place for such an "analysis". If we would allow multi-dimensional output spaces then to represent vector values which are actually multi-dimensional values.

[jdoerfert]

include/llvm/Analysis/PolyhedralValueInfo.h

160

No, because then the information is gone.

Take:

{ [i0] -> [(i0 + 1)] }

with an invalid domain:

{ [i0] : i0 < 5 }

If we can later proof i0 >= 5 we can use the PEXP without restriction. However, if we would have mapped all i0 < 5 to nan we would have lost their original mapping for good. (Also it would make the PVAff more complex.)

lib/Analysis/PValue.cpp

72

When I wrote/copied it there were no isl++ bindings.

234

While I didn't know that I am aware of other code snippets I directly took from Polly, thus which are now duplicated. Though we're talking about 5-15 lines of code not more at a time.

914

Binary operations are all done via combinator functions which automatically adjust dimensions, yes.

lib/Analysis/PolyhedralValueInfo.cpp

449

I'll just have to implement PVSet::isComplex similar to PVAff::isComplex.

[grosser]

In D38255#881010, @jdoerfert wrote:

In D38255#880989, @grosser wrote:

Hi Johannes,

thanks for posting the patch. Obviously it misses comments, and unittests for the C++ interface, but it already gives a very good idea where you are heading. I also feel this patch covers a couple of areas:

1. A new C++ interface which seems to serve multiple purposes
   • Automatic memory management
   • Add some additional math functionality not available in isl at the moment
   • Rename a couple of functions to provide a better interface to LLVM
   • Add a couple of helpers / convenience features on top of isl (e.g. automatic space adjustment)
   • Add some functionality that is directly needed for the domain/range modeling, but not necessarily belongs to the core properties of an isl set.

All of these ideas make a lot of sense. I am however slightly worried regarding the large amount of hand-written interfacing code -- which is often replicated across different classes. How much of isl are you planning to cover?
Will you also introduce callbacks and stuff? I wonder if there would be a way to avoid a lot of this duplication and possibly make the separation between the parts that are just isl interfaces and the parts that are indeed LLVM additions more clear. We also have a larger set of isl extensions in Polly -- including corresponding unit tests. I think sharing these would indeed make a lot of sense.

2. The polyhedral value analysis

The general interface makes a lot of sense - I played with this myself (after having introduced islpp), but waited for your proposal to come out. It is a clear extension of the LLVM-IR modeling we discussed together in Polly and you nicely mixed it with the ScalarEvolution design of LLVM. Cool! The code is currently a little too large to comment on specific items. Some of the things you do are already things we did in Polly but unfortunately missing most comments, others are clearly new and I need to read through them in detail. As I said on the mailing list thread, I feel that this analysis generally makes a lot of sense -- assuming we agree -- I would like to help getting it into LLVM. If you would like to do this incrementally -- the RISC-V model would make a lot of sense here. Do you believe there is a way to split this into smaller pieces? Maybe this can be split into:

• Basic Interface
• Analysis of scalar values without control flow
• Simple loops
• Wrapping

I am especially interested in understanding (and having documented well) how integer wrapping is modeled.

• Specifically, I would like this analysis to speculate the wrapping introduced by casts as they commonly arise e.g. in OpenCL code get_global_id / get_local_id. Not sure if this is currently possibly / optional.

• Also, did you consider multi-dimensional output spaces. I discussed with Siddharth and we might be able to model certain polynomial expressions this way. Most interestingly, we might be able to do delinearization on this model, which would allow us to effectively delinearize even in the presence of integer casts.

• Can you make wrapping optional -- meaning can you potentially model precise wrapping?

Also, do you happen to have a design description why all this works? If not, I wonder if we should create this together when building up the code incrementally in LLVM.

I also have a random set of comments, but these are clearly by far not complete but just passby comments.

These are all very good but also very detailed questions. I would like to postpone them till this patch is in a form that should be reviewed. Right now I'd like to focus on the general idea, query interface and early results. Specific design choices (such as optional wrapping) can be discussed and added on top of a first implementation.

Just as a remark to the multi-dimentional spaces: Creating a multi-dimensional memory view (aka. "deliniarization") is already happening (for simple cases) in the memory analysis (which I did not yet publish). Conceptually that should be the place for such an "analysis". If we would allow multi-dimensional output spaces then to represent vector values which are actually multi-dimensional values.

Fair point! Well taken.

Best,
Tobias

[fhahn]

I think it would be easier to review if you would create a separate patch that adds isl and then have a patch with just the files for PolyhedralValueInfo & co.

[etherzhhb]

include/llvm/Analysis/PValue.h

42–46

Why PVBase need to be friend with these class?

maybe we could make getIslCtx and getSpace as protected function instead?

include/llvm/Analysis/PValue.h

+//===- PValue.h -------- isl C++ interface and wrapper --------*- C++ -*---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// High-level interface for the genration and manipulation of polyhedral values
+// (PV) with an isl backedn. Abstractions for sets (isl_set -> PVSet), maps
+// (isl_map -> PVMap) and piece-wise affine functions (isl_pw_aff -> PVAff)
+// exist. Memory managment and space adjustments happen automatically.
+//
+// Parts of the code and ideas have been ported from the Polly [0] project.
+//
+// [0] http://polly.llvm.org/
+//
+// NOTE: This is a work in progress and therefor not a stable interface.
+//
+// TODO: Comments and descriptions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_PVALUE_H
+#define LLVM_SUPPORT_PVALUE_H
+
+#include "llvm/IR/Instructions.h"
+#include "llvm/Support/raw_ostream.h"
+
+struct isl_id;
+struct isl_ctx;
+struct isl_set;
+struct isl_map;
+struct isl_space;
+struct isl_pw_aff;
+
+namespace llvm {
+class PVAff;
+
+class PVBase {
+  friend class PVAff;
+  friend class PVMap;
+  friend class PVCtx;
+  friend class PVSet;
+  friend class PVId;
+
+  virtual isl_ctx *getIslCtx() const = 0;
+  virtual isl_space *getSpace() const = 0;
+
+public:
+  virtual std::string str() const;
+
+  virtual bool isComplex() const { return false; }
+
+  virtual operator bool() const = 0;
+
+  /// Return @p Prefix + @p Middle + @p Suffix but Isl compatible.
+  static std::string getIslCompatibleName(const std::string &Prefix,
+                                          const std::string &Middle,
+                                          const std::string &Suffix);
+};
+
+class PVCtx : public PVBase {
+  isl_ctx *Obj;
+
+public:
+  PVCtx();
+  PVCtx(isl_ctx *Ctx) : Obj(Ctx) {}
+  PVCtx(const PVCtx &Other) : Obj(Other.Obj) {}
+
+  isl_ctx *getIslCtx() const { return Obj; }
+  isl_space *getSpace() const;
+
+  std::string str() const;
+  operator bool() const { return Obj != nullptr; }
+};
+
+
+class PVId : public PVBase {
+  friend class PVAff;
+  friend class PVMap;
+  friend class PVSet;
+
+  isl_id *Obj;
+
+  operator isl_id *() const;
+
+public:
+  PVId() : Obj(nullptr) {}
+  PVId(isl_id *Obj) : Obj(Obj) {}
+  PVId(const PVId &Other);
+  PVId(PVId &&Other);
+  PVId(const PVBase &Base, const std::string &Name, void *Payload = nullptr);
+
+  ~PVId();
+
+  PVId &operator=(const PVId &Other);
+  PVId &operator=(PVId &&Other);
+
+  void *getPayload() const;
+  template <typename T> T getPayloadAs() const {
+    return static_cast<T>(getPayload());
+  }
+
+  isl_ctx *getIslCtx() const;
+  isl_space *getSpace() const;
+  std::string str() const;
+
+  operator bool() const { return Obj != nullptr; }
+};
+
+
+class PVSet : public PVBase {
+  friend class PVAff;
+  friend class PVMap;
+
+  isl_set *Obj;
+
+  operator isl_set *() const;
+
+protected:
+
+  isl_ctx *getIslCtx() const;
+  isl_space *getSpace() const;
+
+public:
+
+  PVSet() : Obj(nullptr) {}
+  PVSet(const PVSet &Other);
+  PVSet(PVSet &&Other) : Obj(Other.Obj) { Other.Obj = nullptr; }
+
+  static PVSet createParameterRange(const PVId &Id, int LowerBound,
+                                    int UpperBound);
+
+  PVSet(isl_set *S);
+
+  ~PVSet();
+
+  PVSet &operator=(const PVSet &Other);
+  PVSet &operator=(PVSet &&Other);
+  operator bool() const { return Obj != nullptr; }
+
+  /// Return the number of dimensions of this set.
+  size_t getNumDimensions() const;
+
+  /// Return the number of parameters of this set.
+  size_t getNumParameters() const;
+
+  bool isEmpty() const;
+  bool isUniverse() const;
+  bool isBounded() const;
+
+  int getParameterPosition(const PVId &Id) const;
+
+  bool hasLowerBoundForParam(const PVId &Id);
+  PVSet &minForParam(const PVId &Id);
+
+  void dropUnusedParameters();
+
+  PVSet &simplify(const PVSet &S);
+  PVSet &simplifyParameters(const PVSet &S);
+
+  /// Unify this set inplace with @p S.
+  PVSet &unify(const PVSet &S);
+
+  /// Subtract ...
+  PVSet &subtract(const PVSet &S);
+
+  /// Intersect this set inplace with @p S.
+  PVSet &intersect(const PVSet &S);
+
+  ///
+  PVSet &complement();
+
+  PVSet &maxInLastInputDims(unsigned Dims);
+
+  PVSet &addInputDims(unsigned Dims);
+  PVSet &dropFirstInputDims(unsigned Dims);
+  PVSet &dropLastInputDims(unsigned Dims);
+  PVSet &dropDimsFrom(unsigned FirstDim);
+  PVSet &fixInputDim(unsigned Dim, int64_t Value);
+  PVSet &equateInputDim(unsigned Dim, const PVId &Id);
+  PVSet &setInputLowerBound(unsigned Dim, int64_t Value);
+
+  PVSet &preimage(const PVAff &PWA);
+  PVSet &projectParameter(const PVId &Id);
+
+  PVSet &getNextIteration(unsigned Dim);
+  PVSet &getNextIterations(unsigned Dim);
+
+  PVId getParameter(unsigned No) const;
+  void getParameters(SmallVectorImpl<PVId> &Parameters) const;
+  void getParameters(SmallVectorImpl<llvm::Value *> &Parameters) const;
+
+  static PVSet empty(const PVBase &Base);
+  static PVSet empty(const PVBase &Base, unsigned Dims);
+  static PVSet universe(const PVBase &Base);
+
+  static PVSet unify(const PVSet &S0, const PVSet &S1);
+  static PVSet intersect(const PVSet &S0, const PVSet &S1);
+
+  std::string str() const;
+};
+
+
+class PVMap : public PVBase {
+  friend class PVAff;
+  friend class PVSet;
+
+  isl_map *Obj;
+
+  operator isl_map *() const;
+
+protected:
+  isl_ctx *getIslCtx() const;
+  isl_space *getSpace() const;
+
+public:
+
+  PVMap() : Obj(nullptr) {}
+  PVMap(const PVMap &Other);
+  PVMap(PVMap &&Other) : Obj(Other.Obj) { Other.Obj = nullptr; }
+  PVMap(ArrayRef<PVAff> Affs, const PVId &Id);
+  PVMap(const PVAff &Aff, long Factor);
+  PVMap(const PVId &ValId, const PVId &InputId = PVId(),
+        const PVId &OutputId = PVId());
+
+  PVMap(isl_map *M);
+
+  ~PVMap();
+
+  PVMap &operator=(const PVMap &Other);
+  PVMap &operator=(PVMap &&Other);
+  operator bool() const { return Obj != nullptr; }
+
+  bool isEmpty() const;
+
+  /// Return the number of input dimensions of this function.
+  size_t getNumInputDimensions() const;
+
+  /// Return the number of output dimensions of this function.
+  size_t getNumOutputDimensions() const;
+
+  /// Return the number of parameters of this function.
+  size_t getNumParameters() const;
+
+  /// Use the intersection of the domain with the set @p S as new domain.
+  ///
+  /// @param Dom The set to intersect the domain with.
+  ///
+  /// @returns A reference to this object (*this).
+  PVMap &intersectDomain(const PVSet &Dom);
+
+  PVMap &intersect(const PVMap &Other);
+
+  PVMap &addToOutputDimension(const PVMap &Other, unsigned Dim);
+
+  int getParameterPosition(const PVId &Id) const;
+  void eliminateParameter(const PVId &Id);
+
+  PVSet getParameterSet() const;
+
+  PVId getParameter(unsigned No) const;
+
+  PVId getInputId() const;
+  PVId getOutputId() const;
+
+  void dropUnusedParameters();
+
+  void getParameters(SmallVectorImpl<PVId> &Parameters) const;
+  void getParameters(SmallVectorImpl<llvm::Value *> &Parameters) const;
+
+  void simplify(const PVAff &Aff);
+
+  using IslCombinatorFn = std::function<isl_map *(isl_map *, isl_map *)>;
+  using CombinatorFn = std::function<PVMap (const PVMap &, const PVMap &)>;
+  static CombinatorFn getCombinatorFn(IslCombinatorFn Fn);
+
+  PVMap &union_add(const PVMap &PM);
+  PVMap &floordiv(int64_t V);
+
+  std::string str() const;
+};
+
+class PVAff : public PVBase {
+  friend class PVMap;
+  friend class PVSet;
+
+  isl_pw_aff *Obj;
+
+  operator isl_pw_aff *() const;
+
+protected:
+  isl_ctx *getIslCtx() const;
+  isl_space *getSpace() const;
+
+public:
+
+  /// Constructors
+  ///{
+  PVAff() : Obj(nullptr) {}
+  PVAff(isl_pw_aff *Obj) : Obj(Obj) {}
+  PVAff(const PVAff &Other);
+  PVAff(PVAff &&Other) : Obj(Other.Obj) { Other.Obj = nullptr; }
+  PVAff(const PVId &Id);
+  PVAff(const PVBase &Base, int64_t ConstVal);
+  PVAff(const PVSet &S);
+  PVAff(const PVSet &S, int64_t ConstVal);
+  PVAff(const PVBase &Base, unsigned CoeffPos, int64_t CoeffVal, const PVId &Id);
+  ///}
+
+  ~PVAff();
+
+  bool operator==(const PVAff &Other);
+  bool operator!=(const PVAff &Other) { return !(*this == Other); }
+
+  PVAff &operator=(const PVAff &Other);
+  PVAff &operator=(PVAff &&Other);
+  operator bool() const { return Obj != nullptr; }
+
+  /// Return the number of input dimensions of this function.
+  size_t getNumInputDimensions() const;
+
+  /// Return the number of output dimensions of this function.
+  size_t getNumOutputDimensions() const;
+
+  /// Return the number of parameters of this function.
+  size_t getNumParameters() const;
+
+  /// Return the number of pieces
+  size_t getNumPieces() const;
+
+  bool isComplex() const;
+  bool isConstant() const;
+
+  int getParameterPosition(const PVId &Id) const;
+  bool involvesId(const PVId &Id) const;
+
+  void addInputDims(unsigned Dims);
+  void insertInputDims(unsigned Pos, unsigned Dims);
+  void dropInputDim(unsigned Dim);
+  void dropLastInputDims(unsigned Dims);
+  void dropParameter(const PVId &Id);
+  void dropUnusedParameters();
+
+  PVId getParameter(unsigned No) const;
+  void getParameters(SmallVectorImpl<PVId> &Parameters) const;
+  void getParameters(SmallVectorImpl<llvm::Value *> &Parameters) const;
+
+  PVAff extractFactor(const PVAff &Aff) const;
+  int getFactor(const PVAff &Aff) const;
+
+  PVAff &add(const PVAff &PV);
+  PVAff &sub(const PVAff &PV);
+  PVAff &multiply(const PVAff &PV);
+  PVAff &union_add(const PVAff &PV);
+
+  PVAff &select(const PVAff &PV0, const PVAff &PV1);
+
+  PVAff &fixParamDim(unsigned Dim, int64_t Value);
+  PVAff &fixInputDim(unsigned Dim, int64_t Value);
+  PVAff &setInputLowerBound(unsigned Dim, int64_t Value);
+  PVAff &floordiv(int64_t V);
+
+  PVSet zeroSet() const;
+  PVSet nonZeroSet() const;
+
+  PVAff getParameterCoeff(const PVId &Id);
+  PVAff perPiecePHIEvolution(const PVId &Id, int LD) const;
+
+  /// Use the intersection of the domain with the set @p S as new domain.
+  ///
+  /// @param Dom The set to intersect the domain with.
+  ///
+  /// @returns A reference to this object (*this).
+  PVAff &intersectDomain(const PVSet &Dom);
+
+  PVAff &simplify(PVSet &S);
+
+  PVSet getLessThanDomain(const PVAff &Aff) const;
+  PVSet getLessEqualDomain(const PVAff &Aff) const;
+  PVSet getGreaterEqualDomain(const PVAff &Aff) const;
+  PVSet getDomain() const;
+
+  static PVAff getExpPWA(const PVAff &PWA);
+  static PVAff createAdd(const PVAff &LHS, const PVAff &RHS);
+  static PVAff createUnionAdd(const PVAff &LHS, const PVAff &RHS);
+  static PVAff createSub(const PVAff &LHS, const PVAff &RHS);
+  static PVAff createMultiply(const PVAff &LHS, const PVAff &RHS);
+  static PVAff createSDiv(const PVAff &LHS, const PVAff &RHS);
+  static PVAff createShiftLeft(const PVAff &LHS, const PVAff &RHS);
+  static PVAff createSelect(const PVAff &CondPV, const PVAff &TruePV,
+                            const PVAff &FalsePV);
+
+  /// Create the conditions under which @p L @p Pred @p R is true.
+  static PVSet buildConditionSet(ICmpInst::Predicate Pred, const PVAff &PV0,
+                                 const PVAff &PV1);
+
+  /// The function type that is needed to combine two polyhedral
+  /// representations.
+  using IslCombinatorFn = std::function<isl_pw_aff *(isl_pw_aff *, isl_pw_aff *)>;
+  using CombinatorFn = std::function<PVAff (const PVAff &, const PVAff &)>;
+  static CombinatorFn getCombinatorFn(IslCombinatorFn Fn);
+
+  std::string str() const;
+};
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const PVBase &PV);
+
+} // end namespace llvm
+
+#endif // LLVM_SUPPORT_PVALUE_H

include/llvm/Analysis/PolyhedralValueInfo.h

+//===--- PolyhedralValueInfo.h -- Polyhedral value analysis -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Analysis to create polyhedral abstractions for values, instructions and
+// iteration domains. These abstractions are parametric, piece-wise affine
+// functions with loop-iteration granularity.
+//
+// Parts of the code and ideas have been ported from the Polly [0] project.
+//
+// [0] http://polly.llvm.org/
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLYHEDRAL_VALUE_INFO_H
+#define POLYHEDRAL_VALUE_INFO_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/PValue.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class PolyhedralValueInfo;
+class PolyhedralExpressionBuilder;
+
+/// Polyhedral representation of a value (or basic block) in a scope. The values
+/// are expressed with regards to loop iterations. The scope defines which loop
+/// iterations are represented explicitly and which are kept parametric.
+///
+/// For the value of j in following two dimensional loop nest there are three
+/// different PEXP values depending on the scope.
+///
+/// for (i = 0; i < N; j++)
+///   for (j = i; j < 2*i; j++)
+///     S(i, j);
+///
+/// Scope    | Polyhedral representation of j   | Description
+/// ----------------------------------------------------------------------------
+/// j-loop   | [j] -> { []      -> [(j)] }      | Unconstrained parametric value
+///          |                                  | in one iteration of the j-loop
+/// i-loop   | [i] -> { [l1]    -> [(i + l1)] } | Parametric value of i plus the
+///          |                                  | current loop iteration (j) of
+///          |                                  | the innermost loop
+/// max/none | [] -> { [l0, l1] -> [(l0 + l1)]} | Sum of the current iterations
+///          |                                  | in the i-loop and j-loop
+///            /\       /\           /\
+///            ||       ||           ||
+///       parameters    ||          value
+///                loop iterations
+///
+/// The domain of S in the above example also depends on the scope and can be
+/// one of the following:
+///
+/// Scope    | Polyhedral representation of the domain of S
+/// ----------------------------------------------------------------------------
+/// j-loop   | []  -> { []       -> [(1)] }
+/// i-loop   | [i] -> { [l0]     -> [(1)] : 0 <= i0 < i }
+/// max/none | [N] -> { [l0, l1] -> [(1)] : 0 <= i1 < i0 and i0 < N }
+///
+///            /\       /\           /\         /\
+///            ||       ||           ||         ||
+///       parameters    ||     (fixed) value    ||
+///                loop iterations          constraints
+///
+/// Note that iterations are always "normalized", thus they are expressed as a
+/// range from 0 to the number of iterations. The value part of the polyhedral
+/// representation will compensate for non-zero initial values or strides not
+/// equal to one.
+///
+/// If a scope loop is given, the PEXP will not contain information about any
+/// expressions outside that loop. Otherwise, the PEXP will represent all
+/// expressions that influence the value in question until the representation
+/// would become non-affine. Instead of a non-affine (thus invalid) result the
+/// non-affine part is represented as a parameter.
+///
+/// TODO: Describe invalid and known domain.
+///
+class PEXP {
+public:
+  /// The possible kinds for a polyhedral expression.
+  enum ExpressionKind {
+    EK_NONE,          ///<= An unspecified, not yet initialized, value.
+    EK_INTEGER,       ///<= A (piece-wise defined) integer value.
+    EK_UNKNOWN_VALUE, ///<= An unknown (parametric) or changing (loop iv) value.
+    EK_DOMAIN,        ///<= A domain value that evaluates to one if the basic
+                      ///   block is executed.
+    EK_NON_AFFINE,    ///<= A non-affine, thus invalid, value.
+  };
+
+  /// Create a new, uninitialized polyhedral expression for @p Val.
+  PEXP(Value *Val, Loop *Scope) : Kind(EK_NONE), Val(Val), Scope(Scope) {
+    assert(Val);
+  }
+
+  /// Return the value this PEXP represents.
+  Value *getValue() const { return Val; }
+
+  /// Return the scope in which this PEXP is expressed.
+  Loop *getScope() const { return Scope; }
+
+  /// Assign the combination of @p PE0 and @p PE1 using @p Combinator.
+  PEXP *assign(const PEXP *PE0, const PEXP *PE1,
+               PVAff::CombinatorFn Combinator);
+  PEXP *assign(const PEXP *PE0, const PEXP *PE1,
+               PVAff::IslCombinatorFn Combinator);
+
+  /// Return the polyhedral piece-wise affine function.
+  const PVAff &getPWA() const { return PWA; }
+  PVAff &getPWA() { return PWA; }
+
+  /// Return the domain for which this PEXP is defined.
+  PVSet getDomain() const { return getPWA().getDomain(); }
+
+  /// Return the invalid domain which this PEXP is undefined.
+  const PVSet &getInvalidDomain() const { return InvalidDomain; }
+
+  /// Return the known constraints about this PEXP.
+  const PVSet &getKnownDomain() const { return KnownDomain; }
+
+  /// Return the expression kind of this PEXP.
+  ExpressionKind getKind() const { return this->Kind; }
+
+  /// Return true if this polyhedral representation has been initialized.
+  bool isInitialized() const { return Kind != EK_NONE; }
+
+  /// Print this polyhedral representation to @p OS.
+  void print(raw_ostream &OS) const;
+
+  /// Dump this polyhedral representation to the dbgs() stream.
+  void dump() const;
+
+private:
+  /// Assignment and move-assignment operator.
+  PEXP &operator=(PEXP &&PE);
+  PEXP &operator=(const PEXP &PE);
+
+  /// The kind of this polyhedral expression.
+  ExpressionKind Kind;
+
+  /// The llvm value that is represented by this polyhedral expression.
+  Value *const Val;
+
+  /// The scope of this polyhedral expression.
+  Loop *const Scope;
+
+  /// The value represented as (p)iece-(w)ise (a)ffine function.
+  PVAff PWA;
+
+  /// The domain under which the representation is invalid.
+  PVSet InvalidDomain;
+
+  /// The domain containing known constraints.
+  PVSet KnownDomain;
+
+  /// Combine the invalid and known domain of @p PE with this PEXP.
+  ///
+  /// @param PE The polyhedral representation to combine.
+  PEXP *combine(const PEXP *PE);
+
+  /// Combine the polyhedral representation @p PE restricted to the domain
+  /// @p Domain into this one using @p Combinator as a combinator function.
+  ///
+  /// @param PE         The polyhedral representation to combine.
+  /// @param Combinator The combinator function.
+  /// @param Domain     The domain for which @p PEXP will be combined.
+  PEXP *combine(const PEXP *PE, PVAff::CombinatorFn Combinator,
+                const PVSet *Domain = nullptr);
+  PEXP *combine(const PEXP *PE, PVAff::IslCombinatorFn Combinator,
+                const PVSet *Domain = nullptr);
+
+  /// Include the constraints in @p ID in the invalid domain.
+  void addInvalidDomain(const PVSet &ID);
+
+  /// Include the constraints in @p KD in the known domain.
+  void addKnownDomain(const PVSet &KD);
+
+  /// Assign @p Domain as the domain of this PEXP and change the kind to
+  /// EK_DOMAIN.
+  PEXP *setDomain(const PVSet &Domain, bool Overwrite = false);
+
+  /// Set the expression kind to @p Kind.
+  void setKind(ExpressionKind Kind) { this->Kind = Kind; }
+
+  /// Add the overflow behaviour to the invalid (or known) domain depending on
+  /// the nsw tag of the underlying computation.
+  void adjustInvalidAndKnownDomain();
+
+  /// Invalidate this PEXP.
+  PEXP *invalidate();
+
+  friend class PolyhedralValueInfo;
+  friend class PolyhedralExpressionBuilder;
+};
+
+/// A cache that maps values/basic blocks and scopes to the computed polyhedral
+/// representation (PEXP). The results for maximal scopes (nullptr) can be used
+/// in an inter-procedural setting.
+class PolyhedralValueInfoCache final {
+
+  /// Mapping from basic blocks to their domain expressed as a PEXP.
+  using DomainMapKey = std::pair<BasicBlock *, Loop *>;
+  DenseMap<DomainMapKey, PEXP *> DomainMap;
+
+  /// Mapping from values to their polyhedral representation.
+  using ValueMapKey = std::pair<Value *, Loop *>;
+  DenseMap<ValueMapKey, PEXP *> ValueMap;
+
+  /// Mapping from parameter values to their unique id.
+  DenseMap<Value *, PVId> ParameterMap;
+
+  /// Return or create and cache a PEXP for @p BB in @p Scope.
+  PEXP *getOrCreateDomain(BasicBlock &BB, Loop *Scope) {
+    auto *&PE = DomainMap[{&BB, Scope}];
+    if (!PE)
+      PE = new PEXP(&BB, Scope);
+
+    // Verify the internal state
+    assert(PE == lookup(BB, Scope));
+    return PE;
+  }
+
+  /// Return or create and cache a PEXP for @p V in @p Scope.
+  PEXP *getOrCreatePEXP(Value &V, Loop *Scope) {
+    auto *&PE = ValueMap[{&V, Scope}];
+    if (!PE)
+      PE = new PEXP(&V, Scope);
+
+    // Verify the internal state
+    assert(PE == lookup(V, Scope));
+    return PE;
+  }
+
+  /// Return the unique parameter id for @p V.
+  PVId getParameterId(Value &V, const PVCtx &Ctx);
+
+  friend class PolyhedralExpressionBuilder;
+
+public:
+  ~PolyhedralValueInfoCache() { releaseMemory(); }
+
+  /// Return the cached polyhedral representation of @p V in @p Scope, if any.
+  PEXP *lookup(Value &V, Loop *Scope) { return ValueMap.lookup({&V, Scope}); }
+
+  /// Return the cached polyhedral representation of @p BB in @p Scope, if any.
+  PEXP *lookup(BasicBlock &BB, Loop *Scope) {
+    return DomainMap.lookup({&BB, Scope});
+  }
+
+  /// Forget the value for @p BB in @p Scope. Returns true if there was one.
+  bool forget(BasicBlock &BB, Loop *Scope) {
+    return DomainMap.erase({&BB, Scope});
+  }
+
+  /// Forget the value for @p V in @p Scope. Returns true if there was one.
+  bool forget(Value &V, Loop *Scope) {
+    return ValueMap.erase({&V, Scope});
+  }
+
+  /// Iterators for polyhedral representation of values.
+  ///{
+  using iterator = decltype(ValueMap)::iterator;
+  using const_iterator = decltype(ValueMap)::const_iterator;
+
+  iterator begin() { return ValueMap.begin(); }
+  iterator end() { return ValueMap.end(); }
+  const_iterator begin() const { return ValueMap.begin(); }
+  const_iterator end() const { return ValueMap.end(); }
+
+  iterator_range<iterator> values() { return make_range(begin(), end()); }
+  iterator_range<const_iterator> values() const {
+    return make_range(begin(), end());
+  }
+  ///}
+
+  /// Iterators for polyhedral domains of basic block.
+  ///{
+  using domain_iterator = decltype(DomainMap)::iterator;
+  using const_domain_iterator = decltype(DomainMap)::const_iterator;
+
+  domain_iterator domain_begin() { return DomainMap.begin(); }
+  domain_iterator domain_end() { return DomainMap.end(); }
+  const_domain_iterator domain_begin() const { return DomainMap.begin(); }
+  const_domain_iterator domain_end() const { return DomainMap.end(); }
+
+  iterator_range<domain_iterator> domains() {
+    return make_range(domain_begin(), domain_end());
+  }
+  iterator_range<const_domain_iterator> domains() const {
+    return make_range(domain_begin(), domain_end());
+  }
+  ///}
+
+  /// Clear all cached information.
+  void releaseMemory();
+};
+
+/// Analysis to create polyhedral abstractions for values, instructions and
+/// iteration domains.
+class PolyhedralValueInfo {
+  /// The (shared) context in which the polyhedral values are build.
+  PVCtx Ctx;
+
+  /// The loop information for the function we are currently analyzing.
+  LoopInfo &LI;
+
+  /// The polyhedral expression builder.
+  PolyhedralExpressionBuilder *PEBuilder;
+
+  friend class PolyhedralExpressionBuilder;
+
+public:
+  /// Constructor
+  PolyhedralValueInfo(PVCtx Ctx, LoopInfo &LI);
+
+  ~PolyhedralValueInfo();
+
+  /// Return the polyhedral expression of @p V in @p Scope.
+  const PEXP *getPEXP(Value *V, Loop *Scope = nullptr);
+
+  /// Return the domain of @p BB as polyhedral expression in @p Scope.
+  const PEXP *getDomainFor(BasicBlock *BB, Loop *Scope = nullptr);
+
+  /// Return the internal context used.
+  const PVCtx &getCtx() const { return Ctx; }
+
+  /// Return the unique parameter id for @p V.
+  PVId getParameterId(Value &V);
+
+  /// Return true if @p PE represents an unknown (parametric) value.
+  bool isUnknown(const PEXP *PE) const;
+
+  /// Return true if @p PE represents an integer value.
+  ///
+  /// As PEXP allow for piecewise representation, integer does not necessarily
+  /// mean constant. An example would be
+  ///   %int = phi i32 [5, %b0], [7, %b1]
+  /// which is an integer value but not a constant one.
+  bool isInteger(const PEXP *PE) const;
+
+  /// Return true if @p PE represents a constant value.
+  bool isConstant(const PEXP *PE) const;
+
+  /// Return true if @p PE represents an affine value.
+  bool isAffine(const PEXP *PE) const;
+
+  /// Return true if @p PE represents a non-affine value.
+  bool isNonAffine(const PEXP *PE) const;
+
+  /// Return true if @p PE represents a value that is fixed for one iteration of
+  /// @p Scope. Thus @p PE is not parametric in an instruction in @p Scope.
+  bool hasScope(const PEXP *PE, Loop *Scope) const;
+
+  /// Return true if @p PE represents a value that is fixed for one function
+  /// invocation, thus @p PE is not parametric in any llvm::Instruction.
+  bool hasFunctionScope(const PEXP *PE) const;
+
+  /// Return the unknown ids referenced by @p PE  in @p Values.
+  void getParameters(const PEXP *PE, SmallVectorImpl<PVId> &Values) const;
+
+  /// Return the unknown values referenced by @p PE  in @p Values.
+  void getParameters(const PEXP *PE, SmallVectorImpl<Value *> &Values) const;
+
+  /// Return true if the @p Pred relation between @p LHS and @p RHS is known to
+  /// hold at @p IP with regards to @p Scope.
+  ///
+  /// TODO: Specify constrains on @p IP wrt. @p LHS and @p RHS.
+  bool isKnownToHold(Value *LHS, Value *RHS, ICmpInst::Predicate Pred,
+                     Instruction *IP = nullptr, Loop *Scope = nullptr);
+
+  /// Print some statistics to @p OS.
+  void print(raw_ostream &OS) const;
+};
+
+/// Wrapper pass for PolyhedralValueInfo on a per-function basis.
+class PolyhedralValueInfoWrapperPass : public FunctionPass {
+  /// The (shared) context in which the polyhedral values are build.
+  PVCtx Ctx;
+
+  PolyhedralValueInfo *PI;
+  Function *F;
+
+public:
+  static char ID;
+  PolyhedralValueInfoWrapperPass()
+      : FunctionPass(ID), PI(nullptr), F(nullptr) {}
+
+  /// Return the PolyhedralValueInfo object for the current function.
+  PolyhedralValueInfo &getPolyhedralValueInfo() {
+    assert(PI);
+    return *PI;
+  }
+
+  /// @name Pass interface
+  //@{
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const override;
+  virtual void releaseMemory() override;
+  virtual bool runOnFunction(Function &F) override;
+  //@}
+
+  virtual void print(raw_ostream &OS, const Module *) const override;
+  void dump() const;
+};
+
+/// Analysis wrapper for the PolyhedralValueInfo in the new pass manager.
+class PolyhedralValueInfoAnalysis
+    : public AnalysisInfoMixin<PolyhedralValueInfoAnalysis> {
+  friend AnalysisInfoMixin<PolyhedralValueInfoAnalysis>;
+  static AnalysisKey Key;
+
+  /// The (shared) context in which the polyhedral values are build.
+  PVCtx Ctx;
+
+public:
+  /// \brief Provide the result typedef for this analysis pass.
+  typedef PolyhedralValueInfo Result;
+
+  /// \brief Run the analysis pass over a function and produce BFI.
+  Result run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// Stream operators to pretty print polyhedral expressions (PEXP)
+///
+///{
+raw_ostream &operator<<(raw_ostream &OS, PEXP::ExpressionKind Kind);
+raw_ostream &operator<<(raw_ostream &OS, const PEXP *PE);
+raw_ostream &operator<<(raw_ostream &OS, const PEXP &PE);
+///}
+
+} // namespace llvm
+#endif

lib/Analysis/PValue.cpp

+//===- PValue.cpp ------ isl C++ interface wrapper ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// TODO Add comments to this implementation!
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/PValue.h"
+
+#include "isl/aff.h"
+#include "isl/id.h"
+#include "isl/map.h"
+#include "isl/set.h"
+#include "isl/constraint.h"
+#include "isl/options.h"
+
+#define DEBUG_TYPE "pvalue"
+
+using namespace llvm;
+
+static int DOMAIN_N_BASIC_SEK_TRESHOLD = 10;
+static int PWA_N_PIECE_TRESHOLD = 4;
+
+
+static void replace(std::string &str, const std::string &find,
+                    const std::string &replace) {
+  size_t pos = 0;
+  while ((pos = str.find(find, pos)) != std::string::npos) {
+    str.replace(pos, find.length(), replace);
+    pos += replace.length();
+  }
+}
+
+static void makeIslCompatible(std::string &str) {
+  replace(str, ".", "_");
+  replace(str, "\"", "_");
+  replace(str, " ", "__");
+  replace(str, "=>", "TO");
+}
+
+/// Create a map to map from a given iteration to a subsequent iteration.
+///
+/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
+/// is incremented by one and all other dimensions are equal, e.g.,
+///             [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
+///
+/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
+static __isl_give isl_map *
+createNextIterationMap(__isl_take isl_space *SetSpace, unsigned Dim, bool All) {
+  auto *MapSpace = isl_space_map_from_set(SetSpace);
+  auto *NextIterationMap = isl_map_universe(isl_space_copy(MapSpace));
+  for (unsigned u = 0; u < isl_map_dim(NextIterationMap, isl_dim_in); u++)
+    if (u != Dim)
+      NextIterationMap =
+          isl_map_equate(NextIterationMap, isl_dim_in, u, isl_dim_out, u);
+  isl_constraint *C;
+  if (All) {
+    C = isl_constraint_alloc_inequality(isl_local_space_from_space(MapSpace));
+    C = isl_constraint_set_constant_si(C, -1);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_in, Dim, -1);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_out, Dim, 1);
+  } else {
+    C = isl_constraint_alloc_equality(isl_local_space_from_space(MapSpace));
+    C = isl_constraint_set_constant_si(C, 1);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_in, Dim, 1);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_out, Dim, -1);
+  }
+  NextIterationMap = isl_map_add_constraint(NextIterationMap, C);
+  return NextIterationMap;
+}
+
+std::string PVBase::getIslCompatibleName(const std::string &Prefix,
+                                         const std::string &Middle,
+                                         const std::string &Suffix) {
+  std::string S = Prefix + Middle + Suffix;
+  makeIslCompatible(S);
+  return S;
+}
+
+std::string PVBase::str() const {
+  llvm_unreachable("PVBase::str() should be overloaded!");
+}
+
+/* -------------------- PVCtx ------------------------- */
+
+PVCtx::PVCtx() : PVCtx(isl_ctx_alloc()) {
+  isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
+}
+
+isl_space *PVCtx::getSpace() const {
+  return isl_space_set_alloc(getIslCtx(), 0, 0);
+}
+
+std::string PVCtx::str() const {
+  return "PVCTX";
+}
+
+/* -------------------- PVId ------------------------- */
+
+PVId::PVId(const PVBase &Base, const std::string &Name, void *Payload)
+    : Obj(isl_id_alloc(Base.getIslCtx(), Name.c_str(), Payload)) {}
+PVId::PVId(const PVId &Other) : Obj(isl_id_copy(Other.Obj)) {}
+PVId::PVId(PVId &&Other) : Obj(Other.Obj) { Other.Obj = nullptr; }
+
+PVId::~PVId() { isl_id_free(Obj); }
+
+PVId &PVId::operator=(const PVId &Other) {
+  if (this != &Other) {
+    isl_id_free(Obj);
+    Obj = isl_id_copy(Other.Obj);
+  }
+  return *this;
+}
+
+PVId &PVId::operator=(PVId &&Other) {
+  if (this != &Other) {
+    Obj = isl_id_free(Obj);
+    std::swap(Obj, Other.Obj);
+  }
+  return *this;
+}
+
+PVId::operator isl_id *() const { return isl_id_copy(Obj); }
+
+void *PVId::getPayload() const {
+  return isl_id_get_user(Obj);
+}
+
+isl_ctx *PVId::getIslCtx() const { return isl_id_get_ctx(Obj); }
+
+isl_space *PVId::getSpace() const {
+  return isl_space_set_alloc(getIslCtx(), 0, 0);
+}
+
+std::string PVId::str() const {
+  const char *cstr = isl_id_get_name(Obj);
+  if (!cstr)
+    return "null";
+  std::string Result(cstr);
+  return Result;
+}
+
+/* -------------------- PVSet ------------------------ */
+
+PVSet::PVSet(isl_set *S) : Obj(S) {}
+PVSet::PVSet(const PVSet &Other) : Obj(isl_set_copy(Other.Obj)) {}
+
+PVSet PVSet::createParameterRange(const PVId &Id, int LowerBound,
+                                  int UpperBound) {
+  PVSet ParamRange = universe(Id);
+  ParamRange.Obj = isl_set_add_dims(ParamRange.Obj, isl_dim_param, 1);
+  ParamRange.Obj = isl_set_set_dim_id(ParamRange.Obj, isl_dim_param, 0, Id);
+  ParamRange.Obj =
+      isl_set_lower_bound_si(ParamRange.Obj, isl_dim_param, 0, LowerBound);
+  ParamRange.Obj =
+      isl_set_upper_bound_si(ParamRange.Obj, isl_dim_param, 0, UpperBound);
+  return ParamRange;
+}
+
+PVSet::~PVSet() { isl_set_free(Obj); }
+
+PVSet &PVSet::operator=(const PVSet &Other) {
+  if (this != &Other) {
+    isl_set_free(Obj);
+    Obj = isl_set_copy(Other.Obj);
+  }
+  return *this;
+}
+
+PVSet &PVSet::operator=(PVSet &&Other) {
+  if (this != &Other) {
+    Obj = isl_set_free(Obj);
+    std::swap(Obj, Other.Obj);
+  }
+  return *this;
+}
+
+PVSet::operator isl_set *() const { return isl_set_copy(Obj); }
+
+isl_ctx *PVSet::getIslCtx() const { return isl_set_get_ctx(Obj); }
+
+isl_space *PVSet::getSpace() const { return isl_set_get_space(Obj); }
+
+size_t PVSet::getNumDimensions() const { return isl_set_n_dim(Obj); }
+
+size_t PVSet::getNumParameters() const { return isl_set_n_param(Obj); }
+
+bool PVSet::isEmpty() const { return isl_set_is_empty(Obj); }
+bool PVSet::isUniverse() const {
+  isl_set *C = isl_set_complement(isl_set_copy(Obj));
+  bool U = isl_set_is_empty(C);
+  isl_set_free(C);
+  return U;
+}
+bool PVSet::isBounded() const { return isl_set_is_bounded(Obj); }
+
+int PVSet::getParameterPosition(const PVId &Id) const {
+  int Pos = isl_set_find_dim_by_id(Obj, isl_dim_param, Id);
+  return Pos;
+}
+
+bool PVSet::hasLowerBoundForParam(const PVId &Id) {
+  int Pos = getParameterPosition(Id);
+  if (Pos < 0)
+    return false;
+  return isl_set_dim_has_any_lower_bound(Obj, isl_dim_param, Pos);
+}
+
+PVSet &PVSet::minForParam(const PVId &Id) {
+  int Pos = getParameterPosition(Id);
+  assert(Pos >= 0);
+  assert(isl_set_is_params(Obj));
+  Obj = isl_set_move_dims(Obj, isl_dim_set, 0, isl_dim_param, Pos, 1);
+  Obj = isl_set_lexmin(Obj);
+  return *this;
+}
+
+void PVSet::dropUnusedParameters() {
+  size_t NumParams = getNumParameters();
+  for (size_t i = 0; i < NumParams; i++) {
+    if (isl_set_involves_dims(Obj, isl_dim_param, i, 1))
+      continue;
+
+    Obj = isl_set_project_out(Obj, isl_dim_param, i, 1);
+    i--;
+    NumParams--;
+  }
+}
+
+PVSet &PVSet::simplify(const PVSet &S) {
+  Obj = isl_set_gist(Obj, S);
+  return *this;
+}
+
+PVSet &PVSet::simplifyParameters(const PVSet &S) {
+  Obj = isl_set_gist_params(Obj, S);
+  return *this;
+}
+
+PVSet &PVSet::complement() {
+  Obj = isl_set_complement(Obj);
+  Obj = isl_set_coalesce(Obj);
+  return *this;
+}
+
+static void unifySetDimensions(isl_set *&S0, isl_set *&S1) {
+  int DimDiff = isl_set_n_dim(S0) - isl_set_n_dim(S1);
+  if (DimDiff > 0)
+    S1 = isl_set_add_dims(S1, isl_dim_set, DimDiff);
+  else if (DimDiff < 0)
+    S0 = isl_set_add_dims(S0, isl_dim_set, -1 * DimDiff);
+  // S0 = isl_set_align_params(S0, isl_set_get_space(S1));
+  // S1 = isl_set_align_params(S1, isl_set_get_space(S0));
+}
+
+PVSet &PVSet::unify(const PVSet &S) {
+  if (!Obj)
+    Obj = isl_set_copy(S.Obj);
+  else if (S.Obj) {
+    isl_set *SObj = S;
+    unifySetDimensions(Obj, SObj);
+    Obj = isl_set_union(Obj, SObj);
+    Obj = isl_set_coalesce(Obj);
+  }
+  return *this;
+}
+
+PVSet &PVSet::subtract(const PVSet &S) {
+  if (!Obj)
+    Obj = isl_set_copy(S.Obj);
+  else if (S.Obj) {
+    isl_set *SObj = S;
+    unifySetDimensions(Obj, SObj);
+    Obj = isl_set_subtract(Obj, SObj);
+    Obj = isl_set_coalesce(Obj);
+  }
+  return *this;
+}
+
+PVSet &PVSet::intersect(const PVSet &S) {
+  if (!Obj)
+    Obj = isl_set_copy(S.Obj);
+  else if (S.Obj) {
+    isl_set *SObj = S;
+    if (isl_set_is_params(SObj)) {
+      Obj = isl_set_intersect_params(Obj, SObj);
+    } else {
+      unifySetDimensions(Obj, SObj);
+      Obj = isl_set_intersect(Obj, SObj);
+    }
+    Obj = isl_set_coalesce(Obj);
+  }
+  return *this;
+}
+
+PVSet PVSet::empty(const PVBase &Base) {
+  auto *Space = Base.getSpace();
+  if (isl_space_is_map(Space))
+    Space = isl_space_domain(Space);
+  return isl_set_empty(Space);
+}
+
+PVSet PVSet::empty(const PVBase &Base, unsigned Dims) {
+  auto *Space = isl_space_set_alloc(Base.getIslCtx(), 0, Dims);
+  return isl_set_empty(Space);
+}
+
+PVSet PVSet::universe(const PVBase &Base) {
+  auto *Space = Base.getSpace();
+  if (isl_space_is_map(Space))
+    Space = isl_space_domain(Space);
+  return isl_set_universe(Space);
+}
+
+PVSet PVSet::unify(const PVSet &S0, const PVSet &S1) {
+  return PVSet(S0).unify(S1);
+}
+
+PVSet PVSet::intersect(const PVSet &S0, const PVSet &S1) {
+  return PVSet(S0).intersect(S1);
+}
+
+PVSet &PVSet::maxInLastInputDims(unsigned Dims) {
+  if (Dims == 0)
+    return *this;
+  unsigned NumDims = getNumDimensions();
+  assert(NumDims >= Dims);
+  Obj = isl_set_project_out(Obj, isl_dim_set, 0, NumDims - Dims);
+  Obj = isl_set_lexmax(Obj);
+  Obj = isl_set_insert_dims(Obj, isl_dim_set, 0, NumDims - Dims);
+  return *this;
+}
+
+PVSet &PVSet::fixInputDim(unsigned Dim, int64_t Value) {
+  auto Dims = getNumDimensions();
+  if (Dims <= Dim)
+    Obj = isl_set_add_dims(Obj, isl_dim_set, Dim - Dims + 1);
+  Obj = isl_set_fix_si(Obj, isl_dim_set, Dim, Value);
+  Obj = isl_set_coalesce(Obj);
+  return *this;
+}
+
+PVSet &PVSet::equateInputDim(unsigned Dim, const PVId &Id) {
+  int Pos = isl_set_find_dim_by_id(Obj, isl_dim_param, Id);
+  assert(Pos >= 0);
+  Obj = isl_set_equate(Obj, isl_dim_param, Pos, isl_dim_set, Dim);
+  return *this;
+}
+
+PVSet &PVSet::addInputDims(unsigned Dims) {
+  Obj = isl_set_add_dims(Obj, isl_dim_set, Dims);
+  return *this;
+}
+
+PVSet &PVSet::dropFirstInputDims(unsigned Dims) {
+  Obj = isl_set_project_out(Obj, isl_dim_set, 0, Dims);
+  return *this;
+}
+
+PVSet &PVSet::dropLastInputDims(unsigned Dims) {
+  Obj = isl_set_eliminate_dims(Obj, getNumDimensions() - Dims, Dims);
+  Obj = isl_set_coalesce(Obj);
+  return *this;
+}
+
+PVSet &PVSet::dropDimsFrom(unsigned Dim) {
+  if (Dim < getNumDimensions())
+    Obj = isl_set_project_out(Obj, isl_dim_set, Dim, getNumDimensions() - Dim);
+  return *this;
+}
+
+PVSet &PVSet::setInputLowerBound(unsigned Dim, int64_t Value) {
+  auto Dims = getNumDimensions();
+  if (Dims <= Dim)
+    Obj = isl_set_add_dims(Obj, isl_dim_set, Dim - Dims + 1);
+  Obj = isl_set_lower_bound_si(Obj, isl_dim_set, Dim, Value);
+  Obj = isl_set_coalesce(Obj);
+  return *this;
+}
+
+PVSet &PVSet::preimage(const PVAff &PWA) {
+  Obj = isl_set_preimage_pw_multi_aff(Obj, isl_pw_multi_aff_from_pw_aff(PWA));
+  return *this;
+}
+
+PVSet &PVSet::projectParameter(const PVId &Id) {
+  int Pos = isl_set_find_dim_by_id(Obj, isl_dim_param, Id);
+  assert(Pos >= 0);
+  Obj = isl_set_project_out(Obj, isl_dim_param, Pos, 1);
+  return *this;
+}
+
+PVSet &PVSet::getNextIteration(unsigned Dim) {
+  isl_map *NIMap = createNextIterationMap(getSpace(), Dim, false);
+  Obj = isl_set_apply(Obj, NIMap);
+  return *this;
+}
+
+PVSet &PVSet::getNextIterations(unsigned Dim) {
+  isl_map *NIMap = createNextIterationMap(getSpace(), Dim, true);
+  Obj = isl_set_apply(Obj, NIMap);
+  return *this;
+}
+
+PVId PVSet::getParameter(unsigned No) const {
+  return PVId(isl_set_get_dim_id(Obj, isl_dim_param, No));
+}
+
+void PVSet::getParameters(SmallVectorImpl<PVId> &Parameters) const {
+  size_t NumParams = getNumParameters();
+  Parameters.reserve(Parameters.size() + NumParams);
+  for (size_t i = 0; i < NumParams; i++) {
+    if (isl_set_involves_dims(Obj, isl_dim_param, i, 1))
+      Parameters.push_back(getParameter(i));
+  }
+}
+
+void PVSet::getParameters(SmallVectorImpl<llvm::Value *> &Parameters) const {
+  size_t NumParams = getNumParameters();
+  Parameters.reserve(Parameters.size() + NumParams);
+  for (size_t i = 0; i < NumParams; i++)
+    if (isl_set_involves_dims(Obj, isl_dim_param, i, 1))
+      Parameters.push_back(getParameter(i).getPayloadAs<Value *>());
+}
+
+std::string PVSet::str() const {
+  char *cstr = isl_set_to_str(Obj);
+  if (!cstr)
+    return "null";
+  std::string Result(cstr);
+  ::free(cstr);
+  return Result;
+}
+
+/* -------------------- PVMap ----------------------- */
+static void adjustDimensionsPlain(isl_map *&Map0, isl_map *&Map1) {
+  int DimIn0 = isl_map_dim(Map0, isl_dim_in);
+  int DimIn1 = isl_map_dim(Map1, isl_dim_in);
+  if (DimIn0 == DimIn1)
+    return;
+
+  auto *&Map = (DimIn0 > DimIn1) ? Map1 : Map0;
+  Map = isl_map_add_dims(Map, isl_dim_in, std::abs(DimIn0 - DimIn1));
+
+  assert(isl_map_dim(Map0, isl_dim_in) == isl_map_dim(Map1, isl_dim_in));
+  assert(isl_map_dim(Map0, isl_dim_out) == isl_map_dim(Map1, isl_dim_out));
+}
+
+
+PVMap::PVMap(isl_map *M) : Obj(M) {}
+PVMap::PVMap(const PVMap &Other) : Obj(isl_map_copy(Other.Obj)) {}
+PVMap::PVMap(ArrayRef<PVAff> Affs, const PVId &Id) {
+  if (Affs.empty())
+    return;
+
+  const PVAff &Aff = Affs.front();
+  isl_space *Space = isl_space_alloc(Aff.getIslCtx(), 0,
+                                     Aff.getNumInputDimensions(), Affs.size());
+  isl_pw_multi_aff *MPWA = isl_pw_multi_aff_zero(Space);
+  for (unsigned i = 0; i < Affs.size(); i++)
+    MPWA = isl_pw_multi_aff_set_pw_aff(MPWA, i, Affs[i]);
+
+  Obj = isl_map_from_pw_multi_aff(MPWA);
+  assert(!isl_map_has_tuple_id(Obj, isl_dim_out));
+  Obj = isl_map_coalesce(Obj);
+
+  Obj = isl_map_set_tuple_id(Obj, isl_dim_out, Id);
+  assert(isl_map_has_tuple_id(Obj, isl_dim_out));
+}
+
+PVMap::PVMap(const PVAff &Aff, long Factor) {
+  isl_val *FactorVal = isl_val_int_from_si(getIslCtx(), Factor);
+  Obj = isl_map_from_pw_aff(isl_pw_aff_scale_val(Aff, FactorVal));
+}
+
+PVMap::PVMap(const PVId &ValId, const PVId &InputId, const PVId &OutputId) {
+  Obj = isl_map_from_pw_aff(PVAff(ValId));
+  if (InputId)
+    Obj = isl_map_set_tuple_id(Obj, isl_dim_in, InputId);
+  if (OutputId)
+    Obj = isl_map_set_tuple_id(Obj, isl_dim_out, OutputId);
+}
+
+PVMap::~PVMap() { isl_map_free(Obj); }
+
+PVMap &PVMap::operator=(const PVMap &Other) {
+  if (this != &Other) {
+    isl_map_free(Obj);
+    Obj = isl_map_copy(Other.Obj);
+  }
+  return *this;
+}
+
+PVMap &PVMap::operator=(PVMap &&Other) {
+  if (this != &Other) {
+    Obj = isl_map_free(Obj);
+    std::swap(Obj, Other.Obj);
+  }
+  return *this;
+}
+PVMap::operator isl_map *() const { return isl_map_copy(Obj); }
+
+isl_ctx *PVMap::getIslCtx() const { return isl_map_get_ctx(Obj); }
+
+isl_space *PVMap::getSpace() const { return isl_map_get_space(Obj); }
+
+bool PVMap::isEmpty() const { return Obj && isl_map_is_empty(Obj); }
+
+size_t PVMap::getNumInputDimensions() const { return isl_map_dim(Obj, isl_dim_in); }
+
+size_t PVMap::getNumOutputDimensions() const { return isl_map_dim(Obj, isl_dim_out); }
+
+size_t PVMap::getNumParameters() const { return isl_map_dim(Obj, isl_dim_param); }
+
+PVMap::CombinatorFn PVMap::getCombinatorFn(PVMap::IslCombinatorFn Fn) {
+  return [&](const PVMap &PV0, const PVMap &PV1) -> PVMap {
+    if (!PV0)
+      return PV1;
+    if (!PV1)
+      return PV0;
+    isl_map *PWAff0 = PV0;
+    isl_map *PWAff1 = PV1;
+    adjustDimensionsPlain(PWAff0, PWAff1);
+    return PVMap(isl_map_coalesce(Fn(PWAff0, PWAff1)));
+  };
+}
+
+PVMap &PVMap::intersect(const PVMap &PM) {
+  Obj = getCombinatorFn(isl_map_intersect)(Obj, PM);
+  return *this;
+}
+
+PVMap &PVMap::intersectDomain(const PVSet &Dom) {
+  auto DomDim = Dom.getNumDimensions();
+  auto MapDim = getNumInputDimensions();
+  if (DomDim > MapDim)
+    Obj = isl_map_add_dims(Obj, isl_dim_in, DomDim - MapDim);
+
+  isl_set *Set = Dom;
+  if (DomDim < MapDim)
+    Set = isl_set_add_dims(Set, isl_dim_set, MapDim - DomDim);
+  Obj = isl_map_intersect_domain(Obj, Set);
+  return *this;
+}
+
+PVMap &PVMap::union_add(const PVMap &PM) {
+  Obj = getCombinatorFn(isl_map_union)(Obj, PM);
+  return *this;
+}
+
+int PVMap::getParameterPosition(const PVId &Id) const {
+  int Pos = isl_map_find_dim_by_id(Obj, isl_dim_param, Id);
+  return Pos;
+}
+
+void PVMap::eliminateParameter(const PVId &Id) {
+  int Pos = getParameterPosition(Id);
+  assert(Pos >= 0);
+  Obj = isl_map_project_out(Obj, isl_dim_param, Pos, 1);
+}
+
+PVSet PVMap::getParameterSet() const {
+  return isl_map_params(isl_map_copy(Obj));
+}
+
+PVId PVMap::getParameter(unsigned No) const {
+  return PVId(isl_map_get_dim_id(Obj, isl_dim_param, No));
+}
+
+PVId PVMap::getInputId() const {
+  return isl_map_get_tuple_id(Obj, isl_dim_in);
+}
+
+PVId PVMap::getOutputId() const {
+  return isl_map_get_tuple_id(Obj, isl_dim_out);
+}
+
+void PVMap::getParameters(SmallVectorImpl<PVId> &Parameters) const {
+  size_t NumParams = getNumParameters();
+  Parameters.reserve(Parameters.size() + NumParams);
+  for (size_t i = 0; i < NumParams; i++) {
+    if (isl_map_involves_dims(Obj, isl_dim_param, i, 1))
+      Parameters.push_back(getParameter(i));
+  }
+}
+
+void PVMap::getParameters(SmallVectorImpl<llvm::Value *> &Parameters) const {
+  size_t NumParams = getNumParameters();
+  Parameters.reserve(Parameters.size() + NumParams);
+  for (size_t i = 0; i < NumParams; i++)
+    if (isl_map_involves_dims(Obj, isl_dim_param, i, 1))
+      Parameters.push_back(getParameter(i).getPayloadAs<Value *>());
+}
+
+void PVMap::simplify(const PVAff &Aff) {
+}
+
+PVMap &PVMap::floordiv(int64_t V) {
+  isl_val *Val = isl_val_int_from_si(getIslCtx(), V);
+  Obj = isl_map_floordiv_val(Obj, Val);
+  return *this;
+}
+
+PVMap &PVMap::addToOutputDimension(const PVMap &Other, unsigned Dim) {
+  assert(Other.getNumOutputDimensions() == getNumOutputDimensions());
+  assert(Other.getNumInputDimensions() == getNumInputDimensions());
+
+  isl_map *OtherMap = Other;
+  OtherMap = isl_map_align_params(OtherMap, getSpace());
+  Obj = isl_map_align_params(Obj, isl_map_get_space(OtherMap));
+  isl_map_dump(Obj);
+  isl_map_dump(OtherMap);
+  Obj = isl_map_sum(Obj, OtherMap);
+  return *this;
+}
+
+void PVMap::dropUnusedParameters() {
+  size_t NumParams = getNumParameters();
+  for (size_t i = 0; i < NumParams; i++) {
+    if (isl_map_involves_dims(Obj, isl_dim_param, i, 1))
+      continue;
+
+    Obj = isl_map_project_out(Obj, isl_dim_param, i, 1);
+    i--;
+    NumParams--;
+  }
+}
+
+std::string PVMap::str() const {
+  char *cstr = isl_map_to_str(Obj);
+  if (!cstr)
+    return "null";
+  std::string Result(cstr);
+  ::free(cstr);
+  return Result;
+}
+
+/* -------------------- PVAff ----------------------- */
+
+static void adjustDimensionsPlain(isl_pw_aff *&PWA0, isl_pw_aff *&PWA1) {
+  int DimIn0 = isl_pw_aff_dim(PWA0, isl_dim_in);
+  int DimIn1 = isl_pw_aff_dim(PWA1, isl_dim_in);
+  if (DimIn0 == DimIn1)
+    return;
+
+  auto *&PWA = (DimIn0 > DimIn1) ? PWA1 : PWA0;
+  PWA = isl_pw_aff_add_dims(PWA, isl_dim_in, std::abs(DimIn0 - DimIn1));
+
+  assert(isl_pw_aff_dim(PWA0, isl_dim_in) == isl_pw_aff_dim(PWA1, isl_dim_in));
+  assert(isl_pw_aff_dim(PWA0, isl_dim_out) ==
+         isl_pw_aff_dim(PWA1, isl_dim_out));
+}
+
+PVAff::PVAff(const PVId &Id) {
+  auto *Space = isl_space_set_alloc(Id.getIslCtx(), 1, 0);
+  Space = isl_space_set_dim_id(Space, isl_dim_param, 0, Id);
+
+  auto *LS = isl_local_space_from_space(Space);
+  Obj = isl_pw_aff_var_on_domain(LS, isl_dim_param, 0);
+}
+
+PVAff::PVAff(const PVBase &Base, int64_t ConstVal)
+    : PVAff(PVSet::universe(Base), ConstVal) {}
+
+PVAff::PVAff(const PVSet &S) {
+  isl_set *Set = S;
+  Set = isl_set_detect_equalities(Set);
+  Set = isl_set_remove_redundancies(Set);
+  Set = isl_set_coalesce(Set);
+  Obj = isl_set_indicator_function(Set);
+}
+
+PVAff::PVAff(const PVSet &S, int64_t ConstVal) {
+  isl_val *V = isl_val_int_from_si(S.getIslCtx(), ConstVal);
+  isl_set *Set = S;
+  Set = isl_set_detect_equalities(Set);
+  Set = isl_set_remove_redundancies(Set);
+  Set = isl_set_coalesce(Set);
+  Obj = isl_pw_aff_val_on_domain(Set, V);
+}
+
+PVAff::PVAff(const PVBase &Base, unsigned CoeffPos, int64_t CoeffVal,
+             const PVId &Id) {
+  auto *Space = isl_space_set_alloc(Base.getIslCtx(), 1, CoeffPos + 1);
+  auto *LSpace = isl_local_space_from_space(Space);
+  auto *Aff = isl_aff_zero_on_domain(LSpace);
+  Aff = isl_aff_set_coefficient_si(Aff, isl_dim_param, 0, CoeffVal);
+  Aff = isl_aff_set_dim_id(Aff, isl_dim_param, 0, Id);
+  Obj = isl_pw_aff_from_aff(Aff);
+}
+
+PVAff::PVAff(const PVAff &Other) : Obj(isl_pw_aff_copy(Other.Obj)) {}
+
+PVAff::~PVAff() { isl_pw_aff_free(Obj); }
+
+PVAff &PVAff::operator=(const PVAff &Other) {
+  if (this != &Other) {
+    isl_pw_aff_free(Obj);
+    Obj = isl_pw_aff_copy(Other.Obj);
+  }
+  return *this;
+}
+
+PVAff &PVAff::operator=(PVAff &&Other) {
+  if (this != &Other) {
+    Obj = isl_pw_aff_free(Obj);
+    std::swap(Obj, Other.Obj);
+  }
+  return *this;
+}
+
+bool PVAff::operator==(const PVAff &Other) {
+  if (this == &Other)
+    return true;
+  if (!(*this) || !Other)
+    return false;
+  return isl_pw_aff_is_equal(Obj, Other.Obj);
+}
+
+PVAff::operator isl_pw_aff *() const { return isl_pw_aff_copy(Obj); }
+
+isl_ctx *PVAff::getIslCtx() const { return isl_pw_aff_get_ctx(Obj); }
+
+isl_space *PVAff::getSpace() const { return isl_pw_aff_get_space(Obj); }
+
+size_t PVAff::getNumInputDimensions() const { return isl_pw_aff_dim(Obj, isl_dim_in); }
+
+size_t PVAff::getNumOutputDimensions() const { return isl_pw_aff_dim(Obj, isl_dim_out); }
+
+size_t PVAff::getNumParameters() const { return isl_pw_aff_dim(Obj, isl_dim_param); }
+
+size_t PVAff::getNumPieces() const { return isl_pw_aff_n_piece(Obj); }
+
+PVAff PVAff::extractFactor(const PVAff &Aff) const {
+  SmallVector<PVId, 4> Parameters;
+  Aff.getParameters(Parameters);
+  assert(Parameters.size() == 1 && "TODO deal with more or less parameters");
+
+  return const_cast<PVAff *>(this)->getParameterCoeff(Parameters.front());
+}
+
+int PVAff::getFactor(const PVAff &Aff) const {
+  // TODO: This is just a test implementation and needs to be replaced!
+  PVAff OtherAff = Aff;
+  OtherAff.intersectDomain(getDomain());
+  if (isl_pw_aff_is_equal(Obj, OtherAff))
+    return 1;
+  for (int i = 2; i < 10; i++) {
+    isl_pw_aff *ScaledAffPWA =
+        isl_pw_aff_scale_val(OtherAff, isl_val_int_from_si(getIslCtx(), i));
+    bool Equal = isl_pw_aff_is_equal(Obj, ScaledAffPWA);
+    isl_pw_aff_free(ScaledAffPWA);
+    if (Equal)
+      return i;
+  }
+  llvm_unreachable("TODO");
+  return -1;
+}
+
+PVId PVAff::getParameter(unsigned No) const {
+  return PVId(isl_pw_aff_get_dim_id(Obj, isl_dim_param, No));
+}
+
+void PVAff::getParameters(SmallVectorImpl<PVId> &Parameters) const {
+  size_t NumParams = getNumParameters();
+  Parameters.reserve(Parameters.size() + NumParams);
+  for (size_t i = 0; i < NumParams; i++)
+    if (isl_pw_aff_involves_dims(Obj, isl_dim_param, i, 1))
+      Parameters.push_back(getParameter(i));
+}
+
+void PVAff::getParameters(SmallVectorImpl<llvm::Value *> &Parameters) const {
+  size_t NumParams = getNumParameters();
+  Parameters.reserve(Parameters.size() + NumParams);
+  for (size_t i = 0; i < NumParams; i++)
+    if (isl_pw_aff_involves_dims(Obj, isl_dim_param, i, 1))
+      Parameters.push_back(getParameter(i).getPayloadAs<Value *>());
+}
+
+int PVAff::getParameterPosition(const PVId &Id) const {
+  auto *Params = isl_pw_aff_params(isl_pw_aff_copy(Obj));
+  int Pos = isl_set_find_dim_by_id(Params, isl_dim_param, Id);
+  isl_set_free(Params);
+  return Pos;
+}
+
+bool PVAff::involvesId(const PVId &Id) const {
+  return getParameterPosition(Id) >= 0;
+}
+
+void PVAff::addInputDims(unsigned Dims) {
+  Obj = isl_pw_aff_add_dims(Obj, isl_dim_in, Dims);
+}
+
+void PVAff::insertInputDims(unsigned Pos, unsigned Dims) {
+  Obj = isl_pw_aff_insert_dims(Obj, isl_dim_in, Pos, Dims);
+}
+
+void PVAff::dropInputDim(unsigned Dim) {
+  Obj = isl_pw_aff_drop_dims(Obj, isl_dim_in, Dim, 1);
+}
+
+struct DropInfo {
+  isl_pw_aff *NewObj;
+  unsigned NumDims;
+  unsigned Dims;
+};
+
+static isl_stat dropLastInputDimsHelper(isl_set *Dom, isl_aff *Aff, void *User) {
+  DropInfo *DI = static_cast<DropInfo *>(User);
+  Dom = isl_set_project_out(Dom, isl_dim_set, DI->NumDims - DI->Dims, DI->Dims);
+  Aff = isl_aff_drop_dims(Aff, isl_dim_in, DI->NumDims - DI->Dims, DI->Dims);
+  isl_pw_aff *PWA = isl_pw_aff_from_aff(Aff);
+  PWA = isl_pw_aff_intersect_domain(PWA, Dom);
+  DI->NewObj = isl_pw_aff_union_max(DI->NewObj, PWA);
+  return isl_stat_ok;
+}
+
+void PVAff::dropLastInputDims(unsigned Dims) {
+  isl_pw_aff *NewObj = isl_pw_aff_empty(isl_space_drop_dims(getSpace(), isl_dim_in, 0, Dims));
+  unsigned NumDims = getNumInputDimensions();
+  DropInfo DI = {NewObj, NumDims, Dims};
+  isl_pw_aff_foreach_piece(Obj, dropLastInputDimsHelper, &DI);
+  isl_pw_aff_free(Obj);
+  Obj = isl_pw_aff_coalesce(DI.NewObj);
+}
+
+void PVAff::dropParameter(const PVId &Id) {
+  int Pos = getParameterPosition(Id);
+  if (Pos >= 0)
+    Obj = isl_pw_aff_drop_dims(Obj, isl_dim_param, Pos, 1);
+}
+
+void PVAff::dropUnusedParameters() {
+  size_t NumParams = getNumParameters();
+  for (size_t i = 0; i < NumParams; i++) {
+    if (isl_pw_aff_involves_dims(Obj, isl_dim_param, i, 1))
+      continue;
+
+    Obj = isl_pw_aff_drop_dims(Obj, isl_dim_param, i, 1);
+    i--;
+    NumParams--;
+  }
+}
+
+bool PVAff::isComplex() const {
+  bool Complex = isl_pw_aff_n_piece(Obj) > PWA_N_PIECE_TRESHOLD;
+  if (!Complex)
+    Complex = isl_set_n_basic_set(getDomain()) > DOMAIN_N_BASIC_SEK_TRESHOLD;
+  return Complex;
+}
+
+bool PVAff::isConstant() const {
+  return isl_pw_aff_is_cst(Obj);
+}
+
+PVSet PVAff::getLessThanDomain(const PVAff &Aff) const {
+  isl_pw_aff *AffPWA = isl_pw_aff_add_dims(
+      Aff, isl_dim_in, getNumInputDimensions() - Aff.getNumInputDimensions());
+  return isl_pw_aff_lt_set(isl_pw_aff_copy(Obj), AffPWA);
+}
+
+PVSet PVAff::getLessEqualDomain(const PVAff &Aff) const {
+  isl_pw_aff *AffPWA = isl_pw_aff_add_dims(
+      Aff, isl_dim_in, getNumInputDimensions() - Aff.getNumInputDimensions());
+  return isl_pw_aff_le_set(isl_pw_aff_copy(Obj), AffPWA);
+}
+PVSet PVAff::getGreaterEqualDomain(const PVAff &Aff) const {
+  isl_pw_aff *AffPWA = isl_pw_aff_add_dims(
+      Aff, isl_dim_in, getNumInputDimensions() - Aff.getNumInputDimensions());
+  return isl_pw_aff_ge_set(isl_pw_aff_copy(Obj), AffPWA);
+}
+
+PVSet PVAff::getDomain() const {
+  return isl_pw_aff_domain(isl_pw_aff_copy(Obj));
+}
+
+PVAff &PVAff::fixParamDim(unsigned Dim, int64_t Value) {
+  auto *Dom = isl_pw_aff_domain(isl_pw_aff_copy(Obj));
+  Dom = isl_set_fix_si(Dom, isl_dim_param, Dim, Value);
+  Obj = isl_pw_aff_intersect_domain(Obj, Dom);
+  return *this;
+}
+
+PVAff &PVAff::fixInputDim(unsigned Dim, int64_t Value) {
+  auto *Dom = isl_pw_aff_domain(isl_pw_aff_copy(Obj));
+  Dom = isl_set_fix_si(Dom, isl_dim_set, Dim, Value);
+  Obj = isl_pw_aff_intersect_domain(Obj, Dom);
+  return *this;
+}
+
+PVAff &PVAff::setInputLowerBound(unsigned Dim,
+                                 int64_t Value) {
+  auto *Dom = isl_pw_aff_domain(isl_pw_aff_copy(Obj));
+  Dom = isl_set_lower_bound_si(Dom, isl_dim_set, Dim, Value);
+  Obj = isl_pw_aff_intersect_domain(Obj, Dom);
+  return *this;
+}
+
+PVAff &PVAff::intersectDomain(const PVSet &Dom) {
+  auto DomDim = Dom.getNumDimensions();
+  auto PWADim = getNumInputDimensions();
+  if (DomDim > PWADim)
+    Obj = isl_pw_aff_add_dims(Obj, isl_dim_in, DomDim - PWADim);
+
+  isl_set *Set = Dom;
+  if (DomDim < PWADim)
+    Set = isl_set_add_dims(Set, isl_dim_set, PWADim - DomDim);
+  Obj = isl_pw_aff_intersect_domain(Obj, Set);
+  Obj = isl_pw_aff_coalesce(Obj);
+  return *this;
+}
+
+PVAff &PVAff::simplify(PVSet &S) {
+  isl_set *Set;
+  int DimDiff = S.getNumDimensions() - getNumInputDimensions();
+  if (DimDiff > 0) {
+    S.dropDimsFrom(S.getNumDimensions() - DimDiff);
+    Set = S;
+  }
+  else if (DimDiff < 0)
+    Set = isl_set_add_dims(S, isl_dim_set, -DimDiff);
+  else
+    Set = S;
+
+  isl_set *Dom = isl_pw_aff_domain(isl_pw_aff_copy(Obj));
+  isl_set *InvDom = isl_set_subtract(Dom, Set);
+  isl_set *InvCtx = isl_set_params(InvDom);
+  isl_set *OkCtx = isl_set_complement(InvCtx);
+  if (isl_set_is_empty(OkCtx)) {
+    isl_set_free(OkCtx);
+    return *this;
+  }
+  S.intersect(isl_set_copy(OkCtx));
+  OkCtx = isl_set_add_dims(OkCtx, isl_dim_set, getNumInputDimensions());
+  Obj = isl_pw_aff_gist(Obj, OkCtx);
+  dropUnusedParameters();
+  return *this;
+}
+
+PVAff &PVAff::floordiv(int64_t V) {
+  isl_val *Val = isl_val_int_from_si(getIslCtx(), V);
+  Obj = isl_pw_aff_div(Obj, isl_pw_aff_val_on_domain(getDomain(), Val));
+  return *this;
+}
+
+PVAff &PVAff::add(const PVAff &PV) {
+  Obj = getCombinatorFn(isl_pw_aff_add)(Obj, PV);
+  return *this;
+}
+
+PVAff &PVAff::sub(const PVAff &PV) {
+  Obj = getCombinatorFn(isl_pw_aff_sub)(Obj, PV);
+  return *this;
+}
+
+PVAff &PVAff::multiply(const PVAff &PV) {
+  Obj = getCombinatorFn(isl_pw_aff_mul)(Obj, PV);
+  return *this;
+}
+
+PVAff &PVAff::union_add(const PVAff &PV) {
+  Obj = getCombinatorFn(isl_pw_aff_union_add)(Obj, PV);
+  return *this;
+}
+
+PVAff &PVAff::select(const PVAff &PV0, const PVAff &PV1) {
+  isl_pw_aff *PV0Obj = PV0;
+  isl_pw_aff *PV1Obj = PV1;
+  adjustDimensionsPlain(Obj, PV0Obj);
+  adjustDimensionsPlain(PV0Obj, PV1Obj);
+  adjustDimensionsPlain(Obj, PV1Obj);
+  Obj = isl_pw_aff_cond(Obj, PV0Obj, PV1Obj);
+  return *this;
+}
+
+PVSet PVAff::zeroSet() const {
+  return isl_pw_aff_zero_set(isl_pw_aff_copy(Obj));
+}
+
+PVSet PVAff::nonZeroSet() const {
+  return isl_pw_aff_non_zero_set(isl_pw_aff_copy(Obj));
+}
+
+struct ParameterInfo {
+  PVAff Coeff;
+  int Pos;
+};
+
+static isl_stat getParameterAff(isl_set *Domain, isl_aff *Aff, void *User) {
+  auto *PI = static_cast<ParameterInfo*>(User);
+  isl_val *CoeffVal = isl_aff_get_coefficient_val(Aff, isl_dim_param, PI->Pos);
+  isl_aff *CoeffAff = isl_aff_zero_on_domain(isl_aff_get_domain_local_space(Aff));
+  CoeffAff = isl_aff_set_constant_val(CoeffAff, CoeffVal);
+  isl_pw_aff *CoeffPWA = isl_pw_aff_from_aff(CoeffAff);
+  CoeffPWA = isl_pw_aff_intersect_domain(CoeffPWA, Domain);
+  PI->Coeff.union_add(CoeffPWA);
+  isl_aff_free(Aff);
+  return isl_stat_ok;
+}
+
+PVAff PVAff::getParameterCoeff(const PVId &Id) {
+  int Pos = getParameterPosition(Id);
+  if (Pos < 0)
+    return PVAff();
+
+  ParameterInfo PI = {PVAff(), Pos};
+  isl_stat Success = isl_pw_aff_foreach_piece(Obj, getParameterAff, &PI);
+  (void) Success;
+  assert(Success == isl_stat_ok);
+
+  return PI.Coeff;
+}
+
+struct EvolutionInfo {
+  PVAff PWA;
+  int LD;
+  int Pos;
+  long Val;
+};
+
+static isl_stat adjustBackedgeVal(isl_set *Domain, isl_aff *Aff, void *User) {
+  auto *EI = static_cast<EvolutionInfo*>(User);
+  auto *Val = isl_aff_get_constant_val(Aff);
+  if (isl_val_is_zero(Val) || isl_val_get_den_si(Val) != 1) {
+    isl_val_free(Val);
+    isl_set_free(Domain);
+    isl_aff_free(Aff);
+    return isl_stat_error;
+  }
+  long ValL = isl_val_get_num_si(Val);
+  if (EI->Val != LONG_MAX && EI->Val != ValL) {
+    isl_val_free(Val);
+    isl_set_free(Domain);
+    isl_aff_free(Aff);
+    return isl_stat_error;
+  }
+  EI->Val = ValL;
+
+  // Aff = isl_aff_set_constant_val(Aff, isl_val_neg(isl_val_copy(Val)));
+  Aff = isl_aff_set_constant_si(Aff, 0);
+  Aff = isl_aff_add_dims(Aff, isl_dim_in, EI->LD + 1);
+  Aff = isl_aff_set_coefficient_val(Aff, isl_dim_in, EI->LD, Val);
+
+  auto *PosVal = isl_aff_get_coefficient_val(Aff, isl_dim_param, EI->Pos);
+  if (!isl_val_is_one(PosVal)) {
+    isl_val_free(Val);
+    isl_set_free(Domain);
+    isl_aff_free(Aff);
+    return isl_stat_error;
+  }
+  Aff = isl_aff_set_coefficient_si(Aff, isl_dim_param, EI->Pos, 0);
+
+  Domain = isl_set_drop_constraints_involving_dims(Domain, isl_dim_param,
+                                                   EI->Pos, 1);
+
+  PVAff Increment = isl_pw_aff_from_aff(Aff);
+  Increment.intersectDomain(Domain);
+  EI->PWA.union_add(Increment);
+  return isl_stat_ok;
+}
+
+PVAff PVAff::perPiecePHIEvolution(const PVId &Id, int LD) const {
+  int Pos = getParameterPosition(Id);
+  if (Pos < 0)
+    return PVAff();
+
+  EvolutionInfo EI = {PVAff(), LD, Pos, LONG_MAX};
+  isl_stat Success = isl_pw_aff_foreach_piece(Obj, adjustBackedgeVal, &EI);
+  if (Success != isl_stat_ok)
+    return PVAff();
+
+  return EI.PWA;
+}
+
+PVAff PVAff::getExpPWA(const PVAff &PWA) {
+  assert(isl_pw_aff_is_cst(PWA));
+
+  auto *ExpPWA = isl_pw_aff_empty(isl_pw_aff_get_space(PWA));
+  auto ExpPiece = [](isl_set *Dom, isl_aff *Aff, void *User) {
+    auto **ExpPWA = static_cast<isl_pw_aff **>(User);
+    assert(isl_aff_is_cst(Aff));
+
+    auto *Val = isl_aff_get_constant_val(Aff);
+    isl_aff_free(Aff);
+
+    Val = isl_val_2exp(Val);
+    auto *ExpPiecePWA = isl_pw_aff_val_on_domain(Dom, Val);
+    *ExpPWA = isl_pw_aff_union_add(*ExpPWA, ExpPiecePWA);
+    return isl_stat_ok;
+  };
+
+  auto Success = isl_pw_aff_foreach_piece(PWA, ExpPiece, &ExpPWA);
+  (void)Success;
+  assert(Success == isl_stat_ok);
+
+  ExpPWA = isl_pw_aff_add_dims(ExpPWA, isl_dim_in, 0);
+  return ExpPWA;
+}
+
+PVAff PVAff::createAdd(const PVAff &LHS, const PVAff &RHS) {
+  return PVAff(LHS).add(RHS);
+}
+
+PVAff PVAff::createUnionAdd(const PVAff &LHS, const PVAff &RHS) {
+  return getCombinatorFn(isl_pw_aff_union_add)(LHS, RHS);
+}
+
+PVAff PVAff::createSub(const PVAff &LHS, const PVAff &RHS) {
+  return PVAff(LHS).sub(RHS);
+}
+
+PVAff PVAff::createMultiply(const PVAff &LHS, const PVAff &RHS) {
+  return PVAff(LHS).multiply(RHS);
+}
+
+PVAff PVAff::createSDiv(const PVAff &LHS, const PVAff &RHS) {
+  return getCombinatorFn(isl_pw_aff_tdiv_q)(LHS, RHS);
+}
+
+PVAff PVAff::createShiftLeft(const PVAff &LHS, const PVAff &RHS) {
+  auto ExpRHS = getExpPWA(RHS);
+  return ExpRHS.multiply(LHS);
+}
+
+PVAff PVAff::createSelect(const PVAff &CondPV, const PVAff &TruePV,
+                    const PVAff &FalsePV) {
+  return PVAff(CondPV).select(TruePV, FalsePV);
+}
+
+PVAff::CombinatorFn PVAff::getCombinatorFn(PVAff::IslCombinatorFn Fn) {
+  return [&](const PVAff &PV0, const PVAff &PV1) -> PVAff {
+    if (!PV0)
+      return PV1;
+    if (!PV1)
+      return PV0;
+    isl_pw_aff *PWAff0 = PV0;
+    isl_pw_aff *PWAff1 = PV1;
+    adjustDimensionsPlain(PWAff0, PWAff1);
+    return PVAff(isl_pw_aff_coalesce(Fn(PWAff0, PWAff1)));
+  };
+}
+
+/// Create the conditions under which @p L @p Pred @p R is true.
+PVSet PVAff::buildConditionSet(ICmpInst::Predicate Pred, const PVAff &PV0,
+                               const PVAff &PV1) {
+  isl_pw_aff *L = PV0;
+  isl_pw_aff *R = PV1;
+  adjustDimensionsPlain(L, R);
+
+  switch (Pred) {
+  case ICmpInst::ICMP_EQ:
+    return isl_pw_aff_eq_set(L, R);
+  case ICmpInst::ICMP_NE:
+    return isl_pw_aff_ne_set(L, R);
+  case ICmpInst::ICMP_SLT:
+    return isl_pw_aff_lt_set(L, R);
+  case ICmpInst::ICMP_SLE:
+    return isl_pw_aff_le_set(L, R);
+  case ICmpInst::ICMP_SGT:
+    return isl_pw_aff_gt_set(L, R);
+  case ICmpInst::ICMP_SGE:
+    return isl_pw_aff_ge_set(L, R);
+  case ICmpInst::ICMP_ULT:
+    return isl_pw_aff_lt_set(L, R);
+  case ICmpInst::ICMP_UGT:
+    return isl_pw_aff_gt_set(L, R);
+  case ICmpInst::ICMP_ULE:
+    return isl_pw_aff_le_set(L, R);
+  case ICmpInst::ICMP_UGE:
+    return isl_pw_aff_ge_set(L, R);
+  default:
+    llvm_unreachable("Non integer predicate not supported");
+  }
+}
+
+std::string PVAff::str() const {
+  char *cstr = isl_pw_aff_to_str(Obj);
+  if (!cstr)
+    return "null";
+  std::string Result(cstr);
+  ::free(cstr);
+  return Result;
+}
+
+llvm::raw_ostream &llvm::operator<<(llvm::raw_ostream &OS, const PVBase &PV) {
+  OS << PV.str();
+  return OS;
+}

lib/Analysis/PolyhedralValueInfo.cpp

+//===-- PolyhedralValueInfo.cpp  - Polyhedral value analysis ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/PolyhedralValueInfo.h"
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <cassert>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "polyhedral-value-info"
+
+STATISTIC(NUM_PARAMETERS, "Number of parameters created");
+STATISTIC(NUM_DOMAINS, "Number of domains created");
+STATISTIC(NUM_EXPRESSIONS, "Number of expressions created");
+STATISTIC(COMPLEX_DOMAIN, "Number of domains to complex");
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, PEXP::ExpressionKind Kind) {
+  switch (Kind) {
+  case PEXP::EK_NONE:
+    return OS << "NONE";
+  case PEXP::EK_INTEGER:
+    return OS << "INTEGER";
+  case PEXP::EK_DOMAIN:
+    return OS << "DOMAIN";
+  case PEXP::EK_UNKNOWN_VALUE:
+    return OS << "UNKNOWN";
+  case PEXP::EK_NON_AFFINE:
+    return OS << "NON AFFINE";
+  default:
+    llvm_unreachable("Unknown polyhedral expression kind");
+  }
+}
+
+PEXP *PEXP::setDomain(const PVSet &Domain, bool Overwrite) {
+  assert((!PWA || Overwrite) && "PWA already initialized");
+  DEBUG(dbgs() << "SetDomain: " << Domain << " for " << Val->getName() << "\n");
+  if (Domain.isComplex()) {
+    DEBUG(dbgs() << "Domain too complex!\n");
+    return invalidate();
+  }
+
+  setKind(PEXP::EK_DOMAIN);
+  PWA = PVAff(Domain, 1);
+  PWA.dropUnusedParameters();
+  if (!InvalidDomain)
+    InvalidDomain = PVSet::empty(PWA);
+  if (!KnownDomain)
+    KnownDomain = PVSet::universe(PWA);
+  else
+    PWA.simplify(KnownDomain);
+  return this;
+}
+
+void PEXP::print(raw_ostream &OS) const {
+  OS << PWA << " [" << getValue()->getName() << "] [" << getKind()
+     << "] [Scope: " << (getScope() ? getScope()->getName() : "<max>") << "]";
+  if (!InvalidDomain.isEmpty())
+    OS << " [ID: " << InvalidDomain << "]";
+  if (!KnownDomain.isUniverse())
+    OS << " [KD: " << KnownDomain << "]";
+}
+void PEXP::dump() const { print(dbgs()); }
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const PEXP *PE) {
+  if (PE)
+    OS << *PE;
+  else
+    OS << "<null>";
+  return OS;
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const PEXP &PE) {
+  PE.print(OS);
+  return OS;
+}
+
+PEXP &PEXP::operator=(const PEXP &PE) {
+  Kind = PE.Kind;
+  PWA = PE.getPWA();
+  InvalidDomain = PE.getInvalidDomain();
+  KnownDomain = PE.getKnownDomain();
+
+  return *this;
+}
+
+PEXP &PEXP::operator=(PEXP &&PE) {
+  std::swap(Kind, PE.Kind);
+  std::swap(PWA, PE.PWA);
+  std::swap(InvalidDomain, PE.InvalidDomain);
+  std::swap(KnownDomain, PE.KnownDomain);
+
+  return *this;
+}
+
+void PEXP::addInvalidDomain(const PVSet &ID) { InvalidDomain.unify(ID); }
+
+void PEXP::addKnownDomain(const PVSet &KD) {
+  KnownDomain.intersect(KD);
+  PWA.simplify(KnownDomain);
+}
+
+PEXP *PEXP::assign(const PEXP *PE0, const PEXP *PE1,
+                   PVAff::IslCombinatorFn Combinator) {
+  return assign(PE0, PE1, PVAff::getCombinatorFn(Combinator));
+}
+
+PEXP *PEXP::assign(const PEXP *PE0, const PEXP *PE1,
+                   PVAff::CombinatorFn Combinator) {
+  DEBUG(dbgs() << "Assign " << this << " [" << PE0 << "][" << PE1 << "]\n");
+  assert(!isInitialized() &&
+         "Cannot assign to an initialized polyhedral expression");
+  assert(PE0 && PE0->isInitialized() && PE1 && PE1->isInitialized() &&
+         "Cannot assign from an uninitialized polyhedral expression");
+
+  // Merge the kinds and exit if the result is non-affine.
+  Kind = std::max(PE0->Kind, PE1->Kind);
+  if (Kind == PEXP::EK_NON_AFFINE)
+    return invalidate();
+
+  auto &PWA0 = PE0->getPWA();
+  auto &PWA1 = PE1->getPWA();
+  PWA = Combinator(PWA0, PWA1);
+
+  InvalidDomain =
+      PVSet::unify(PE0->getInvalidDomain(), PE1->getInvalidDomain());
+  KnownDomain = PVSet::intersect(PE0->getKnownDomain(), PE1->getKnownDomain());
+
+  return this;
+}
+
+PEXP *PEXP::combine(const PEXP *PE) {
+  Kind = std::max(Kind, PE->Kind);
+
+  InvalidDomain.unify(PE->getInvalidDomain());
+  KnownDomain.intersect(PE->getKnownDomain());
+  return this;
+}
+
+PEXP *PEXP::combine(const PEXP *PE, PVAff::IslCombinatorFn Combinator,
+                    const PVSet *Domain) {
+  return combine(PE, PVAff::getCombinatorFn(Combinator), Domain);
+}
+
+PEXP *PEXP::combine(const PEXP *PE, PVAff::CombinatorFn Combinator,
+                    const PVSet *Domain) {
+  assert(isInitialized() && PE && PE->isInitialized() && Combinator &&
+         "Can only combine initialized polyhedral expressions");
+
+  combine(PE);
+  if (Kind == PEXP::EK_NON_AFFINE)
+    return invalidate();
+
+  PVAff PEPWA = PE->getPWA();
+  if (Domain)
+    PEPWA.intersectDomain(*Domain);
+
+  PWA = PWA ? Combinator(PWA, PEPWA) : PEPWA;
+
+  return this;
+}
+
+PEXP *PEXP::invalidate() {
+  Kind = PEXP::EK_NON_AFFINE;
+  PWA = PVAff();
+  return this;
+}
+
+void PEXP::adjustInvalidAndKnownDomain() {
+  auto *ITy = cast<IntegerType>(getValue()->getType());
+  unsigned BitWidth = ITy->getBitWidth();
+  assert(BitWidth > 0 && BitWidth <= 64);
+  int64_t LowerBound = -1 * (1 << (BitWidth - 1));
+  int64_t UpperBound = (1 << (BitWidth - 1)) - 1;
+
+  PVAff LowerPWA(getDomain(), LowerBound);
+  PVAff UpperPWA(getDomain(), UpperBound);
+
+  auto *OVBinOp = cast<OverflowingBinaryOperator>(getValue());
+  bool HasNSW = OVBinOp->hasNoSignedWrap();
+
+  const PVAff &PWA = getPWA();
+  if (HasNSW) {
+    PVSet BoundedDomain = PWA.getGreaterEqualDomain(LowerPWA).intersect(
+        PWA.getLessEqualDomain(UpperPWA));
+    KnownDomain.intersect(BoundedDomain);
+  } else {
+    PVSet BoundedDomain = LowerPWA.getGreaterEqualDomain(PWA).unify(
+        UpperPWA.getLessEqualDomain(PWA));
+
+    InvalidDomain.unify(BoundedDomain);
+  }
+}
+
+// ------------------------------------------------------------------------- //
+
+void PolyhedralValueInfoCache::releaseMemory() {
+  DeleteContainerSeconds(ValueMap);
+  DeleteContainerSeconds(DomainMap);
+  ParameterMap.clear();
+}
+
+PVId PolyhedralValueInfoCache::getParameterId(Value &V, const PVCtx &Ctx) {
+  PVId &Id = ParameterMap[&V];
+  if (Id)
+    return Id;
+
+  std::string ParameterName;
+  ParameterName = V.hasName() ? V.getName().str()
+                              : "p" + std::to_string(ParameterMap.size());
+  ParameterName = PVBase::getIslCompatibleName("", ParameterName, "");
+  DEBUG(dbgs() << "NEW PARAM: " << V << " ::: " << ParameterName << "\n";);
+  Id = PVId(Ctx, ParameterName, &V);
+
+  return Id;
+}
+
+// ------------------------------------------------------------------------- //
+
+class llvm::PolyhedralExpressionBuilder
+    : public InstVisitor<PolyhedralExpressionBuilder, PEXP *> {
+
+  Loop *Scope;
+
+  PolyhedralValueInfo &PI;
+  PolyhedralValueInfoCache PIC;
+
+  PEXP *visit(Constant &I);
+  PEXP *visit(ConstantInt &I);
+  PEXP *visitParameter(Value &V);
+  PEXP *createParameter(PEXP *PE);
+
+  PVAff getZero(const PVAff &RefPWA) { return PVAff(RefPWA.getDomain(), 0); }
+
+  PVAff getOne(const PVAff &RefPWA) { return PVAff(RefPWA.getDomain(), 1); }
+
+  PEXP *getOrCreatePEXP(Value &V) {
+    Loop *UsedScope = Scope;
+    if (!Scope || !isa<Instruction>(V))
+      UsedScope = nullptr;
+
+    PEXP *PE = PIC.getOrCreatePEXP(V, UsedScope);
+    assert(PE && PIC.lookup(V, UsedScope));
+    assert(PE->getScope() == UsedScope && PE->getValue() == &V);
+    return PE;
+  }
+
+  PEXP *getOrCreateDomain(BasicBlock &BB) {
+    return PIC.getOrCreateDomain(BB, Scope);
+  }
+
+  unsigned getRelativeLoopDepth(BasicBlock *BB);
+
+public:
+  PolyhedralExpressionBuilder(PolyhedralValueInfo &PI)
+      : Scope(nullptr), PI(PI) {}
+
+  PVSet buildNotEqualDomain(const PEXP *VI, ArrayRef<Constant *> CIs);
+  PVSet buildEqualDomain(const PEXP *VI, Constant &CI);
+
+  void setScope(Loop *NewScope) { Scope = NewScope; }
+
+  PEXP *getDomain(BasicBlock &BB);
+
+  PVId getParameterId(Value &V) { return PIC.getParameterId(V, PI.getCtx()); }
+
+  void setEdgeCondition(PEXP *PE, BasicBlock &PredBB, BasicBlock &BB);
+  PEXP *getTerminatorPEXP(BasicBlock &BB);
+
+  PEXP *getDomainOnEdge(BasicBlock &PredBB, BasicBlock &BB);
+  PEXP *getDomainOnEdge(const PEXP &PredDomPE, BasicBlock &BB);
+
+  PEXP *visitOperand(Value &Op, Instruction &I);
+  PEXP *visit(Value &V);
+  PEXP *visit(Instruction &I);
+
+  PEXP *visitBinaryOperator(BinaryOperator &I);
+  PEXP *visitCallInst(CallInst &I);
+  PEXP *visitCastInst(CastInst &I);
+  PEXP *visitFCmpInst(FCmpInst &I);
+  PEXP *visitGetElementPtrInst(GetElementPtrInst &I);
+  PEXP *visitICmpInst(ICmpInst &I);
+  PEXP *visitInvokeInst(InvokeInst &I);
+  PEXP *visitLoadInst(LoadInst &I);
+  PEXP *visitSelectInst(SelectInst &I);
+  PEXP *visitConditionalPHINode(PHINode &I);
+  PEXP *visitPHINode(PHINode &I);
+  PEXP *visitAllocaInst(AllocaInst &I);
+
+  PEXP *visitInstruction(Instruction &I);
+};
+
+void PolyhedralExpressionBuilder::setEdgeCondition(PEXP *PE, BasicBlock &PredBB,
+                                                   BasicBlock &BB) {
+  assert(PE && !PE->isInitialized());
+
+  auto &TI = *PredBB.getTerminator();
+  if (TI.getNumSuccessors() == 1) {
+    assert(&BB == TI.getSuccessor(0));
+    PE->setDomain(PVSet::universe(PI.getCtx()));
+    return;
+  }
+
+  auto *TermPE = getTerminatorPEXP(PredBB);
+  if (!TermPE) {
+    PE->invalidate();
+    return;
+  }
+  DEBUG(dbgs() << "TERMPE: " << TermPE << "\n");
+
+  PVSet EdgeCond;
+  auto *Int64Ty = Type::getInt64Ty(TI.getContext());
+  if (isa<BranchInst>(TI)) {
+    if (TI.getSuccessor(0) == &BB)
+      EdgeCond = buildEqualDomain(TermPE, *ConstantInt::get(Int64Ty, 1));
+    if (TI.getSuccessor(1) == &BB)
+      EdgeCond.unify(buildEqualDomain(TermPE, *ConstantInt::get(Int64Ty, 0)));
+  } else if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
+    bool IsDefaultBlock = (SI->getDefaultDest() == &BB);
+    SmallVector<Constant *, 8> OtherCaseValues;
+    for (auto &Case : SI->cases()) {
+      if (Case.getCaseSuccessor() == &BB)
+        EdgeCond.unify(buildEqualDomain(TermPE, *Case.getCaseValue()));
+      else if (IsDefaultBlock)
+        OtherCaseValues.push_back(Case.getCaseValue());
+    }
+
+    if (IsDefaultBlock && !OtherCaseValues.empty())
+      EdgeCond.unify(buildNotEqualDomain(TermPE, OtherCaseValues));
+  }
+
+  PE->combine(TermPE);
+  PE->setDomain(EdgeCond);
+  if (PE->PWA.isComplex()) {
+    DEBUG(dbgs() << "Too complex edge condition!\n";);
+    COMPLEX_DOMAIN++;
+    PE->invalidate();
+  }
+}
+
+PEXP *PolyhedralExpressionBuilder::getDomain(BasicBlock &BB) {
+  PEXP *PE = getOrCreateDomain(BB);
+  assert(PE);
+
+  if (PE->isInitialized())
+    return PE;
+
+  DEBUG(dbgs() << "Get domain of: " << BB.getName() << "\n";);
+
+  auto *L = PI.LI.getLoopFor(&BB);
+  bool IsLoopHeader = L && L->getHeader() == &BB;
+
+  if (&BB.getParent()->getEntryBlock() == &BB) {
+    DEBUG(dbgs() << "Universe domain for entry [" << BB.getName() << "]\n");
+    NUM_DOMAINS++;
+    return PE->setDomain(PVSet::universe(PI.getCtx()));
+  }
+
+  if (Scope && (Scope == L || !Scope->contains(&BB))) {
+    DEBUG(dbgs() << "Universe domain for outside block for [" << BB.getName()
+                 << "] [" << (Scope ? Scope->getName() : "<max>") << "]\n");
+    NUM_DOMAINS++;
+    return PE->setDomain(PVSet::universe(PI.getCtx()));
+  }
+
+  if (L) {
+    if (!IsLoopHeader) {
+      DEBUG(dbgs() << "recurse for loop header [" << L->getHeader()->getName()
+                   << "] first!\n");
+      getDomain(*L->getHeader());
+    } else if (auto *PL = L->getParentLoop()) {
+      DEBUG(dbgs() << "recurse for parent loop header ["
+                   << PL->getHeader()->getName() << "] first!\n");
+      getDomain(*PL->getHeader());
+    }
+
+    // After the recursion we have to update PE.
+    PE = getOrCreateDomain(BB);
+  }
+
+  DEBUG(dbgs() << "-- PE: " << PE << " : " << (void *)PE << " [L: " << L
+               << "][LH: " << IsLoopHeader << "]\n";);
+
+  // While we created the domain of the loop header we did produce partial
+  // results for other blocks in the loop. While we could update these results
+  // we will simply forget them for now and recreate them if necessary.
+  auto ForgetDomainsInLoop = [&](Loop &L) {
+    if (!IsLoopHeader)
+      return;
+    for (auto *BB : L.blocks())
+      if (BB != L.getHeader())
+        PIC.forget(*BB, Scope);
+  };
+
+  unsigned LD = getRelativeLoopDepth(&BB);
+  PVSet Domain = PVSet::empty(PI.getCtx(), LD);
+  for (auto *PredBB : predecessors(&BB)) {
+    DEBUG(dbgs() << "\t Pred: " << PredBB->getName() << "\n");
+    if (IsLoopHeader && L->contains(PredBB)) {
+      DEBUG(dbgs() << "Skip backedge from " << PredBB->getName() << "\n");
+      continue;
+    }
+
+    PEXP *PredDomainPE = getDomainOnEdge(*PredBB, BB);
+    DEBUG(dbgs() << "Domain on edge " << PredBB->getName() << " => "
+                 << BB.getName() << ": " << PredDomainPE << "\n");
+    if (!PredDomainPE || PredDomainPE->PWA.isComplex()) {
+      ForgetDomainsInLoop(*L);
+      return PE->invalidate();
+    }
+
+    PE->combine(PredDomainPE);
+
+    PVSet PredDomain = PredDomainPE->getDomain();
+
+    auto *PredL = PI.LI.getLoopFor(PredBB);
+    if (PredL && L && PredL != L) {
+      if (getRelativeLoopDepth(PredBB) == LD)
+        PredDomain.dropDimsFrom(LD - 1);
+      else
+        PredDomain.dropDimsFrom(LD);
+    } else if (PredL != L) {
+      PredDomain.dropDimsFrom(LD);
+    }
+    DEBUG(dbgs() << "Domain on edge " << PredBB->getName() << " => "
+                 << BB.getName() << ": " << PredDomain << "\n");
+
+    Domain.unify(PredDomain);
+    delete PredDomainPE;
+    if (Domain.isComplex()) {
+      DEBUG(dbgs() << "Too complex domain on edge!\n";);
+      COMPLEX_DOMAIN++;
+      ForgetDomainsInLoop(*L);
+      return PE->invalidate();
+    }
+  }
+
+  DEBUG(dbgs() << "PE: " << PE << "\n");
+  DEBUG(dbgs() << "DOmain: " << Domain << "\n");
+  PVSet ParameterRange = PVSet::universe(Domain);
+
+  SmallVector<PVId, 4> Parameters;
+  Domain.getParameters(Parameters);
+  for (const PVId &PId : Parameters) {
+    auto *Parameter = PId.getPayloadAs<Value *>();
+    if (!Parameter->getType()->isIntegerTy(1)) {
+      DEBUG(dbgs() << "TODO simplify parameter of non boolean type: "
+                   << *Parameter << "\n");
+      continue;
+    }
+
+    ParameterRange.intersect(PVSet::createParameterRange(PId, 0, 1));
+  }
+  Domain.simplifyParameters(ParameterRange);
+
+  if (!IsLoopHeader) {
+    PE->setDomain(Domain, true);
+    NUM_DOMAINS++;
+    return PE;
+  }
+
+  PVSet NonExitDom = Domain.setInputLowerBound(LD - 1, 0);
+  DEBUG(dbgs() << "NonExitDom :" << NonExitDom << "\n");
+  PE->setDomain(NonExitDom, true);
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  for (auto *ExitingBB : ExitingBlocks) {
+    DEBUG(dbgs() << "ExitingBB: " << ExitingBB->getName() << "\n");
+    const PEXP *ExitingBBDomainPE =
+        ExitingBB == &BB ? PE : getDomain(*ExitingBB);
+    if (!ExitingBBDomainPE || PI.isNonAffine(ExitingBBDomainPE)) {
+      DEBUG(dbgs() << "TODO: Fix exiting bb domain hack for loop domains!");
+      ForgetDomainsInLoop(*L);
+      return PE->invalidate();
+    }
+    DEBUG(dbgs() << "NonExitDom :" << NonExitDom << "\n");
+    PVSet ExitingBBDom = ExitingBBDomainPE->getDomain();
+    DEBUG(dbgs() << "ExitingDom: " << ExitingBBDom << "\n");
+    PVSet ExitCond;
+    for (auto *SuccBB : successors(ExitingBB))
+      if (!L->contains(SuccBB)) {
+        PEXP *ExitingPE = getDomainOnEdge(*ExitingBBDomainPE, *SuccBB);
+        if (!ExitingPE || ExitingPE->PWA.isComplex()) {
+          ForgetDomainsInLoop(*L);
+          return PE->invalidate();
+        }
+        PE->combine(ExitingPE);
+        ExitCond.unify(ExitingPE->getDomain());
+        delete ExitingPE;
+      }
+    DEBUG(dbgs() << "ExitCond: " << ExitCond << "\n");
+    ExitingBBDom.intersect(ExitCond);
+    ExitingBBDom.dropDimsFrom(LD);
+    DEBUG(dbgs() << "ExitingDom: " << ExitingBBDom << "\n");
+    if (ExitingBBDom.getNumDimensions() >= LD)
+      ExitingBBDom.getNextIterations(LD - 1);
+    DEBUG(dbgs() << "ExitingDom: " << ExitingBBDom << "\n");
+    NonExitDom.subtract(ExitingBBDom);
+    DEBUG(dbgs() << "NonExitDom :" << NonExitDom << "\n");
+    if (NonExitDom.isComplex()) {
+      ForgetDomainsInLoop(*L);
+      return PE->invalidate();
+    }
+  }
+
+  DEBUG(dbgs() << "NonExitDom :" << NonExitDom << "\nDom :" << Domain << "\n");
+  Domain.fixInputDim(LD - 1, 0);
+  DEBUG(dbgs() << "Dom :" << Domain << "\n");
+  Domain.unify(NonExitDom);
+  DEBUG(dbgs() << "Dom :" << Domain << "\n");
+
+  PE->setDomain(Domain, true);
+
+  ForgetDomainsInLoop(*L);
+
+  NUM_DOMAINS++;
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::getDomainOnEdge(BasicBlock &PredBB,
+                                                   BasicBlock &BB) {
+  PEXP *PredDomPE = getDomain(PredBB);
+  assert(PredDomPE);
+  if (PI.isNonAffine(PredDomPE))
+    return nullptr;
+  return getDomainOnEdge(*PredDomPE, BB);
+}
+
+PEXP *PolyhedralExpressionBuilder::getDomainOnEdge(const PEXP &PredDomPE,
+                                                   BasicBlock &BB) {
+  assert(PredDomPE.getKind() == PEXP::EK_DOMAIN);
+  auto &PredBB = *cast<BasicBlock>(PredDomPE.getValue());
+  DEBUG(dbgs() << "getDomOnEdge: " << PredBB.getName() << " => " << BB.getName()
+               << "\n");
+  PEXP *EdgeDomain = new PEXP(&BB, Scope);
+  setEdgeCondition(EdgeDomain, PredBB, BB);
+  DEBUG(dbgs() << "EdgeCond: " << EdgeDomain << " "
+               << EdgeDomain->isInitialized() << "\n");
+  assert(EdgeDomain->isInitialized());
+
+  EdgeDomain->combine(&PredDomPE);
+
+  PVSet PredDomain = PredDomPE.getDomain();
+  DEBUG(dbgs() << "Pred: " << PredBB.getName() << "    BB: " << BB.getName()
+               << "\n"
+               << "Pred Dom: " << PredDomain << "\n"
+               << "EdgeDomain: " << EdgeDomain << "\n");
+
+  return EdgeDomain->setDomain(EdgeDomain->getDomain().intersect(PredDomain),
+                               true);
+}
+
+PEXP *PolyhedralExpressionBuilder::visitOperand(Value &Op, Instruction &I) {
+  PEXP *PE = visit(Op);
+
+  Instruction *OpI = dyn_cast<Instruction>(&Op);
+  if (!OpI)
+    return PE;
+
+  Loop *OpIL = PI.LI.getLoopFor(OpI->getParent());
+  unsigned NumDims = PE->getPWA().getNumInputDimensions();
+  unsigned NumLeftLoops = 0;
+  while (OpIL && NumDims && !OpIL->contains(&I)) {
+    NumLeftLoops++;
+    NumDims--;
+    OpIL = OpIL->getParentLoop();
+  }
+
+  if (NumLeftLoops) {
+    PEXP *OpIDomPE = getDomain(*OpI->getParent());
+    if (PI.isNonAffine(OpIDomPE))
+      PE->getPWA().dropLastInputDims(NumLeftLoops);
+    else {
+      PVSet OpIDom = OpIDomPE->getDomain();
+      OpIDom.maxInLastInputDims(NumLeftLoops);
+      PE->getPWA().intersectDomain(OpIDom);
+      PE->getPWA().dropLastInputDims(NumLeftLoops);
+    }
+  }
+
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visit(Value &V) {
+
+  PEXP *PE = PIC.lookup(V, Scope);
+  if (PE && PE->isInitialized()) {
+    return PE;
+  }
+
+  DEBUG(dbgs() << "Visit V: " << V << " [" << Scope << "]\n");
+  if (!V.getType()->isIntegerTy() && !V.getType()->isPointerTy())
+    PE = visitParameter(V);
+  else if (auto *I = dyn_cast<Instruction>(&V))
+    PE = visit(*I);
+  else if (auto *CI = dyn_cast<ConstantInt>(&V))
+    PE = visit(*CI);
+  else if (auto *C = dyn_cast<Constant>(&V))
+    PE = visit(*C);
+  else
+    PE = visitParameter(V);
+
+  assert(PE && PE->isInitialized());
+
+  if (PI.isAffine(PE))
+    NUM_EXPRESSIONS++;
+
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visit(Constant &I) {
+  DEBUG(dbgs() << "Visit C: " << I << "\n";);
+  if (I.isNullValue())
+    return visit(*ConstantInt::get(Type::getInt64Ty(I.getContext()), 0));
+  return visitParameter(I);
+}
+
+PEXP *PolyhedralExpressionBuilder::visit(ConstantInt &I) {
+  DEBUG(dbgs() << "Visit CI: " << I << "\n";);
+
+  auto *PE = getOrCreatePEXP(I);
+  if (PE->isInitialized())
+    return PE;
+
+  int64_t ConstVal;
+  if (auto *CI = dyn_cast<ConstantInt>(&I))
+    ConstVal = CI->isOne() ? 1 : CI->getSExtValue();
+  else if (I.isNullValue())
+    ConstVal = 0;
+  else
+    llvm_unreachable("Unhandled ConstantInt!");
+
+  PE->PWA = PVAff(PI.getCtx(), ConstVal);
+  PE->setKind(PEXP::EK_INTEGER);
+
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::createParameter(PEXP *PE) {
+  PE->PWA = PVAff(PI.getParameterId(*PE->getValue()));
+  PE->setKind(PEXP::EK_UNKNOWN_VALUE);
+
+  NUM_PARAMETERS++;
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visitParameter(Value &V) {
+  DEBUG(dbgs() << "PESIT Par: " << V << "\n");
+  auto *PE = getOrCreatePEXP(V);
+  return createParameter(PE);
+}
+
+unsigned PolyhedralExpressionBuilder::getRelativeLoopDepth(BasicBlock *BB) {
+  Loop *L = PI.LI.getLoopFor(BB);
+  if (!L)
+    return 0;
+  if (!Scope)
+    return L->getLoopDepth();
+  if (!Scope->contains(L))
+    return 0;
+  return L->getLoopDepth() - Scope->getLoopDepth();
+}
+
+PEXP *PolyhedralExpressionBuilder::visit(Instruction &I) {
+  if (!I.getType()->isIntegerTy() && !I.getType()->isPointerTy())
+    return visitParameter(I);
+
+  DEBUG(dbgs() << "Visit I: " << I << "\n");
+  auto *PE = InstVisitor::visit(I);
+
+  unsigned RelLD = getRelativeLoopDepth(I.getParent());
+  unsigned NumDims = PE->PWA.getNumInputDimensions();
+  DEBUG(dbgs() << "RelLD: " << RelLD << " NumDims " << NumDims << "\n\t => "
+               << PE << "\n");
+  assert(NumDims <= RelLD);
+  PE->PWA.addInputDims(RelLD - NumDims);
+  assert(PE->PWA.getNumInputDimensions() == RelLD);
+
+  DEBUG(dbgs() << "Visited I: " << I << "\n\t => " << PE << "\n");
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::getTerminatorPEXP(BasicBlock &BB) {
+  auto *Term = BB.getTerminator();
+
+  switch (Term->getOpcode()) {
+  case Instruction::Br: {
+    auto *BI = cast<BranchInst>(Term);
+    if (BI->isUnconditional())
+      return nullptr;
+    else
+      return visitOperand(*BI->getCondition(), *Term);
+  }
+  case Instruction::Switch:
+    return visitOperand(*cast<SwitchInst>(Term)->getCondition(), *Term);
+  case Instruction::Ret:
+  case Instruction::Unreachable:
+    return nullptr;
+  case Instruction::IndirectBr:
+    /// @TODO This can be over-approximated
+    return nullptr;
+  case Instruction::Invoke:
+  case Instruction::Resume:
+  case Instruction::CleanupRet:
+  case Instruction::CatchRet:
+  case Instruction::CatchSwitch:
+    return nullptr;
+  default:
+    return nullptr;
+  }
+
+  llvm_unreachable("unknown terminator");
+  return nullptr;
+}
+
+// ------------------------------------------------------------------------- //
+
+PEXP *PolyhedralExpressionBuilder::visitICmpInst(ICmpInst &I) {
+
+  auto *PE = getOrCreatePEXP(I);
+  auto *LPE = visitOperand(*I.getOperand(0), I);
+  if (PI.isNonAffine(LPE))
+    return visitParameter(I);
+  auto *RPE = visitOperand(*I.getOperand(1), I);
+  if (PI.isNonAffine(RPE))
+    return visitParameter(I);
+
+  DEBUG(dbgs() << "ICMP: " << I << "\n");
+  DEBUG(dbgs() << "LPE: " << LPE << "\n");
+  DEBUG(dbgs() << "RPE: " << RPE << "\n");
+
+  auto Pred = I.getPredicate();
+  auto IPred = I.getInversePredicate();
+  auto TrueDomain = PVAff::buildConditionSet(Pred, LPE->PWA, RPE->PWA);
+  DEBUG(dbgs() << "TD: " << TrueDomain << "\n");
+  if (TrueDomain.isComplex()) {
+    DEBUG(dbgs() << "Too complex true domain!\n";);
+    COMPLEX_DOMAIN++;
+    return visitParameter(I);
+  }
+
+  auto FalseDomain = PVAff::buildConditionSet(IPred, LPE->PWA, RPE->PWA);
+  DEBUG(dbgs() << "FD: " << FalseDomain << "\n");
+  if (FalseDomain.isComplex()) {
+    DEBUG(dbgs() << "Too complex false domain!\n";);
+    COMPLEX_DOMAIN++;
+    return visitParameter(I);
+  }
+
+  PE->PWA = PVAff(FalseDomain, 0);
+  PE->PWA.union_add(PVAff(TrueDomain, 1));
+  PE->combine(LPE);
+  PE->combine(RPE);
+  PE->Kind = PEXP::EK_INTEGER;
+  DEBUG(dbgs() << PE << "\n");
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visitFCmpInst(FCmpInst &I) {
+  return visitParameter(I);
+}
+
+PEXP *PolyhedralExpressionBuilder::visitLoadInst(LoadInst &I) {
+  return visitParameter(I);
+}
+
+PEXP *
+PolyhedralExpressionBuilder::visitGetElementPtrInst(GetElementPtrInst &I) {
+  auto &DL = I.getModule()->getDataLayout();
+
+  auto *PtrPE = visitOperand(*I.getPointerOperand(), I);
+  if (PI.isNonAffine(PtrPE))
+    return visitParameter(I);
+
+  auto *PE = getOrCreatePEXP(I);
+  *PE = *PtrPE;
+
+  auto *Ty = I.getPointerOperandType();
+  for (auto &Op : make_range(I.idx_begin(), I.idx_end())) {
+    auto *PEOp = visitOperand(*Op, I);
+    if (PI.isNonAffine(PEOp))
+      return visitParameter(I);
+
+    if (Ty->isStructTy()) {
+      // TODO: Struct
+      DEBUG(dbgs() << "TODO: Struct ty " << *Ty << " for " << I << "\n");
+      return visitParameter(I);
+    }
+
+    uint64_t Size = 0;
+    if (Ty->isPointerTy()) {
+      Ty = Ty->getPointerElementType();
+      Size = DL.getTypeAllocSize(Ty);
+    } else if (Ty->isArrayTy()) {
+      Ty = Ty->getArrayElementType();
+      Size = DL.getTypeAllocSize(Ty);
+    } else {
+      DEBUG(dbgs() << "TODO: Unknown ty " << *Ty << " for " << I << "\n");
+      return visitParameter(I);
+    }
+    DEBUG(dbgs() << "Ty: " << *Ty << " Size: " << Size << "\n");
+    DEBUG(dbgs() << "GepPE: " << PE << "\n");
+
+    PE->combine(PEOp);
+
+    PVAff ScaledPWA(PEOp->getDomain(), Size);
+    ScaledPWA.multiply(PEOp->getPWA());
+    PE->PWA.add(ScaledPWA);
+    DEBUG(dbgs() << "GepPE: " << PE << "\n");
+  }
+
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visitCastInst(CastInst &I) {
+  PEXP *PE = getOrCreatePEXP(I);
+  *PE = *visitOperand(*I.getOperand(0), I);
+
+  switch (I.getOpcode()) {
+  case Instruction::Trunc: {
+    // Handle changed values.
+    unsigned TypeWidth =
+        I.getModule()->getDataLayout().getTypeSizeInBits(I.getType());
+    if (TypeWidth >= 64)
+      return visitParameter(I);
+    uint64_t ExpVal = ((uint64_t)1) << TypeWidth;
+    PE->addInvalidDomain(
+        PE->getPWA().getGreaterEqualDomain(PVAff(PE->getPWA(), ExpVal)));
+    PE->addInvalidDomain(
+        PE->getPWA().getLessEqualDomain(PVAff(PE->getPWA(), -ExpVal)));
+    break;
+  }
+  case Instruction::ZExt:
+    // Handle negative values.
+    PE->addInvalidDomain(
+        PE->getPWA().getLessThanDomain(PVAff(PE->getPWA(), 0)));
+    break;
+  case Instruction::SExt:
+  case Instruction::FPToSI:
+  case Instruction::FPToUI:
+  case Instruction::PtrToInt:
+  case Instruction::IntToPtr:
+  case Instruction::BitCast:
+  case Instruction::AddrSpaceCast:
+    // No-op
+    break;
+  default:
+    llvm_unreachable("Unhandled cast operation!\n");
+  }
+
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visitSelectInst(SelectInst &I) {
+  auto *CondPE = visitOperand(*I.getCondition(), I);
+  if (PI.isNonAffine(CondPE))
+    return visitParameter(I);
+
+  auto *OpTrue = visitOperand(*I.getTrueValue(), I);
+  if (PI.isNonAffine(OpTrue))
+    return visitParameter(I);
+
+  auto *OpFalse = visitOperand(*I.getFalseValue(), I);
+  if (PI.isNonAffine(OpFalse))
+    return visitParameter(I);
+
+  auto CondZero = CondPE->getPWA().zeroSet();
+  auto CondOne = CondPE->getPWA().nonZeroSet();
+
+  auto *PE = getOrCreatePEXP(I);
+  if (!PI.isNonAffine(OpTrue))
+    PE->combine(OpTrue);
+
+  if (!PI.isNonAffine(OpFalse))
+    PE->combine(OpFalse);
+
+  if (PI.isNonAffine(OpTrue)) {
+    PE->InvalidDomain.unify(CondOne);
+    PE->PWA = OpFalse->getPWA();
+    PE->setKind(OpFalse->getKind());
+    return PE;
+  }
+
+  if (PI.isNonAffine(OpFalse)) {
+    PE->InvalidDomain.unify(CondZero);
+    PE->PWA = OpTrue->getPWA();
+    PE->setKind(OpTrue->getKind());
+    return PE;
+  }
+
+  PE->PWA = PVAff::createSelect(CondPE->getPWA(), OpTrue->getPWA(),
+                                OpFalse->getPWA());
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visitInvokeInst(InvokeInst &I) {
+  return visitParameter(I);
+}
+
+PEXP *PolyhedralExpressionBuilder::visitCallInst(CallInst &I) {
+  return visitParameter(I);
+}
+
+PEXP *PolyhedralExpressionBuilder::visitConditionalPHINode(PHINode &I) {
+  bool InvalidOtherwise = false;
+
+  unsigned RelLD = getRelativeLoopDepth(I.getParent());
+  DEBUG(dbgs() << "\nCondPHI: " << I << " [RelLD: " << RelLD << "]\n");
+  auto *PE = getOrCreatePEXP(I);
+  PE->setKind(PEXP::EK_NONE);
+
+  for (unsigned u = 0, e = I.getNumIncomingValues(); u < e; u++) {
+    PEXP *PredEdgePE = getDomainOnEdge(*I.getIncomingBlock(u), *I.getParent());
+    if (!PredEdgePE) {
+      DEBUG(dbgs() << "PHI op " << u << " (" << *I.getIncomingValue(u)
+                   << ") no domain on edge\n");
+      InvalidOtherwise = true;
+      continue;
+    }
+
+    auto *PredOpPE = visit(*I.getIncomingValue(u));
+    assert(!PI.isNonAffine(PredOpPE));
+
+    DEBUG(dbgs() << "Op: " << PredOpPE << " " << u
+                 << "\n On edge: " << PredEdgePE << "\n";);
+    PE->combine(PredEdgePE);
+    PVSet PredDomain = PredEdgePE->getDomain();
+    unsigned NumDims = PredDomain.getNumDimensions();
+    assert(RelLD <= NumDims);
+    if (RelLD < NumDims)
+      PredDomain.maxInLastInputDims(NumDims - RelLD);
+    DEBUG(dbgs() << "PredDom: " << PredDomain << "\n");
+    PE->combine(PredOpPE, PVAff::createUnionAdd, &PredDomain);
+    delete PredEdgePE;
+  }
+
+  if (!PE->isInitialized())
+    return visitParameter(I);
+
+  DEBUG(dbgs() << "\nCONDITIONAL PHI: " << I << "\n" << PE << "\n";);
+  assert(PE->PWA.getNumInputDimensions() >= RelLD);
+
+  PE->PWA.dropLastInputDims(PE->PWA.getNumInputDimensions() - RelLD);
+  if (InvalidOtherwise) {
+    assert(PE->PWA);
+    PVSet Dom = PE->getDomain();
+    PE->InvalidDomain.unify(Dom.complement());
+  }
+
+  DEBUG(dbgs() << "\nCONDITIONAL PHI: " << I << "\n" << PE << "\n";);
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visitPHINode(PHINode &I) {
+  auto &BB = *I.getParent();
+  Loop *L = PI.LI.getLoopFor(&BB);
+  bool IsLoopHeader = L && L->getHeader() == &BB;
+
+  if (!IsLoopHeader)
+    return visitConditionalPHINode(I);
+
+  PEXP *ParamPE = PIC.getOrCreatePEXP(I, L);
+  assert(ParamPE);
+
+  PVId Id = PI.getParameterId(I);
+  if (!ParamPE->isInitialized()) {
+    ParamPE->PWA = PVAff(Id);
+    ParamPE->Kind = PEXP::EK_UNKNOWN_VALUE;
+  }
+  if (Scope == L) {
+    DEBUG(dbgs() << "PHI loop is scope. Parametric value is sufficent!\n");
+    return ParamPE;
+  }
+
+  PEXP *PE = getOrCreatePEXP(I);
+  assert(PE && !PE->isInitialized());
+  if (Scope && !Scope->contains(&I)) {
+    DEBUG(dbgs() << "PHI not in scope. Parametric value is sufficent!\n");
+    *PE = *ParamPE;
+    return PE;
+  }
+
+  unsigned LoopDim = getRelativeLoopDepth(L->getHeader());
+
+  auto OldScope = Scope;
+  setScope(L);
+
+  bool ConstantStride = true;
+  PVAff BackEdgeOp;
+  unsigned NumLatches = L->getNumBackEdges();
+  for (unsigned u = 0, e = I.getNumIncomingValues(); u != e; u++) {
+    auto *OpBB = I.getIncomingBlock(u);
+    if (!L->contains(OpBB))
+      continue;
+
+    auto *OpVal = I.getIncomingValue(u);
+    auto *OpPE = visit(*OpVal);
+    PVAff OpAff = OpPE->getPWA();
+    OpAff.dropParameter(Id);
+    if (!OpAff.isConstant()) {
+      DEBUG(dbgs() << "PHI has non constant stride: " << OpPE << "\n\tfor "
+                   << *OpVal << "\n");
+      if (OpPE->getPWA() != OpAff) {
+        DEBUG(dbgs() << "  Operand involves PHI! Invalid!\n");
+        setScope(OldScope);
+        return visitParameter(I);
+      }
+
+      ConstantStride = false;
+      if (OldScope != Scope) {
+        setScope(OldScope);
+        OpPE = visit(*OpVal);
+        setScope(L);
+      }
+    }
+
+    OpAff = OpPE->getPWA();
+    if (NumLatches > 1 || !ConstantStride) {
+      PEXP *EdgeDomPE = getDomainOnEdge(*OpBB, BB);
+      if (!EdgeDomPE) {
+        DEBUG(dbgs() << "PHI back edge has unknown domain!\n");
+        setScope(OldScope);
+        return visitParameter(I);
+      }
+
+      PVSet EdgeDom = EdgeDomPE->getDomain();
+      DEBUG(dbgs() << "EdgeDom: " << EdgeDom << " [LD: " << LoopDim << "]\n");
+      EdgeDom.setInputLowerBound(LoopDim - 1, 1);
+      DEBUG(dbgs() << "EdgeDom: " << EdgeDom << " [LD: " << LoopDim << "]\n");
+      OpAff.intersectDomain(EdgeDom);
+      delete EdgeDomPE;
+    }
+
+    DEBUG(dbgs() << "Back edge Op: " << OpAff << "\n");
+    BackEdgeOp.union_add(OpAff);
+  }
+
+  DEBUG(dbgs() << "Final Back edge Op: " << BackEdgeOp << "\n");
+  if (ConstantStride) {
+    BackEdgeOp = BackEdgeOp.perPiecePHIEvolution(Id, LoopDim - 1);
+    if (!BackEdgeOp) {
+      DEBUG(dbgs() << "TODO: non constant back edge operand value!\n");
+      setScope(OldScope);
+      return visitParameter(I);
+    }
+  }
+
+  DEBUG(dbgs() << "BackEdgeOp: " << BackEdgeOp << "\n");
+
+  PE->PWA = PVAff();
+  PE->PWA.union_add(BackEdgeOp);
+  PE->PWA.dropParameter(Id);
+  setScope(OldScope);
+
+  for (unsigned u = 0, e = I.getNumIncomingValues(); u != e; u++) {
+    auto *OpBB = I.getIncomingBlock(u);
+    if (L->contains(OpBB))
+      continue;
+
+    auto *OpVal = I.getIncomingValue(u);
+    auto *OpPE = visit(*OpVal);
+    if (PI.isNonAffine(OpPE)) {
+      return visitParameter(I);
+    }
+
+    PVAff OpAff = OpPE->getPWA();
+    assert(e > NumLatches);
+    if (e - NumLatches > 1 || !ConstantStride) {
+      PEXP *EdgeDomPE = getDomainOnEdge(*OpBB, BB);
+      if (!EdgeDomPE) {
+        return visitParameter(I);
+      }
+
+      PVSet EdgeDom = EdgeDomPE->getDomain();
+      EdgeDom.fixInputDim(LoopDim - 1, 0);
+      OpAff.intersectDomain(EdgeDom);
+      delete EdgeDomPE;
+    }
+
+    DEBUG(dbgs() << "Init Op: " << OpAff << "\n");
+    PE->PWA.union_add(OpAff);
+    PE->combine(OpPE);
+  }
+
+  PE->Kind = PEXP::EK_UNKNOWN_VALUE;
+  DEBUG(dbgs() << "PHI: " << PE->PWA << "\n");
+
+  return PE;
+}
+
+PEXP *PolyhedralExpressionBuilder::visitBinaryOperator(BinaryOperator &I) {
+
+  Value *Op0 = I.getOperand(0);
+  auto *PEOp0 = visitOperand(*Op0, I);
+  if (PI.isNonAffine(PEOp0))
+    return visitParameter(I);
+
+  Value *Op1 = I.getOperand(1);
+  auto *PEOp1 = visitOperand(*Op1, I);
+  if (PI.isNonAffine(PEOp1))
+    return visitParameter(I);
+
+  auto *PE = getOrCreatePEXP(I);
+  switch (I.getOpcode()) {
+  case Instruction::Add:
+    PE->assign(PEOp0, PEOp1, PVAff::createAdd);
+    PE->adjustInvalidAndKnownDomain();
+    return PE;
+  case Instruction::Sub:
+    PE->assign(PEOp0, PEOp1, PVAff::createSub);
+    PE->adjustInvalidAndKnownDomain();
+    return PE;
+
+  case Instruction::Mul:
+    if (PEOp0->Kind != PEXP::EK_INTEGER && PEOp1->Kind != PEXP::EK_INTEGER)
+      return visitParameter(I);
+    PE->assign(PEOp0, PEOp1, PVAff::createMultiply);
+    PE->adjustInvalidAndKnownDomain();
+    return PE;
+
+  case Instruction::SRem:
+// TODO: This is not yet compatible with the PHI handling which assumes
+// monotonicity!
+#if 0
+    if (PEOp1->Kind == PEXP::EK_INTEGER) {
+      auto NZ = PEOp1->PWA.nonZeroSet();
+      PEOp1->PWA.intersectDomain(NZ);
+      return PE->assign(PEOp0, PEOp1, isl_pw_aff_tdiv_r);
+    }
+#endif
+    return visitParameter(I);
+  case Instruction::SDiv:
+    if (PEOp1->Kind == PEXP::EK_INTEGER) {
+      auto NZ = PEOp1->PWA.nonZeroSet();
+      PEOp1->PWA.intersectDomain(NZ);
+      return PE->assign(PEOp0, PEOp1, PVAff::createSDiv);
+    }
+    return visitParameter(I);
+  case Instruction::Shl:
+    if (PEOp1->Kind == PEXP::EK_INTEGER) {
+      return PE->assign(PEOp0, PEOp1, PVAff::createShiftLeft);
+    }
+    return visitParameter(I);
+  case Instruction::UDiv:
+  case Instruction::AShr:
+  case Instruction::LShr:
+  case Instruction::URem:
+    // TODO
+    return visitParameter(I);
+
+  // Bit operations
+  case Instruction::And:
+    if (I.getType()->isIntegerTy(1)) {
+      PE->assign(PEOp0, PEOp1, PVAff::createMultiply);
+      PE->PWA.select(getOne(PE->PWA), getZero(PE->PWA));
+      return PE;
+    }
+    return visitParameter(I);
+  case Instruction::Or:
+    if (I.getType()->isIntegerTy(1)) {
+      PE->assign(PEOp0, PEOp1, PVAff::createAdd);
+      PE->PWA.select(getOne(PE->PWA), getZero(PE->PWA));
+      return PE;
+    }
+    return visitParameter(I);
+  case Instruction::Xor:
+    if (I.getType()->isIntegerTy(1)) {
+      auto OneBitXOR = [this](const PVAff &PWA0, const PVAff &PWA1) {
+        auto OnePWA = getOne(PWA0);
+        auto ZeroPWA = getZero(PWA0);
+        auto Mul = PVAff::createMultiply(PWA0, PWA1);
+        auto MulZero = Mul.zeroSet();
+        auto Add = PVAff::createAdd(PWA0, PWA1);
+        auto AddNonZero = Add.nonZeroSet();
+        auto TrueSet = MulZero.intersect(AddNonZero);
+        return PVAff(TrueSet).select(OnePWA, ZeroPWA);
+      };
+      return PE->assign(PEOp0, PEOp1, OneBitXOR);
+    }
+    if (auto *COp0 = dyn_cast<ConstantInt>(Op0))
+      if (COp0->isMinusOne()) {
+        PE->assign(PEOp0, PEOp1, PVAff::createMultiply);
+        PE->combine(PEOp0, PVAff::createAdd);
+      }
+    if (auto *COp1 = dyn_cast<ConstantInt>(Op1))
+      if (COp1->isMinusOne()) {
+        PE->assign(PEOp0, PEOp1, PVAff::createMultiply);
+        PE->combine(PEOp1, PVAff::createAdd);
+      }
+
+    // TODO
+    return visitParameter(I);
+  case Instruction::FAdd:
+  case Instruction::FSub:
+  case Instruction::FMul:
+  case Instruction::FDiv:
+  case Instruction::FRem:
+  case Instruction::BinaryOpsEnd:
+    break;
+  }
+
+  llvm_unreachable("Invalid Binary Operation");
+}
+
+PEXP *PolyhedralExpressionBuilder::visitAllocaInst(AllocaInst &I) {
+  return visitParameter(I);
+}
+
+PEXP *PolyhedralExpressionBuilder::visitInstruction(Instruction &I) {
+  DEBUG(dbgs() << "UNKNOWN INST " << I << "\n";);
+  assert(!I.getType()->isVoidTy());
+  return visitParameter(I);
+}
+
+PVSet PolyhedralExpressionBuilder::buildNotEqualDomain(
+    const PEXP *PE, ArrayRef<Constant *> CIs) {
+  assert(PE->Kind != PEXP::EK_NON_AFFINE && PE->PWA);
+
+  PVSet NotEqualDomain;
+  for (auto *CI : CIs) {
+    auto *CPE = visit(*static_cast<Value *>(CI));
+    assert(CPE->Kind == PEXP::EK_INTEGER && CPE->PWA && !CPE->InvalidDomain);
+
+    NotEqualDomain.intersect(
+        PVAff::buildConditionSet(ICmpInst::ICMP_NE, PE->PWA, CPE->PWA));
+  }
+
+  return NotEqualDomain;
+}
+
+PVSet PolyhedralExpressionBuilder::buildEqualDomain(const PEXP *PE,
+                                                    Constant &CI) {
+  assert(PE->Kind != PEXP::EK_NON_AFFINE && PE->PWA);
+
+  auto *CPE = visit(static_cast<Value &>(CI));
+  assert(CPE->Kind == PEXP::EK_INTEGER && CPE->PWA && !CPE->InvalidDomain);
+
+  return PVAff::buildConditionSet(ICmpInst::ICMP_EQ, PE->PWA, CPE->PWA);
+}
+
+// ------------------------------------------------------------------------- //
+
+PolyhedralValueInfo::PolyhedralValueInfo(PVCtx Ctx, LoopInfo &LI)
+    : Ctx(Ctx), LI(LI), PEBuilder(new PolyhedralExpressionBuilder(*this)) {
+}
+
+PolyhedralValueInfo::~PolyhedralValueInfo() { delete PEBuilder; }
+
+const PEXP *PolyhedralValueInfo::getDomainFor(BasicBlock *BB, Loop *Scope) {
+  PEBuilder->setScope(Scope);
+  return PEBuilder->getDomain(*BB);
+}
+
+const PEXP *PolyhedralValueInfo::getPEXP(Value *V, Loop *Scope) {
+  PEBuilder->setScope(Scope);
+  return PEBuilder->visit(*V);
+}
+
+PVId PolyhedralValueInfo::getParameterId(Value &V) {
+  return PEBuilder->getParameterId(V);
+}
+
+bool PolyhedralValueInfo::isUnknown(const PEXP *PE) const {
+  return PE->Kind == PEXP::EK_UNKNOWN_VALUE;
+}
+
+bool PolyhedralValueInfo::isInteger(const PEXP *PE) const {
+  return PE->Kind == PEXP::EK_INTEGER;
+}
+
+bool PolyhedralValueInfo::isConstant(const PEXP *PE) const {
+  return isInteger(PE) && PE->PWA.getNumPieces() == 1;
+}
+
+bool PolyhedralValueInfo::isAffine(const PEXP *PE) const {
+  return PE->Kind != PEXP::EK_NON_AFFINE && PE->isInitialized();
+}
+
+bool PolyhedralValueInfo::isNonAffine(const PEXP *PE) const {
+  return PE->Kind == PEXP::EK_NON_AFFINE;
+}
+
+bool PolyhedralValueInfo::hasScope(const PEXP *PE, Loop *Scope) const {
+  SmallVector<Value *, 4> Values;
+  getParameters(PE, Values);
+  for (Value *V : Values) {
+    auto *I = dyn_cast<Instruction>(V);
+    if (!I)
+      continue;
+    if (!Scope || Scope->contains(I))
+      return false;
+  }
+  return true;
+}
+
+bool PolyhedralValueInfo::hasFunctionScope(const PEXP *PE) const {
+  return hasScope(PE, nullptr);
+}
+
+void PolyhedralValueInfo::getParameters(const PEXP *PE,
+                                        SmallVectorImpl<PVId> &Values) const {
+  const PVAff &PWA = PE->getPWA();
+  PWA.getParameters(Values);
+}
+
+void PolyhedralValueInfo::getParameters(
+    const PEXP *PE, SmallVectorImpl<Value *> &Values) const {
+  const PVAff &PWA = PE->getPWA();
+  PWA.getParameters(Values);
+}
+
+bool PolyhedralValueInfo::isKnownToHold(Value *LHS, Value *RHS,
+                                        ICmpInst::Predicate Pred,
+                                        Instruction *IP, Loop *Scope) {
+  const PEXP *LHSPE = getPEXP(LHS, Scope);
+  if (isNonAffine(LHSPE))
+    return false;
+
+  const PEXP *RHSPE = getPEXP(RHS, Scope);
+  if (isNonAffine(RHSPE))
+    return false;
+
+  const PEXP *IPDomPE = IP ? getDomainFor(IP->getParent(), Scope) : nullptr;
+  if (IP && (isNonAffine(IPDomPE) || !IPDomPE->getInvalidDomain().isEmpty()))
+    return false;
+
+  PVSet LHSInvDom = LHSPE->getInvalidDomain();
+  PVSet RHSInvDom = RHSPE->getInvalidDomain();
+  if (IPDomPE) {
+    LHSInvDom.intersect(IPDomPE->getDomain());
+    RHSInvDom.intersect(IPDomPE->getDomain());
+  }
+
+  if (!LHSInvDom.isEmpty() || !RHSInvDom.isEmpty())
+    return false;
+
+  PVAff LHSAff = LHSPE->getPWA();
+  PVAff RHSAff = RHSPE->getPWA();
+
+  if (IPDomPE) {
+    LHSAff.intersectDomain(IPDomPE->getDomain());
+    RHSAff.intersectDomain(IPDomPE->getDomain());
+  }
+
+  auto FalseDomain = PVAff::buildConditionSet(
+      ICmpInst::getInversePredicate(Pred), LHSAff, RHSAff);
+  return FalseDomain.isEmpty();
+}
+
+void PolyhedralValueInfo::print(raw_ostream &OS) const {}
+
+// ------------------------------------------------------------------------- //
+
+char PolyhedralValueInfoWrapperPass::ID = 0;
+
+void PolyhedralValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<LoopInfoWrapperPass>();
+  AU.setPreservesAll();
+}
+
+void PolyhedralValueInfoWrapperPass::releaseMemory() {
+  F = nullptr;
+  delete PI;
+  PI = nullptr;
+}
+
+bool PolyhedralValueInfoWrapperPass::runOnFunction(Function &F) {
+
+  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+
+  delete PI;
+  PI = new PolyhedralValueInfo(Ctx, LI);
+
+  this->F = &F;
+
+  return false;
+}
+
+void PolyhedralValueInfoWrapperPass::print(raw_ostream &OS,
+                                           const Module *) const {
+  PI->print(OS);
+
+  if (!F)
+    return;
+
+  PolyhedralValueInfoWrapperPass &PIWP =
+      *const_cast<PolyhedralValueInfoWrapperPass *>(this);
+  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+
+  for (auto &BB : *PIWP.F) {
+    Loop *Scope = LI.getLoopFor(&BB);
+    do {
+      PIWP.PI->getDomainFor(&BB, Scope);
+      for (auto &Inst : BB)
+        if (!Inst.getType()->isVoidTy())
+          PIWP.PI->getPEXP(&Inst, Scope);
+      if (!Scope)
+        break;
+      Scope = Scope->getParentLoop();
+    } while (true);
+  }
+
+  for (auto &BB : *PIWP.F) {
+    Loop *Scope = LI.getLoopFor(&BB);
+    do {
+      OS << "Scope: " << (Scope ? Scope->getName() : "<none>") << "\n";
+      const PEXP *PE = PIWP.PI->getDomainFor(&BB, Scope);
+      OS << "Domain of " << BB.getName() << ":\n";
+      OS << "\t => " << PE << "\n";
+      for (auto &Inst : BB) {
+        if (Inst.getType()->isVoidTy()) {
+          OS << "\tValue of " << Inst << ":\n";
+          OS << "\t\t => void type!\n";
+          continue;
+        }
+        const PEXP *PE = PIWP.PI->getPEXP(&Inst, Scope);
+        OS << "\tValue of " << Inst << ":\n";
+        OS << "\t\t => " << PE << "\n";
+        SmallVector<Value *, 4> Values;
+        PIWP.PI->getParameters(PE, Values);
+        if (Values.empty())
+          continue;
+        OS << "\t\t\tParams:\n";
+        for (Value *Val : Values)
+          OS << "\t\t\t - " << *Val << "\n";
+      }
+
+      if (!Scope)
+        break;
+      Scope = Scope->getParentLoop();
+    } while (true);
+  }
+}
+
+FunctionPass *llvm::createPolyhedralValueInfoWrapperPass() {
+  return new PolyhedralValueInfoWrapperPass();
+}
+
+void PolyhedralValueInfoWrapperPass::dump() const {
+  return print(dbgs(), nullptr);
+}
+
+AnalysisKey PolyhedralValueInfoAnalysis::Key;
+
+PolyhedralValueInfo
+PolyhedralValueInfoAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
+  auto &LI = AM.getResult<LoopAnalysis>(F);
+  return PolyhedralValueInfo(Ctx, LI);
+}
+
+INITIALIZE_PASS_BEGIN(PolyhedralValueInfoWrapperPass, "polyhedral-value-info",
+                      "Polyhedral value analysis", false, true);
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
+INITIALIZE_PASS_END(PolyhedralValueInfoWrapperPass, "polyhedral-value-info",
+                    "Polyhedral value analysis", false, true)