Don't check side effects for functions outside of SCoP

[sabuasal]

Summary

In r304074 we introduce a patch to accept results from side effect free
functions into SCEV modeling. This causes rejection of cases where the
call is happening outside the SCoP. This patch checks if the call is
outside the Region and treats the results as a parameter (SCEVType::PARAM)
to the SCoP instead of returning SCEVType::INVALID.

[grosser]

Very nice. Thanks for fixing it. Please feel free to commit!

[singam-sanjay]

lib/Support/SCEVValidator.cpp

121

For polyhedral analysis, do we also need the function to evaluate to the same value always (not just side effect free) inside the Scop ? I got this notion from the name of the function.

If that's the case, is it possible to check for that ? ( I have a feeling that it's not feasible )

125

Can we consider llvm::ConstantFP as well ? Or any constant type ?

396

How is this function called ? I don't find any explicit call to this function and the code coverage reports are a month old.

[grosser]

Hi Sanjay,

thanks for your feedback. This is very valuable!

@sameer.abuasal: Our discussion does not seem to hold back your patch, but as your patch triggered it, it seems OK to complete it here. Feel free to commit.

@singam-sanjay: I replied to you inline. Please keep asking if my answers need further clarification.

Best,
Tobias

lib/Support/SCEVValidator.cpp

121

Yes, that's what we need. I believe that we can assume that if a function does not read memory it will always return the same value.

However, there is another bug that slipped in. I assumed mayReadOrWriteMemory corresponds to is-always-executed. This is not the case, so we should likely limit this to functions that are called in the entry block (or at least post-dominate the entry block).

125

We use this for ScalarEvolution expressions, which are all integral. So I am note really seeing if/when we would need other constant types. In general, I made good experience with working use-case driven. Meaning, in case we have a benchmark/code that could benefit from such constructs, we add them.

[grosser]

Forgot one comment.

lib/Support/SCEVValidator.cpp

396

I wrote an email to @sylvestre.ledru (see llvm-dev) to check about the status of the coverage reports.

It is called by the SCEVVisitor which serves as base class for the SCEVValidator.

[singam-sanjay]

lib/Support/SCEVValidator.cpp

121

Yes, that's what we need. I believe that we can assume that if a function does not read memory it will always return the same value.

What about random number generators ?

However, there is another bug that slipped in. I assumed mayReadOrWriteMemory corresponds to is-always-executed. This is not the case, so we should likely limit this to functions that are called in the entry block (or at least post-dominate the entry block).

How does mayReadOrWrite become mustReadOrWrite for those functions ?

125

We use this for ScalarEvolution expressions, which are all integral.

I had this doubt in the context of detecting any ConstCall to a function, including something like sqrt(2.3) .

Thanks for the info ! it was very helpful.

Meaning, in case we have a benchmark/code that could benefit from such constructs, we add them.

Makes sense.

396

I wrote an email to @sylvestre.ledru (see llvm-dev) to check about the status of the coverage reports.

I thought the coverage reports were automated, like CI services, which start compiling as soon as a commit is made.

It is called by the SCEVVisitor which serves as base class for the SCEVValidator.

Oh ok.

[sabuasal]

Thanks @grosser
@efriedma can you please commit on my behalf, I am still waiting for my commit access :)

[sabuasal]

lib/Support/SCEVValidator.cpp

121

Well, random number generators actually modify some object internally to keep trak of the series of random numbers generated so by definition they are not const functions.

[sabuasal]

lib/Support/SCEVValidator.cpp

121

Oh for the second part, in this test case I am we only have declarations of the function g() not the definition so we can't really tell.

[singam-sanjay]

lib/Support/SCEVValidator.cpp

121

Well, random number generators actually modify some object internally to keep trak of the series of random numbers generated so by definition they are not const functions.

So what you're saying is that mayReadOrWrite will return true ?

Even then, I do not understand how llvm could have access to such information. A function for random number generation would be a part of a standard library, how could llvm retrieve such information from a shared-lib.so or a static-lib.a file ?

Oh for the second part, in this test case I am we only have declarations of the function g() not the definition so we can't really tell.

The behaviour of mayReadOrWriteMemory is undefined in this case ?

[efriedma]

mayReadOrWriteMemory() just checks for the "readnone" attribute (http://llvm.org/docs/LangRef.html#function-attributes). If it's set, LLVM knows the call can't read from or write to memory; if it isn't set, the call might write to memory, so mayReadOrWriteMemory() conservatively returns true.

[efriedma]

https://reviews.llvm.org/rL305423

lib/Support/SCEVValidator.cpp

 };
 
 raw_ostream &operator<<(raw_ostream &OS, class ValidatorResult &VR) {
   VR.print(OS);
   return OS;
 }
 
 bool polly::isConstCall(llvm::CallInst *Call) {
   if (Call->mayReadOrWriteMemory())
     return false;
 
   for (auto &Operand : Call->arg_operands())
     if (!isa<ConstantInt>(&Operand))
       return false;
 
   return true;
 }
 
 /// Check if a SCEV is valid in a SCoP.
 struct SCEVValidator
     : public SCEVVisitor<SCEVValidator, class ValidatorResult> {
ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
     }
 
     return ValidatorResult(SCEVType::PARAM, S);
   }
 
   ValidatorResult visitCallInstruction(Instruction *I, const SCEV *S) {
     assert(I->getOpcode() == Instruction::Call && "Call instruction expected");
 
+    if (R->contains(I)) {
       auto Call = cast<CallInst>(I);
 
       if (!isConstCall(Call))
         return ValidatorResult(SCEVType::INVALID, S);
-
+    }
     return ValidatorResult(SCEVType::PARAM, S);
   }
 
   ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
     if (R->contains(I) && ILS) {
       ILS->insert(cast<LoadInst>(I));
       return ValidatorResult(SCEVType::PARAM, S);
     }
ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) {
     if (!CI || CI->isZeroValue())
       return visitGenericInst(SRem, S);
 
     auto *Dividend = SRem->getOperand(0);
     auto *DividendSCEV = SE.getSCEV(Dividend);
     return visit(DividendSCEV);
   }
 
   ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
     Value *V = Expr->getValue();
 
     if (!Expr->getType()->isIntegerTy() && !Expr->getType()->isPointerTy()) {
       DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
       return ValidatorResult(SCEVType::INVALID);
     }
 
     if (isa<UndefValue>(V)) {

test/ScopInfo/constant_functions_outside_scop_as_unknown.ll

+; RUN: opt -polly-process-unprofitable -polly-scops -analyze < %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+
+; CHECK: Region: %for.cond62---%for.cond
+; CHECK: p0: {0,+,1}<nuw><%for.cond>
+; CHECK-NEXT: p1: %param1
+; CHECK-NEXT: p2: %param2
+; CHECK-NEXT: Arrays {
+
+define void @f(i8* %param1) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %hook = phi i8* [ %param1, %entry ], [ %add.ptr201, %cleanup ]
+  br i1 undef, label %for.body, label %for.cond.cleanup
+
+for.body:
+  %param2 = call i32 @g()
+  %add.ptr60 = getelementptr inbounds i8, i8* %hook, i32 %param2
+  br label %for.cond62
+
+for.cond62:
+  %cmp64 = icmp ule i8* %add.ptr60, null
+  br i1 %cmp64, label %for.cond62, label %cleanup
+
+cleanup:
+  %add.ptr201 = getelementptr inbounds i8, i8* %hook, i32 1
+  br label %for.cond
+
+for.cond.cleanup:
+  ret void
+}
+
+declare i32 @g()