How to make Polly ignore some non-affine memory accesses

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
41 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
2011/11/14 Tobias Grosser <[hidden email]>:

> On 11/14/2011 01:24 AM, Marcello Maggioni wrote:
>>
>> Hi Tobias.
>>
>> I worked on enabling Polly accepting non affine memory accesses and I
>> produced a patch.
>
> Great.
>
>> I saw that there were a lot of updates in Polly recently, so I had to
>> redo a lot of the work I did and that slowed me quite a bit.
>
> Ups, sorry! However, I believe without these changes detecting non-affine
> memory access functions would have been a lot more complicated.

Indeed! The patch almost shrinked to half the code it was before those
changes! Great work.

>> I tested the patch on some programs and it seems to work and not to
>> break anything, but you know the topic much better than me, so if you
>> find something wrong please tell me! (at least it shouldn't produce a
>> crash I believe ... I tested the patch quite a lot from that point of
>> view ...). The patch is in the attachment to this mail and was last
>> tested on LLVM SVN revision 144502 .
>
> OK. Review is inlined in the patch.
>
>> I also found a bug in polly or ISL/GMP libraries. If polly encounters
>> an array access of type:
>>
>> A[i][i]
>>
>> it enters an infinite loop (I believe it is an infinite loop because I
>> waited 5 minutes and it didn't terminate compiling a code that was
>> like 15 lines long).  I tried to track down the problem with gdb , but
>> it seems to be in some gmp function called by ISL of which I'm not a
>> very expert of.
>
> [remove backtrace & code]
>
>> I actually don't know if it is an ISL bug or an improper use by polly.
>> To compile isl I use gmp-5.0.2
>
> I will look into this.
>
>> --- ./include/polly/ScopDetection.h     2011-11-13 02:37:59.000000000
>> +0100
>> +++ ../llvm2/tools/polly/./include/polly/ScopDetection.h        2011-11-13
>> 01:11:17.000000000 +0100
>> @@ -145,6 +145,8 @@
>>    /// @return True if the call instruction is valid, false otherwise.
>>    static bool isValidCallInst(CallInst&CI);
>>
>> +  const Value *GetBaseValue(const SCEV *S)  const;
>
> Why is this function needed? For me it looks like it implements
> the same as
>
> SCEVValue *Operand = dyn_cast<SCEVValue>(getPointerOperand())
>
> if (!Operand)
>  return invalid Value;
>
> return Operand->getValue();

Mmm, about this I think that depends on the fact that I'm still quite
unexperienced on the topic and fail to be "optimal" in doing some
things.
In the old version of Polly in ScopDetection (isValidMemoryAccess
function) there was an "isValidAffineFunction" that detected if the
access function was affine or not. That function initialized a "Value*
" pointer used for alias analysis later in the isValidMemoryAccess
function itself. If the "isValidAffineFunction" failed that pointer
was left uninitialized. I needed a way to get that pointer value in
order to make the alias analysis work and the one used in
"isValidAffineFunction" on affine functions didn't seemed to work (as
far as I remember), so I searched for alternative methods and
GetBaseValue did work.
With the recent changes to Polly this function doesn't seem to be
useful anymore though , and after removing that "if block" actually
all the test cases I have seem to continue working well, so this code
can be removed without problems I think!

>>    /// @brief Check if a memory access can be part of a Scop.
>>    ///
>>    /// @param Inst The instruction accessing the memory.
>> --- ./include/polly/TempScopInfo.h      2011-11-13 02:37:59.000000000
>> +0100
>> +++ ../llvm2/tools/polly/./include/polly/TempScopInfo.h 2011-11-13
>> 02:34:47.000000000 +0100
>> @@ -45,12 +45,13 @@
>>  private:
>>    unsigned ElemBytes;
>>    TypeKind Type;
>> +  bool is_affine;
>
> I think IsAffine matches more the LLVM coding conventions.
>
>>
>>  public:
>>    explicit IRAccess (TypeKind Type, const Value *BaseAddress,
>> -                     const SCEV *Offset, unsigned elemBytes)
>> +                     const SCEV *Offset, unsigned elemBytes, bool affine)
>
> 'affine' should start with an uppercase letter. Polly itself has some
> inconsistent naming, but we started to follow the LLVM coding conventions
> since a while.
>
>>      : BaseAddress(BaseAddress), Offset(Offset),
>> -      ElemBytes(elemBytes), Type(Type) {}
>> +      ElemBytes(elemBytes), Type(Type), is_affine(affine) {}
>>
>>    enum TypeKind getType() const { return Type; }
>>
>> @@ -60,7 +61,10 @@
>>
>>    unsigned getElemSizeInBytes() const { return ElemBytes; }
>>
>> +  bool isAffine() const { return is_affine; }
>> +
>>    bool isRead() const { return Type == READ; }
>> +
>>  };
>>
>>  class Comparison {
>> --- ./lib/Analysis/ScopDetection.cpp    2011-11-13 02:38:06.000000000
>> +0100
>> +++ ../llvm2/tools/polly/./lib/Analysis/ScopDetection.cpp       2011-11-13
>> 01:28:00.000000000 +0100
>> @@ -226,6 +226,24 @@
>>    return false;
>>  }
>>
>> +const Value *ScopDetection::GetBaseValue(const SCEV *S)  const {
>> +  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
>> +    // In an addrec, assume that the base will be in the start, rather
>> +    // than the step.
>> +    return GetBaseValue(AR->getStart());
>> +  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
>> +    // If there's a pointer operand, it'll be sorted at the end of the
>> list.
>> +    const SCEV *Last = A->getOperand(A->getNumOperands()-1);
>> +    if (Last->getType()->isPointerTy())
>> +      return GetBaseValue(Last);
>> +  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
>> +    // This is a leaf node.
>> +    return U->getValue();
>> +  }
>> +  // No Identified object found.
>> +  return 0;
>> +}
>
> As remarked earlier, I believ this can be replaced by getPointerOperand().
>
>>  bool ScopDetection::isValidMemoryAccess(Instruction&Inst,
>>                                          DetectionContext&Context) const {
>>    Value *Ptr = getPointerOperand(Inst);
>> @@ -236,8 +254,12 @@
>>    BasePointer =
>> dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
>>
>>    if (!BasePointer)
>> -    INVALID(AffFunc, "No base pointer");
>> -
>> +  {
>> +//    INVALID(AffFunc, "No base pointer");
>> +    BaseValue = (Value*) GetBaseValue(AccessFunction);
>> +  }
>> +  else
>> +  {
>>    BaseValue = BasePointer->getValue();
>
> I don't see a need for any change here. Both functions get the base pointer
> and we should fail, if we cannot derive a base pointer. Do you have a test
> case where getPointerBase() does not yield a valid base pointer, but
> GetBaseValue(AccessFunction) does?
>
>>    if (isa<UndefValue>(BaseValue))
>> @@ -245,8 +267,9 @@
>>
>>    AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
>>
>> -  if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
>> -    INVALID(AffFunc, "Bad memory address "<<  *AccessFunction);
>> +    //if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE,
>> BaseValue))
>> +    //  INVALID(AffFunc, "Bad memory address "<<  *AccessFunction);
>
> Can you leave this and add a command line option
> '-polly-allow-nonaffine' to allow non affine access functions.
>
>> +  }
>>
>>    // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca
>> instructions
>>    // created by IndependentBlocks Pass.
>> --- ./lib/Analysis/ScopInfo.cpp 2011-11-13 02:38:06.000000000 +0100
>> +++ ../llvm2/tools/polly/./lib/Analysis/ScopInfo.cpp    2011-11-13
>> 02:36:12.000000000 +0100
>> @@ -310,9 +310,13 @@
>>    Type = Access.isRead() ? Read : Write;
>>    statement = Statement;
>>
>> -  isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement,
>> Access.getOffset());
>>    BaseAddr = Access.getBase();
>>
>> +  if (Access.isAffine())
>> +  {
>
> This should be
>
> if (Access.isAffine()) {
>
>
>> +
>> +  isl_pw_aff *Affine = SCEVAffinator::getPwAff(Statement,
>> Access.getOffset());
>> +
>>    setBaseName();
>>
>>    // Devide the access function by the size of the elements in the array.
>> @@ -334,6 +338,12 @@
>>    AccessRelation = isl_map_set_tuple_name(AccessRelation, isl_dim_out,
>>                                            getBaseName().c_str());
>>  }
>> +  else
>> +  {
>
> this should be
>    } else {
>
>> +    Type = MayWrite;
>
> You are right, we should use may-accesses here. But why always setting the
> type to may-write? A read should remain a read (as there is no difference
> between read and may-read).

You are right, in the patch for the old version that was handled
correctly, I don't know how this reverted back to this way in the
patch for the new version , I'll get it fixed.

>> +    AccessRelation =
>> isl_map_from_basic_map(createBasicAccessMap(Statement));
>> +  }
>> +}
>>
>>  void MemoryAccess::realignParams() {
>>    isl_space *ParamSpace = statement->getParent()->getParamSpace();
>> --- ./lib/Analysis/TempScopInfo.cpp     2011-11-13 02:38:06.000000000
>> +0100
>> +++ ../llvm2/tools/polly/./lib/Analysis/TempScopInfo.cpp        2011-11-13
>> 02:35:22.000000000 +0100
>> @@ -98,13 +98,24 @@
>>          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()))
>> +      {
>
> Put the '{' in the previous line.
>
>> +
>>        Functions.push_back(std::make_pair(IRAccess(Type,
>>
>>  BasePointer->getValue(),
>> -                                                  AccessFunction, Size),
>> +                                                  AccessFunction, Size,
>> true),
>>                                           &Inst));
>>      }
>> +      else
>> +      {
>
> This should be
>
> } else {
>
>> +         Functions.push_back(std::make_pair(IRAccess(Type,
>> +
>>  BasePointer->getValue(),
>> +                                                  AccessFunction, Size,
>> false),
>> +&Inst));
>> +      }
>> +    }
>>    }
>>
>>    if (Functions.empty())

Yeah, there are quite a few stylistic problems actually, my bad!! I'll
get all the style problems fixed as fast as possible! Sorry for that.

> Besides the comments above, the patch looks great. It is a nice improvement
> to Polly. Can you repost it after the comments are addressed? Also could you
> include a minimal test case in the patch, that verifies this features is
> working correctly.

Thank you, for your time Tobias explaining all the issues with the
patch so throughly and in a clear manner .

Should I make a specific subdirectory for the test case?

> Thanks
> Tobi
>
> P.S.: Please post patches to the mailing lists.
>
>

What do you mean with post patches to the mailing lists? Do you mean
in llvm-dev or llvm-commit?
The previous patch has been posted on llvm-dev, was that wrong?

Thanks again.

Marcello

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
On 11/14/2011 02:45 PM, Marcello Maggioni wrote:

> 2011/11/14 Tobias Grosser<[hidden email]>:
>> On 11/14/2011 01:24 AM, Marcello Maggioni wrote:
>>>
>>> Hi Tobias.
>>>
>>> I worked on enabling Polly accepting non affine memory accesses and I
>>> produced a patch.
>>
>> Great.
>>
>>> I saw that there were a lot of updates in Polly recently, so I had to
>>> redo a lot of the work I did and that slowed me quite a bit.
>>
>> Ups, sorry! However, I believe without these changes detecting non-affine
>> memory access functions would have been a lot more complicated.
>
> Indeed! The patch almost shrinked to half the code it was before those
> changes! Great work.

Thanks. (You motivated me to fix this, when you asked about non-affine
access functions)

>> this should be
>>     } else {
>>
>>> +    Type = MayWrite;
>>
>> You are right, we should use may-accesses here. But why always setting the
>> type to may-write? A read should remain a read (as there is no difference
>> between read and may-read).
>
> You are right, in the patch for the old version that was handled
> correctly, I don't know how this reverted back to this way in the
> patch for the new version , I'll get it fixed.

Wonderful. Very cool that you realized I added MayWrite exactly for this
case.

>>> +         Functions.push_back(std::make_pair(IRAccess(Type,
>>> +
>>>   BasePointer->getValue(),
>>> +                                                  AccessFunction, Size,
>>> false),
>>> +&Inst));
>>> +      }
>>> +    }
>>>     }
>>>
>>>     if (Functions.empty())
>
> Yeah, there are quite a few stylistic problems actually, my bad!! I'll
> get all the style problems fixed as fast as possible! Sorry for that.

Alright. I failed on this myself, which is why Polly is not everywhere
perfect. Still, we should try to follow the LLVM style guide.

BTW, if you find any problems in patches I commit or in Polly itself or
if your find anything that you don't understand, please go ahead and let
me know. Even if it is correct and you just did not get it, I think this
is a documentation bug and should be fixed.

>> Besides the comments above, the patch looks great. It is a nice improvement
>> to Polly. Can you repost it after the comments are addressed? Also could you
>> include a minimal test case in the patch, that verifies this features is
>> working correctly.
>
> Thank you, for your time Tobias explaining all the issues with the
> patch so throughly and in a clear manner .

You did a good job working on the patch. It is great if people go ahead,
work for themselves and send in a patch that works. Even better if the
right approach was taken and just some smaller remarks are necessary.

> Should I make a specific subdirectory for the test case?

No. I think you can put one test case in test/ScopInfo that runs
-polly-scops -analyze and one in test/CodeGeneration that ensures that
the correct code is generated.

> >> Thanks
>> Tobi
>>
>> P.S.: Please post patches to the mailing lists.

> What do you mean with post patches to the mailing lists? Do you mean
> in llvm-dev or llvm-commit?
> The previous patch has been posted on llvm-dev, was that wrong?

Normally patches should either be posted on llvm-commit or
[hidden email].

In this case it seems you sent two separate emails, one to me and
another to Sebastian and llvmdev. I just saw the one to me and did not
see that another one was sent to llvmdev. Just send next time one email
with all of us copied.

Cheers
Tobi
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
2011/11/14 Tobias Grosser <[hidden email]>:

> On 11/14/2011 02:45 PM, Marcello Maggioni wrote:
>>
>> 2011/11/14 Tobias Grosser<[hidden email]>:
>>>
>>> On 11/14/2011 01:24 AM, Marcello Maggioni wrote:
>>>>
>>>> Hi Tobias.
>>>>
>>>> I worked on enabling Polly accepting non affine memory accesses and I
>>>> produced a patch.
>>>
>>> Great.
>>>
>>>> I saw that there were a lot of updates in Polly recently, so I had to
>>>> redo a lot of the work I did and that slowed me quite a bit.
>>>
>>> Ups, sorry! However, I believe without these changes detecting non-affine
>>> memory access functions would have been a lot more complicated.
>>
>> Indeed! The patch almost shrinked to half the code it was before those
>> changes! Great work.
>
> Thanks. (You motivated me to fix this, when you asked about non-affine
> access functions)
>
>>> this should be
>>>    } else {
>>>
>>>> +    Type = MayWrite;
>>>
>>> You are right, we should use may-accesses here. But why always setting
>>> the
>>> type to may-write? A read should remain a read (as there is no difference
>>> between read and may-read).
>>
>> You are right, in the patch for the old version that was handled
>> correctly, I don't know how this reverted back to this way in the
>> patch for the new version , I'll get it fixed.
>
> Wonderful. Very cool that you realized I added MayWrite exactly for this
> case.
>
>>>> +         Functions.push_back(std::make_pair(IRAccess(Type,
>>>> +
>>>>  BasePointer->getValue(),
>>>> +                                                  AccessFunction, Size,
>>>> false),
>>>> +&Inst));
>>>> +      }
>>>> +    }
>>>>    }
>>>>
>>>>    if (Functions.empty())
>>
>> Yeah, there are quite a few stylistic problems actually, my bad!! I'll
>> get all the style problems fixed as fast as possible! Sorry for that.
>
> Alright. I failed on this myself, which is why Polly is not everywhere
> perfect. Still, we should try to follow the LLVM style guide.
>
> BTW, if you find any problems in patches I commit or in Polly itself or if
> your find anything that you don't understand, please go ahead and let me
> know. Even if it is correct and you just did not get it, I think this is a
> documentation bug and should be fixed.
>
>>> Besides the comments above, the patch looks great. It is a nice
>>> improvement
>>> to Polly. Can you repost it after the comments are addressed? Also could
>>> you
>>> include a minimal test case in the patch, that verifies this features is
>>> working correctly.
>>
>> Thank you, for your time Tobias explaining all the issues with the
>> patch so throughly and in a clear manner .
>
> You did a good job working on the patch. It is great if people go ahead,
> work for themselves and send in a patch that works. Even better if the right
> approach was taken and just some smaller remarks are necessary.
>
>> Should I make a specific subdirectory for the test case?
>
> No. I think you can put one test case in test/ScopInfo that runs
> -polly-scops -analyze and one in test/CodeGeneration that ensures that the
> correct code is generated.
>
>> >> Thanks
>>>
>>> Tobi
>>>
>>> P.S.: Please post patches to the mailing lists.
>
>> What do you mean with post patches to the mailing lists? Do you mean
>> in llvm-dev or llvm-commit?
>> The previous patch has been posted on llvm-dev, was that wrong?
>
> Normally patches should either be posted on llvm-commit or
> [hidden email].
>
> In this case it seems you sent two separate emails, one to me and another to
> Sebastian and llvmdev. I just saw the one to me and did not see that another
> one was sent to llvmdev. Just send next time one email with all of us
> copied.
>
> Cheers
> Tobi
>
Hi, I implemented the changes you required, I hope this I solved all
the stylistic issues now and I also added the flag you required.

I added a test case to the patch , but I'm not very expert with the
llvm testing framework and I had difficulties testing running the
test. I tried running the polly test suite compiling polly with CMAKE,
but I have linking problems with CMAKE while linking the
LLVMPolly.dylib library and can't figure out why (lots of linker
errors). The autotools build works perfectly but polly-tests doesn't
work with autotools.
I tried running directly the tests with lit , but it gives me

lit.py: lit.cfg:74: fatal: No site specific configuration available!

Do you know how can I run the tests manually to check if they are
correct? I tried searching around , but couldn't find a reliable way
to check if the test works.

The preliminary patch is attached to the mail.

Marcello

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

accept_affine3.diff (14K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
2011/11/15 Marcello Maggioni <[hidden email]>:

> 2011/11/14 Tobias Grosser <[hidden email]>:
>> On 11/14/2011 02:45 PM, Marcello Maggioni wrote:
>>>
>>> 2011/11/14 Tobias Grosser<[hidden email]>:
>>>>
>>>> On 11/14/2011 01:24 AM, Marcello Maggioni wrote:
>>>>>
>>>>> Hi Tobias.
>>>>>
>>>>> I worked on enabling Polly accepting non affine memory accesses and I
>>>>> produced a patch.
>>>>
>>>> Great.
>>>>
>>>>> I saw that there were a lot of updates in Polly recently, so I had to
>>>>> redo a lot of the work I did and that slowed me quite a bit.
>>>>
>>>> Ups, sorry! However, I believe without these changes detecting non-affine
>>>> memory access functions would have been a lot more complicated.
>>>
>>> Indeed! The patch almost shrinked to half the code it was before those
>>> changes! Great work.
>>
>> Thanks. (You motivated me to fix this, when you asked about non-affine
>> access functions)
>>
>>>> this should be
>>>>    } else {
>>>>
>>>>> +    Type = MayWrite;
>>>>
>>>> You are right, we should use may-accesses here. But why always setting
>>>> the
>>>> type to may-write? A read should remain a read (as there is no difference
>>>> between read and may-read).
>>>
>>> You are right, in the patch for the old version that was handled
>>> correctly, I don't know how this reverted back to this way in the
>>> patch for the new version , I'll get it fixed.
>>
>> Wonderful. Very cool that you realized I added MayWrite exactly for this
>> case.
>>
>>>>> +         Functions.push_back(std::make_pair(IRAccess(Type,
>>>>> +
>>>>>  BasePointer->getValue(),
>>>>> +                                                  AccessFunction, Size,
>>>>> false),
>>>>> +&Inst));
>>>>> +      }
>>>>> +    }
>>>>>    }
>>>>>
>>>>>    if (Functions.empty())
>>>
>>> Yeah, there are quite a few stylistic problems actually, my bad!! I'll
>>> get all the style problems fixed as fast as possible! Sorry for that.
>>
>> Alright. I failed on this myself, which is why Polly is not everywhere
>> perfect. Still, we should try to follow the LLVM style guide.
>>
>> BTW, if you find any problems in patches I commit or in Polly itself or if
>> your find anything that you don't understand, please go ahead and let me
>> know. Even if it is correct and you just did not get it, I think this is a
>> documentation bug and should be fixed.
>>
>>>> Besides the comments above, the patch looks great. It is a nice
>>>> improvement
>>>> to Polly. Can you repost it after the comments are addressed? Also could
>>>> you
>>>> include a minimal test case in the patch, that verifies this features is
>>>> working correctly.
>>>
>>> Thank you, for your time Tobias explaining all the issues with the
>>> patch so throughly and in a clear manner .
>>
>> You did a good job working on the patch. It is great if people go ahead,
>> work for themselves and send in a patch that works. Even better if the right
>> approach was taken and just some smaller remarks are necessary.
>>
>>> Should I make a specific subdirectory for the test case?
>>
>> No. I think you can put one test case in test/ScopInfo that runs
>> -polly-scops -analyze and one in test/CodeGeneration that ensures that the
>> correct code is generated.
>>
>>> >> Thanks
>>>>
>>>> Tobi
>>>>
>>>> P.S.: Please post patches to the mailing lists.
>>
>>> What do you mean with post patches to the mailing lists? Do you mean
>>> in llvm-dev or llvm-commit?
>>> The previous patch has been posted on llvm-dev, was that wrong?
>>
>> Normally patches should either be posted on llvm-commit or
>> [hidden email].
>>
>> In this case it seems you sent two separate emails, one to me and another to
>> Sebastian and llvmdev. I just saw the one to me and did not see that another
>> one was sent to llvmdev. Just send next time one email with all of us
>> copied.
>>
>> Cheers
>> Tobi
>>
>
> Hi, I implemented the changes you required, I hope this I solved all
> the stylistic issues now and I also added the flag you required.
>
> I added a test case to the patch , but I'm not very expert with the
> llvm testing framework and I had difficulties testing running the
> test. I tried running the polly test suite compiling polly with CMAKE,
> but I have linking problems with CMAKE while linking the
> LLVMPolly.dylib library and can't figure out why (lots of linker
> errors). The autotools build works perfectly but polly-tests doesn't
> work with autotools.
> I tried running directly the tests with lit , but it gives me
>
> lit.py: lit.cfg:74: fatal: No site specific configuration available!
>
> Do you know how can I run the tests manually to check if they are
> correct? I tried searching around , but couldn't find a reliable way
> to check if the test works.
>
> The preliminary patch is attached to the mail.
>
> Marcello
>
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 to correct the test runs on OSX will be posted shortly after
this one (I preferred to separate the two so that a problem with
either one of the two wouldn't give problems to the other and also to
give more clarity on what patch solves what problem).

Marcello

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

accept_affine_final.diff (10K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
2011/11/18 Marcello Maggioni <[hidden email]>:

> 2011/11/15 Marcello Maggioni <[hidden email]>:
>> 2011/11/14 Tobias Grosser <[hidden email]>:
>>> On 11/14/2011 02:45 PM, Marcello Maggioni wrote:
>>>>
>>>> 2011/11/14 Tobias Grosser<[hidden email]>:
>>>>>
>>>>> On 11/14/2011 01:24 AM, Marcello Maggioni wrote:
>>>>>>
>>>>>> Hi Tobias.
>>>>>>
>>>>>> I worked on enabling Polly accepting non affine memory accesses and I
>>>>>> produced a patch.
>>>>>
>>>>> Great.
>>>>>
>>>>>> I saw that there were a lot of updates in Polly recently, so I had to
>>>>>> redo a lot of the work I did and that slowed me quite a bit.
>>>>>
>>>>> Ups, sorry! However, I believe without these changes detecting non-affine
>>>>> memory access functions would have been a lot more complicated.
>>>>
>>>> Indeed! The patch almost shrinked to half the code it was before those
>>>> changes! Great work.
>>>
>>> Thanks. (You motivated me to fix this, when you asked about non-affine
>>> access functions)
>>>
>>>>> this should be
>>>>>    } else {
>>>>>
>>>>>> +    Type = MayWrite;
>>>>>
>>>>> You are right, we should use may-accesses here. But why always setting
>>>>> the
>>>>> type to may-write? A read should remain a read (as there is no difference
>>>>> between read and may-read).
>>>>
>>>> You are right, in the patch for the old version that was handled
>>>> correctly, I don't know how this reverted back to this way in the
>>>> patch for the new version , I'll get it fixed.
>>>
>>> Wonderful. Very cool that you realized I added MayWrite exactly for this
>>> case.
>>>
>>>>>> +         Functions.push_back(std::make_pair(IRAccess(Type,
>>>>>> +
>>>>>>  BasePointer->getValue(),
>>>>>> +                                                  AccessFunction, Size,
>>>>>> false),
>>>>>> +&Inst));
>>>>>> +      }
>>>>>> +    }
>>>>>>    }
>>>>>>
>>>>>>    if (Functions.empty())
>>>>
>>>> Yeah, there are quite a few stylistic problems actually, my bad!! I'll
>>>> get all the style problems fixed as fast as possible! Sorry for that.
>>>
>>> Alright. I failed on this myself, which is why Polly is not everywhere
>>> perfect. Still, we should try to follow the LLVM style guide.
>>>
>>> BTW, if you find any problems in patches I commit or in Polly itself or if
>>> your find anything that you don't understand, please go ahead and let me
>>> know. Even if it is correct and you just did not get it, I think this is a
>>> documentation bug and should be fixed.
>>>
>>>>> Besides the comments above, the patch looks great. It is a nice
>>>>> improvement
>>>>> to Polly. Can you repost it after the comments are addressed? Also could
>>>>> you
>>>>> include a minimal test case in the patch, that verifies this features is
>>>>> working correctly.
>>>>
>>>> Thank you, for your time Tobias explaining all the issues with the
>>>> patch so throughly and in a clear manner .
>>>
>>> You did a good job working on the patch. It is great if people go ahead,
>>> work for themselves and send in a patch that works. Even better if the right
>>> approach was taken and just some smaller remarks are necessary.
>>>
>>>> Should I make a specific subdirectory for the test case?
>>>
>>> No. I think you can put one test case in test/ScopInfo that runs
>>> -polly-scops -analyze and one in test/CodeGeneration that ensures that the
>>> correct code is generated.
>>>
>>>> >> Thanks
>>>>>
>>>>> Tobi
>>>>>
>>>>> P.S.: Please post patches to the mailing lists.
>>>
>>>> What do you mean with post patches to the mailing lists? Do you mean
>>>> in llvm-dev or llvm-commit?
>>>> The previous patch has been posted on llvm-dev, was that wrong?
>>>
>>> Normally patches should either be posted on llvm-commit or
>>> [hidden email].
>>>
>>> In this case it seems you sent two separate emails, one to me and another to
>>> Sebastian and llvmdev. I just saw the one to me and did not see that another
>>> one was sent to llvmdev. Just send next time one email with all of us
>>> copied.
>>>
>>> Cheers
>>> Tobi
>>>
>>
>> Hi, I implemented the changes you required, I hope this I solved all
>> the stylistic issues now and I also added the flag you required.
>>
>> I added a test case to the patch , but I'm not very expert with the
>> llvm testing framework and I had difficulties testing running the
>> test. I tried running the polly test suite compiling polly with CMAKE,
>> but I have linking problems with CMAKE while linking the
>> LLVMPolly.dylib library and can't figure out why (lots of linker
>> errors). The autotools build works perfectly but polly-tests doesn't
>> work with autotools.
>> I tried running directly the tests with lit , but it gives me
>>
>> lit.py: lit.cfg:74: fatal: No site specific configuration available!
>>
>> Do you know how can I run the tests manually to check if they are
>> correct? I tried searching around , but couldn't find a reliable way
>> to check if the test works.
>>
>> The preliminary patch is attached to the mail.
>>
>> Marcello
>>
>
> 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 to correct the test runs on OSX will be posted shortly after
> this one (I preferred to separate the two so that a problem with
> either one of the two wouldn't give problems to the other and also to
> give more clarity on what patch solves what problem).
>
> Marcello
>
And here attached the patch to solve OSX tests run problems

Marcello

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

tests_osx_patch.diff (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
In reply to this post by Marcello Maggioni
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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Bernhard Reutner-Fischer


On Nov 19, 2011 5:40 PM, "Tobias Grosser" <[hidden email]> wrote:
>
> On 11/18/2011 01:34 PM, Marcello Maggioni wrote:

> > +    // Devide the access function by the size of the elements in the array.

Decide,  with a 'c', please. Multiple other occurances below, too.

Thanks,


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
On 11/19/2011 10:43 AM, Bernhard Reutner-Fischer wrote:

>
> On Nov 19, 2011 5:40 PM, "Tobias Grosser" <[hidden email]
> <mailto:[hidden email]>> wrote:
>  >
>  > On 11/18/2011 01:34 PM, Marcello Maggioni wrote:
>
>  > > +    // Devide the access function by the size of the elements in
> the array.
>
> Decide,  with a 'c', please. Multiple other occurances below, too.

I think the use of 'Devide' is correct here. It is the mathematical
operation '/' - to devide. Or do I miss something obvious?

Tobi
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Bernhard Reutner-Fischer


On Nov 19, 2011 7:45 PM, "Tobias Grosser" <[hidden email]> wrote:
>
> On 11/19/2011 10:43 AM, Bernhard Reutner-Fischer wrote:
>>
>>
>> On Nov 19, 2011 5:40 PM, "Tobias Grosser" <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>  >
>>  > On 11/18/2011 01:34 PM, Marcello Maggioni wrote:
>>
>>  > > +    // Devide the access function by the size of the elements in
>> the array.
>>
>> Decide,  with a 'c', please. Multiple other occurances below, too.
>
>
> I think the use of 'Devide' is correct here. It is the mathematical operation '/' - to devide. Or do I miss something obvious?

Isn't / more "divide"?


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
On 11/19/2011 10:48 AM, Bernhard Reutner-Fischer wrote:

>
> On Nov 19, 2011 7:45 PM, "Tobias Grosser" <[hidden email]
> <mailto:[hidden email]>> wrote:
>  >
>  > On 11/19/2011 10:43 AM, Bernhard Reutner-Fischer wrote:
>  >>
>  >>
>  >> On Nov 19, 2011 5:40 PM, "Tobias Grosser" <[hidden email]
> <mailto:[hidden email]>
>  >> <mailto:[hidden email] <mailto:[hidden email]>>> wrote:
>  >> >
>  >> > On 11/18/2011 01:34 PM, Marcello Maggioni wrote:
>  >>
>  >> > > +    // Devide the access function by the size of the elements in
>  >> the array.
>  >>
>  >> Decide,  with a 'c', please. Multiple other occurances below, too.
>  >
>  >
>  > I think the use of 'Devide' is correct here. It is the mathematical
> operation '/' - to devide. Or do I miss something obvious?
>
> Isn't / more "divide"?

True, it should be 'divide' instead of 'devide'.
Thanks for pointing out this typo.

Tobi

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
In reply to this post by Tobias Grosser-5
2011/11/19 Tobias Grosser <[hidden email]>:

> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
On 11/20/2011 03:01 AM, Marcello Maggioni wrote:

> 2011/11/19 Tobias Grosser<[hidden email]>:
>> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
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 <[hidden email]>:

> On 11/20/2011 03:01 AM, Marcello Maggioni wrote:
>>
>> 2011/11/19 Tobias Grosser<[hidden email]>:
>>>
>>> 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
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
On 11/20/2011 04:36 PM, Marcello Maggioni wrote:
> 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

Hi Marcello,

the SCEV returns SCEVCouldNotCompute in case it cannot analyze an
expression or if the analysis would be to complicated. I am currently
not sure if this may actually happen when calling getSCEV(), because
getSCEV() could just return a SCEVUnknown referencing the Value itself.
Maybe SCEVCouldNotCompute is just generated by functions like
SE->getBackedgeTakenCount()?

In case you cannot generate a test case that yields to this, I don't
think there is a need to try more. Even without such a test case the
patch should be OK.

Cheers
Tobi
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
2011/11/21 Tobias Grosser <[hidden email]>:

> On 11/20/2011 04:36 PM, Marcello Maggioni wrote:
>>
>> 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
>
> Hi Marcello,
>
> the SCEV returns SCEVCouldNotCompute in case it cannot analyze an expression
> or if the analysis would be to complicated. I am currently
> not sure if this may actually happen when calling getSCEV(), because
> getSCEV() could just return a SCEVUnknown referencing the Value itself.
> Maybe SCEVCouldNotCompute is just generated by functions like
> SE->getBackedgeTakenCount()?
>
> In case you cannot generate a test case that yields to this, I don't think
> there is a need to try more. Even without such a test case the patch should
> be OK.
>
> Cheers
> Tobi
>

Ok, thanks, I'll try other test cases to check if everything is ok,
better being sure.

About SCOPs with a "bitcast instruction" inside them I see that
ScopDetection discards those.
What problems can cause bitcasts to the Scop? Is it related to aliasing?

Marcello

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
On 11/21/2011 03:44 AM, Marcello Maggioni wrote:

> 2011/11/21 Tobias Grosser<[hidden email]>:
>> On 11/20/2011 04:36 PM, Marcello Maggioni wrote:
>>>
>>> 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
>>
>> Hi Marcello,
>>
>> the SCEV returns SCEVCouldNotCompute in case it cannot analyze an expression
>> or if the analysis would be to complicated. I am currently
>> not sure if this may actually happen when calling getSCEV(), because
>> getSCEV() could just return a SCEVUnknown referencing the Value itself.
>> Maybe SCEVCouldNotCompute is just generated by functions like
>> SE->getBackedgeTakenCount()?
>>
>> In case you cannot generate a test case that yields to this, I don't think
>> there is a need to try more. Even without such a test case the patch should
>> be OK.
>>
>> Cheers
>> Tobi
>>
>
> Ok, thanks, I'll try other test cases to check if everything is ok,
> better being sure.
>
> About SCOPs with a "bitcast instruction" inside them I see that
> ScopDetection discards those.
> What problems can cause bitcasts to the Scop? Is it related to aliasing?

I don't know. At the moment I wrote the scop detection I was not sure
that they don't cause any problems, so I conservatively discarded them.
Meanwhile I actually believe the don't introduce any problems and could
be allowed. However, before changing this, I would like to set up a
nightly tester that ensures the llvm test suite is compiled correctly.
This would allow us to understand if the support for this construct
introduces any regressions.

Cheers
Tobi
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
In reply to this post by Marcello Maggioni
On 11/18/2011 01:36 PM, Marcello Maggioni wrote:

> 2011/11/18 Marcello Maggioni<[hidden email]>:
>> The patch is attached.
>>
>> The patch to correct the test runs on OSX will be posted shortly after
>> this one (I preferred to separate the two so that a problem with
>> either one of the two wouldn't give problems to the other and also to
>> give more clarity on what patch solves what problem).
>>
>> Marcello
>>
>
> And here attached the patch to solve OSX tests run problems

Your patch did not apply cleanly, so I applied it by hand. I also added
the cmake part of this patch.

Everything is committed in:

---------------------------------------------------------
commit c007d1207ebaccedfa86b05d419f7f51ccf0204a
Author: Tobias Grosser <[hidden email]>
Date:   Tue Nov 22 19:40:38 2011 +0000

     test: Do not hardcode '.so' as library suffix

     Contributed by: Marcello Maggioni <[hidden email]>

     git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@145076 
---------------------------------------------------------

Can you check if it works for you?

Tobi
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
2011/11/22 Tobias Grosser <[hidden email]>:

> On 11/18/2011 01:36 PM, Marcello Maggioni wrote:
>>
>> 2011/11/18 Marcello Maggioni<[hidden email]>:
>>>
>>> The patch is attached.
>>>
>>> The patch to correct the test runs on OSX will be posted shortly after
>>> this one (I preferred to separate the two so that a problem with
>>> either one of the two wouldn't give problems to the other and also to
>>> give more clarity on what patch solves what problem).
>>>
>>> Marcello
>>>
>>
>> And here attached the patch to solve OSX tests run problems
>
> Your patch did not apply cleanly, so I applied it by hand. I also added the
> cmake part of this patch.
>
> Everything is committed in:
>
> ---------------------------------------------------------
> commit c007d1207ebaccedfa86b05d419f7f51ccf0204a
> Author: Tobias Grosser <[hidden email]>
> Date:   Tue Nov 22 19:40:38 2011 +0000
>
>    test: Do not hardcode '.so' as library suffix
>
>    Contributed by: Marcello Maggioni <[hidden email]>
>
>    git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@145076
> ---------------------------------------------------------
>
> Can you check if it works for you?
>
> Tobi
>

Sorry for the late response, I've been away.

The patch seems to work, thanks.

Marcello

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Tobias Grosser-5
In reply to this post by Marcello Maggioni
On 11/21/2011 12:44 PM, Marcello Maggioni wrote:

> 2011/11/21 Tobias Grosser<[hidden email]>:
>> On 11/20/2011 04:36 PM, Marcello Maggioni wrote:
>>>
>>> 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
>>
>> Hi Marcello,
>>
>> the SCEV returns SCEVCouldNotCompute in case it cannot analyze an expression
>> or if the analysis would be to complicated. I am currently
>> not sure if this may actually happen when calling getSCEV(), because
>> getSCEV() could just return a SCEVUnknown referencing the Value itself.
>> Maybe SCEVCouldNotCompute is just generated by functions like
>> SE->getBackedgeTakenCount()?
>>
>> In case you cannot generate a test case that yields to this, I don't think
>> there is a need to try more. Even without such a test case the patch should
>> be OK.
>>
>> Cheers
>> Tobi
>>
>
> Ok, thanks, I'll try other test cases to check if everything is ok,
> better being sure.

Hi Marcello,

any news here? I would love to commit your patch. Do you happen to have
a final version ready?

Cheers
Tobi

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: How to make Polly ignore some non-affine memory accesses

Marcello Maggioni
Hi, sorry for the late response. I've been away for a week and after
that probably I missed your email (considering the high amount of
mails that come from LLVMDev :p )
Anyway, now it's just a matter of checking the code , I'm finalizing a
test and after that (a couple of days) I'll post the patch hoping
everything is ok :)

Thank you

Marcello

2011/12/4 Tobias Grosser <[hidden email]>:

> On 11/21/2011 12:44 PM, Marcello Maggioni wrote:
>>
>> 2011/11/21 Tobias Grosser<[hidden email]>:
>>>
>>> On 11/20/2011 04:36 PM, Marcello Maggioni wrote:
>>>>
>>>>
>>>> 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
>>>
>>>
>>> Hi Marcello,
>>>
>>> the SCEV returns SCEVCouldNotCompute in case it cannot analyze an
>>> expression
>>> or if the analysis would be to complicated. I am currently
>>> not sure if this may actually happen when calling getSCEV(), because
>>> getSCEV() could just return a SCEVUnknown referencing the Value itself.
>>> Maybe SCEVCouldNotCompute is just generated by functions like
>>> SE->getBackedgeTakenCount()?
>>>
>>> In case you cannot generate a test case that yields to this, I don't
>>> think
>>> there is a need to try more. Even without such a test case the patch
>>> should
>>> be OK.
>>>
>>> Cheers
>>> Tobi
>>>
>>
>> Ok, thanks, I'll try other test cases to check if everything is ok,
>> better being sure.
>
>
> Hi Marcello,
>
> any news here? I would love to commit your patch. Do you happen to have a
> final version ready?
>
> Cheers
> Tobi
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
123