llvm dev - Nov 2011 - [LLVMdev] How to make Polly ignore some non-affine memory accesses

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

On 11/20/2011 03:01 AM, Marcello Maggioni wrote:
> 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).he
XFAIL it not the way to test this. You can just add another command line
to the passing test, remove the flag to enable non-affine access 
functions and replace '| FileCheck' with '| not FileCheck'.
> Originally you said I had to add a minimst al test case to the patch,
> should I add some more tests now withore complex scops?
I do not see that a more complex scope would test more of the feature. 
You could add a test case where the access subscript is not a valid
SCEV, but COULD_NOT_COMPUTE.

Cheers
Tobi

Sorry for the noobish question, but what kind of subscripts generate a
SCEVCouldNotCompute  from the SCEV engine?
I tried for a while but I wasn't able to trigger that.

2011/11/20 Tobias Grosser <tobias at grosser.es>:
> On 11/20/2011 03:01 AM, Marcello Maggioni wrote:
>>
>> 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).he
>
> XFAIL it not the way to test this. You can just add another command line
> to the passing test, remove the flag to enable non-affine access functions
> and replace '| FileCheck' with '| not FileCheck'.
>
>> Originally you said I had to add a minimst al test case to the patch,
>> should I add some more tests now withore complex scops?
>
> I do not see that a more complex scope would test more of the feature. You
> could add a test case where the access subscript is not a valid
> SCEV, but COULD_NOT_COMPUTE.
>
> Cheers
> Tobi
>