diff options
| -rwxr-xr-x | polly/include/polly/ScopDetection.h | 9 | ||||
| -rw-r--r-- | polly/lib/Analysis/ScopDetection.cpp | 55 | ||||
| -rw-r--r-- | polly/test/ScopDetect/base_pointer.ll | 71 |
3 files changed, 130 insertions, 5 deletions
diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h index 63c5c1bbe72..0450311e256 100755 --- a/polly/include/polly/ScopDetection.h +++ b/polly/include/polly/ScopDetection.h @@ -152,6 +152,15 @@ class ScopDetection : public FunctionPass { /// @return The failure message why the alias is invalid. std::string formatInvalidAlias(AliasSet &AS) const; + /// @brief Check if a value is invariant in the region Reg. + /// + /// @param Val Value to check for invariance. + /// @param Reg The region to consider for the invariance of Val. + /// + /// @return True if the value represented by Val is invariant in the region + /// identified by Reg. + bool isInvariant(const Value &Val, const Region &Reg) const; + /// @brief Check if a memory access can be part of a Scop. /// /// @param Inst The instruction accessing the memory. diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp index 9456ab3afa5..87314b88200 100644 --- a/polly/lib/Analysis/ScopDetection.cpp +++ b/polly/lib/Analysis/ScopDetection.cpp @@ -348,6 +348,53 @@ std::string ScopDetection::formatInvalidAlias(AliasSet &AS) const { return OS.str(); } +bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const { + // A reference to function argument or constant value is invariant. + if (isa<Argument>(Val) || isa<Constant>(Val)) + return true; + + const Instruction *I = dyn_cast<Instruction>(&Val); + if (!I) + return false; + + if (!Reg.contains(I)) + return true; + + if (I->mayHaveSideEffects()) + return false; + + // When Val is a Phi node, it is likely not invariant. We do not check whether + // Phi nodes are actually invariant, we assume that Phi nodes are usually not + // invariant. Recursively checking the operators of Phi nodes would lead to + // infinite recursion. + if (isa<PHINode>(*I)) + return false; + + // Check that all operands of the instruction are + // themselves invariant. + const Instruction::const_op_iterator OE = I->op_end(); + for (Instruction::const_op_iterator OI = I->op_begin(); OI != OE; ++OI) { + if (!isInvariant(**OI, Reg)) + return false; + } + + // When the instruction is a load instruction, check that no write to memory + // in the region aliases with the load. + if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { + AliasAnalysis::Location Loc = AA->getLocation(LI); + const Region::const_block_iterator BE = Reg.block_end(); + // Check if any basic block in the region can modify the location pointed to + // by 'Loc'. If so, 'Val' is (likely) not invariant in the region. + for (Region::const_block_iterator BI = Reg.block_begin(); BI != BE; ++BI) { + const BasicBlock &BB = **BI; + if (AA->canBasicBlockModify(BB, Loc)) + return false; + } + } + + return true; +} + bool ScopDetection::isValidMemoryAccess(Instruction &Inst, DetectionContext &Context) const { Value *Ptr = getPointerOperand(Inst); @@ -370,6 +417,14 @@ bool ScopDetection::isValidMemoryAccess(Instruction &Inst, return false; } + // Check that the base address of the access is invariant in the current + // region. + if (!isInvariant(*BaseValue, Context.CurRegion)) { + INVALID(AffFunc, + "Base address not invariant in current region:" << *BaseValue); + return false; + } + AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); if (!AllowNonAffine && diff --git a/polly/test/ScopDetect/base_pointer.ll b/polly/test/ScopDetect/base_pointer.ll index 45bd6b78bbc..ee05d13a3b1 100644 --- a/polly/test/ScopDetect/base_pointer.ll +++ b/polly/test/ScopDetect/base_pointer.ll @@ -151,9 +151,9 @@ entry: for.i: %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ] %ptr = phi float* [ %ptr.next, %for.i.inc ], [ %A, %entry ] -; To get a PHI node inside a SCoP, that can not be analyzed but -; for which the surrounding scop is normally still valid we use a function -; without any sideeffects. +; To get a PHI node inside a SCoP that can not be analyzed but +; for which the surrounding SCoP is normally still valid we use a function +; without any side effects. %ptr.next = call float* @getNextBasePtr(float* %ptr) br label %S1 @@ -182,8 +182,8 @@ entry: for.i: %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ] ; To get an instruction inside a region, we use a function without side -; effects on which SCEV blocks, but for which still is clear that the return -; value remains invariant throughout the whole loop. +; effects on which SCEV blocks, but for which it is still clear that the +; return value remains invariant throughout the whole loop. %ptr = call float* @getNextBasePtr(float* %A) br label %S1 @@ -234,3 +234,64 @@ exit: ; CHECK-LABEL: base_pointer_is_inst_inside_invariant_2 ; CHECK: Valid Region for Scop: for.i => exit + +declare float* @getNextBasePtr3(float*, i64) readnone nounwind + +define void @base_pointer_is_inst_inside_variant(i64 %n, float* %A) { +entry: + br label %for.i + +for.i: + %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ] + %ptr = call float* @getNextBasePtr3(float* %A, i64 %indvar.i) + %ptr2 = call float* @getNextBasePtr(float* %ptr) + br label %S1 + +S1: + %conv = sitofp i64 %indvar.i to float + %arrayidx5 = getelementptr float* %ptr2, i64 %indvar.i + store float %conv, float* %arrayidx5, align 4 + br label %for.i.inc + +for.i.inc: + %indvar.i.next = add i64 %indvar.i, 1 + %exitcond.i = icmp ne i64 %indvar.i.next, %n + br i1 %exitcond.i, label %for.i, label %exit + +exit: + ret void +} + +; CHECK: base_pointer_is_inst_inside_variant +; CHECK-NOT: Valid Region for Scop + +define void @base_pointer_is_ptr2ptr(float** noalias %A, i64 %n) { +entry: + br label %for.i + +for.i: + %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ] + %arrayidx = getelementptr float** %A, i64 %indvar.i + br label %for.j + +for.j: + %indvar.j = phi i64 [ 0, %for.i ], [ %indvar.j.next, %for.j ] + %conv = sitofp i64 %indvar.i to float + %basepointer = load float** %arrayidx, align 8 + %arrayidx5 = getelementptr float* %basepointer, i64 %indvar.j + store float %conv, float* %arrayidx5, align 4 + %indvar.j.next = add i64 %indvar.j, 1 + %exitcond.j = icmp ne i64 %indvar.j.next, %n + br i1 %exitcond.j, label %for.j, label %for.i.inc + +for.i.inc: + %indvar.i.next = add i64 %indvar.i, 1 + %exitcond.i = icmp ne i64 %indvar.i.next, %n + br i1 %exitcond.i, label %for.i, label %exit + +exit: + ret void +} + +; CHECK: base_pointer_is_ptr2ptr +; CHECK-NOT: Valid Region for Scop |
