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

[Tobias Grosser]

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.

> 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();

>     /// @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).

> +    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())

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.

Thanks
Tobi

P.S.: Please post patches to the mailing lists.