diff --git a/src/gallium/drivers/r600/sb/sb_dce_cleanup.cpp b/src/gallium/drivers/r600/sb/sb_dce_cleanup.cpp
index 79aef91..079c0d2 100644
--- a/src/gallium/drivers/r600/sb/sb_dce_cleanup.cpp
+++ b/src/gallium/drivers/r600/sb/sb_dce_cleanup.cpp
@@ -30,6 +30,19 @@
 
 namespace r600_sb {
 
+int dce_cleanup::run() {
+	int r;
+
+	// TODO Limit iterations? Probably would need to harden gcm pass due to
+	// kept unused ops, though.
+	do {
+		nodes_changed = false;
+		r = vpass::run();
+	} while (r == 0 && nodes_changed);
+
+	return r;
+}
+
 bool dce_cleanup::visit(node& n, bool enter) {
 	if (enter) {
 	} else {
@@ -110,7 +123,19 @@ bool dce_cleanup::visit(region_node& n, bool enter) {
 void dce_cleanup::cleanup_dst(node& n) {
 	if (!cleanup_dst_vec(n.dst) && remove_unused &&
 			!n.dst.empty() && !(n.flags & NF_DONT_KILL) && n.parent)
+	{
+		// Delete use references to the removed op from src values, to allow for
+		// additional removes in the next iteration.
+		for (vvec::iterator I = n.src.begin(), E = n.src.end(); I != E; ++I) {
+			value* v = *I;
+			if (v && v->def && v->uses.size())
+			{
+				v->remove_use(&n);
+			}
+		}
 		n.remove();
+		nodes_changed = true;
+	}
 }
 
 bool dce_cleanup::visit(container_node& n, bool enter) {
@@ -130,7 +155,7 @@ bool dce_cleanup::cleanup_dst_vec(vvec& vv) {
 		if (v->gvn_source && v->gvn_source->is_dead())
 			v->gvn_source = NULL;
 
-		if (v->is_dead() || (remove_unused && !v->is_rel() && !v->uses))
+		if (v->is_dead() || (remove_unused && !v->is_rel() && !v->uses.size()))
 			v = NULL;
 		else
 			alive = true;
diff --git a/src/gallium/drivers/r600/sb/sb_gcm.cpp b/src/gallium/drivers/r600/sb/sb_gcm.cpp
index 236b2ea..9c75389 100644
--- a/src/gallium/drivers/r600/sb/sb_gcm.cpp
+++ b/src/gallium/drivers/r600/sb/sb_gcm.cpp
@@ -199,10 +199,9 @@ void gcm::td_release_val(value *v) {
 		sblog << "\n";
 	);
 
-	use_info *u = v->uses;
-	while (u) {
+	for (uselist::iterator I = v->uses.begin(), E = v->uses.end(); I != E; ++I) {
+		use_info *u = *I;
 		if (u->op->parent != &pending) {
-			u = u->next;
 			continue;
 		}
 
@@ -212,6 +211,7 @@ void gcm::td_release_val(value *v) {
 			sblog << "\n";
 		);
 
+		assert(uses[u->op] > 0);
 		if (--uses[u->op] == 0) {
 			GCM_DUMP(
 				sblog << "td        released : ";
@@ -222,7 +222,6 @@ void gcm::td_release_val(value *v) {
 			pending.remove_node(u->op);
 			ready.push_back(u->op);
 		}
-		u = u->next;
 	}
 
 }
diff --git a/src/gallium/drivers/r600/sb/sb_ir.cpp b/src/gallium/drivers/r600/sb/sb_ir.cpp
index 5226893..d989dce 100644
--- a/src/gallium/drivers/r600/sb/sb_ir.cpp
+++ b/src/gallium/drivers/r600/sb/sb_ir.cpp
@@ -255,7 +255,7 @@ void container_node::expand() {
 void node::remove() {parent->remove_node(this);
 }
 
-value_hash node::hash_src() {
+value_hash node::hash_src() const {
 
 	value_hash h = 12345;
 
@@ -269,7 +269,7 @@ value_hash node::hash_src() {
 }
 
 
-value_hash node::hash() {
+value_hash node::hash() const {
 
 	if (parent && parent->subtype == NST_LOOP_PHI_CONTAINER)
 		return 47451;
diff --git a/src/gallium/drivers/r600/sb/sb_ir.h b/src/gallium/drivers/r600/sb/sb_ir.h
index 4fc4da2..74c0549 100644
--- a/src/gallium/drivers/r600/sb/sb_ir.h
+++ b/src/gallium/drivers/r600/sb/sb_ir.h
@@ -446,15 +446,16 @@ enum use_kind {
 };
 
 struct use_info {
-	use_info *next;
 	node *op;
 	use_kind kind;
 	int arg;
 
-	use_info(node *n, use_kind kind, int arg, use_info* next)
-		: next(next), op(n), kind(kind), arg(arg) {}
+	use_info(node *n, use_kind kind, int arg)
+		: op(n), kind(kind), arg(arg) {}
 };
 
+typedef std::list< use_info * > uselist;
+
 enum constraint_kind {
 	CK_SAME_REG,
 	CK_PACKED_BS,
@@ -498,7 +499,7 @@ public:
 	value_hash ghash;
 
 	node *def, *adef;
-	use_info *uses;
+	uselist uses;
 
 	ra_constraint *constraint;
 	ra_chunk *chunk;
@@ -585,6 +586,7 @@ public:
 	}
 
 	void add_use(node *n, use_kind kind, int arg);
+	void remove_use(const node *n);
 
 	value_hash hash();
 	value_hash rel_hash();
@@ -790,8 +792,8 @@ public:
 	void replace_with(node *n);
 	void remove();
 
-	virtual value_hash hash();
-	value_hash hash_src();
+	virtual value_hash hash() const;
+	value_hash hash_src() const;
 
 	virtual bool fold_dispatch(expr_handler *ex);
 
diff --git a/src/gallium/drivers/r600/sb/sb_pass.h b/src/gallium/drivers/r600/sb/sb_pass.h
index 0346df1..e878f8c 100644
--- a/src/gallium/drivers/r600/sb/sb_pass.h
+++ b/src/gallium/drivers/r600/sb/sb_pass.h
@@ -124,7 +124,9 @@ class dce_cleanup : public vpass {
 public:
 
 	dce_cleanup(shader &s) : vpass(s),
-		remove_unused(s.dce_flags & DF_REMOVE_UNUSED) {}
+		remove_unused(s.dce_flags & DF_REMOVE_UNUSED), nodes_changed(false) {}
+
+	virtual int run();
 
 	virtual bool visit(node &n, bool enter);
 	virtual bool visit(alu_group_node &n, bool enter);
@@ -140,6 +142,8 @@ private:
 	void cleanup_dst(node &n);
 	bool cleanup_dst_vec(vvec &vv);
 
+	// Did we alter/remove nodes during a single pass?
+	bool nodes_changed;
 };
 
 
diff --git a/src/gallium/drivers/r600/sb/sb_valtable.cpp b/src/gallium/drivers/r600/sb/sb_valtable.cpp
index eb242b1..0fc7f46 100644
--- a/src/gallium/drivers/r600/sb/sb_valtable.cpp
+++ b/src/gallium/drivers/r600/sb/sb_valtable.cpp
@@ -220,17 +223,33 @@ void value::add_use(node* n, use_kind kind, int arg) {
 	dump::dump_op(n);
 	sblog << "     kind " << kind << "    arg " << arg << "\n";
 	}
-	uses = new use_info(n, kind, arg, uses);
+	uses.push_back(new use_info(n, kind, arg));
 }
 
-unsigned value::use_count() {
-	use_info *u = uses;
-	unsigned c = 0;
-	while (u) {
-		++c;
-		u = u->next;
+struct use_node_comp {
+	explicit use_node_comp(const node *n) : n(n) {}
+	bool operator() (const use_info *u) {
+		return u->op->hash() == n->hash();
+	}
+
+	private:
+		const node *n;
+};
+
+void value::remove_use(const node *n) {
+	uselist::iterator it =
+		std::find_if(uses.begin(), uses.end(), use_node_comp(n));
+
+	if (it != uses.end())
+	{
+		//assert((*it)->kind == kind);
+		//assert((*it)->arg == arg);
+		uses.erase(it);
 	}
-	return c;
+}
+
+unsigned value::use_count() {
+	return uses.size();
 }
 
 bool value::is_global() {
@@ -274,13 +293,7 @@ bool value::is_prealloc() {
 }
 
 void value::delete_uses() {
-	use_info *u, *c = uses;
-	while (c) {
-		u = c->next;
-		delete c;
-		c = u;
-	}
-	uses = NULL;
+	uses.erase(uses.begin(), uses.end());
 }
 
 void ra_constraint::update_values() {
@@ -468,7 +481,7 @@ bool r600_sb::sb_value_set::add_vec(vvec& vv) {
 bool r600_sb::sb_value_set::contains(value* v) {
 	unsigned b = v->uid - 1;
 	if (b < bs.size())
-		return bs.get(v->uid - 1);
+		return bs.get(b);
 	else
 		return false;
 }