diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CommonPrerequisiteValidator.java b/src/main/java/com/google/devtools/build/lib/analysis/CommonPrerequisiteValidator.java
index 14f7262..198cee2 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CommonPrerequisiteValidator.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CommonPrerequisiteValidator.java
@@ -41,7 +41,7 @@
       ConfiguredTargetAndData prerequisite,
       Attribute attribute) {
     validateDirectPrerequisiteLocation(contextBuilder, prerequisite);
-    validateDirectPrerequisiteVisibility(contextBuilder, prerequisite, attribute.getName());
+    validateDirectPrerequisiteVisibility(contextBuilder, prerequisite, attribute);
     validateDirectPrerequisiteForTestOnly(contextBuilder, prerequisite);
     validateDirectPrerequisiteForDeprecation(
         contextBuilder, contextBuilder.getRule(), prerequisite, contextBuilder.forAspect());
@@ -66,18 +66,43 @@
   protected abstract boolean allowExperimentalDeps(RuleContext.Builder context);
 
   private void validateDirectPrerequisiteVisibility(
-      RuleContext.Builder context, ConfiguredTargetAndData prerequisite, String attrName) {
+      RuleContext.Builder context, ConfiguredTargetAndData prerequisite, Attribute attribute) {
+    String attrName = attribute.getName();
     Rule rule = context.getRule();
     Target prerequisiteTarget = prerequisite.getTarget();
+
     // We don't check the visibility of late-bound attributes, because it would break some
     // features.
     if (!isSameLogicalPackage(
             rule.getLabel().getPackageIdentifier(),
             AliasProvider.getDependencyLabel(prerequisite.getConfiguredTarget())
                 .getPackageIdentifier())
-        && !context.isVisible(prerequisite.getConfiguredTarget())
         && !Attribute.isLateBound(attrName)) {
-      handleVisibilityConflict(context, prerequisite, rule);
+
+      // Determine if we should use the new visibility rules for tools.
+      boolean toolCheckAtDefinition = false;
+      try {
+        toolCheckAtDefinition =
+            context.getStarlarkSemantics().incompatibleVisibilityPrivateAttributesAtDefinition();
+      } catch (InterruptedException e) {
+        Thread.currentThread().interrupt();
+      }
+
+      if (!toolCheckAtDefinition
+          || !attribute.isImplicit()
+          || rule.getRuleClassObject().getRuleDefinitionEnvironmentLabel() == null) {
+        // Default check: The attribute must be visible from the target.
+        if (!context.isVisible(prerequisite.getConfiguredTarget())) {
+          handleVisibilityConflict(context, prerequisite, rule.getLabel());
+        }
+      } else {
+        // For implicit attributes, check if the prerequisite is visible from the location of the
+        // rule definition
+        Label implicitDefinition = rule.getRuleClassObject().getRuleDefinitionEnvironmentLabel();
+        if (!RuleContext.isVisible(implicitDefinition, prerequisite.getConfiguredTarget())) {
+          handleVisibilityConflict(context, prerequisite, implicitDefinition);
+        }
+      }
     }
 
     if (prerequisiteTarget instanceof PackageGroup) {
@@ -107,8 +132,8 @@
   }
 
   private void handleVisibilityConflict(
-      RuleContext.Builder context, ConfiguredTargetAndData prerequisite, Rule rule) {
-    if (packageUnderExperimental(rule.getLabel().getPackageIdentifier())
+      RuleContext.Builder context, ConfiguredTargetAndData prerequisite, Label rule) {
+    if (packageUnderExperimental(rule.getPackageIdentifier())
         && !checkVisibilityForExperimental(context)) {
       return;
     }
@@ -118,8 +143,7 @@
           String.format(
               "Target '%s' violates visibility of "
                   + "%s. Continuing because --nocheck_visibility is active",
-              rule.getLabel(),
-              AliasProvider.describeTargetWithAliases(prerequisite, TargetMode.WITHOUT_KIND));
+              rule, AliasProvider.describeTargetWithAliases(prerequisite, TargetMode.WITHOUT_KIND));
       context.ruleWarning(errorMessage);
     } else {
       String errorMessage =
@@ -127,8 +151,7 @@
               "%s is not visible from target '%s'. Check "
                   + "the visibility declaration of the former target if you think "
                   + "the dependency is legitimate",
-              AliasProvider.describeTargetWithAliases(prerequisite, TargetMode.WITHOUT_KIND),
-              rule.getLabel());
+              AliasProvider.describeTargetWithAliases(prerequisite, TargetMode.WITHOUT_KIND), rule);
       context.ruleError(errorMessage);
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
index 75442b9..1465a83 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/StarlarkSemanticsOptions.java
@@ -398,6 +398,20 @@
               + "instead return a list of provider instances.")
   public boolean incompatibleDisallowStructProviderSyntax;
 
+  @Option(
+      name = "incompatible_visibility_private_attributes_at_definition",
+      defaultValue = "false",
+      documentationCategory = OptionDocumentationCategory.STARLARK_SEMANTICS,
+      effectTags = {OptionEffectTag.BUILD_FILE_SEMANTICS},
+      metadataTags = {
+        OptionMetadataTag.INCOMPATIBLE_CHANGE,
+        OptionMetadataTag.TRIGGERED_BY_ALL_INCOMPATIBLE_CHANGES
+      },
+      help =
+          "If set to true, the visibility of private rule attributes is checked with respect "
+              + "to the rule definition, rather than the rule usage.")
+  public boolean incompatibleVisibilityPrivateAttributesAtDefinition;
+
   /** Controls legacy arguments to ctx.actions.Args#add. */
   @Option(
       name = "incompatible_disallow_old_style_args_add",
@@ -689,6 +703,8 @@
             .incompatibleRestrictNamedParams(incompatibleRestrictNamedParams)
             .incompatibleRunShellCommandString(incompatibleRunShellCommandString)
             .incompatibleStringJoinRequiresStrings(incompatibleStringJoinRequiresStrings)
+            .incompatibleVisibilityPrivateAttributesAtDefinition(
+                incompatibleVisibilityPrivateAttributesAtDefinition)
             .internalSkylarkFlagTestCanary(internalSkylarkFlagTestCanary)
             .incompatibleDoNotSplitLinkingCmdline(incompatibleDoNotSplitLinkingCmdline)
             .incompatibleDepsetForLibrariesToLinkGetter(incompatibleDepsetForLibrariesToLinkGetter)
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
index 3b77a92..9f7386b 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/StarlarkSemantics.java
@@ -201,6 +201,8 @@
 
   public abstract boolean incompatibleStringJoinRequiresStrings();
 
+  public abstract boolean incompatibleVisibilityPrivateAttributesAtDefinition();
+
   public abstract boolean internalSkylarkFlagTestCanary();
 
   public abstract boolean incompatibleDoNotSplitLinkingCmdline();
@@ -285,6 +287,7 @@
           .incompatibleRunShellCommandString(false)
           .incompatibleRestrictNamedParams(true)
           .incompatibleStringJoinRequiresStrings(true)
+          .incompatibleVisibilityPrivateAttributesAtDefinition(false)
           .internalSkylarkFlagTestCanary(false)
           .incompatibleDoNotSplitLinkingCmdline(true)
           .incompatibleDepsetForLibrariesToLinkGetter(true)
@@ -373,6 +376,8 @@
 
     public abstract Builder incompatibleStringJoinRequiresStrings(boolean value);
 
+    public abstract Builder incompatibleVisibilityPrivateAttributesAtDefinition(boolean value);
+
     public abstract Builder internalSkylarkFlagTestCanary(boolean value);
 
     public abstract Builder incompatibleDoNotSplitLinkingCmdline(boolean value);
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/VisibilityTest.java b/src/test/java/com/google/devtools/build/lib/analysis/VisibilityTest.java
new file mode 100644
index 0000000..9bf9999
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/analysis/VisibilityTest.java
@@ -0,0 +1,168 @@
+// Copyright 2019 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.analysis;
+
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.testutil.MoreAsserts.assertThrows;
+
+import com.google.devtools.build.lib.analysis.util.AnalysisTestCase;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Test for visibility of targets. */
+@RunWith(JUnit4.class)
+public class VisibilityTest extends AnalysisTestCase {
+
+  void setupArgsScenario() throws Exception {
+    scratch.file("tool/tool.sh", "#!/bin/sh", "echo Hello > $2", "cat $1 >> $2");
+    scratch.file("rule/BUILD");
+    scratch.file(
+        "rule/rule.bzl",
+        "def _impl(ctx):",
+        "  output = ctx.actions.declare_file(ctx.label.name + '.out')",
+        "  ctx.actions.run(",
+        "    inputs = ctx.files._tool + ctx.files.data,",
+        "    executable = ctx.files._tool[0].path,",
+        "    arguments =  [f.path for f in ctx.files.data] + [output.path],",
+        "    outputs = [output],",
+        "  )",
+        "",
+        "greet = rule(",
+        "  implementation = _impl,",
+        "  attrs = {",
+        "    'data' : attr.label(allow_files=True),",
+        "    '_tool' : attr.label(cfg='host', allow_files=True,",
+        "                         default = Label('//tool:tool.sh')),",
+        "  },",
+        "  outputs = {'out' : '%{name}.out'},",
+        ")");
+    scratch.file("data/data.txt", "World");
+    scratch.file(
+        "use/BUILD",
+        "load('//rule:rule.bzl', 'greet')",
+        "",
+        "greet(",
+        "  name = 'world',",
+        "  data = '//data:data.txt',",
+        ")");
+  }
+
+  @Test
+  public void testToolVisibilityRuleCheckAtRule() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:public'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//rule:__pkg__'])");
+    useConfiguration("--incompatible_visibility_private_attributes_at_definition");
+    update("//use:world");
+    assertThat(hasErrors(getConfiguredTarget("//use:world"))).isFalse();
+  }
+
+  @Test
+  public void testToolVisibilityRuleCheckAtUse() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:public'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//rule:__pkg__'])");
+    useConfiguration("--noincompatible_visibility_private_attributes_at_definition");
+
+    reporter.removeHandler(failFastHandler);
+    assertThrows(ViewCreationFailedException.class, () -> update("//use:world"));
+  }
+
+  @Test
+  public void testToolVisibilityUseCheckAtUse() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:public'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//use:__pkg__'])");
+    useConfiguration("--noincompatible_visibility_private_attributes_at_definition");
+    update("//use:world");
+    assertThat(hasErrors(getConfiguredTarget("//use:world"))).isFalse();
+  }
+
+  @Test
+  public void testToolVisibilityUseCheckAtRule() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:public'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//use:__pkg__'])");
+    useConfiguration("--incompatible_visibility_private_attributes_at_definition");
+
+    reporter.removeHandler(failFastHandler);
+    assertThrows(ViewCreationFailedException.class, () -> update("//use:world"));
+  }
+
+  @Test
+  public void testToolVisibilityPrivateCheckAtUse() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:public'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//visibility:private'])");
+    useConfiguration("--noincompatible_visibility_private_attributes_at_definition");
+
+    reporter.removeHandler(failFastHandler);
+    assertThrows(ViewCreationFailedException.class, () -> update("//use:world"));
+  }
+
+  @Test
+  public void testToolVisibilityPrivateCheckAtRule() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:public'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//visibility:private'])");
+    useConfiguration("--incompatible_visibility_private_attributes_at_definition");
+
+    reporter.removeHandler(failFastHandler);
+    assertThrows(ViewCreationFailedException.class, () -> update("//use:world"));
+  }
+
+  @Test
+  public void testDataVisibilityUseCheckPrivateAtUse() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//use:__pkg__'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//visibility:public'])");
+    useConfiguration("--noincompatible_visibility_private_attributes_at_definition");
+    update("//use:world");
+    assertThat(hasErrors(getConfiguredTarget("//use:world"))).isFalse();
+  }
+
+  @Test
+  public void testDataVisibilityUseCheckPrivateAtRule() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//use:__pkg__'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//visibility:public'])");
+    useConfiguration("--incompatible_visibility_private_attributes_at_definition");
+    update("//use:world");
+    assertThat(hasErrors(getConfiguredTarget("//use:world"))).isFalse();
+  }
+
+  @Test
+  public void testDataVisibilityPrivateCheckPrivateAtRule() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:private'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//visibility:public'])");
+    useConfiguration("--incompatible_visibility_private_attributes_at_definition");
+
+    reporter.removeHandler(failFastHandler);
+    assertThrows(ViewCreationFailedException.class, () -> update("//use:world"));
+  }
+
+  @Test
+  public void testDataVisibilityPrivateCheckPrivateAtUse() throws Exception {
+    setupArgsScenario();
+    scratch.file("data/BUILD", "exports_files(['data.txt'], visibility=['//visibility:private'])");
+    scratch.file("tool/BUILD", "exports_files(['tool.sh'], visibility=['//visibility:public'])");
+    useConfiguration("--noincompatible_visibility_private_attributes_at_definition");
+
+    reporter.removeHandler(failFastHandler);
+    assertThrows(ViewCreationFailedException.class, () -> update("//use:world"));
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
index 3d99da4..f81268f 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
@@ -463,7 +463,7 @@
             targetConfig.extendedSanityChecks(),
             targetConfig.allowAnalysisFailures(),
             eventHandler,
-            /*env=*/ null);
+            skyframeExecutor.getSkyFunctionEnvironmentForTesting(eventHandler));
     return getRuleContextForTesting(eventHandler, target, env, configurations);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index 90ff3e8..714a6e6 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -258,6 +258,8 @@
     getOutputPath().createDirectoryAndParents();
     ImmutableList<PrecomputedValue.Injected> extraPrecomputedValues =
         ImmutableList.of(
+            PrecomputedValue.injected(
+                PrecomputedValue.STARLARK_SEMANTICS, StarlarkSemantics.DEFAULT_SEMANTICS),
             PrecomputedValue.injected(PrecomputedValue.REPO_ENV, ImmutableMap.<String, String>of()),
             PrecomputedValue.injected(
                 RepositoryDelegatorFunction.REPOSITORY_OVERRIDES,
@@ -582,7 +584,7 @@
         /*extendedSanityChecks=*/ false,
         /*allowAnalysisFailures=*/ false,
         reporter,
-        /* env= */ null);
+        skyframeExecutor.getSkyFunctionEnvironmentForTesting(reporter));
   }
 
   /**
@@ -2000,7 +2002,7 @@
 
     @Override
     public StarlarkSemantics getSkylarkSemantics() {
-      throw new UnsupportedOperationException();
+      return starlarkSemanticsOptions.toSkylarkSemantics();
     }
 
     @Override
diff --git a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
index b88537e..aed9a4f 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/SkylarkSemanticsConsistencyTest.java
@@ -160,6 +160,7 @@
         "--incompatible_restrict_named_params=" + rand.nextBoolean(),
         "--incompatible_run_shell_command_string=" + rand.nextBoolean(),
         "--incompatible_string_join_requires_strings=" + rand.nextBoolean(),
+        "--incompatible_visibility_private_attributes_at_definition=" + rand.nextBoolean(),
         "--incompatible_restrict_string_escapes=" + rand.nextBoolean(),
         "--incompatible_disallow_dict_lookup_unhashable_keys=" + rand.nextBoolean(),
         "--incompatible_disallow_hashing_frozen_mutables=" + rand.nextBoolean(),
@@ -213,6 +214,7 @@
         .incompatibleRestrictNamedParams(rand.nextBoolean())
         .incompatibleRunShellCommandString(rand.nextBoolean())
         .incompatibleStringJoinRequiresStrings(rand.nextBoolean())
+        .incompatibleVisibilityPrivateAttributesAtDefinition(rand.nextBoolean())
         .incompatibleRestrictStringEscapes(rand.nextBoolean())
         .incompatibleDisallowDictLookupUnhashableKeys(rand.nextBoolean())
         .incompatibleDisallowHashingFrozenMutables(rand.nextBoolean())
diff --git a/src/test/java/com/google/devtools/build/lib/rules/android/ResourceTestBase.java b/src/test/java/com/google/devtools/build/lib/rules/android/ResourceTestBase.java
index e1a5d17..d75a86f 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/android/ResourceTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/android/ResourceTestBase.java
@@ -241,7 +241,7 @@
             targetConfig.extendedSanityChecks(),
             targetConfig.allowAnalysisFailures(),
             eventHandler,
-            null),
+            skyframeExecutor.getSkyFunctionEnvironmentForTesting(eventHandler)),
         new BuildConfigurationCollection(
             ImmutableList.of(dummy.getConfiguration()), dummy.getHostConfiguration()));
   }