diff --git a/include/polly/Support/AffineSCEVIterator.h b/include/polly/Support/AffineSCEVIterator.h
index 7036c60..c845a49 100755
--- a/include/polly/Support/AffineSCEVIterator.h
+++ b/include/polly/Support/AffineSCEVIterator.h
@@ -191,7 +191,8 @@ private:
return ret;
}
- // The step is not a constant. Then this AddRec is not Affine
+ // The step is not a constant. Then this AddRec is not Affine or
+ // no canonical induction variable found.
// Fall through.
}
}
--
1.7.3.3
diff --git a/lib/IndependentBlocks.cpp b/lib/IndependentBlocks.cpp
index 9083c48..6154000 100644
--- a/lib/IndependentBlocks.cpp
+++ b/lib/IndependentBlocks.cpp
@@ -339,7 +339,7 @@ bool IndependentBlocks::splitExitBlock(Region *R) {
Reg->replaceExit(NewExit);
}
- RI->setRegionFor(NewExit, R);
+ RI->setRegionFor(NewExit, R->getParent());
return true;
}
--
1.7.3.3
diff --git a/test/CodeGen/20100717.ll b/test/CodeGen/20100717.ll
index 8b8f7f6..c97a2ea 100644
--- a/test/CodeGen/20100717.ll
+++ b/test/CodeGen/20100717.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-codegen -disable-output < %s
+; RUN: opt %loadPolly %defaultOpts -polly-codegen -disable-output < %s
; ModuleID = 'bugpoint-reduced-simplified.bc'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"
diff --git a/test/ScopInfo/bad_loop_1.ll b/test/ScopInfo/bad_loop_1.ll
index 09831de..e5421e0 100644
--- a/test/ScopInfo/bad_loop_1.ll
+++ b/test/ScopInfo/bad_loop_1.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=INDVAR
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=INDVAR
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
;void f(long a[][128], long N, long M) {
diff --git a/test/ScopInfo/cast.ll b/test/ScopInfo/cast.ll
index 01af394..f26e7c4 100644
--- a/test/ScopInfo/cast.ll
+++ b/test/ScopInfo/cast.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
;void f(long a[], long N, long M) {
; long i, j, k;
diff --git a/test/ScopInfo/indvar_out_of_loop.ll b/test/ScopInfo/indvar_out_of_loop.ll
index 943280d..c5a6f58 100644
--- a/test/ScopInfo/indvar_out_of_loop.ll
+++ b/test/ScopInfo/indvar_out_of_loop.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
diff --git a/test/ScopInfo/indvar_out_of_loop_1.ll b/test/ScopInfo/indvar_out_of_loop_1.ll
index 3d4064f..2ad2aa1 100644
--- a/test/ScopInfo/indvar_out_of_loop_1.ll
+++ b/test/ScopInfo/indvar_out_of_loop_1.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
;void f(long a[], long N) {
diff --git a/test/ScopInfo/indvar_out_of_loop_2.ll b/test/ScopInfo/indvar_out_of_loop_2.ll
index bbf8b56..4cb0cf4 100644
--- a/test/ScopInfo/indvar_out_of_loop_2.ll
+++ b/test/ScopInfo/indvar_out_of_loop_2.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
diff --git a/test/ScopInfo/loop_affine_bound_0.ll b/test/ScopInfo/loop_affine_bound_0.ll
index 9ff3175..205cf25 100644
--- a/test/ScopInfo/loop_affine_bound_0.ll
+++ b/test/ScopInfo/loop_affine_bound_0.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
diff --git a/test/ScopInfo/loop_affine_bound_1.ll b/test/ScopInfo/loop_affine_bound_1.ll
index 745f388..f756799 100644
--- a/test/ScopInfo/loop_affine_bound_1.ll
+++ b/test/ScopInfo/loop_affine_bound_1.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
;void f(long a[][128], long N, long M) {
diff --git a/test/ScopInfo/loop_affine_bound_2.ll b/test/ScopInfo/loop_affine_bound_2.ll
index edbddff..69560b6 100644
--- a/test/ScopInfo/loop_affine_bound_2.ll
+++ b/test/ScopInfo/loop_affine_bound_2.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
;void f(long a[][128], long N, long M) {
diff --git a/test/ScopInfo/loop_complex_parameter.ll b/test/ScopInfo/loop_complex_parameter.ll
index 7e97d15..c10d410 100644
--- a/test/ScopInfo/loop_complex_parameter.ll
+++ b/test/ScopInfo/loop_complex_parameter.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
diff --git a/test/ScopInfo/loop_depth_0.ll b/test/ScopInfo/loop_depth_0.ll
index fe7feed..f846e7d 100644
--- a/test/ScopInfo/loop_depth_0.ll
+++ b/test/ScopInfo/loop_depth_0.ll
@@ -1,5 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=NOCIV
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
;void f(long a[][128], long N, long M) {
; long i, j, k;
@@ -55,4 +54,3 @@ return: ; preds = %bb6
}
; CHECK: Scop: entry => <Function Return> Parameters: (%N, %M, ), Max Loop Depth: 2
-; NOCIV: Scop: entry => bb6 Parameters: (%N, %M, ), Max Loop Depth: 2
\ No newline at end of file
diff --git a/test/ScopInfo/loop_multi_exits.ll b/test/ScopInfo/loop_multi_exits.ll
index 859fc77..0898ca5 100644
--- a/test/ScopInfo/loop_multi_exits.ll
+++ b/test/ScopInfo/loop_multi_exits.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=INDVAR
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=INDVAR
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
;From pollybench.
diff --git a/test/ScopInfo/nest_loop_0.ll b/test/ScopInfo/nest_loop_0.ll
index f1cb7b1..ea4e096 100644
--- a/test/ScopInfo/nest_loop_0.ll
+++ b/test/ScopInfo/nest_loop_0.ll
@@ -1,6 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=INDVARS
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
-; RUN: opt %loadPolly %defaultOpts -O3 -indvars -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=WITHAF
;void f(long a[][128], long N, long M) {
; long i, j;
@@ -42,10 +40,3 @@ return: ; preds = %bb3, %entry
}
; CHECK: Scop: bb2.preheader => return Parameters: (%M, %N, ), Max Loop Depth: 2
-; INDVARS: Scop: bb2.preheader => return Parameters: (%N, %M, ), Max Loop Depth: 2
-; WITHAF: Scop: bb2.preheader => return Parameters: (%N, %M, ), Max Loop Depth: 2
-; WITHAF: Bounds of Loop: bb2.preheader: { 1 * %M + -1 }
-; WITHAF: Bounds of Loop: bb1: { 1 * %N + -1 }
-; WITHAF: BB: bb1{
-; WITHAF: Writes %a[1024 * {0,+,1}<nuw><nsw><%bb1> + 8 * {0,+,1}<%bb2.preheader> + 0]
-; WITHAF: }
diff --git a/test/ScopInfo/out_of_loop_0.ll b/test/ScopInfo/out_of_loop_0.ll
index 959fad8..776f96a 100644
--- a/test/ScopInfo/out_of_loop_0.ll
+++ b/test/ScopInfo/out_of_loop_0.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
;void f(long a[], long N, long M) {
diff --git a/test/ScopInfo/simple_loop_0.ll b/test/ScopInfo/simple_loop_0.ll
index 2548315..40900ca 100644
--- a/test/ScopInfo/simple_loop_0.ll
+++ b/test/ScopInfo/simple_loop_0.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=WITHAF
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s -check-prefix=WITHAF
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
;void f(long a[], long N) {
diff --git a/test/ScopInfo/simple_loop_1.ll b/test/ScopInfo/simple_loop_1.ll
index 2dca930..f718d1b 100644
--- a/test/ScopInfo/simple_loop_1.ll
+++ b/test/ScopInfo/simple_loop_1.ll
@@ -1,4 +1,4 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
; XFAIL: *
;void f(int a[], int N) {
diff --git a/test/ScopInfo/static_known_0.ll b/test/ScopInfo/static_known_0.ll
index 0e4a62b..799b6c6 100644
--- a/test/ScopInfo/static_known_0.ll
+++ b/test/ScopInfo/static_known_0.ll
@@ -1,6 +1,5 @@
-; RUN: opt %loadPolly %defaultOpts -indvars -polly-analyze-ir -analyze %s | FileCheck %s
-; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
-; XFAIL: *
+; RUN: opt %loadPolly %defaultOpts -polly-analyze-ir -analyze %s | FileCheck %s
+
;void f(long a[], long N) {
; long M = rnd();
@@ -37,4 +36,4 @@ bb2: ; preds = %bb, %entry
declare i64 @rnd(...)
-; CHECK: Scop: entry => <Function Return> Parameters: (%1, %N, )
+; CHECK: Scop: bb => bb2 Parameters: (%0, ), Max Loop Depth: 1
--
1.7.3.3
diff --git a/lib/RegionSimplify.cpp b/lib/RegionSimplify.cpp
index 875ecf9..f34f1f4 100644
--- a/lib/RegionSimplify.cpp
+++ b/lib/RegionSimplify.cpp
@@ -16,9 +16,12 @@
#include "llvm/Instructions.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/RegionPass.h"
#include "llvm/Analysis/RegionInfo.h"
+#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#define DEBUG_TYPE "region-simplify"
@@ -76,7 +79,13 @@ void RegionSimplify::print(raw_ostream &O, const Module *M) const {
}
void RegionSimplify::getAnalysisUsage(AnalysisUsage &AU) const {
+ // Function SplitBlockPredecessors currently updates/preserves AliasAnalysis,
+ /// DominatorTree, LoopInfo, and LCCSA but no other analyses.
+ //AU.addPreserved<AliasAnalysis>(); Break SCEV-AA
AU.addPreserved<DominatorTree> ();
+ AU.addPreserved<LoopInfo>();
+ AU.addPreservedID(LCSSAID);
+
AU.addPreserved<RegionInfo> ();
AU.addRequired<RegionInfo> ();
}
--
1.7.3.3
diff --git a/lib/RegionSimplify.cpp b/lib/RegionSimplify.cpp
index f34f1f4..403d3ae 100644
--- a/lib/RegionSimplify.cpp
+++ b/lib/RegionSimplify.cpp
@@ -33,15 +33,13 @@ STATISTIC(NumExits, "The # of created exit edges");
namespace {
class RegionSimplify: public RegionPass {
- bool modified;
- Region *CR;
+ // Remember the modified region.
+ Region *r;
void createSingleEntryEdge(Region *R);
void createSingleExitEdge(Region *R);
public:
static char ID;
- explicit RegionSimplify() :
- RegionPass(ID) {
- }
+ explicit RegionSimplify() : RegionPass(ID), r(0) {}
virtual void print(raw_ostream &O, const Module *M) const;
@@ -61,19 +59,25 @@ namespace polly {
}
void RegionSimplify::print(raw_ostream &O, const Module *M) const {
- if (!modified)
- return;
+ if (r == 0) return;
+
+ BasicBlock *enteringBlock = r->getEnteringBlock();
+ BasicBlock *exitingBlock = r->getExitingBlock();
- BasicBlock *enteringBlock = CR->getEnteringBlock();
- BasicBlock *exitingBlock = CR->getExitingBlock();
+ O << "Region: " << r->getNameStr() << " Edges:\t";
- O << "\nRegion: [" << CR->getNameStr() << "] Edges:\n";
if (enteringBlock)
- O << " Entry: ]" << enteringBlock->getNameStr() << " => "
- << enteringBlock->getNameStr() << "]\n";
- if (exitingBlock)
- O << " Exit: [" << exitingBlock->getNameStr() << " => "
- << exitingBlock->getNameStr() << "[\n";
+ O << "Entering: [" << enteringBlock->getNameStr() << " -> "
+ << r->getEntry()->getName() << "], ";
+
+ if (exitingBlock) {
+ O << "Exiting: [" << exitingBlock->getNameStr() << " -> ";
+ if (r->getExit())
+ O << r->getExit()->getName();
+ else
+ O << "<return>";
+ O << "]";
+ }
O << "\n";
}
@@ -179,7 +183,7 @@ void RegionSimplify::createSingleExitEdge(Region *R) {
}
bool RegionSimplify::runOnRegion(Region *R, RGPassManager &RGM) {
- modified = false;
+ r = 0;
if (!R->isTopLevelRegion()) {
@@ -187,17 +191,17 @@ bool RegionSimplify::runOnRegion(Region *R, RGPassManager &RGM) {
if (!(R->getEnteringBlock())
&& (pred_begin(R->getEntry()) != pred_end(R->getEntry()))) {
createSingleEntryEdge(R);
- modified = true;
+ r = R;
++NumEntries;
}
// split exit node if the region has multiple exit edges
if (!(R->getExitingBlock())) {
createSingleExitEdge(R);
- modified = true;
+ r = R;
++NumExits;
}
}
- return modified;
+ return r != 0;
}
--
1.7.3.3
diff --git a/lib/RegionSimplify.cpp b/lib/RegionSimplify.cpp
index 403d3ae..eb61e38 100644
--- a/lib/RegionSimplify.cpp
+++ b/lib/RegionSimplify.cpp
@@ -116,6 +116,10 @@ void RegionSimplify::createSingleEntryEdge(Region *R) {
// the entry node with their parents.
// all parent regions whose entry is oldEntry are updated with newEntry
Region *r = R->getParent();
+
+ // Put the new entry to R's parent.
+ RI->setRegionFor(newEntry,r);
+
while (r->getEntry() == oldEntry && !r->isTopLevelRegion()) {
r->replaceEntry(newEntry);
r = r->getParent();
--
1.7.3.3
diff --git a/test/ScopInfo/nest_loop_0.ll b/test/ScopInfo/nest_loop_0.ll
index ea4e096..1a6ce2c 100644
--- a/test/ScopInfo/nest_loop_0.ll
+++ b/test/ScopInfo/nest_loop_0.ll
@@ -39,4 +39,4 @@ return: ; preds = %bb3, %entry
ret void
}
-; CHECK: Scop: bb2.preheader => return Parameters: (%M, %N, ), Max Loop Depth: 2
+; CHECK: Scop: bb2.preheader => return.single_exit Parameters: (%M, %N, ), Max Loop Depth: 2
diff --git a/test/ScopInfo/static_known_0.ll b/test/ScopInfo/static_known_0.ll
index 799b6c6..0435d50 100644
--- a/test/ScopInfo/static_known_0.ll
+++ b/test/ScopInfo/static_known_0.ll
@@ -36,4 +36,4 @@ bb2: ; preds = %bb, %entry
declare i64 @rnd(...)
-; CHECK: Scop: bb => bb2 Parameters: (%0, ), Max Loop Depth: 1
+; CHECK: Scop: bb => bb2.single_exit Parameters: (%0, ), Max Loop Depth: 1
diff --git a/test/lit.site.cfg.in b/test/lit.site.cfg.in
index ecf977e..a525c98 100644
--- a/test/lit.site.cfg.in
+++ b/test/lit.site.cfg.in
@@ -19,7 +19,7 @@ except KeyError,e:
config.substitutions.append(('%loadPolly', '-load '
+ config.llvm_libs_dir + '/LLVMPolly.so '))
-config.substitutions.append(('%defaultOpts', ' -polly-prepare -basicaa -scev-aa '))
+config.substitutions.append(('%defaultOpts', ' -basicaa -polly-prepare -polly-region-simplify -scev-aa '))
config.substitutions.append(('%polybenchOpts', ' -O3 -loop-simplify -indvars '))
# Let the main config do the real work.
diff --git a/test/polybench/datamining/covariance/covariance_without_param.ll b/test/polybench/datamining/covariance/covariance_without_param.ll
index 67f0d83..a0c1f51 100644
--- a/test/polybench/datamining/covariance/covariance_without_param.ll
+++ b/test/polybench/datamining/covariance/covariance_without_param.ll
@@ -1,4 +1,7 @@
; RUN: opt %loadPolly %defaultOpts -polly-detect -polly-cloog -analyze %s | FileCheck %s
+; region-simplify make polly fail to detect the canonical induction variable.
+; XFAIL:*
+
; ModuleID = './datamining/covariance/covariance_without_param.ll'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"
diff --git a/test/polybench/linear-algebra/solvers/lu/lu_with_param.ll b/test/polybench/linear-algebra/solvers/lu/lu_with_param.ll
index fa9e616..f122643 100644
--- a/test/polybench/linear-algebra/solvers/lu/lu_with_param.ll
+++ b/test/polybench/linear-algebra/solvers/lu/lu_with_param.ll
@@ -1,4 +1,7 @@
; RUN: opt %loadPolly %defaultOpts -polly-detect -analyze %s | FileCheck %s
+; region-simplify make polly fail to detect the canonical induction variable.
+; XFAIL:*
+
; ModuleID = './linear-algebra/solvers/lu/lu_with_param.ll'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"
diff --git a/test/polybench/linear-algebra/solvers/lu/lu_without_param.ll b/test/polybench/linear-algebra/solvers/lu/lu_without_param.ll
index 29188e6..93a3c1b 100644
--- a/test/polybench/linear-algebra/solvers/lu/lu_without_param.ll
+++ b/test/polybench/linear-algebra/solvers/lu/lu_without_param.ll
@@ -1,4 +1,7 @@
; RUN: opt %loadPolly %defaultOpts -polly-detect -analyze %s | FileCheck %s
+; region-simplify make polly fail to detect the canonical induction variable.
+; XFAIL:*
+
; ModuleID = './linear-algebra/solvers/lu/lu_without_param.ll'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"
diff --git a/test/polybench/linear-algebra/solvers/ludcmp/ludcmp_without_param.ll b/test/polybench/linear-algebra/solvers/ludcmp/ludcmp_without_param.ll
index ab76fea..2fa70af 100644
--- a/test/polybench/linear-algebra/solvers/ludcmp/ludcmp_without_param.ll
+++ b/test/polybench/linear-algebra/solvers/ludcmp/ludcmp_without_param.ll
@@ -1,4 +1,7 @@
; RUN: opt %loadPolly %defaultOpts -polly-detect -polly-cloog -analyze %s | FileCheck %s
+; region-simplify make polly fail to detect the canonical induction variable.
+; XFAIL:*
+
; ModuleID = './linear-algebra/solvers/ludcmp/ludcmp_without_param.ll'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"
diff --git a/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll b/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll
index fea93ec..58fa7a1 100644
--- a/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll
+++ b/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll
@@ -1,4 +1,7 @@
; RUN: opt %loadPolly %defaultOpts -polly-detect -analyze %s | FileCheck %s
+; region-simplify causes: Non canonical PHI node found
+; XFAIL:*
+
; ModuleID = './stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"
--
1.7.3.3
diff --git a/lib/RegionSimplify.cpp b/lib/RegionSimplify.cpp
index eb61e38..5e6e9c7 100644
--- a/lib/RegionSimplify.cpp
+++ b/lib/RegionSimplify.cpp
@@ -25,6 +25,7 @@
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#define DEBUG_TYPE "region-simplify"
+#include "llvm/Support/Debug.h"
using namespace llvm;
@@ -156,6 +157,8 @@ void RegionSimplify::createSingleExitEdge(Region *R) {
if (R->contains(*PI))
Preds.push_back(*PI);
+ DEBUG(dbgs() << "Going to create single exit for:\n");
+ DEBUG(R->print(dbgs(), true, 0, Region::PrintRN));
BasicBlock *newExit = SplitBlockPredecessors(oldExit,
Preds.data(), Preds.size(),
".single_exit", this);
@@ -165,6 +168,7 @@ void RegionSimplify::createSingleExitEdge(Region *R) {
// this region and it affects only this region and all of its children.
// The new split node belongs to this region
RI->setRegionFor(newExit,R);
+ DEBUG(dbgs() << "Adding new exiting block: " << newExit->getName() << '\n');
// all children of this region whose exit is oldExit is changed to newExit
std::vector<Region *> RQ;
@@ -182,8 +186,12 @@ void RegionSimplify::createSingleExitEdge(Region *R) {
RQ.push_back(*RI);
R->replaceExit(newExit);
+ DEBUG(dbgs() << "Replacing exit for:\n");
+ DEBUG(R->print(dbgs(), true, 0, Region::PrintRN));
}
+ DEBUG(dbgs() << "After split exit:\n");
+ DEBUG(R->print(dbgs(), true, 0, Region::PrintRN));
}
bool RegionSimplify::runOnRegion(Region *R, RGPassManager &RGM) {
--
1.7.3.3
diff --git a/lib/Analysis/ScopDetection.cpp b/lib/Analysis/ScopDetection.cpp
index 389b490..50a6af0 100644
--- a/lib/Analysis/ScopDetection.cpp
+++ b/lib/Analysis/ScopDetection.cpp
@@ -571,6 +571,13 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) const {
return false;
}
+ // Only a simple region is allowed.
+ if (!R.isSimple()) {
+ DEBUG(dbgs() << "Region not simple: " << R.getNameStr() << '\n');
+ STATSCOP(SimpleRegion);
+ return false;
+ }
+
if (!allBlocksValid(Context))
return false;
--
1.7.3.3
diff --git a/lib/Analysis/ScopDetection.cpp b/lib/Analysis/ScopDetection.cpp
index 50a6af0..8ceb2e3 100644
--- a/lib/Analysis/ScopDetection.cpp
+++ b/lib/Analysis/ScopDetection.cpp
@@ -98,6 +98,7 @@ bool ScopDetection::isValidAffineFunction(const SCEV *S, Region &RefRegion,
assert(S && "S must not be null!");
bool isMemoryAccess = (BasePtr != 0);
if (isMemoryAccess) *BasePtr = 0;
+ DEBUG(dbgs() << "Checking " << *S << " ... ");
if (isa<SCEVCouldNotCompute>(S)) {
DEBUG(dbgs() << "Non Affine: SCEV could not be computed\n");
@@ -129,7 +130,10 @@ bool ScopDetection::isValidAffineFunction(const SCEV *S, Region &RefRegion,
assert(I->second->isOne() && "Only one as pointer coefficient allowed.\n");
const SCEVUnknown *BaseAddr = dyn_cast<SCEVUnknown>(Var);
- if (!BaseAddr || isa<UndefValue>(BaseAddr->getValue())) return false;
+ if (!BaseAddr || isa<UndefValue>(BaseAddr->getValue())){
+ DEBUG(dbgs() << "Cannot handle base: " << *Var << "\n");
+ return false;
+ }
// BaseAddr must be invariant in Scop.
if (!isParameter(BaseAddr, RefRegion, *LI, *SE)) {
@@ -152,6 +156,7 @@ bool ScopDetection::isValidAffineFunction(const SCEV *S, Region &RefRegion,
return false;
}
+ DEBUG(dbgs() << " is affine.\n");
return !isMemoryAccess || (*BasePtr != 0);
}
--
1.7.3.3
We should always have a canonical induction variable, as the
ScopDetection is checking this, no?
Tobi
OK.
Tobi
Tobi
OK.
Tobi
This code becomes useless and should be removed in the very same commit:
(About 10 lines later in this file)
BasicBlock *entry = R.getEntry();
if (Loop *L = LI->getLoopFor(entry))
if (L->getHeader() == entry && !R.isSimple()) {
errs() << "Warning: Run a region simplify pass to increase
coverage\n";
if (!Context.Verifying) {
STATSCOP(SimpleRegion);
}
OK.
> # Let the main config do the real work.
> diff --git a/test/polybench/datamining/covariance/covariance_without_param.ll b/test/polybench/datamining/covariance/covariance_without_param.ll
> index 67f0d83..a0c1f51 100644
> --- a/test/polybench/datamining/covariance/covariance_without_param.ll
> +++ b/test/polybench/datamining/covariance/covariance_without_param.ll
> @@ -1,4 +1,7 @@
> ; RUN: opt %loadPolly %defaultOpts -polly-detect -polly-cloog -analyze %s | FileCheck %s
> +; region-simplify make polly fail to detect the canonical induction variable.
> +; XFAIL:*
The reason here is a bug in region-simplify. It is reordering the
operands of the canonical induction variable (the first one is not any
more the edge pointing into the loop, but it is the back edge of the
loop). We should fix this and add a test case for this to
'test/RegionSimplify'.
> --- a/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll
> +++ b/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll
> @@ -1,4 +1,7 @@
> ; RUN: opt %loadPolly %defaultOpts -polly-detect -analyze %s | FileCheck %s
> +; region-simplify causes: Non canonical PHI node found
> +; XFAIL:*
Mh. I do not get this bug yet. Maybe the same as the previous one?
I think you can commit this with those XFAILS and then we can work on
fixing them.
Cheers and thanks for your work
Tobi
P.S.: I forgot to CC you on the other mails.
Not exactly, the non-canonical induction variable may comes from the
outer loop, one example is:
for (i = 0; i < N; ++i) { // i can not be recognized as canonical
induction variable
scop {
for (j = 0; j < N; ++i)
a[i][j] ...
}
}
In this example, the outer loop do not detected as a scop, and a
access function in scop refers i, so we get the scev like this:
{{(8200 + @A),+,8200}<outerloop>,+,8192}<innerloop>
and {(8200 + @A),+,8200}<outerloop> not can not decompose further to
the A + 8200*IV of outerloop ....
I think we can fix this by run -polly-prepare after
-polly-region-simplify, i will try this out.
best regards
ether
>
> Tobi
>
Forgot to metion a problem about the regioninfo pass and regionsimplify pass:
If you drop the region tree and re-detect it again after
region-simplify (this happen when i run -basicaa after
region-simplify, becasue it is a module level pass), the new detected
region tree will contains a non-simple region with the origin exiting
block as its exit block, for example:
build/llvm/bin/opt -load /home/ether/build/llvm/lib/LLVMPolly.so
/home/ether/sources/llvm/tools/polly/test/polybench/linear-algebra/kernels/bicg/bicg_with_param.ll
-regions -polly-region-simplify -regions -analyze
-print-region-style=rn'
Printing analysis 'Detect single entry single exit regions' for
function 'scop_func':
Region tree:
...
[2] bb.nph8 => return
{
bb.nph8, bb.nph.us.preheader, bb.nph.us => return.loopexit1,
return.loopexit1, bb6.preheader, bb6 => return.loopexit,
return.loopexit,
...
End region tree
Region: bb.nph8 => return Edges: Entering: [bb7.preheader ->
bb.nph8], Exiting: [return.single_exit -> return]
Region: bb7.preheader => return Edges: Entering:
[bb7.preheader.single_entry -> bb7.preheader], Exiting:
[return.single_exit1 -> return]
Region: entry => bb7.preheader.single_entry Edges: Exiting:
[bb7.preheader.single_entry.single_exit -> bb7.preheader.single_entry]
------after region simplify:
Region tree:
...
[2] bb.nph8 => return.single_exit1
{
bb.nph8, bb.nph.us.preheader, bb.nph.us => return.loopexit1,
return.loopexit1, return.single_exit, bb6.preheader, bb6 =>
return.loopexit, return.loopexit,
...
End region tree
you can try to place -basicaa after regionsimplify, i got these cases fail:
Polly :: CodeGen/constant_condition.ll
Polly :: ScopInfo/bad_loop_1.ll
Polly :: ScopInfo/bug_2010_07_16.ll
Polly :: ScopInfo/cast.ll
Polly :: ScopInfo/indvar_out_of_loop_3.ll
Polly :: ScopInfo/loop_carry.ll
Polly :: polybench/linear-algebra/kernels/atax/atax_with_param.ll
Polly :: polybench/linear-algebra/kernels/bicg/bicg_with_param.ll
Polly :: polybench/linear-algebra/kernels/gemver/gemver_with_param.ll
to fix this, i think we could try to make polly require a regioninfo
pass that only detected simple region, or we make regioninfo try to
detect simple regions at a higher priority.
>
>> # Let the main config do the real work.
>> diff --git
>> a/test/polybench/datamining/covariance/covariance_without_param.ll
>> b/test/polybench/datamining/covariance/covariance_without_param.ll
>> index 67f0d83..a0c1f51 100644
>> --- a/test/polybench/datamining/covariance/covariance_without_param.ll
>> +++ b/test/polybench/datamining/covariance/covariance_without_param.ll
>> @@ -1,4 +1,7 @@
>> ; RUN: opt %loadPolly %defaultOpts -polly-detect -polly-cloog -analyze
>> %s | FileCheck %s
>> +; region-simplify make polly fail to detect the canonical induction
>> variable.
>> +; XFAIL:*
>
> The reason here is a bug in region-simplify. It is reordering the operands
> of the canonical induction variable (the first one is not any more the edge
> pointing into the loop, but it is the back edge of the loop). We should fix
> this and add a test case for this to 'test/RegionSimplify'.
Oh, i see.
>
>> ---
>> a/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll
>> +++
>> b/test/polybench/stencils/jacobi-2d-imper/jacobi-2d-imper_with_param.ll
>> @@ -1,4 +1,7 @@
>> ; RUN: opt %loadPolly %defaultOpts -polly-detect -analyze %s |
>> FileCheck %s
>> +; region-simplify causes: Non canonical PHI node found
>> +; XFAIL:*
>
> Mh. I do not get this bug yet. Maybe the same as the previous one?
I thinks so.
>
> I think you can commit this with those XFAILS and then we can work on fixing
> them.
>
> Cheers and thanks for your work
> Tobi
>
> P.S.: I forgot to CC you on the other mails.
No worry, I fix the setting of my gmail account, and i got them all :)
>
best regards
ether
I am not fully understand this code, so now it can be removed?
It is great if you could explain this code :)
best regards
ether
I think the best would be if the RegionInfo Pass would detect all
canonical simple regions and all canonical refined regions. At the
moment it only detects the refined regions, but that are not canonical
refined regions.
Cheers
Tobi
It requires for a certain case (where the region entry is a loop header)
a simple region, as the codegeneration has a bug here. If we only allow
simple regions we do not need to worry about this special case.
Cheers
Tobi
sorry, i do not make myself clean.
for the question:
>>> We should always have a canonical induction variable, as the
>>> ScopDetection
>>> is checking this, no?
no if we do not run the polly-prerpare pass, which translate non
canonical induction variable to stack variable. there may be non
canonical induction variable when we detecting scops.
and after we detected scops, we will always have a canonical induction
variable.
>> for (i = 0; i< N; ++i) { // i can not be recognized as canonical
>> induction variable
>> scop {
>> for (j = 0; j< N; ++i)
>> a[i][j] ...
>> }
>> }
>>
>> In this example, the outer loop do not detected as a scop, and a
>> access function in scop refers i, so we get the scev like this:
>> {{(8200 + @A),+,8200}<outerloop>,+,8192}<innerloop>
>> and {(8200 + @A),+,8200}<outerloop> not can not decompose further to
>> the A + 8200*IV of outerloop ....
>
> So _do_ we need to decompose it further, or can we just assume this is some
> kind of parameter to the SCoP?
At the moment, yes we have to decompose it.
Because it have a pointer type, and the access function class expected
a scevunknown for pointer type, so we need to decompose it untill we
get a scevunknown. Later we can improve access function pass to allow
it support other scev as base address.
>
>
best regards
ether
>>> I would prefer to not add the region-simplify to the default opts, but to
>>> just apply it to the LLVM-IR files directly. You may want to add it to
>>> 'test/create_ll.sh'. I think it is OK to add it to the polybenchOpts.
>>> The polybench test cases are for me something like whole program test
>>> cases,
>
> I think the best would be if the RegionInfo Pass would detect all canonical
> simple regions and all canonical refined regions. At the moment it only
> detects the refined regions, but that are not canonical refined regions.
>
> Cheers
> Tobi
>
So at the moment, we can treat this for a work around. what do you
think about this?
best regards
ether
On Mon, Apr 11, 2011 at 1:08 PM, Tobias Grosser
ok.
>
> Cheers
> Tobi
>
best regards
ether
commit 5de447c15819d9ece8bec48e0b5fec892f668a7a
Author: ether <ethe...@gmail.com>
Date: Wed Apr 6 00:08:14 2011 +0800
AffineSCEVIterator.h : Fix the comment.