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

[Marcello Maggioni]

2011/11/19 Tobias Grosser <tobias at grosser.es>:
> 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?

I wanted to add a test case that in case of a "missing the flag" at
command line confirmed the functionality was actually disabled (and
this is the reason of the XFAIL test).
Originally you said I had to add a minimal test case to the patch,
should I add some more tests now with more complex scops?

>> 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.

Ouch!

>
>> 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
>

Ok, I'll simplify these parts, thanks.

Marcello