[Polly] [RFC] Calculate AST expression type

[maxf]

Summary

(This is a work-in-progress, feedback is welcome).
Until now, Polly always uses 64 bits for each expression as there is no
way to figure out the correct type. This patch changes the behavour:

• (isl) At AST generation time the type of each AST expression is calculated. In the base case, this is the exact minimal type, optionally types can be approximated to reduce compile-time overhead
• (isl) During this phase, we now take the concept of the 'biggest native type' into account. The biggest native type (fixed 64 bit atm) is the largest type we *want* to generate. Whenever an expression exceeds this size, a precondition is generated that, when satisfied, assures that the biggest native type is enough to hold said expression

Polly then uses this information to:

• Take all preconditions into account when creating the run condition of a SCoP
• Use a correct type for each expression. The default behaviour at the moment is to still use 64 bits per default to save on sext's.

The isl part of this patch has been partially discussed previously on
the isl mailinglist. Before upstreaming this into isl, we need to agree
on an interface, therefore it seems resonable to also put this on
Phabricator.

[maxf]

Note: Modifications in codegen.c are only for debugging.

lib/External/isl/codegen.c

304

The changes in this file are for debugging only and will be removed for the final version.

[grosser]

Hi Maximilian,

thank you for pushing your WIP-patch. I know it still must be cleaned up, but here some comments which would make it easier to reason about the current patch:

1. Many test cases fail because we print casts when printing the generated AST. Can you disable the printing of these casts? They only distract and removing them makes it a lot easier to understand what is still failing,

2. In ScopInfo/int2ptr_ptr2int.ll and some others the IR is changed. Do you have an idea why? I would expect for us to not yet change the IR, no?

Best,
Tobias

include/polly/CodeGen/IslAst.h

86

Could you add documentation?

include/polly/CodeGen/IslExprBuilder.h

188

Could you add documentation?

265

Could you add documentation?

(I know there is not too much documentation around, but as this function is doing something rather special it would be good to document it).

322

Could you add documentation?

lib/CodeGen/IslAst.cpp

426

Could you add flags to be able to control all configurations?

428

Just write:

isl_options_set_ast_build_compute_bounds(Ctx, ComputeBounds);

without the if-condition around.

517

Would it make sense to use `isl_ast_node_foreach_descendant_top_down```?

lib/CodeGen/IslExprBuilder.cpp

20

No need to include iostream, just use llvm::errs()

736

`llvm::errs() <<` is what we use by default.

lib/CodeGen/IslNodeBuilder.cpp

550

descending

lib/External/isl/isl_ast_graft_private.h

102 ↗

(On Diff #106830)

Unrelated

lib/External/isl/isl_options_private.h

62

Alignment?

[maxf]

Hello Tobias,

as for (1): Hmm, I can do that, at least for now. I'd rather have them in in the final version so that we also test this feature whenever possible, but I guess it makes sense to differ between tests that fail and tests that only fail due to format changes now. I'd disable printing bounds in ISL_C format for now and put it back in the final version, along with fixed testcases, if that's okay with you?

for (2): Not exactly. There are two reasons why the given test fails:

• We already generate a (more restrictive) precondition, the failure type you observed can be introduced because the register numbers increase because we codegenerate the precondition in front of the loop which now needs more registers.
• We only use 64 bits when we can proof that it will be enough. In the test case you indicated this seems not to be possible inside the precondition as the inputs are already 64 bit integers if I read the test correctly.

Best,

Maximilian

lib/CodeGen/IslAst.cpp

517

Ah, I didn't know about that one. Well, this function visits all AST nodes and the expression trees they reference (that's why the method is overloaded), so in order to use isl_ast_node_foreach_descendant_top_down I'd still need a function that does a big switch on the node statement, so it wouldn't make the code much shorter.

[etherzhhb]

Just out of curiosity, are we supposed to change the isl inside polly? what is the relationship between this isl and the "upstream" isl?

[maxf]

No, this is not supposed to only change isl inside of polly. Among the things that were noted when I originally wanted to upstream the code into isl is a lack of motivation for the interface, since at that time it was a big patch to isl only. After discussion with Sven, we agreed on changing the original interface (store information in AST (expression) nodes instead of directly inside expressions) but before cleaning up and preparing another round of patches and resubmitting it seems like a good idea to show the whole code in one place so that we can agree on what and how we'd like isl to provide.

[grosser]

In D35471#812102, @maxf wrote:

Hello Tobias,

as for (1): Hmm, I can do that, at least for now. I'd rather have them in in the final version so that we also test this feature whenever possible, but I guess it makes sense to differ between tests that fail and tests that only fail due to format changes now. I'd disable printing bounds in ISL_C format for now and put it back in the final version, along with fixed testcases, if that's okay with you?

I personally believe the printed types in Polly make the output more difficult to read. I would prefer to not have the types there everywhere.

for (2): Not exactly. There are two reasons why the given test fails:

• We already generate a (more restrictive) precondition, the failure type you observed can be introduced because the register numbers increase because we codegenerate the precondition in front of the loop which now needs more registers.
• We only use 64 bits when we can proof that it will be enough. In the test case you indicated this seems not to be possible inside the precondition as the inputs are already 64 bit integers if I read the test correctly.

I see. Interesting.

Best,
Tobias

lib/CodeGen/IslAst.cpp

517

If it does not simplify the code, feel free to leave it as it is.

[maxf]

First round of cleanups:

• Down to four test cases that fail code generation
• Adressed most comments
• Added an option to isl to not print bounds on values that polly enables per default

[grosser]

Nice. I will have a look immediately. I am also at ETH tomorrow in case you wanna chat.

[grosser]

Hi Maximilian,

here another round of reviews:

It seems we loose some "braces":

/home/grosser/Projects/polly/git/tools/polly/test/ScheduleOptimizer/pattern-matching-based-opts_5.ll:100:15: error: expected string not found in input
; CHECK-NEXT: Stmt_for_body6(-((ni + 4) % 4) + ni + c6, 2048 * c0 + 8 * c3 + c7, 256 * c1 + c5);
              ^
<stdin>:80:2: note: scanning from here
 Stmt_for_body6(-ni + 4 % 4 + ni + c6, 2048 * c0 + 8 * c3 + c7, 256 * c1 + c5);

lib/CodeGen/IslAst.cpp

546

You are syntactically connecting preconditions with a "&&". This does not allow for any simplifications. Instead, I suggest to intersect Cond, and only at the very end to build preconditions.

lib/CodeGen/IslExprBuilder.cpp

804

Please use full types, rather than 'auto'. (except for iterators or where the type is obvious)

lib/External/isl/isl_ast_codegen.c

1649

Unrelated change.

[grosser]

More comments:

• Can you check if the constructors miss some isl cleanups.
• There are more isl print output changes

[maxf]

Another round of cleanups:

• Excluding GPU tests, we're down to 9 unexpected failures, two of which are miscompiles
• isl printer output fixed
• Usage of computed bounds disabled for now until as they will result in at least some changes to our test suite.

[grosser]

Hi Maximilian,

this is very cool! Good work!

Best,
Tobias

[maxf]

Another round of fixes:

• Fix last miscompiles in polly unittests. This brings us down to two testcases where the generated IR changed (GPU test cases excluded).
• Prepare PPCGCodeGen. It's still not working (memory accesses need to be handled), but move initialization of options on isl_ctx so that they are set early enough for this. Also fix the addditional RTC generated by PPCGCodeGen.
• Small cleanups

[maxf]

Another round of fixes:

• All unit tests pass now. The last remaining test was changed to reflect the newly generated preconditions
• Types are now limited to 63 bits to leave space for the sign bit
• Fixed preconditions meaning the exact opposite of what was intended
• Generate preconditions and parts of polly-acc generated code (e.g. host <-> device memory transfer) using fixed 64 bits
• More code cleanup

[grosser]

Hi Maximilian,

this looks indeed very good! Thanks for pushing this forward! I did a first round with stylistic comments.

Could you also please add test cases for some of the code generation changes. I will do another round with comments on the content of the patch itself soonish.

include/polly/CodeGen/IslExprBuilder.h

188

preceeded

194

Add "." at end of sentence?

270

THE inner

lib/CodeGen/IslAst.cpp

525

No braces around single statement bodies.

lib/CodeGen/IslExprBuilder.cpp

737

No need for else, If the previous branch condition holds, we anyhow assert.

744

"." at end of sentence. Also, can you check the grammar. Something seems wrong.

lib/CodeGen/IslNodeBuilder.cpp

95

I removed this in r309533. Thank you for spotting!

552

What is the "compute case"?

lib/External/isl/isl_ast_build_expr.c

2757

Indentation?

lib/External/isl/isl_ast_build_private.h

208

Indentation?

lib/External/isl/isl_ast_codegen.c

1441

Unrelated change.

[grosser]

Another set of smaller changes.

I also have another more higher-level comment for this. Could you possibly add a small set of test cases that focuses on:

1. How we derive run-time conditions when generating 64 bit computations
2. How we actually generate minimal types (maybe add a mode for this?)

include/polly/CodeGen/IslAst.h

85

Why are there two whitespaces after the parameter names?

100

Why are there two whitespaces after the parameter names?

include/polly/CodeGen/IslExprBuilder.h

173

"for e.g." -> "for example"

Now, instead of describing the user of this (which might change and we then certainly won't update this comment), please describe what the change to the generated code here is.

lib/CodeGen/IslAst.cpp

541

No braces around single-assignment bodies.

[jdoerfert]

Just out of curiosity, did you compare the results (compile time, runtime, number of required overflow tracking intrinsics,...) to the simple bit-width tracking that was implemented in the IslExpr builder?

[grosser]

Hi Johannes,

AFAIR you talk about: https://llvm.org/svn/llvm-project/polly/trunk@271878

Thanks for initiating a discussion which we should have had a year ago. Maximilian is about to generate some numbers / example test cases. We will get back to you soonish.

Best,
Tobias

[grosser]

Hi Johannes,

just to clarify. I never said your approach is wrong or has an entirely wrong design, but said that a similar approach caused issues in graphite, hence I would like to understand your patch in detail before going this road. I still don't fully understand how this works, but tried some simple examples with https://llvm.org/svn/llvm-project/polly/trunk@271878. Maybe you can cross-check if what I observe is the intended behavior of your patch.

define void @foo32(float* %A, i32 %n) {
entry:
  br label %loop

loop:
  %indvar = phi i32 [0, %entry], [%indvar.next, %loop]
  %indvar.next = add nsw i32 %indvar, 1
  %cmp = icmp slt i32 %indvar, %n
  store float 1.0, float* %A
  br i1 %cmp, label %loop, label %exit

exit:
  ret void
}

define void @foo64(float* %A, i64 %n) {
entry:
  br label %loop

loop:
  %indvar = phi i64 [0, %entry], [%indvar.next, %loop]
  %indvar.next = add nsw i64 %indvar, 1
  %cmp = icmp slt i64 %indvar, %n
  store float 1.0, float* %A
  br i1 %cmp, label %loop, label %exit

exit:
  ret void
}

when I change the schedule from [i] -> [i + 1024] (using jscop to simulate a scheduler which decides to perform skewing) I get the following ASTs:

foo32:
if (1)

    {
      for (int c0 = 1024; c0 <= n + 1024; c0 += 1)
        Stmt_loop(c0 - 1024);
      if (n <= -1)
        Stmt_loop(0);
    }

foo64:

if (1)


    {
      for (int c0 = 1024; c0 <= n + 1024; c0 += 1)
        Stmt_loop(c0 - 1024);
      if (n <= -1)
        Stmt_loop(0);
    }

The code that is generated for foo32 to model the addition n + 1024 is:

%0 = sext i32 %n to i33
 %1 = add nsw i33 %0, 1024

This seems to be correct. Also, in general, I feel that generating non power-of-two types is something we should better avoid.

The code that is generated for foo64 to model the addition n + 1024 is:

%0 = add nsw i64 %n, 1024

but it seems no run-time bounds checks are generated. Your commit message says: " If the type adjustment is not possible, thus the necessary type is bigger than the type value of --polly-max-expr-bit-width, we will use assumptions to verify the computation will not wrap." hence I would expect a RTC to be generated. Is the behavior I observe the expected behavior?

[jdoerfert]

In D35471#883365, @grosser wrote:

I never said your approach is wrong or has an entirely wrong design, but said that a similar approach caused issues in graphite,

I am pretty sure you did say exactly that.

In D35471#883365, @grosser wrote:

hence I would like to understand your patch in detail before going this road. I still don't fully understand how this works, but tried some simple examples with https://llvm.org/svn/llvm-project/polly/trunk@271878. Maybe you can cross-check if what I observe is the intended behavior of your patch.

I am not sure what this is supposed to achieve. I did (~1.5 years ago) try to get this in in order to improve performance but now I have a lot of other things on my plate. I asked if you compared yourself against this but it's OK if you feel that is impossible because the patch is hard to understand.

%0 = sext i32 %n to i33
 %1 = add nsw i33 %0, 1024

This seems to be correct. Also, in general, I feel that generating non power-of-two types is something we should better avoid.

That could have been done "virtually" but the discussion didn't come up.

The code that is generated for foo64 to model the addition n + 1024 is:

%0 = add nsw i64 %n, 1024

but it seems no run-time bounds checks are generated. Your commit message says: " If the type adjustment is not possible, thus the necessary type is bigger than the type value of --polly-max-expr-bit-width, we will use assumptions to verify the computation will not wrap." hence I would expect a RTC to be generated. Is the behavior I observe the expected behavior?

To be honest, I don't remember.

[grosser]

In D35471#883398, @jdoerfert wrote:

In D35471#883365, @grosser wrote:

I never said your approach is wrong or has an entirely wrong design, but said that a similar approach caused issues in graphite,

I am pretty sure you did say exactly that.

In D35471#883365, @grosser wrote:

hence I would like to understand your patch in detail before going this road. I still don't fully understand how this works, but tried some simple examples with https://llvm.org/svn/llvm-project/polly/trunk@271878. Maybe you can cross-check if what I observe is the intended behavior of your patch.

I am not sure what this is supposed to achieve. I did (~1.5 years ago) try to get this in in order to improve performance but now I have a lot of other things on my plate. I asked if you compared yourself against this but it's OK if you feel that is impossible because the patch is hard to understand.

It is hard to compare -- quality-wise -- if I am not certain about how the patch works. We will at some point need to solve this problem in LLVM and if you have a good solution, I would like to mention this in my presentation.

%0 = sext i32 %n to i33
 %1 = add nsw i33 %0, 1024

This seems to be correct. Also, in general, I feel that generating non power-of-two types is something we should better avoid.

That could have been done "virtually" but the discussion didn't come up.

Unfortunately, we did not manage to have one.

What do you mean by 'virtually'? Keeping track of the type information on the side and then pushing things out. Sure, this could have been done.

The code that is generated for foo64 to model the addition n + 1024 is:

%0 = add nsw i64 %n, 1024

but it seems no run-time bounds checks are generated. Your commit message says: " If the type adjustment is not possible, thus the necessary type is bigger than the type value of --polly-max-expr-bit-width, we will use assumptions to verify the computation will not wrap." hence I would expect a RTC to be generated. Is the behavior I observe the expected behavior?

To be honest, I don't remember.

That's unfortunate as this is the point I am very unclear about and I fail to find the corresponding code. Maybe you want to have a brief look. The patch is rather short and likely for you easy to understand.

Best,
Tobias

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

1029

Can we create a wrapper that does this? Example,

template<typename FTy>
auto scopeFixedSizeMode(FTy F, IslExprBuilder &ExprBuilder) -> decltype(FTy()) typename std::enable_if<!std::is_same<decltype(std::declval<FTy>()()), void>::value,
                 decltype(std::declval<FTy>()())>::type
scopedFixedSizeMode(FTy F) {
    ExprBuilder.setBuildMode(true);
    auto Ret = F();
    ExprBuilder.setBuildMode(false);
    return Ret;
}

template <typename FTy>
typename std::enable_if<std::is_same<decltype(std::declval<FTy>()()), void>::value, void>::type
scopedFixedSizeMode(FTy F) {
    ExprBuilder.setBuildMode(true);
    F();
    ExprBuilder.setBuildMode(false);
}

The wrapper right now is crazy, but there has to be a way for this to be more "canonical".

[philip.pfaffe]

lib/CodeGen/PPCGCodeGeneration.cpp

1029

Here's a way to express the same thing more nicely:

template<typename T> T Foo(std::function<T()> F) {                              
  auto R = F();                                                                 
  return R;                                                                     
}                                                                               
                                                                                
void Foo(std::function<void()> F) {                                             
  F();                                                                          
}

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

1029

This should let us write

ExprBuilder.setFixedSizeMode(true);
Value *NumElements = ExprBuilder.create(Res);
ExprBuilder.setFixedSizeMode(false);

as:

Value *NumElements = scopedFixedSizeMode([&] () { ExprBuilder.create(Res); });

I primarily want this because it's much less error prone.

[maxf]

More cleanups. Also fixed a pathologic edge case...

[maxf]

lib/CodeGen/PPCGCodeGeneration.cpp

1029

Sounds good. We should probably also think about doing this for setTrackOverflow (which originally convinced me to use a simple flag for this).

include/polly/CodeGen/IslAst.h

 private:
   Scop &S;
   isl_ast_node *Root;
   isl_ast_expr *RunCondition;
   std::shared_ptr<isl_ctx> Ctx;
 
   IslAst(Scop &Scop);
   void init(const Dependences &D);
+
+  /// Extract precondition to include in RTC from an isl ast node
+  ///
+  /// @param Node The node to extract the condition from
+  /// @param Cond The set of conditions to add constraints to
+  ///
+  /// @returns A set of constraints from \p Node including \p Cond
+  ///
+  /// This method visits all nodes in the AST tree given by \p Node,
+  /// passing off all expression trees to
+  /// @link extractPreconditionFromAST(Expr, Cond)
+  isl_set *extractPreconditionFromAST(isl_ast_node *Node, isl_set *Cond);
+
+  /// Extract precondition to include in RTC from an isl ast expression
+  ///
+  /// @param Expr The expression to extract the condition from
+  /// @param Cond The set of conditions to add constraints to
+  ///
+  /// @returns A set of constraints from \p Expr including \p Cond
+  isl_set *extractPreconditionFromAST(isl_ast_expr *Expr, isl_set *Cond);
 };
 
 class IslAstInfo {
 public:
   using MemoryAccessSet = SmallPtrSet<MemoryAccess *, 4>;
 
   /// Payload information used to annotate an AST node.
   struct IslAstUserPayload {

include/polly/CodeGen/IslExprBuilder.h

public:
   /// Note that this will reset the tracking state and that tracking is only
   /// allowed if the last tracked expression dominates the current insert point.
   void setTrackOverflow(bool Enable);
 
   /// Return the current overflow status or nullptr if it is not tracked.
   ///
   /// @return A nullptr if tracking is disabled or otherwise an i1 that has the
   ///         value of "0" if and only if no overflow happened since tracking
   ///         was enabled.
   llvm::Value *getOverflowState() const;
 
   /// Create LLVM-IR that computes the memory location of an access expression.
   ///
   /// For a given isl_ast_expr[ession] of type isl_ast_op_access this function
   /// creates IR that computes the address the access expression refers to.
   ///
   /// @param Expr The ast expression of type isl_ast_op_access
   ///             for which we generate LLVM-IR.
   ///
   /// @return The llvm::Value* containing the result of the computation.
   llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr);
 
+  /// Inject \p Bound into the expression generator. Normally, a node in the
+  /// AST tree is preceded by it's bound, therefore it's sufficient to store
+  /// the bound in @link CurrentBound before descending.
+  /// However, when generating nodes manually (e.g. as done in our
+  /// LoopGenerators), this does not work as the nodes we create do not form
+  /// a full AST tree. This function is therefore used in those instances to
+  /// manually inject a bound for the next expression before calling
+  /// @link create.
+  ///
+  /// @param Bound The bound to inject
+  void injectBound(__isl_keep isl_ast_expr *Bound);
+
+  /// Execute the enclosed funtion with @link FixedSizeMode set to true.
+  template <typename R> R withFixedSizeMode(std::function<R()> Fun) {
+    FixedSizeMode = true;
+    R Result = Fun();
+    FixedSizeMode = false;
+    return Result;
+  };
+
+  /// Execute the enclosed funtion with @link FixedSizeMode set to true.
+  void withFixedSizeMode(std::function<void()> Fun) {
+    FixedSizeMode = true;
+    Fun();
+    FixedSizeMode = false;
+  };
+
 private:
+  /// The current bound, that is the bound that we expect the next call of
+  /// @link getType to refer to. This is set everytime we encounter an AST
+  /// expression node with a type of isl_ast_expr_bound_t and cleared on every
+  /// call to @link getType.
+  isl_ast_expr *CurrentBound = nullptr;
+
+  /// Whether to always use 64 bits.
+  /// If enabled, the expression generator will always use 64 bit types
+  /// regardless of what bounds were actually calculated. This is useful for
+  /// example when generating the RTC, where we track overflows and therefore
+  /// do not need to use types >64 bits, which can be generated for ISL in this
+  /// context.
+  bool FixedSizeMode = false;
+
   Scop &S;
 
   /// Flag that will be set if an overflow occurred at runtime.
   ///
   /// Note that this flag is by default a nullptr and if it is a nullptr
   /// we will not record overflows but simply perform the computations.
   /// The intended usage is as follows:
   ///   - If overflows in [an] expression[s] should be tracked, call
private:
   llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr);
   llvm::Value *createId(__isl_take isl_ast_expr *Expr);
   llvm::Value *createInt(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr);
 
+  /// Create a 'bound': An expression node with a type of isl_ast_expr_bound_t
+  /// is inserted into the AST expression tree directly above each 'numerical'
+  /// node. To use them, we store the bound in @link CurrentBound before
+  /// generating the inner expression which is then read by @link getType when
+  /// asked for the expression's type.
+  /// When encountering a bound while the previous bound is not consumed, it is
+  /// saved and restored after the subtree has been generated.
+  ///
+  /// @param Expr The expression to generate
+  /// @return The value the expression represents
+  llvm::Value *createBound(__isl_take isl_ast_expr *Expr);
+
   /// Create a binary operation @p Opc and track overflows if requested.
   ///
   /// @param OpC  The binary operation that should be performed [Add/Sub/Mul].
   /// @param LHS  The left operand.
   /// @param RHS  The right operand.
   /// @param Name The (base) name of the new IR operations.
   ///
   /// @return A value that represents the result of the binary operation.
private:
   /// @param RHS  The right operand.
   /// @param Name The (base) name of the new IR operations.
   ///
   /// @return A value that represents the result of the multiplication.
   llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS,
                          const llvm::Twine &Name = "");
 };
 } // namespace polly
 
 #endif
+/* vim: set ts=8 sw=8 tw=0 noet :*/

lib/Analysis/ScopInfo.cpp

static cl::opt<bool, true> XUseInstructionNames(
     cl::desc("Use LLVM-IR names when deriving statement names"),
     cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
     cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool> PollyPrintInstructions(
     "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
     cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
 
+static cl::opt<bool> ComputeBounds(
+    "polly-ast-compute-bounds",
+    cl::desc("Compute bounds on isl_asl_exprs to determine their type"),
+    cl::init(true), cl::Hidden, cl::Optional, cl::cat(PollyCategory));
+
+static cl::opt<bool> ApproximateBounds(
+    "polly-ast-approximate-bounds",
+    cl::desc("Approximate compute bounds to speed up computation"),
+    cl::init(true), cl::Hidden, cl::Optional, cl::cat(PollyCategory));
+
+static cl::opt<int> MaximumNativeType(
+    "polly-ast-maximum-native-type",
+    cl::desc("Maximum native type, try to keep types smaller than this"),
+    cl::init(63), cl::Hidden, cl::Optional, cl::cat(PollyCategory));
+
 //===----------------------------------------------------------------------===//
 
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static __isl_give isl_schedule *
 combineInSequence(__isl_take isl_schedule *Prev,
                   __isl_take isl_schedule *Succ) {
: SE(&ScalarEvolution), R(R), name(R.getNameStr()), IsOptimized(false),
       HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false),
       MaxLoopDepth(0), CopyStmtsNum(0), SkipScop(false), DC(DC), ORE(ORE),
       IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr),
       Affinator(this, LI), AssumedContext(nullptr), InvalidContext(nullptr),
       Schedule(nullptr),
       ID(getNextID((*R.getEntry()->getParent()).getName().str())) {
   if (IslOnErrorAbort)
     isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
+  isl_options_set_ast_build_compute_bounds(getIslCtx(), ComputeBounds);
+  isl_options_set_ast_build_maximum_native_type(getIslCtx(), MaximumNativeType);
+  isl_options_set_ast_build_approximate_computed_bounds(getIslCtx(),
+                                                        ApproximateBounds);
+  isl_options_set_ast_build_print_computed_bounds(getIslCtx(), false);
+
   buildContext();
 }
 
 void Scop::foldSizeConstantsToRight() {
   isl_union_set *Accessed = isl_union_map_range(getAccesses());
 
   for (auto Array : arrays()) {
     if (Array->getNumberOfDimensions() <= 1)

lib/CodeGen/IslAst.cpp

 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Support/Debug.h"
 #include "isl/aff.h"
+#include "isl/ast.h"
 #include "isl/ast_build.h"
 #include "isl/list.h"
 #include "isl/map.h"
 #include "isl/set.h"
 #include "isl/union_map.h"
 
 #include <utility>
 
void IslAst::init(const Dependences &D) {
 
   // Skip AST and code generation if there was no benefit achieved.
   if (!benefitsFromPolly(S, PerformParallelTest))
     return;
 
   isl_ctx *Ctx = S.getIslCtx();
   isl_options_set_ast_build_atomic_upper_bound(Ctx, true);
   isl_options_set_ast_build_detect_min_max(Ctx, true);
   isl_ast_build *Build;
   AstBuildUserInfo BuildInfo;
 
   if (UseContext)
     Build = isl_ast_build_from_context(S.getContext());
   else
     Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
 
   Build = isl_ast_build_set_at_each_domain(Build, AtEachDomain, nullptr);
 
   if (PerformParallelTest) {
if (PerformParallelTest) {
 
     Build = isl_ast_build_set_after_each_mark(Build, &astBuildAfterMark,
                                               &BuildInfo);
   }
 
   RunCondition = buildRunCondition(S, Build);
 
   Root = isl_ast_build_node_from_schedule(Build, S.getScheduleTree());
+  isl_set *AdditionalConditionSet =
+      extractPreconditionFromAST(isl_ast_node_copy(Root), nullptr);
+  if (AdditionalConditionSet) {
+    AdditionalConditionSet =
+        isl_set_gist(AdditionalConditionSet, isl_set_params(S.getContext()));
+    isl_ast_expr *AdditionalConditions =
+        isl_ast_build_expr_from_set(Build, AdditionalConditionSet);
+    // As the set contains all parameter values we want to exclude, we need to
+    // negate it.
+    AdditionalConditions = isl_ast_expr_neg(AdditionalConditions);
+    RunCondition = isl_ast_expr_and(RunCondition, AdditionalConditions);
+  }
 
   isl_ast_build_free(Build);
 }
 
+isl_set *IslAst::extractPreconditionFromAST(isl_ast_node *Node, isl_set *Cond) {
+  if (!Node) {
+    return Cond;
+  }
+  switch (isl_ast_node_get_type(Node)) {
+  case isl_ast_node_error:
+    llvm_unreachable("Code generation error");
+  case isl_ast_node_mark:
+    Cond = extractPreconditionFromAST(isl_ast_node_mark_get_node(Node), Cond);
+    isl_ast_node_free(Node);
+    break;
+  case isl_ast_node_for:
+    Cond = extractPreconditionFromAST(isl_ast_node_for_get_init(Node), Cond);
+    Cond = extractPreconditionFromAST(isl_ast_node_for_get_inc(Node), Cond);
+    Cond =
+        extractPreconditionFromAST(isl_ast_node_for_get_iterator(Node), Cond);
+    Cond = extractPreconditionFromAST(isl_ast_node_for_get_body(Node), Cond);
+    isl_ast_node_free(Node);
+    break;
+  case isl_ast_node_if:
+    Cond = extractPreconditionFromAST(isl_ast_node_if_get_cond(Node), Cond);
+    Cond = extractPreconditionFromAST(isl_ast_node_if_get_then(Node), Cond);
+    Cond = extractPreconditionFromAST(isl_ast_node_if_get_else(Node), Cond);
+    isl_ast_node_free(Node);
+    break;
+  case isl_ast_node_user:
+    Cond = extractPreconditionFromAST(isl_ast_node_user_get_expr(Node), Cond);
+    isl_ast_node_free(Node);
+    break;
+  case isl_ast_node_block:
+    isl_ast_node_list *List = isl_ast_node_block_get_children(Node);
+
+    for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i) {
+      Cond = extractPreconditionFromAST(isl_ast_node_list_get_ast_node(List, i),
+                                        Cond);
+    }
+    isl_ast_node_list_free(List);
+    isl_ast_node_free(Node);
+    break;
+  }
+  return Cond;
+}
+
+isl_set *IslAst::extractPreconditionFromAST(isl_ast_expr *Expr, isl_set *Cond) {
+  int NumArgs;
+  isl_set *OtherCondition;
+
+  switch (isl_ast_expr_get_type(Expr)) {
+  case isl_ast_expr_error:
+    llvm_unreachable("Code generation error");
+  case isl_ast_expr_op:
+    NumArgs = isl_ast_expr_get_op_n_arg(Expr);
+    for (int i = 0; i < NumArgs; i++)
+      Cond = extractPreconditionFromAST(isl_ast_expr_get_op_arg(Expr, i), Cond);
+    isl_ast_expr_free(Expr);
+    return Cond;
+  case isl_ast_expr_id:
+    isl_ast_expr_free(Expr);
+    return Cond;
+  case isl_ast_expr_int:
+    isl_ast_expr_free(Expr);
+    return Cond;
+  case isl_ast_expr_bound_t:
+    OtherCondition = isl_ast_expr_get_bound_condition(Expr);
+    if (OtherCondition) {
+      if (Cond)
+        Cond = isl_set_union(Cond, OtherCondition);
+      else
+        Cond = OtherCondition;
+    }
+
+    Cond = extractPreconditionFromAST(isl_ast_expr_get_bound_expr(Expr), Cond);
+
+    isl_ast_expr_free(Expr);
+    return Cond;
+  }
+}
+
 IslAst IslAst::create(Scop &Scop, const Dependences &D) {
   IslAst Ast{Scop};
   Ast.init(D);
   return Ast;
 }
 
 IslAst::IslAst(IslAst &&O)
     : S(O.S), Root(O.Root), RunCondition(O.RunCondition), Ctx(O.Ctx) {

lib/CodeGen/IslExprBuilder.cpp

 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/CodeGen/RuntimeDebugBuilder.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/ScopHelper.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 using namespace polly;
 
+static cl::opt<bool>
+    UseBounds("polly-ast-use-bounds",
+              cl::desc("Use computed bounds to determine types"),
+              cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::opt<bool>
+    ExtendBounds("polly-ast-extend-bounds",
+                 cl::desc("Extend types smaller than 64 bits to 64 bits"),
+                 cl::init(true), cl::Hidden, cl::Optional,
+                 cl::cat(PollyCategory));
+
 /// Different overflow tracking modes.
 enum OverflowTrackingChoice {
   OT_NEVER,   ///< Never tack potential overflows.
   OT_REQUEST, ///< Track potential overflows if requested.
   OT_ALWAYS   ///< Always track potential overflows.
 };
 
 static cl::opt<OverflowTrackingChoice> OTMode(
Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) {
 
   isl_id_free(Id);
   isl_ast_expr_free(Expr);
 
   return V;
 }
 
 IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) {
-  // XXX: We assume i64 is large enough. This is often true, but in general
-  //      incorrect. Also, on 32bit architectures, it would be beneficial to
-  //      use a smaller type. We can and should directly derive this information
-  //      during code generation.
+  if (isl_options_get_ast_build_compute_bounds(isl_ast_expr_get_ctx(Expr)) &&
+      UseBounds && !FixedSizeMode) {
+    if (CurrentBound == NULL) {
+      // Bail out with verbose error during dev:
+      llvm::errs() << "BEGIN EXPR\n";
+      isl_printer *p = isl_printer_to_file(isl_ast_expr_get_ctx(Expr), stderr);
+      p = isl_printer_set_output_format(p, ISL_FORMAT_C);
+      p = isl_printer_print_ast_expr(p, Expr);
+      isl_printer_free(p);
+      llvm::errs() << "\nEND EXPR\n";
+      llvm_unreachable("Unbound expression!");
+    }
+
+    int size = isl_ast_expr_get_bound_bits(CurrentBound);
+    if (isl_ast_expr_get_bound_signed(CurrentBound) != isl_bool_true)
+      size++;
+
+    // Extend to 64. After discussing this with Tobias, it might actually be
+    // more useful to only use the exact type for annotations and only use this
+    // for code generation on specific request. For now, there is a flag to
+    // toggle this behaviour.
+    if (size < 64 && ExtendBounds)
+      size = 64;
+
+    CurrentBound = nullptr;
+    return IntegerType::get(Builder.getContext(), size);
+  }
+  CurrentBound = nullptr;
   return IntegerType::get(Builder.getContext(), 64);
 }
 
 Value *IslExprBuilder::createInt(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_int &&
          "Expression not of type isl_ast_expr_int");
   isl_val *Val;
   Value *V;
Value *IslExprBuilder::create(__isl_take isl_ast_expr *Expr) {
   case isl_ast_expr_error:
     llvm_unreachable("Code generation error");
   case isl_ast_expr_op:
     return createOp(Expr);
   case isl_ast_expr_id:
     return createId(Expr);
   case isl_ast_expr_int:
     return createInt(Expr);
+  case isl_ast_expr_bound_t:
+    return createBound(Expr);
   }
 
   llvm_unreachable("Unexpected enum value");
 }
+
+Value *IslExprBuilder::createBound(__isl_take isl_ast_expr *Expr) {
+  Value *V;
+  assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_bound_t &&
+         "Expression not of type isl_ast_expr_bound_t");
+
+  isl_ast_expr *OldBound = CurrentBound;
+  CurrentBound = Expr;
+  V = create(isl_ast_expr_get_bound_expr(Expr));
+  isl_ast_expr_free(Expr);
+  CurrentBound = OldBound;
+  return V;
+}
+
+void IslExprBuilder::injectBound(__isl_keep isl_ast_expr *Bound) {
+  if (UseBounds) {
+    assert(!CurrentBound &&
+           "Cannot inject bound while previous bound is not consumed");
+
+    CurrentBound = Bound;
+  }
+}

lib/CodeGen/IslNodeBuilder.cpp

static cl::opt<int> PollyTargetFirstLevelCacheLineSize(
     "polly-target-first-level-cache-line-size",
     cl::desc("The size of the first level cache line size specified in bytes."),
     cl::Hidden, cl::init(64), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 __isl_give isl_ast_expr *
 IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
                               ICmpInst::Predicate &Predicate) {
   isl_id *UBID, *IteratorID;
-  isl_ast_expr *Cond, *Iterator, *UB, *Arg0;
+  isl_ast_expr *Cond, *Tmp, *Iterator, *UB, *Arg0;
   isl_ast_op_type Type;
 
   Cond = isl_ast_node_for_get_cond(For);
+  if (isl_ast_expr_get_type(Cond) == isl_ast_expr_bound_t) {
+    Tmp = Cond;
+    Cond = isl_ast_expr_get_bound_expr(Cond);
+    isl_ast_expr_free(Tmp);
+  }
   Iterator = isl_ast_node_for_get_iterator(For);
+  if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) {
+    Tmp = Iterator;
+    Iterator = isl_ast_expr_get_bound_expr(Iterator);
+    isl_ast_expr_free(Tmp);
+  }
+
   isl_ast_expr_get_type(Cond);
   assert(isl_ast_expr_get_type(Cond) == isl_ast_expr_op &&
          "conditional expression is not an atomic upper bound");
 
   Type = isl_ast_expr_get_op_type(Cond);
 
   switch (Type) {
   case isl_ast_op_le:
     Predicate = ICmpInst::ICMP_SLE;
     break;
   case isl_ast_op_lt:
     Predicate = ICmpInst::ICMP_SLT;
     break;
   default:
     llvm_unreachable("Unexpected comparison type in loop condition");
   }
 
   Arg0 = isl_ast_expr_get_op_arg(Cond, 0);
+  if (isl_ast_expr_get_type(Arg0) == isl_ast_expr_bound_t) {
+    Tmp = Arg0;
+    Arg0 = isl_ast_expr_get_bound_expr(Arg0);
+    isl_ast_expr_free(Tmp);
+  }
 
   assert(isl_ast_expr_get_type(Arg0) == isl_ast_expr_id &&
          "conditional expression is not an atomic upper bound");
 
   UBID = isl_ast_expr_get_id(Arg0);
 
   assert(isl_ast_expr_get_type(Iterator) == isl_ast_expr_id &&
          "Could not get the iterator");
IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
 
   return UB;
 }
 
 /// Return true if a return value of Predicate is true for the value represented
 /// by passed isl_ast_expr_int.
 static bool checkIslAstExprInt(__isl_take isl_ast_expr *Expr,
                                isl_bool (*Predicate)(__isl_keep isl_val *)) {
+  if (isl_ast_expr_get_type(Expr) == isl_ast_expr_bound_t) {
+    auto Tmp0 = Expr;
+    Expr = isl_ast_expr_get_bound_expr(Expr);
+    isl_ast_expr_free(Tmp0);
+  }
   if (isl_ast_expr_get_type(Expr) != isl_ast_expr_int) {
     isl_ast_expr_free(Expr);
     return false;
   }
   auto ExprVal = isl_ast_expr_get_val(Expr);
   isl_ast_expr_free(Expr);
   if (Predicate(ExprVal) != true) {
     isl_val_free(ExprVal);
int IslNodeBuilder::getNumberOfIterations(__isl_keep isl_ast_node *For) {
   auto Init = isl_ast_node_for_get_init(For);
   if (!checkIslAstExprInt(Init, isl_val_is_zero))
     return -1;
   auto Inc = isl_ast_node_for_get_inc(For);
   if (!checkIslAstExprInt(Inc, isl_val_is_one))
     return -1;
   CmpInst::Predicate Predicate;
   auto UB = getUpperBound(For, Predicate);
+  if (isl_ast_expr_get_type(UB) == isl_ast_expr_bound_t) {
+    auto Tmp0 = UB;
+    UB = isl_ast_expr_get_bound_expr(UB);
+    isl_ast_expr_free(Tmp0);
+  }
   if (isl_ast_expr_get_type(UB) != isl_ast_expr_int) {
     isl_ast_expr_free(UB);
     return -1;
   }
   auto UpVal = isl_ast_expr_get_val(UB);
   isl_ast_expr_free(UB);
   int NumberIterations = isl_val_get_num_si(UpVal);
   isl_val_free(UpVal);

 }
 
 void IslNodeBuilder::createForVector(__isl_take isl_ast_node *For,
                                      int VectorWidth) {
   isl_ast_node *Body = isl_ast_node_for_get_body(For);
   isl_ast_expr *Init = isl_ast_node_for_get_init(For);
   isl_ast_expr *Inc = isl_ast_node_for_get_inc(For);
   isl_ast_expr *Iterator = isl_ast_node_for_get_iterator(For);
-  isl_id *IteratorID = isl_ast_expr_get_id(Iterator);
+  isl_id *IteratorID;
+  if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) {
+    auto Content = isl_ast_expr_get_bound_expr(Iterator);
+    IteratorID = isl_ast_expr_get_id(Content);
+    isl_ast_expr_free(Content);
+  } else {
+    IteratorID = isl_ast_expr_get_id(Iterator);
+  }
 
   Value *ValueLB = ExprBuilder.create(Init);
   Value *ValueInc = ExprBuilder.create(Inc);
 
-  Type *MaxType = ExprBuilder.getType(Iterator);
+  Type *MaxType;
+  if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) {
+    ExprBuilder.injectBound(Iterator);
+    auto Content = isl_ast_expr_get_bound_expr(Iterator);
+    MaxType = ExprBuilder.getType(Content);
+    isl_ast_expr_free(Content);
+  } else {
+    MaxType = ExprBuilder.getType(Iterator);
+  }
   MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
   MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
 
   if (MaxType != ValueLB->getType())
     ValueLB = Builder.CreateSExt(ValueLB, MaxType);
   if (MaxType != ValueInc->getType())
     ValueInc = Builder.CreateSExt(ValueInc, MaxType);
 
void IslNodeBuilder::createForVector(__isl_take isl_ast_node *For,
 
   isl_ast_node_free(For);
   isl_ast_expr_free(Iterator);
 }
 
 void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For,
                                          bool KnownParallel) {
   isl_ast_node *Body;
-  isl_ast_expr *Init, *Inc, *Iterator, *UB;
+  isl_ast_expr *Init, *Inc, *Iterator, *IteratorContent, *UB;
   isl_id *IteratorID;
   Value *ValueLB, *ValueUB, *ValueInc;
   Type *MaxType;
   BasicBlock *ExitBlock;
   Value *IV;
   CmpInst::Predicate Predicate;
   bool Parallel;
 
   Parallel = KnownParallel || (IslAstInfo::isParallel(For) &&
                                !IslAstInfo::isReductionParallel(For));
 
   Body = isl_ast_node_for_get_body(For);
 
   // isl_ast_node_for_is_degenerate(For)
   //
   // TODO: For degenerated loops we could generate a plain assignment.
   //       However, for now we just reuse the logic for normal loops, which will
   //       create a loop with a single iteration.
 
   Init = isl_ast_node_for_get_init(For);
   Inc = isl_ast_node_for_get_inc(For);
   Iterator = isl_ast_node_for_get_iterator(For);
+
+  if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) {
+    IteratorContent = isl_ast_expr_get_bound_expr(Iterator);
+    IteratorID = isl_ast_expr_get_id(IteratorContent);
+    isl_ast_expr_free(IteratorContent);
+  } else {
     IteratorID = isl_ast_expr_get_id(Iterator);
+  }
   UB = getUpperBound(For, Predicate);
 
   ValueLB = ExprBuilder.create(Init);
   ValueUB = ExprBuilder.create(UB);
   ValueInc = ExprBuilder.create(Inc);
 
+  // When computing bounds, the iterator will be a subtree of the shape
+  //    ....
+  //     |
+  //  isl_ast_expr_bound_t
+  //     |
+  //  isl_ast_expr
+  // When codegenerating this tree, the visitor would store the bound before
+  // descending, but we're not using the visitor. If there are no bound nodes,
+  // we can simply use getType(Iterator), but if we compute bounds
+  // (polly-ast-compute-bounds is set), we have to do this differently...
+  if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) {
+    ExprBuilder.injectBound(Iterator);
+    IteratorContent = isl_ast_expr_get_bound_expr(Iterator);
+    MaxType = ExprBuilder.getType(IteratorContent);
+    isl_ast_expr_free(IteratorContent);
+  } else {
     MaxType = ExprBuilder.getType(Iterator);
+  }
   MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
   MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
   MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
 
   if (MaxType != ValueLB->getType())
     ValueLB = Builder.CreateSExt(ValueLB, MaxType);
   if (MaxType != ValueUB->getType())
     ValueUB = Builder.CreateSExt(ValueUB, MaxType);
for (po_iterator<DomTreeNode *> I = po_begin(N), E = po_end(N); I != E; ++I)
     Nodes.push_back(I->getBlock());
 
   for (BasicBlock *BB : Nodes)
     DT.eraseNode(BB);
 }
 
 void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
   isl_ast_node *Body;
-  isl_ast_expr *Init, *Inc, *Iterator, *UB;
+  isl_ast_expr *Init, *Inc, *Iterator, *UB, *IteratorContent;
   isl_id *IteratorID;
   Value *ValueLB, *ValueUB, *ValueInc;
   Type *MaxType;
   Value *IV;
   CmpInst::Predicate Predicate;
 
   // The preamble of parallel code interacts different than normal code with
   // e.g., scalar initialization. Therefore, we ensure the parallel code is
   // separated from the last basic block.
   BasicBlock *ParBB = SplitBlock(Builder.GetInsertBlock(),
                                  &*Builder.GetInsertPoint(), &DT, &LI);
   ParBB->setName("polly.parallel.for");
   Builder.SetInsertPoint(&ParBB->front());
 
   Body = isl_ast_node_for_get_body(For);
   Init = isl_ast_node_for_get_init(For);
   Inc = isl_ast_node_for_get_inc(For);
   Iterator = isl_ast_node_for_get_iterator(For);
+  if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) {
+    IteratorContent = isl_ast_expr_get_bound_expr(Iterator);
+    IteratorID = isl_ast_expr_get_id(IteratorContent);
+    isl_ast_expr_free(IteratorContent);
+  } else {
     IteratorID = isl_ast_expr_get_id(Iterator);
+  }
   UB = getUpperBound(For, Predicate);
 
   ValueLB = ExprBuilder.create(Init);
   ValueUB = ExprBuilder.create(UB);
   ValueInc = ExprBuilder.create(Inc);
 
   // OpenMP always uses SLE. In case the isl generated AST uses a SLT
   // expression, we need to adjust the loop bound by one.
   if (Predicate == CmpInst::ICMP_SLT)
     ValueUB = Builder.CreateAdd(
         ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType()));
 
+  // When computing bounds, the iterator will be a subtree of the shape
+  //    ....
+  //     |
+  //  isl_ast_expr_bound_t
+  //     |
+  //  isl_ast_expr
+  // When codegenerating this tree, the visitor would store the bound before
+  // descending, but we're not using the visitor. If there are no bound nodes,
+  // we can simply use getType(Iterator), but if we compute bounds
+  // (polly-ast-compute-bounds is set), we have to do this differently...
+  if (isl_ast_expr_get_type(Iterator) == isl_ast_expr_bound_t) {
+    ExprBuilder.injectBound(Iterator);
+    IteratorContent = isl_ast_expr_get_bound_expr(Iterator);
+    MaxType = ExprBuilder.getType(IteratorContent);
+    isl_ast_expr_free(IteratorContent);
+  } else {
     MaxType = ExprBuilder.getType(Iterator);
+  }
   MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
   MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
   MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
 
   if (MaxType != ValueLB->getType())
     ValueLB = Builder.CreateSExt(ValueLB, MaxType);
   if (MaxType != ValueUB->getType())
     ValueUB = Builder.CreateSExt(ValueUB, MaxType);
Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
   AccessRange = isl_set_gist_params(AccessRange, S.getContext());
 
   if (!materializeParameters(AccessRange)) {
     isl_set_free(AccessRange);
     isl_set_free(Domain);
     return nullptr;
   }
 
-  auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
+  isl_ast_build *Build = isl_ast_build_from_context(S.getContext());
+
   isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));
   bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);
   isl_set_free(Universe);
 
   Instruction *AccInst = MA.getAccessInstruction();
   Type *AccInstTy = AccInst->getType();
 
   Value *PreloadVal = nullptr;

 
 /// The AST expression we generate to perform the run-time check assumes
 /// computations on integer types of infinite size. As we only use 64-bit
 /// arithmetic we check for overflows, in case of which we set the result
 /// of this run-time check to false to be conservatively correct,
 Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {
   auto ExprBuilder = getExprBuilder();
   ExprBuilder.setTrackOverflow(true);
-  Value *RTC = ExprBuilder.create(Condition);
+  Value *RTC;
+  ExprBuilder.withFixedSizeMode([&]() {
+    RTC = ExprBuilder.create(Condition);
     if (!RTC->getType()->isIntegerTy(1))
       RTC = Builder.CreateIsNotNull(RTC);
-  Value *OverflowHappened =
-      Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");
+    Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(),
+                                                "polly.rtc.overflown");
 
     if (PollyGenerateRTCPrint) {
       auto *F = Builder.GetInsertBlock()->getParent();
       RuntimeDebugBuilder::createCPUPrinter(
           Builder,
           "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
               " __RTC: ",
           RTC, " Overflow: ", OverflowHappened, "\n");
     }
 
     RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");
+  });
   ExprBuilder.setTrackOverflow(false);
 
   if (!isa<ConstantInt>(RTC))
     VersionedScops++;
 
   return RTC;
 }

lib/CodeGen/LoopGenerators.cpp

Value *ParallelLoopGenerator::createParallelLoop(
   *LoopBody = Builder.GetInsertPoint();
   Builder.SetInsertPoint(&*BeforeLoop);
 
   Value *SubFnParam = Builder.CreateBitCast(Struct, Builder.getInt8PtrTy(),
                                             "polly.par.userContext");
 
   // Add one as the upper bound provided by OpenMP is a < comparison
   // whereas the codegenForSequential function creates a <= comparison.
-  UB = Builder.CreateAdd(UB, ConstantInt::get(LongType, 1));
+  UB = Builder.CreateAdd(UB, ConstantInt::get(UB->getType(), 1));
 
   // Tell the runtime we start a parallel loop
   createCallSpawnThreads(SubFn, SubFnParam, LB, UB, Stride);
   Builder.CreateCall(SubFn, SubFnParam);
   createCallJoinThreads();
 
   return IV;
 }

lib/CodeGen/PPCGCodeGeneration.cpp

if (!gpu_array_is_scalar(Array)) {
     isl_ast_expr *Res = isl_ast_build_expr_from_pw_aff(Build, OffsetDimZero);
 
     for (unsigned int i = 1; i < Array->n_index; i++) {
       isl_pw_aff *Bound_I = isl_multi_pw_aff_get_pw_aff(Array->bound, i);
       isl_ast_expr *Expr = isl_ast_build_expr_from_pw_aff(Build, Bound_I);
       Res = isl_ast_expr_mul(Res, Expr);
     }
 
-    Value *NumElements = ExprBuilder.create(Res);
+    Value *NumElements =
+        ExprBuilder.withFixedSizeMode([&]() { ExprBuilder.create(Res); });
     if (NumElements->getType() != ArraySize->getType())
       NumElements = Builder.CreateSExt(NumElements, ArraySize->getType());
     ArraySize = Builder.CreateMul(ArraySize, NumElements);
   }
   isl_ast_build_free(Build);
   return ArraySize;
 }
 
if (i > 0) {
       isl_ast_expr *BExpr = isl_ast_build_expr_from_pw_aff(Build, Bound_I);
       Result = isl_ast_expr_mul(Result, BExpr);
     }
     isl_pw_aff *DimMin = isl_set_dim_min(isl_set_copy(Min), i);
     isl_ast_expr *MExpr = isl_ast_build_expr_from_pw_aff(Build, DimMin);
     Result = isl_ast_expr_add(Result, MExpr);
   }
 
-  Value *ResultValue = ExprBuilder.create(Result);
+  Value *ResultValue =
+      ExprBuilder.withFixedSizeMode([&]() { ExprBuilder.create(Result); });
+
   isl_set_free(Min);
   isl_ast_build_free(Build);
 
   return ResultValue;
 }
 
 Value *GPUNodeBuilder::getOrCreateManagedDeviceArray(gpu_array_info *Array,
                                                      ScopArrayInfo *ArrayInfo) {
void GPUNodeBuilder::createUser(__isl_take isl_ast_node *UserStmt) {
 
   isl_ast_expr_free(Expr);
   isl_ast_node_free(UserStmt);
   return;
 }
 void GPUNodeBuilder::createKernelCopy(ppcg_kernel_stmt *KernelStmt) {
   isl_ast_expr *LocalIndex = isl_ast_expr_copy(KernelStmt->u.c.local_index);
   LocalIndex = isl_ast_expr_address_of(LocalIndex);
-  Value *LocalAddr = ExprBuilder.create(LocalIndex);
+
+  Value *GlobalAddr, *LocalAddr;
+  ExprBuilder.withFixedSizeMode([&]() {
+    LocalAddr = ExprBuilder.create(LocalIndex);
     isl_ast_expr *Index = isl_ast_expr_copy(KernelStmt->u.c.index);
     Index = isl_ast_expr_address_of(Index);
-  Value *GlobalAddr = ExprBuilder.create(Index);
+    GlobalAddr = ExprBuilder.create(Index);
+  });
 
   if (KernelStmt->u.c.read) {
     LoadInst *Load = Builder.CreateLoad(GlobalAddr, "shared.read");
     Builder.CreateStore(Load, LocalAddr);
   } else {
     LoadInst *Load = Builder.CreateLoad(LocalAddr, "shared.write");
     Builder.CreateStore(Load, GlobalAddr);
   }
void generateCode(__isl_take isl_ast_node *Root, gpu_prog *Prog) {
     GPUNodeBuilder NodeBuilder(Builder, Annotator, *DL, *LI, *SE, *DT, *S,
                                StartBlock, Prog, Runtime, Architecture);
 
     // TODO: Handle LICM
     auto SplitBlock = StartBlock->getSinglePredecessor();
     Builder.SetInsertPoint(SplitBlock->getTerminator());
     NodeBuilder.addParameters(S->getContext());
 
-    isl_ast_build *Build = isl_ast_build_alloc(S->getIslCtx());
+    isl_ast_build *Build = isl_ast_build_from_context(S->getContext());
     isl_ast_expr *Condition = IslAst::buildRunCondition(*S, Build);
     isl_ast_expr *SufficientCompute = createSufficientComputeCheck(*S, Build);
     Condition = isl_ast_expr_and(Condition, SufficientCompute);
     isl_ast_build_free(Build);
 
     // preload invariant loads. Note: This should happen before the RTC
     // because the RTC may depend on values that are invariant load hoisted.
     NodeBuilder.preloadInvariantLoads();

lib/External/isl/codegen.c

  * - a schedule map
  * - a context
  * - a relation describing AST generation options
  */
 
 #include <assert.h>
 #include <stdlib.h>
 #include <isl/ast.h>
+#include <isl/aff.h>
 #include <isl/ast_build.h>
 #include <isl/options.h>
-#include <isl/set.h>
 #include <isl/union_set.h>
-#include <isl/union_map.h>
 #include <isl/stream.h>
 #include <isl/schedule_node.h>
+#include <string.h>
+#include "isl_ast_private.h"
+#include "isl_ast_build_private.h"
+#include "isl_union_map_private.h"
+#include "isl_aff_private.h"
+#include "isl_space_private.h"
+#include "isl_options_private.h"
 
 struct options {
   struct isl_options  *isl;
   unsigned     atomic;
   unsigned     separate;
+  char*      infile;
 };
 
 ISL_ARGS_START(struct options, options_args)
 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
 ISL_ARG_BOOL(struct options, atomic, 0, "atomic", 0,
   "globally set the atomic option")
 ISL_ARG_BOOL(struct options, separate, 0, "separate", 0,
   "globally set the separate option")
+ISL_ARG_STR(struct options, infile, 0, "infile", "file", "-", "File to read instead of stdin or - for stdin")
 ISL_ARGS_END
 
 ISL_ARG_DEF(cg_options, struct options, options_args)
 ISL_ARG_CTX_DEF(cg_options, struct options, options_args)
 
 /* Return a universal, 1-dimensional set with the given name.
  */
 static __isl_give isl_union_set *universe(isl_ctx *ctx, const char *name)
static __isl_give isl_ast_build *set_options(__isl_take isl_ast_build *build,
   if (options->atomic)
     opt = set_universe(opt, schedule, "atomic");
 
   build = isl_ast_build_set_options(build, opt);
 
   return build;
 }
 
+struct ast_from_union_ret {
+  isl_ast_node* tree;
+  isl_ast_expr* expr;
+};
 /* Construct an AST in case the schedule is specified by a union map.
  *
  * We read the context and the options from "s" and construct the AST.
  */
-static __isl_give isl_ast_node *construct_ast_from_union_map(
+static __isl_give struct ast_from_union_ret *construct_ast_from_union_map(
   __isl_take isl_union_map *schedule, __isl_keep isl_stream *s)
 {
   isl_set *context;
   isl_union_map *options_map;
-  isl_ast_build *build;
+  isl_ast_build *build, *aff_build;
   isl_ast_node *tree;
   struct options *options;
-
+  struct isl_obj obj;
+  isl_ast_expr *expr = NULL;
+  struct ast_from_union_ret *retval;
   options = isl_ctx_peek_cg_options(isl_stream_get_ctx(s));
 
   context = isl_stream_read_set(s);
   options_map = isl_stream_read_union_map(s);
 
   build = isl_ast_build_from_context(context);
   build = set_options(build, options_map, options, schedule);
   tree = isl_ast_build_node_from_schedule_map(build, schedule);
+  isl_pw_aff *aff = isl_stream_read_pw_aff(s);
+  if (aff) {
+    aff_build = isl_ast_build_copy(build);
+    aff_build = isl_ast_build_set_single_valued(aff_build, 0);
+    aff_build = isl_ast_build_init_options(aff_build);
+    expr = isl_ast_build_expr_from_pw_aff(aff_build, aff);
+    isl_ast_build_free(aff_build);
+  }
+
   isl_ast_build_free(build);
 
-  return tree;
+  retval = malloc(sizeof(struct ast_from_union_ret));
+  if (expr)
+    retval->expr = expr;
+  else
+    retval->expr = NULL;
+  retval->tree = tree;
+  return retval;
 }
 
 /* If "node" is a band node, then replace the AST build options
  * by "options".
  */
 static __isl_give isl_schedule_node *node_set_options(
   __isl_take isl_schedule_node *node, void *user)
 {

  * schedule map, context and options and construct an AST from
  * those elements
  * If it is a schedule object, then construct the AST from the schedule.
  */
 int main(int argc, char **argv)
 {
   isl_ctx *ctx;
   isl_stream *s;
+  struct ast_from_union_ret *retval = NULL;
   isl_ast_node *tree = NULL;
   struct options *options;
   isl_printer *p;
   struct isl_obj obj;
   int r = EXIT_SUCCESS;
+  FILE *fd;
+  isl_ast_expr *expr = NULL;
 
   options = cg_options_new_with_defaults();
   assert(options);
   ctx = isl_ctx_alloc_with_options(&options_args, options);
   isl_options_set_ast_build_detect_min_max(ctx, 1);
   argc = cg_options_parse(options, argc, argv, ISL_ARG_ALL);
 
-  s = isl_stream_new_file(ctx, stdin);
+  if (strcmp(options->infile, "-") != 0) {
+    fd = fopen(options->infile, "r");
+    if (!fd) {
+      isl_die(ctx, isl_error_invalid, "Couldn't open file",
+          r = EXIT_FAILURE);
+      return r;
+    }
+  } else {
+    fd = stdin;
+  }
+
+  s = isl_stream_new_file(ctx, fd);
   obj = isl_stream_read_obj(s);
+
   if (obj.v == NULL) {
     r = EXIT_FAILURE;
   } else if (obj.type == isl_obj_map) {
     isl_union_map *umap;
 
     umap = isl_union_map_from_map(obj.v);
-    tree = construct_ast_from_union_map(umap, s);
+    retval = construct_ast_from_union_map(umap, s);
+    tree = retval->tree;
+    expr = retval->expr;
+    free(retval);
   } else if (obj.type == isl_obj_union_map) {
-    tree = construct_ast_from_union_map(obj.v, s);
+    retval = construct_ast_from_union_map(obj.v, s);
+    tree = retval->tree;
+    expr = retval->expr;
+    free(retval);
   } else if (obj.type == isl_obj_schedule) {
     tree = construct_ast_from_schedule(obj.v);
   } else {
     obj.type->free(obj.v);
     isl_die(ctx, isl_error_invalid, "unknown input",
       r = EXIT_FAILURE);
   }
+  p = isl_printer_to_file(ctx, stdout);
   isl_stream_free(s);
 
-  p = isl_printer_to_file(ctx, stdout);
+//if (isl_options_get_ast_build_print_computed_bounds(ctx)) {
+    p = isl_printer_set_output_format(p, ISL_FORMAT_C);
+/*    p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_BLOCK);*/
+/*  } else {
     p = isl_printer_set_output_format(p, ISL_FORMAT_C);
+  }*/
   p = isl_printer_print_ast_node(p, tree);
+  if (expr) {
+    p = isl_printer_print_ast_expr(p, expr);
+    isl_ast_expr_free(expr);
+  }
+
   isl_printer_free(p);
 
   isl_ast_node_free(tree);
 
   isl_ctx_free(ctx);
+  if (fd != stdin)
+    fclose(fd);
   return r;
 }

lib/External/isl/include/isl/ast.h

 #endif
 
 isl_stat isl_options_set_ast_iterator_type(isl_ctx *ctx, const char *val);
 const char *isl_options_get_ast_iterator_type(isl_ctx *ctx);
 
 isl_stat isl_options_set_ast_always_print_block(isl_ctx *ctx, int val);
 int isl_options_get_ast_always_print_block(isl_ctx *ctx);
 
+isl_stat isl_options_set_ast_build_print_computed_bounds(isl_ctx *ctx, int val);
+int isl_options_get_ast_build_print_computed_bounds(isl_ctx *ctx);
+
 __isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v);
 __isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id);
 __isl_give isl_ast_expr *isl_ast_expr_neg(__isl_take isl_ast_expr *expr);
 __isl_give isl_ast_expr *isl_ast_expr_add(__isl_take isl_ast_expr *expr1,
   __isl_take isl_ast_expr *expr2);
 __isl_give isl_ast_expr *isl_ast_expr_sub(__isl_take isl_ast_expr *expr1,
   __isl_take isl_ast_expr *expr2);
 __isl_give isl_ast_expr *isl_ast_expr_mul(__isl_take isl_ast_expr *expr1,
__isl_give isl_ast_expr *isl_ast_expr_gt(__isl_take isl_ast_expr *expr1,
   __isl_take isl_ast_expr *expr2);
 __isl_give isl_ast_expr *isl_ast_expr_eq(__isl_take isl_ast_expr *expr1,
   __isl_take isl_ast_expr *expr2);
 __isl_give isl_ast_expr *isl_ast_expr_access(__isl_take isl_ast_expr *array,
   __isl_take isl_ast_expr_list *indices);
 __isl_give isl_ast_expr *isl_ast_expr_call(__isl_take isl_ast_expr *function,
   __isl_take isl_ast_expr_list *arguments);
 __isl_give isl_ast_expr *isl_ast_expr_address_of(__isl_take isl_ast_expr *expr);
+__isl_give isl_ast_expr *isl_ast_expr_bound(__isl_take isl_ast_expr *expr,
+   isl_bool is_signed, unsigned int size, __isl_take isl_set *conditions);
 
 __isl_give isl_ast_expr *isl_ast_expr_copy(__isl_keep isl_ast_expr *expr);
 __isl_null isl_ast_expr *isl_ast_expr_free(__isl_take isl_ast_expr *expr);
 
 isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr);
 enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr);
 __isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr);
 __isl_give isl_id *isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr);
 
+unsigned int isl_ast_expr_get_bound_bits(__isl_keep isl_ast_expr *expr);
+isl_bool isl_ast_expr_get_bound_signed(__isl_keep isl_ast_expr *expr);
+__isl_give isl_ast_expr* isl_ast_expr_get_bound_expr (__isl_keep isl_ast_expr *expr);
+__isl_give isl_set* isl_ast_expr_get_bound_condition (__isl_keep isl_ast_expr *expr);
+
 enum isl_ast_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr);
 int isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr);
 __isl_give isl_ast_expr *isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr,
   int pos);
 __isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr,
   int pos, __isl_take isl_ast_expr *arg);
 
 isl_bool isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1,

lib/External/isl/include/isl/ast_build.h

 
 
 isl_stat isl_options_set_ast_build_atomic_upper_bound(isl_ctx *ctx, int val);
 int isl_options_get_ast_build_atomic_upper_bound(isl_ctx *ctx);
 
 isl_stat isl_options_set_ast_build_prefer_pdiv(isl_ctx *ctx, int val);
 int isl_options_get_ast_build_prefer_pdiv(isl_ctx *ctx);
 
+isl_stat isl_options_set_ast_build_compute_bounds(isl_ctx *ctx, int val);
+int isl_options_get_ast_build_compute_bounds(isl_ctx *ctx);
+isl_stat isl_options_set_ast_build_approximate_computed_bounds(isl_ctx *ctx, int val);
+int isl_options_get_ast_build_approximate_computed_bounds(isl_ctx *ctx);
+isl_stat isl_options_set_ast_build_maximum_native_type(isl_ctx *ctx, int val);
+int isl_options_get_ast_build_maximum_native_type(isl_ctx *ctx);
 isl_stat isl_options_set_ast_build_detect_min_max(isl_ctx *ctx, int val);
 int isl_options_get_ast_build_detect_min_max(isl_ctx *ctx);
 
 isl_stat isl_options_set_ast_build_exploit_nested_bounds(isl_ctx *ctx, int val);
 int isl_options_get_ast_build_exploit_nested_bounds(isl_ctx *ctx);
 
 isl_stat isl_options_set_ast_build_group_coscheduled(isl_ctx *ctx, int val);
 int isl_options_get_ast_build_group_coscheduled(isl_ctx *ctx);

 __isl_give isl_ast_node *isl_ast_build_node_from_schedule(
   __isl_keep isl_ast_build *build, __isl_take isl_schedule *schedule);
 __isl_export
 __isl_give isl_ast_node *isl_ast_build_node_from_schedule_map(
   __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule);
 __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
   __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule);
 
+__isl_give isl_ast_expr *isl_ast_bin_op_set_size(__isl_take isl_ast_expr *expr,
+  __isl_keep isl_ast_build *build);
+
 #if defined(__cplusplus)
 }
 #endif
 
 #endif

lib/External/isl/include/isl/ast_type.h

enum isl_ast_op_type {
   isl_ast_op_member,
   isl_ast_op_address_of
 };
 
 enum isl_ast_expr_type {
   isl_ast_expr_error = -1,
   isl_ast_expr_op,
   isl_ast_expr_id,
-  isl_ast_expr_int
+  isl_ast_expr_int,
+  isl_ast_expr_bound_t
 };
 
 enum isl_ast_node_type {
   isl_ast_node_error = -1,
   isl_ast_node_for = 1,
   isl_ast_node_if,
   isl_ast_node_block,
   isl_ast_node_mark,

lib/External/isl/include/isl/stream.h

 __isl_give isl_multi_aff *isl_stream_read_multi_aff(__isl_keep isl_stream *s);
 __isl_give isl_map *isl_stream_read_map(__isl_keep isl_stream *s);
 __isl_give isl_set *isl_stream_read_set(__isl_keep isl_stream *s);
 __isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
   __isl_keep isl_stream *s);
 __isl_give isl_union_set *isl_stream_read_union_set(__isl_keep isl_stream *s);
 __isl_give isl_union_map *isl_stream_read_union_map(__isl_keep isl_stream *s);
 __isl_give isl_schedule *isl_stream_read_schedule(isl_stream *s);
+__isl_give isl_pw_aff *isl_stream_read_pw_aff(__isl_keep isl_stream *s);
 
 int isl_stream_yaml_read_start_mapping(__isl_keep isl_stream *s);
 int isl_stream_yaml_read_end_mapping(__isl_keep isl_stream *s);
 int isl_stream_yaml_read_start_sequence(__isl_keep isl_stream *s);
 int isl_stream_yaml_read_end_sequence(__isl_keep isl_stream *s);
 int isl_stream_yaml_next(__isl_keep isl_stream *s);
 
 #if defined(__cplusplus)
 }
 #endif
 
 #endif

lib/External/isl/include/isl/val.h

 
 __isl_give isl_multi_val *isl_multi_val_read_from_str(isl_ctx *ctx,
   const char *str);
 __isl_give isl_printer *isl_printer_print_multi_val(__isl_take isl_printer *p,
   __isl_keep isl_multi_val *mv);
 void isl_multi_val_dump(__isl_keep isl_multi_val *mv);
 __isl_give char *isl_multi_val_to_str(__isl_keep isl_multi_val *mv);
 
+int isl_val_size_in_bits(__isl_keep isl_val *v, int is_signed);
+
 #if defined(__cplusplus)
 }
 #endif
 
 #endif

lib/External/isl/isl_ast.c

 /*
  * Copyright 2012-2013 Ecole Normale Superieure
  *
  * Use of this software is governed by the MIT license
  *
  * Written by Sven Verdoolaege,
  * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  */
 
 #include <string.h>
 
 #include <isl_ast_private.h>
+#include <include/isl/ast_build.h>
 
 #undef BASE
 #define BASE ast_expr
 
 #include <isl_list_templ.c>
 
 #undef BASE
 #define BASE ast_node
 
 #include <isl_list_templ.c>
+#include "isl_ast_private.h"
 
 isl_ctx *isl_ast_print_options_get_ctx(
   __isl_keep isl_ast_print_options *options)
 {
   return options ? options->ctx : NULL;
 }
 
 __isl_give isl_ast_print_options *isl_ast_print_options_alloc(isl_ctx *ctx)
case isl_ast_expr_op:
     dup = isl_ast_expr_alloc_op(ctx,
               expr->u.op.op, expr->u.op.n_arg);
     if (!dup)
       return NULL;
     for (i = 0; i < expr->u.op.n_arg; ++i)
       dup->u.op.args[i] =
         isl_ast_expr_copy(expr->u.op.args[i]);
     break;
+  case isl_ast_expr_bound_t:
+    dup = isl_ast_expr_bound(isl_ast_expr_copy(expr->u.bound.expr),
+      expr->u.bound.is_signed, expr->u.bound.size,
+      expr->u.bound.condition);
   case isl_ast_expr_error:
     dup = NULL;
   }
 
   if (!dup)
     return NULL;
 
   return dup;
case isl_ast_expr_id:
     isl_id_free(expr->u.id);
     break;
   case isl_ast_expr_op:
     if (expr->u.op.args)
       for (i = 0; i < expr->u.op.n_arg; ++i)
         isl_ast_expr_free(expr->u.op.args[i]);
     free(expr->u.op.args);
     break;
+  case isl_ast_expr_bound_t:
+    isl_ast_expr_free(expr->u.bound.expr);
+    isl_set_free(expr->u.bound.condition);
+    break;
   case isl_ast_expr_error:
     break;
   }
 
   free(expr);
   return NULL;
 }
 
 isl_ctx *isl_ast_expr_get_ctx(__isl_keep isl_ast_expr *expr)
 {
   return expr ? expr->ctx : NULL;
 }
 
 enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
 {
   return expr ? expr->type : isl_ast_expr_error;
 }
 
+/* Return the number of bits required to represent 'expr' in two's complement
+ */
+unsigned int isl_ast_expr_get_bound_bits(__isl_keep isl_ast_expr *expr)
+{
+  if (!expr)
+    return isl_ast_op_error;
+  if (expr->type != isl_ast_expr_bound_t)
+    isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
+        "expression not a bound", return isl_ast_op_error);
+  return expr->u.bound.size;
+}
+
+/* Return whether the value of 'expr' at runtime can be signed.
+ */
+isl_bool isl_ast_expr_get_bound_signed(__isl_keep isl_ast_expr *expr)
+{
+  if (!expr)
+    return isl_bool_error;
+  if (expr->type != isl_ast_expr_bound_t)
+    isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
+        "expression not a bound", return isl_ast_op_error);
+  return expr->u.bound.is_signed;
+}
+
+/* Return the expression contained within the bounds of "expr".
+ */
+__isl_give isl_ast_expr* isl_ast_expr_get_bound_expr (__isl_keep isl_ast_expr *expr)
+{
+
+  if (!expr)
+    return NULL;
+  if (expr->type != isl_ast_expr_bound_t)
+    isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
+        "expression not an int", return NULL);
+  return isl_ast_expr_copy(expr->u.bound.expr);
+}
+
+/* Return the condition under which the bound "expr" is valid.
+ */
+__isl_give isl_set* isl_ast_expr_get_bound_condition (__isl_keep isl_ast_expr *expr)
+{
+
+  if (!expr)
+    return NULL;
+  if (expr->type != isl_ast_expr_bound_t)
+    isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
+        "expression not an int", return NULL);
+  return isl_set_copy(expr->u.bound.condition);
+}
+
 /* Return the integer value represented by "expr".
  */
 __isl_give isl_val *isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr)
 {
   if (!expr)
     return NULL;
   if (expr->type != isl_ast_expr_int)
     isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
error:
   return NULL;
 }
 
 /* Create a new integer expression representing "i".
  */
 __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i)
 {
   isl_ast_expr *expr;
+  isl_bool is_neg;
+  int size;
 
   expr = isl_calloc_type(ctx, isl_ast_expr);
   if (!expr)
     return NULL;
 
   expr->ctx = ctx;
   isl_ctx_ref(ctx);
   expr->ref = 1;
   expr->type = isl_ast_expr_int;
   expr->u.v = isl_val_int_from_si(ctx, i);
   if (!expr->u.v)
     return isl_ast_expr_free(expr);
 
+  if (isl_options_get_ast_build_compute_bounds(ctx)) {
+    is_neg = isl_val_is_neg(expr->u.v);
+    size = isl_val_size_in_bits(expr->u.v, is_neg);
+    expr = isl_ast_expr_bound(expr, is_neg, size, NULL);
+  }
+
   return expr;
 }
 
 /* Create a new integer expression representing "v".
  */
 __isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v)
 {
   isl_ctx *ctx;
   isl_ast_expr *expr;
+  isl_bool is_neg;
+  int size;
 
   if (!v)
     return NULL;
   if (!isl_val_is_int(v))
     isl_die(isl_val_get_ctx(v), isl_error_invalid,
       "expecting integer value", goto error);
 
   ctx = isl_val_get_ctx(v);
   expr = isl_calloc_type(ctx, isl_ast_expr);
   if (!expr)
     goto error;
 
   expr->ctx = ctx;
   isl_ctx_ref(ctx);
   expr->ref = 1;
   expr->type = isl_ast_expr_int;
   expr->u.v = v;
 
+  if (isl_options_get_ast_build_compute_bounds(isl_val_get_ctx(v))) {
+    is_neg = isl_val_is_neg(expr->u.v);
+    size = isl_val_size_in_bits(expr->u.v, is_neg);
+    expr = isl_ast_expr_bound(expr, is_neg, size, NULL);
+  }
+
   return expr;
 error:
   isl_val_free(v);
   return NULL;
 }
 
 /* Create an expression representing the unary operation "type" applied to
  * "arg".
if (isl_ast_expr_get_type(expr) != isl_ast_expr_op ||
       isl_ast_expr_get_op_type(expr) != isl_ast_op_access)
     isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
       "can only take address of access expressions",
       return isl_ast_expr_free(expr));
 
   return isl_ast_expr_alloc_unary(isl_ast_op_address_of, expr);
 }
 
+/* Create an expression representing the bounds on "expr".
+ *
+ */
+__isl_give isl_ast_expr *isl_ast_expr_bound(__isl_take isl_ast_expr *expr,
+  isl_bool is_signed, unsigned int size, __isl_take isl_set *conditions)
+{
+  isl_ctx *ctx;
+  isl_ast_expr *result;
+
+  if (!expr)
+    return NULL;
+
+  if (expr->type == isl_ast_expr_bound_t) {
+    isl_die(isl_ast_expr_get_ctx(expr), isl_error_internal,
+      "Cannot take bound of bound",
+      return isl_ast_expr_free(expr));
+  }
+
+  ctx = isl_ast_expr_get_ctx(expr);
+  result = isl_calloc_type(ctx, isl_ast_expr);
+  if (!result) {
+    isl_ast_expr_free(result);
+    return NULL;
+  }
+  result->type = isl_ast_expr_bound_t;
+
+  result->ctx = ctx;
+  isl_ctx_ref(ctx);
+  result->ref = 1;
+  result->u.bound.expr = expr;
+  result->u.bound.is_signed = is_signed;
+  result->u.bound.size = size;
+  result->u.bound.condition = conditions;
+
+  return result;
+}
+
 /* Create an expression representing the binary operation "type"
  * applied to "expr1" and "expr2".
  */
 __isl_give isl_ast_expr *isl_ast_expr_alloc_binary(enum isl_ast_op_type type,
   __isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2)
 {
   isl_ctx *ctx;
   isl_ast_expr *expr = NULL;
if (op == isl_ast_op_mul && expr->u.op.op != isl_ast_op_mul &&
       op_prec[expr->u.op.op] == op_prec[op])
     return 1;
   if (is_add_sub(op) && is_div_mod(expr->u.op.op))
     return 1;
 
   return 0;
 }
 
+/* Print a c-style cast operator containing the integer type of expr
+ */
+__isl_give isl_printer *printer_print_cast(__isl_take isl_printer *p,
+  __isl_keep isl_ast_expr *expr)
+{
+  if (isl_ast_expr_get_type(expr) != isl_ast_expr_bound_t)
+    return p;
+
+  if (!isl_options_get_ast_build_print_computed_bounds(
+        isl_printer_get_ctx(p)))
+    return p;
+
+  p = isl_printer_print_str(p, "(");
+  if (!isl_ast_expr_get_bound_signed(expr))
+    p = isl_printer_print_str(p, "u");
+
+  p = isl_printer_print_str(p, "int");
+  p = isl_printer_print_int(p, isl_ast_expr_get_bound_bits(expr));
+  p = isl_printer_print_str(p, ")");
+
+  return p;
+}
+
 /* Print "expr" as a subexpression of an "op" operation in C format.
  * If "left" is set, then "expr" is the left-most operand.
  */
 static __isl_give isl_printer *print_sub_expr_c(__isl_take isl_printer *p,
-  enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
+  enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left,
+  __isl_keep isl_ast_expr *parent)
 {
   int need_parens;
 
   need_parens = sub_expr_need_parens(op, expr, left);
 
+  if (isl_ast_expr_get_type(expr) == isl_ast_expr_bound_t) {
+    p = printer_print_cast(p, expr);
+    expr = expr->u.bound.expr;
+    if (isl_options_get_ast_build_print_computed_bounds(
+          isl_printer_get_ctx(p)))
+      need_parens = 1;
+    else
+            need_parens = sub_expr_need_parens(op, expr, left);
+
+  }
+
   if (need_parens)
     p = isl_printer_print_str(p, "(");
   p = print_ast_expr_c(p, expr);
   if (need_parens)
     p = isl_printer_print_str(p, ")");
   return p;
 }
 
case isl_ast_expr_op:
     }
     if (expr->u.op.op == isl_ast_op_access) {
       p = print_access_c(p, expr);
       break;
     }
     if (expr->u.op.n_arg == 1) {
       p = isl_printer_print_str(p,
             get_op_str_c(p, expr->u.op.op));
+      p = printer_print_cast(p, expr);
       p = print_sub_expr_c(p, expr->u.op.op,
-            expr->u.op.args[0], 0);
+            expr->u.op.args[0], 0, expr);
       break;
     }
     if (expr->u.op.op == isl_ast_op_fdiv_q) {
       const char *name = get_op_str_c(p, isl_ast_op_fdiv_q);
       p = isl_printer_print_str(p, name);
       p = isl_printer_print_str(p, "(");
       p = print_ast_expr_c(p, expr->u.op.args[0]);
       p = isl_printer_print_str(p, ", ");
if (expr->u.op.op == isl_ast_op_cond ||
       p = isl_printer_print_str(p, " : ");
       p = print_ast_expr_c(p, expr->u.op.args[2]);
       break;
     }
     if (expr->u.op.n_arg != 2)
       isl_die(isl_printer_get_ctx(p), isl_error_internal,
         "operation should have two arguments",
         return isl_printer_free(p));
-    p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[0], 1);
+    p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[0], 1,
+             expr);
     if (expr->u.op.op != isl_ast_op_member)
       p = isl_printer_print_str(p, " ");
     p = isl_printer_print_str(p, get_op_str_c(p, expr->u.op.op));
     if (expr->u.op.op != isl_ast_op_member)
       p = isl_printer_print_str(p, " ");
-    p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[1], 0);
+    p = print_sub_expr_c(p, expr->u.op.op, expr->u.op.args[1], 0,
+             expr);
     break;
   case isl_ast_expr_id:
     p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
     break;
   case isl_ast_expr_int:
     p = isl_printer_print_val(p, expr->u.v);
     break;
+  case isl_ast_expr_bound_t:
+    if (!isl_options_get_ast_build_print_computed_bounds(
+          isl_printer_get_ctx(p)))
+      p = print_ast_expr_c(p, expr->u.bound.expr);
+    else {
+      p = printer_print_cast(p, expr);
+      p = isl_printer_print_str(p, "(");
+      p = print_ast_expr_c(p, expr->u.bound.expr);
+      p = isl_printer_print_str(p, ")");
+    }
+    break;
   case isl_ast_expr_error:
     break;
   }
 
   return p;
 }
 
 /* Textual representation of the isl_ast_op_type elements
for (i = 0; i < n; ++i) {
     isl_ast_expr_free(arg);
     p = isl_printer_yaml_next(p);
   }
   p = isl_printer_yaml_end_sequence(p);
 
   return p;
 }
 
+isl_printer *print_ast_expr_size_isl(__isl_take isl_printer *p,
+   __isl_keep isl_ast_expr *expr) {
+  if (isl_ast_expr_get_type(expr) == isl_ast_expr_bound_t) {
+    p = isl_printer_yaml_next(p);
+    p = isl_printer_print_str(p, "size");
+    p = isl_printer_yaml_next(p);
+    p = isl_printer_print_int(p, expr->u.bound.size);
+    p = isl_printer_yaml_next(p);
+    p = isl_printer_print_str(p, "is_signed");
+    p = isl_printer_yaml_next(p);
+    p = isl_printer_print_int(p, expr->u.bound.is_signed);
+    if (expr->u.bound.condition) {
+      p = isl_printer_yaml_next(p);
+      p = isl_printer_print_str(p, "condition");
+      p = isl_printer_yaml_next(p);
+      isl_printer_print_set(p, expr->u.bound.condition);
+    }
+  }
+  return p;
+}
+
 /* Print "expr" to "p" in isl format.
  *
  * In particular, print the isl_ast_expr as a YAML document.
  */
 static __isl_give isl_printer *print_ast_expr_isl(__isl_take isl_printer *p,
   __isl_keep isl_ast_expr *expr)
 {
   enum isl_ast_expr_type type;
case isl_ast_expr_error:
     return isl_printer_free(p);
   case isl_ast_expr_op:
     op = isl_ast_expr_get_op_type(expr);
     if (op == isl_ast_op_error)
       return isl_printer_free(p);
     p = isl_printer_print_str(p, "op");
     p = isl_printer_yaml_next(p);
     p = isl_printer_print_str(p, op_str[op]);
+    p = print_ast_expr_size_isl(p, expr);
     p = isl_printer_yaml_next(p);
     p = print_arguments(p, expr);
     break;
   case isl_ast_expr_id:
     p = isl_printer_print_str(p, "id");
     p = isl_printer_yaml_next(p);
     id = isl_ast_expr_get_id(expr);
     p = isl_printer_print_id(p, id);
     isl_id_free(id);
+    p = print_ast_expr_size_isl(p, expr);
     break;
   case isl_ast_expr_int:
     p = isl_printer_print_str(p, "val");
     p = isl_printer_yaml_next(p);
     v = isl_ast_expr_get_val(expr);
     p = isl_printer_print_val(p, v);
+    p = print_ast_expr_size_isl(p, expr);
     isl_val_free(v);
     break;
+  case isl_ast_expr_bound_t:
+    if (!isl_options_get_ast_build_print_computed_bounds(
+          isl_printer_get_ctx(p)))
+      p = print_ast_expr_size_isl(p, expr);
+    p = print_ast_expr_isl(p, expr->u.bound.expr);
   }
   p = isl_printer_yaml_end_mapping(p);
 
   return p;
 }
 
 /* Print "expr" to "p".
  *
static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
   __isl_keep isl_ast_node *node,
   __isl_keep isl_ast_print_options *options, int in_block, int in_list)
 {
   isl_id *id;
   const char *name;
   const char *type;
 
   type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
+
   if (!node->u.f.degenerate) {
+    if (node->u.f.iterator->type == isl_ast_expr_bound_t) {
+      id = isl_ast_expr_get_id(node->u.f.iterator->
+          u.bound.expr);
+    } else {
       id = isl_ast_expr_get_id(node->u.f.iterator);
+    }
     name = isl_id_get_name(id);
     isl_id_free(id);
     p = isl_printer_start_line(p);
     p = isl_printer_print_str(p, "for (");
     p = isl_printer_print_str(p, type);
     p = isl_printer_print_str(p, " ");
     p = isl_printer_print_str(p, name);
     p = isl_printer_print_str(p, " = ");

lib/External/isl/isl_ast_build.c

 #include <isl/aff.h>
 #include <isl/constraint.h>
 #include <isl/map.h>
 #include <isl/union_set.h>
 #include <isl/union_map.h>
 #include <isl_ast_build_private.h>
 #include <isl_ast_private.h>
 #include <isl_config.h>
+#include <include/isl/hash.h>
 
 /* Construct a map that isolates the current dimension.
  *
  * Essentially, the current dimension of "set" is moved to the single output
  * dimension in the result, with the current dimension in the domain replaced
  * by an unconstrained variable.
  */
 __isl_give isl_map *isl_ast_build_map_to_iterator(
   __isl_keep isl_ast_build *build, __isl_take isl_set *set)
 {
   isl_map *map;
 
   map = isl_map_from_domain(set);
   map = isl_map_add_dims(map, isl_dim_out, 1);
 
   if (!build)
     return isl_map_free(map);
 
   map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
   map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
 
   return map;
 }
 
+/* Initialize the local copy of the build-specific options
+ * from the associated isl_ctx.
+ */
+__isl_give isl_ast_build *isl_ast_build_init_options(
+  __isl_take isl_ast_build *build)
+{
+  isl_ctx *ctx;
+
+  build = isl_ast_build_cow(build);
+  if (!build)
+          return NULL;
+  
+  ctx = isl_ast_build_get_ctx(build);
+  build->compute_bounds = isl_options_get_ast_build_compute_bounds(ctx);
+  build->approximate_bounds = isl_options_get_ast_build_approximate_computed_bounds(ctx);
+  build->maximum_size = isl_options_get_ast_build_maximum_native_type(ctx);
+
+  return build;
+}
+
 /* Initialize the information derived during the AST generation to default
  * values for a schedule domain in "space".
  *
  * We also check that the remaining fields are not NULL so that
  * the calling functions don't have to perform this test.
  */
 static __isl_give isl_ast_build *isl_ast_build_init_derived(
   __isl_take isl_ast_build *build, __isl_take isl_space *space)
if (isl_set_has_dim_id(set, isl_dim_set, i))
       id = isl_set_get_dim_id(set, isl_dim_set, i);
     else
       id = generate_name(ctx, i, build);
     build->iterators = isl_id_list_add(build->iterators, id);
   }
   space = isl_set_get_space(set);
   if (isl_space_is_params(space))
     space = isl_space_set_from_params(space);
+  build->compute_bounds = isl_options_get_ast_build_compute_bounds(ctx);
+  build->approximate_bounds = isl_options_get_ast_build_approximate_computed_bounds(ctx);
+  build->maximum_size = isl_options_get_ast_build_maximum_native_type(ctx);
+
 
   return isl_ast_build_init_derived(build, space);
 error:
   isl_set_free(set);
   return NULL;
 }
 
 /* Create an isl_ast_build with a universe (parametric) context.
if (!build)
     return NULL;
 
   ctx = isl_ast_build_get_ctx(build);
   dup = isl_calloc_type(ctx, isl_ast_build);
   if (!dup)
     return NULL;
 
   dup->ref = 1;
+  dup->compute_bounds = build->compute_bounds;
+  dup->approximate_bounds = build->approximate_bounds;
+  dup->maximum_size = build->maximum_size;
   dup->outer_pos = build->outer_pos;
   dup->depth = build->depth;
   dup->iterators = isl_id_list_copy(build->iterators);
   dup->domain = isl_set_copy(build->domain);
   dup->generated = isl_set_copy(build->generated);
   dup->pending = isl_set_copy(build->pending);
   dup->values = isl_multi_aff_copy(build->values);
   dup->internal2input = isl_multi_aff_copy(build->internal2input);
if (!build)
     return NULL;
 
   if (build->ref == 1)
     return build;
   build->ref--;
   return isl_ast_build_dup(build);
 }
 
+static isl_stat free_cache_entry(void **p, void *user)
+{
+  struct isl_aff *expr = *p;
+
+  isl_aff_free(expr);
+
+  return isl_stat_ok;
+}
+
 __isl_null isl_ast_build *isl_ast_build_free(
   __isl_take isl_ast_build *build)
 {
   if (!build)
     return NULL;
 
   if (--build->ref > 0)
     return NULL;
 
+  if (build->cache) {
+    isl_hash_table_foreach(isl_ast_build_get_ctx(build), build->cache, &free_cache_entry, NULL);
+    isl_hash_table_free(isl_ast_build_get_ctx(build), build->cache);
+  }
+
   isl_id_list_free(build->iterators);
   isl_set_free(build->domain);
   isl_set_free(build->generated);
   isl_set_free(build->pending);
   isl_multi_aff_free(build->values);
   isl_multi_aff_free(build->internal2input);
   isl_pw_aff_free(build->value);
   isl_vec_free(build->strides);
__isl_give isl_ast_build *isl_ast_build_set_single_valued(
   if (build->single_valued == sv)
     return build;
   build = isl_ast_build_cow(build);
   if (!build)
     return build;
   build->single_valued = sv;
 
   return build;
-}
+}
 No newline at end of file

lib/External/isl/isl_ast_build_expr.h

 
 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
   __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa);
 __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
   __isl_keep isl_ast_build *build);
 __isl_give isl_ast_expr *isl_ast_expr_set_op_arg(__isl_take isl_ast_expr *expr,
   int pos, __isl_take isl_ast_expr *arg);
 
+__isl_give isl_ast_expr *isl_ast_build_set_size(
+    __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr,
+    __isl_keep isl_aff *aff);
+
 __isl_give isl_ast_node *isl_ast_build_call_from_executed(
   __isl_keep isl_ast_build *build, __isl_take isl_map *executed);
 
 #endif

lib/External/isl/isl_ast_build_expr.c

  */
 
 #include <isl/constraint.h>
 #include <isl/ilp.h>
 #include <isl_ast_build_expr.h>
 #include <isl_ast_private.h>
 #include <isl_ast_build_private.h>
 #include <isl_sort.h>
+#include <include/isl/hash.h>
+
+static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr);
+
+/* Compute the minimum of the integer affine expression "obj" over the points
+ * in build->domain and put the result in *opt.
+ */
+__isl_give isl_val *isl_ast_build_min(__isl_keep isl_ast_build *build,
+  __isl_keep isl_aff *obj)
+{
+  if (!build)
+    return NULL;
+
+  return isl_set_min_val(build->domain, obj);
+}
+
+/* Compute the maximum of the integer affine expression "obj" over the points
+ * in build->domain and put the result in *opt.
+ */
+__isl_give isl_val *isl_ast_build_max(__isl_keep isl_ast_build *build,
+  __isl_keep isl_aff *obj)
+{
+  if (!build)
+    return NULL;
+
+  return isl_set_max_val(build->domain, obj);
+}
+
+/* Approximate the size of the binary operation "expr" by looking at the type
+ * of it's arguments. This only works if the size of the arguments is already
+ * know.
+ */
+__isl_give isl_ast_expr *isl_ast_bin_op_set_size_max(
+  __isl_take isl_ast_expr *expr,  __isl_keep isl_ast_build *build)
+{
+  int flag, num_args;
+  int base_offset = 0;
+  int add = 0;
+  isl_bool is_signed;
+  size_t bits;
+
+  if (!build->compute_bounds)
+    return expr;
+
+  switch (expr->u.op.op) {
+    case isl_ast_op_min:
+      flag = 0;
+      break;
+    case isl_ast_op_sub:
+    case isl_ast_op_max:
+            flag = 1;
+            break;
+    case isl_ast_op_select:
+      flag = 1;
+            base_offset = 1;
+      break;
+    case isl_ast_op_add:
+      flag = 1;
+      add = 1;
+      break;
+    default:
+      isl_die(isl_ast_expr_get_ctx(expr), isl_error_internal,
+        "invalid expression type",  goto error);
+  }
+
+  num_args = expr->u.op.n_arg;
+  for (int i = base_offset; i < num_args; i++) {
+    if (expr->u.op.args[i]->type != isl_ast_expr_bound_t) {
+      return expr;
+    }
+  }
+
+  is_signed = expr->u.op.args[base_offset]->u.bound.is_signed;
+  bits = expr->u.op.args[base_offset]->u.bound.size;
+  if (flag == 1) {
+    // Result is maximum type
+    if (expr->u.op.args[base_offset + 1]->u.bound.size > bits) {
+      bits = expr->u.op.args[base_offset + 1]->u.bound.size;
+      if (is_signed && !expr->u.op.args[base_offset + 1]->
+          u.bound.is_signed)
+        bits++;
+      else
+        is_signed = expr->u.op.args[base_offset + 1]->
+          u.bound.is_signed;
+    } else if (!is_signed && expr->u.op.args[base_offset + 1]->
+        u.bound.is_signed) {
+      is_signed = expr->u.op.args[base_offset + 1]->
+        u.bound.is_signed;
+      if (bits == expr->u.op.args[base_offset + 1]->
+          u.bound.size)
+        bits++;
+    }
+  } else {
+    // Result is minimum type
+    if (expr->u.op.args[base_offset + 1]->u.bound.size < bits ||
+      (expr->u.op.args[base_offset + 1]->u.bound.size == bits
+         && !expr->u.op.args[base_offset + 1]->
+          u.bound.is_signed)) {
+      bits = expr->u.op.args[base_offset + 1]->u.bound.size;
+      is_signed = expr->u.op.args[base_offset + 1]->
+        u.bound.is_signed;
+    }
+  }
+
+  if (add)
+    bits++;
+
+    return isl_ast_expr_bound(expr, is_signed, bits, NULL);
+
+error:
+  return isl_ast_expr_free(expr);
+}
+
+__isl_give isl_ast_expr *isl_ast_bin_op_set_size_mul(
+  __isl_take isl_ast_expr *expr, __isl_keep isl_ast_build *build)
+{
+  int flag;
+  int add = 0;
+  isl_bool is_signed;
+  size_t bits;
+
+  if (expr->u.op.args[0]->type == isl_ast_expr_bound_t &&
+      expr->u.op.args[1]->type == isl_ast_expr_bound_t) {
+    is_signed = expr->u.op.args[0]->u.bound.is_signed;
+    bits = expr->u.op.args[0]->u.bound.size +
+      expr->u.op.args[1]->u.bound.size;
+    if (is_signed != expr->u.op.args[1]->u.bound.is_signed) {
+      bits++;
+      is_signed = isl_bool_true;
+    }
+
+    expr = isl_ast_expr_bound(expr, is_signed, bits, NULL);
+  }
+  return expr;
+}
+
+__isl_give isl_ast_expr *isl_ast_bin_op_set_size_div(
+  __isl_take isl_ast_expr *expr, __isl_keep isl_ast_build *build)
+{
+  int flag;
+  int add = 0;
+  isl_bool is_signed;
+  size_t bits;
+
+  if (expr->u.op.args[0]->type == isl_ast_expr_bound_t &&
+      expr->u.op.args[1]->type == isl_ast_expr_bound_t) {
+    is_signed = expr->u.op.args[1]->u.bound.is_signed;
+    bits = expr->u.op.args[1]->u.bound.size;
+    if (expr->u.op.args[0]->u.bound.is_signed || is_signed) {
+      bits++;
+      is_signed = isl_bool_true;
+    }
+
+    expr = isl_ast_expr_bound(expr, is_signed, bits, NULL);
+  }
+  return expr;
+}
+
+__isl_give isl_ast_expr *isl_ast_bin_op_set_size_minus(
+  __isl_take isl_ast_expr *expr, __isl_keep isl_ast_build *build)
+{
+  int flag;
+  int add = 0;
+  isl_bool is_signed;
+  size_t bits;
+
+  if (expr->u.op.args[0]->type == isl_ast_expr_bound_t) {
+    is_signed = expr->u.op.args[0]->u.bound.is_signed;
+    bits = expr->u.op.args[0]->u.bound.size;
+
+    if (!is_signed) {
+      is_signed = isl_bool_true;
+      bits++;
+    } else {
+      bits++;
+    }
+
+    expr = isl_ast_expr_bound(expr, is_signed, bits, NULL);
+  }
+  return expr;
+}
+
+/* Approximates the size of some binary operators by looking at the size
+ * of their arguments. If the arguments of the operation are not already
+ * bounded, the function will recurse if possible.
+ */
+__isl_give isl_ast_expr *isl_ast_bin_op_set_size(__isl_take isl_ast_expr *expr,
+  __isl_keep isl_ast_build *build)
+{
+  if (!build->compute_bounds)
+    return expr;
+  if (expr->type != isl_ast_expr_op)
+    isl_die(isl_ast_expr_get_ctx(expr), isl_error_internal,
+      "invalid expression type - not an isl_ast_expr_op",
+      goto error);
+
+  for (int i = 0; i < expr->u.op.n_arg; i++) {
+    if (expr->u.op.args[i]->type != isl_ast_expr_bound_t) {
+      if (expr->u.op.args[i]->type == isl_ast_expr_op) {
+        expr->u.op.args[i] = isl_ast_bin_op_set_size(
+            expr->u.op.args[i], build);
+      }
+    }
+  }
+  switch (expr->u.op.op) {
+    case isl_ast_op_min:
+    case isl_ast_op_max:
+    case isl_ast_op_select:
+    case isl_ast_op_add:
+    case isl_ast_op_sub:
+      return isl_ast_bin_op_set_size_max(expr, build);
+    case isl_ast_op_mul:
+      return isl_ast_bin_op_set_size_mul(expr, build);
+    case isl_ast_op_div:
+    case isl_ast_op_fdiv_q:
+    case isl_ast_op_pdiv_r:
+    case isl_ast_op_zdiv_r:
+    case isl_ast_op_pdiv_q:
+      return isl_ast_bin_op_set_size_div(expr, build);
+    case isl_ast_op_minus:
+      return isl_ast_bin_op_set_size_minus(expr, build);
+    default:
+      return expr;
+  }
+
+error:
+  return isl_ast_expr_free(expr);
+}
+
+static int same_aff(const void *entry, const void *val)
+{
+  if (!entry || !val)
+    return 0;
+  return isl_aff_plain_is_equal((isl_aff*)entry, (isl_aff*)val);
+}
+
+/* Compute the minimum type needed to hold 'expr' using 'aff'. This function
+ * gives an exact result but imposes a performance penalty as it invokes the
+ * ILP solver twice.
+ */
+__isl_give isl_ast_expr *isl_ast_build_set_size_with_solver(
+  __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr,
+  __isl_keep isl_aff *aff)
+{
+  isl_val *res = NULL;
+  int upper_bits, lower_bits;
+  uint64_t bound_val;
+  isl_bool is_lower_signed;
+  isl_local_space *ls;
+  isl_aff *upper_val, *lower_val;
+  isl_set *problems = NULL, *problems_parameters;
+  isl_basic_set *bigger;
+  isl_set *smaller;
+
+  if (!build || !expr)
+    return NULL;
+
+  if (!build->compute_bounds)
+    return expr;
+
+  res = isl_ast_build_min(build, aff);
+
+  if (!isl_val_is_int(res)) {
+    isl_val_free(res);
+    return expr;
+  }
+
+  is_lower_signed = isl_val_is_neg(res);
+  lower_bits = isl_val_size_in_bits(res, is_lower_signed);
+  isl_val_free(res);
+
+  res = isl_ast_build_max(build, aff);
+
+  if (!isl_val_is_int(res)) {
+    isl_val_free(res);
+    return expr;
+  }
+
+  upper_bits = isl_val_size_in_bits(res, is_lower_signed);
+  isl_val_free(res);
+
+  if (upper_bits > lower_bits)
+    lower_bits = upper_bits;
+
+  if (build->maximum_size && lower_bits > build->maximum_size) {
+    isl_val *upper, *lower;
+    if (is_lower_signed) {
+      bound_val = (1UL << (build->maximum_size-1))-1;
+      upper = isl_val_int_from_si(
+          isl_ast_build_get_ctx(build),
+          bound_val);
+      bound_val = -(1UL << (build->maximum_size-1));
+      lower = isl_val_int_from_si(
+          isl_ast_build_get_ctx(build),
+          bound_val);
+    } else {
+      bound_val = ~(1UL<< (build->maximum_size));
+      upper = isl_val_int_from_ui(
+          isl_ast_build_get_ctx(build),
+          bound_val);
+      lower = isl_val_int_from_ui(
+          isl_ast_build_get_ctx(build), 0);
+    }
+    ls = isl_aff_get_domain_local_space(aff);
+    upper_val = isl_aff_val_on_domain(isl_local_space_copy(ls),
+        upper);
+    lower_val = isl_aff_val_on_domain(ls, lower);
+
+    bigger = isl_aff_ge_basic_set(isl_aff_copy(aff), upper_val);
+    smaller = isl_pw_aff_lt_set(isl_pw_aff_from_aff(
+          isl_aff_copy(aff)),
+        isl_pw_aff_from_aff(lower_val));
+    problems = isl_set_union(isl_set_from_basic_set(bigger),
+        smaller);
+
+    problems_parameters = isl_set_params(isl_set_copy(problems));
+    if (isl_set_plain_is_universe(problems_parameters)) {
+      problems = isl_set_intersect(problems,
+          isl_set_copy(build->generated));
+    }
+    isl_set_free(problems_parameters);
+
+    problems = isl_set_params(problems);
+    problems = isl_set_gist(problems,
+        isl_set_params(isl_set_copy(build->domain)));
+    lower_bits = build->maximum_size;
+  }
+
+  expr = isl_ast_expr_bound(expr, is_lower_signed, lower_bits, problems);
+
+  return expr;
+}
+
+static int bare_var_cached = 0;
+static int expr_approximated_try = 0;
+static int expr_approximated_success = 0;
+static int expr_total = 0;
+
+/* Try to approximate the binary operation expr (also represented by aff)
+ * by looking at it's arguments.
+ */
+__isl_give isl_ast_expr *isl_ast_build_try_approximate_size(
+  __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr,
+  __isl_keep isl_aff *aff)
+{
+  int all_bound = 1;
+  isl_ast_expr *result;
+
+  for (int i = 0; i < expr->u.op.n_arg; i++)
+    if (expr->u.op.args[i]->type != isl_ast_expr_bound_t)
+      all_bound = 0;
+
+  if (all_bound) {
+    expr = isl_ast_bin_op_set_size(expr, build);
+    expr_approximated_try++;
+    if (expr->type == isl_ast_expr_bound_t &&
+        expr->u.bound.size > build->maximum_size) {
+      result = isl_ast_build_set_size_with_solver(build,
+          isl_ast_expr_get_bound_expr(expr), aff);
+      isl_ast_expr_free(expr);
+      return result;
+    }
+    expr_approximated_success++;
+    return expr;
+  }
+  return isl_ast_build_set_size_with_solver(build, expr, aff);
+}
+
+/* If the ast_build_compute_bounds is set, then compute bounds on "expr"
+ * based on the possible value of "aff" over build->domain.
+ */
+__isl_give isl_ast_expr *isl_ast_build_set_size(
+  __isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr,
+  __isl_keep isl_aff *aff)
+{
+  expr_total++;
+
+  if (build->approximate_bounds) {
+    if (!build->cache) {
+      build->cache = isl_hash_table_alloc(
+          isl_ast_build_get_ctx(build), 16);
+      isl_hash_table_init(isl_ast_build_get_ctx(build),
+          build->cache, 16);
+    }
+
+    if (expr->type == isl_ast_expr_id) {
+      uint32_t hash = isl_id_get_hash(expr->u.id);
+      struct isl_hash_table_entry *entry =
+        isl_hash_table_find(
+          isl_ast_build_get_ctx(build),
+          build->cache, hash, same_aff, aff, 1);
+      if (!entry->data) {
+        expr = isl_ast_build_set_size_with_solver(build,
+            expr, aff);
+        entry->data = isl_aff_copy(aff);
+      } else {
+        bare_var_cached++;
+      }
+      return expr;
+    } else if (expr->type == isl_ast_expr_op) {
+      switch (expr->u.op.op) {
+        case isl_ast_op_min:
+        case isl_ast_op_max:
+        case isl_ast_op_select:
+        case isl_ast_op_add:
+        case isl_ast_op_sub:
+        case isl_ast_op_mul:
+        case isl_ast_op_div:
+        case isl_ast_op_fdiv_q:
+        case isl_ast_op_pdiv_r:
+        case isl_ast_op_zdiv_r:
+        case isl_ast_op_pdiv_q:
+        case isl_ast_op_minus:
+        // (Default: Fall through to solver)
+        return isl_ast_build_try_approximate_size(
+            build, expr, aff);
+      }
+    }
+  }
+
+  return isl_ast_build_set_size_with_solver(build, expr, aff);
+}
+
+/* Data structure that holds an isl_ast_expr and its corresponding
+ * isl_aff.
+ */
+struct isl_ast_expr_constructor {
+  isl_ast_expr *expr;
+  isl_aff *aff;
+};
+typedef struct isl_ast_expr_constructor isl_ast_expr_constructor;
+
+__isl_give isl_ast_expr_constructor *ast_expr_constructor_from_aff(
+  __isl_take isl_aff *aff, __isl_keep isl_ast_build *build);
+
+static void *isl_ast_expr_constructor_free(
+  __isl_take isl_ast_expr_constructor *cons)
+{
+  if (!cons)
+    return NULL;
+
+  isl_ast_expr_free(cons->expr);
+  isl_aff_free(cons->aff);
+  free(cons);
+  return NULL;
+}
+
+static __isl_give isl_ast_expr *isl_ast_expr_constructor_get_ast_expr(
+  __isl_take isl_ast_expr_constructor *cons)
+{
+  if (!cons)
+    return NULL;
+
+  return isl_ast_expr_copy(cons->expr);
+}
+
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_alloc(
+  __isl_take isl_local_space *ls)
+{
+  isl_ast_expr_constructor *cons;
+  isl_ctx *ctx;
+
+  if (!ls)
+    return NULL;
+
+  ctx = isl_local_space_get_ctx(ls);
+  cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+  if (!cons)
+    goto error;
+
+  cons->expr = isl_ast_expr_alloc_int_si(ctx, 0);
+  cons->aff = isl_aff_zero_on_domain(ls);
+
+  if (!cons->expr || !cons->aff)
+    return isl_ast_expr_constructor_free(cons);
+
+  return cons;
+error:
+  isl_local_space_free(ls);
+  return NULL;
+}
+
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_val(
+  __isl_take isl_local_space *ls, __isl_take isl_val *v,
+  __isl_keep isl_ast_build *build)
+{
+  isl_ast_expr_constructor *cons;
+  isl_ctx *ctx;
+
+  if (!ls)
+    return NULL;
+
+  ctx = isl_local_space_get_ctx(ls);
+  cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+  if (!cons)
+    goto error;
+
+  cons->aff = isl_aff_zero_on_domain(ls);
+  cons->aff = isl_aff_add_constant_val(cons->aff, isl_val_copy(v));
+  cons->expr = isl_ast_expr_from_val(v);
+
+  if (!cons->expr || !cons->aff)
+    return isl_ast_expr_constructor_free(cons);
+
+  return cons;
+error:
+  isl_local_space_free(ls);
+  return NULL;
+}
 
 /* Compute the "opposite" of the (numerator of the) argument of a div
  * with denominator "d".
  *
  * In particular, compute
  *
  *  -aff + (d - 1)
  */
static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,
   t = isl_val_copy(shift);
   t = isl_val_mul(t, isl_val_copy(data->v));
   data->cst = isl_val_sub(data->cst, t);
 
   shift = isl_val_mul(shift, isl_val_copy(d));
   return isl_aff_add_constant_val(aff, shift);
 }
 
+/* Set the size of cons->expr based on range of values attained
+ * by cons->aff over build->domain. This is used to handle edge-cases
+ * where the constructor does not actually contain a composite expression.
+ */
+static void isl_ast_expr_constructor_set_size(
+  __isl_keep isl_ast_expr_constructor *cons,
+  __isl_keep isl_ast_build *build)
+{
+  if (cons->expr->type != isl_ast_expr_bound_t) {
+    cons->expr = isl_ast_build_set_size(build, cons->expr,
+        cons->aff);
+  }
+}
+
+/* Add cons2->expr to cons1->expr and compute the size of the result.
+ * The result is simplified in terms of build->domain.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add(
+    __isl_take isl_ast_expr_constructor *cons1,
+  __isl_take isl_ast_expr_constructor *cons2,
+  __isl_keep isl_ast_build *build)
+{
+  if (!cons1 || !cons2)
+    goto error;
+
+  if (isl_aff_plain_is_zero(cons1->aff)) {
+    isl_ast_expr_constructor_free(cons1);
+    return cons2;
+  }
+
+  if (isl_aff_plain_is_zero(cons2->aff)) {
+    isl_ast_expr_constructor_free(cons2);
+    return cons1;
+  }
+
+  cons1->expr = isl_ast_expr_add(cons1->expr,
+          isl_ast_expr_copy(cons2->expr));
+  cons1->aff = isl_aff_add(cons1->aff, isl_aff_copy(cons2->aff));
+  isl_ast_expr_constructor_set_size(cons1, build);
+
+  isl_ast_expr_constructor_free(cons2);
+
+  if (!cons1->expr || !cons1->aff)
+    return isl_ast_expr_constructor_free(cons1);
+  return cons1;
+error:
+  isl_ast_expr_constructor_free(cons2);
+  return isl_ast_expr_constructor_free(cons1);
+}
+
+/* Subtract cons2->expr from cons1->expr and compute the size of the result.
+ * The result is simplified in terms of build->domain.
+ *
+ * If cons2->expr is zero, we simply return cons1->expr.
+ * If cons1->expr is zero, we return
+ *
+ *      (isl_ast_op_minus, cons2->expr)
+ *
+ * Otherwise, we return
+ *
+ *      (isl_ast_op_sub, cons1->expr, cons2->expr)
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_sub(
+  __isl_take isl_ast_expr_constructor *cons1,
+  __isl_take isl_ast_expr_constructor *cons2,
+  __isl_keep isl_ast_build *build)
+{
+  if (!cons1 || !cons2)
+    goto error;
+
+  if (isl_aff_plain_is_zero(cons2->aff)) {
+    isl_ast_expr_constructor_free(cons2);
+    return cons1;
+  }
+
+  if (isl_aff_plain_is_zero(cons1->aff)) {
+    cons2->aff = isl_aff_neg(cons2->aff);
+    cons2->expr = isl_ast_expr_neg(cons2->expr);
+    isl_ast_expr_constructor_free(cons1);
+    isl_ast_expr_constructor_set_size(cons2, build);
+    if (!cons2->expr || !cons2->aff)
+      return isl_ast_expr_constructor_free(cons2);
+    return cons2;
+  }
+
+  cons1->expr = isl_ast_expr_sub(cons1->expr,
+          isl_ast_expr_copy(cons2->expr));
+  cons1->aff = isl_aff_sub(cons1->aff, isl_aff_copy(cons2->aff));
+  isl_ast_expr_constructor_set_size(cons1, build);
+
+  isl_ast_expr_constructor_free(cons2);
+
+  if (!cons1->expr || !cons1->aff)
+    return isl_ast_expr_constructor_free(cons1);
+  return cons1;
+error:
+  isl_ast_expr_constructor_free(cons2);
+  return isl_ast_expr_constructor_free(cons1);
+}
+
+/* Return an isl_ast_expr_constructor that represents
+ *
+ *      v * (aff mod d)
+ *
+ * v is assumed to be non-negative.
+ * The result is simplified in terms of build->domain.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_mod(
+  __isl_take isl_val *v, __isl_keep isl_aff *aff,
+  __isl_take isl_val *d,
+  __isl_keep isl_ast_build *build)
+{
+  isl_ctx *ctx;
+  isl_ast_expr_constructor *cons;
+  isl_ast_expr *c;
+
+  if (!aff)
+    goto out;
+
+  ctx = isl_aff_get_ctx(aff);
+  cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+  if (!cons)
+    goto out;
+
+  cons->aff = isl_aff_copy(aff);
+  cons->expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
+
+  c = isl_ast_expr_from_val(isl_val_copy(d));
+  cons->expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r,
+            cons->expr, c);
+  cons->aff = isl_aff_mod_val(cons->aff, d);
+  isl_ast_expr_constructor_set_size(cons, build);
+
+  if (!isl_val_is_one(v)) {
+    c = isl_ast_expr_from_val(isl_val_copy(v));
+    cons->expr = isl_ast_expr_mul(c, cons->expr);
+    cons->aff = isl_aff_scale_val(cons->aff, isl_val_copy(v));
+    isl_ast_expr_constructor_set_size(cons, build);
+  }
+
+  if (!cons->expr || !cons->aff) {
+    isl_val_free(v);
+    return isl_ast_expr_constructor_free(cons);
+  }
+
+
+  isl_val_free(v);
+  return cons;
+
+out:
+  isl_val_free(v);
+  isl_val_free(d);
+  return NULL;
+}
+
+/* Devide cons2->expr by cons1->expr and compute the size of the result.
+ * The result is simplified in terms of build->domain.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_div(
+    __isl_take isl_ast_expr_constructor *cons1,
+  __isl_take isl_ast_expr_constructor *cons2,
+  __isl_keep isl_ast_build *build)
+{
+  if (!cons1 || !cons2)
+    goto error;
+
+  cons1->expr = isl_ast_expr_div(cons1->expr,
+          isl_ast_expr_copy(cons2->expr));
+  cons1->aff = isl_aff_div(cons1->aff, isl_aff_copy(cons2->aff));
+  cons1->aff = isl_aff_floor(cons1->aff);
+  isl_ast_expr_constructor_set_size(cons1, build);
+
+  isl_ast_expr_constructor_free(cons2);
+
+  if (!cons1->expr || !cons1->aff)
+    return isl_ast_expr_constructor_free(cons1);
+  return cons1;
+error:
+  isl_ast_expr_constructor_free(cons2);
+  return isl_ast_expr_constructor_free(cons1);
+}
+
 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
  * The result is simplified in terms of data->build->domain.
  * This function may change (the sign of) data->v.
  *
  * "ls" is known to be non-NULL.
  *
  * Let the div be of the form floor(e/d).
  * If the ast_build_prefer_pdiv option is set then we check if "e"
static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,
 
   if (!isl_local_space_has_dim_id(ls, type, pos))
     isl_die(ctx, isl_error_internal, "unnamed dimension",
       return NULL);
   id = isl_local_space_get_dim_id(ls, type, pos);
   return isl_ast_expr_from_id(id);
 }
 
+/* Add an expression for "v" to cons->expr.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_int(
+  __isl_take isl_ast_expr_constructor *cons, __isl_take isl_val *v,
+  __isl_keep isl_ast_build *build);
+
 /* Does "expr" represent the zero integer?
  */
 static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
 {
   if (!expr)
     return -1;
+  if (expr->type == isl_ast_expr_bound_t)
+    expr = expr->u.bound.expr;
   if (expr->type != isl_ast_expr_int)
     return 0;
   return isl_val_is_zero(expr->u.v);
 }
 
 /* Create an expression representing the sum of "expr1" and "expr2",
  * provided neither of the two expressions is identically zero.
  */
static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
 
   return isl_ast_expr_sub(expr1, expr2);
 error:
   isl_ast_expr_free(expr1);
   isl_ast_expr_free(expr2);
   return NULL;
 }
 
-/* Return an isl_ast_expr that represents
- *
- *  v * (aff mod d)
- *
- * v is assumed to be non-negative.
- * The result is simplified in terms of build->domain.
- */
-static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
-  __isl_keep isl_aff *aff, __isl_keep isl_val *d,
-  __isl_keep isl_ast_build *build)
-{
-  isl_ast_expr *expr;
-  isl_ast_expr *c;
-
-  if (!aff)
-    return NULL;
-
-  expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
-
-  c = isl_ast_expr_from_val(isl_val_copy(d));
-  expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
-
-  if (!isl_val_is_one(v)) {
-    c = isl_ast_expr_from_val(isl_val_copy(v));
-    expr = isl_ast_expr_mul(c, expr);
-  }
-
-  return expr;
-}
-
 /* Create an isl_ast_expr that scales "expr" by "v".
  *
  * If v is 1, we simply return expr.
  * If v is -1, we return
  *
  *  (isl_ast_op_minus, expr)
  *
  * Otherwise, we return
  *
  *  (isl_ast_op_mul, expr(v), expr)
  */
-static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
-  __isl_take isl_val *v)
+static __isl_give isl_ast_expr_constructor *scale(
+  __isl_take isl_ast_expr_constructor *cons,
+  __isl_take isl_val *v, __isl_keep isl_ast_build *build)
 {
   isl_ast_expr *c;
 
-  if (!expr || !v)
+  if (!cons || !v)
     goto error;
   if (isl_val_is_one(v)) {
     isl_val_free(v);
-    return expr;
+    return cons;
   }
 
   if (isl_val_is_negone(v)) {
     isl_val_free(v);
-    expr = isl_ast_expr_neg(expr);
+    cons->expr = isl_ast_expr_neg(cons->expr);
+    cons->aff = isl_aff_neg(cons->aff);
   } else {
-    c = isl_ast_expr_from_val(v);
-    expr = isl_ast_expr_mul(c, expr);
+    c = isl_ast_expr_from_val(isl_val_copy(v));
+    cons->expr = isl_ast_expr_mul(c, cons->expr);
+    cons->aff = isl_aff_scale_val(cons->aff, v);
   }
 
-  return expr;
+  isl_ast_expr_constructor_set_size(cons, build);
+
+  return cons;
 error:
   isl_val_free(v);
-  isl_ast_expr_free(expr);
+  isl_ast_expr_constructor_free(cons);
   return NULL;
 }
 
+/* Create an isl_ast_expr evaluating "v" times the specified dimension of "ls".
+ * The result is simplified in terms of build->domain.
+ *
+ * Let e be the expression for the specified dimension.
+ * If v is 1, we simply return e.
+ * If v is -1, we return
+ *
+ *  (isl_ast_op_minus, e)
+ *
+ * Otherwise, we return
+ *
+ *  (isl_ast_op_mul, expr(v), e)
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_term(
+  __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
+  struct isl_ast_add_term_data *data)
+{
+  isl_ctx *ctx;
+  isl_ast_expr_constructor *cons;
+  if (!ls)
+    return NULL;
+
+  ctx = isl_local_space_get_ctx(ls);
+  cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+  if (!cons)
+    return NULL;
+
+  cons->expr = var(data, ls, type, pos);
+  cons->aff = isl_aff_var_on_domain(isl_local_space_copy(ls), type, pos);
+  isl_ast_expr_constructor_set_size(cons, data->build);
+
+  if (!cons->expr || !cons->aff)
+    return isl_ast_expr_constructor_free(cons);
+  return cons;
+}
+
 /* Add an expression for "*v" times the specified dimension of "ls"
  * to expr.
  * If the dimension is an integer division, then this function
  * may modify data->cst in order to make the numerator non-negative.
  * The result is simplified in terms of data->build->domain.
  *
  * Let e be the expression for the specified dimension,
  * multiplied by the absolute value of "*v".
  * If "*v" is negative, we create
  *
  *  (isl_ast_op_sub, expr, e)
  *
  * except when expr is trivially zero, in which case we create
  *
  *  (isl_ast_op_minus, e)
  *
  * instead.
  *
  * If "*v" is positive, we simply create
  *
  *  (isl_ast_op_add, expr, e)
  *
  */
-static __isl_give isl_ast_expr *isl_ast_expr_add_term(
-  __isl_take isl_ast_expr *expr,
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_term(
+  __isl_take isl_ast_expr_constructor *cons,
   __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
   __isl_take isl_val *v, struct isl_ast_add_term_data *data)
 {
-  isl_ast_expr *term;
+  isl_ast_expr_constructor *term;
 
-  if (!expr)
+  if (!cons)
     return NULL;
 
   data->v = v;
-  term = var(data, ls, type, pos);
+  term = isl_ast_expr_constructor_term(ls, type, pos, data);
   v = data->v;
 
-  if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
+  if (isl_val_is_neg(v) && !ast_expr_is_zero(cons->expr)) {
     v = isl_val_neg(v);
-    term = scale(term, v);
-    return ast_expr_sub(expr, term);
+    term = scale(term, v, data->build);
+    cons = isl_ast_expr_constructor_sub(cons, term, data->build);
+    return cons;
   } else {
-    term = scale(term, v);
-    return ast_expr_add(expr, term);
+    term = scale(term, v, data->build);
+    cons = isl_ast_expr_constructor_add(cons, term, data->build);
+    return cons;
   }
 }
 
 /* Add an expression for "v" to expr.
  */
 static __isl_give isl_ast_expr *isl_ast_expr_add_int(
   __isl_take isl_ast_expr *expr, __isl_take isl_val *v)
 {
if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
     return ast_expr_add(expr, expr_int);
   }
 error:
   isl_ast_expr_free(expr);
   isl_val_free(v);
   return NULL;
 }
 
+/* Add an expression for "v" to expr.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_int(
+  __isl_take isl_ast_expr_constructor *cons, __isl_take isl_val *v,
+  __isl_keep isl_ast_build *build)
+{
+  isl_local_space *ls;
+  isl_ast_expr_constructor *cons_int;
+
+  if (!cons || !v)
+    goto error;
+
+  if (isl_val_is_zero(v)) {
+    isl_val_free(v);
+    return cons;
+  }
+
+  ls = isl_aff_get_domain_local_space(cons->aff);
+
+  if (isl_val_is_neg(v) && !ast_expr_is_zero(cons->expr)) {
+    v = isl_val_neg(v);
+    cons_int = isl_ast_expr_constructor_val(ls, v, build);
+    if (!cons_int)
+      goto error;
+    cons = isl_ast_expr_constructor_sub(cons, cons_int, build);
+  } else {
+    cons_int = isl_ast_expr_constructor_val(ls, v, build);
+    if (!cons_int)
+      goto error;
+    cons = isl_ast_expr_constructor_add(cons, cons_int, build);
+  }
+
+  return cons;
+error:
+  isl_ast_expr_constructor_free(cons);
+  isl_val_free(v);
+  return NULL;
+}
+
 /* Internal data structure used inside extract_modulos.
  *
  * If any modulo expressions are detected in "aff", then the
  * expression is removed from "aff" and added to either "pos" or "neg"
  * depending on the sign of the coefficient of the modulo expression
  * inside "aff".
  *
  * "add" is an expression that needs to be added to "aff" at the end of

  * are equal to those of "div" modulo "d".  If "sign" is -1, then
  * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
  * If "sign" is 0, then no such affine expression has been found (yet).
  */
 struct isl_extract_mod_data {
   isl_ast_build *build;
   isl_aff *aff;
 
-  isl_ast_expr *pos;
-  isl_ast_expr *neg;
+  isl_ast_expr_constructor *pos;
+  isl_ast_expr_constructor *neg;
 
   isl_aff *add;
 
   int i;
   isl_val *v;
   isl_val *d;
   isl_aff *div;
 

  *
  * to data->add and
  *
  *  abs(f) * (arg mod d)
  *
  * to data->neg or data->pos depending on the sign of -f.
  */
 static int extract_term_and_mod(struct isl_extract_mod_data *data,
-  __isl_take isl_aff *term, __isl_take isl_aff *arg)
+  __isl_take isl_aff *term, __isl_take isl_aff *arg,
+  __isl_keep isl_ast_build *build)
 {
-  isl_ast_expr *expr;
+  isl_ast_expr_constructor *cons;
   int s;
 
   data->v = isl_val_div(data->v, isl_val_copy(data->d));
   s = isl_val_sgn(data->v);
   data->v = isl_val_abs(data->v);
-  expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
+  cons = isl_ast_expr_constructor_mod(isl_val_copy(data->v), arg,
+      isl_val_copy(data->d), data->build);
   isl_aff_free(arg);
   if (s > 0)
-    data->neg = ast_expr_add(data->neg, expr);
+    data->neg = isl_ast_expr_constructor_add(data->neg, cons,
+        build);
   else
-    data->pos = ast_expr_add(data->pos, expr);
+    data->pos = isl_ast_expr_constructor_add(data->pos, cons,
+        build);
   data->aff = isl_aff_set_coefficient_si(data->aff,
-            isl_dim_div, data->i, 0);
   if (s < 0)
     data->v = isl_val_neg(data->v);
   term = isl_aff_scale_val(term, isl_val_copy(data->v));
 
   if (!data->add)
     data->add = term;
   else
     data->add = isl_aff_add(data->add, term);

  *  f * div
  *
  * to data->add and
  *
  *  abs(f) * (div mod d)
  *
  * to data->neg or data->pos depending on the sign of -f.
  */
-static int extract_mod(struct isl_extract_mod_data *data)
+static int extract_mod(struct isl_extract_mod_data *data,
+  __isl_keep isl_ast_build *build)
 {
   return extract_term_and_mod(data, isl_aff_copy(data->div),
-      isl_aff_copy(data->div));
+      isl_aff_copy(data->div), build);
 }
 
 /* Given that data->v * div_i in data->aff is of the form
  *
  *  f * d * floor(div/d)          (1)
  *
  * check if div is non-negative on data->build and, if so,
  * extract the corresponding modulo from data->aff.
  * If not, then check if
  *
  *  -div + d - 1
  *
  * is non-negative on data->build.  If so, replace (1) by
  *
  *  -f * d * floor((-div + d - 1)/d)
  *
  * and extract the corresponding modulo from data->aff.
  *
  * This function may modify data->div.
  */
-static int extract_nonneg_mod(struct isl_extract_mod_data *data)
+static int extract_nonneg_mod(struct isl_extract_mod_data *data,
+  __isl_take isl_ast_build *build)
 {
   int mod;
 
   mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
   if (mod < 0)
     goto error;
   if (mod)
-    return extract_mod(data);
+    return extract_mod(data, build);
 
   data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
   mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
   if (mod < 0)
     goto error;
   if (mod) {
     data->v = isl_val_neg(data->v);
-    return extract_mod(data);
+    return extract_mod(data, build);
   }
 
   return 0;
 error:
   data->aff = isl_aff_free(data->aff);
   return -1;
 }
 

  * also in one with a minimal range, then we don't just want
  * c = \sum_i lambda_i v_i to be non-negative over the domain,
  * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
  * that we want to minimize and we now also have to take into account
  * the constant terms of the constraints.
  * Alternatively, we could first compute the dual of the domain
  * and plug in the constraints on the coefficients.
  */
-static int try_extract_mod(struct isl_extract_mod_data *data)
+static int try_extract_mod(struct isl_extract_mod_data *data,
+  __isl_keep isl_ast_build *build)
 {
   isl_basic_set *hull;
   isl_val *v1, *v2;
   int r, n;
 
   if (!data->build)
     goto error;
 
   n = isl_aff_dim(data->div, isl_dim_div);
 
   if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
-    return extract_nonneg_mod(data);
+    return extract_nonneg_mod(data, build);
 
   hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
   hull = isl_basic_set_remove_divs(hull);
   data->sign = 0;
   data->nonneg = NULL;
   r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,
           data);
   isl_basic_set_free(hull);
 
   if (!data->sign || r < 0) {
     isl_aff_free(data->nonneg);
     if (r < 0)
       goto error;
-    return extract_nonneg_mod(data);
+    return extract_nonneg_mod(data, build);
   }
 
   v1 = isl_aff_get_constant_val(data->div);
   v2 = isl_aff_get_constant_val(data->nonneg);
   if (data->sign < 0) {
     v1 = isl_val_neg(v1);
     v1 = isl_val_add(v1, isl_val_copy(data->d));
     v1 = isl_val_sub_ui(v1, 1);
static int try_extract_mod(struct isl_extract_mod_data *data,
   isl_val_free(v2);
 
   if (data->sign < 0) {
     data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
     data->v = isl_val_neg(data->v);
   }
 
   return extract_term_and_mod(data,
-            isl_aff_copy(data->div), data->nonneg);
+      isl_aff_copy(data->div), data->nonneg, build);
 error:
   data->aff = isl_aff_free(data->aff);
   return -1;
 }
 
 /* Check if "data->aff" involves any (implicit) modulo computations based
  * on div "data->i".
  * If so, remove them from aff and add expressions corresponding

  * we need to make sure that a is non-negative.
  * If not, we check if "-a + m - 1" is non-negative.
  * If so, we can rewrite
  *
  *  floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
  *
  * and still extract a modulo.
  */
-static int extract_modulo(struct isl_extract_mod_data *data)
+static int extract_modulo(struct isl_extract_mod_data *data,
+  __isl_keep isl_ast_build *build)
 {
   data->div = isl_aff_get_div(data->aff, data->i);
   data->d = isl_aff_get_denominator_val(data->div);
   if (isl_val_is_divisible_by(data->v, data->d)) {
     data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
-    if (try_extract_mod(data) < 0)
+    if (try_extract_mod(data, build) < 0)
       data->aff = isl_aff_free(data->aff);
   }
   isl_aff_free(data->div);
   isl_val_free(data->d);
   return 0;
 }
 
 /* Check if "aff" involves any (implicit) modulo computations.

  *
  *  f * (a - (a mod m)) = f * a - f * (a mod m)
  *
  * and extract out -f * (a mod m).
  * In particular, if f > 0, we add (f * (a mod m)) to *neg.
  * If f < 0, we add ((-f) * (a mod m)) to *pos.
  */
 static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
-  __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
+  __isl_keep isl_ast_expr_constructor **cons_pos,
+  __isl_keep isl_ast_expr_constructor **cons_neg,
   __isl_keep isl_ast_build *build)
 {
-  struct isl_extract_mod_data data = { build, aff, *pos, *neg };
+  struct isl_extract_mod_data data = { build, aff, *cons_pos, *cons_neg };
   isl_ctx *ctx;
   int n;
 
   if (!aff)
     return NULL;
 
   ctx = isl_aff_get_ctx(aff);
   if (!isl_options_get_ast_build_prefer_pdiv(ctx))
     return aff;
 
   n = isl_aff_dim(data.aff, isl_dim_div);
   for (data.i = 0; data.i < n; ++data.i) {
     data.v = isl_aff_get_coefficient_val(data.aff,
               isl_dim_div, data.i);
     if (!data.v)
       return isl_aff_free(aff);
     if (isl_val_is_zero(data.v) ||
         isl_val_is_one(data.v) || isl_val_is_negone(data.v)) {
       isl_val_free(data.v);
       continue;
     }
-    if (extract_modulo(&data) < 0)
+    if (extract_modulo(&data, build) < 0)
       data.aff = isl_aff_free(data.aff);
     isl_val_free(data.v);
     if (!data.aff)
       break;
   }
 
   if (data.add)
     data.aff = isl_aff_add(data.aff, data.add);
 
-  *pos = data.pos;
-  *neg = data.neg;
+  *cons_pos = data.pos;
+  *cons_neg = data.neg;
   return data.aff;
 }
 
 /* Check if aff involves any non-integer coefficients.
  * If so, split aff into
  *
  *  aff = aff1 + (aff2 / d)
  *
  * with both aff1 and aff2 having only integer coefficients.
  * Return aff1 and add (aff2 / d) to *expr.
  */
 static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
-  __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
+  __isl_keep isl_ast_expr_constructor **cons, __isl_keep isl_ast_build *build)
 {
   int i, j, n;
   isl_aff *rat = NULL;
   isl_local_space *ls = NULL;
-  isl_ast_expr *rat_expr;
+  isl_ast_expr_constructor *rat_cons;
   isl_val *v, *d;
   enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
   enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
 
   if (!aff)
     return NULL;
   d = isl_aff_get_denominator_val(aff);
   if (!d)
if (isl_val_is_divisible_by(v, d)) {
     isl_val_free(v);
   } else {
     isl_aff *rat_0;
 
     rat_0 = isl_aff_val_on_domain(isl_local_space_copy(ls), v);
     rat = isl_aff_add(rat, rat_0);
   }
 
-  isl_local_space_free(ls);
-
   aff = isl_aff_sub(aff, isl_aff_copy(rat));
   aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
 
-  rat_expr = isl_ast_expr_from_aff(rat, build);
-  rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
-  *expr = ast_expr_add(*expr, rat_expr);
+  rat_cons = ast_expr_constructor_from_aff(rat, build);
+  rat_cons = isl_ast_expr_constructor_div(rat_cons,
+      isl_ast_expr_constructor_val(ls, d, build), build);
+  *cons = isl_ast_expr_constructor_add(*cons, rat_cons, build);
 
   return aff;
 error:
   isl_aff_free(rat);
   isl_local_space_free(ls);
   isl_aff_free(aff);
   isl_val_free(d);
   return NULL;
 }
 
 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
  * The result is simplified in terms of build->domain.
  *
  * We first extract hidden modulo computations from the affine expression
  * and then add terms for each variable with a non-zero coefficient.
  * Finally, if the affine expression has a non-trivial denominator,
  * we divide the resulting isl_ast_expr by this denominator.
  */
-__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
-  __isl_keep isl_ast_build *build)
+__isl_give isl_ast_expr_constructor *ast_expr_constructor_from_aff(
+  __isl_take isl_aff *aff, __isl_keep isl_ast_build *build)
 {
   int i, j;
   int n;
   isl_val *v;
-  isl_ctx *ctx = isl_aff_get_ctx(aff);
-  isl_ast_expr *expr, *expr_neg;
+  isl_ast_expr_constructor *cons, *cons_neg;
   enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
   enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
   isl_local_space *ls;
   struct isl_ast_add_term_data data;
 
   if (!aff)
     return NULL;
 
-  expr = isl_ast_expr_alloc_int_si(ctx, 0);
-  expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
-
-  aff = extract_rational(aff, &expr, build);
+  ls = isl_aff_get_domain_local_space(aff);
 
-  aff = extract_modulos(aff, &expr, &expr_neg, build);
-  expr = ast_expr_sub(expr, expr_neg);
+  cons = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls));
+  cons_neg = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls));
+  aff = extract_rational(aff, &cons, build);
+  aff = extract_modulos(aff, &cons, &cons_neg, build);
 
-  ls = isl_aff_get_domain_local_space(aff);
+  cons = isl_ast_expr_constructor_sub(cons, cons_neg, build);
 
   data.build = build;
   data.cst = isl_aff_get_constant_val(aff);
   for (i = 0; i < 3; ++i) {
     n = isl_aff_dim(aff, t[i]);
     for (j = 0; j < n; ++j) {
       v = isl_aff_get_coefficient_val(aff, t[i], j);
       if (!v)
-        expr = isl_ast_expr_free(expr);
+        cons = isl_ast_expr_constructor_free(cons);
       if (isl_val_is_zero(v)) {
         isl_val_free(v);
         continue;
       }
-      expr = isl_ast_expr_add_term(expr,
+      cons = isl_ast_expr_constructor_add_term(cons,
               ls, l[i], j, v, &data);
     }
   }
 
-  expr = isl_ast_expr_add_int(expr, data.cst);
+  v = data.cst;
+  cons = isl_ast_expr_constructor_add_int(cons, v, build);
+  if (!cons)
+    isl_die(isl_val_get_ctx(v), isl_error_internal,
+        "couldn't create constructor", goto out);
 
+out:
   isl_local_space_free(ls);
   isl_aff_free(aff);
+  return cons;
+}
+
+/* Construct an isl_ast_expr that evaluates the affine expression "aff",
+ * The result is simplified in terms of build->domain.
+ */
+__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
+  __isl_keep isl_ast_build *build)
+{
+  isl_ast_expr_constructor *cons;
+  isl_ast_expr *expr;
+
+  cons = ast_expr_constructor_from_aff(aff, build);
+  if (cons)
+    isl_ast_expr_constructor_set_size(cons, build);
+  expr = isl_ast_expr_constructor_get_ast_expr(cons);
+  isl_ast_expr_constructor_free(cons);
+
   return expr;
 }
 
 /* Add terms to "expr" for each variable in "aff" with a coefficient
  * with sign equal to "sign".
  * The result is simplified in terms of data->build->domain.
  */
-static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
+static __isl_give isl_ast_expr_constructor *add_signed_terms(
+  __isl_take isl_ast_expr_constructor *cons,
   __isl_keep isl_aff *aff, int sign, struct isl_ast_add_term_data *data)
 {
   int i, j;
   isl_val *v;
   enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
   enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
   isl_local_space *ls;
 
   ls = isl_aff_get_domain_local_space(aff);
 
   for (i = 0; i < 3; ++i) {
     int n = isl_aff_dim(aff, t[i]);
     for (j = 0; j < n; ++j) {
       v = isl_aff_get_coefficient_val(aff, t[i], j);
       if (sign * isl_val_sgn(v) <= 0) {
         isl_val_free(v);
         continue;
       }
       v = isl_val_abs(v);
-      expr = isl_ast_expr_add_term(expr,
+      cons = isl_ast_expr_constructor_add_term(cons,
             ls, l[i], j, v, data);
     }
   }
 
   isl_local_space_free(ls);
 
-  return expr;
+  return cons;
 }
 
 /* Should the constant term "v" be considered positive?
  *
  * A positive constant will be added to "pos" by the caller,
  * while a negative constant will be added to "neg".
  * If either "pos" or "neg" is exactly zero, then we prefer
  * to add the constant "v" to that side, irrespective of the sign of "v".

  * instead.
  */
 static __isl_give isl_ast_expr *extract_stride_constraint(
   __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
 {
   isl_ctx *ctx;
   isl_val *c;
   isl_ast_expr *expr, *cst;
+  isl_aff *aff_in;
 
   if (!aff)
     return NULL;
 
   ctx = isl_aff_get_ctx(aff);
 
   c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
   aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
 
   if (all_negative_coefficients(aff))
     aff = isl_aff_neg(aff);
 
   cst = isl_ast_expr_from_val(isl_val_abs(c));
+  aff_in = isl_aff_copy(aff);
   expr = isl_ast_expr_from_aff(aff, build);
 
   expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst);
   cst = isl_ast_expr_alloc_int_si(ctx, 0);
   expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst);
 
+  expr = isl_ast_build_set_size(build,expr,aff_in);
+  isl_aff_free(aff_in);
+
   return expr;
 }
 
 /* Construct an isl_ast_expr that evaluates the condition "constraint",
  * The result is simplified in terms of build->domain.
  *
  * We first check if the constraint is an equality of the form
  *

  * with negative coefficients), then the constant term is added to "pos"
  * (or "neg"), ignoring the sign of the constant term.
  */
 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
   __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
 {
   int i, n;
   isl_ctx *ctx;
-  isl_ast_expr *expr_pos;
-  isl_ast_expr *expr_neg;
+  isl_ast_expr *expr_pos, *expr_pos_t;
+  isl_ast_expr *expr_neg, *expr_neg_t;
   isl_ast_expr *expr;
-  isl_aff *aff;
+  isl_ast_expr_constructor *cons_pos, *cons_neg;
+  isl_local_space *ls;
+  isl_aff *aff, *aff_val;
   int eq;
   enum isl_ast_op_type type;
   struct isl_ast_add_term_data data;
 
   if (!constraint)
     return NULL;
 
   aff = isl_constraint_get_aff(constraint);
   eq = isl_constraint_is_equality(constraint);
   isl_constraint_free(constraint);
 
   n = isl_aff_dim(aff, isl_dim_div);
   if (eq && n > 0)
     for (i = 0; i < n; ++i) {
       int is_stride;
       is_stride = is_stride_constraint(aff, i);
       if (is_stride < 0)
         goto error;
       if (is_stride)
         return extract_stride_constraint(aff, i, build);
     }
 
-  ctx = isl_aff_get_ctx(aff);
-  expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
-  expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
-
-  aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
+  ls = isl_aff_get_domain_local_space(aff);
+  cons_pos = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls));
+  cons_neg = isl_ast_expr_constructor_alloc(ls);
+  aff = extract_modulos(aff, &cons_pos, &cons_neg, build);
 
   data.build = build;
   data.cst = isl_aff_get_constant_val(aff);
-  expr_pos = add_signed_terms(expr_pos, aff, 1, &data);
+
+  cons_pos = add_signed_terms(cons_pos, aff, 1, &data);
+  expr_pos = isl_ast_expr_constructor_get_ast_expr(cons_pos);
+
   data.cst = isl_val_neg(data.cst);
-  expr_neg = add_signed_terms(expr_neg, aff, -1, &data);
+  cons_neg = add_signed_terms(cons_neg, aff, -1, &data);
+  expr_neg = isl_ast_expr_constructor_get_ast_expr(cons_neg);
   data.cst = isl_val_neg(data.cst);
 
   if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) {
-    expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);
+    cons_pos = isl_ast_expr_constructor_add_int(cons_pos, data.cst,
+                  build);
+    isl_ast_expr_free(expr_pos);
+    expr_pos = isl_ast_expr_constructor_get_ast_expr(cons_pos);
   } else {
     data.cst = isl_val_neg(data.cst);
-    expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);
+    cons_neg = isl_ast_expr_constructor_add_int(cons_neg, data.cst,
+                  build);
+    isl_ast_expr_free(expr_neg);
+    expr_neg = isl_ast_expr_constructor_get_ast_expr(cons_neg);
   }
 
-  if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
-      isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) {
+  isl_ast_expr_constructor_free(cons_pos);
+  isl_ast_expr_constructor_free(cons_neg);
+
+  if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_bound_t)
+    expr_pos_t = expr_pos->u.bound.expr;
+  else
+    expr_pos_t = expr_pos;
+
+  if (isl_ast_expr_get_type(expr_neg) == isl_ast_expr_bound_t)
+    expr_neg_t = expr_neg->u.bound.expr;
+  else
+    expr_neg_t = expr_neg;
+
+  if (isl_ast_expr_get_type(expr_pos_t) == isl_ast_expr_int &&
+    isl_ast_expr_get_type(expr_neg_t) != isl_ast_expr_int) {
     type = eq ? isl_ast_op_eq : isl_ast_op_le;
     expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
   } else {
     type = eq ? isl_ast_op_eq : isl_ast_op_ge;
     expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
   }
 
   isl_aff_free(aff);
for (i = 0; i < n; ++i) {
 
     aff = isl_aff_list_get_aff(list, i);
     expr_i = isl_ast_expr_from_aff(aff, build);
     if (!expr_i)
       goto error;
     expr->u.op.args[i] = expr_i;
   }
 
+  expr = isl_ast_bin_op_set_size(expr, build);
   isl_aff_list_free(list);
   return expr;
 error:
   isl_aff_list_free(list);
   isl_ast_expr_free(expr);
   return NULL;
 }
 
for (i = 0; i + 1 < data->n; ++i) {
     next = add_intermediate_piece(data, i, next);
     if (!next)
       return isl_ast_expr_free(res);
   }
 
   if (add_last_piece(data, data->n - 1, next) < 0)
     return isl_ast_expr_free(res);
 
+  if (res->type == isl_ast_expr_op)
+    res = isl_ast_bin_op_set_size(res, data->build);
   return res;
 }
 
 /* Is the domain of the current entry of "data", which is assumed
  * to contain a single subpiece, a subset of "set"?
  */
 static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,
   __isl_keep isl_set *set)

lib/External/isl/isl_ast_build_private.h

 #ifndef ISL_AST_BUILD_PRIVATE_H
 #define ISL_AST_BUILD_PRIVATE_H
 
 #include <isl/aff.h>
 #include <isl/ast.h>
 #include <isl/ast_build.h>
 #include <isl/set.h>
 #include <isl/list.h>
 #include <isl/schedule_node.h>
 
 /* An isl_ast_build represents the context in which AST is being
  * generated.  That is, it (mostly) contains information about outer
  * loops that can be used to simplify inner loops.
  *
+ * "compute_bounds", "approximate_bounds" and maximum_size are local copies
+ * of the corresponding option.
+ *
  * "domain" represents constraints on the internal schedule domain,
  * corresponding to the context of the AST generation and the constraints
  * implied by the loops that have already been generated.
  * When an isl_ast_build is first created, outside any AST generation,
  * the domain is typically a parameter set.  It is only when a AST
  * generation phase is initiated that the domain of the isl_ast_build
  * is changed to refer to the internal schedule domain.
  * The domain then lives in a space of the form

  *
  * "isolated" is the piece of the schedule domain isolated by the isolate
  * option on the current band.  This set may be NULL if we have not checked
  * for the isolate option yet.
  */
 struct isl_ast_build {
   int ref;
 
+  int compute_bounds;
+  int approximate_bounds;
+  int maximum_size;
+
   int outer_pos;
   int depth;
 
   isl_id_list *iterators;
 
   isl_set *domain;
   isl_set *generated;
   isl_set *pending;
struct isl_ast_build {
 
   isl_union_map *executed;
   int single_valued;
 
   isl_schedule_node *node;
   int n;
   enum isl_ast_loop_type *loop_type;
   isl_set *isolated;
+
+  struct isl_hash_table *cache;
 };
 
+__isl_give isl_ast_build *isl_ast_build_init_options(
+  __isl_take isl_ast_build *context);
 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
   __isl_take isl_ast_build *build);
 __isl_give isl_ast_build *isl_ast_build_increase_depth(
   __isl_take isl_ast_build *build);
 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build);
 unsigned isl_ast_build_dim(__isl_keep isl_ast_build *build,
   enum isl_dim_type type);
 __isl_give isl_space *isl_ast_build_get_space(

lib/External/isl/isl_ast_codegen.c

  * simply computes that affine expression.
  * If the list contains more than one element, then we sort it
  * using a fairly abitrary but hopefully reasonably stable order.
  */
 static __isl_give isl_ast_expr *reduce_list(enum isl_ast_op_type type,
   __isl_keep isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
 {
   int i, n;
+  isl_bool is_signed = isl_bool_false;
+  size_t bits = 0;
   isl_ctx *ctx;
   isl_ast_expr *expr;
 
   if (!list)
     return NULL;
 
   n = isl_pw_aff_list_n_pw_aff(list);
 
static __isl_give isl_ast_expr *reduce_list(enum isl_ast_op_type type,
   for (i = 0; i < n; ++i) {
     isl_ast_expr *expr_i;
 
     expr_i = isl_ast_build_expr_from_pw_aff_internal(build,
         isl_pw_aff_list_get_pw_aff(list, i));
     if (!expr_i)
       goto error;
     expr->u.op.args[i] = expr_i;
+    if (build->compute_bounds) {
+      if (expr->u.op.args[i]->type != isl_ast_expr_bound_t)
+        isl_die(isl_ast_build_get_ctx(build),
+          isl_error_internal,
+          "Unbound expression found", continue);
+      if (expr->u.op.args[i]->u.bound.is_signed && !is_signed) {
+        is_signed = 1;
+        bits++;
+      }
+      if (expr->u.op.args[i]->u.bound.size > bits)
+        bits = expr->u.op.args[i]->u.bound.size;
+    }
   }
 
   isl_pw_aff_list_free(list);
+  if (build->compute_bounds && bits > 0) {
+    expr = isl_ast_expr_bound(expr, is_signed, bits, NULL);
+  }
   return expr;
 error:
   isl_pw_aff_list_free(list);
   isl_ast_expr_free(expr);
   return NULL;
 }
 
 /* Add guards implied by the "generated constraints",
for (i = 0; i < n; ++i) {
     list = isl_pw_aff_list_set_pw_aff(list, i, pa);
   }
 
   isl_pw_aff_free(one);
 
   return list;
 }
 
+/*
+ * Set the bounds of node->u.f.iterator by calculating max(size(bound),
+ * size(bound + add_offset)).
+ */
+static void isl_ast_node_for_set_iterator_type(
+  __isl_keep isl_ast_node *node, __isl_take isl_aff *bound,
+  __isl_take isl_local_space *ls,  __isl_take isl_val *add_offset,
+  __isl_take isl_ast_build *build)
+{
+  isl_aff *constant, *pos_bound;
+  size_t bits;
+  isl_bool is_signed;
+  isl_ast_expr *org_expr = node->u.f.iterator;
+
+  constant = isl_aff_val_on_domain(ls, add_offset);
+  pos_bound = isl_aff_add(isl_aff_copy(bound), constant);
+  node->u.f.iterator = isl_ast_build_set_size(build,
+            isl_ast_expr_copy(org_expr),
+            pos_bound);
+
+  if (node->u.f.iterator->type != isl_ast_expr_bound_t) {
+    isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
+      "Unbound loop iterator found", goto out);
+  }
+  bits = node->u.f.iterator->u.bound.size;
+  is_signed = node->u.f.iterator->u.bound.is_signed;
+  isl_ast_expr_free(node->u.f.iterator);
+
+  node->u.f.iterator = isl_ast_build_set_size(build, org_expr, bound);
+  if (node->u.f.iterator->type != isl_ast_expr_bound_t) {
+    isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
+        "Unbound loop iterator found", goto out);
+  }
+
+  if (node->u.f.iterator->u.bound.size < bits) {
+    node->u.f.iterator->u.bound.size = bits;
+    node->u.f.iterator->u.bound.is_signed = is_signed;
+  }
+
+out:
+  isl_aff_free(pos_bound);
+  isl_aff_free(bound);
+  isl_ast_build_free(build);
+}
+
 /* Set the condition part of the for node graft->node in case
  * the upper bound is represented as a list of piecewise affine expressions.
  *
  * In particular, set the condition to
  *
  *  iterator <= min(list of upper bounds)
  *
  * If each of the upper bounds has a negative constant term, then
static __isl_give isl_ast_graft *set_for_cond_from_set(
 
   cond = isl_ast_build_expr_from_set_internal(build, isl_set_copy(set));
   graft->node->u.f.cond = cond;
   if (!graft->node->u.f.cond)
     return isl_ast_graft_free(graft);
   return graft;
 }
 
+__isl_give isl_ast_node_for_priv *isl_ast_node_alloc_for_priv(
+  __isl_keep isl_ctx *ctx)
+{
+  return isl_calloc_type(ctx, isl_ast_node_for_priv);
+}
+
+__isl_null isl_ast_node_for_priv *isl_ast_node_for_priv_free(
+  __isl_take isl_ast_node_for_priv *priv)
+{
+  isl_ast_build_free(priv->inner_build);
+  isl_aff_free(priv->iterator_expr);
+  free(priv);
+
+  return NULL;
+}
+
 /* Construct an isl_ast_expr for the increment (i.e., stride) of
  * the current dimension.
  */
-static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build)
+static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build,
+  __isl_keep isl_ast_node *node)
 {
   int depth;
   isl_val *v;
   isl_ctx *ctx;
+  isl_local_space *ls;
+  isl_aff *iterator_expr;
+  isl_ast_build *inner_build;
 
   if (!build)
     return NULL;
   ctx = isl_ast_build_get_ctx(build);
   depth = isl_ast_build_get_depth(build);
 
-  if (!isl_ast_build_has_stride(build, depth))
+  if (build->compute_bounds) {
+    iterator_expr = isl_aff_copy(node->u.f.priv->iterator_expr);
+    ls = isl_aff_get_domain_local_space(iterator_expr);
+    inner_build = isl_ast_build_copy(node->u.f.priv->inner_build);
+    isl_ast_node_for_priv_free(node->u.f.priv);
+  }
+
+  if (!isl_ast_build_has_stride(build, depth)) {
+    if (build->compute_bounds) {
+      v = isl_val_int_from_ui(ctx, 1);
+      isl_ast_node_for_set_iterator_type(node, iterator_expr,
+                 ls, v, inner_build);
+    }
+
     return isl_ast_expr_alloc_int_si(ctx, 1);
+  }
 
   v = isl_ast_build_get_stride(build, depth);
+
+  if (build->compute_bounds) {
+    isl_ast_node_for_set_iterator_type(node, iterator_expr, ls,
+             isl_val_copy(v), inner_build);
+  }
+
   return isl_ast_expr_from_val(v);
 }
 
 /* Should we express the loop condition as
  *
  *  iterator <= min(list of upper bounds)
  *
  * or as a conjunction of constraints?

  *  or on a set of upper bound constraints.
  */
 static __isl_give isl_ast_graft *set_for_node_expressions(
   __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *lower,
   int use_list, __isl_keep isl_pw_aff_list *upper_list,
   __isl_keep isl_set *upper_set, __isl_keep isl_ast_build *build)
 {
   isl_ast_node *node;
+  isl_ast_expr *incr;
 
   if (!graft)
     return NULL;
 
   build = isl_ast_build_copy(build);
 
   node = graft->node;
   node->u.f.init = reduce_list(isl_ast_op_max, lower, build);
-  node->u.f.inc = for_inc(build);
+  node->u.f.inc = for_inc(build, node);
 
   if (!node->u.f.init || !node->u.f.inc)
     graft = isl_ast_graft_free(graft);
 
   if (use_list)
     graft = set_for_cond_from_list(graft, upper_list, build);
   else
     graft = set_for_cond_from_set(graft, upper_set, build);
static __isl_give isl_ast_graft *refine_generic(
   return graft;
 }
 
 /* Create a for node for the current level.
  *
  * Mark the for node degenerate if "degenerate" is set.
  */
 static __isl_give isl_ast_node *create_for(__isl_keep isl_ast_build *build,
+  __isl_keep isl_basic_set* bounds,
+  __isl_keep isl_ast_build *sub_build,
   int degenerate)
 {
   int depth;
   isl_id *id;
   isl_ast_node *node;
+  isl_local_space *ls;
+  isl_aff *iterator_expr;
+  isl_val *v;
 
   if (!build)
     return NULL;
 
   depth = isl_ast_build_get_depth(build);
   id = isl_ast_build_get_iterator_id(build, depth);
   node = isl_ast_node_alloc_for(id);
+
+  if (build->compute_bounds) {
+    ls = isl_basic_set_get_local_space(bounds);
+    iterator_expr = isl_aff_var_on_domain(ls, isl_dim_out, depth);
+
+    node->u.f.priv = isl_ast_node_alloc_for_priv(
+            isl_aff_get_ctx(iterator_expr));
+    node->u.f.priv->inner_build = isl_ast_build_copy(sub_build);
+    node->u.f.priv->iterator_expr = iterator_expr;
+    if (degenerate) {
+      v = isl_val_int_from_ui(isl_aff_get_ctx(iterator_expr), 1);
+      ls = isl_basic_set_get_local_space(bounds);
+      isl_ast_node_for_set_iterator_type(node, isl_aff_copy(iterator_expr),
+                 ls, v, isl_ast_build_copy(node->u.f.priv->inner_build));
+      isl_ast_node_for_priv_free(node->u.f.priv);
+    }
+  }
+
   if (degenerate)
     node = isl_ast_node_for_mark_degenerate(node);
 
   return node;
 }
 
 /* If the ast_build_exploit_nested_bounds option is set, then return
  * the constraints enforced by all elements in "list".
if (degenerate < 0 || eliminated < 0)
     executed = isl_union_map_free(executed);
   if (!degenerate)
     bounds = isl_ast_build_compute_gist_basic_set(build, bounds);
   sub_build = isl_ast_build_set_pending_generated(sub_build,
             isl_basic_set_copy(bounds));
   if (eliminated)
     executed = plug_in_values(executed, sub_build);
   else
-    node = create_for(build, degenerate);
+    node = create_for(build, bounds, sub_build, degenerate);
 
   body_build = isl_ast_build_copy(sub_build);
   body_build = isl_ast_build_increase_depth(body_build);
   if (!eliminated)
     node = before_each_for(node, body_build);
   children = generate_next_level(executed,
             isl_ast_build_copy(body_build));
 
if (!eliminated) {
     for_build = isl_ast_build_copy(build);
     for_build = isl_ast_build_replace_pending_by_guard(for_build,
               isl_set_copy(guard));
     if (degenerate)
       graft = refine_degenerate(graft, for_build, sub_build);
     else
       graft = refine_generic(graft, bounds,
           domain, for_build);
     isl_ast_build_free(for_build);
   }
   isl_set_free(guard);
   if (!eliminated)
     graft = after_each_for(graft, body_build);
 
   isl_ast_build_free(body_build);
   isl_ast_build_free(sub_build);
   isl_ast_build_free(build);
__isl_give isl_ast_node *isl_ast_build_node_from_schedule_map(
   __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule)
 {
   isl_ast_graft_list *list;
   isl_ast_node *node;
   isl_union_map *executed;
 
   build = isl_ast_build_copy(build);
   build = isl_ast_build_set_single_valued(build, 0);
+  build = isl_ast_build_init_options(build);
   schedule = isl_union_map_coalesce(schedule);
   schedule = isl_union_map_remove_redundancies(schedule);
   executed = isl_union_map_reverse(schedule);
   list = generate_code(executed, isl_ast_build_copy(build), 0);
   node = isl_ast_node_from_graft_list(list, build);
   isl_ast_build_free(build);
 
   return node;

lib/External/isl/isl_ast_private.h

 #ifndef ISL_AST_PRIVATE_H
 #define ISL_AST_PRIVATE_H
 
 #include <isl/aff.h>
 #include <isl/ast.h>
 #include <isl/set.h>
 #include <isl/map.h>
 #include <isl/vec.h>
 #include <isl/list.h>
+#include <isl/ast_build.h>
 
 /* An expression is either an integer, an identifier or an operation
  * with zero or more arguments.
  */
 struct isl_ast_expr {
   int ref;
 
   isl_ctx *ctx;
-
   enum isl_ast_expr_type type;
 
   union {
     isl_val *v;
     isl_id *id;
     struct {
       enum isl_ast_op_type op;
       unsigned n_arg;
       isl_ast_expr **args;
     } op;
+    struct {
+      unsigned int size;
+      isl_bool is_signed;
+      isl_ast_expr *expr;
+      isl_set *condition;
+    } bound;
   } u;
 };
 
 #undef EL
 #define EL isl_ast_expr
 
 #include <isl_list_templ.h>
 
 __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i);
 __isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
   enum isl_ast_op_type op, int n_arg);
 __isl_give isl_ast_expr *isl_ast_expr_alloc_binary(enum isl_ast_op_type type,
   __isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2);
 
 #undef EL
 #define EL isl_ast_node
 
 #include <isl_list_templ.h>
 
+struct isl_ast_node_for_priv {
+    isl_aff *iterator_expr;
+    isl_ast_build *inner_build;
+};
+typedef struct isl_ast_node_for_priv isl_ast_node_for_priv;
+
 /* A node is either a block, an if, a for, a user node or a mark node.
  * "else_node" is NULL if the if node does not have an else branch.
  * "cond" and "inc" are NULL for degenerate for nodes.
  * In case of a mark node, "mark" is the mark and "node" is the marked node.
  */
 struct isl_ast_node {
   int ref;
 
union {
     } i;
     struct {
       unsigned degenerate : 1;
       isl_ast_expr *iterator;
       isl_ast_expr *init;
       isl_ast_expr *cond;
       isl_ast_expr *inc;
       isl_ast_node *body;
+      isl_ast_node_for_priv *priv;
     } f;
     struct {
       isl_ast_expr *expr;
     } e;
     struct {
       isl_id *mark;
       isl_ast_node *node;
     } m;

lib/External/isl/isl_gmp.c

uint32_t isl_gmp_hash(mpz_t v, uint32_t hash)
   unsigned char *end = data + abs_sa * sizeof(v[0]._mp_d[0]);
 
   if (sa < 0)
     isl_hash_byte(hash, 0xFF);
   for (; data < end; ++data)
     isl_hash_byte(hash, *data);
   return hash;
 }
+
+size_t isl_gmp_size_in_bits(mpz_t v, int is_signed)
+{
+  size_t bits;
+
+  if (!is_signed)
+    return mpz_sizeinbase(v, 2);
+
+  if (mpz_sgn(v) >= 0)
+    return 1 + mpz_sizeinbase(v, 2);
+
+  mpz_add_ui(v, v, 1);
+  bits = 1 + mpz_sizeinbase(v, 2);
+  mpz_sub_ui(v, v, 1);
+
+  return bits;
+}

lib/External/isl/isl_imath.c

void isl_imath_submul_ui(mp_int rop, mp_int op1, unsigned long op2)
 
   mp_int_set_uvalue(&temp, op2);
   mp_int_mul(op1, &temp, &temp);
   mp_int_sub(rop, &temp, rop);
 
   mp_int_clear(&temp);
 }
 
+size_t isl_imath_size_in_bits(mp_int val, int sign) {
+  mp_result result;
+  mpz_t tmp;
+
+  if ((result = mp_int_count_bits(val)) < 0)
+    isl_die(NULL, isl_error_invalid, "Coudln't get size", return 1);
+
+  if (MP_SIGN(val)!=0) {
+    mp_int_init(&tmp);
+    mp_int_neg(val, &tmp);
+    if (mp_int_is_pow2(&tmp)<0)
+      result++;
+    mp_int_clear(&tmp);
+  } else if (MP_SIGN(val)==0 && sign==1) {
+    result++;
+  }
+
+  return result;
+}
+
 /* Compute the division of lhs by a rhs of type unsigned long, rounding towards
  * positive infinity (Ceil).
  */
 void isl_imath_cdiv_q_ui(mp_int rop, mp_int lhs, unsigned long rhs)
 {
   mpz_t temp;
   mp_int_init(&temp);
 

lib/External/isl/isl_int_gmp.h

 #define isl_int_abs_cmp(i,j)  mpz_cmpabs(i,j)
 #define isl_int_abs_eq(i,j) (mpz_cmpabs(i,j) == 0)
 #define isl_int_abs_ne(i,j) (mpz_cmpabs(i,j) != 0)
 #define isl_int_abs_lt(i,j) (mpz_cmpabs(i,j) < 0)
 #define isl_int_abs_gt(i,j) (mpz_cmpabs(i,j) > 0)
 #define isl_int_abs_ge(i,j) (mpz_cmpabs(i,j) >= 0)
 #define isl_int_is_divisible_by(i,j)  mpz_divisible_p(i,j)
 
+
+size_t isl_gmp_size_in_bits(mpz_t v, int is_signed);
+#define isl_int_size_in_bits(v,s) isl_gmp_size_in_bits(v,s)
+
 uint32_t isl_gmp_hash(mpz_t v, uint32_t hash);
 #define isl_int_hash(v,h) isl_gmp_hash(v,h)
 
 #ifndef mp_get_memory_functions
 void mp_get_memory_functions(
     void *(**alloc_func_ptr) (size_t),
     void *(**realloc_func_ptr) (void *, size_t, size_t),
     void (**free_func_ptr) (void *, size_t));

lib/External/isl/isl_int_imath.h

 #define isl_int_is_divisible_by(i,j)  impz_divisible_p(i,j)
 
 uint32_t isl_imath_hash(mp_int v, uint32_t hash);
 #define isl_int_hash(v,h) isl_imath_hash(v,h)
 
 typedef void (*isl_int_print_mp_free_t)(void *, size_t);
 #define isl_int_free_str(s) free(s)
 
+#define isl_int_size_in_bits(v,s) isl_imath_size_in_bits(v,s)
 #endif /* ISL_INT_IMATH_H */

lib/External/isl/isl_int_sioimath.h

 #define isl_int_abs_gt(i, j)    (isl_sioimath_abs_cmp(*(i), *(j)) > 0)
 #define isl_int_abs_ge(i, j)    (isl_sioimath_abs_cmp(*(i), *(j)) >= 0)
 #define isl_int_is_divisible_by(i, j) isl_sioimath_is_divisible_by(*(i), *(j))
 
 #define isl_int_hash(v, h)    isl_sioimath_hash(*(v), h)
 #define isl_int_free_str(s)   free(s)
 #define isl_int_print(out, i, width)  isl_sioimath_print(out, *(i), width)
 
+#define isl_int_size_in_bits(v,s) isl_sioimath_size_in_bits(v,s)
+
 #endif /* ISL_INT_SIOIMATH_H */

lib/External/isl/isl_int_sioimath.c

extern void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
   isl_sioimath_src rhs);
 extern void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
   unsigned long rhs);
 extern void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
   isl_sioimath_src rhs);
 extern void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
   unsigned long rhs);
 
+extern size_t isl_imath_size_in_bits(mp_int val, int sign);
+
 /* Implements the Euclidean algorithm to compute the greatest common divisor of
  * two values in small representation.
  */
 static uint32_t isl_sioimath_smallgcd(int32_t lhs, int32_t rhs)
 {
   uint32_t dividend, divisor, remainder;
 
   dividend = labs(lhs);

 }
 
 /* Print a number to stdout. Meant for debugging.
  */
 void isl_sioimath_dump(isl_sioimath_src arg)
 {
   isl_sioimath_print(stdout, arg, 0);
 }
+
+size_t isl_sioimath_size_in_bits(isl_sioimath_ptr val, int sign) {
+  int32_t small;
+  size_t size = 1;
+
+  if (isl_sioimath_decode_small(*val, &small)) {
+    if (small >= 0) {
+      while ((small=(small>>1))!=0)
+        size++;
+      if (sign)
+        size++;
+    } else {
+      while ((small=(small>>1))!=-1)
+        size++;
+      size++;
+    }
+    return size;
+  } else {
+    return isl_imath_size_in_bits(*val, sign);
+  }
+}
 No newline at end of file

lib/External/isl/isl_options.c

ISL_ARG_BOOL(struct isl_options, ast_always_print_block, 0,
   "ast-always-print-block", 0, "print for and if bodies as a block "
   "regardless of the number of statements in the body")
 ISL_ARG_BOOL(struct isl_options, ast_print_macro_once, 0,
   "ast-print-macro-once", 0, "only print macro definitions once")
 ISL_ARG_BOOL(struct isl_options, ast_build_atomic_upper_bound, 0,
   "ast-build-atomic-upper-bound", 1, "generate atomic upper bounds")
 ISL_ARG_BOOL(struct isl_options, ast_build_prefer_pdiv, 0,
   "ast-build-prefer-pdiv", 1, "prefer pdiv operation over fdiv")
+ISL_ARG_BOOL(struct isl_options, ast_build_compute_bounds, 0,
+       "ast-build-compute-bounds", 0, "compute bounds on isl_ast_expr objects")
+ISL_ARG_BOOL(struct isl_options, ast_build_print_computed_bounds, 0,
+       "ast-build-print-computed-bounds", 1,
+       "print computed bounds on isl_ast_expr objects")
+ISL_ARG_BOOL(struct isl_options, ast_build_approximate_computed_bounds, 0,
+       "ast-build-approximate-computed-bounds",
+       0, "approximate computed bounds on isl_ast_expr objects")
+ISL_ARG_INT(struct isl_options, ast_build_maximum_native_type, 0, 0,
+      "ast-build-maximum-native-type", 0,
+      "try to keep computed bounds within this type (in bits)")
 ISL_ARG_BOOL(struct isl_options, ast_build_detect_min_max, 0,
   "ast-build-detect-min-max", 0, "detect min/max expressions")
 ISL_ARG_BOOL(struct isl_options, ast_build_exploit_nested_bounds, 0,
   "ast-build-exploit-nested-bounds", 1,
   "simplify conditions based on bounds of nested for loops")
 ISL_ARG_BOOL(struct isl_options, ast_build_group_coscheduled, 0,
   "ast-build-group-coscheduled", 0,
   "keep coscheduled domain elements together")

 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   ast_build_atomic_upper_bound)
 
 ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   ast_build_prefer_pdiv)
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   ast_build_prefer_pdiv)
 
+ISL_CTX_SET_INT_DEF(isl_options, struct isl_options, isl_options_args,
+  ast_build_maximum_native_type)
+ISL_CTX_GET_INT_DEF(isl_options, struct isl_options, isl_options_args,
+  ast_build_maximum_native_type)
+ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+    ast_build_print_computed_bounds)
+ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+    ast_build_print_computed_bounds)
+ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+  ast_build_compute_bounds)
+ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+  ast_build_compute_bounds)
+ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+  ast_build_approximate_computed_bounds)
+ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+  ast_build_approximate_computed_bounds)
 ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   ast_build_detect_min_max)
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   ast_build_detect_min_max)
 
 ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
   ast_build_exploit_nested_bounds)
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,

lib/External/isl/isl_options_private.h

struct isl_options {
   int     tile_shift_point_loops;
 
   char      *ast_iterator_type;
   int     ast_always_print_block;
   int     ast_print_macro_once;
 
   int     ast_build_atomic_upper_bound;
   int     ast_build_prefer_pdiv;
+  int     ast_build_compute_bounds;
+  int     ast_build_print_computed_bounds;
+  int     ast_build_approximate_computed_bounds;
+  int     ast_build_maximum_native_type;
   int     ast_build_detect_min_max;
   int     ast_build_exploit_nested_bounds;
   int     ast_build_group_coscheduled;
   int     ast_build_separation_bounds;
   int     ast_build_scale_strides;
   int     ast_build_allow_else;
   int     ast_build_allow_or;
 
   int     print_stats;
   unsigned long   max_operations;
 };
 
 #endif

lib/External/isl/isl_test.c

for (i = 0; i < ARRAY_SIZE(val_bin_tests); ++i) {
     if (!ok)
       isl_die(ctx, isl_error_unknown,
         "unexpected result", return -1);
   }
 
   return 0;
 }
 
+struct {
+  const char *val;
+  int sgn;
+  int size;
+} val_size_in_bits_tests[] = {
+  { "0", 0, 1 },
+  { "1", 0, 1 },
+  { "2", 0, 2 },
+  { "3", 0, 2 },
+  { "15", 0, 4 },
+  { "16", 0, 5 },
+  { "340282366920938463463374607431768211455", 0, 128 },
+  { "340282366920938463463374607431768211456", 0, 129 },
+  { "0", 1, 2 },
+  { "1", 1, 2 },
+  { "2", 1, 3 },
+  { "3", 1, 3 },
+  { "340282366920938463463374607431768211455", 1, 129 },
+  { "340282366920938463463374607431768211456", 1, 130 },
+};
+
+/* Perform some basic tests of the isl_val_size_in_bits function
+ */
+static int test_size_in_bits_val(isl_ctx *ctx)
+{
+  int i;
+  isl_val *v;
+  int size;
+
+  for (i = 0; i < ARRAY_SIZE(val_size_in_bits_tests); ++i) {
+    v = isl_val_read_from_str(ctx, val_size_in_bits_tests[i].val);
+    size = isl_val_size_in_bits(v, val_size_in_bits_tests[i].sgn);
+    isl_val_free(v);
+    if (size !=  val_size_in_bits_tests[i].size)
+      isl_die(ctx, isl_error_unknown,
+        "unexpected result", return -1);
+  }
+
+  return 0;
+}
+
 /* Perform some basic tests on isl_val objects.
  */
 static int test_val(isl_ctx *ctx)
 {
   if (test_un_val(ctx) < 0)
     return -1;
   if (test_bin_val(ctx) < 0)
     return -1;
+  if (test_size_in_bits_val(ctx) < 0)
+    return -1;
   return 0;
 }
 
 /* Sets described using existentially quantified variables that
  * can also be described without.
  */
 static const char *elimination_tests[] = {
   "{ [i,j] : 2 * [i/2] + 3 * [j/4] <= 10 and 2 i = j }",

lib/External/isl/isl_val.c

 
 /* Reduce the elements of "mv" modulo "v".
  */
 __isl_give isl_multi_val *isl_multi_val_mod_val(__isl_take isl_multi_val *mv,
   __isl_take isl_val *v)
 {
   return isl_multi_val_fn_val(mv, &isl_val_mod, v);
 }
+
+int isl_val_size_in_bits(__isl_keep isl_val *v, int is_signed)
+{
+  if (!v)
+    return 0;
+
+  if (!isl_val_is_int(v))
+    isl_die(isl_val_get_ctx(v), isl_error_invalid,
+      "expecting integral value", return 0);
+
+  return isl_int_size_in_bits(v->n, is_signed);
+}

test/Isl/Ast/simple-run-time-condition.ll

 ;     for (long j = 0; j < m; j++)
 ;         A[i+p][j+q-100] = 1.0;
 ;
 
 ; This test case is meant to verify that the run-time condition generated
 ; for the delinearization is simplified such that conditions that would not
 ; cause any code to be executed are not generated.
 
-; CHECK: if (((o >= 1 && q <= 0 && m + q >= 0) || (o <= 0 && m + q >= 100 && q <= 100)) && 0 == ((m >= 1 && n + p >= 9223372036854775809) || (o <= 0 && n >= 1 && m + q >= 9223372036854775909) || (o <= 0 && m >= 1 && n >= 1 && q <= -9223372036854775709)))
+; CHECK: if (((o >= 1 && q <= 0 && m + q >= 0) || (o <= 0 && m + q >= 100 && q <= 100)) && 0 == ((m >= 1 && n + p >= 9223372036854775809) || (o <= 0 && n >= 1 && m + q >= 9223372036854775909) || (o <= 0 && m >= 1 && n >= 1 && q <= -9223372036854775709)) && -(o <= -4611686018427387905 || o >= 4611686018427387903))
 
 ; CHECK:     if (o <= 0) {
 ; CHECK:       for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:         for (int c1 = 0; c1 < m; c1 += 1)
 ; CHECK:           Stmt_for_j_1(c0, c1);
 ; CHECK:     } else
 ; CHECK:       for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:         for (int c1 = 0; c1 < m; c1 += 1)