diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index 8d452e5..3332b46 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -33,6 +33,7 @@
         "//src/main/java/com/google/devtools/build/lib/graph:srcs",
         "//src/main/java/com/google/devtools/build/lib/profiler:srcs",
         "//src/main/java/com/google/devtools/build/lib/profiler/callcounts:srcs",
+        "//src/main/java/com/google/devtools/build/lib/profiler/memory:srcs",
         "//src/main/java/com/google/devtools/build/lib/query2:srcs",
         "//src/main/java/com/google/devtools/build/lib/remote:srcs",
         "//src/main/java/com/google/devtools/build/lib/rules/apple/cpp:srcs",
@@ -478,6 +479,7 @@
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/graph",
         "//src/main/java/com/google/devtools/build/lib/profiler",
+        "//src/main/java/com/google/devtools/build/lib/profiler/memory:current_rule_tracker",
         "//src/main/java/com/google/devtools/build/lib/shell",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
         "//src/main/java/com/google/devtools/build/lib/vfs",
@@ -582,6 +584,7 @@
         "//src/main/java/com/google/devtools/build/lib/buildeventservice",
         "//src/main/java/com/google/devtools/build/lib/clock",
         "//src/main/java/com/google/devtools/build/lib/profiler/callcounts:callcounts_module",
+        "//src/main/java/com/google/devtools/build/lib/profiler/memory:allocationtracker_module",
         "//src/main/java/com/google/devtools/build/lib/remote",
         "//src/main/java/com/google/devtools/build/lib/sandbox",
         "//src/main/java/com/google/devtools/build/lib/shell",
@@ -1009,6 +1012,7 @@
         "//src/main/java/com/google/devtools/build/lib/exec/local",
         "//src/main/java/com/google/devtools/build/lib/profiler",
         "//src/main/java/com/google/devtools/build/lib/profiler:profiler-output",
+        "//src/main/java/com/google/devtools/build/lib/profiler/memory:allocationtracker",
         "//src/main/java/com/google/devtools/build/lib/query2",
         "//src/main/java/com/google/devtools/build/lib/query2:query-engine",
         "//src/main/java/com/google/devtools/build/lib/query2:query-output",
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
index 7635078..744d94c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java
@@ -63,6 +63,7 @@
 import com.google.devtools.build.lib.packages.RuleVisibility;
 import com.google.devtools.build.lib.packages.SkylarkProviderIdentifier;
 import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.profiler.memory.CurrentRuleTracker;
 import com.google.devtools.build.lib.skyframe.BuildConfigurationValue;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
@@ -227,14 +228,19 @@
       Preconditions.checkArgument(
           toolchainContext != null,
           "ToolchainContext should never be null when creating a ConfiguredTarget for a Rule");
-      return createRule(
-          analysisEnvironment,
-          (Rule) target,
-          config,
-          hostConfig,
-          prerequisiteMap,
-          configConditions,
-          toolchainContext);
+      try {
+        CurrentRuleTracker.beginConfiguredTarget(((Rule) target).getRuleClassObject());
+        return createRule(
+            analysisEnvironment,
+            (Rule) target,
+            config,
+            hostConfig,
+            prerequisiteMap,
+            configConditions,
+            toolchainContext);
+      } finally {
+        CurrentRuleTracker.endConfiguredTarget();
+      }
     }
 
     // Visibility, like all package groups, doesn't have a configuration
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java
index 6c84873..2ed3cc3 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/skylark/SkylarkRuleClassFunctions.java
@@ -27,7 +27,6 @@
 import static com.google.devtools.build.lib.syntax.Type.STRING;
 import static com.google.devtools.build.lib.syntax.Type.STRING_LIST;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.cache.CacheBuilder;
 import com.google.common.cache.CacheLoader;
 import com.google.common.cache.LoadingCache;
@@ -67,6 +66,7 @@
 import com.google.devtools.build.lib.packages.RuleFactory;
 import com.google.devtools.build.lib.packages.RuleFactory.BuildLangTypedAttributeValuesMap;
 import com.google.devtools.build.lib.packages.RuleFactory.InvalidRuleException;
+import com.google.devtools.build.lib.packages.RuleFunction;
 import com.google.devtools.build.lib.packages.SkylarkAspect;
 import com.google.devtools.build.lib.packages.SkylarkExportable;
 import com.google.devtools.build.lib.packages.SkylarkProvider;
@@ -548,7 +548,7 @@
           builder.setRuleDefinitionEnvironment(funcallEnv);
           builder.addRequiredToolchains(collectToolchainLabels(toolchains, ast));
 
-          return new RuleFunction(builder, type, attributes, ast.getLocation());
+          return new SkylarkRuleFunction(builder, type, attributes, ast.getLocation());
         }
       };
 
@@ -799,7 +799,8 @@
       };
 
   /** The implementation for the magic function "rule" that creates Skylark rule classes */
-  public static final class RuleFunction extends BaseFunction implements SkylarkExportable {
+  public static final class SkylarkRuleFunction extends BaseFunction
+      implements SkylarkExportable, RuleFunction {
     private RuleClass.Builder builder;
 
     private RuleClass ruleClass;
@@ -808,7 +809,9 @@
     private final Location definitionLocation;
     private Label skylarkLabel;
 
-    public RuleFunction(Builder builder, RuleClassType type,
+    public SkylarkRuleFunction(
+        Builder builder,
+        RuleClassType type,
         ImmutableList<Pair<String, SkylarkAttr.Descriptor>> attributes,
         Location definitionLocation) {
       super("rule", FunctionSignature.KWARGS);
@@ -884,13 +887,12 @@
         addAttribute(definitionLocation, builder,
             descriptor.build(attribute.getFirst()));
       }
-      this.ruleClass = builder.build(ruleClassName);
+      this.ruleClass = builder.build(ruleClassName, skylarkLabel + "%" + ruleClassName);
 
       this.builder = null;
       this.attributes = null;
     }
 
-    @VisibleForTesting
     public RuleClass getRuleClass() {
       Preconditions.checkState(ruleClass != null && builder == null);
       return ruleClass;
@@ -912,10 +914,10 @@
    * file.
    *
    * <p>Order in list is significant: all {@link SkylarkAspect}s need to be exported before {@link
-   * RuleFunction}s etc.
+   * SkylarkRuleFunction}s etc.
    */
   private static final ImmutableList<Class<? extends SkylarkExportable>> EXPORTABLES =
-      ImmutableList.of(SkylarkProvider.class, SkylarkAspect.class, RuleFunction.class);
+      ImmutableList.of(SkylarkProvider.class, SkylarkAspect.class, SkylarkRuleFunction.class);
 
   @SkylarkSignature(
     name = "Label",
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java b/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
index 885bbc2..4c52695 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
@@ -51,7 +51,8 @@
           com.google.devtools.build.lib.bazel.rules.BazelRulesModule.class,
           com.google.devtools.build.lib.bazel.rules.BazelStrategyModule.class,
           com.google.devtools.build.lib.buildeventservice.BazelBuildEventServiceModule.class,
-          com.google.devtools.build.lib.profiler.callcounts.CallcountsModule.class);
+          com.google.devtools.build.lib.profiler.callcounts.CallcountsModule.class,
+          com.google.devtools.build.lib.profiler.memory.AllocationTrackerModule.class);
 
   public static void main(String[] args) {
     BlazeVersionInfo.setBuildInfo(tryGetBuildInfo());
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
index b8aea7c..251ba6e 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/skylark/SkylarkRepositoryModule.java
@@ -169,7 +169,7 @@
         throw new IllegalStateException("Function is not an identifier or method call");
       }
       try {
-        RuleClass ruleClass = builder.build(ruleClassName);
+        RuleClass ruleClass = builder.build(ruleClassName, ruleClassName);
         PackageContext context = PackageFactory.getContext(env, ast);
         @SuppressWarnings("unchecked")
         Map<String, Object> attributeValues = (Map<String, Object>) args[0];
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AspectClass.java b/src/main/java/com/google/devtools/build/lib/packages/AspectClass.java
index 6b5f08a..c0ea7ce 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AspectClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AspectClass.java
@@ -104,4 +104,8 @@
    * Returns an aspect name.
    */
   String getName();
+
+  default String getKey() {
+    return getName();
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index df241d4..015ac01 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -331,7 +331,7 @@
   private static final Logger logger = Logger.getLogger(PackageFactory.class.getName());
 
   private final RuleFactory ruleFactory;
-  private final ImmutableMap<String, RuleFunction> ruleFunctions;
+  private final ImmutableMap<String, BuiltinRuleFunction> ruleFunctions;
   private final RuleClassProvider ruleClassProvider;
 
   private AtomicReference<? extends UnixGlob.FilesystemCalls> syscalls;
@@ -1206,21 +1206,22 @@
     return value;
   }
 
-  private static ImmutableMap<String, RuleFunction> buildRuleFunctions(RuleFactory ruleFactory) {
-    ImmutableMap.Builder<String, RuleFunction> result = ImmutableMap.builder();
+  private static ImmutableMap<String, BuiltinRuleFunction> buildRuleFunctions(
+      RuleFactory ruleFactory) {
+    ImmutableMap.Builder<String, BuiltinRuleFunction> result = ImmutableMap.builder();
     for (String ruleClass : ruleFactory.getRuleClassNames()) {
-      result.put(ruleClass, new RuleFunction(ruleClass, ruleFactory));
+      result.put(ruleClass, new BuiltinRuleFunction(ruleClass, ruleFactory));
     }
     return result.build();
   }
 
   /** {@link BuiltinFunction} adapter for creating {@link Rule}s for native {@link RuleClass}es. */
-  private static class RuleFunction extends BuiltinFunction {
+  private static class BuiltinRuleFunction extends BuiltinFunction implements RuleFunction {
     private final String ruleClassName;
     private final RuleFactory ruleFactory;
     private final RuleClass ruleClass;
 
-    RuleFunction(String ruleClassName, RuleFactory ruleFactory) {
+    BuiltinRuleFunction(String ruleClassName, RuleFactory ruleFactory) {
       super(ruleClassName, FunctionSignature.KWARGS, BuiltinFunction.USE_AST_ENV, /*isRule=*/ true);
       this.ruleClassName = ruleClassName;
       this.ruleFactory = Preconditions.checkNotNull(ruleFactory, "ruleFactory was null");
@@ -1256,6 +1257,11 @@
       RuleFactory.createAndAddRule(
           context, ruleClass, attributeValues, ast, env, attributeContainer);
     }
+
+    @Override
+    public RuleClass getRuleClass() {
+      return ruleClass;
+    }
   }
 
   /**
@@ -1584,7 +1590,7 @@
         .setup("repository_name", SkylarkNativeModule.repositoryName)
         .setup("environment_group", newEnvironmentGroupFunction.apply(context));
 
-    for (Entry<String, RuleFunction> entry : ruleFunctions.entrySet()) {
+    for (Entry<String, BuiltinRuleFunction> entry : ruleFunctions.entrySet()) {
       pkgEnv.setup(entry.getKey(), entry.getValue());
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index 6e1e70b..a031f2c 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -550,13 +550,12 @@
      * @throws IllegalStateException if any of the required attributes is missing
      */
     public RuleClass build() {
-      return build(name);
+      // For built-ins, name == key
+      return build(name, name);
     }
 
-    /**
-     * Same as {@link #build} except with setting the name parameter.
-     */
-    public RuleClass build(String name) {
+    /** Same as {@link #build} except with setting the name and key parameters. */
+    public RuleClass build(String name, String key) {
       Preconditions.checkArgument(this.name.isEmpty() || this.name.equals(name));
       type.checkName(name);
       type.checkAttributes(attributes);
@@ -575,6 +574,7 @@
       }
       return new RuleClass(
           name,
+          key,
           skylark,
           skylarkExecutable,
           skylarkTestable,
@@ -1025,6 +1025,8 @@
 
   private final String name; // e.g. "cc_library"
 
+  private final String key; // Just the name for native, label + name for skylark
+
   /**
    * The kind of target represented by this RuleClass (e.g. "cc_library rule").
    * Note: Even though there is partial duplication with the {@link RuleClass#name} field,
@@ -1154,6 +1156,7 @@
   @VisibleForTesting
   RuleClass(
       String name,
+      String key,
       boolean isSkylark,
       boolean skylarkExecutable,
       boolean skylarkTestable,
@@ -1180,6 +1183,7 @@
       Set<Label> requiredToolchains,
       Attribute... attributes) {
     this.name = name;
+    this.key = key;
     this.isSkylark = isSkylark;
     this.targetKind = name + Rule.targetKindSuffix();
     this.skylarkExecutable = skylarkExecutable;
@@ -1277,6 +1281,11 @@
     return name;
   }
 
+  /** Returns a unique key. Used for profiling purposes. */
+  public String getKey() {
+    return key;
+  }
+
   /**
    * Returns the target kind of this class of rule (e.g. "cc_library rule").
    */
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleFunction.java b/src/main/java/com/google/devtools/build/lib/packages/RuleFunction.java
new file mode 100644
index 0000000..3b73342
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleFunction.java
@@ -0,0 +1,20 @@
+// Copyright 2017 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.packages;
+
+/** Marker interface for a native or Skylark rule function. */
+public interface RuleFunction {
+  RuleClass getRuleClass();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTracker.java b/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTracker.java
new file mode 100644
index 0000000..9631279
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTracker.java
@@ -0,0 +1,370 @@
+// Copyright 2017 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.profiler.memory;
+
+import com.google.common.base.Objects;
+import com.google.common.base.Strings;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.MapMaker;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ConditionallyThreadCompatible;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.packages.AspectClass;
+import com.google.devtools.build.lib.packages.RuleClass;
+import com.google.devtools.build.lib.packages.RuleFunction;
+import com.google.devtools.build.lib.syntax.ASTNode;
+import com.google.devtools.build.lib.syntax.BaseFunction;
+import com.google.devtools.build.lib.syntax.Callstack;
+import com.google.monitoring.runtime.instrumentation.Sampler;
+import com.google.perftools.profiles.ProfileProto.Function;
+import com.google.perftools.profiles.ProfileProto.Line;
+import com.google.perftools.profiles.ProfileProto.Profile;
+import com.google.perftools.profiles.ProfileProto.Profile.Builder;
+import com.google.perftools.profiles.ProfileProto.Sample;
+import com.google.perftools.profiles.ProfileProto.ValueType;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.time.Instant;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+import java.util.zip.GZIPOutputStream;
+import javax.annotation.Nullable;
+
+/** Tracks allocations for memory reporting. */
+@ConditionallyThreadCompatible
+public class AllocationTracker implements Sampler {
+
+  private static class AllocationSample {
+    @Nullable final RuleClass ruleClass; // Current rule being analysed, if any
+    @Nullable final AspectClass aspectClass; // Current aspect being analysed, if any
+    final List<Object> callstack; // Skylark callstack, if any
+    final long bytes;
+
+    AllocationSample(
+        @Nullable RuleClass ruleClass,
+        @Nullable AspectClass aspectClass,
+        List<Object> callstack,
+        long bytes) {
+      this.ruleClass = ruleClass;
+      this.aspectClass = aspectClass;
+      this.callstack = callstack;
+      this.bytes = bytes;
+    }
+  }
+
+  private final Map<Object, AllocationSample> allocations =
+      new MapMaker().weakKeys().concurrencyLevel(1).makeMap();
+  private final int samplePeriod;
+  private final int sampleVariance;
+  private boolean enabled = true;
+
+  /**
+   * Cheap wrapper class for a long. Avoids having to do two thread-local lookups per allocation.
+   */
+  private static final class LongValue {
+    long value;
+  }
+
+  private final ThreadLocal<LongValue> currentSampleBytes = ThreadLocal.withInitial(LongValue::new);
+  private final ThreadLocal<Long> nextSampleBytes = ThreadLocal.withInitial(this::getNextSample);
+  private final Random random = new Random();
+
+  AllocationTracker(int samplePeriod, int variance) {
+    this.samplePeriod = samplePeriod;
+    this.sampleVariance = variance;
+  }
+
+  @Override
+  @ThreadSafe
+  public void sampleAllocation(int count, String desc, Object newObj, long size) {
+    if (!enabled) {
+      return;
+    }
+    List<Object> callstack = Callstack.get();
+    RuleClass ruleClass = CurrentRuleTracker.getRule();
+    AspectClass aspectClass = CurrentRuleTracker.getAspect();
+    // Should we bother sampling?
+    if (callstack.isEmpty() && ruleClass == null && aspectClass == null) {
+      return;
+    }
+    // If we start getting stack overflows here, it's because the memory sampling
+    // implementation has changed to call back into the sampling method immediately on
+    // every allocation. Since thread locals can allocate, this can in this case lead
+    // to infinite recursion. This method will then need to be rewritten to not
+    // allocate, or at least not allocate to obtain its sample counters.
+    LongValue bytesValue = currentSampleBytes.get();
+    long bytes = bytesValue.value + size;
+    if (bytes < nextSampleBytes.get()) {
+      bytesValue.value = bytes;
+      return;
+    }
+    bytesValue.value = 0;
+    nextSampleBytes.set(getNextSample());
+    allocations.put(
+        newObj,
+        new AllocationSample(ruleClass, aspectClass, ImmutableList.copyOf(callstack), bytes));
+  }
+
+  private long getNextSample() {
+    return (long) samplePeriod
+        + (sampleVariance > 0 ? (random.nextInt(sampleVariance * 2) - sampleVariance) : 0);
+  }
+
+  /** A pair of rule/aspect name and the bytes it consumes. */
+  public static class RuleBytes {
+    private final String name;
+    private long bytes;
+
+    public RuleBytes(String name) {
+      this.name = name;
+    }
+
+    /** The name of the rule or aspect. */
+    public String getName() {
+      return name;
+    }
+
+    /** The number of bytes total occupied by this rule or aspect class. */
+    public long getBytes() {
+      return bytes;
+    }
+
+    public RuleBytes addBytes(long bytes) {
+      this.bytes += bytes;
+      return this;
+    }
+
+    @Override
+    public String toString() {
+      return String.format("RuleBytes(%s, %d)", name, bytes);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      RuleBytes ruleBytes = (RuleBytes) o;
+      return bytes == ruleBytes.bytes && Objects.equal(name, ruleBytes.name);
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hashCode(name, bytes);
+    }
+  }
+
+  @Nullable
+  private static RuleFunction getRuleCreationCall(AllocationSample allocationSample) {
+    Object topOfCallstack = Iterables.getLast(allocationSample.callstack, null);
+    if (topOfCallstack instanceof RuleFunction) {
+      return (RuleFunction) topOfCallstack;
+    }
+    return null;
+  }
+
+  /**
+   * Returns the total memory consumption for rules and aspects, keyed by {@link RuleClass#getKey}
+   * or {@link AspectClass#getKey}.
+   */
+  public void getRuleMemoryConsumption(
+      Map<String, RuleBytes> rules, Map<String, RuleBytes> aspects) {
+    // Make sure we don't track our own allocations
+    enabled = false;
+    System.gc();
+
+    // Get loading phase memory for rules.
+    for (AllocationSample allocationSample : allocations.values()) {
+      RuleFunction ruleCreationCall = getRuleCreationCall(allocationSample);
+      if (ruleCreationCall != null) {
+        RuleClass ruleClass = ruleCreationCall.getRuleClass();
+        String key = ruleClass.getKey();
+        RuleBytes ruleBytes = rules.computeIfAbsent(key, k -> new RuleBytes(ruleClass.getName()));
+        rules.put(key, ruleBytes.addBytes(allocationSample.bytes));
+      }
+    }
+    // Get analysis phase memory for rules and aspects
+    for (AllocationSample allocationSample : allocations.values()) {
+      if (allocationSample.ruleClass != null) {
+        String key = allocationSample.ruleClass.getKey();
+        RuleBytes ruleBytes =
+            rules.computeIfAbsent(key, k -> new RuleBytes(allocationSample.ruleClass.getName()));
+        rules.put(key, ruleBytes.addBytes(allocationSample.bytes));
+      }
+      if (allocationSample.aspectClass != null) {
+        String key = allocationSample.aspectClass.getKey();
+        RuleBytes ruleBytes =
+            aspects.computeIfAbsent(
+                key, k -> new RuleBytes(allocationSample.aspectClass.getName()));
+        aspects.put(key, ruleBytes.addBytes(allocationSample.bytes));
+      }
+    }
+
+    enabled = true;
+  }
+
+  /** Dumps all skylark analysis time allocations to a pprof-compatible file. */
+  public void dumpSkylarkAllocations(String path) throws IOException {
+    // Make sure we don't track our own allocations
+    enabled = false;
+    System.gc();
+    Profile profile = buildMemoryProfile();
+    try (GZIPOutputStream outputStream = new GZIPOutputStream(new FileOutputStream(path))) {
+      profile.writeTo(outputStream);
+      outputStream.finish();
+    }
+    enabled = true;
+  }
+
+  Profile buildMemoryProfile() {
+    Profile.Builder profile = Profile.newBuilder();
+    StringTable stringTable = new StringTable(profile);
+    FunctionTable functionTable = new FunctionTable(profile, stringTable);
+    LocationTable locationTable = new LocationTable(profile, functionTable);
+    profile.addSampleType(
+        ValueType.newBuilder()
+            .setType(stringTable.get("memory"))
+            .setUnit(stringTable.get("bytes"))
+            .build());
+    for (AllocationSample allocationSample : allocations.values()) {
+      // Skip empty callstacks
+      if (allocationSample.callstack.isEmpty()) {
+        continue;
+      }
+      Sample.Builder sample = Sample.newBuilder().addValue(allocationSample.bytes);
+      int line = -1;
+      String file = null;
+      for (int i = allocationSample.callstack.size() - 1; i >= 0; --i) {
+        Object object = allocationSample.callstack.get(i);
+        if (line == -1) {
+          final Location location;
+          if (object instanceof ASTNode) {
+            location = ((ASTNode) object).getLocation();
+          } else if (object instanceof BaseFunction) {
+            location = ((BaseFunction) object).getLocation();
+          } else {
+            throw new IllegalStateException(
+                "Unknown node type: " + object.getClass().getSimpleName());
+          }
+          if (location != null) {
+            file = location.getPath() != null ? location.getPath().getPathString() : "<unknown>";
+            line = location.getStartLine() != null ? location.getStartLine() : -1;
+          } else {
+            file = "<native>";
+          }
+        }
+        String function = null;
+        if (object instanceof BaseFunction) {
+          BaseFunction baseFunction = (BaseFunction) object;
+          function = baseFunction.getName();
+        }
+        if (function != null) {
+          sample.addLocationId(
+              locationTable.get(Strings.nullToEmpty(file), Strings.nullToEmpty(function), line));
+          line = -1;
+          file = null;
+        }
+      }
+      profile.addSample(sample.build());
+    }
+    profile.setTimeNanos(Instant.now().getEpochSecond() * 1000000000);
+    return profile.build();
+  }
+
+  private static class StringTable {
+    final Profile.Builder profile;
+    final Map<String, Long> table = new HashMap<>();
+    long index = 0;
+
+    StringTable(Profile.Builder profile) {
+      this.profile = profile;
+      get(""); // 0 is reserved for the empty string
+    }
+
+    long get(String str) {
+      return table.computeIfAbsent(
+          str,
+          key -> {
+            profile.addStringTable(key);
+            return index++;
+          });
+    }
+  }
+
+  private static class FunctionTable {
+    final Profile.Builder profile;
+    final StringTable stringTable;
+    final Map<String, Long> table = new HashMap<>();
+    long index = 1; // 0 is reserved
+
+    FunctionTable(Profile.Builder profile, StringTable stringTable) {
+      this.profile = profile;
+      this.stringTable = stringTable;
+    }
+
+    long get(String file, String function) {
+      return table.computeIfAbsent(
+          file + "#" + function,
+          key -> {
+            Function fn =
+                Function.newBuilder()
+                    .setId(index)
+                    .setFilename(stringTable.get(file))
+                    .setName(stringTable.get(function))
+                    .build();
+            profile.addFunction(fn);
+            table.put(key, index);
+            return index++;
+          });
+    }
+  }
+
+  private static class LocationTable {
+    final Profile.Builder profile;
+    final FunctionTable functionTable;
+    final Map<String, Long> table = new HashMap<>();
+    long index = 1; // 0 is reserved
+
+    LocationTable(Builder profile, FunctionTable functionTable) {
+      this.profile = profile;
+      this.functionTable = functionTable;
+    }
+
+    long get(String file, String function, long line) {
+      return table.computeIfAbsent(
+          file + "#" + function + "#" + line,
+          key -> {
+            com.google.perftools.profiles.ProfileProto.Location location =
+                com.google.perftools.profiles.ProfileProto.Location.newBuilder()
+                    .setId(index)
+                    .addLine(
+                        Line.newBuilder()
+                            .setFunctionId(functionTable.get(file, function))
+                            .setLine(line)
+                            .build())
+                    .build();
+            profile.addLocation(location);
+            table.put(key, index);
+            return index++;
+          });
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTrackerInstaller.java b/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTrackerInstaller.java
new file mode 100644
index 0000000..73fc24d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTrackerInstaller.java
@@ -0,0 +1,23 @@
+// Copyright 2017 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.profiler.memory;
+
+import com.google.monitoring.runtime.instrumentation.AllocationRecorder;
+
+class AllocationTrackerInstaller {
+  static void installAllocationTracker(AllocationTracker tracker) {
+    AllocationRecorder.addSampler(tracker);
+  }
+}
\ No newline at end of file
diff --git a/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTrackerModule.java b/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTrackerModule.java
new file mode 100644
index 0000000..4a503e4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/profiler/memory/AllocationTrackerModule.java
@@ -0,0 +1,79 @@
+// Copyright 2017 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.profiler.memory;
+
+import com.google.devtools.build.lib.analysis.BlazeDirectories;
+import com.google.devtools.build.lib.analysis.BlazeVersionInfo;
+import com.google.devtools.build.lib.analysis.ServerDirectories;
+import com.google.devtools.build.lib.clock.Clock;
+import com.google.devtools.build.lib.runtime.BlazeModule;
+import com.google.devtools.build.lib.runtime.BlazeRuntime;
+import com.google.devtools.build.lib.runtime.WorkspaceBuilder;
+import com.google.devtools.build.lib.syntax.Callstack;
+import com.google.devtools.common.options.OptionsProvider;
+import java.util.UUID;
+
+/**
+ * A {@link BlazeModule} that can be used to record interesting information about all allocations
+ * done during every command on the current blaze server.
+ *
+ * <p>To enable tracking, you must pass:
+ *
+ * <ol>
+ *   <li>--host_jvm_args=-javaagent:(path to Google's java agent jar)
+ *   <li>--host_jvm_args=-RULE_MEMORY_TRACKER=1
+ * </ol>
+ *
+ * <p>The memory tracking information is accessible via blaze dump --rules and blaze dump
+ * --skylark_memory=(path)
+ */
+public class AllocationTrackerModule extends BlazeModule {
+
+  /** Sample allocations every N bytes for performance. */
+  private static final int SAMPLE_SIZE = 256 * 1024;
+  /**
+   * Add some variance to how often we sample, to avoid sampling the same callstack all the time due
+   * to overly regular allocation patterns.
+   */
+  private static final int VARIANCE = 100;
+
+  private boolean enabled;
+  private AllocationTracker tracker = null;
+
+  @Override
+  public void blazeStartup(
+      OptionsProvider startupOptions,
+      BlazeVersionInfo versionInfo,
+      UUID instanceId,
+      ServerDirectories directories,
+      Clock clock) {
+    String memoryTrackerPropery = System.getProperty("RULE_MEMORY_TRACKER");
+    enabled = memoryTrackerPropery != null && memoryTrackerPropery.equals("1");
+    if (enabled) {
+      tracker = new AllocationTracker(SAMPLE_SIZE, VARIANCE);
+      Callstack.setEnabled(true);
+      CurrentRuleTracker.setEnabled(true);
+      AllocationTrackerInstaller.installAllocationTracker(tracker);
+    }
+  }
+
+  @Override
+  public void workspaceInit(
+      BlazeRuntime runtime, BlazeDirectories directories, WorkspaceBuilder builder) {
+    if (enabled) {
+      builder.setAllocationTracker(tracker);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/profiler/memory/BUILD b/src/main/java/com/google/devtools/build/lib/profiler/memory/BUILD
new file mode 100644
index 0000000..e4d909f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/profiler/memory/BUILD
@@ -0,0 +1,61 @@
+package(default_visibility = ["//src:__subpackages__"])
+
+filegroup(
+    name = "srcs",
+    srcs = glob(["**"]),
+    visibility = ["//src/main/java/com/google/devtools/build/lib:__pkg__"],
+)
+
+java_library(
+    name = "allocationtracker_module",
+    srcs = [
+        "AllocationTrackerInstaller.java",
+        "AllocationTrackerModule.java",
+    ],
+    deps = [
+        ":allocationtracker",
+        ":current_rule_tracker",
+        "//src/main/java/com/google/devtools/build/lib:build-base",
+        "//src/main/java/com/google/devtools/build/lib:runtime",
+        "//src/main/java/com/google/devtools/build/lib:syntax",
+        "//src/main/java/com/google/devtools/build/lib:util",
+        "//src/main/java/com/google/devtools/common/options",
+        "//third_party:guava",
+        "//third_party/allocation_instrumenter",
+    ],
+)
+
+java_library(
+    name = "current_rule_tracker",
+    srcs = ["CurrentRuleTracker.java"],
+    visibility = [
+        "//src/main/java/com/google/devtools/build/lib:__pkg__",
+        "//src/test/java/com/google/devtools/build/lib/profiler/memory:__subpackages__",
+    ],
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib:packages",
+        "//third_party:guava",
+        "//third_party/pprof:profile_java_proto",
+    ],
+)
+
+java_library(
+    name = "allocationtracker",
+    srcs = [
+        "AllocationTracker.java",
+    ],
+    visibility = [
+        "//src/main/java/com/google/devtools/build/lib:__pkg__",
+        "//src/test/java/com/google/devtools/build/lib/profiler/memory:__subpackages__",
+    ],
+    deps = [
+        ":current_rule_tracker",
+        "//src/main/java/com/google/devtools/build/lib:packages",
+        "//src/main/java/com/google/devtools/build/lib:syntax",
+        "//src/main/java/com/google/devtools/build/lib/concurrent",
+        "//third_party:guava",
+        "//third_party:jsr305",
+        "//third_party/allocation_instrumenter",
+        "//third_party/pprof:profile_java_proto",
+    ],
+)
diff --git a/src/main/java/com/google/devtools/build/lib/profiler/memory/CurrentRuleTracker.java b/src/main/java/com/google/devtools/build/lib/profiler/memory/CurrentRuleTracker.java
new file mode 100644
index 0000000..484fde9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/profiler/memory/CurrentRuleTracker.java
@@ -0,0 +1,80 @@
+// Copyright 2017 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.profiler.memory;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.packages.AspectClass;
+import com.google.devtools.build.lib.packages.RuleClass;
+
+/** Thread-local variables that keep track of the current rule being configured. */
+public final class CurrentRuleTracker {
+  private static final ThreadLocal<RuleClass> currentRule = new ThreadLocal<>();
+  private static final ThreadLocal<AspectClass> currentAspect = new ThreadLocal<>();
+  private static boolean enabled;
+
+  private CurrentRuleTracker() {}
+
+  public static void setEnabled(boolean enabled) {
+    CurrentRuleTracker.enabled = enabled;
+  }
+
+  /**
+   * Sets the current rule being instantiated. Used for memory tracking.
+   *
+   * <p>You must call {@link CurrentRuleTracker#endConfiguredTarget()} after calling this.
+   */
+  public static void beginConfiguredTarget(RuleClass ruleClass) {
+    if (!enabled) {
+      return;
+    }
+    currentRule.set(ruleClass);
+  }
+
+  public static void endConfiguredTarget() {
+    if (!enabled) {
+      return;
+    }
+    currentRule.set(null);
+  }
+
+  /**
+   * Sets the current aspect being instantiated. Used for memory tracking.
+   *
+   * <p>You must call {@link CurrentRuleTracker#endConfiguredAspect()} after calling this.
+   */
+  public static void beginConfiguredAspect(AspectClass aspectClass) {
+    if (!enabled) {
+      return;
+    }
+    currentAspect.set(aspectClass);
+  }
+
+  public static void endConfiguredAspect() {
+    if (!enabled) {
+      return;
+    }
+    currentAspect.set(null);
+  }
+
+  public static RuleClass getRule() {
+    Preconditions.checkState(enabled);
+    return currentRule.get();
+  }
+
+  public static AspectClass getAspect() {
+    Preconditions.checkState(enabled);
+    return currentAspect.get();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeWorkspace.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeWorkspace.java
index eee68fa..2a2d23e 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeWorkspace.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeWorkspace.java
@@ -28,6 +28,7 @@
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
+import com.google.devtools.build.lib.profiler.memory.AllocationTracker;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
 import com.google.devtools.build.lib.util.LoggingUtil;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -56,6 +57,7 @@
   private final SubscriberExceptionHandler eventBusExceptionHandler;
   private final WorkspaceStatusAction.Factory workspaceStatusActionFactory;
   private final BinTools binTools;
+  @Nullable private final AllocationTracker allocationTracker;
 
   private final BlazeDirectories directories;
   private final SkyframeExecutor skyframeExecutor;
@@ -72,11 +74,13 @@
       SkyframeExecutor skyframeExecutor,
       SubscriberExceptionHandler eventBusExceptionHandler,
       WorkspaceStatusAction.Factory workspaceStatusActionFactory,
-      BinTools binTools) {
+      BinTools binTools,
+      @Nullable AllocationTracker allocationTracker) {
     this.runtime = runtime;
     this.eventBusExceptionHandler = eventBusExceptionHandler;
     this.workspaceStatusActionFactory = workspaceStatusActionFactory;
     this.binTools = binTools;
+    this.allocationTracker = allocationTracker;
 
     this.directories = directories;
     this.skyframeExecutor = skyframeExecutor;
@@ -304,5 +308,10 @@
           "failed to create execution root '" + directories.getExecRoot() + "': " + e.getMessage());
     }
   }
+
+  @Nullable
+  public AllocationTracker getAllocationTracker() {
+    return allocationTracker;
+  }
 }
 
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java b/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java
index b1cac6c..882f6f0 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/WorkspaceBuilder.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
 import com.google.devtools.build.lib.analysis.config.BinTools;
 import com.google.devtools.build.lib.packages.PackageFactory;
+import com.google.devtools.build.lib.profiler.memory.AllocationTracker;
 import com.google.devtools.build.lib.skyframe.DiffAwareness;
 import com.google.devtools.build.lib.skyframe.SequencedSkyframeExecutorFactory;
 import com.google.devtools.build.lib.skyframe.SkyValueDirtinessChecker;
@@ -54,6 +55,7 @@
       ImmutableMap.builder();
   private final ImmutableList.Builder<SkyValueDirtinessChecker> customDirtinessCheckers =
       ImmutableList.builder();
+  private AllocationTracker allocationTracker;
 
   WorkspaceBuilder(BlazeDirectories directories, BinTools binTools) {
     this.directories = directories;
@@ -84,8 +86,13 @@
             skyFunctions.build(),
             customDirtinessCheckers.build());
     return new BlazeWorkspace(
-        runtime, directories, skyframeExecutor, eventBusExceptionHandler,
-        workspaceStatusActionFactory, binTools);
+        runtime,
+        directories,
+        skyframeExecutor,
+        eventBusExceptionHandler,
+        workspaceStatusActionFactory,
+        binTools,
+        allocationTracker);
   }
 
   /**
@@ -114,6 +121,13 @@
     return this;
   }
 
+  public WorkspaceBuilder setAllocationTracker(AllocationTracker allocationTracker) {
+    Preconditions.checkState(
+        this.allocationTracker == null, "At most one allocation tracker can be set.");
+    this.allocationTracker = Preconditions.checkNotNull(allocationTracker);
+    return this;
+  }
+
   /**
    * Add a {@link DiffAwareness} factory. These will be used to determine which files, if any,
    * changed between Blaze commands. Note that these factories are attempted in the order in which
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/commands/DumpCommand.java b/src/main/java/com/google/devtools/build/lib/runtime/commands/DumpCommand.java
index b2aeef2..96b3149 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/commands/DumpCommand.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/commands/DumpCommand.java
@@ -14,16 +14,22 @@
 
 package com.google.devtools.build.lib.runtime.commands;
 
+import static java.util.stream.Collectors.toList;
+
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.packages.RuleClass;
+import com.google.devtools.build.lib.profiler.memory.AllocationTracker;
+import com.google.devtools.build.lib.profiler.memory.AllocationTracker.RuleBytes;
 import com.google.devtools.build.lib.runtime.BlazeCommand;
 import com.google.devtools.build.lib.runtime.BlazeCommandUtils;
 import com.google.devtools.build.lib.runtime.BlazeRuntime;
+import com.google.devtools.build.lib.runtime.BlazeWorkspace;
 import com.google.devtools.build.lib.runtime.Command;
 import com.google.devtools.build.lib.runtime.CommandEnvironment;
 import com.google.devtools.build.lib.skyframe.SkyframeExecutor;
+import com.google.devtools.build.lib.skyframe.SkyframeExecutor.RuleStat;
 import com.google.devtools.build.lib.util.ExitCode;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.common.options.EnumConverter;
@@ -38,6 +44,7 @@
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
@@ -104,6 +111,28 @@
     public boolean dumpRuleClasses;
 
     @Option(
+      name = "rules",
+      defaultValue = "false",
+      category = "verbosity",
+      documentationCategory = OptionDocumentationCategory.OUTPUT_SELECTION,
+      effectTags = {OptionEffectTag.BAZEL_MONITORING},
+      help = "Dump rules, including counts and memory usage (if memory is tracked)."
+    )
+    public boolean dumpRules;
+
+    @Option(
+      name = "skylark_memory",
+      defaultValue = "null",
+      category = "verbosity",
+      documentationCategory = OptionDocumentationCategory.OUTPUT_SELECTION,
+      effectTags = {OptionEffectTag.BAZEL_MONITORING},
+      help =
+          "Dumps a pprof-compatible memory profile to the specified path."
+              + " To learn more please see <a href=https://github.com/google/pprof>pprof</a>."
+    )
+    public String skylarkMemory;
+
+    @Option(
       name = "skyframe",
       defaultValue = "off",
       category = "verbosity",
@@ -146,6 +175,8 @@
             || dumpOptions.dumpVfs
             || dumpOptions.dumpActionCache
             || dumpOptions.dumpRuleClasses
+            || dumpOptions.dumpRules
+            || dumpOptions.skylarkMemory != null
             || (dumpOptions.dumpSkyframe != SkyframeDumpOption.OFF);
     if (!anyOutput) {
       Map<String, String> categories = new HashMap<>();
@@ -189,6 +220,19 @@
         out.println();
       }
 
+      if (dumpOptions.dumpRules) {
+        dumpRuleStats(env.getBlazeWorkspace(), env.getSkyframeExecutor(), out);
+        out.println();
+      }
+
+      if (dumpOptions.skylarkMemory != null) {
+        try {
+          dumpSkylarkHeap(env.getBlazeWorkspace(), dumpOptions.skylarkMemory, out);
+        } catch (IOException e) {
+          env.getReporter().error(null, "Could not dump skylark memory", e);
+        }
+      }
+
       if (dumpOptions.dumpSkyframe != SkyframeDumpOption.OFF) {
         success &= dumpSkyframe(
             env.getSkyframeExecutor(),
@@ -244,4 +288,113 @@
       out.println(")");
     }
   }
+
+  private void dumpRuleStats(BlazeWorkspace workspace, SkyframeExecutor executor, PrintStream out) {
+    List<RuleStat> ruleStats = executor.getRuleStats();
+    if (ruleStats.isEmpty()) {
+      out.print("No rules in Blaze server, please run a build command first.");
+      return;
+    }
+    List<RuleStat> rules = ruleStats.stream().filter(RuleStat::isRule).collect(toList());
+    List<RuleStat> aspects = ruleStats.stream().filter(r -> !r.isRule()).collect(toList());
+    Map<String, RuleBytes> ruleBytes = new HashMap<>();
+    Map<String, RuleBytes> aspectBytes = new HashMap<>();
+    AllocationTracker allocationTracker = workspace.getAllocationTracker();
+    if (allocationTracker != null) {
+      allocationTracker.getRuleMemoryConsumption(ruleBytes, aspectBytes);
+    }
+    printRuleStatsOfType(rules, "RULE", out, ruleBytes, allocationTracker != null);
+    printRuleStatsOfType(aspects, "ASPECT", out, aspectBytes, allocationTracker != null);
+  }
+
+  private static void printRuleStatsOfType(
+      List<RuleStat> ruleStats,
+      String type,
+      PrintStream out,
+      Map<String, RuleBytes> ruleToBytes,
+      boolean bytesEnabled) {
+    if (ruleStats.isEmpty()) {
+      return;
+    }
+    ruleStats.sort(Comparator.comparing(RuleStat::getCount).reversed());
+    int longestName =
+        ruleStats.stream().map(r -> r.getName().length()).max(Integer::compareTo).get();
+    int maxNameWidth = 30;
+    int nameColumnWidth = Math.min(longestName, maxNameWidth);
+    int numberColumnWidth = 10;
+    int bytesColumnWidth = 13;
+    int eachColumnWidth = 11;
+    printWithPadding(out, type, nameColumnWidth);
+    printWithPaddingBefore(out, "COUNT", numberColumnWidth);
+    printWithPaddingBefore(out, "ACTIONS", numberColumnWidth);
+    if (bytesEnabled) {
+      printWithPaddingBefore(out, "BYTES", bytesColumnWidth);
+      printWithPaddingBefore(out, "EACH", eachColumnWidth);
+    }
+    out.println();
+    for (RuleStat ruleStat : ruleStats) {
+      printWithPadding(
+          out, truncateName(ruleStat.getName(), ruleStat.isRule(), maxNameWidth), nameColumnWidth);
+      printWithPaddingBefore(out, formatLong(ruleStat.getCount()), numberColumnWidth);
+      printWithPaddingBefore(out, formatLong(ruleStat.getActionCount()), numberColumnWidth);
+      if (bytesEnabled) {
+        RuleBytes ruleBytes = ruleToBytes.get(ruleStat.getKey());
+        long bytes = ruleBytes != null ? ruleBytes.getBytes() : 0L;
+        printWithPaddingBefore(out, formatLong(bytes), bytesColumnWidth);
+        printWithPaddingBefore(out, formatLong(bytes / ruleStat.getCount()), eachColumnWidth);
+      }
+      out.println();
+    }
+    out.println();
+  }
+
+  private static String truncateName(String name, boolean isRule, int maxNameWidth) {
+    // If this is an aspect, we'll chop off everything except the aspect name
+    if (!isRule) {
+      int dividerIndex = name.lastIndexOf('%');
+      if (dividerIndex >= 0) {
+        name = name.substring(dividerIndex + 1);
+      }
+    }
+    if (name.length() <= maxNameWidth) {
+      return name;
+    }
+    int starti = name.length() - maxNameWidth + "...".length();
+    return "..." + name.substring(starti);
+  }
+
+  private static void printWithPadding(PrintStream out, String str, int columnWidth) {
+    out.print(str);
+    pad(out, columnWidth + 2, str.length());
+  }
+
+  private static void printWithPaddingBefore(PrintStream out, String str, int columnWidth) {
+    pad(out, columnWidth, str.length());
+    out.print(str);
+    pad(out, 2, 0);
+  }
+
+  private static void pad(PrintStream out, int columnWidth, int consumed) {
+    for (int i = 0; i < columnWidth - consumed; ++i) {
+      out.print(' ');
+    }
+  }
+
+  private static String formatLong(long number) {
+    return String.format("%,d", number);
+  }
+
+  private void dumpSkylarkHeap(BlazeWorkspace workspace, String path, PrintStream out)
+      throws IOException {
+    AllocationTracker allocationTracker = workspace.getAllocationTracker();
+    if (allocationTracker == null) {
+      out.println(
+          "Cannot dump skylark heap without running in memory tracking mode. "
+              + "Please refer to the user manual for the dump commnd "
+              + "for information how to turn on memory tracking.");
+      return;
+    }
+    out.println("Dumping skylark heap to: " + path);
+    allocationTracker.dumpSkylarkAllocations(path);
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index f67a4e8..def0b02 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -51,6 +51,7 @@
 import com.google.devtools.build.lib.packages.SkylarkAspect;
 import com.google.devtools.build.lib.packages.SkylarkAspectClass;
 import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.profiler.memory.CurrentRuleTracker;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.ConfiguredTargetFunctionException;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetFunction.ConfiguredValueCreationException;
@@ -468,19 +469,24 @@
 
     ConfiguredAspect configuredAspect;
     if (AspectResolver.aspectMatchesConfiguredTarget(associatedTarget, aspect)) {
-      configuredAspect =
-          view.getConfiguredTargetFactory()
-              .createAspect(
-                  analysisEnvironment,
-                  associatedTarget,
-                  aspectPath,
-                  aspectFactory,
-                  aspect,
-                  directDeps,
-                  configConditions,
-                  toolchainContext,
-                  aspectConfiguration,
-                  view.getHostConfiguration(aspectConfiguration));
+      try {
+        CurrentRuleTracker.beginConfiguredAspect(aspect.getAspectClass());
+        configuredAspect =
+            view.getConfiguredTargetFactory()
+                .createAspect(
+                    analysisEnvironment,
+                    associatedTarget,
+                    aspectPath,
+                    aspectFactory,
+                    aspect,
+                    directDeps,
+                    configConditions,
+                    toolchainContext,
+                    aspectConfiguration,
+                    view.getHostConfiguration(aspectConfiguration));
+      } finally {
+        CurrentRuleTracker.endConfiguredAspect();
+      }
     } else {
       configuredAspect = ConfiguredAspect.forNonapplicableTarget(aspect.getDescriptor());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index 6704f9e..76f64c4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -30,11 +30,14 @@
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction.Factory;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
+import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.concurrent.Uninterruptibles;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
+import com.google.devtools.build.lib.packages.AspectClass;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.PackageFactory;
+import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.SkylarkSemanticsOptions;
 import com.google.devtools.build.lib.pkgcache.PackageCacheOptions;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
@@ -77,6 +80,7 @@
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.EnumSet;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
@@ -629,6 +633,48 @@
     discardAnalysisCache(topLevelTargets, topLevelAspects);
   }
 
+  @Override
+  public List<RuleStat> getRuleStats() {
+    Map<String, RuleStat> ruleStats = new HashMap<>();
+    for (Map.Entry<SkyKey, ? extends NodeEntry> skyKeyAndNodeEntry :
+        memoizingEvaluator.getGraphMap().entrySet()) {
+      NodeEntry entry = skyKeyAndNodeEntry.getValue();
+      if (entry == null || !entry.isDone()) {
+        continue;
+      }
+      SkyKey key = skyKeyAndNodeEntry.getKey();
+      SkyFunctionName functionName = key.functionName();
+      if (functionName.equals(SkyFunctions.CONFIGURED_TARGET)) {
+        try {
+          ConfiguredTargetValue ctValue = (ConfiguredTargetValue) entry.getValue();
+          ConfiguredTarget configuredTarget = ctValue.getConfiguredTarget();
+          if (configuredTarget instanceof RuleConfiguredTarget) {
+            RuleConfiguredTarget ruleConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
+            RuleClass ruleClass = ruleConfiguredTarget.getTarget().getRuleClassObject();
+            RuleStat ruleStat =
+                ruleStats.computeIfAbsent(
+                    ruleClass.getKey(), k -> new RuleStat(k, ruleClass.getName(), true));
+            ruleStat.addRule(ctValue.getNumActions());
+          }
+        } catch (InterruptedException e) {
+          throw new IllegalStateException("No interruption in sequenced evaluation", e);
+        }
+      } else if (functionName.equals(SkyFunctions.ASPECT)) {
+        try {
+          AspectValue aspectValue = (AspectValue) entry.getValue();
+          AspectClass aspectClass = aspectValue.getAspect().getAspectClass();
+          RuleStat ruleStat =
+              ruleStats.computeIfAbsent(
+                  aspectClass.getKey(), k -> new RuleStat(k, aspectClass.getName(), false));
+          ruleStat.addRule(aspectValue.getNumActions());
+        } catch (InterruptedException e) {
+          throw new IllegalStateException("No interruption in sequenced evaluation", e);
+        }
+      }
+    }
+    return new ArrayList<>(ruleStats.values());
+  }
+
   /**
    * In addition to calling the superclass method, deletes all ConfiguredTarget values from the
    * Skyframe cache. This is done to save memory (e.g. on a configuration change); since the
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index c6afa32..a13278f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -625,6 +625,54 @@
     skyframeBuildView.clearLegacyData();
   }
 
+  /** Used with dump --rules. */
+  public static class RuleStat {
+    private final String key;
+    private final String name;
+    private final boolean isRule;
+    private long count;
+    private long actionCount;
+
+    public RuleStat(String key, String name, boolean isRule) {
+      this.key = key;
+      this.name = name;
+      this.isRule = isRule;
+    }
+
+    public void addRule(long actionCount) {
+      this.count++;
+      this.actionCount += actionCount;
+    }
+
+    /** Returns a key that uniquely identifies this rule or aspect. */
+    public String getKey() {
+      return key;
+    }
+
+    /** Returns a name for the rule or aspect. */
+    public String getName() {
+      return name;
+    }
+
+    /** Returns whether this is a rule or an aspect. */
+    public boolean isRule() {
+      return isRule;
+    }
+
+    /** Returns the instance count of this rule or aspect class. */
+    public long getCount() {
+      return count;
+    }
+
+    /** Returns the total action count of all instance of this rule or aspect class. */
+    public long getActionCount() {
+      return actionCount;
+    }
+  }
+
+  /** Computes statistics on heap-resident rules and aspects. */
+  public abstract List<RuleStat> getRuleStats();
+
   /**
    * Removes ConfigurationFragmentValues from the cache.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
index a62e869..3f7d43b 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
@@ -425,7 +425,12 @@
     Object[] arguments = processArguments(args, kwargs, loc, env);
     canonicalizeArguments(arguments, loc);
 
-    return call(arguments, ast, env);
+    try {
+      Callstack.push(this);
+      return call(arguments, ast, env);
+    } finally {
+      Callstack.pop();
+    }
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Callstack.java b/src/main/java/com/google/devtools/build/lib/syntax/Callstack.java
new file mode 100644
index 0000000..b336430
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Callstack.java
@@ -0,0 +1,67 @@
+// Copyright 2017 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.syntax;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.devtools.build.lib.util.Preconditions;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Holds the Skylark callstack in thread-local storage. Contains all Expressions and BaseFunctions
+ * currently being evaluated.
+ *
+ * <p>This is needed for memory tracking, since the evaluator is not available in the context of
+ * instrumentation. It should not be used by normal Skylark interpreter logic.
+ */
+public class Callstack {
+  private static boolean enabled;
+  private static final ThreadLocal<List<Object>> callstack =
+      ThreadLocal.withInitial(ArrayList::new);
+
+  public static void setEnabled(boolean enabled) {
+    Callstack.enabled = enabled;
+  }
+
+  public static void push(ASTNode node) {
+    if (enabled) {
+      callstack.get().add(node);
+    }
+  }
+
+  public static void push(BaseFunction function) {
+    if (enabled) {
+      callstack.get().add(function);
+    }
+  }
+
+  public static void pop() {
+    if (enabled) {
+      List<Object> threadStack = callstack.get();
+      threadStack.remove(threadStack.size() - 1);
+    }
+  }
+
+  public static List<Object> get() {
+    Preconditions.checkState(enabled, "Must call Callstack#setEnabled before getting");
+    return callstack.get();
+  }
+
+  @VisibleForTesting
+  public static void resetStateForTest() {
+    enabled = false;
+    callstack.get().clear();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
index a7188d8..db5d4e6 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
@@ -62,9 +62,14 @@
    */
   public final Object eval(Environment env) throws EvalException, InterruptedException {
     try {
-      return doEval(env);
-    } catch (EvalException ex) {
-      throw maybeTransformException(ex);
+      Callstack.push(this);
+      try {
+        return doEval(env);
+      } catch (EvalException ex) {
+        throw maybeTransformException(ex);
+      }
+    } finally {
+      Callstack.pop();
     }
   }