--- a/taskcluster/taskgraph/generator.py
+++ b/taskcluster/taskgraph/generator.py
@@ -193,17 +193,17 @@ class TaskGraphGenerator(object):
         full_task_set = TaskGraph(all_tasks, Graph(set(all_tasks), set()))
         self.verify_attributes(all_tasks)
         self.verify_run_using()
         yield 'full_task_set', full_task_set
 
         logger.info("Generating full task graph")
         edges = set()
         for t in full_task_set:
-            for dep, depname in t.get_dependencies(full_task_set):
+            for depname, dep in t.dependencies.iteritems():
                 edges.add((t.label, dep, depname))
 
         full_task_graph = TaskGraph(all_tasks,
                                     Graph(full_task_set.graph.nodes, edges))
         full_task_graph.for_each_task(verify_task_graph_symbol, scratch_pad={})
         full_task_graph.for_each_task(verify_gecko_v2_routes, scratch_pad={})
         logger.info("Full task graph contains %d tasks and %d dependencies" % (
             len(full_task_set.graph.nodes), len(edges)))

--- a/taskcluster/taskgraph/task/base.py
+++ b/taskcluster/taskgraph/task/base.py
@@ -13,59 +13,55 @@ from taskgraph.util.taskcluster import f
 class Task(object):
     """
     Representation of a task in a TaskGraph.  Each Task has, at creation:
 
     - kind: the name of the task kind
     - label; the label for this task
     - attributes: a dictionary of attributes for this task (used for filtering)
     - task: the task definition (JSON-able dictionary)
+    - index_paths: index paths where equivalent tasks might be found for optimization
+    - dependencies: tasks this one depends on, in the form {name: label}, for example
+      {'build': 'build-linux64/opt', 'docker-image': 'build-docker-image-desktop-test'}
 
     And later, as the task-graph processing proceeds:
 
     - task_id -- TaskCluster taskId under which this task will be created
     - optimized -- true if this task need not be performed
 
     A kind represents a collection of tasks that share common characteristics.
     For example, all build jobs.  Each instance of a kind is intialized with a
     path from which it draws its task configuration.  The instance is free to
     store as much local state as it needs.
     """
     __metaclass__ = abc.ABCMeta
 
-    def __init__(self, kind, label, attributes, task, index_paths=None):
+    def __init__(self, kind, label, attributes, task,
+                 index_paths=None, dependencies=None):
         self.kind = kind
         self.label = label
         self.attributes = attributes
         self.task = task
 
         self.task_id = None
         self.optimized = False
 
         self.attributes['kind'] = kind
 
         self.index_paths = index_paths or ()
+        self.dependencies = dependencies or {}
 
     def __eq__(self, other):
         return self.kind == other.kind and \
             self.label == other.label and \
             self.attributes == other.attributes and \
             self.task == other.task and \
             self.task_id == other.task_id and \
-            self.index_paths == other.index_paths
-
-    @abc.abstractmethod
-    def get_dependencies(self, taskgraph):
-        """
-        Get the set of task labels this task depends on, by querying the full
-        task set, given as `taskgraph`.
-
-        Returns a list of (task_label, dependency_name) pairs describing the
-        dependencies.
-        """
+            self.index_paths == other.index_paths and \
+            self.dependencies == other.dependencies
 
     def optimize(self, params):
         """
         Determine whether this task can be optimized, and if it can, what taskId
         it should be replaced with.
 
         The return value is a tuple `(optimized, taskId)`.  If `optimized` is
         true, then the task will be optimized (in other words, not included in

--- a/taskcluster/taskgraph/task/docker_image.py
+++ b/taskcluster/taskgraph/task/docker_image.py
@@ -35,18 +35,16 @@ def transform_inputs(inputs, kind, path,
 
 def load_tasks(kind, path, config, params, loaded_tasks):
     return transform_inputs(
         transform.get_inputs(kind, path, config, params, loaded_tasks),
         kind, path, config, params, loaded_tasks)
 
 
 class DockerImageTask(transform.TransformTask):
-    def get_dependencies(self, taskgraph):
-        return []
 
     def optimize(self, params):
         optimized, taskId = super(DockerImageTask, self).optimize(params)
         if optimized and taskId:
             try:
                 # Only return the task ID if the artifact exists for the indexed
                 # task.
                 request = urllib2.Request(get_artifact_url(

--- a/taskcluster/taskgraph/task/transform.py
+++ b/taskcluster/taskgraph/task/transform.py
@@ -79,24 +79,21 @@ class TransformTask(base.Task):
     """
     Tasks of this class are generated by applying transformations to a sequence
     of input entities.  By default, it gets those inputs from YAML data in the
     kind directory, but subclasses may override `get_inputs` to produce them in
     some other way.
     """
 
     def __init__(self, kind, task):
-        self.dependencies = task.get('dependencies', {})
         self.when = task.get('when', {})
         super(TransformTask, self).__init__(kind, task['label'],
                                             task['attributes'], task['task'],
-                                            index_paths=task.get('index-paths'))
-
-    def get_dependencies(self, taskgraph):
-        return [(label, name) for name, label in self.dependencies.items()]
+                                            index_paths=task.get('index-paths'),
+                                            dependencies=task.get('dependencies'))
 
     def optimize(self, params):
         bbb_task = False
 
         if self.index_paths:
             optimized, taskId = super(TransformTask, self).optimize(params)
             if optimized:
                 return optimized, taskId

--- a/taskcluster/taskgraph/test/test_generator.py
+++ b/taskcluster/taskgraph/test/test_generator.py
@@ -11,24 +11,25 @@ from taskgraph import graph, target_task
 from taskgraph.task import base
 from mozunit import main
 
 
 class FakeTask(base.Task):
 
     def __init__(self, **kwargs):
         self.i = kwargs.pop('i')
-        super(FakeTask, self).__init__(**kwargs)
 
-    def get_dependencies(self, full_task_set):
         i = self.i
         if i > 0:
-            return [('{}-t-{}'.format(self.kind, i - 1), 'prev')]
+            dependencies = {'prev': '{}-t-{}'.format(kwargs['kind'], i - 1)}
         else:
-            return []
+            dependencies = {}
+        kwargs['dependencies'] = dependencies
+
+        super(FakeTask, self).__init__(**kwargs)
 
     def optimize(self, params):
         return False, None
 
 
 def fake_loader(kind, path, config, parameters, loaded_tasks):
     return [FakeTask(kind=kind,
                      label='{}-t-{}'.format(kind, i),