--- a/taskcluster/taskgraph/generator.py
+++ b/taskcluster/taskgraph/generator.py
@@ -7,17 +7,17 @@ import logging
 import os
 import yaml
 
 from . import filter_tasks
 from .graph import Graph
 from .taskgraph import TaskGraph
 from .optimize import optimize_task_graph
 from .util.python_path import find_object
-from .util.verifydoc import verify_docs
+from .util.verify import verify_docs, verify_task_graph_symbol
 
 logger = logging.getLogger(__name__)
 
 
 class Kind(object):
 
     def __init__(self, name, path, config):
         self.name = name
@@ -212,16 +212,17 @@ class TaskGraphGenerator(object):
 
         yield 'target_task_set', target_task_set
 
         logger.info("Generating target task graph")
         target_graph = full_task_graph.graph.transitive_closure(target_tasks)
         target_task_graph = TaskGraph(
             {l: all_tasks[l] for l in target_graph.nodes},
             target_graph)
+        target_task_graph.for_each_task(verify_task_graph_symbol, scratch_pad={})
         yield 'target_task_graph', target_task_graph
 
         logger.info("Generating optimized task graph")
         do_not_optimize = set()
 
         if not self.parameters.get('optimize_target_tasks', True):
             do_not_optimize = target_task_set.graph.nodes
         optimized_task_graph, label_to_taskid = optimize_task_graph(target_task_graph,

--- a/taskcluster/taskgraph/taskgraph.py
+++ b/taskcluster/taskgraph/taskgraph.py
@@ -41,16 +41,21 @@ class TaskGraph(object):
                 'task': task.task,
                 'kind_implementation': implementation
             }
             if task.task_id:
                 task_json['task_id'] = task.task_id
             tasks[key] = task_json
         return tasks
 
+    def for_each_task(self, f, *args, **kwargs):
+        for task_label in self.graph.visit_postorder():
+            task = self.tasks[task_label]
+            f(task, self, *args, **kwargs)
+
     def __getitem__(self, label):
         "Get a task by label"
         return self.tasks[label]
 
     def __iter__(self):
         "Iterate over tasks in undefined order"
         return self.tasks.itervalues()
 

new file mode 100644
--- /dev/null
+++ b/taskcluster/taskgraph/util/verify.py
@@ -0,0 +1,67 @@
+# -*- coding: utf-8 -*-
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+import re
+import os
+
+base_path = os.path.join(os.getcwd(), "taskcluster/docs/")
+
+
+def verify_docs(filename, identifiers, appearing_as):
+
+    # We ignore identifiers starting with '_' for the sake of tests.
+    # Strings starting with "_" are ignored for doc verification
+    # hence they can be used for faking test values
+    with open(os.path.join(base_path, filename)) as fileObject:
+        doctext = "".join(fileObject.readlines())
+        if appearing_as == "inline-literal":
+            expression_list = [
+                "``" + identifier + "``"
+                for identifier in identifiers
+                if not identifier.startswith("_")
+            ]
+        elif appearing_as == "heading":
+            expression_list = [
+                identifier + "\n(?:(?:(?:-+\n)+)|(?:(?:.+\n)+))"
+                for identifier in identifiers
+                if not identifier.startswith("_")
+            ]
+        else:
+            raise Exception("appearing_as = `{}` not defined".format(appearing_as))
+
+        for expression, identifier in zip(expression_list, identifiers):
+            match_group = re.search(expression, doctext)
+            if not match_group:
+                raise Exception(
+                    "{}: `{}` missing from doc file: `{}`"
+                    .format(appearing_as, identifier, filename)
+                )
+
+
+def verify_task_graph_symbol(task, taskgraph, scratch_pad):
+    """
+        This function verifies that tuple
+        (collection.keys(), machine.platform, groupSymbol, symbol) is unique
+        for a target task graph.
+    """
+    task_dict = task.task
+    if "extra" in task_dict:
+        extra = task_dict["extra"]
+        if "treeherder" in extra:
+            treeherder = extra["treeherder"]
+
+            collection_keys = tuple(sorted(treeherder.get('collection', {}).keys()))
+            platform = treeherder.get('machine', {}).get('platform')
+            group_symbol = treeherder.get('groupSymbol')
+            symbol = treeherder.get('symbol')
+
+            key = (collection_keys, platform, group_symbol, symbol)
+            if key in scratch_pad:
+                raise Exception(
+                    "conflict between `{}`:`{}` for values `{}`"
+                    .format(task.label, scratch_pad[key], key)
+                )
+            else:
+                scratch_pad[key] = task.label

deleted file mode 100644
--- a/taskcluster/taskgraph/util/verifydoc.py
+++ /dev/null
@@ -1,40 +0,0 @@
-# -*- coding: utf-8 -*-
-# This Source Code Form is subject to the terms of the Mozilla Public
-# License, v. 2.0. If a copy of the MPL was not distributed with this
-# file, You can obtain one at http://mozilla.org/MPL/2.0/.
-
-import re
-import os
-
-base_path = os.path.join(os.getcwd(), "taskcluster/docs/")
-
-
-def verify_docs(filename, identifiers, appearing_as):
-
-    # We ignore identifiers starting with '_' for the sake of tests.
-    # Strings starting with "_" are ignored for doc verification
-    # hence they can be used for faking test values
-    with open(os.path.join(base_path, filename)) as fileObject:
-        doctext = "".join(fileObject.readlines())
-        if appearing_as == "inline-literal":
-            expression_list = [
-                "``" + identifier + "``"
-                for identifier in identifiers
-                if not identifier.startswith("_")
-            ]
-        elif appearing_as == "heading":
-            expression_list = [
-                identifier + "\n(?:(?:(?:-+\n)+)|(?:(?:.+\n)+))"
-                for identifier in identifiers
-                if not identifier.startswith("_")
-            ]
-        else:
-            raise Exception("appearing_as = `{}` not defined".format(appearing_as))
-
-        for expression, identifier in zip(expression_list, identifiers):
-            match_group = re.search(expression, doctext)
-            if not match_group:
-                raise Exception(
-                    "{}: `{}` missing from doc file: `{}`"
-                    .format(appearing_as, identifier, filename)
-                )