[LLVMdev] How to make Polly ignore some non-affine memory accesses

[Tobias Grosser]

On 11/18/2011 01:34 PM, Marcello Maggioni wrote:
> Ok , this is what I believe is the final patch that adds the
> non-affine accept functionality to Polly, this should have no issues.
>
> I added three tests, two in ScopInfo (two simple tests, one expected
> fail and one success based on the same source) and one in CodeGen that
> verifies that the code is generated.
>
> The patch is attached.

The patch includes only one test case. I also have some tiny last 
comments inline. Otherwise the patch looks good.

 > +++ test/ScopInfo/simple_nonaffine_loop_exfail.ll	(revision 0)
 > @@ -0,0 +1,42 @@
 > +; RUN: opt %loadPolly %defaultOpts -polly-scops -analyze %s |
 > FileCheck %s
 > +; XFAIL: *

Why is this one still XFAIL?

> Index: lib/Analysis/ScopInfo.cpp
> ===================================================================
> --- lib/Analysis/ScopInfo.cpp	(revision 144978)
> +++ lib/Analysis/ScopInfo.cpp	(working copy)
> @@ -311,29 +311,38 @@
>     Type = Access.isRead() ? Read : Write;
>     statement = Statement;
>
> -  isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement, Access.getOffset());
>     BaseAddr = Access.getBase();
>
> -  setBaseName();
> +  if (Access.isAffine()) {
>
> -  // Devide the access function by the size of the elements in the array.
> -  //
> -  // A stride one array access in C expressed as A[i] is expressed in LLVM-IR
> -  // as something like A[i * elementsize]. This hides the fact that two
> -  // subsequent values of 'i' index two values that are stored next to each
> -  // other in memory. By this devision we make this characteristic obvious
> -  // again.
> -  isl_int v;
> -  isl_int_init(v);
> -  isl_int_set_si(v, Access.getElemSizeInBytes());
> -  Affine = isl_pw_aff_scale_down(Affine, v);
> -  isl_int_clear(v);
> +    isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement, Access.getOffset());
>
> -  AccessRelation = isl_map_from_pw_aff(Affine);
> -  AccessRelation = isl_map_set_tuple_name(AccessRelation, isl_dim_in,
> -                                          Statement->getBaseName());
> -  AccessRelation = isl_map_set_tuple_name(AccessRelation, isl_dim_out,
> -                                          getBaseName().c_str());
> +    setBaseName();
> +
> +    // Devide the access function by the size of the elements in the array.
> +    //
> +    // A stride one array access in C expressed as A[i] is expressed in LLVM-IR
> +    // as something like A[i * elementsize]. This hides the fact that two
> +    // subsequent values of 'i' index two values that are stored next to each
> +    // other in memory. By this devision we make this characteristic obvious
> +    // again.
> +    isl_int v;
> +    isl_int_init(v);
> +    isl_int_set_si(v, Access.getElemSizeInBytes());
> +    Affine = isl_pw_aff_scale_down(Affine, v);
> +    isl_int_clear(v);
> +
> +    AccessRelation = isl_map_from_pw_aff(Affine);
> +    AccessRelation = isl_map_set_tuple_name(AccessRelation, isl_dim_in,
> +                                            Statement->getBaseName());
> +    AccessRelation = isl_map_set_tuple_name(AccessRelation, isl_dim_out,
> +                                            getBaseName().c_str());
> +  }
> +  else
> +  {

Use '} else {' here.


> Index: lib/Analysis/ScopDetection.cpp
> ===================================================================
> --- lib/Analysis/ScopDetection.cpp	(revision 144978)
> +++ lib/Analysis/ScopDetection.cpp	(working copy)
> @@ -79,6 +79,11 @@
>                  cl::desc("Ignore possible aliasing of the array bases"),
>                  cl::Hidden, cl::init(false));
>
> +static cl::opt<bool>
> +AllowNonAffine("polly-allow-nonaffine",
> +               cl::desc("Allow non affine access functions for arrays"),
> +               cl::Hidden, cl::init(false));
> +
>   //===----------------------------------------------------------------------===//
>   // Statistics.
>
> @@ -236,7 +241,9 @@
>     BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
>
>     if (!BasePointer)
> +  {
>       INVALID(AffFunc, "No base pointer");
> +  }
This change is unneeded and unrelated.

>
>     BaseValue = BasePointer->getValue();
>
> @@ -245,8 +252,9 @@
>
>     AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
>
> -  if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
> +  if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue)&&  !AllowNonAffine)
>       INVALID(AffFunc, "Bad memory address "<<  *AccessFunction);
> +
>
>     // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
>     // created by IndependentBlocks Pass.
> Index: lib/Analysis/TempScopInfo.cpp
> ===================================================================
> --- lib/Analysis/TempScopInfo.cpp	(revision 144978)
> +++ lib/Analysis/TempScopInfo.cpp	(working copy)
> @@ -98,12 +98,20 @@
>           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
>
>         assert(BasePointer&&  "Could not find base pointer");
> +      AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
> +
> +      if (isAffineExpr(&R, AccessFunction, *SE, BasePointer->getValue())) {
>
> -      AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
> -      Functions.push_back(std::make_pair(IRAccess(Type,
> +        Functions.push_back(std::make_pair(IRAccess(Type,
>                                                     BasePointer->getValue(),
> -                                                  AccessFunction, Size),
> +                                                  AccessFunction, Size, true),
>                                            &Inst));
> +      } else {
> +        Functions.push_back(std::make_pair(IRAccess(Type,
> +                                                  BasePointer->getValue(),
> +                                                  AccessFunction, Size, false),
> +&Inst));
> +      }

You may want to simplify this to:

AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
bool IsAffine = isAffineExpr(&R, AccessFunction, *SE,
                              BasePointer->getValue()));
Functions.push_back(std::make_pair(IRAccess(Type, 

                                             BasePointer->getValue(),
                                             AccessFunction, Size,
					    IsAffine);

Cheers and thanks for you work
Tobi