From d7e82167a4abafc2c9ed92c3f25552434102e073 Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Sun, 2 Feb 2014 07:52:41 +0100
Subject: [PATCH] handle pencil independent pragmas

For each pencil independent pragma, we keep track of the pairs
of statement instances that are excluded from depending on each other
as well as the variables that are local to the independent loop.
The representation may not be very efficient, but this potential
problem can be solved when we move to schedule trees and/or
perform dependence analysis inside pet.

We conservatively only keep track of independences on affine for loops
with an affine loop condition.  We can later extend this to other
types of loops as the need arises.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
---
 emit.c                              | 127 +++++++++++++++
 include/pet.h                       |  20 +++
 parse.c                             | 113 +++++++++++++-
 pet.cc                              |  48 +++++-
 scan.cc                             |  23 ++-
 scan.h                              |  19 ++-
 scop.c                              | 300 ++++++++++++++++++++++++++++++++++++
 scop.h                              |   3 +
 tests/encapsulate/independent5.c    |   9 ++
 tests/encapsulate/independent5.scop | 124 +++++++++++++++
 tests/independent1.c                |   9 ++
 tests/independent1.scop             |  55 +++++++
 tests/independent2.c                |   9 ++
 tests/independent2.scop             |  55 +++++++
 tests/independent3.c                |  11 ++
 tests/independent3.scop             | 122 +++++++++++++++
 tests/independent4.c                |   9 ++
 tests/independent4.scop             |  52 +++++++
 tree.c                              |   9 +-
 tree.h                              |   4 +-
 tree2scop.c                         | 122 +++++++++++++++
 21 files changed, 1231 insertions(+), 12 deletions(-)
 create mode 100644 tests/encapsulate/independent5.c
 create mode 100644 tests/encapsulate/independent5.scop
 create mode 100644 tests/independent1.c
 create mode 100644 tests/independent1.scop
 create mode 100644 tests/independent2.c
 create mode 100644 tests/independent2.scop
 create mode 100644 tests/independent3.c
 create mode 100644 tests/independent3.scop
 create mode 100644 tests/independent4.c
 create mode 100644 tests/independent4.scop

diff --git a/emit.c b/emit.c
index 1bd7f16..6ec0855 100644
--- a/emit.c
+++ b/emit.c
@@ -216,6 +216,68 @@ static int emit_named_map(yaml_emitter_t *emitter, const char *name,
 	return 0;
 }
 
+/* Print the union set "uset" to "emitter".
+ */
+static int emit_union_set(yaml_emitter_t *emitter,
+	__isl_keep isl_union_set *uset)
+{
+	isl_ctx *ctx = isl_union_set_get_ctx(uset);
+	isl_printer *p;
+	char *str;
+	int r;
+
+	p = isl_printer_to_str(ctx);
+	p = isl_printer_print_union_set(p, uset);
+	str = isl_printer_get_str(p);
+	isl_printer_free(p);
+	r = emit_string(emitter, str);
+	free(str);
+	return r;
+}
+
+/* Print the union map "umap" to "emitter".
+ */
+static int emit_union_map(yaml_emitter_t *emitter,
+	__isl_keep isl_union_map *umap)
+{
+	isl_ctx *ctx = isl_union_map_get_ctx(umap);
+	isl_printer *p;
+	char *str;
+	int r;
+
+	p = isl_printer_to_str(ctx);
+	p = isl_printer_print_union_map(p, umap);
+	str = isl_printer_get_str(p);
+	isl_printer_free(p);
+	r = emit_string(emitter, str);
+	free(str);
+	return r;
+}
+
+/* Print the string "name" and the union set "uset" to "emitter".
+ */
+static int emit_named_union_set(yaml_emitter_t *emitter, const char *name,
+	__isl_keep isl_union_set *uset)
+{
+	if (emit_string(emitter, name) < 0)
+		return -1;
+	if (emit_union_set(emitter, uset) < 0)
+		return -1;
+	return 0;
+}
+
+/* Print the string "name" and the union map "umap" to "emitter".
+ */
+static int emit_named_union_map(yaml_emitter_t *emitter, const char *name,
+	__isl_keep isl_union_map *umap)
+{
+	if (emit_string(emitter, name) < 0)
+		return -1;
+	if (emit_union_map(emitter, umap) < 0)
+		return -1;
+	return 0;
+}
+
 /* Print the isl_multi_pw_aff "mpa" to "emitter".
  */
 static int emit_multi_pw_aff(yaml_emitter_t *emitter,
@@ -592,6 +654,9 @@ static int emit_tree(yaml_emitter_t *emitter, __isl_keep pet_tree *tree)
 			return -1;
 		break;
 	case pet_tree_for:
+		if (tree->u.l.independent)
+			if (emit_named_int(emitter, "independent", 1) < 0)
+				return -1;
 		if (emit_named_int(emitter, "declared", tree->u.l.declared) < 0)
 			return -1;
 		if (emit_named_expr(emitter, "variable", tree->u.l.iv) < 0)
@@ -795,6 +860,64 @@ static int emit_implications(yaml_emitter_t *emitter, int n_implication,
 	return 0;
 }
 
+/* Print "independence" to "emitter".
+ */
+static int emit_independence(yaml_emitter_t *emitter,
+	struct pet_independence *independence)
+{
+	yaml_event_t event;
+
+	if (!yaml_mapping_start_event_initialize(&event, NULL, NULL, 1,
+						YAML_BLOCK_MAPPING_STYLE))
+		return -1;
+	if (!yaml_emitter_emit(emitter, &event))
+		return -1;
+
+	if (emit_named_union_map(emitter, "filter", independence->filter) < 0)
+		return -1;
+
+	if (emit_named_union_set(emitter, "local", independence->local) < 0)
+		return -1;
+
+	if (!yaml_mapping_end_event_initialize(&event))
+		return -1;
+	if (!yaml_emitter_emit(emitter, &event))
+		return -1;
+
+	return 0;
+}
+
+/* Print the list of "n_independence" "independences", if any, to "emitter".
+ */
+static int emit_independences(yaml_emitter_t *emitter, int n_independence,
+	struct pet_independence **independences)
+{
+	int i;
+	yaml_event_t event;
+
+	if (n_independence == 0)
+		return 0;
+
+	if (emit_string(emitter, "independences") < 0)
+		return -1;
+	if (!yaml_sequence_start_event_initialize(&event, NULL, NULL, 1,
+						YAML_BLOCK_SEQUENCE_STYLE))
+		return -1;
+	if (!yaml_emitter_emit(emitter, &event))
+		return -1;
+
+	for (i = 0; i < n_independence; ++i)
+		if (emit_independence(emitter, independences[i]) < 0)
+			return -1;
+
+	if (!yaml_sequence_end_event_initialize(&event))
+		return -1;
+	if (!yaml_emitter_emit(emitter, &event))
+		return -1;
+
+	return 0;
+}
+
 static int emit_scop(yaml_emitter_t *emitter, struct pet_scop *scop)
 {
 	yaml_event_t event;
@@ -833,6 +956,10 @@ static int emit_scop(yaml_emitter_t *emitter, struct pet_scop *scop)
 				scop->implications) < 0)
 		return -1;
 
+	if (emit_independences(emitter, scop->n_independence,
+				scop->independences) < 0)
+		return -1;
+
 	if (!yaml_mapping_end_event_initialize(&event))
 		return -1;
 	if (!yaml_emitter_emit(emitter, &event))
diff --git a/include/pet.h b/include/pet.h
index c0aef36..7dbd02b 100644
--- a/include/pet.h
+++ b/include/pet.h
@@ -437,6 +437,20 @@ struct pet_implication {
 	isl_map *extension;
 };
 
+/* This structure represents an independence implied by a for loop
+ * that is marked as independent in the source code.
+ * "filter" contains pairs of statement instances that are guaranteed
+ * not to be dependent on each other based on the independent for loop,
+ * assuming that no dependences carried by this loop are implied
+ * by the variables in "local".
+ * "local" contains the variables that are local to the loop that was
+ * marked independent.
+ */
+struct pet_independence {
+	isl_union_map *filter;
+	isl_union_set *local;
+};
+
 /* "loc" represents the region of the source code that is represented
  * by this scop.
  * If the scop was detected based on scop and endscop pragmas, then
@@ -451,6 +465,9 @@ struct pet_implication {
  * The n_type types define types that may be referenced from by the arrays.
  *
  * The n_implication implications describe implications on boolean filters.
+ *
+ * The n_independence independences describe independences implied
+ * by for loops that are marked independent in the source code.
  */
 struct pet_scop {
 	pet_loc *loc;
@@ -469,6 +486,9 @@ struct pet_scop {
 
 	int n_implication;
 	struct pet_implication **implications;
+
+	int n_independence;
+	struct pet_independence **independences;
 };
 
 /* Return a textual representation of the operator. */
diff --git a/parse.c b/parse.c
index c7e1a48..11d9fc6 100644
--- a/parse.c
+++ b/parse.c
@@ -121,6 +121,32 @@ static __isl_give isl_map *extract_map(isl_ctx *ctx, yaml_document_t *document,
 	return isl_map_read_from_str(ctx, (char *) node->data.scalar.value);
 }
 
+/* Extract an isl_union_set from "node".
+ */
+static __isl_give isl_union_set *extract_union_set(isl_ctx *ctx,
+	yaml_document_t *document, yaml_node_t *node)
+{
+	if (node->type != YAML_SCALAR_NODE)
+		isl_die(ctx, isl_error_invalid, "expecting scalar node",
+			return NULL);
+
+	return isl_union_set_read_from_str(ctx,
+					    (char *) node->data.scalar.value);
+}
+
+/* Extract an isl_union_map from "node".
+ */
+static __isl_give isl_union_map *extract_union_map(isl_ctx *ctx,
+	yaml_document_t *document, yaml_node_t *node)
+{
+	if (node->type != YAML_SCALAR_NODE)
+		isl_die(ctx, isl_error_invalid, "expecting scalar node",
+			return NULL);
+
+	return isl_union_map_read_from_str(ctx,
+					    (char *) node->data.scalar.value);
+}
+
 /* Extract an isl_val from "node".
  */
 static __isl_give isl_val *extract_val(isl_ctx *ctx, yaml_document_t *document,
@@ -953,6 +979,7 @@ static __isl_give pet_tree *extract_tree_for(isl_ctx *ctx,
 {
 	yaml_node_pair_t *pair;
 	int declared = 0;
+	int independent = 0;
 	pet_expr *iv = NULL;
 	pet_expr *init = NULL;
 	pet_expr *cond = NULL;
@@ -972,6 +999,8 @@ static __isl_give pet_tree *extract_tree_for(isl_ctx *ctx,
 
 		if (!strcmp((char *) key->data.scalar.value, "declared"))
 			declared = extract_int(ctx, document, value);
+		if (!strcmp((char *) key->data.scalar.value, "independent"))
+			independent = extract_int(ctx, document, value);
 		if (!strcmp((char *) key->data.scalar.value, "variable")) {
 			iv = extract_expr(ctx, document, value);
 			if (!iv)
@@ -1016,7 +1045,8 @@ static __isl_give pet_tree *extract_tree_for(isl_ctx *ctx,
 		isl_die(ctx, isl_error_invalid,
 			"no body field", goto error);
 
-	return pet_tree_new_for(declared, iv, init, cond, inc, body);
+	return pet_tree_new_for(independent, declared, iv, init, cond, inc,
+				body);
 error:
 	pet_expr_free(iv);
 	pet_expr_free(init);
@@ -1293,6 +1323,84 @@ static struct pet_scop *extract_implications(isl_ctx *ctx,
 	return scop;
 }
 
+/* Extract a pet_independence from "node".
+ */
+static struct pet_independence *extract_independence(isl_ctx *ctx,
+	yaml_document_t *document, yaml_node_t *node)
+{
+	struct pet_independence *independence;
+	yaml_node_pair_t * pair;
+
+	if (node->type != YAML_MAPPING_NODE)
+		isl_die(ctx, isl_error_invalid, "expecting mapping",
+			return NULL);
+
+	independence = isl_calloc_type(ctx, struct pet_independence);
+	if (!independence)
+		return NULL;
+
+	for (pair = node->data.mapping.pairs.start;
+	     pair < node->data.mapping.pairs.top; ++pair) {
+		yaml_node_t *key, *value;
+
+		key = yaml_document_get_node(document, pair->key);
+		value = yaml_document_get_node(document, pair->value);
+
+		if (key->type != YAML_SCALAR_NODE)
+			isl_die(ctx, isl_error_invalid, "expecting scalar key",
+				return pet_independence_free(independence));
+
+		if (!strcmp((char *) key->data.scalar.value, "filter"))
+			independence->filter =
+					extract_union_map(ctx, document, value);
+		if (!strcmp((char *) key->data.scalar.value, "local"))
+			independence->local =
+					extract_union_set(ctx, document, value);
+	}
+
+	if (!independence->filter)
+		isl_die(ctx, isl_error_invalid, "no filter field",
+			return pet_independence_free(independence));
+	if (!independence->local)
+		isl_die(ctx, isl_error_invalid, "no local field",
+			return pet_independence_free(independence));
+
+	return independence;
+}
+
+/* Extract a sequence of independences from "node" and
+ * store them in scop->independences.
+ */
+static struct pet_scop *extract_independences(isl_ctx *ctx,
+	yaml_document_t *document, yaml_node_t *node, struct pet_scop *scop)
+{
+	int i;
+	yaml_node_item_t *item;
+
+	if (node->type != YAML_SEQUENCE_NODE)
+		isl_die(ctx, isl_error_invalid, "expecting sequence",
+			return NULL);
+
+	scop->n_independence = node->data.sequence.items.top
+				- node->data.sequence.items.start;
+	scop->independences = isl_calloc_array(ctx, struct pet_independence *,
+						scop->n_independence);
+	if (!scop->independences)
+		return pet_scop_free(scop);
+
+	for (item = node->data.sequence.items.start, i = 0;
+	     item < node->data.sequence.items.top; ++item, ++i) {
+		yaml_node_t *n;
+
+		n = yaml_document_get_node(document, *item);
+		scop->independences[i] = extract_independence(ctx, document, n);
+		if (!scop->independences[i])
+			return pet_scop_free(scop);
+	}
+
+	return scop;
+}
+
 static struct pet_scop *extract_scop(isl_ctx *ctx, yaml_document_t *document,
 	yaml_node_t *node)
 {
@@ -1332,6 +1440,9 @@ static struct pet_scop *extract_scop(isl_ctx *ctx, yaml_document_t *document,
 			scop = extract_statements(ctx, document, value, scop);
 		if (!strcmp((char *) key->data.scalar.value, "implications"))
 			scop = extract_implications(ctx, document, value, scop);
+		if (!strcmp((char *) key->data.scalar.value, "independences"))
+			scop = extract_independences(ctx,
+							document, value, scop);
 		if (!scop)
 			return NULL;
 	}
diff --git a/pet.cc b/pet.cc
index 55b47f4..98c01b9 100644
--- a/pet.cc
+++ b/pet.cc
@@ -1,6 +1,6 @@
 /*
- * Copyright 2011 Leiden University. All rights reserved.
- * Copyright 2012 Ecole Normale Superieure. All rights reserved.
+ * Copyright 2011      Leiden University. All rights reserved.
+ * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
  * 
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -305,6 +305,43 @@ struct PragmaParameterHandler : public PragmaHandler {
 	}
 };
 
+/* Handle pragmas of the form
+ *
+ *	#pragma pencil independent
+ *
+ * For each such pragma, add an entry to the "independent" vector.
+ */
+struct PragmaPencilHandler : public PragmaHandler {
+	std::vector<Independent> &independent;
+
+	PragmaPencilHandler(std::vector<Independent> &independent) :
+		PragmaHandler("pencil"), independent(independent) {}
+
+	virtual void HandlePragma(Preprocessor &PP,
+				  PragmaIntroducerKind Introducer,
+				  Token &PencilTok) {
+		Token token;
+		IdentifierInfo *info;
+
+		PP.Lex(token);
+		if (token.isNot(tok::identifier))
+			return;
+
+		info = token.getIdentifierInfo();
+		if (!info->isStr("independent"))
+			return;
+
+		PP.Lex(token);
+		if (token.isNot(tok::eod))
+			return;
+
+		SourceManager &SM = PP.getSourceManager();
+		SourceLocation sloc = PencilTok.getLocation();
+		unsigned line = SM.getExpansionLineNumber(sloc);
+		independent.push_back(Independent(line));
+	}
+};
+
 #ifdef HAVE_TRANSLATELINECOL
 
 /* Return a SourceLocation for line "line", column "col" of file "FID".
@@ -506,6 +543,7 @@ struct PetASTConsumer : public ASTConsumer {
 	ASTContext &ast_context;
 	DiagnosticsEngine &diags;
 	ScopLocList &scops;
+	std::vector<Independent> independent;
 	const char *function;
 	pet_options *options;
 	isl_ctx *ctx;
@@ -546,6 +584,7 @@ struct PetASTConsumer : public ASTConsumer {
 	void add_pragma_handlers(Sema *sema) {
 		PP.AddPragmaHandler(new PragmaParameterHandler(*sema, context,
 								context_value));
+		PP.AddPragmaHandler(new PragmaPencilHandler(independent));
 		handle_value_bounds(sema);
 	}
 
@@ -604,7 +643,7 @@ struct PetASTConsumer : public ASTConsumer {
 			if (end < loc.start)
 				continue;
 			PetScan ps(PP, ast_context, loc, options,
-				    isl_union_map_copy(vb));
+				    isl_union_map_copy(vb), independent);
 			scop = ps.scan(fd);
 			call_fn(scop);
 		}
@@ -630,7 +669,8 @@ struct PetASTConsumer : public ASTConsumer {
 				ScopLoc loc;
 				pet_scop *scop;
 				PetScan ps(PP, ast_context, loc, options,
-					    isl_union_map_copy(vb));
+					    isl_union_map_copy(vb),
+					    independent);
 				scop = ps.scan(fd);
 				call_fn(scop);
 				continue;
diff --git a/scan.cc b/scan.cc
index 7590552..a88275a 100644
--- a/scan.cc
+++ b/scan.cc
@@ -1210,9 +1210,12 @@ __isl_give pet_tree *PetScan::extract_for(ForStmt *stmt)
 	ValueDecl *iv;
 	pet_tree *tree;
 	struct pet_scop *scop;
+	int independent;
 	int declared;
 	pet_expr *pe_init, *pe_inc, *pe_iv, *pe_cond;
 
+	independent = is_current_stmt_marked_independent();
+
 	if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) {
 		tree = extract(stmt->getBody());
 		if (partial)
@@ -1256,7 +1259,7 @@ __isl_give pet_tree *PetScan::extract_for(ForStmt *stmt)
 	else
 		pe_cond = extract_expr(stmt->getCond());
 	pe_inc = extract_increment(stmt, iv);
-	tree = pet_tree_new_for(declared, pe_iv, pe_init, pe_cond,
+	tree = pet_tree_new_for(independent, declared, pe_iv, pe_init, pe_cond,
 				pe_inc, tree);
 	return tree;
 }
@@ -2262,3 +2265,21 @@ void PetScan::set_current_stmt(Stmt *stmt)
 	last_line = current_line;
 	current_line = SM.getExpansionLineNumber(loc);
 }
+
+/* Is the current statement marked by an independent pragma?
+ * That is, is there an independent pragma on a line between
+ * the line of the current statement and the line of the previous statement.
+ * The search is not implemented very efficiently.  We currently
+ * assume that there are only a few independent pragmas, if any.
+ */
+bool PetScan::is_current_stmt_marked_independent()
+{
+	for (int i = 0; i < independent.size(); ++i) {
+		unsigned line = independent[i].line;
+
+		if (last_line < line && line < current_line)
+			return true;
+	}
+
+	return false;
+}
diff --git a/scan.h b/scan.h
index 5e6761d..e18f43a 100644
--- a/scan.h
+++ b/scan.h
@@ -26,6 +26,16 @@ struct ScopLoc {
 	unsigned end;
 };
 
+/* The information extracted from a pragma pencil independent.
+ * We currently only keep track of the line number where
+ * the pragma appears.
+ */
+struct Independent {
+	Independent(unsigned line) : line(line) {}
+
+	unsigned line;
+};
+
 /* Compare two RecordDecl pointers based on their names.
  */
 struct less_name {
@@ -68,14 +78,18 @@ struct PetScan {
 	unsigned last_line;
 	/* The line number of the Stmt currently being considered. */
 	unsigned current_line;
+	/* Information about the independent pragmas in the source code. */
+	std::vector<Independent> &independent;
 
 	PetScan(clang::Preprocessor &PP,
 		clang::ASTContext &ast_context, ScopLoc &loc,
-		pet_options *options, __isl_take isl_union_map *value_bounds) :
+		pet_options *options, __isl_take isl_union_map *value_bounds,
+		std::vector<Independent> &independent) :
 		ctx(isl_union_map_get_ctx(value_bounds)), PP(PP),
 		ast_context(ast_context), loc(loc),
 		options(options), value_bounds(value_bounds),
-		partial(false), last_line(0), current_line(0) { }
+		partial(false), last_line(0), current_line(0),
+		independent(independent) { }
 
 	~PetScan();
 
@@ -88,6 +102,7 @@ struct PetScan {
 		lex_recorddecl_set *types, __isl_keep pet_context *pc);
 private:
 	void set_current_stmt(clang::Stmt *stmt);
+	bool is_current_stmt_marked_independent();
 
 	struct pet_scop *scan(clang::Stmt *stmt);
 
diff --git a/scop.c b/scop.c
index f17c259..4ebd5f7 100644
--- a/scop.c
+++ b/scop.c
@@ -747,6 +747,110 @@ static struct pet_scop *scop_combine_start_end(struct pet_scop *scop,
 	return scop;
 }
 
+/* Create and return an independence that filters out the dependences
+ * in "filter" with local variables "local".
+ */
+static struct pet_independence *new_independence(
+	__isl_take isl_union_map *filter, __isl_take isl_union_set *local)
+{
+	isl_ctx *ctx;
+	struct pet_independence *independence;
+
+	if (!filter || !local)
+		goto error;
+	ctx = isl_union_map_get_ctx(filter);
+	independence = isl_alloc_type(ctx, struct pet_independence);
+	if (!independence)
+		goto error;
+
+	independence->filter = filter;
+	independence->local = local;
+
+	return independence;
+error:
+	isl_union_map_free(filter);
+	isl_union_set_free(local);
+	return NULL;
+}
+
+/* Add an independence that filters out the dependences
+ * in "filter" with local variables "local" to "scop".
+ */
+struct pet_scop *pet_scop_add_independence(struct pet_scop *scop,
+	__isl_take isl_union_map *filter, __isl_take isl_union_set *local)
+{
+	isl_ctx *ctx;
+	struct pet_independence *independence;
+	struct pet_independence **independences;
+
+	ctx = isl_union_map_get_ctx(filter);
+	independence = new_independence(filter, local);
+	if (!scop || !independence)
+		goto error;
+
+	independences = isl_realloc_array(ctx, scop->independences,
+					    struct pet_independence *,
+					    scop->n_independence + 1);
+	if (!independences)
+		goto error;
+	scop->independences = independences;
+	scop->independences[scop->n_independence] = independence;
+	scop->n_independence++;
+
+	return scop;
+error:
+	pet_independence_free(independence);
+	pet_scop_free(scop);
+	return NULL;
+}
+
+/* Store the concatenation of the independences of "scop1" and "scop2"
+ * in "scop".
+ */
+static struct pet_scop *scop_collect_independences(isl_ctx *ctx,
+	struct pet_scop *scop, struct pet_scop *scop1, struct pet_scop *scop2)
+{
+	int i, off;
+
+	if (!scop)
+		return NULL;
+
+	if (scop2->n_independence == 0) {
+		scop->n_independence = scop1->n_independence;
+		scop->independences = scop1->independences;
+		scop1->n_independence = 0;
+		scop1->independences = NULL;
+		return scop;
+	}
+
+	if (scop1->n_independence == 0) {
+		scop->n_independence = scop2->n_independence;
+		scop->independences = scop2->independences;
+		scop2->n_independence = 0;
+		scop2->independences = NULL;
+		return scop;
+	}
+
+	scop->independences = isl_calloc_array(ctx, struct pet_independence *,
+				scop1->n_independence + scop2->n_independence);
+	if (!scop->independences)
+		return pet_scop_free(scop);
+
+	for (i = 0; i < scop1->n_independence; ++i) {
+		scop->independences[i] = scop1->independences[i];
+		scop1->independences[i] = NULL;
+	}
+
+	off = scop1->n_independence;
+	for (i = 0; i < scop2->n_independence; ++i) {
+		scop->independences[off + i] = scop2->independences[i];
+		scop2->independences[i] = NULL;
+	}
+	scop->n_independence = scop1->n_independence + scop2->n_independence;
+
+	return scop;
+}
+
 /* Construct a pet_scop that contains the offset information,
  * arrays, statements and skip information in "scop1" and "scop2".
  */
@@ -808,6 +912,7 @@ static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
 	scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context));
 	scop = scop_combine_skips(scop, scop1, scop2);
 	scop = scop_combine_start_end(scop, scop1, scop2);
+	scop = scop_collect_independences(ctx, scop, scop1, scop2);
 
 	pet_scop_free(scop1);
 	pet_scop_free(scop2);
@@ -892,6 +997,18 @@ void *pet_implication_free(struct pet_implication *implication)
 	return NULL;
 }
 
+void *pet_independence_free(struct pet_independence *independence)
+{
+	if (!independence)
+		return NULL;
+
+	isl_union_map_free(independence->filter);
+	isl_union_set_free(independence->local);
+
+	free(independence);
+	return NULL;
+}
+
 struct pet_scop *pet_scop_free(struct pet_scop *scop)
 {
 	int i;
@@ -918,6 +1035,10 @@ struct pet_scop *pet_scop_free(struct pet_scop *scop)
 		for (i = 0; i < scop->n_implication; ++i)
 			pet_implication_free(scop->implications[i]);
 	free(scop->implications);
+	if (scop->independences)
+		for (i = 0; i < scop->n_independence; ++i)
+			pet_independence_free(scop->independences[i]);
+	free(scop->independences);
 	isl_multi_pw_aff_free(ext->skip[pet_skip_now]);
 	isl_multi_pw_aff_free(ext->skip[pet_skip_later]);
 	free(scop);
@@ -1060,6 +1181,23 @@ int pet_implication_is_equal(struct pet_implication *implication1,
 	return 1;
 }
 
+/* Return 1 if the two pet_independences are equivalent.
+ */
+int pet_independence_is_equal(struct pet_independence *independence1,
+	struct pet_independence *independence2)
+{
+	if (!independence1 || !independence2)
+		return 0;
+
+	if (!isl_union_map_is_equal(independence1->filter,
+					independence2->filter))
+		return 0;
+	if (!isl_union_set_is_equal(independence1->local, independence2->local))
+		return 0;
+
+	return 1;
+}
+
 /* Return 1 if the two pet_scops are equivalent.
  */
 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
@@ -1099,6 +1237,13 @@ int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
 						scop2->implications[i]))
 			return 0;
 
+	if (scop1->n_independence != scop2->n_independence)
+		return 0;
+	for (i = 0; i < scop1->n_independence; ++i)
+		if (!pet_independence_is_equal(scop1->independences[i],
+						scop2->independences[i]))
+			return 0;
+
 	return 1;
 }
 
@@ -2004,6 +2149,22 @@ static __isl_give isl_space *array_collect_params(struct pet_array *array,
 	return space;
 }
 
+/* Add all parameters in "independence" to "space" and return the result.
+ */
+static __isl_give isl_space *independence_collect_params(
+	struct pet_independence *independence, __isl_take isl_space *space)
+{
+	if (!independence)
+		return isl_space_free(space);
+
+	space = isl_space_align_params(space,
+				isl_union_map_get_space(independence->filter));
+	space = isl_space_align_params(space,
+				isl_union_set_get_space(independence->local));
+
+	return space;
+}
+
 /* Add all parameters in "scop" to "space" and return the result.
  */
 static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
@@ -2020,6 +2181,10 @@ static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
 	for (i = 0; i < scop->n_stmt; ++i)
 		space = stmt_collect_params(scop->stmts[i], space);
 
+	for (i = 0; i < scop->n_independence; ++i)
+		space = independence_collect_params(scop->independences[i],
+							space);
+
 	return space;
 }
 
@@ -2086,6 +2251,28 @@ error:
 	return pet_array_free(array);
 }
 
+/* Add all parameters in "space" to "independence".
+ */
+static struct pet_independence *independence_propagate_params(
+	struct pet_independence *independence, __isl_take isl_space *space)
+{
+	if (!independence)
+		goto error;
+
+	independence->filter = isl_union_map_align_params(independence->filter,
+						isl_space_copy(space));
+	independence->local = isl_union_set_align_params(independence->local,
+						isl_space_copy(space));
+	if (!independence->filter || !independence->local)
+		goto error;
+
+	isl_space_free(space);
+	return independence;
+error:
+	isl_space_free(space);
+	return pet_independence_free(independence);
+}
+
 /* Add all parameters in "space" to "scop".
  */
 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
@@ -2110,6 +2297,13 @@ static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
 			goto error;
 	}
 
+	for (i = 0; i < scop->n_independence; ++i) {
+		scop->independences[i] = independence_propagate_params(
+				scop->independences[i], isl_space_copy(space));
+		if (!scop->independences[i])
+			goto error;
+	}
+
 	isl_space_free(space);
 	return scop;
 error:
@@ -2618,6 +2812,23 @@ static struct pet_implication *implication_anonymize(
 	return implication;
 }
 
+/* Reset the user pointer on the tuple ids and all parameter ids
+ * in "independence".
+ */
+static struct pet_independence *independence_anonymize(
+	struct pet_independence *independence)
+{
+	if (!independence)
+		return NULL;
+
+	independence->filter = isl_union_map_reset_user(independence->filter);
+	independence->local = isl_union_set_reset_user(independence->local);
+	if (!independence->filter || !independence->local)
+		return pet_independence_free(independence);
+
+	return independence;
+}
+
 /* Reset the user pointer on all parameter and tuple ids in "scop".
  */
 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
@@ -2651,6 +2862,13 @@ struct pet_scop *pet_scop_anonymize(struct pet_scop *scop)
 			return pet_scop_free(scop);
 	}
 
+	for (i = 0; i < scop->n_independence; ++i) {
+		scop->independences[i] =
+				independence_anonymize(scop->independences[i]);
+		if (!scop->independences[i])
+			return pet_scop_free(scop);
+	}
+
 	return scop;
 }
 
@@ -2947,6 +3165,88 @@ error:
 	return pet_scop_free(scop);
 }
 
+/* Create and return a function that maps the iteration domains
+ * of the statements in "scop" onto their outer "n" dimensions.
+ * "space" is the parameters space of the created function.
+ */
+static __isl_give isl_union_pw_multi_aff *outer_projection(
+	struct pet_scop *scop, __isl_take isl_space *space, int n)
+{
+	int i;
+	isl_union_pw_multi_aff *res;
+
+	res = isl_union_pw_multi_aff_empty(space);
+
+	if (!scop)
+		return isl_union_pw_multi_aff_free(res);
+
+	for (i = 0; i < scop->n_stmt; ++i) {
+		struct pet_stmt *stmt = scop->stmts[i];
+		isl_space *space;
+		isl_multi_aff *ma;
+		isl_pw_multi_aff *pma;
+
+		space = pet_stmt_get_space(stmt);
+		ma = pet_prefix_projection(space, n);
+		pma = isl_pw_multi_aff_from_multi_aff(ma);
+		res = isl_union_pw_multi_aff_add_pw_multi_aff(res, pma);
+	}
+
+	return res;
+}
+
+/* Add an independence to "scop" for the inner iterator of "domain"
+ * with local variables "local", where "domain" represents the outer
+ * loop iterators of all statements in "scop".
+ * If "sign" is positive, then the inner iterator increases.
+ * Otherwise it decreases.
+ *
+ * The independence is supposed to filter out any dependence of
+ * an iteration of domain on a previous iteration along the inner dimension.
+ * We therefore create a mapping from an iteration to later iterations and
+ * then plug in the projection of the iterations domains of "scop"
+ * onto the outer loop iterators.
+ */
+struct pet_scop *pet_scop_set_independent(struct pet_scop *scop,
+	__isl_keep isl_set *domain, __isl_take isl_union_set *local, int sign)
+{
+	int i, dim;
+	isl_space *space;
+	isl_map *map;
+	isl_union_map *independence;
+	isl_union_pw_multi_aff *proj;
+
+	if (!scop || !domain || !local)
+		goto error;
+
+	dim = isl_set_dim(domain, isl_dim_set);
+	space = isl_space_map_from_set(isl_set_get_space(domain));
+	map = isl_map_universe(space);
+	for (i = 0; i + 1 < dim; ++i)
+		map = isl_map_equate(map, isl_dim_in, i, isl_dim_out, i);
+	if (sign > 0)
+		map = isl_map_order_lt(map,
+				    isl_dim_in, dim - 1, isl_dim_out, dim - 1);
+	else
+		map = isl_map_order_gt(map,
+				    isl_dim_in, dim - 1, isl_dim_out, dim - 1);
+
+	independence = isl_union_map_from_map(map);
+	space = isl_space_params(isl_set_get_space(domain));
+	proj = outer_projection(scop, space, dim);
+	independence = isl_union_map_preimage_domain_union_pw_multi_aff(
+			    independence, isl_union_pw_multi_aff_copy(proj));
+	independence = isl_union_map_preimage_range_union_pw_multi_aff(
+			    independence, proj);
+
+	scop = pet_scop_add_independence(scop, independence, local);
+
+	return scop;
+error:
+	isl_union_set_free(local);
+	return pet_scop_free(scop);
+}
+
 /* Given an access expression, check if it is data dependent.
  * If so, set *found and abort the search.
  */
diff --git a/scop.h b/scop.h
index d7568ab..97f4fec 100644
--- a/scop.h
+++ b/scop.h
@@ -30,6 +30,7 @@ void pet_array_dump(struct pet_array *array);
 struct pet_array *pet_array_free(struct pet_array *array);
 
 void *pet_implication_free(struct pet_implication *implication);
+void *pet_independence_free(struct pet_independence *independence);
 
 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos);
 
@@ -59,6 +60,8 @@ struct pet_scop *pet_scop_filter(struct pet_scop *scop,
 struct pet_scop *pet_scop_merge_filters(struct pet_scop *scop);
 struct pet_scop *pet_scop_add_implication(struct pet_scop *scop,
 	__isl_take isl_map *map, int satisfied);
+struct pet_scop *pet_scop_set_independent(struct pet_scop *scop,
+	__isl_keep isl_set *domain, __isl_take isl_union_set *local, int sign);
 
 struct pet_scop *pet_scop_gist(struct pet_scop *scop,
 	__isl_keep isl_union_map *value_bounds);
diff --git a/tests/encapsulate/independent5.c b/tests/encapsulate/independent5.c
new file mode 100644
index 0000000..1739fe3
--- /dev/null
+++ b/tests/encapsulate/independent5.c
@@ -0,0 +1,9 @@
+void foo(int n, int A[n], int B[n], int C[n])
+{
+#pragma scop
+	#pragma pencil independent
+	for (int i = 0; i < n; ++i)
+		for (int j = C[i]; j < n; ++j)
+			B[A[i]] += j;
+#pragma endscop
+}
diff --git a/tests/encapsulate/independent5.scop b/tests/encapsulate/independent5.scop
new file mode 100644
index 0000000..ba2ffe1
--- /dev/null
+++ b/tests/encapsulate/independent5.scop
@@ -0,0 +1,124 @@
+start: 48
+end: 184
+indent: "\t"
+context: '[n] -> {  : n <= 2147483647 and n >= -2147483648 }'
+arrays:
+- context: '{  :  }'
+  extent: '[n] -> { j[] }'
+  element_type: int
+  element_size: 4
+  declared: 1
+- context: '{  :  }'
+  extent: '[n] -> { A[i0] : i0 >= 0 }'
+  element_type: int
+  element_size: 4
+- context: '{  :  }'
+  extent: '[n] -> { B[i0] : i0 >= 0 }'
+  element_type: int
+  element_size: 4
+- context: '{  :  }'
+  extent: '[n] -> { C[i0] : i0 >= 0 }'
+  element_type: int
+  element_size: 4
+statements:
+- line: 6
+  domain: '[n] -> { S_7[i] : i <= -1 + n and i >= 0 }'
+  schedule: '[n] -> { S_7[i] -> [0, i, 0] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: kill
+      arguments:
+      - type: access
+        relation: '[n] -> { S_7[i] -> j[] }'
+        index: '[n] -> { S_7[i] -> j[] }'
+        reference: __pet_ref_0
+        read: 0
+        write: 0
+- line: 6
+  domain: '[n] -> { S_6[i] : i <= -1 + n and i >= 0 }'
+  schedule: '[n] -> { S_6[i] -> [0, i, 1] }'
+  body:
+    type: for
+    declared: 1
+    variable:
+      type: access
+      relation: '[n] -> { S_6[i] -> j[] }'
+      index: '[n] -> { S_6[i] -> j[] }'
+      reference: __pet_ref_1
+      read: 0
+      write: 1
+    initialization:
+      type: access
+      relation: '[n] -> { S_6[i] -> C[i] }'
+      index: '[n] -> { S_6[i] -> C[(i)] }'
+      reference: __pet_ref_2
+      read: 1
+      write: 0
+    condition:
+      type: op
+      operation: <
+      arguments:
+      - type: access
+        relation: '[n] -> { S_6[i] -> j[] }'
+        index: '[n] -> { S_6[i] -> j[] }'
+        reference: __pet_ref_3
+        read: 1
+        write: 0
+      - type: access
+        relation: '[n] -> { S_6[i] -> [n] }'
+        index: '[n] -> { S_6[i] -> [(n)] }'
+        reference: __pet_ref_4
+        read: 1
+        write: 0
+    increment:
+      type: int
+      value: 1
+    body:
+      type: expression
+      expr:
+        type: op
+        operation: +=
+        arguments:
+        - type: access
+          relation: '[n] -> { [S_6[i] -> [i1]] -> B[i1] : i1 >= 0 }'
+          index: '[n] -> { [S_6[i] -> [i1]] -> B[((i1) : i1 >= 0)] }'
+          reference: __pet_ref_6
+          read: 1
+          write: 1
+          arguments:
+          - type: access
+            relation: '[n] -> { S_6[i] -> A[i] }'
+            index: '[n] -> { S_6[i] -> A[(i)] }'
+            reference: __pet_ref_5
+            read: 1
+            write: 0
+        - type: access
+          relation: '[n] -> { S_6[i] -> j[] }'
+          index: '[n] -> { S_6[i] -> j[] }'
+          reference: __pet_ref_7
+          read: 1
+          write: 0
+- line: 6
+  domain: '[n] -> { S_8[i] : i <= -1 + n and i >= 0 }'
+  schedule: '[n] -> { S_8[i] -> [0, i, 2] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: kill
+      arguments:
+      - type: access
+        relation: '[n] -> { S_8[i] -> j[] }'
+        index: '[n] -> { S_8[i] -> j[] }'
+        reference: __pet_ref_8
+        read: 0
+        write: 0
+independences:
+- filter: '[n] -> { S_6[i] -> S_7[i''] : i'' >= 1 + i; S_8[i] -> S_7[i''] : i'' >=
+    1 + i; S_7[i] -> S_8[i''] : i'' >= 1 + i; S_6[i] -> S_6[i''] : i'' >= 1 + i; S_6[i]
+    -> S_8[i''] : i'' >= 1 + i; S_8[i] -> S_8[i''] : i'' >= 1 + i; S_7[i] -> S_6[i'']
+    : i'' >= 1 + i; S_7[i] -> S_7[i''] : i'' >= 1 + i; S_8[i] -> S_6[i''] : i'' >=
+    1 + i }'
+  local: '{ j[] }'
diff --git a/tests/independent1.c b/tests/independent1.c
new file mode 100644
index 0000000..1d424ad
--- /dev/null
+++ b/tests/independent1.c
@@ -0,0 +1,9 @@
+void foo(int n, int A[n][n], int B[n][n])
+{
+#pragma scop
+	for (int i = 0; i < n; ++i)
+		#pragma pencil independent
+		for (int j = 0; j < n; ++j)
+			B[i][A[i][j]] = i + j;
+#pragma endscop
+}
diff --git a/tests/independent1.scop b/tests/independent1.scop
new file mode 100644
index 0000000..a050038
--- /dev/null
+++ b/tests/independent1.scop
@@ -0,0 +1,55 @@
+start: 44
+end: 187
+indent: "\t"
+context: '[n] -> {  : n >= 0 and n <= 2147483647 }'
+arrays:
+- context: '[n] -> {  : n >= 0 }'
+  extent: '[n] -> { A[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + n }'
+  element_type: int
+  element_size: 4
+- context: '[n] -> {  : n >= 0 }'
+  extent: '[n] -> { B[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + n }'
+  element_type: int
+  element_size: 4
+statements:
+- line: 7
+  domain: '[n] -> { S_0[i, j] : i >= 0 and i <= -1 + n and j <= -1 + n and j >= 0
+    }'
+  schedule: '[n] -> { S_0[i, j] -> [0, i, j] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: =
+      arguments:
+      - type: access
+        relation: '[n] -> { [S_0[i, j] -> [i2]] -> B[i, i2] : i2 >= 0 }'
+        index: '[n] -> { [S_0[i, j] -> [i2]] -> B[(i), ((i2) : i2 >= 0)] }'
+        reference: __pet_ref_1
+        read: 0
+        write: 1
+        arguments:
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> A[i, j] }'
+          index: '[n] -> { S_0[i, j] -> A[(i), (j)] }'
+          reference: __pet_ref_0
+          read: 1
+          write: 0
+      - type: op
+        operation: +
+        arguments:
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> [i] }'
+          index: '[n] -> { S_0[i, j] -> [(i)] }'
+          reference: __pet_ref_2
+          read: 1
+          write: 0
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> [j] }'
+          index: '[n] -> { S_0[i, j] -> [(j)] }'
+          reference: __pet_ref_3
+          read: 1
+          write: 0
+independences:
+- filter: '[n] -> { S_0[i, j] -> S_0[i, j''] : j'' >= 1 + j }'
+  local: '{  }'
diff --git a/tests/independent2.c b/tests/independent2.c
new file mode 100644
index 0000000..4c00297
--- /dev/null
+++ b/tests/independent2.c
@@ -0,0 +1,9 @@
+void foo(int n, int A[n], int B[n][n])
+{
+#pragma scop
+	#pragma pencil independent
+	for (int i = 0; i < n; ++i)
+		for (int j = 0; j < n; ++j)
+			B[A[i]][j] = i + j;
+#pragma endscop
+}
diff --git a/tests/independent2.scop b/tests/independent2.scop
new file mode 100644
index 0000000..6f7d56d
--- /dev/null
+++ b/tests/independent2.scop
@@ -0,0 +1,55 @@
+start: 41
+end: 180
+indent: "\t"
+context: '[n] -> {  : n >= 0 and n <= 2147483647 }'
+arrays:
+- context: '{  :  }'
+  extent: '[n] -> { A[i0] : i0 >= 0 }'
+  element_type: int
+  element_size: 4
+- context: '[n] -> {  : n >= 0 }'
+  extent: '[n] -> { B[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + n }'
+  element_type: int
+  element_size: 4
+statements:
+- line: 7
+  domain: '[n] -> { S_0[i, j] : i >= 0 and i <= -1 + n and j <= -1 + n and j >= 0
+    }'
+  schedule: '[n] -> { S_0[i, j] -> [0, i, j] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: =
+      arguments:
+      - type: access
+        relation: '[n] -> { [S_0[i, j] -> [i2]] -> B[i2, j] : i2 >= 0 }'
+        index: '[n] -> { [S_0[i, j] -> [i2]] -> B[((i2) : i2 >= 0), (j)] }'
+        reference: __pet_ref_1
+        read: 0
+        write: 1
+        arguments:
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> A[i] }'
+          index: '[n] -> { S_0[i, j] -> A[(i)] }'
+          reference: __pet_ref_0
+          read: 1
+          write: 0
+      - type: op
+        operation: +
+        arguments:
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> [i] }'
+          index: '[n] -> { S_0[i, j] -> [(i)] }'
+          reference: __pet_ref_2
+          read: 1
+          write: 0
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> [j] }'
+          index: '[n] -> { S_0[i, j] -> [(j)] }'
+          reference: __pet_ref_3
+          read: 1
+          write: 0
+independences:
+- filter: '[n] -> { S_0[i, j] -> S_0[i'', j''] : i'' >= 1 + i }'
+  local: '{  }'
diff --git a/tests/independent3.c b/tests/independent3.c
new file mode 100644
index 0000000..2ce3609
--- /dev/null
+++ b/tests/independent3.c
@@ -0,0 +1,11 @@
+void foo(int n, int A[n][n], int B[n][n])
+{
+#pragma scop
+	for (int i = 0; i < n; ++i)
+		#pragma pencil independent
+		for (int j = 0; j < n; ++j) {
+			float t = i + j;
+			B[i][A[i][j]] = t;
+		}
+#pragma endscop
+}
diff --git a/tests/independent3.scop b/tests/independent3.scop
new file mode 100644
index 0000000..4a20aba
--- /dev/null
+++ b/tests/independent3.scop
@@ -0,0 +1,122 @@
+start: 44
+end: 209
+indent: "\t"
+context: '[n] -> {  : n >= 0 and n <= 2147483647 }'
+arrays:
+- context: '{  :  }'
+  extent: '[n] -> { t[] }'
+  element_type: float
+  element_size: 4
+  declared: 1
+- context: '[n] -> {  : n >= 0 }'
+  extent: '[n] -> { A[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + n }'
+  element_type: int
+  element_size: 4
+- context: '[n] -> {  : n >= 0 }'
+  extent: '[n] -> { B[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + n }'
+  element_type: int
+  element_size: 4
+statements:
+- line: 7
+  domain: '[n] -> { S_0[i, j] : i >= 0 and i <= -1 + n and j <= -1 + n and j >= 0
+    }'
+  schedule: '[n] -> { S_0[i, j] -> [0, i, j, 0, 0] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: kill
+      arguments:
+      - type: access
+        relation: '[n] -> { S_0[i, j] -> t[] }'
+        index: '[n] -> { S_0[i, j] -> t[] }'
+        reference: __pet_ref_0
+        read: 0
+        write: 0
+- line: 7
+  domain: '[n] -> { S_1[i, j] : i >= 0 and i <= -1 + n and j <= -1 + n and j >= 0
+    }'
+  schedule: '[n] -> { S_1[i, j] -> [0, i, j, 0, 1] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: =
+      arguments:
+      - type: access
+        relation: '[n] -> { S_1[i, j] -> t[] }'
+        index: '[n] -> { S_1[i, j] -> t[] }'
+        reference: __pet_ref_1
+        read: 0
+        write: 1
+      - type: op
+        operation: +
+        arguments:
+        - type: access
+          relation: '[n] -> { S_1[i, j] -> [i] }'
+          index: '[n] -> { S_1[i, j] -> [(i)] }'
+          reference: __pet_ref_2
+          read: 1
+          write: 0
+        - type: access
+          relation: '[n] -> { S_1[i, j] -> [j] }'
+          index: '[n] -> { S_1[i, j] -> [(j)] }'
+          reference: __pet_ref_3
+          read: 1
+          write: 0
+- line: 8
+  domain: '[n] -> { S_3[i, j] : i >= 0 and i <= -1 + n and j <= -1 + n and j >= 0
+    }'
+  schedule: '[n] -> { S_3[i, j] -> [0, i, j, 1] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: =
+      arguments:
+      - type: access
+        relation: '[n] -> { [S_3[i, j] -> [i2]] -> B[i, i2] : i2 >= 0 }'
+        index: '[n] -> { [S_3[i, j] -> [i2]] -> B[(i), ((i2) : i2 >= 0)] }'
+        reference: __pet_ref_5
+        read: 0
+        write: 1
+        arguments:
+        - type: access
+          relation: '[n] -> { S_3[i, j] -> A[i, j] }'
+          index: '[n] -> { S_3[i, j] -> A[(i), (j)] }'
+          reference: __pet_ref_4
+          read: 1
+          write: 0
+      - type: access
+        relation: '[n] -> { S_3[i, j] -> t[] }'
+        index: '[n] -> { S_3[i, j] -> t[] }'
+        reference: __pet_ref_6
+        read: 1
+        write: 0
+- line: 7
+  domain: '[n] -> { S_2[i, j] : i >= 0 and i <= -1 + n and j <= -1 + n and j >= 0
+    }'
+  schedule: '[n] -> { S_2[i, j] -> [0, i, j, 2] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: kill
+      arguments:
+      - type: access
+        relation: '[n] -> { S_2[i, j] -> t[] }'
+        index: '[n] -> { S_2[i, j] -> t[] }'
+        reference: __pet_ref_7
+        read: 0
+        write: 0
+independences:
+- filter: '[n] -> { S_2[i, j] -> S_2[i, j''] : j'' >= 1 + j; S_0[i, j] -> S_1[i, j'']
+    : j'' >= 1 + j; S_2[i, j] -> S_1[i, j''] : j'' >= 1 + j; S_3[i, j] -> S_1[i, j'']
+    : j'' >= 1 + j; S_0[i, j] -> S_2[i, j''] : j'' >= 1 + j; S_3[i, j] -> S_2[i, j'']
+    : j'' >= 1 + j; S_1[i, j] -> S_0[i, j''] : j'' >= 1 + j; S_2[i, j] -> S_0[i, j'']
+    : j'' >= 1 + j; S_0[i, j] -> S_0[i, j''] : j'' >= 1 + j; S_0[i, j] -> S_3[i, j'']
+    : j'' >= 1 + j; S_3[i, j] -> S_0[i, j''] : j'' >= 1 + j; S_1[i, j] -> S_2[i, j'']
+    : j'' >= 1 + j; S_3[i, j] -> S_3[i, j''] : j'' >= 1 + j; S_1[i, j] -> S_3[i, j'']
+    : j'' >= 1 + j; S_1[i, j] -> S_1[i, j''] : j'' >= 1 + j; S_2[i, j] -> S_3[i, j'']
+    : j'' >= 1 + j }'
+  local: '{ t[] }'
diff --git a/tests/independent4.c b/tests/independent4.c
new file mode 100644
index 0000000..9b3beef
--- /dev/null
+++ b/tests/independent4.c
@@ -0,0 +1,9 @@
+void foo(int n, int A[n][n], int B[n][n])
+{
+#pragma scop
+	for (int i = 0; i < n; ++i)
+		#pragma pencil independent with random qualifiers
+		for (int j = 0; j < n; ++j)
+			B[i][A[i][j]] = i + j;
+#pragma endscop
+}
diff --git a/tests/independent4.scop b/tests/independent4.scop
new file mode 100644
index 0000000..0fc840a
--- /dev/null
+++ b/tests/independent4.scop
@@ -0,0 +1,52 @@
+start: 44
+end: 210
+indent: "\t"
+context: '[n] -> {  : n >= 0 and n <= 2147483647 }'
+arrays:
+- context: '[n] -> {  : n >= 0 }'
+  extent: '[n] -> { A[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + n }'
+  element_type: int
+  element_size: 4
+- context: '[n] -> {  : n >= 0 }'
+  extent: '[n] -> { B[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + n }'
+  element_type: int
+  element_size: 4
+statements:
+- line: 7
+  domain: '[n] -> { S_0[i, j] : i >= 0 and i <= -1 + n and j <= -1 + n and j >= 0
+    }'
+  schedule: '[n] -> { S_0[i, j] -> [0, i, j] }'
+  body:
+    type: expression
+    expr:
+      type: op
+      operation: =
+      arguments:
+      - type: access
+        relation: '[n] -> { [S_0[i, j] -> [i2]] -> B[i, i2] : i2 >= 0 }'
+        index: '[n] -> { [S_0[i, j] -> [i2]] -> B[(i), ((i2) : i2 >= 0)] }'
+        reference: __pet_ref_1
+        read: 0
+        write: 1
+        arguments:
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> A[i, j] }'
+          index: '[n] -> { S_0[i, j] -> A[(i), (j)] }'
+          reference: __pet_ref_0
+          read: 1
+          write: 0
+      - type: op
+        operation: +
+        arguments:
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> [i] }'
+          index: '[n] -> { S_0[i, j] -> [(i)] }'
+          reference: __pet_ref_2
+          read: 1
+          write: 0
+        - type: access
+          relation: '[n] -> { S_0[i, j] -> [j] }'
+          index: '[n] -> { S_0[i, j] -> [(j)] }'
+          reference: __pet_ref_3
+          read: 1
+          write: 0
diff --git a/tree.c b/tree.c
index eed850c..51b799a 100644
--- a/tree.c
+++ b/tree.c
@@ -207,11 +207,12 @@ __isl_give pet_tree *pet_tree_new_continue(isl_ctx *ctx)
  * with induction variable "iv", initial value for the induction
  * variable "init", loop condition "cond", induction variable increment "inc"
  * and loop body "body".  "declared" indicates whether the induction variable
- * is declared by the loop.
+ * is declared by the loop.  "independent" is set if the for loop is marked
+ * independent.
  *
  * The location of the loop is initialized to that of the body.
  */
-__isl_give pet_tree *pet_tree_new_for(int declared,
+__isl_give pet_tree *pet_tree_new_for(int independent, int declared,
 	__isl_take pet_expr *iv, __isl_take pet_expr *init,
 	__isl_take pet_expr *cond, __isl_take pet_expr *inc,
 	__isl_take pet_tree *body)
@@ -226,6 +227,7 @@ __isl_give pet_tree *pet_tree_new_for(int declared,
 	if (!tree)
 		goto error;
 
+	tree->u.l.independent = independent;
 	tree->u.l.declared = declared;
 	tree->u.l.iv = iv;
 	tree->u.l.init = init;
@@ -406,7 +408,8 @@ static __isl_give pet_tree *pet_tree_dup(__isl_keep pet_tree *tree)
 		dup = pet_tree_new_expr(pet_expr_copy(tree->u.e.expr));
 		break;
 	case pet_tree_for:
-		dup = pet_tree_new_for(tree->u.l.declared,
+		dup = pet_tree_new_for(tree->u.l.independent,
+		    tree->u.l.declared,
 		    pet_expr_copy(tree->u.l.iv), pet_expr_copy(tree->u.l.init),
 		    pet_expr_copy(tree->u.l.cond), pet_expr_copy(tree->u.l.inc),
 		    pet_tree_copy(tree->u.l.body));
diff --git a/tree.h b/tree.h
index 8abed56..131f239 100644
--- a/tree.h
+++ b/tree.h
@@ -35,6 +35,7 @@ extern "C" {
  " "declared" is set if this induction variable is declared by the loop.
  * "init" is the initial value of the induction variable.
  * "inc" is the increment to the induction variable.
+ * "independent" is set if the for loop is marked independent.
  *
  * The "i" field of the union is used for types pet_tree_if
  * and pet_tree_if_else.
@@ -67,6 +68,7 @@ struct pet_tree {
 			pet_expr *expr;
 		} e;
 		struct {
+			int independent;
 			int declared;
 			pet_expr *iv;
 			pet_expr *init;
@@ -114,7 +116,7 @@ __isl_give pet_tree *pet_tree_new_continue(isl_ctx *ctx);
 __isl_give pet_tree *pet_tree_new_infinite_loop(__isl_take pet_tree *body);
 __isl_give pet_tree *pet_tree_new_while(__isl_take pet_expr *cond,
 	__isl_take pet_tree *body);
-__isl_give pet_tree *pet_tree_new_for(int declared,
+__isl_give pet_tree *pet_tree_new_for(int independent, int declared,
 	__isl_take pet_expr *iv, __isl_take pet_expr *init,
 	__isl_take pet_expr *cond, __isl_take pet_expr *inc,
 	__isl_take pet_tree *body);
diff --git a/tree2scop.c b/tree2scop.c
index 435f8ab..fad5662 100644
--- a/tree2scop.c
+++ b/tree2scop.c
@@ -1133,6 +1133,126 @@ static int is_nested_allowed(__isl_keep isl_pw_aff *pa,
 	return 1;
 }
 
+/* Internal data structure for collect_local.
+ * "pc" and "state" are needed to extract pet_arrays for the local variables.
+ * "local" collects the results.
+ */
+struct pet_tree_collect_local_data {
+	pet_context *pc;
+	struct pet_state *state;
+	isl_union_set *local;
+};
+
+/* Add the variable accessed by "var" to data->local.
+ * We extract a representation of the variable from
+ * the pet_array constructed using extract_array
+ * to ensure consistency with the rest of the scop.
+ */
+static int add_local(struct pet_tree_collect_local_data *data,
+	__isl_keep pet_expr *var)
+{
+	struct pet_array *array;
+	isl_set *universe;
+
+	array = extract_array(var, data->pc, data->state);
+	if (!array)
+		return -1;
+
+	universe = isl_set_universe(isl_set_get_space(array->extent));
+	data->local = isl_union_set_add_set(data->local, universe);
+	pet_array_free(array);
+
+	return 0;
+}
+
+/* If the node "tree" declares a variable, then add it to
+ * data->local.
+ */
+static int extract_local_var(__isl_keep pet_tree *tree, void *user)
+{
+	enum pet_tree_type type;
+	struct pet_tree_collect_local_data *data = user;
+
+	type = pet_tree_get_type(tree);
+	if (type == pet_tree_decl || type == pet_tree_decl_init)
+		return add_local(data, tree->u.d.var);
+
+	return 0;
+}
+
+/* If the node "tree" is a for loop that declares its induction variable,
+ * then add it this induction variable to data->local.
+ */
+static int extract_local_iterator(__isl_keep pet_tree *tree, void *user)
+{
+	struct pet_tree_collect_local_data *data = user;
+
+	if (pet_tree_get_type(tree) == pet_tree_for && tree->u.l.declared)
+		return add_local(data, tree->u.l.iv);
+
+	return 0;
+}
+
+/* Collect and return all local variables of the for loop represented
+ * by "tree", with "scop" the corresponding pet_scop.
+ * "pc" and "state" are needed to extract pet_arrays for the local variables.
+ *
+ * We collect not only the variables that are declared inside "tree",
+ * but also the loop iterators that are declared anywhere inside
+ * any possible macro statements in "scop".
+ * The latter also appear as declared variable in the scop,
+ * whereas other declared loop iterators only appear implicitly
+ * in the iteration domains.
+ */
+static __isl_give isl_union_set *collect_local(struct pet_scop *scop,
+	__isl_keep pet_tree *tree, __isl_keep pet_context *pc,
+	struct pet_state *state)
+{
+	int i;
+	isl_ctx *ctx;
+	struct pet_tree_collect_local_data data = { pc, state };
+
+	ctx = pet_tree_get_ctx(tree);
+	data.local = isl_union_set_empty(isl_space_params_alloc(ctx, 0));
+
+	if (pet_tree_foreach_sub_tree(tree, &extract_local_var, &data) < 0)
+		return isl_union_set_free(data.local);
+
+	for (i = 0; i < scop->n_stmt; ++i) {
+		pet_tree *body = scop->stmts[i]->body;
+		if (pet_tree_foreach_sub_tree(body, &extract_local_iterator,
+						&data) < 0)
+			return isl_union_set_free(data.local);
+	}
+
+	return data.local;
+}
+
+/* Add an independence to "scop" if the for node "tree" was marked
+ * independent.
+ * "domain" is the set of loop iterators, with the current for loop
+ * innermost.  If "sign" is positive, then the inner iterator increases.
+ * Otherwise it decreases.
+ * "pc" and "state" are needed to extract pet_arrays for the local variables.
+ *
+ * If the tree was marked, then collect all local variables and
+ * add an independence.
+ */
+static struct pet_scop *set_independence(struct pet_scop *scop,
+	__isl_keep pet_tree *tree, __isl_keep isl_set *domain, int sign,
+	__isl_keep pet_context *pc, struct pet_state *state)
+{
+	isl_union_set *local;
+
+	if (!tree->u.l.independent)
+		return scop;
+
+	local = collect_local(scop, tree, pc, state);
+	scop = pet_scop_set_independent(scop, domain, local, sign);
+
+	return scop;
+}
+
 /* Construct a pet_scop for a for tree with static affine initialization
  * and constant increment within the context "pc".
  * The domain of "pc" has already been extended with an (at this point
@@ -1375,6 +1495,8 @@ static struct pet_scop *scop_from_affine_for(__isl_keep pet_tree *tree,
 		valid_inc = isl_set_intersect(valid_inc, valid_cond_init);
 		valid_inc = isl_set_project_out(valid_inc, isl_dim_set, pos, 1);
 		scop = pet_scop_restrict_context(scop, valid_inc);
+		scop = set_independence(scop, tree, domain, isl_val_sgn(inc),
+					pc, state);
 		isl_set_free(domain);
 	}
 
-- 
2.11.4.GIT