From 7b8110358912c296a52fed7fdb50f883a74414e0 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Fri, 8 Apr 2016 10:25:58 +0000 Subject: [PATCH] [FIX] Look through div & srem instructions in SCEVs The findValues() function did not look through div & srem instructions that were part of the argument SCEV. However, in different other places we already look through it. This mismatch caused us to preload values in the wrong order. llvm-svn: 265775 --- polly/include/polly/Support/SCEVValidator.h | 8 +-- polly/lib/Analysis/ScopInfo.cpp | 2 +- polly/lib/CodeGen/IslNodeBuilder.cpp | 4 +- polly/lib/Support/SCEVValidator.cpp | 34 +++++++++++-- .../CodeGen/scev-division-invariant-load.ll | 51 +++++++++++++++++++ 5 files changed, 88 insertions(+), 11 deletions(-) create mode 100644 polly/test/Isl/CodeGen/scev-division-invariant-load.ll diff --git a/polly/include/polly/Support/SCEVValidator.h b/polly/include/polly/Support/SCEVValidator.h index 4e1351ce4197..b95c667dd55e 100644 --- a/polly/include/polly/Support/SCEVValidator.h +++ b/polly/include/polly/Support/SCEVValidator.h @@ -37,9 +37,11 @@ void findLoops(const llvm::SCEV *Expr, /// @brief Find the values referenced by SCEVUnknowns in a given SCEV /// expression. /// -/// @param Expr The SCEV expression to scan for SCEVUnknowns. -/// @param Expr A vector into which the found values are inserted. -void findValues(const llvm::SCEV *Expr, llvm::SetVector &Values); +/// @param Expr The SCEV expression to scan for SCEVUnknowns. +/// @param SE The ScalarEvolution analysis for this function. +/// @param Values A vector into which the found values are inserted. +void findValues(const llvm::SCEV *Expr, llvm::ScalarEvolution &SE, + llvm::SetVector &Values); /// Returns true when the SCEV contains references to instructions within the /// region. diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index ff88536846c2..a56318bf7a36 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -3063,7 +3063,7 @@ void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) { SetVector Values; for (const SCEV *Parameter : Parameters) { Values.clear(); - findValues(Parameter, Values); + findValues(Parameter, *SE, Values); if (!Values.count(AccInst)) continue; diff --git a/polly/lib/CodeGen/IslNodeBuilder.cpp b/polly/lib/CodeGen/IslNodeBuilder.cpp index 3068de4915b6..b21136e5a4fb 100644 --- a/polly/lib/CodeGen/IslNodeBuilder.cpp +++ b/polly/lib/CodeGen/IslNodeBuilder.cpp @@ -304,7 +304,7 @@ void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For, addReferencesFromStmtUnionSet(Schedule, References); for (const SCEV *Expr : SCEVs) { - findValues(Expr, Values); + findValues(Expr, SE, Values); findLoops(Expr, Loops); } @@ -852,7 +852,7 @@ bool IslNodeBuilder::materializeValue(isl_id *Id) { // check if any value refered to in ParamSCEV is an invariant load // and if so make sure its equivalence class is preloaded. SetVector Values; - findValues(ParamSCEV, Values); + findValues(ParamSCEV, SE, Values); for (auto *Val : Values) { // Check if the value is an instruction in a dead block within the SCoP diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp index 0bece55de0ac..4b91025fd0e0 100644 --- a/polly/lib/Support/SCEVValidator.cpp +++ b/polly/lib/Support/SCEVValidator.cpp @@ -560,21 +560,45 @@ void findLoops(const SCEV *Expr, SetVector &Loops) { /// Find all values referenced in SCEVUnknowns. class SCEVFindValues { + ScalarEvolution &SE; SetVector &Values; public: - SCEVFindValues(SetVector &Values) : Values(Values) {} + SCEVFindValues(ScalarEvolution &SE, SetVector &Values) + : SE(SE), Values(Values) {} bool follow(const SCEV *S) { - if (const SCEVUnknown *Unknown = dyn_cast(S)) + const SCEVUnknown *Unknown = dyn_cast(S); + if (!Unknown) + return true; + + Instruction *Inst = dyn_cast(Unknown->getValue()); + if (!Inst || (Inst->getOpcode() != Instruction::SRem && + Inst->getOpcode() != Instruction::SDiv)) { Values.insert(Unknown->getValue()); - return true; + return false; + } + + auto *Dividend = SE.getSCEV(Inst->getOperand(1)); + if (!isa(Dividend)) { + Values.insert(Unknown->getValue()); + return false; + } + + auto *Divisor = SE.getSCEV(Inst->getOperand(0)); + SCEVFindValues FindValues(SE, Values); + SCEVTraversal ST(FindValues); + ST.visitAll(Dividend); + ST.visitAll(Divisor); + + return false; } bool isDone() { return false; } }; -void findValues(const SCEV *Expr, SetVector &Values) { - SCEVFindValues FindValues(Values); +void findValues(const SCEV *Expr, ScalarEvolution &SE, + SetVector &Values) { + SCEVFindValues FindValues(SE, Values); SCEVTraversal ST(FindValues); ST.visitAll(Expr); } diff --git a/polly/test/Isl/CodeGen/scev-division-invariant-load.ll b/polly/test/Isl/CodeGen/scev-division-invariant-load.ll new file mode 100644 index 000000000000..3af47b6be5a4 --- /dev/null +++ b/polly/test/Isl/CodeGen/scev-division-invariant-load.ll @@ -0,0 +1,51 @@ +; RUN: opt %loadPolly -S -polly-codegen < %s +; +; Check that we generate valid code as we did not use the preloaded +; value of %tmp1 for the access function of the preloaded %tmp4. +; +; ModuleID = 'bug.ll' +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +%struct.frame_store = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, %struct.picture*, %struct.picture*, %struct.picture* } +%struct.picture = type { i32, i32, i32, i32, i32, i32, [6 x [33 x i64]], [6 x [33 x i64]], [6 x [33 x i64]], [6 x [33 x i64]], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i16**, i16*, i16*, i16**, i16**, i16***, i8*, i16***, i64***, i64***, i16****, i8**, i8**, %struct.picture*, %struct.picture*, %struct.picture*, i32, i32, i32, i32, i32, i32, i32 } + +define void @dpb_split_field(%struct.frame_store* %fs) { +entry: + br label %for.body544 + +for.body544: ; preds = %if.end908, %for.body544.lr.ph + %indvars.iv87 = phi i64 [ 0, %entry ], [ %indvars.iv.next88, %if.end908 ] + %tmp = phi %struct.picture* [ undef, %entry ], [ %tmp6, %if.end908 ] + br label %land.lhs.true563 + +land.lhs.true563: ; preds = %for.body544 + %size_x551 = getelementptr inbounds %struct.picture, %struct.picture* %tmp, i64 0, i32 18 + %tmp1 = load i32, i32* %size_x551, align 8 + %div552 = sdiv i32 %tmp1, 16 + %tmp2 = trunc i64 %indvars.iv87 to i32 + %div554 = sdiv i32 %tmp2, 4 + %mul555 = mul i32 %div552, %div554 + %tmp9 = add i32 %mul555, 0 + %tmp10 = shl i32 %tmp9, 1 + %add559 = add i32 %tmp10, 0 + %idxprom564 = sext i32 %add559 to i64 + %mb_field566 = getelementptr inbounds %struct.picture, %struct.picture* %tmp, i64 0, i32 31 + %tmp3 = load i8*, i8** %mb_field566, align 8 + %arrayidx567 = getelementptr inbounds i8, i8* %tmp3, i64 %idxprom564 + %tmp4 = load i8, i8* %arrayidx567, align 1 + %tobool569 = icmp eq i8 %tmp4, 0 + br i1 %tobool569, label %if.end908, label %if.then570 + +if.then570: ; preds = %land.lhs.true563 + %frame = getelementptr inbounds %struct.frame_store, %struct.frame_store* %fs, i64 0, i32 10 + %tmp5 = load %struct.picture*, %struct.picture** %frame, align 8 + br label %if.end908 + +if.end908: ; preds = %if.then570, %land.lhs.true563 + %tmp6 = phi %struct.picture* [ %tmp, %land.lhs.true563 ], [ undef, %if.then570 ] + %indvars.iv.next88 = add nuw nsw i64 %indvars.iv87, 1 + br i1 undef, label %for.body544, label %for.inc912 + +for.inc912: ; preds = %if.end908 + ret void +} -- 2.34.1