[Polly] Runtime alias checks

[jdoerfert]

Summary

Allow the IslExprBuilder to compare pointers

Ensure the runtime condition is always a i1 type

Allow the IslExprBuilder to build address of expressions

[Fix] Expression builder access expressions

Access expressions (e.g., A[i]) are now treated as left hand values.
Thus, the isl expression builder will create a load of A[i] instead of
a gep pointing to the address. If the gep is needed use the address of
operator.

Build and print alias groups

This change will build and print all alias groups (minimal/maximal
accesses to possible aliasing base pointers) we have to check before
we can assume an alias free environment.

Generate runtime alias checks.

This check will also annotate the IslAst with runtime alias checks.
Most imporantly it makes -polly-use-runtime-alias-checks=true save for
the isl code generator.

[jdoerfert]

Fixed offset by one bug in the maximal access (now it points to the address after the last element).

[jdoerfert]

Rebase

[grosser]

Hi Johannes,

the patch looks really good for most parts.

Two remaining issues:

• There seems to be an off by one error (< instead of <=)
• Iteration over a SmallPtrSet may cause random changes.

A comment to think about:

• I am unsure if we should use AST.add(LoadPtr, 8) or AST.add(BasePtr, INT_MAX)

And then a set of smaller comments on the patch.

include/polly/ScopInfo.h

505

As you iterate over this set I propose to use a SetVector. Otherwise, the iteration order may randomly change due to adress space randomization, different memory allocators or different operating systems.

549

a set of accesses.

(There is an 'a' too much)

558

typo: _an_ alias free

(Btw, the documentation above is very nice)

lib/Analysis/ScopDetection.cpp

201

We may want to get rid of those two conditions, but it seems OK to insert them for now as this can make the code review more incremental.

lib/Analysis/ScopInfo.cpp

72

This is a great feature. We should enable it by default. This also will allow our automatic testers to ensure no regressions slip in throughout time.

1151

This may cause an out of bound access in the last dimension. Was this intended and is this safe?

In case this is intended, I believe it would be good to add a comment that this case may happen and why it is safe. Nothing complicated, just to ensure people browsing the code see that we though about it.

1176

Very nice comment.

1186

This is interesting. When I was thinking of this, my thought was to use the base pointer and UINT64_MAX as size, you seem to use the pointer in the load/store instruction and the actual load/store value as size.

I am currently thinking about if there is a difference in terms of expressiveness/correctness. Honestly, I don't know yet. Did you think about the correct size? Is there a reason one approach might be incorrect?

1271

I am personally not a big fan of such somehow surprising line saving tricks.

1578

As mentioned earlier, it would be nice to only call this on-demand in getAliasGroups(), as users who only need to analysis part of Polly should not need to pay the cost of building alias groups. The same holds in case we want to bail out from optimizing a scop.

We have specific performance testers that ensure that -polly-scops is not getting more expensive over time. Having them not note this change would be ensuring that we did not increase compile time in the early phase of Polly.

I remember you felt very strong about not moving this piece of code over. If you still believe that way, I won't discuss this further.

lib/CodeGen/IslAst.cpp

302

This change is the reason why we suddenly get conditions such as:

if (1 == 1)

It is not of cricital importance, but you could probably get rid of them by applying the following patch to createOpBoolean:

-  assert(LHS->getType() == Builder.getInt1Ty() && "Expected i1 type");
-  assert(RHS->getType() == Builder.getInt1Ty() && "Expected i1 type"); 
+  if (LHS->getType() != Builder.getInt1Ty()) 
+    LHS = Builder.CreateIsNotNull(LHS);
+  if (RHS->getType() != Builder.getInt1Ty()) 
+    RHS = Builder.CreateIsNotNull(RHS);

This would also reduce the number of test cases that get touched by this commit, which again helps people doing post-commit review or who later look at the patch.

305

typo: group

lib/CodeGen/IslCodeGeneration.cpp

596

Not needed if you auto booleanize values in createOpBoolean()

test/Isl/Ast/alias_simple_1.ll

16

I think this should be '<=' instead of '<'.

Assuming this is:

0 1 2 3 4 5 6 7
x x x x x x x x

^A ^B

// N = 2

short A[N]
short B[N]

&A[N] => Base + (2 * sizeof(short)) = 0 + 2 * 2 = 4
&B[0] => Base + (0 * sizeof(short)) = 4 + 0 * 2 = 4

&A[N] < &B[N] is false, but indeed it should evaluate to true

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

31 ↗

(On Diff #13546)

Not needed if you auto booleanize values in createOpBoolean()

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

21 ↗

(On Diff #13546)

Not needed if you auto booleanize values in createOpBoolean()

test/Isl/CodeGen/multidim_2d_parametric_array_static_loop_bounds.ll

16 ↗

(On Diff #13546)

Not needed if you auto booleanize values in createOpBoolean()

test/Isl/CodeGen/run-time-condition-with-scev-parameters.ll

7 ↗

(On Diff #13546)

Not needed if you auto booleanize values in createOpBoolean()

test/Isl/CodeGen/scop_never_executed_runtime_check_location.ll

14 ↗

(On Diff #13546)

Not needed if you auto booleanize values in createOpBoolean()

test/ScopDetectionDiagnostics/ReportAlias-01.ll

9

For me, the test case still produces "A", "B" as output. Is there a specific reason this needs to be changed (e.g. your system gives "B", "A")?

I am asking as unpredictable output sometimes points to cases where we loop over unsorted sets, which then cause this kind of behaviour that is hard to debug and consequently better avoided.

[grosser]

I did not mention this before, but the test cases look all very nice. It is good to have proper test coverage of this feature.

[jdoerfert]

Comments

include/polly/ScopInfo.h

505

Ok.

549

Fixed.

558

Fixed. Thanks.

lib/Analysis/ScopDetection.cpp

201

In the long run we want to remove them but we cannot turn RuntimeAliasChecks on by default without them atm.

lib/Analysis/ScopInfo.cpp

72

Enabled by default in the last commit of this series.

1151

Added a sentence, just stating the possibility and that it is safe.

1176

thx.

1186

I'm sorry but I don't understand what you are saying. I also do not know why we should use UINT64_MAX except when we can't represent the real offset. However, the runtime alias checks are disabled for now in case "allow non affine" is enabled, thus we always know the exact (parametric) offset.

Could you explain your idea and the problem this approach might have in a bit more detail?

1271

Changed it.

1578

Your right, I still like the code here, but I also gave you some reasons for this.

One more (wrt. what you said about polly as analyser) is that we can provide exact information about possibly overlapping accesses. I will use this feature together with the dependency analysis in another project, both with and without generating an optimized SCoP with Polly.

lib/CodeGen/IslAst.cpp

302

Changed + removed the patch "force rtc to be i1 type".

305

fixed.

lib/CodeGen/IslCodeGeneration.cpp

596

I changed the assert to an if + createIsNotNull.

test/Isl/Ast/alias_simple_1.ll

16

If I get your example correctly we have:

short *A = ...
short *B = A + 2;

and accesses (with N=2):

A[2] and B[0]

then the alias check should say false (what it does) becasue both accesses will load the same value.

What do you think?

test/Isl/CodeGen/multidim_2d_parametric_array_static_loop_bounds.ll

16 ↗

(On Diff #13546)

As you see on the left, either a "!=" or "==" comparison is needed.

test/Isl/CodeGen/run-time-condition-with-scev-parameters.ll

7 ↗

(On Diff #13546)

As you see on the left, either a "!=" or "==" comparison is needed.

test/Isl/CodeGen/scop_never_executed_runtime_check_location.ll

14 ↗

(On Diff #13546)

As you see on the left, either a "!=" or "==" comparison is needed.

test/ScopDetectionDiagnostics/ReportAlias-01.ll

9

It doesn't now but it did say "B", "A" for a while.

I changed it back to only match "A", "B" but someone might want to take a look at this.

[grosser]

Hi Johannes,

here some feedback to your comments.

Tobias

P.S: Did you push the changed patch? I can not find it in the web interface.

lib/Analysis/ScopInfo.cpp

1151

I think it would be helpful to mention why we believe it is safe. Otherwise no-one can verify if our assumptions still hold e.g., after changes to LLVM.

1186

In the ScopDetection we use the following code to check for aliasing:

// Check if the base pointer of the memory access does alias with              
// any other pointer. This cannot be handled at the moment.                    
AliasSet &AS =                                                                 
  Context.AST.getAliasSetForPointer(BaseValue, AliasAnalysis::UnknownSize,   
                                        Inst.getMetadata(LLVMContext::MD_tbaa));

Similarly, the AST has a set of add() functions:

bool add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc.    
bool add(LoadInst *LI);                                                        
bool add(StoreInst *SI);

The LoadInst/StoreInst version of the add reason about a single load of maybe 16 bytes, whereas the first version of the add instruction allows to give a base pointer and an arbitrary offset.

The reason I implemented the alias check in the scop detection using the base pointer + an UnknownSize parameter is that I wanted to include all possible (positive?) offsets from this base pointer in the alias check.

This is similar to how we in the end construct the run-time alias check. Only checking the individual loads did not come to my mind.

Now, as I said, I don't really know what is better/more correct.

Some first thoughts are here:

When checking individual accesses I could imagine that a single base array is split into multiple alias sets:

for: int i
  S1:  A[2 i] = A[2i + 1]; 
  S2:  A[2i + 2] = A[2i - 1];

Here an alias analysis could possibly form two groups AS_1 = {A[2i], A[2i + 2]}, AS_2 = {A[2i+1], A[2i-1]},
as the even and odd accesses could be proven to not alias. Would this have any drawbacks?

When checking the baseptr + large-offset, we may have troubles to exploit the tbaa and other per-access annotations. Is this right?

In case we decide to go for the per-access checks, I wonder if we then should change the check in the scop detection as well?

1578

Just to make it clear. I agree that all the code should remain in ScopInfo. The only change I suggested was to not call buildAliasGroups() in runOnScop, but rather on-demand from getAliasGroups() (and to then use getAliasGroups() in the analysis-printer).

test/Isl/Ast/alias_simple_1.ll

16

My example extends the code in the test case by defining a specific N and a specific memory address for A and B. For this N, the test case only accesses A[0], A[1], B[0], B[1], but not A[2]. For the pointer offsets specified (short *B = A+2), this means there are no conflicting accesses. However, as you seem to agree the alias check will detect the existence of aliasing. To me this seems overly and unnecessarily conservative. Especially as it is not unlikely that two arrays are allocated right after each other.

test/Isl/CodeGen/multidim_2d_parametric_array_static_loop_bounds.ll

16 ↗

(On Diff #13546)

To clarify: The instruction is needed, but most likely the change from "!=" to "==" disappears when using CreateIsNotNull(). This reduces the set of test cases that is changed, which is by itself already a good thing.

[jdoerfert]

Comments, new version is comming up.

lib/Analysis/ScopInfo.cpp

1186

The ScopDetection implementation shouldn't matter as long as runtime alias checks are turned on.
Changing it to the way I implemented it here is a different matter for another time.

I now understood your problem partially, however I still do not know why I shouldn't use the

AST.add(Instruction *)

interface which then will sue the LoadInst and StoreInst versions. AST offers this, thus it should do the correct thing with the pointer operand. And since I add all memory instructions it also knows about all pointer operands.

The single base address problem is handled here anyway and the check is cheap.

I'm not a hundred procent sure about the TBAA information but I suspect your right. They are attached to the load/store instructions and we need the AST to see them.

I vote very strongly for the load/store version over the baseptr + unknown offset version here, in ScopDetection I do not care to much as the code is alsmost dead after this commit anyway.

1578

You can change that afterwards, we would also see how much compile time it safes us that way. I'm at the moment not sure e.g., how to mark the alias checks as computed or not.

test/Isl/Ast/alias_simple_1.ll

16

I think your right. I'll change that.

[jdoerfert]

Some fixes according to the review

[grosser]

This code is good and was committed in r218046.

include/polly/CodeGen/IslExprBuilder.h

private:
   llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr);
   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 *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);
+  llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr);
 };
 }
 
 #endif

include/polly/ScopDetection.h

 typedef std::map<const Instruction *, MemAcc *> MapInsnToMemAcc;
 typedef std::pair<const Instruction *, const SCEVAddRecExpr *> PairInsnAddRec;
 typedef std::vector<PairInsnAddRec> AFs;
 typedef std::map<const SCEVUnknown *, AFs> BaseToAFs;
 typedef std::map<const SCEVUnknown *, const SCEV *> BaseToElSize;
 
 extern bool PollyTrackFailures;
 extern bool PollyDelinearize;
+extern bool PollyUseRuntimeAliasChecks;
 
 /// @brief A function attribute which will cause Polly to skip the function
 extern llvm::StringRef PollySkipFnAttr;
 
 //===----------------------------------------------------------------------===//
 /// @brief Pass to detect the maximal static control parts (Scops) of a
 /// function.
 class ScopDetection : public FunctionPass {
class ScopDetection : public FunctionPass {
   /// @param Assert Throw an assert in verify mode or not.
   /// @param Args Argument list that gets passed to the constructor of RR.
   template <class RR, typename... Args>
   inline bool invalid(DetectionContext &Context, bool Assert,
                       Args &&... Arguments) const;
 
 public:
   static char ID;
-  explicit ScopDetection() : FunctionPass(ID) {}
+  explicit ScopDetection();
 
   /// @brief Get the RegionInfo stored in this pass.
   ///
   /// This was added to give the DOT printer easy access to this information.
   RegionInfo *getRI() const { return RI; }
 
   /// @brief Is the region is the maximum region of a Scop?
   ///

include/polly/ScopInfo.h

 struct isl_map;
 struct isl_basic_map;
 struct isl_id;
 struct isl_set;
 struct isl_union_set;
 struct isl_union_map;
 struct isl_space;
 struct isl_constraint;
+struct isl_pw_multi_aff;
 
 namespace polly {
 
 class IRAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 class TempScop;

 ///   * A set of global parameters
 ///   Those parameters are scalar integer values, which are constant during
 ///   execution.
 ///
 ///   * A context
 ///   This context contains information about the values the parameters
 ///   can take and relations between different parameters.
 class Scop {
-  //===-------------------------------------------------------------------===//
+public:
+  /// @brief Type to represent a pair of minimal/maximal access to an array.
+  using MinMaxAccessTy = std::pair<isl_pw_multi_aff *, isl_pw_multi_aff *>;
+
+  /// @brief Vector of minimal/maximal accesses to different arrays.
+  using MinMaxVectorTy = SmallVector<MinMaxAccessTy, 4>;
+
+  /// @brief Vector of minimal/maximal access vectors one for each alias group.
+  using MinMaxVectorVectorTy = SmallVector<MinMaxVectorTy *, 4>;
+
+private:
   Scop(const Scop &) LLVM_DELETED_FUNCTION;
   const Scop &operator=(const Scop &) LLVM_DELETED_FUNCTION;
 
   ScalarEvolution *SE;
 
   /// The underlying Region.
   Region &R;
 
private:
   ///
   /// When constructing a scop sometimes the exact representation of a statement
   /// or condition would be very complex, but there is a common case which is a
   /// lot simpler, but which is only valid under certain assumptions. The
   /// assumed context records the assumptions taken during the construction of
   /// this scop and that need to be code generated as a run-time test.
   isl_set *AssumedContext;
 
+  /// @brief The set of minimal/maximal accesses for each alias group.
+  ///
+  /// When building runtime alias checks we look at all memory instructions and
+  /// build so called alias groups. Each group contains a set of accesses to
+  /// different base arrays which might alias with each other. However, between
+  /// alias groups there is no aliasing possible.
+  ///
+  /// In a program with int and float pointers annotated with tbaa information
+  /// we would probably generate two alias groups, one for the int pointers and
+  /// one for the float pointers.
+  ///
+  /// During code generation we will create a runtime alias check for each alias
+  /// group to ensure the SCoP is executed in an alias free environment.
+  MinMaxVectorVectorTy MinMaxAliasGroups;
+
   /// Create the static control part with a region, max loop depth of this
   /// region and parameters used in this region.
   Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, isl_ctx *ctx);
 
   /// @brief Check if a basic block is trivial.
   ///
   /// A trivial basic block does not contain any useful calculation. Therefore,
   /// it does not need to be represented as a polyhedral statement.
private:
 
   /// Build the Scop and Statement with precalculated scop information.
   void buildScop(TempScop &TempScop, const Region &CurRegion,
                  // Loops in Scop containing CurRegion
                  SmallVectorImpl<Loop *> &NestLoops,
                  // The scattering numbers
                  SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI);
 
-  /// Helper function for printing the Scop.
+  /// @name Helper function for printing the Scop.
+  ///
+  ///{
   void printContext(raw_ostream &OS) const;
   void printStatements(raw_ostream &OS) const;
+  void printAliasAssumptions(raw_ostream &OS) const;
+  ///}
 
   friend class ScopInfo;
 
 public:
   ~Scop();
 
   ScalarEvolution *getSE() const;
 
public:
   /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
   ///          that assumptions do not change the set of statement instances
   ///          executed.
   ///
   /// @param Set A set describing relations between parameters that are assumed
   ///            to hold.
   void addAssumption(__isl_take isl_set *Set);
 
+  /// @brief Build all alias groups for this SCoP.
+  void buildAliasGroups(AliasAnalysis &AA);
+
+  /// @brief Return all alias groups for this SCoP.
+  const MinMaxVectorVectorTy &getAliasGroups() const {
+    return MinMaxAliasGroups;
+  }
+
   /// @brief Get an isl string representing the context.
   std::string getContextStr() const;
 
   /// @brief Get an isl string representing the assumed context.
   std::string getAssumedContextStr() const;
 
   /// @name Statements Iterators
   ///

include/polly/Support/GICHelper.h

 }
 
 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                      __isl_keep isl_map *Map) {
   OS << polly::stringFromIslObj(Map);
   return OS;
 }
 
+inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                                     __isl_keep isl_pw_multi_aff *PMA) {
+  OS << polly::stringFromIslObj(PMA);
+  return OS;
+}
+
 /// @brief Return @p Prefix + @p Val->getName() + @p Suffix but Isl compatible.
 std::string getIslCompatibleName(std::string Prefix, const llvm::Value *Val,
                                  std::string Suffix);
 
 } // end namespace polly
 
 #endif

lib/Analysis/ScopDetection.cpp

void DiagnosticScopFound::print(DiagnosticPrinter &DP) const {
 
   DP << FileName << ":" << EntryLine << ": Start of scop\n";
   DP << FileName << ":" << ExitLine << ": End of scop";
 }
 
 //===----------------------------------------------------------------------===//
 // ScopDetection.
 
+ScopDetection::ScopDetection() : FunctionPass(ID) {
+  if (!PollyUseRuntimeAliasChecks)
+    return;
+
+  if (PollyDelinearize) {
+    DEBUG(errs() << "WARNING: We disable runtime alias checks as "
+                    "delinearization is enabled.\n");
+    PollyUseRuntimeAliasChecks = false;
+  }
+
+  if (AllowNonAffine) {
+    DEBUG(errs() << "WARNING: We disable runtime alias checks as non affine "
+                    "accesses are enabled.\n");
+    PollyUseRuntimeAliasChecks = false;
+  }
+}
+
 template <class RR, typename... Args>
 inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert,
                                    Args &&... Arguments) const {
 
   if (!Context.Verifying) {
     RejectLog &Log = Context.Log;
     std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
 
if (AllowNonAffine) {
     Context.AffineAccesses[BasePointer].push_back({&Inst, AF});
   }
 
   // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
   // created by IndependentBlocks Pass.
   if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
     return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
 
-  if (IgnoreAliasing)
+  if (PollyUseRuntimeAliasChecks || IgnoreAliasing)
     return true;
 
   // Check if the base pointer of the memory access does alias with
   // any other pointer. This cannot be handled at the moment.
   AliasSet &AS =
       Context.AST.getAliasSetForPointer(BaseValue, AliasAnalysis::UnknownSize,
                                         Inst.getMetadata(LLVMContext::MD_tbaa));
 

lib/Analysis/ScopInfo.cpp

 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/TempScopInfo.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Support/Debug.h"
 
 #include "isl/constraint.h"
 #include "isl/set.h"
 #include "isl/map.h"
 #include "isl/union_map.h"

 // Multiplicative reductions can be disabled separately as these kind of
 // operations can overflow easily. Additive reductions and bit operations
 // are in contrast pretty stable.
 static cl::opt<bool> DisableMultiplicativeReductions(
     "polly-disable-multiplicative-reductions",
     cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
     cl::init(false), cl::cat(PollyCategory));
 
+bool polly::PollyUseRuntimeAliasChecks;
+static cl::opt<bool, true> XPollyUseRuntimeAliasChecks(
+    "polly-use-runtime-alias-checks",
+    cl::desc("Use runtime alias checks to resolve possible aliasing."),
+    cl::location(PollyUseRuntimeAliasChecks), cl::Hidden, cl::ZeroOrMore,
+    cl::init(true), cl::cat(PollyCategory));
+
 /// Translate a 'const SCEV *' expression in an isl_pw_aff.
 struct SCEVAffinator : public SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
 public:
   /// @brief Translate a 'const SCEV *' to an isl_pw_aff.
   ///
   /// @param Stmt The location at which the scalar evolution expression
   ///             is evaluated.
   /// @param Expr The expression that is translated.
void Scop::simplifyAssumedContext() {
   //
   //   we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
   //   otherwise we would access out of bound data. Now, knowing that code is
   //   only executed for the case m >= 0, it is sufficient to assume p >= 0.
   AssumedContext =
       isl_set_gist_params(AssumedContext, isl_union_set_params(getDomains()));
 }
 
+/// @brief Add the minimal/maximal access in @p Set to @p User.
+static int buildMinMaxAccess(__isl_take isl_set *Set, void *User) {
+  Scop::MinMaxVectorTy *MinMaxAccesses = (Scop::MinMaxVectorTy *)User;
+  isl_pw_multi_aff *MinPMA, *MaxPMA;
+  isl_pw_aff *LastDimAff;
+  isl_aff *OneAff;
+  unsigned Pos;
+
+  MinPMA = isl_set_lexmin_pw_multi_aff(isl_set_copy(Set));
+  MaxPMA = isl_set_lexmax_pw_multi_aff(isl_set_copy(Set));
+
+  // Adjust the last dimension of the maximal access by one as we want to
+  // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
+  // we test during code generation might now point after the end of the
+  // allocated array but we will never dereference it anyway.
+  assert(isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) &&
+         "Assumed at least one output dimension");
+  Pos = isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) - 1;
+  LastDimAff = isl_pw_multi_aff_get_pw_aff(MaxPMA, Pos);
+  OneAff = isl_aff_zero_on_domain(
+      isl_local_space_from_space(isl_pw_aff_get_domain_space(LastDimAff)));
+  OneAff = isl_aff_add_constant_si(OneAff, 1);
+  LastDimAff = isl_pw_aff_add(LastDimAff, isl_pw_aff_from_aff(OneAff));
+  MaxPMA = isl_pw_multi_aff_set_pw_aff(MaxPMA, Pos, LastDimAff);
+
+  MinMaxAccesses->push_back(std::make_pair(MinPMA, MaxPMA));
+
+  isl_set_free(Set);
+  return 0;
+}
+
+void Scop::buildAliasGroups(AliasAnalysis &AA) {
+  // To create sound alias checks we perform the following steps:
+  //   o) Use the alias analysis and an alias set tracker to build alias sets
+  //      for all memory accesses inside the SCoP.
+  //   o) For each alias set we then map the aliasing pointers back to the
+  //      memory accesses we know, thus obtain groups of memory accesses which
+  //      might alias.
+  //   o) For each group with more then one base pointer we then compute minimal
+  //      and maximal accesses to each array in this group.
+  using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
+
+  AliasSetTracker AST(AA);
+
+  DenseMap<Value *, MemoryAccess *> PtrToAcc;
+  for (ScopStmt *Stmt : *this) {
+    for (MemoryAccess *MA : *Stmt) {
+      if (MA->isScalar())
+        continue;
+      Instruction *Acc = MA->getAccessInstruction();
+      PtrToAcc[getPointerOperand(*Acc)] = MA;
+      AST.add(Acc);
+    }
+  }
+
+  SmallVector<AliasGroupTy, 4> AliasGroups;
+  for (AliasSet &AS : AST) {
+    if (AS.isMustAlias())
+      continue;
+    AliasGroupTy AG;
+    for (auto PR : AS)
+      AG.push_back(PtrToAcc[PR.getValue()]);
+    assert(AG.size() > 1 &&
+           "Alias groups should contain at least two accesses");
+    AliasGroups.push_back(std::move(AG));
+  }
+
+  SmallPtrSet<const Value *, 4> BaseValues;
+  for (auto I = AliasGroups.begin(); I != AliasGroups.end();) {
+    BaseValues.clear();
+    for (MemoryAccess *MA : *I)
+      BaseValues.insert(MA->getBaseAddr());
+    if (BaseValues.size() > 1)
+      I++;
+    else
+      I = AliasGroups.erase(I);
+  }
+
+  for (AliasGroupTy &AG : AliasGroups) {
+    MinMaxVectorTy *MinMaxAccesses = new MinMaxVectorTy();
+    MinMaxAccesses->reserve(AG.size());
+
+    isl_union_map *Accesses = isl_union_map_empty(getParamSpace());
+    for (MemoryAccess *MA : AG)
+      Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation());
+    Accesses = isl_union_map_intersect_domain(Accesses, getDomains());
+
+    isl_union_set *Locations = isl_union_map_range(Accesses);
+    Locations = isl_union_set_intersect_params(Locations, getAssumedContext());
+    Locations = isl_union_set_coalesce(Locations);
+    Locations = isl_union_set_detect_equalities(Locations);
+    isl_union_set_foreach_set(Locations, buildMinMaxAccess, MinMaxAccesses);
+    isl_union_set_free(Locations);
+
+    MinMaxAliasGroups.push_back(MinMaxAccesses);
+  }
+}
+
 Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution,
            isl_ctx *Context)
     : SE(&ScalarEvolution), R(tempScop.getMaxRegion()),
       MaxLoopDepth(tempScop.getMaxLoopDepth()) {
   IslCtx = Context;
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;

 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
 
   // Free the statements;
   for (ScopStmt *Stmt : *this)
     delete Stmt;
+
+  // Free the alias groups
+  for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
+    for (MinMaxAccessTy &MMA : *MinMaxAccesses) {
+      isl_pw_multi_aff_free(MMA.first);
+      isl_pw_multi_aff_free(MMA.second);
+    }
+    delete MinMaxAccesses;
+  }
 }
 
 std::string Scop::getContextStr() const { return stringFromIslObj(Context); }
 std::string Scop::getAssumedContextStr() const {
   return stringFromIslObj(AssumedContext);
 }
 
 std::string Scop::getNameStr() const {
void Scop::printContext(raw_ostream &OS) const {
   OS.indent(4) << getAssumedContextStr() << "\n";
 
   for (const SCEV *Parameter : Parameters) {
     int Dim = ParameterIds.find(Parameter)->second;
     OS.indent(4) << "p" << Dim << ": " << *Parameter << "\n";
   }
 }
 
+void Scop::printAliasAssumptions(raw_ostream &OS) const {
+  OS.indent(4) << "Alias Groups (" << MinMaxAliasGroups.size() << "):\n";
+  if (MinMaxAliasGroups.empty()) {
+    OS.indent(8) << "n/a\n";
+    return;
+  }
+  for (MinMaxVectorTy *MinMaxAccesses : MinMaxAliasGroups) {
+    OS.indent(8) << "[[";
+    for (MinMaxAccessTy &MinMacAccess : *MinMaxAccesses)
+      OS << " <" << MinMacAccess.first << ", " << MinMacAccess.second << ">";
+    OS << " ]]\n";
+  }
+}
+
 void Scop::printStatements(raw_ostream &OS) const {
   OS << "Statements {\n";
 
   for (ScopStmt *Stmt : *this)
     OS.indent(4) << *Stmt;
 
   OS.indent(4) << "}\n";
 }
 
 void Scop::print(raw_ostream &OS) const {
   OS.indent(4) << "Function: " << getRegion().getEntry()->getParent()->getName()
                << "\n";
   OS.indent(4) << "Region: " << getNameStr() << "\n";
   printContext(OS.indent(4));
+  printAliasAssumptions(OS);
   printStatements(OS.indent(4));
 }
 
 void Scop::dump() const { print(dbgs()); }
 
 isl_ctx *Scop::getIslCtx() const { return IslCtx; }
 
 __isl_give isl_union_set *Scop::getDomains() {
ScopInfo::~ScopInfo() {
   isl_ctx_free(ctx);
 }
 
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfo>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<ScalarEvolution>();
   AU.addRequired<TempScopInfo>();
+  AU.addRequired<AliasAnalysis>();
   AU.setPreservesAll();
 }
 
 bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
   LoopInfo &LI = getAnalysis<LoopInfo>();
+  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
   ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
 
   TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop(R);
 
   // This region is no Scop.
   if (!tempScop) {
     scop = 0;
     return false;
   }
 
   // Statistics.
   ++ScopFound;
   if (tempScop->getMaxLoopDepth() > 0)
     ++RichScopFound;
 
   scop = new Scop(*tempScop, LI, SE, ctx);
 
+  if (PollyUseRuntimeAliasChecks)
+    scop->buildAliasGroups(AA);
+
   return false;
 }
 
 char ScopInfo::ID = 0;
 
 Pass *polly::createScopInfoPass() { return new ScopInfo(); }
 
 INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",
                       "Polly - Create polyhedral description of Scops", false,
                       false);
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
 INITIALIZE_PASS_DEPENDENCY(LoopInfo);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
 INITIALIZE_PASS_DEPENDENCY(TempScopInfo);
 INITIALIZE_PASS_END(ScopInfo, "polly-scops",
                     "Polly - Create polyhedral description of Scops", false,
                     false)

lib/CodeGen/BlockGenerators.cpp

ScheduleU = isl_union_map_intersect_domain(
       ScheduleU, isl_union_set_from_set(MA.getStatement()->getDomain()));
   Schedule = isl_map_from_union_map(ScheduleU);
 
   PWSchedule = isl_pw_multi_aff_from_map(isl_map_reverse(Schedule));
   PWAccRel = isl_pw_multi_aff_from_map(AccRel);
   PWAccRel = isl_pw_multi_aff_pullback_pw_multi_aff(PWAccRel, PWSchedule);
 
   Expr = isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
+  Expr = isl_ast_expr_address_of(Expr);
 
   return ExprBuilder->create(Expr);
 }
 
 Value *BlockGenerator::generateLocationAccessed(const Instruction *Inst,
                                                 const Value *Pointer,
                                                 ValueMapT &BBMap,
                                                 ValueMapT &GlobalMap,

lib/CodeGen/IslAst.cpp

void IslAst::buildRunCondition(__isl_keep isl_ast_build *Build) {
 
   PwOne = isl_pw_aff_intersect_domain(PwOne, S->getAssumedContext());
   PwZero = isl_pw_aff_intersect_domain(
       PwZero, isl_set_complement(S->getAssumedContext()));
 
   isl_pw_aff *Cond = isl_pw_aff_union_max(PwOne, PwZero);
 
   RunCondition = isl_ast_build_expr_from_pw_aff(Build, Cond);
+
+  // Create the alias checks from the minimal/maximal accesses in each alias
+  // group. This operation is by construction quadratic in the number of
+  // elements in each alias group.
+  isl_ast_expr *NonAliasGroup, *MinExpr, *MaxExpr;
+  for (const Scop::MinMaxVectorTy *MinMaxAccesses : S->getAliasGroups()) {
+    auto AccEnd = MinMaxAccesses->end();
+    for (auto AccIt0 = MinMaxAccesses->begin(); AccIt0 != AccEnd; ++AccIt0) {
+      for (auto AccIt1 = AccIt0 + 1; AccIt1 != AccEnd; ++AccIt1) {
+        MinExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt0->first)));
+        MaxExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt1->second)));
+        NonAliasGroup = isl_ast_expr_le(MaxExpr, MinExpr);
+        MinExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt1->first)));
+        MaxExpr =
+            isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
+                Build, isl_pw_multi_aff_copy(AccIt0->second)));
+        NonAliasGroup =
+            isl_ast_expr_or(NonAliasGroup, isl_ast_expr_le(MaxExpr, MinExpr));
+        RunCondition = isl_ast_expr_and(RunCondition, NonAliasGroup);
+      }
+    }
+  }
 }
 
 IslAst::IslAst(Scop *Scop, Dependences &D) : S(Scop) {
   isl_ctx *Ctx = S->getIslCtx();
   isl_options_set_ast_build_atomic_upper_bound(Ctx, true);
   isl_ast_build *Build;
   AstBuildUserInfo BuildInfo;
 

lib/CodeGen/IslCodeGeneration.cpp

public:
   ///
   /// Build the condition that evaluates at run-time to true iff all
   /// assumptions taken for the SCoP hold, and to false otherwise.
   ///
   /// @return A value evaluating to true/false if execution is save/unsafe.
   Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
     Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
     Value *RTC = ExprBuilder.create(AI->getRunCondition());
-    return Builder.CreateIsNotNull(RTC);
+    if (!RTC->getType()->isIntegerTy(1))
+      RTC = Builder.CreateIsNotNull(RTC);
+    return RTC;
   }
 
   bool runOnScop(Scop &S) {
     LI = &getAnalysis<LoopInfo>();
     AI = &getAnalysis<IslAstInfo>();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     SE = &getAnalysis<ScalarEvolution>();
 

lib/CodeGen/IslExprBuilder.cpp

Value *IslExprBuilder::createOpNAry(__isl_take isl_ast_expr *Expr) {
   // TODO: We can truncate the result, if it fits into a smaller type. This can
   // help in cases where we have larger operands (e.g. i67) but the result is
   // known to fit into i64. Without the truncation, the larger i67 type may
   // force all subsequent operations to be performed on a non-native type.
   isl_ast_expr_free(Expr);
   return V;
 }
 
-Value *IslExprBuilder::createOpAccess(isl_ast_expr *Expr) {
+Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
          "isl ast expression not of type isl_ast_op");
   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_access &&
          "not an access isl ast expression");
   assert(isl_ast_expr_get_op_n_arg(Expr) >= 2 &&
          "We need at least two operands to create a member access.");
 
   // TODO: Support for multi-dimensional array.
assert((PtrElTy->isIntOrIntVectorTy() || PtrElTy->isFPOrFPVectorTy()) &&
          "generation.");
 
   Access = Builder.CreateGEP(Base, Indices, "polly.access." + Base->getName());
 
   isl_ast_expr_free(Expr);
   return Access;
 }
 
+Value *IslExprBuilder::createOpAccess(isl_ast_expr *Expr) {
+  Value *Addr = createAccessAddress(Expr);
+  assert(Addr && "Could not create op access address");
+  return Builder.CreateLoad(Addr, Addr->getName() + ".load");
+}
+
 Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
   Value *LHS, *RHS, *Res;
   Type *MaxType;
   isl_ast_op_type OpType;
 
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
          "isl ast expression not of type isl_ast_op");
   assert(isl_ast_expr_get_op_n_arg(Expr) == 2 &&
Value *IslExprBuilder::createOpICmp(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
          "Expected an isl_ast_expr_op expression");
 
   Value *LHS, *RHS, *Res;
 
   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 
+  bool IsPtrType = LHS->getType()->isPointerTy();
+  assert((!IsPtrType || RHS->getType()->isPointerTy()) &&
+         "Both ICmp operators should be pointer types or none of them");
+
+  if (!IsPtrType) {
     Type *MaxType = LHS->getType();
     MaxType = getWidestType(MaxType, RHS->getType());
 
     if (MaxType != RHS->getType())
       RHS = Builder.CreateSExt(RHS, MaxType);
 
     if (MaxType != LHS->getType())
       LHS = Builder.CreateSExt(LHS, MaxType);
-
-  switch (isl_ast_expr_get_op_type(Expr)) {
-  default:
-    llvm_unreachable("Unsupported ICmp isl ast expression");
-  case isl_ast_op_eq:
-    Res = Builder.CreateICmpEQ(LHS, RHS);
-    break;
-  case isl_ast_op_le:
-    Res = Builder.CreateICmpSLE(LHS, RHS);
-    break;
-  case isl_ast_op_lt:
-    Res = Builder.CreateICmpSLT(LHS, RHS);
-    break;
-  case isl_ast_op_ge:
-    Res = Builder.CreateICmpSGE(LHS, RHS);
-    break;
-  case isl_ast_op_gt:
-    Res = Builder.CreateICmpSGT(LHS, RHS);
-    break;
   }
 
+  isl_ast_op_type OpType = isl_ast_expr_get_op_type(Expr);
+  assert(OpType >= isl_ast_op_eq && OpType <= isl_ast_op_gt &&
+         "Unsupported ICmp isl ast expression");
+  assert(isl_ast_op_eq + 4 == isl_ast_op_gt &&
+         "Isl ast op type interface changed");
+
+  CmpInst::Predicate Predicates[5][2] = {
+      {CmpInst::ICMP_EQ, CmpInst::ICMP_EQ},
+      {CmpInst::ICMP_SLE, CmpInst::ICMP_ULE},
+      {CmpInst::ICMP_SLT, CmpInst::ICMP_ULT},
+      {CmpInst::ICMP_SGE, CmpInst::ICMP_UGE},
+      {CmpInst::ICMP_SGT, CmpInst::ICMP_UGT},
+  };
+
+  Res = Builder.CreateICmp(Predicates[OpType - isl_ast_op_eq][IsPtrType], LHS,
+                           RHS);
+
   isl_ast_expr_free(Expr);
   return Res;
 }
 
 Value *IslExprBuilder::createOpBoolean(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
          "Expected an isl_ast_expr_op expression");
 
Value *IslExprBuilder::createOpBoolean(__isl_take isl_ast_expr *Expr) {
   // to go for bitwise operations is, that we assume the reduced control flow
   // will outweight the overhead introduced by evaluating unneeded expressions.
   // The isl code generation currently does not take advantage of the fact that
   // the expression after an '||' or '&&' is in some cases not evaluated.
   // Evaluating it anyways does not cause any undefined behaviour.
   //
   // TODO: Document in isl itself, that the unconditionally evaluating the
   // second part of '||' or '&&' expressions is safe.
-  assert(LHS->getType() == Builder.getInt1Ty() && "Expected i1 type");
-  assert(RHS->getType() == Builder.getInt1Ty() && "Expected i1 type");
+  if (!LHS->getType()->isIntegerTy(1))
+    LHS = Builder.CreateIsNotNull(LHS);
+  if (!RHS->getType()->isIntegerTy(1))
+    RHS = Builder.CreateIsNotNull(RHS);
 
   switch (OpType) {
   default:
     llvm_unreachable("Unsupported boolean expression");
   case isl_ast_op_and:
     Res = Builder.CreateAnd(LHS, RHS);
     break;
   case isl_ast_op_or:
Value *IslExprBuilder::createOp(__isl_take isl_ast_expr *Expr) {
   case isl_ast_op_or:
     return createOpBoolean(Expr);
   case isl_ast_op_eq:
   case isl_ast_op_le:
   case isl_ast_op_lt:
   case isl_ast_op_ge:
   case isl_ast_op_gt:
     return createOpICmp(Expr);
+  case isl_ast_op_address_of:
+    return createOpAddressOf(Expr);
   }
 
   llvm_unreachable("Unsupported isl_ast_expr_op kind.");
 }
 
+Value *IslExprBuilder::createOpAddressOf(__isl_take isl_ast_expr *Expr) {
+  assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
+         "Expected an isl_ast_expr_op expression.");
+  assert(isl_ast_expr_get_op_n_arg(Expr) == 1 && "Address of should be unary.");
+
+  isl_ast_expr *Op = isl_ast_expr_get_op_arg(Expr, 0);
+  assert(isl_ast_expr_get_type(Op) == isl_ast_expr_op &&
+         "Expected address of operator to be an isl_ast_expr_op expression.");
+  assert(isl_ast_expr_get_op_type(Op) == isl_ast_op_access &&
+         "Expected address of operator to be an access expression.");
+
+  Value *V = createAccessAddress(Op);
+
+  isl_ast_expr_free(Expr);
+
+  return V;
+}
+
 Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_id &&
          "Expression not of type isl_ast_expr_ident");
 
   isl_id *Id;
   Value *V;
 
   Id = isl_ast_expr_get_id(Expr);

test/Isl/Ast/alias_simple_1.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze < %s | FileCheck %s --check-prefix=NOAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -basicaa < %s | FileCheck %s --check-prefix=BASI
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -tbaa < %s | FileCheck %s --check-prefix=TBAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -scev-aa < %s | FileCheck %s --check-prefix=SCEV
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -globalsmodref-aa < %s | FileCheck %s --check-prefix=GLOB
+;
+;    int A[1024];
+;
+;
+;    void jd(float *B, int N) {
+;      for (int i = 0; i < N; i++)
+;        A[i] = B[i];
+;    }
+;
+; NOAA: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; BASI: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; TBAA: if (1)
+; SCEV: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; GLOB: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@A = common global [1024 x i32] zeroinitializer, align 16
+
+define void @jd(float* nocapture readonly %B, i32 %N) {
+entry:
+  %cmp6 = icmp sgt i32 %N, 0
+  br i1 %cmp6, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds float* %B, i64 %indvars.iv
+  %tmp = load float* %arrayidx, align 4, !tbaa !1
+  %conv = fptosi float %tmp to i32
+  %arrayidx2 = getelementptr inbounds [1024 x i32]* @A, i64 0, i64 %indvars.iv
+  store i32 %conv, i32* %arrayidx2, align 4, !tbaa !5
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv1 = trunc i64 %indvars.iv.next to i32
+  %exitcond2 = icmp eq i32 %lftr.wideiv1, %N
+  br i1 %exitcond2, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}
+
+!0 = metadata !{metadata !""}
+!1 = metadata !{metadata !2, metadata !2, i64 0}
+!2 = metadata !{metadata !"float", metadata !3, i64 0}
+!3 = metadata !{metadata !"omnipotent char", metadata !4, i64 0}
+!4 = metadata !{metadata !"Simple C/C++ TBAA"}
+!5 = metadata !{metadata !6, metadata !6, i64 0}
+!6 = metadata !{metadata !"int", metadata !3, i64 0}

test/Isl/Ast/alias_simple_2.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze < %s | FileCheck %s --check-prefix=NOAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -basicaa < %s | FileCheck %s --check-prefix=BASI
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -tbaa < %s | FileCheck %s --check-prefix=TBAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -scev-aa < %s | FileCheck %s --check-prefix=SCEV
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -globalsmodref-aa < %s | FileCheck %s --check-prefix=GLOB
+;
+;    int A[1024], B[1024];
+;
+;
+;    void jd(int N) {
+;      for (int i = 0; i < N; i++)
+;        A[i] = B[i];
+;    }
+;
+; NOAA: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; BASI: if (1)
+; TBAA: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; SCEV: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; GLOB: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@A = common global [1024 x i32] zeroinitializer, align 16
+@B = common global [1024 x i32] zeroinitializer, align 16
+
+define void @jd(i32 %N) {
+entry:
+  %cmp6 = icmp sgt i32 %N, 0
+  br i1 %cmp6, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds  [1024 x i32]* @B, i64 0, i64 %indvars.iv
+  %tmp = load i32* %arrayidx, align 4, !tbaa !5
+  %arrayidx2 = getelementptr inbounds [1024 x i32]* @A, i64 0, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx2, align 4, !tbaa !5
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv1 = trunc i64 %indvars.iv.next to i32
+  %exitcond2 = icmp eq i32 %lftr.wideiv1, %N
+  br i1 %exitcond2, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}
+
+!0 = metadata !{metadata !""}
+!1 = metadata !{metadata !2, metadata !2, i64 0}
+!2 = metadata !{metadata !"float", metadata !3, i64 0}
+!3 = metadata !{metadata !"omnipotent char", metadata !4, i64 0}
+!4 = metadata !{metadata !"Simple C/C++ TBAA"}
+!5 = metadata !{metadata !6, metadata !6, i64 0}
+!6 = metadata !{metadata !"int", metadata !3, i64 0}

test/Isl/Ast/alias_simple_3.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze < %s | FileCheck %s --check-prefix=NOAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -basicaa < %s | FileCheck %s --check-prefix=BASI
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -tbaa < %s | FileCheck %s --check-prefix=TBAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -scev-aa < %s | FileCheck %s --check-prefix=SCEV
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze -globalsmodref-aa < %s | FileCheck %s --check-prefix=GLOB
+;
+;    int A[1024];
+;    float B[1024];
+;
+;    void jd(int N) {
+;      for (int i = 0; i < N; i++)
+;        A[i] = B[i];
+;    }
+;
+; NOAA: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; BASI: if (1)
+; TBAA: if (1)
+; SCEV: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+; GLOB: if (1 && (&MemRef_A[N] <= &MemRef_B[0] || &MemRef_B[N] <= &MemRef_A[0]))
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@A = common global [1024 x i32] zeroinitializer, align 16
+@B = common global [1024 x float] zeroinitializer, align 16
+
+define void @jd(i32 %N) {
+entry:
+  %cmp6 = icmp sgt i32 %N, 0
+  br i1 %cmp6, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds  [1024 x float]* @B, i64 0, i64 %indvars.iv
+  %tmp = load float* %arrayidx, align 4, !tbaa !1
+  %conv = fptosi float %tmp to i32
+  %arrayidx2 = getelementptr inbounds [1024 x i32]* @A, i64 0, i64 %indvars.iv
+  store i32 %conv, i32* %arrayidx2, align 4, !tbaa !5
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv1 = trunc i64 %indvars.iv.next to i32
+  %exitcond2 = icmp eq i32 %lftr.wideiv1, %N
+  br i1 %exitcond2, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}
+
+!0 = metadata !{metadata !""}
+!1 = metadata !{metadata !2, metadata !2, i64 0}
+!2 = metadata !{metadata !"float", metadata !3, i64 0}
+!3 = metadata !{metadata !"omnipotent char", metadata !4, i64 0}
+!4 = metadata !{metadata !"Simple C/C++ TBAA"}
+!5 = metadata !{metadata !6, metadata !6, i64 0}
+!6 = metadata !{metadata !"int", metadata !3, i64 0}

test/Isl/Ast/aliasing_multiple_alias_groups.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-ast -analyze          < %s | FileCheck %s --check-prefix=NOAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-ast -analyze -tbaa    < %s | FileCheck %s --check-prefix=TBAA
+;
+;    void jd(int *Int0, int *Int1, float *Float0, float *Float1) {
+;      for (int i = 0; i < 1024; i++) {
+;        Int0[i] = Int1[i];
+;        Float0[i] = Float1[i];
+;      }
+;    }
+;
+; NOAA:      if (1 && (
+; NOAA-DAG:    &MemRef_Float0[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Float0[0]
+; NOAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Float1[0]
+; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Int0[0] || &MemRef_Int0[1024] <= &MemRef_Int1[0]
+; NOAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Float1[0]
+; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Int1[0]
+; NOAA-DAG:    &MemRef_Int1[1024] <= &MemRef_Float1[0] || &MemRef_Float1[1024] <= &MemRef_Int1[0]
+; NOAA:      ))
+;
+; TBAA:      if (1 && (
+; TBAA-DAG:    &MemRef_Int0[1024] <= &MemRef_Int1[0] || &MemRef_Int1[1024] <= &MemRef_Int0[0]
+; TBAA-DAG:    &MemRef_Float1[1024] <= &MemRef_Float0[0] || &MemRef_Float0[1024] <= &MemRef_Float1[0]
+; TBAA:      ))
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* nocapture %Int0, i32* nocapture readonly %Int1, float* nocapture %Float0, float* nocapture readonly %Float1) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32* %Int1, i64 %indvars.iv
+  %tmp = load i32* %arrayidx, align 4, !tbaa !0
+  %arrayidx2 = getelementptr inbounds i32* %Int0, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx2, align 4, !tbaa !0
+  %arrayidx4 = getelementptr inbounds float* %Float1, i64 %indvars.iv
+  %tmp1 = load float* %arrayidx4, align 4, !tbaa !4
+  %arrayidx6 = getelementptr inbounds float* %Float0, i64 %indvars.iv
+  store float %tmp1, float* %arrayidx6, align 4, !tbaa !4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+!0 = metadata !{metadata !1, metadata !1, i64 0}
+!1 = metadata !{metadata !"int", metadata !2, i64 0}
+!2 = metadata !{metadata !"omnipotent char", metadata !3, i64 0}
+!3 = metadata !{metadata !"Simple C/C++ TBAA"}
+!4 = metadata !{metadata !5, metadata !5, i64 0}
+!5 = metadata !{metadata !"float", metadata !2, i64 0}

test/Isl/Ast/aliasing_parametric_simple_1.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze %s | FileCheck %s
+;
+;    void jd(int *A, int *B, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[c];
+;    }
+;
+; CHECK: if (1 && (&MemRef_A[1024] <= &MemRef_B[c] || &MemRef_B[c + 1] <= &MemRef_A[0]))
+; CHECK:     for (int c1 = 0; c1 <= 1023; c1 += 1)
+; CHECK:       Stmt_for_body(c1);
+; CHECK: else
+; CHECK:     /* original code */
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %idxprom = sext i32 %c to i64
+  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/Isl/Ast/aliasing_parametric_simple_2.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks -polly-ast -analyze < %s | FileCheck %s
+;
+;    void jd(int *A, int *B, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[c - 10] + B[5];
+;    }
+;
+; CHECK: if (1 && (&MemRef_A[1024] <= &MemRef_B[c >= 15 ? 5 : c - 10] || &MemRef_B[c <= 15 ? 6 : c - 9] <= &MemRef_A[0]))
+; CHECK:     for (int c1 = 0; c1 <= 1023; c1 += 1)
+; CHECK:       Stmt_for_body(c1);
+; CHECK: else
+; CHECK:    /* original code */
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %sub = add nsw i32 %c, -10
+  %idxprom = sext i32 %sub to i64
+  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32* %B, i64 5
+  %tmp1 = load i32* %arrayidx1, align 4
+  %add = add nsw i32 %tmp, %tmp1
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/Isl/CodeGen/MemAccess/codegen_simple_float.ll

+;RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-codegen-isl -instnamer < %s -S | FileCheck %s
+;
+;float A[100];
+;
+;int codegen_simple () {
+;  for (int i = 0; i < 12; i++)
+;    A[13] = A[i] + A[i-1];
+;
+;  return 0;
+;}
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32"
+
+@A = common global [100 x float] zeroinitializer, align 4
+
+define i32 @codegen_simple() nounwind {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %tmp1 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %tmp = add i32 %tmp1, -1
+  %arrayidx4 = getelementptr [100 x float]* @A, i32 0, i32 %tmp
+  %arrayidx = getelementptr [100 x float]* @A, i32 0, i32 %tmp1
+  %exitcond = icmp ne i32 %tmp1, 12
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp2 = load float* %arrayidx, align 4
+  %tmp5 = load float* %arrayidx4, align 4
+  %add = fadd float %tmp2, %tmp5
+  store float %add, float* getelementptr inbounds ([100 x float]* @A, i32 0, i32 13), align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %tmp1, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 0
+}
+; CHECK: load float* getelementptr inbounds ([100 x float]* @A, i64 0, i64 0)

test/Isl/CodeGen/MemAccess/codegen_simple_md_float.ll

+;RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed+withconst -polly-codegen-isl < %s -S | FileCheck -check-prefix=WITHCONST %s
+;RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed+withoutconst -polly-codegen-isl < %s -S | FileCheck -check-prefix=WITHOUTCONST %s
+;RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed+withconst -polly-codegen-isl -polly-codegen-scev < %s -S | FileCheck -check-prefix=WITHCONST %s
+;RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed+withoutconst -polly-codegen-isl -polly-codegen-scev < %s -S | FileCheck -check-prefix=WITHOUTCONST %s
+;
+;float A[1040];
+;
+;int codegen_simple_md() {
+;  for (int i = 0; i < 32; ++i)
+;    for (int j = 0; j < 32; ++j)
+;      A[32*i+j] = 100;
+;}
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
+
+@A = common global [1040 x float] zeroinitializer, align 4
+
+define void @codegen_simple_md() nounwind {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc4, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc5, %for.inc4 ]
+  %exitcond1 = icmp ne i32 %i.0, 32
+  br i1 %exitcond1, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, 32
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %mul = shl nsw i32 %i.0, 5
+  %add = add nsw i32 %mul, %j.0
+  %arrayidx = getelementptr inbounds [1040 x float]* @A, i32 0, i32 %add
+  store float 100.0, float* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %inc5 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret void
+}
+
+; WITHCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
+; WITHCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
+; WITHCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
+; WITHCONST:  %[[SUM2:[._a-zA-Z0-9]+]] = add nsw i64 %[[SUM1]], 5
+; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr [1040 x float]* @A, i64 0, i64 %[[SUM2]]
+; WITHCONST:  store float 1.000000e+02, float* %[[ACC]]
+
+; WITHOUTCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHOUTCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHOUTCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
+; WITHOUTCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
+; WITHOUTCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
+; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr [1040 x float]* @A, i64 0, i64 %[[SUM1]]
+; WITHOUTCONST:  store float 1.000000e+02, float* %[[ACC]]

test/Isl/CodeGen/MemAccess/simple___%for.cond---%for.end14.jscop

+{
+   "context" : "{  :  }",
+   "name" : "for.cond => for.end14",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body[i0] -> MemRef_A[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_body[i0] : i0 >= 0 and i0 <= 11 }",
+         "name" : "Stmt_for_body",
+         "schedule" : "{ Stmt_for_body[i0] -> scattering[0, i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body7[i0] -> MemRef_B[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_body7[i0] : i0 >= 0 and i0 <= 11 }",
+         "name" : "Stmt_for_body7",
+         "schedule" : "{ Stmt_for_body7[i0] -> scattering[0, i0, 0] }"
+      }
+   ]
+}

test/Isl/CodeGen/MemAccess/simple___%for.cond---%for.end14.jscop.transformed

+{
+   "context" : "{  :  }",
+   "name" : "for.cond => for.end14",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_body[i0] : i0 >= 0 and i0 <= 11 }",
+         "name" : "Stmt_for_body",
+         "schedule" : "{ Stmt_for_body[i0] -> scattering[0, i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body7[i0] -> MemRef_B[0] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_body7[i0] : i0 >= 0 and i0 <= 11 }",
+         "name" : "Stmt_for_body7",
+         "schedule" : "{ Stmt_for_body7[i0] -> scattering[0, i0, 0] }"
+      }
+   ]
+}

test/Isl/CodeGen/MemAccess/simple_analyze.ll

 
 for.inc11:                                        ; preds = %for.body7
   %inc13 = add nsw i32 %1, 1
   br label %for.cond4
 
 for.end14:                                        ; preds = %for.cond4
   ret i32 0
 }
-; CHECK: New access function '{ Stmt_for_body7[i0] -> MemRef_B[0] }'detected in JSCOP file
-; CHECK: New access function '{ Stmt_for_body[i0] -> MemRef_A[0] }'detected in JSCOP file
+; CHECK-DAG: New access function '{ Stmt_for_body7[i0] -> MemRef_B[0] }'detected in JSCOP file
+; CHECK-DAG: New access function '{ Stmt_for_body[i0] -> MemRef_A[0] }'detected in JSCOP file

test/Isl/CodeGen/aliasing_parametric_simple_1.ll

+; RUN: opt %loadPolly -polly-codegen-isl -polly-use-runtime-alias-checks -S < %s | FileCheck %s
+;
+;    void jd(int *A, int *B, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[c];
+;    }
+;
+; CHECK:  %[[AMax:[._a-zA-Z0-9]*]] = getelementptr i32* %A, i64 1024
+; CHECK:  %[[BMin:[._a-zA-Z0-9]*]] = getelementptr i32* %B, i32 %c
+; CHECK:  %[[AltB:[._a-zA-Z0-9]*]] = icmp ule i32* %[[AMax]], %[[BMin]]
+; CHECK:  %[[Cext:[._a-zA-Z0-9]*]] = sext i32 %c to i64
+; CHECK:  %[[Cp1:[._a-zA-Z0-9]*]] = add nsw i64 %[[Cext]], 1
+; CHECK:  %[[BMax:[._a-zA-Z0-9]*]] = getelementptr i32* %B, i64 %[[Cp1]]
+; CHECK:  %[[AMin:[._a-zA-Z0-9]*]] = getelementptr i32* %A, i64 0
+; CHECK:  %[[BltA:[._a-zA-Z0-9]*]] = icmp ule i32* %[[BMax]], %[[AMin]]
+; CHECK:  %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[AltB]], %[[BltA]]
+; CHECK:  %[[RTC:[._a-zA-Z0-9]*]] = and i1 true, %[[NoAlias]]
+; CHECK:  br i1 %[[RTC]], label %polly.start, label %for.cond
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %idxprom = sext i32 %c to i64
+  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/Isl/CodeGen/aliasing_parametric_simple_2.ll

+; RUN: opt %loadPolly -polly-codegen-isl -polly-use-runtime-alias-checks -S < %s | FileCheck %s
+;
+;    void jd(int *A, int *B, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[c - 10] + B[5];
+;    }
+;
+; CHECK:  %[[AMax:[._a-zA-Z0-9]*]] = getelementptr i32* %A, i64 1024
+; CHECK:  %[[m0:[._a-zA-Z0-9]*]] = sext i32 %c to i64
+; CHECK:  %[[m1:[._a-zA-Z0-9]*]] = icmp sge i64 %[[m0]], 15
+; CHECK:  %[[m2:[._a-zA-Z0-9]*]] = sext i32 %c to i64
+; CHECK:  %[[m3:[._a-zA-Z0-9]*]] = sub nsw i64 %[[m2]], 10
+; CHECK:  %[[m4:[._a-zA-Z0-9]*]] = select i1 %[[m1]], i64 5, i64 %[[m3]]
+; CHECK:  %[[BMin:[._a-zA-Z0-9]*]] = getelementptr i32* %B, i64 %[[m4]]
+; CHECK:  %[[AltB:[._a-zA-Z0-9]*]] = icmp ule i32* %[[AMax]], %[[BMin]]
+; CHECK:  %[[M0:[._a-zA-Z0-9]*]] = sext i32 %c to i64
+; CHECK:  %[[M1:[._a-zA-Z0-9]*]] = icmp sle i64 %[[M0]], 15
+; CHECK:  %[[M2:[._a-zA-Z0-9]*]] = sext i32 %c to i64
+; CHECK:  %[[M3:[._a-zA-Z0-9]*]] = sub nsw i64 %[[M2]], 9
+; CHECK:  %[[M4:[._a-zA-Z0-9]*]] = select i1 %[[M1]], i64 6, i64 %[[M3]]
+; CHECK:  %[[BMax:[._a-zA-Z0-9]*]] = getelementptr i32* %B, i64 %[[M4]]
+; CHECK:  %[[AMin:[._a-zA-Z0-9]*]] = getelementptr i32* %A, i64 0
+; CHECK:  %[[BltA:[._a-zA-Z0-9]*]] = icmp ule i32* %[[BMax]], %[[AMin]]
+; CHECK:  %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[AltB]], %[[BltA]]
+; CHECK:  %[[RTC:[._a-zA-Z0-9]*]] = and i1 true, %[[NoAlias]]
+; CHECK:  br i1 %[[RTC]], label %polly.start, label %for.cond
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %sub = add nsw i32 %c, -10
+  %idxprom = sext i32 %sub to i64
+  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32* %B, i64 5
+  %tmp1 = load i32* %arrayidx1, align 4
+  %add = add nsw i32 %tmp, %tmp1
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopDetect/aliasing_parametric_simple_1.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: Valid Region for Scop:
+;
+;    void jd(int *A, int *B, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[c];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %idxprom = sext i32 %c to i64
+  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopDetect/aliasing_parametric_simple_2.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: Valid Region for Scop:
+;
+;    void jd(int *A, int *B, int c) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[c - 10] + B[5];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B, i32 %c) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %sub = add nsw i32 %c, -10
+  %idxprom = sext i32 %sub to i64
+  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
+  %tmp = load i32* %arrayidx, align 4
+  %arrayidx1 = getelementptr inbounds i32* %B, i64 5
+  %tmp1 = load i32* %arrayidx1, align 4
+  %add = add nsw i32 %tmp, %tmp1
+  %arrayidx3 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopDetect/aliasing_simple_1.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: Valid Region for Scop:
+;
+;    void jd(int *A, int *B) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[0];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = load i32* %B, align 4
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopDetect/aliasing_simple_2.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: Valid Region for Scop:
+;
+;    void jd(int *A, int *B) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = B[0] + B[1023];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A, i32* %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp = load i32* %B, align 4
+  %arrayidx1 = getelementptr inbounds i32* %B, i64 1023
+  %tmp1 = load i32* %arrayidx1, align 4
+  %add = add nsw i32 %tmp, %tmp1
+  %arrayidx2 = getelementptr inbounds i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopDetectionDiagnostics/ReportAlias-01.ll

-; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=false -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s
 
 ;void f(int A[], int B[]) {
 ;  for (int i=0; i<42; i++)
 ;    A[i] = B[i];
 ;}
 
 ; CHECK: remark: ReportAlias-01.c:2:8: The following errors keep this region from being a Scop.
 ; CHECK: remark: ReportAlias-01.c:3:5: Accesses to the arrays "A", "B" may access the same memory.
 ; CHECK: remark: ReportAlias-01.c:3:5: Invalid Scop candidate ends here.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @f(i32* %A, i32* %B) {
 entry:
   br label %entry.split

test/ScopInfo/Alias-0.ll

-; RUN: opt %loadPolly -polly-analyze-ir -analyze < %s -stats 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=true -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=RTA
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=false -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=NORTA
 ; REQUIRES: asserts
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 define void @f(i32* nocapture %a, i32* nocapture %b) nounwind {
 bb.nph:
   %0 = tail call i32 (...)* @rnd() nounwind       ; <i32> [#uses=1]

 
 return:                                           ; preds = %bb3
   ret void
 }
 
 declare i32 @rnd(...)
 
 
-; CHECK: 1 polly-detect     - Number of bad regions for Scop: Found base address alias
+; RTA:   1 polly-detect     - Number of regions that a valid part of Scop
+; NORTA: 1 polly-detect     - Number of bad regions for Scop: Found base address alias

test/ScopInfo/Alias-1.ll

-; RUN: opt %loadPolly -polly-analyze-ir -analyze < %s -stats 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=true -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=RTA
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=false -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=NORTA
 ; REQUIRES: asserts
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 define void @f(i32* nocapture %a, i32* nocapture %b) nounwind {
 bb.nph:
   %0 = tail call i32 (...)* @rnd() nounwind       ; <i32> [#uses=1]

 
 return:                                           ; preds = %bb3
   ret void
 }
 
 declare i32 @rnd(...)
 
 
-; CHECK: 1 polly-detect     - Number of bad regions for Scop: Found base address alias
+; RTA:   1 polly-detect     - Number of regions that a valid part of Scop
+; NORTA: 1 polly-detect     - Number of bad regions for Scop: Found base address alias

test/ScopInfo/Alias-2.ll

-; RUN: opt %loadPolly -polly-analyze-ir -analyze < %s -stats 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=true -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=RTA
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=false -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=NORTA
 ; REQUIRES: asserts
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 define void @f(i32** nocapture %ptrs, i64 %p0, i64 %p1, i64 %p2) nounwind {
 bb.nph:
   %0 = getelementptr inbounds i32** %ptrs, i64 %p0 ; <i32**> [#uses=1]
bb:                                               ; preds = %bb, %bb.nph
   store i32 %8, i32* %scevgep5, align 4
   %exitcond = icmp eq i64 %tmp, 64                ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:                                           ; preds = %bb
   ret void
 }
 
-; CHECK: 1 polly-detect     - Number of bad regions for Scop: Found base address alias
+; RTA:   1 polly-detect     - Number of regions that a valid part of Scop
+; NORTA: 1 polly-detect     - Number of bad regions for Scop: Found base address alias

test/ScopInfo/Alias-3.ll

-; RUN: opt %loadPolly -polly-analyze-ir -analyze < %s -stats 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=true -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=RTA
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=false -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=NORTA
 ; REQUIRES: asserts
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 define void @f(i32* nocapture %a, i32* nocapture %b) nounwind {
 bb.nph:
   br label %bb
bb:                                               ; preds = %bb, %bb.nph
   %exitcond = icmp eq i64 %2, 128                 ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:                                           ; preds = %bb
   ret void
 }
 
 
-; CHECK: 1 polly-detect     - Number of bad regions for Scop: Found base address alias
+; RTA:   1 polly-detect     - Number of regions that a valid part of Scop
+; NORTA: 1 polly-detect     - Number of bad regions for Scop: Found base address alias

test/ScopInfo/Alias-4.ll

-; RUN: opt %loadPolly -basicaa -polly-analyze-ir -analyze < %s -stats 2>&1 | not FileCheck %s
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=true -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=RTA
+; RUN: opt %loadPolly -polly-analyze-ir -polly-use-runtime-alias-checks=false -analyze < %s -stats 2>&1 | FileCheck %s --check-prefix=NORTA
 ; REQUIRES: asserts
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-linux-gnu"
 
 define void @f(i32* noalias nocapture %a, i32* noalias nocapture %b) nounwind {
 bb.nph:
   br label %bb
bb:                                               ; preds = %bb, %bb.nph
   %exitcond = icmp eq i64 %2, 128                 ; <i1> [#uses=1]
   br i1 %exitcond, label %return, label %bb
 
 return:                                           ; preds = %bb
   ret void
 }
 
 
-; CHECK:  Found base address alias
+; RTA:   1 polly-detect     - Number of regions that a valid part of Scop
+; NORTA: 1 polly-detect     - Number of bad regions for Scop: Found base address alias

test/ScopInfo/aliasing_multiple_alias_groups.ll

+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-scops -analyze          < %s | FileCheck %s --check-prefix=NOAA
+; RUN: opt %loadPolly -polly-use-runtime-alias-checks=true -polly-scops -analyze -tbaa    < %s | FileCheck %s --check-prefix=TBAA
+;
+;    void jd(int *Int0, int *Int1, float *Float0, float *Float1) {
+;      for (int i = 0; i < 1024; i++) {
+;        Int0[i] = Int1[i];
+;        Float0[i] = Float1[i];
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* nocapture %Int0, i32* nocapture readonly %Int1, float* nocapture %Float0, float* nocapture readonly %Float1) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32* %Int1, i64 %indvars.iv
+  %tmp = load i32* %arrayidx, align 4, !tbaa !0
+  %arrayidx2 = getelementptr inbounds i32* %Int0, i64 %indvars.iv
+  store i32 %tmp, i32* %arrayidx2, align 4, !tbaa !0
+  %arrayidx4 = getelementptr inbounds float* %Float1, i64 %indvars.iv
+  %tmp1 = load float* %arrayidx4, align 4, !tbaa !4
+  %arrayidx6 = getelementptr inbounds float* %Float0, i64 %indvars.iv
+  store float %tmp1, float* %arrayidx6, align 4, !tbaa !4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+!0 = metadata !{metadata !1, metadata !1, i64 0}
+!1 = metadata !{metadata !"int", metadata !2, i64 0}
+!2 = metadata !{metadata !"omnipotent char", metadata !3, i64 0}
+!3 = metadata !{metadata !"Simple C/C++ TBAA"}
+!4 = metadata !{metadata !5, metadata !5, i64 0}
+!5 = metadata !{metadata !"float", metadata !2, i64 0}
+
+; NOAA: Alias Groups (1):
+; NOAA-DAG:      <{ MemRef_Int0[(0)] }, { MemRef_Int0[(1024)] }>
+; NOAA-DAG:      <{ MemRef_Int1[(0)] }, { MemRef_Int1[(1024)] }>
+; NOAA-DAG:      <{ MemRef_Float0[(0)] }, { MemRef_Float0[(1024)] }>
+; NOAA-DAG:      <{ MemRef_Float1[(0)] }, { MemRef_Float1[(1024)] }>
+
+; TBAA-DAG: Alias Groups (2):
+; TBAA-DAG:      <{ MemRef_Int0[(0)] }, { MemRef_Int0[(1024)] }>
+; TBAA-DAG:      <{ MemRef_Int1[(0)] }, { MemRef_Int1[(1024)] }>
+; TBAA-DAG:      <{ MemRef_Float0[(0)] }, { MemRef_Float0[(1024)] }>
+; TBAA-DAG:      <{ MemRef_Float1[(0)] }, { MemRef_Float1[(1024)] }>