diff --git a/bootstrap/bootstrap.go b/bootstrap/bootstrap.go
index c596ac4..c05f799 100644
--- a/bootstrap/bootstrap.go
+++ b/bootstrap/bootstrap.go
@@ -143,7 +143,7 @@
 func pluginDeps(ctx blueprint.BottomUpMutatorContext) {
 	if pkg, ok := ctx.Module().(*goPackage); ok {
 		for _, plugin := range pkg.properties.PluginFor {
-			ctx.AddReverseDependency(ctx.Module(), plugin)
+			ctx.AddReverseDependency(ctx.Module(), nil, plugin)
 		}
 	}
 }
diff --git a/context.go b/context.go
index 0dc84a2..fdb977a 100644
--- a/context.go
+++ b/context.go
@@ -140,7 +140,7 @@
 	moduleProperties []interface{}
 
 	// set during ResolveDependencies
-	directDeps  []*moduleInfo
+	directDeps  []depInfo
 	missingDeps []string
 
 	// set during updateDependencies
@@ -157,6 +157,11 @@
 	actionDefs localBuildActions
 }
 
+type depInfo struct {
+	module *moduleInfo
+	tag    DependencyTag
+}
+
 func (module *moduleInfo) String() string {
 	s := fmt.Sprintf("module %q", module.properties.Name)
 	if module.variantName != "" {
@@ -960,7 +965,7 @@
 
 		m := *origModule
 		newModule := &m
-		newModule.directDeps = append([]*moduleInfo(nil), origModule.directDeps...)
+		newModule.directDeps = append([]depInfo{}, origModule.directDeps...)
 		newModule.logicModule = newLogicModule
 		newModule.variant = newVariant
 		newModule.dependencyVariant = origModule.dependencyVariant.clone()
@@ -997,9 +1002,9 @@
 	mutatorName, variationName string) (errs []error) {
 
 	for i, dep := range module.directDeps {
-		if dep.logicModule == nil {
+		if dep.module.logicModule == nil {
 			var newDep *moduleInfo
-			for _, m := range dep.splitModules {
+			for _, m := range dep.module.splitModules {
 				if m.variant[mutatorName] == variationName {
 					newDep = m
 					break
@@ -1008,12 +1013,12 @@
 			if newDep == nil {
 				errs = append(errs, &Error{
 					Err: fmt.Errorf("failed to find variation %q for module %q needed by %q",
-						variationName, dep.properties.Name, module.properties.Name),
+						variationName, dep.module.properties.Name, module.properties.Name),
 					Pos: module.pos,
 				})
 				continue
 			}
-			module.directDeps[i] = newDep
+			module.directDeps[i].module = newDep
 		}
 	}
 
@@ -1137,7 +1142,7 @@
 // AddVariationDependencies on DynamicDependencyModuleContext.  Otherwise it
 // is simply those names listed in its "deps" property.
 func blueprintDepsMutator(ctx BottomUpMutatorContext) {
-	ctx.AddDependency(ctx.Module(), ctx.moduleInfo().properties.Deps...)
+	ctx.AddDependency(ctx.Module(), nil, ctx.moduleInfo().properties.Deps...)
 
 	if dynamicDepender, ok := ctx.Module().(DynamicDependerModule); ok {
 		func() {
@@ -1152,7 +1157,7 @@
 				return
 			}
 
-			ctx.AddDependency(ctx.Module(), dynamicDeps...)
+			ctx.AddDependency(ctx.Module(), nil, dynamicDeps...)
 		}()
 	}
 }
@@ -1173,7 +1178,7 @@
 	return nil
 }
 
-func (c *Context) addDependency(module *moduleInfo, depName string) []error {
+func (c *Context) addDependency(module *moduleInfo, tag DependencyTag, depName string) []error {
 	if depName == module.properties.Name {
 		return []error{&Error{
 			Err: fmt.Errorf("%q depends on itself", depName),
@@ -1181,7 +1186,7 @@
 		}}
 	}
 
-	depInfo, ok := c.moduleGroups[depName]
+	depGroup, ok := c.moduleGroups[depName]
 	if !ok {
 		if c.allowMissingDependencies {
 			module.missingDeps = append(module.missingDeps, depName)
@@ -1194,20 +1199,20 @@
 		}}
 	}
 
-	for _, m := range module.directDeps {
-		if m.group == depInfo {
-			return nil
+	if m := c.findMatchingVariant(module, depGroup); m != nil {
+		for _, dep := range module.directDeps {
+			if m == dep.module {
+				// TODO(ccross): what if adding a dependency with a different tag?
+				return nil
+			}
 		}
-	}
-
-	if m := c.findMatchingVariant(module, depInfo); m != nil {
-		module.directDeps = append(module.directDeps, m)
+		module.directDeps = append(module.directDeps, depInfo{m, tag})
 		return nil
 	}
 
 	return []error{&Error{
 		Err: fmt.Errorf("dependency %q of %q missing variant %q",
-			depInfo.modules[0].properties.Name, module.properties.Name,
+			depGroup.modules[0].properties.Name, module.properties.Name,
 			c.prettyPrintVariant(module.dependencyVariant)),
 		Pos: module.pos,
 	}}
@@ -1243,9 +1248,9 @@
 }
 
 func (c *Context) addVariationDependency(module *moduleInfo, variations []Variation,
-	depName string, far bool) []error {
+	tag DependencyTag, depName string, far bool) []error {
 
-	depInfo, ok := c.moduleGroups[depName]
+	depGroup, ok := c.moduleGroups[depName]
 	if !ok {
 		if c.allowMissingDependencies {
 			module.missingDeps = append(module.missingDeps, depName)
@@ -1271,7 +1276,7 @@
 		newVariant[v.Mutator] = v.Variation
 	}
 
-	for _, m := range depInfo.modules {
+	for _, m := range depGroup.modules {
 		var found bool
 		if far {
 			found = m.variant.subset(newVariant)
@@ -1288,20 +1293,20 @@
 			// AddVariationDependency allows adding a dependency on itself, but only if
 			// that module is earlier in the module list than this one, since we always
 			// run GenerateBuildActions in order for the variants of a module
-			if depInfo == module.group && beforeInModuleList(module, m, module.group.modules) {
+			if depGroup == module.group && beforeInModuleList(module, m, module.group.modules) {
 				return []error{&Error{
 					Err: fmt.Errorf("%q depends on later version of itself", depName),
 					Pos: module.pos,
 				}}
 			}
-			module.directDeps = append(module.directDeps, m)
+			module.directDeps = append(module.directDeps, depInfo{m, tag})
 			return nil
 		}
 	}
 
 	return []error{&Error{
 		Err: fmt.Errorf("dependency %q of %q missing variant %q",
-			depInfo.modules[0].properties.Name, module.properties.Name,
+			depGroup.modules[0].properties.Name, module.properties.Name,
 			c.prettyPrintVariant(newVariant)),
 		Pos: module.pos,
 	}}
@@ -1403,7 +1408,7 @@
 		}
 
 		for _, dep := range module.directDeps {
-			deps[dep] = true
+			deps[dep.module] = true
 		}
 
 		module.reverseDeps = []*moduleInfo{}
@@ -1641,7 +1646,7 @@
 func (c *Context) runBottomUpMutator(config interface{},
 	name string, mutator BottomUpMutator) (errs []error) {
 
-	reverseDeps := make(map[*moduleInfo][]*moduleInfo)
+	reverseDeps := make(map[*moduleInfo][]depInfo)
 
 	for _, module := range c.modulesSorted {
 		newModules := make([]*moduleInfo, 0, 1)
@@ -1682,8 +1687,8 @@
 		// Fix up any remaining dependencies on modules that were split into variants
 		// by replacing them with the first variant
 		for i, dep := range module.directDeps {
-			if dep.logicModule == nil {
-				module.directDeps[i] = dep.splitModules[0]
+			if dep.module.logicModule == nil {
+				module.directDeps[i].module = dep.module.splitModules[0]
 			}
 		}
 
@@ -1697,7 +1702,7 @@
 	}
 
 	for module, deps := range reverseDeps {
-		sort.Sort(moduleSorter(deps))
+		sort.Sort(depSorter(deps))
 		module.directDeps = append(module.directDeps, deps...)
 	}
 
@@ -1963,12 +1968,12 @@
 
 	var walk func(module *moduleInfo)
 	walk = func(module *moduleInfo) {
-		for _, moduleDep := range module.directDeps {
-			if !visited[moduleDep] {
-				visited[moduleDep] = true
-				visiting = moduleDep
-				if visit(moduleDep.logicModule, module.logicModule) {
-					walk(moduleDep)
+		for _, dep := range module.directDeps {
+			if !visited[dep.module] {
+				visited[dep.module] = true
+				visiting = dep.module
+				if visit(dep.module.logicModule, module.logicModule) {
+					walk(dep.module)
 				}
 			}
 		}
@@ -1993,9 +1998,9 @@
 	var walk func(module *moduleInfo)
 	walk = func(module *moduleInfo) {
 		visited[module] = true
-		for _, moduleDep := range module.directDeps {
-			if !visited[moduleDep] {
-				walk(moduleDep)
+		for _, dep := range module.directDeps {
+			if !visited[dep.module] {
+				walk(dep.module)
 			}
 		}
 
@@ -2024,9 +2029,9 @@
 	var walk func(module *moduleInfo)
 	walk = func(module *moduleInfo) {
 		visited[module] = true
-		for _, moduleDep := range module.directDeps {
-			if !visited[moduleDep] {
-				walk(moduleDep)
+		for _, dep := range module.directDeps {
+			if !visited[dep.module] {
+				walk(dep.module)
 			}
 		}
 
@@ -2041,40 +2046,6 @@
 	walk(topModule)
 }
 
-func (c *Context) visitDirectDeps(module *moduleInfo, visit func(Module)) {
-	var dep *moduleInfo
-
-	defer func() {
-		if r := recover(); r != nil {
-			panic(newPanicErrorf(r, "VisitDirectDeps(%s, %s) for dependency %s",
-				module, funcName(visit), dep))
-		}
-	}()
-
-	for _, dep = range module.directDeps {
-		visit(dep.logicModule)
-	}
-}
-
-func (c *Context) visitDirectDepsIf(module *moduleInfo, pred func(Module) bool,
-	visit func(Module)) {
-
-	var dep *moduleInfo
-
-	defer func() {
-		if r := recover(); r != nil {
-			panic(newPanicErrorf(r, "VisitDirectDepsIf(%s, %s, %s) for dependency %s",
-				module, funcName(pred), funcName(visit), dep))
-		}
-	}()
-
-	for _, dep = range module.directDeps {
-		if pred(dep.logicModule) {
-			visit(dep.logicModule)
-		}
-	}
-}
-
 func (c *Context) sortedModuleNames() []string {
 	if c.cachedSortedModuleNames == nil {
 		c.cachedSortedModuleNames = make([]string, 0, len(c.moduleGroups))
@@ -2693,6 +2664,26 @@
 	return nil
 }
 
+type depSorter []depInfo
+
+func (s depSorter) Len() int {
+	return len(s)
+}
+
+func (s depSorter) Less(i, j int) bool {
+	iName := s[i].module.properties.Name
+	jName := s[j].module.properties.Name
+	if iName == jName {
+		iName = s[i].module.variantName
+		jName = s[j].module.variantName
+	}
+	return iName < jName
+}
+
+func (s depSorter) Swap(i, j int) {
+	s[i], s[j] = s[j], s[i]
+}
+
 type moduleSorter []*moduleInfo
 
 func (s moduleSorter) Len() int {
diff --git a/module_ctx.go b/module_ctx.go
index 381b54a..055e7f7 100644
--- a/module_ctx.go
+++ b/module_ctx.go
@@ -129,6 +129,7 @@
 
 	OtherModuleName(m Module) string
 	OtherModuleErrorf(m Module, fmt string, args ...interface{})
+	OtherModuleDependencyTag(m Module) DependencyTag
 
 	VisitDirectDeps(visit func(Module))
 	VisitDirectDepsIf(pred func(Module) bool, visit func(Module))
@@ -154,10 +155,11 @@
 var _ BaseModuleContext = (*baseModuleContext)(nil)
 
 type baseModuleContext struct {
-	context *Context
-	config  interface{}
-	module  *moduleInfo
-	errs    []error
+	context  *Context
+	config   interface{}
+	module   *moduleInfo
+	errs     []error
+	visiting depInfo
 }
 
 func (d *baseModuleContext) moduleInfo() *moduleInfo {
@@ -236,12 +238,12 @@
 	handledMissingDeps bool
 }
 
-func (m *moduleContext) OtherModuleName(logicModule Module) string {
+func (m *baseModuleContext) OtherModuleName(logicModule Module) string {
 	module := m.context.moduleInfo[logicModule]
 	return module.properties.Name
 }
 
-func (m *moduleContext) OtherModuleErrorf(logicModule Module, format string,
+func (m *baseModuleContext) OtherModuleErrorf(logicModule Module, format string,
 	args ...interface{}) {
 
 	module := m.context.moduleInfo[logicModule]
@@ -251,25 +253,64 @@
 	})
 }
 
-func (m *moduleContext) VisitDirectDeps(visit func(Module)) {
-	m.context.visitDirectDeps(m.module, visit)
+func (m *baseModuleContext) OtherModuleDependencyTag(logicModule Module) DependencyTag {
+	// fast path for calling OtherModuleDependencyTag from inside VisitDirectDeps
+	if logicModule == m.visiting.module.logicModule {
+		return m.visiting.tag
+	}
+
+	for _, dep := range m.module.directDeps {
+		if dep.module.logicModule == logicModule {
+			return dep.tag
+		}
+	}
+
+	return nil
 }
 
-func (m *moduleContext) VisitDirectDepsIf(pred func(Module) bool, visit func(Module)) {
-	m.context.visitDirectDepsIf(m.module, pred, visit)
+func (m *baseModuleContext) VisitDirectDeps(visit func(Module)) {
+	defer func() {
+		if r := recover(); r != nil {
+			panic(newPanicErrorf(r, "VisitDirectDeps(%s, %s) for dependency %s",
+				m.module, funcName(visit), m.visiting.module))
+		}
+	}()
+
+	for _, dep := range m.module.directDeps {
+		m.visiting = dep
+		visit(dep.module.logicModule)
+	}
+	m.visiting = depInfo{}
 }
 
-func (m *moduleContext) VisitDepsDepthFirst(visit func(Module)) {
+func (m *baseModuleContext) VisitDirectDepsIf(pred func(Module) bool, visit func(Module)) {
+	defer func() {
+		if r := recover(); r != nil {
+			panic(newPanicErrorf(r, "VisitDirectDepsIf(%s, %s, %s) for dependency %s",
+				m.module, funcName(pred), funcName(visit), m.visiting.module))
+		}
+	}()
+
+	for _, dep := range m.module.directDeps {
+		m.visiting = dep
+		if pred(dep.module.logicModule) {
+			visit(dep.module.logicModule)
+		}
+	}
+	m.visiting = depInfo{}
+}
+
+func (m *baseModuleContext) VisitDepsDepthFirst(visit func(Module)) {
 	m.context.visitDepsDepthFirst(m.module, visit)
 }
 
-func (m *moduleContext) VisitDepsDepthFirstIf(pred func(Module) bool,
+func (m *baseModuleContext) VisitDepsDepthFirstIf(pred func(Module) bool,
 	visit func(Module)) {
 
 	m.context.visitDepsDepthFirstIf(m.module, pred, visit)
 }
 
-func (m *moduleContext) WalkDeps(visit func(Module, Module) bool) {
+func (m *baseModuleContext) WalkDeps(visit func(Module, Module) bool) {
 	m.context.walkDeps(m.module, visit)
 }
 
@@ -342,7 +383,7 @@
 type mutatorContext struct {
 	baseModuleContext
 	name        string
-	reverseDeps map[*moduleInfo][]*moduleInfo
+	reverseDeps map[*moduleInfo][]depInfo
 }
 
 type baseMutatorContext interface {
@@ -363,6 +404,7 @@
 
 	OtherModuleName(m Module) string
 	OtherModuleErrorf(m Module, fmt string, args ...interface{})
+	OtherModuleDependencyTag(m Module) DependencyTag
 
 	VisitDirectDeps(visit func(Module))
 	VisitDirectDepsIf(pred func(Module) bool, visit func(Module))
@@ -374,13 +416,13 @@
 type BottomUpMutatorContext interface {
 	baseMutatorContext
 
-	AddDependency(module Module, name ...string)
-	AddReverseDependency(module Module, name string)
+	AddDependency(module Module, tag DependencyTag, name ...string)
+	AddReverseDependency(module Module, tag DependencyTag, name string)
 	CreateVariations(...string) []Module
 	CreateLocalVariations(...string) []Module
 	SetDependencyVariation(string)
-	AddVariationDependencies([]Variation, ...string)
-	AddFarVariationDependencies([]Variation, ...string)
+	AddVariationDependencies([]Variation, DependencyTag, ...string)
+	AddFarVariationDependencies([]Variation, DependencyTag, ...string)
 }
 
 // A Mutator function is called for each Module, and can use
@@ -396,6 +438,22 @@
 type BottomUpMutator func(mctx BottomUpMutatorContext)
 type EarlyMutator func(mctx EarlyMutatorContext)
 
+// DependencyTag is an interface to an arbitrary object that embeds BaseDependencyTag.  It can be
+// used to transfer information on a dependency between the mutator that called AddDependency
+// and the GenerateBuildActions method.  Variants created by CreateVariations have a copy of the
+// interface (pointing to the same concrete object) from their original module.
+type DependencyTag interface {
+	dependencyTag(DependencyTag)
+}
+
+type BaseDependencyTag struct {
+}
+
+func (BaseDependencyTag) dependencyTag(DependencyTag) {
+}
+
+var _ DependencyTag = BaseDependencyTag{}
+
 // Split a module into mulitple variants, one for each name in the variationNames
 // parameter.  It returns a list of new modules in the same order as the variationNames
 // list.
@@ -456,9 +514,9 @@
 // Add a dependency to the given module.
 // Does not affect the ordering of the current mutator pass, but will be ordered
 // correctly for all future mutator passes.
-func (mctx *mutatorContext) AddDependency(module Module, deps ...string) {
+func (mctx *mutatorContext) AddDependency(module Module, tag DependencyTag, deps ...string) {
 	for _, dep := range deps {
-		errs := mctx.context.addDependency(mctx.context.moduleInfo[module], dep)
+		errs := mctx.context.addDependency(mctx.context.moduleInfo[module], tag, dep)
 		if len(errs) > 0 {
 			mctx.errs = append(mctx.errs, errs...)
 		}
@@ -470,7 +528,7 @@
 // correctly for all future mutator passes.  All reverse dependencies for a destination module are
 // collected until the end of the mutator pass, sorted by name, and then appended to the destination
 // module's dependency list.
-func (mctx *mutatorContext) AddReverseDependency(module Module, destName string) {
+func (mctx *mutatorContext) AddReverseDependency(module Module, tag DependencyTag, destName string) {
 	destModule, errs := mctx.context.findReverseDependency(mctx.context.moduleInfo[module], destName)
 	if len(errs) > 0 {
 		mctx.errs = append(mctx.errs, errs...)
@@ -478,18 +536,18 @@
 	}
 
 	mctx.reverseDeps[destModule] = append(mctx.reverseDeps[destModule],
-		mctx.context.moduleInfo[module])
+		depInfo{mctx.context.moduleInfo[module], tag})
 }
 
 // AddVariationDependencies adds deps as dependencies of the current module, but uses the variations
 // argument to select which variant of the dependency to use.  A variant of the dependency must
 // exist that matches the all of the non-local variations of the current module, plus the variations
 // argument.
-func (mctx *mutatorContext) AddVariationDependencies(variations []Variation,
+func (mctx *mutatorContext) AddVariationDependencies(variations []Variation, tag DependencyTag,
 	deps ...string) {
 
 	for _, dep := range deps {
-		errs := mctx.context.addVariationDependency(mctx.module, variations, dep, false)
+		errs := mctx.context.addVariationDependency(mctx.module, variations, tag, dep, false)
 		if len(errs) > 0 {
 			mctx.errs = append(mctx.errs, errs...)
 		}
@@ -503,50 +561,13 @@
 //
 // Unlike AddVariationDependencies, the variations of the current module are ignored - the
 // depdendency only needs to match the supplied variations.
-func (mctx *mutatorContext) AddFarVariationDependencies(variations []Variation,
+func (mctx *mutatorContext) AddFarVariationDependencies(variations []Variation, tag DependencyTag,
 	deps ...string) {
 
 	for _, dep := range deps {
-		errs := mctx.context.addVariationDependency(mctx.module, variations, dep, true)
+		errs := mctx.context.addVariationDependency(mctx.module, variations, tag, dep, true)
 		if len(errs) > 0 {
 			mctx.errs = append(mctx.errs, errs...)
 		}
 	}
 }
-
-func (mctx *mutatorContext) OtherModuleName(logicModule Module) string {
-	module := mctx.context.moduleInfo[logicModule]
-	return module.properties.Name
-}
-
-func (mctx *mutatorContext) OtherModuleErrorf(logicModule Module, format string,
-	args ...interface{}) {
-
-	module := mctx.context.moduleInfo[logicModule]
-	mctx.errs = append(mctx.errs, &Error{
-		Err: fmt.Errorf(format, args...),
-		Pos: module.pos,
-	})
-}
-
-func (mctx *mutatorContext) VisitDirectDeps(visit func(Module)) {
-	mctx.context.visitDirectDeps(mctx.module, visit)
-}
-
-func (mctx *mutatorContext) VisitDirectDepsIf(pred func(Module) bool, visit func(Module)) {
-	mctx.context.visitDirectDepsIf(mctx.module, pred, visit)
-}
-
-func (mctx *mutatorContext) VisitDepsDepthFirst(visit func(Module)) {
-	mctx.context.visitDepsDepthFirst(mctx.module, visit)
-}
-
-func (mctx *mutatorContext) VisitDepsDepthFirstIf(pred func(Module) bool,
-	visit func(Module)) {
-
-	mctx.context.visitDepsDepthFirstIf(mctx.module, pred, visit)
-}
-
-func (mctx *mutatorContext) WalkDeps(visit func(Module, Module) bool) {
-	mctx.context.walkDeps(mctx.module, visit)
-}