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

[Marcello Maggioni]

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