Experimental support LLVM ThinLTO.

ThinLTO is a Link Time Opimization strategy, where the inlining step operates on LLVM intermediate code, and is sharded across multiple compiler invocations, so they can be parallelized. For more information, see http://llvm.org/devmtg/2015-04/slides/ThinLTO_EuroLLVM2015.pdf

Using this features requires an experimental LLVM toolchain, with the following stanza in CROSSTOOL

  feature {
    name: "thin_lto"
    flag_set {
      action: "c-compile"
      action: "c++-compile"
      flag_group {
       flag: "-Xclang-only=-Wno-inconsistent-missing-override"
       flag: "-flto"
       flag: "-O2"
      }
    }
  }

--
MOS_MIGRATED_REVID=100269776

7 files changed, 403 insertions, 65 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/ParameterFile.java b/src/main/java/com/google/devtools/build/lib/actions/ParameterFile.java
index d9af4f82e4..736d50fea5 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ParameterFile.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ParameterFile.java
@@ -66,7 +66,14 @@ public class ParameterFile {
    * Derives an path from a given path by appending <code>".params"</code>.
    */
   public static PathFragment derivePath(PathFragment original) {
-    return original.replaceName(original.getBaseName() + "-2.params");
+    return derivePath(original, "2");
+  }
+
+  /**
+   * Derives an path from a given path by appending <code>".params"</code>.
+   */
+  public static PathFragment derivePath(PathFragment original, String flavor) {
+    return original.replaceName(original.getBaseName() + "-" + flavor + ".params");
   }
 
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
index e061961671..08f5394592 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
@@ -72,15 +72,9 @@ public final class ParamFileHelper {
       return null;
     }
 
-    return getParamsFile(analysisEnvironment, configuration, Iterables.getFirst(outputs, null));
-  }
+    PathFragment paramFilePath =
+        ParameterFile.derivePath(Iterables.getFirst(outputs, null).getRootRelativePath());
 
-  /**
-   * Returns a params file for the specified output file.
-   */
-  public static Artifact getParamsFile(AnalysisEnvironment analysisEnvironment,
-      BuildConfiguration configuration, Artifact output) {
-    PathFragment paramFilePath = ParameterFile.derivePath(output.getRootRelativePath());
     return analysisEnvironment.getDerivedArtifact(paramFilePath, configuration.getBinDirectory());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
index 815af7005d..99ebe89310 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
@@ -223,9 +223,22 @@ public abstract class CcBinary implements RuleConfiguredTargetFactory {
           ruleContext.getConfiguration().getBinDirectory()));
     }
 
-    // store immutable context now, recreate builder later
+    // Store immutable context for use in other *_binary rules that are implemented by
+    // linking the interpreter (Java, Python, etc.) together with native deps.
     CppLinkAction.Context linkContext = new CppLinkAction.Context(linkActionBuilder);
 
+    if (featureConfiguration.isEnabled(CppRuleClasses.THIN_LTO)) {
+      linkActionBuilder.setLTOIndexing(true);
+      CppLinkAction indexAction = linkActionBuilder.build();
+      ruleContext.registerAction(indexAction);
+
+      for (LTOBackendArtifacts ltoArtifacts : indexAction.getAllLTOBackendArtifacts()) {
+        ltoArtifacts.scheduleLTOBackendAction(ruleContext);
+      }
+
+      linkActionBuilder.setLTOIndexing(false);
+    }
+
     CppLinkAction linkAction = linkActionBuilder.build();
     ruleContext.registerAction(linkAction);
     LibraryToLink outputLibrary = linkAction.getOutputLibrary();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java
index cc0caa11d4..eac16b4c72 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkAction.java
@@ -39,7 +39,6 @@ import com.google.devtools.build.lib.actions.extra.ExtraActionInfo;
 import com.google.devtools.build.lib.analysis.AnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
-import com.google.devtools.build.lib.analysis.actions.ParamFileHelper;
 import com.google.devtools.build.lib.analysis.actions.ParameterFileWriteAction;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.collect.CollectionUtils;
@@ -72,7 +71,7 @@ import java.util.Set;
 import javax.annotation.Nullable;
 
 /**
- * Action that represents an ELF linking step.
+ * Action that represents a linking step.
  */
 @ThreadCompatible
 public final class CppLinkAction extends AbstractAction {
@@ -87,7 +86,10 @@ public final class CppLinkAction extends AbstractAction {
 
   /** True for cc_fake_binary targets. */
   private final boolean fake;
+  private final boolean isLTOIndexing;
 
+  // This is set for both LTO indexing and LTO linking.
+  @Nullable private final Iterable<LTOBackendArtifacts> allLTOBackendArtifacts;
   private final Iterable<Artifact> mandatoryInputs;
 
   // Linking uses a lot of memory; estimate 1 MB per input file, min 1.5 Gib.
@@ -114,21 +116,25 @@ public final class CppLinkAction extends AbstractAction {
    * <p>This constructor is intentionally private and is only to be called from
    * {@link Builder#build()}.
    */
-  private CppLinkAction(ActionOwner owner,
-                        Iterable<Artifact> inputs,
-                        ImmutableList<Artifact> outputs,
-                        CppConfiguration cppConfiguration,
-                        LibraryToLink outputLibrary,
-                        LibraryToLink interfaceOutputLibrary,
-                        boolean fake,
-                        LinkCommandLine linkCommandLine) {
+  private CppLinkAction(
+      ActionOwner owner,
+      Iterable<Artifact> inputs,
+      ImmutableList<Artifact> outputs,
+      CppConfiguration cppConfiguration,
+      LibraryToLink outputLibrary,
+      LibraryToLink interfaceOutputLibrary,
+      boolean fake,
+      boolean isLTOIndexing,
+      Iterable<LTOBackendArtifacts> allLTOBackendArtifacts,
+      LinkCommandLine linkCommandLine) {
     super(owner, inputs, outputs);
     this.mandatoryInputs = inputs;
     this.cppConfiguration = cppConfiguration;
     this.outputLibrary = outputLibrary;
     this.interfaceOutputLibrary = interfaceOutputLibrary;
     this.fake = fake;
-
+    this.isLTOIndexing = isLTOIndexing;
+    this.allLTOBackendArtifacts = allLTOBackendArtifacts;
     this.linkCommandLine = linkCommandLine;
   }
 
@@ -210,6 +216,10 @@ public final class CppLinkAction extends AbstractAction {
     return linkCommandLine.getCommandLine();
   }
 
+  Iterable<LTOBackendArtifacts> getAllLTOBackendArtifacts() {
+    return allLTOBackendArtifacts;
+  }
+
   @Override
   @ThreadCompatible
   public void execute(
@@ -367,6 +377,7 @@ public final class CppLinkAction extends AbstractAction {
     if (linkCommandLine.getRuntimeSolibDir() != null) {
       f.addPath(linkCommandLine.getRuntimeSolibDir());
     }
+    f.addBoolean(isLTOIndexing);
     return f.hexDigestAndReset();
   }
 
@@ -379,8 +390,8 @@ public final class CppLinkAction extends AbstractAction {
     message.append(getProgressMessage());
     message.append('\n');
     message.append("  Command: ");
-    message.append(ShellEscaper.escapeString(
-        getCppConfiguration().getLdExecutable().getPathString()));
+    message.append(
+        ShellEscaper.escapeString(getCppConfiguration().getLdExecutable().getPathString()));
     message.append('\n');
     // Outputting one argument per line makes it easier to diff the results.
     for (String argument : ShellEscaper.escapeAll(linkCommandLine.arguments())) {
@@ -392,11 +403,14 @@ public final class CppLinkAction extends AbstractAction {
   }
 
   @Override
-  public String getMnemonic() { return "CppLink"; }
+  public String getMnemonic() {
+    return (isLTOIndexing) ? "CppLTOIndexing" : "CppLink";
+  }
 
   @Override
   protected String getRawProgressMessage() {
-    return "Linking " + outputLibrary.getArtifact().prettyPrint();
+    return (isLTOIndexing ? "LTO indexing " : "Linking ")
+        + outputLibrary.getArtifact().prettyPrint();
   }
 
   @Override
@@ -457,6 +471,7 @@ public final class CppLinkAction extends AbstractAction {
     private final AnalysisEnvironment analysisEnvironment;
     private final Artifact output;
 
+    @Nullable private PathFragment interfaceOutputPath;
     // can be null for CppLinkAction.createTestBuilder()
     @Nullable private final CcToolchainProvider toolchain;
     private Artifact interfaceOutput;
@@ -483,6 +498,9 @@ public final class CppLinkAction extends AbstractAction {
     private boolean useTestOnlyFlags;
     private boolean wholeArchive;
 
+    private boolean isLTOIndexing = false;
+    private Iterable<LTOBackendArtifacts> allLTOArtifacts = null;
+
     /**
      * Creates a builder that builds {@link CppLinkAction} instances.
      *
@@ -559,6 +577,35 @@ public final class CppLinkAction extends AbstractAction {
       this.useTestOnlyFlags = linkContext.useTestOnlyFlags;
     }
 
+    private Iterable<LTOBackendArtifacts> createLTOArtifacts(
+        PathFragment ltoOutputRootPrefix, NestedSet<LibraryToLink> uniqueLibraries) {
+      // This flattens the set of object files, so for M binaries and N .o files,
+      // this is O(M*N). If we had a nested set of .o files, we could have O(M + N) instead.
+      NestedSetBuilder<Artifact> bitcodeBuilder = NestedSetBuilder.stableOrder();
+      for (LibraryToLink lib : uniqueLibraries) {
+        bitcodeBuilder.addAll(lib.getObjectFiles());
+      }
+      for (LinkerInput input : nonLibraries) {
+        // This relies on file naming conventions. It would be less fragile to have a dedicated
+        // field for non-library .o files.
+        if (CppFileTypes.OBJECT_FILE.matches(input.getArtifact().getExecPath())
+            || CppFileTypes.PIC_OBJECT_FILE.matches(input.getArtifact().getExecPath())) {
+          bitcodeBuilder.add(input.getArtifact());
+        }
+      }
+
+      NestedSet<Artifact> allBitcode = bitcodeBuilder.build();
+
+      ImmutableList.Builder<LTOBackendArtifacts> ltoOutputs = ImmutableList.builder();
+      for (Artifact a : allBitcode) {
+        LTOBackendArtifacts ltoArtifacts =
+            new LTOBackendArtifacts(
+                ltoOutputRootPrefix, a, allBitcode, analysisEnvironment, configuration);
+        ltoOutputs.add(ltoArtifacts);
+      }
+      return ltoOutputs.build();
+    }
+
     @VisibleForTesting
     boolean canSplitCommandLine() {
       if (toolchain == null || !toolchain.supportsParamFiles()) {
@@ -584,8 +631,6 @@ public final class CppLinkAction extends AbstractAction {
 
     /**
      * Builds the Action as configured and returns it.
-     *
-     * <p>This method may only be called once.
      */
     public CppLinkAction build() {
       if (interfaceOutput != null && (fake || linkType != LinkTargetType.DYNAMIC_LIBRARY)) {
@@ -603,6 +648,7 @@ public final class CppLinkAction extends AbstractAction {
       NestedSet<LibraryToLink> uniqueLibraries = libraries.build();
       final Iterable<Artifact> filteredNonLibraryArtifacts =
           filterLinkerInputArtifacts(LinkerInputs.toLibraryArtifacts(nonLibraries));
+
       final Iterable<LinkerInput> linkerInputs = IterablesChain.<LinkerInput>builder()
           .add(ImmutableList.copyOf(filterLinkerInputs(nonLibraries)))
           .add(ImmutableIterable.from(Link.mergeInputsCmdLine(
@@ -616,61 +662,119 @@ public final class CppLinkAction extends AbstractAction {
 
       final LibraryToLink outputLibrary =
           LinkerInputs.newInputLibrary(output, filteredNonLibraryArtifacts);
-      final LibraryToLink interfaceOutputLibrary = interfaceOutput == null ? null :
-          LinkerInputs.newInputLibrary(interfaceOutput, filteredNonLibraryArtifacts);
+      final LibraryToLink interfaceOutputLibrary =
+          (interfaceOutput == null)
+              ? null
+              : LinkerInputs.newInputLibrary(interfaceOutput, filteredNonLibraryArtifacts);
 
       final ImmutableMap<Artifact, Artifact> linkstampMap =
           mapLinkstampsToOutputs(linkstamps, ruleContext, output);
 
-      final ImmutableList<Artifact> actionOutputs =
-          constructOutputs(
-              outputLibrary.getArtifact(),
-              linkstampMap.values(),
-              interfaceOutputLibrary == null ? null : interfaceOutputLibrary.getArtifact(),
-              symbolCounts);
+      PathFragment ltoOutputRootPrefix = null;
+      if (isLTOIndexing && allLTOArtifacts == null) {
+        ltoOutputRootPrefix =
+            FileSystemUtils.appendExtension(
+                outputLibrary.getArtifact().getRootRelativePath(), ".lto");
+        allLTOArtifacts = createLTOArtifacts(ltoOutputRootPrefix, uniqueLibraries);
+      }
+
+      final ImmutableList<Artifact> actionOutputs;
+      if (isLTOIndexing) {
+        ImmutableList.Builder<Artifact> builder = ImmutableList.builder();
+        for (LTOBackendArtifacts ltoA : allLTOArtifacts) {
+          ltoA.addIndexingOutputs(builder);
+        }
+        actionOutputs = builder.build();
+      } else {
+        actionOutputs =
+            constructOutputs(
+                outputLibrary.getArtifact(),
+                linkstampMap.values(),
+                interfaceOutputLibrary == null ? null : interfaceOutputLibrary.getArtifact(),
+                symbolCounts);
+      }
+
+      PathFragment paramRootPath =
+          ParameterFile.derivePath(
+              outputLibrary.getArtifact().getRootRelativePath(), (isLTOIndexing) ? "lto" : "2");
 
       @Nullable
-      final Artifact paramFile = canSplitCommandLine()
-          ? ParamFileHelper.getParamsFile(
-          analysisEnvironment, configuration, outputLibrary.getArtifact())
-          : null;
+      final Artifact paramFile =
+          canSplitCommandLine()
+              ? analysisEnvironment.getDerivedArtifact(
+                  paramRootPath, configuration.getBinDirectory())
+              : null;
 
-      LinkCommandLine linkCommandLine =
+      LinkCommandLine.Builder linkCommandLineBuilder =
           new LinkCommandLine.Builder(configuration, getOwner(), ruleContext)
-              .setOutput(outputLibrary.getArtifact())
-              .setInterfaceOutput(interfaceOutput)
-              .setSymbolCountsOutput(symbolCounts)
-              .setBuildInfoHeaderArtifacts(buildInfoHeaderArtifacts)
               .setLinkerInputs(linkerInputs)
               .setRuntimeInputs(
                   ImmutableList.copyOf(LinkerInputs.simpleLinkerInputs(runtimeInputs)))
               .setLinkTargetType(linkType)
               .setLinkStaticness(linkStaticness)
-              .setLinkopts(ImmutableList.copyOf(linkopts))
               .setFeatures(features)
-              .setLinkstamps(linkstampMap)
-              .addLinkstampCompileOptions(linkstampOptions)
               .setRuntimeSolibDir(linkType.isStaticLibraryLink() ? null : runtimeSolibDir)
               .setNativeDeps(isNativeDeps)
               .setUseTestOnlyFlags(useTestOnlyFlags)
               .setNeedWholeArchive(needWholeArchive)
-              .setInterfaceSoBuilder(getInterfaceSoBuilder())
               .setParamFile(paramFile)
-              .build();
+              .setAllLTOArtifacts(isLTOIndexing ? null : allLTOArtifacts);
+
+      if (!isLTOIndexing) {
+        linkCommandLineBuilder
+            .setOutput(outputLibrary.getArtifact())
+            .setInterfaceOutput(interfaceOutput)
+            .setSymbolCountsOutput(symbolCounts)
+            .setBuildInfoHeaderArtifacts(buildInfoHeaderArtifacts)
+            .setInterfaceSoBuilder(getInterfaceSoBuilder())
+            .setLinkstamps(linkstampMap)
+            .setLinkopts(ImmutableList.copyOf(linkopts))
+            .addLinkstampCompileOptions(linkstampOptions);
+      } else {
+        // TODO(bazel-team): once the LLVM compiler patches have been finalized, this should
+        // be converted to a crosstool feature configuration instead.
+        List<String> opts = new ArrayList<String>(linkopts);
+        opts.add("-flto");
+        opts.add(
+            "-Wl,-plugin-opt,thin-lto="
+                + configuration.getBinDirectory().getExecPathString()
+                + ":"
+                + configuration
+                    .getBinDirectory()
+                    .getExecPath()
+                    .getRelative(ltoOutputRootPrefix)
+                    .toString());
+        linkCommandLineBuilder.setLinkopts(ImmutableList.copyOf(opts));
+      }
+
+      LinkCommandLine linkCommandLine = linkCommandLineBuilder.build();
 
       // Compute the set of inputs - we only need stable order here.
       NestedSetBuilder<Artifact> dependencyInputsBuilder = NestedSetBuilder.stableOrder();
-      dependencyInputsBuilder.addAll(buildInfoHeaderArtifacts);
-      dependencyInputsBuilder.addAll(linkstamps);
       dependencyInputsBuilder.addTransitive(crosstoolInputs);
       if (runtimeMiddleman != null) {
         dependencyInputsBuilder.add(runtimeMiddleman);
       }
-      dependencyInputsBuilder.addTransitive(compilationInputs.build());
+      if (!isLTOIndexing) {
+        dependencyInputsBuilder.addAll(buildInfoHeaderArtifacts);
+        dependencyInputsBuilder.addAll(linkstamps);
+        dependencyInputsBuilder.addTransitive(compilationInputs.build());
+      }
 
       Iterable<Artifact> expandedInputs =
-          LinkerInputs.toLibraryArtifacts(Link.mergeInputsDependencies(uniqueLibraries,
-              needWholeArchive, cppConfiguration.archiveType()));
+          LinkerInputs.toLibraryArtifacts(
+              Link.mergeInputsDependencies(
+                  uniqueLibraries, needWholeArchive, cppConfiguration.archiveType()));
+
+      if (!isLTOIndexing && allLTOArtifacts != null) {
+        // This is the real link, rename the inputs.
+        List<Artifact> renamed = new ArrayList<>();
+        for (LTOBackendArtifacts a : allLTOArtifacts) {
+          renamed.add(a.getObjectFile());
+        }
+        expandedInputs = renamed;
+      }
+
       // getPrimaryInput returns the first element, and that is a public interface - therefore the
       // order here is important.
       IterablesChain.Builder<Artifact> inputsBuilder = IterablesChain.<Artifact>builder()
@@ -698,6 +802,8 @@ public final class CppLinkAction extends AbstractAction {
           outputLibrary,
           interfaceOutputLibrary,
           fake,
+          isLTOIndexing,
+          allLTOArtifacts,
           linkCommandLine);
     }
 
@@ -740,7 +846,7 @@ public final class CppLinkAction extends AbstractAction {
      */
     public static ImmutableMap<Artifact, Artifact> mapLinkstampsToOutputs(
         Collection<Artifact> linkstamps, RuleContext ruleContext, Artifact outputBinary) {
- ImmutableMap.Builder<Artifact, Artifact> mapBuilder = ImmutableMap.builder();
+      ImmutableMap.Builder<Artifact, Artifact> mapBuilder = ImmutableMap.builder();
 
       PathFragment outputBinaryPath = outputBinary.getRootRelativePath();
       PathFragment stampOutputDirectory = outputBinaryPath.getParentDirectory().
@@ -774,6 +880,18 @@ public final class CppLinkAction extends AbstractAction {
     }
 
     /**
+     * This is the LTO indexing step, rather than the real link.
+     *
+     * <p>When using this, build() will store allLTOArtifacts as a side-effect so the next build()
+     * call can emit the real link. Do not call addInput() between the two build() calls.
+     *
+     */
+    public Builder setLTOIndexing(boolean ltoIndexing) {
+      this.isLTOIndexing = ltoIndexing;
+      return this;
+    }
+
+    /**
      * Sets the C++ runtime library inputs for the action.
      */
     public Builder setRuntimeInputs(Artifact middleman, NestedSet<Artifact> inputs) {
@@ -820,6 +938,7 @@ public final class CppLinkAction extends AbstractAction {
           "'%s' is a library file", input);
       this.nonLibraries.add(input);
     }
+
     /**
      * Adds a single artifact to the set of inputs (C++ source files, header files, etc). Artifacts
      * that are not of recognized types will be used for dependency checking but will not be passed
@@ -852,9 +971,10 @@ public final class CppLinkAction extends AbstractAction {
     private void checkLibrary(LibraryToLink input) {
       String name = input.getArtifact().getFilename();
       Preconditions.checkArgument(
-          Link.ARCHIVE_LIBRARY_FILETYPES.matches(name) ||
-          Link.SHARED_LIBRARY_FILETYPES.matches(name),
-          "'%s' is not a library file", input);
+          Link.ARCHIVE_LIBRARY_FILETYPES.matches(name)
+              || Link.SHARED_LIBRARY_FILETYPES.matches(name),
+          "'%s' is not a library file",
+          input);
     }
 
     /**
@@ -1028,7 +1148,7 @@ public final class CppLinkAction extends AbstractAction {
   }
 
   /**
-   * Immutable ELF linker context, suitable for serialization.
+   * TransitiveInfoProvider for ELF link actions.
    */
   @Immutable @ThreadSafe
   public static final class Context implements TransitiveInfoProvider {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
index a7fc64ef9a..ef2adfa186 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppRuleClasses.java
@@ -147,6 +147,11 @@ public class CppRuleClasses {
   public static final String INCLUDE_PATHS = "include_paths";
 
   /**
+   * A string constant for the ThinLTO feature.
+   */
+  public static final String THIN_LTO = "thin_lto";
+
+  /*
    * A string constant for the fdo_instrument feature.
    */
   public static final String FDO_INSTRUMENT = "fdo_instrument";
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LTOBackendArtifacts.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LTOBackendArtifacts.java
new file mode 100644
index 0000000000..edeb70edf2
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LTOBackendArtifacts.java
@@ -0,0 +1,142 @@
+// Copyright 2015 Google Inc. 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.rules.cpp;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Root;
+import com.google.devtools.build.lib.analysis.AnalysisEnvironment;
+import com.google.devtools.build.lib.analysis.RuleContext;
+import com.google.devtools.build.lib.analysis.actions.SpawnAction;
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+/**
+ * LTOBackendArtifacts represents a set of artifacts for a single LTO backend compile.
+ *
+ * <p>LTO expands the traditional 2 step compile (N x compile .cc, 1x link (N .o files) into a
+ * 4 step process:
+ * <ul>
+ *   <li>1. Bitcode generation (N times). This is produces intermediate LLVM bitcode from a source
+ *   file. For this product, it reuses the .o extension.
+ *   </li>
+ *   <li>2. Indexing (once on N files). This takes all bitcode .o files, and for each .o file, it
+ *   decides from which other .o files symbols can be inlined. In addition, it generates an
+ *   index for looking up these symbols.
+ *   </li>
+ *   <li>3. Backend compile (N times). This is the traditional compilation, and uses the same
+ *   command line
+ *   as the Bitcode generation in 1). Since the compiler has many bit code files available, it
+ *   can inline functions and propagate constants across .o files. This step is costly, as it
+ *   will do traditional optimization. The result is a .lto.o file, a traditional ELF object file.
+ *   <p>
+ *     For simplicity, our current prototype step 2. also generates a command line which we execute
+ *     in step 3.
+ *   </p>
+ *   </li>
+ *   <li>4. Backend link (once). This is the traditional link, and produces the final executable.
+ *   </li>
+ * </ul>
+ */
+public final class LTOBackendArtifacts {
+  // A file containing mapping of symbol => bitcode file containing the symbol.
+  private final Artifact index;
+
+  // The bitcode file which is the input of the compile.
+  private final Artifact bitcodeFile;
+
+  // A file containing a list of bitcode files necessary to run the backend step. Currently
+  // unused.
+  private final Artifact imports;
+
+  // A file containing a command-line to run for the backend compile.
+  private final Artifact beCommandline;
+
+  // The result of executing the above command line, an ELF object file.
+  private final Artifact objectFile;
+
+  // A collection of all of the bitcode files. This is the universe from which the .imports file
+  // distills its lists.  The nested set is the same across all LTOBackendArtifacts of a given
+  // binary.
+  private final NestedSet<Artifact> bitcodeFiles;
+
+  LTOBackendArtifacts(
+      PathFragment ltoOutputRootPrefix,
+      Artifact bitcodeFile,
+      NestedSet<Artifact> allBitCodeFiles,
+      AnalysisEnvironment analysisEnvironment,
+      BuildConfiguration configuration) {
+    this.bitcodeFile = bitcodeFile;
+    PathFragment obj = ltoOutputRootPrefix.getRelative(bitcodeFile.getRootRelativePath());
+    Root binDir = configuration.getBinDirectory();
+
+    objectFile = analysisEnvironment.getDerivedArtifact(obj, binDir);
+    imports =
+        analysisEnvironment.getDerivedArtifact(
+            FileSystemUtils.replaceExtension(obj, ".imports"), binDir);
+    index =
+        analysisEnvironment.getDerivedArtifact(
+            FileSystemUtils.replaceExtension(obj, ".thinlto.index"), binDir);
+    beCommandline =
+        analysisEnvironment.getDerivedArtifact(
+            FileSystemUtils.replaceExtension(obj, ".thinlto_commandline.txt"), binDir);
+
+    bitcodeFiles = allBitCodeFiles;
+  }
+
+  public Artifact getObjectFile() {
+    return objectFile;
+  }
+
+  public Artifact getBitcodeFile() {
+    return bitcodeFile;
+  }
+
+  public void addIndexingOutputs(ImmutableList.Builder<Artifact> builder) {
+    builder.add(imports);
+    builder.add(index);
+    builder.add(beCommandline);
+  }
+
+  public void scheduleLTOBackendAction(RuleContext ruleContext) {
+    SpawnAction.Builder builder = new SpawnAction.Builder();
+
+    // TODO(bazel-team): should prune to the files mentioned in .imports.
+    builder.addTransitiveInputs(bitcodeFiles);
+    builder.addInput(imports);
+    builder.addInput(index);
+    builder.addInput(beCommandline);
+    builder.addTransitiveInputs(CppHelper.getToolchain(ruleContext).getCompile());
+    builder.addOutput(objectFile);
+
+    builder.setProgressMessage("LTO Backend Compile");
+    builder.setMnemonic("CcLtoBackendCompile");
+
+    // The command-line doesn't specify the full path to clang++, so we set it in the
+    // environment.
+    CppConfiguration cppConfiguration = ruleContext.getFragment(CppConfiguration.class);
+
+    PathFragment compiler = cppConfiguration.getCppExecutable();
+
+    builder.setShellCommand(beCommandline.getExecPathString());
+    builder.setEnvironment(
+        ImmutableMap.of("CLANGXX", compiler.replaceName("clang++").getPathString()));
+
+    ruleContext.registerAction(builder.build(ruleContext));
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java
index 66b2722e83..5da414f134 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java
@@ -41,6 +41,7 @@ import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
@@ -78,6 +79,8 @@ public final class LinkCommandLine extends CommandLine {
   private final boolean nativeDeps;
   private final boolean useTestOnlyFlags;
   private final boolean needWholeArchive;
+
+  @Nullable private final Iterable<LTOBackendArtifacts> allLTOArtifacts;
   @Nullable private final Artifact paramFile;
   @Nullable private final Artifact interfaceSoBuilder;
 
@@ -106,6 +109,7 @@ public final class LinkCommandLine extends CommandLine {
       boolean nativeDeps,
       boolean useTestOnlyFlags,
       boolean needWholeArchive,
+      @Nullable Iterable<LTOBackendArtifacts> allLTOArtifacts,
       @Nullable Artifact paramFile,
       Artifact interfaceSoBuilder,
       CcToolchainFeatures.Variables variables,
@@ -161,6 +165,7 @@ public final class LinkCommandLine extends CommandLine {
     this.nativeDeps = nativeDeps;
     this.useTestOnlyFlags = useTestOnlyFlags;
     this.needWholeArchive = needWholeArchive;
+    this.allLTOArtifacts = allLTOArtifacts;
     this.paramFile = paramFile;
 
     // For now, silently ignore interfaceSoBuilder if we don't build an interface dynamic library.
@@ -641,7 +646,7 @@ public final class LinkCommandLine extends CommandLine {
           && linkTargetType == LinkTargetType.EXECUTABLE
           && cppConfiguration.skipStaticOutputs()) {
         // Linked binary goes to /dev/null; bogus dependency info in its place.
-        Collections.addAll(argv, "/dev/null", "-MMD", "-MF", execpath);  // thanks Ambrose
+        Collections.addAll(argv, "/dev/null", "-MMD", "-MF", execpath);
       } else {
         argv.add(execpath);
       }
@@ -784,6 +789,23 @@ public final class LinkCommandLine extends CommandLine {
 
     boolean includeSolibDir = false;
 
+
+    Map<Artifact, Artifact> ltoMap = null;
+    if (allLTOArtifacts != null) {
+      // TODO(bazel-team): The LTO final link can only work if there are individual .o files on the
+      // command line. Rather than crashing, this should issue a nice error. We will get this by
+      // 1) moving supports_start_end_lib to a toolchain feature
+      // 2) having thin_lto require start_end_lib
+      // As a bonus, we can rephrase --nostart_end_lib as --features=-start_end_lib and get rid
+      // of a command line option.
+
+      Preconditions.checkState(cppConfiguration.useStartEndLib());
+      ltoMap = new HashMap<>();
+      for (LTOBackendArtifacts l : allLTOArtifacts) {
+        ltoMap.put(l.getBitcodeFile(), l.getObjectFile());
+      }
+    }
+
     for (LinkerInput input : getLinkerInputs()) {
       if (isDynamicLibrary(input)) {
         PathFragment libDir = input.getArtifact().getExecPath().getParentDirectory();
@@ -795,7 +817,7 @@ public final class LinkCommandLine extends CommandLine {
         }
         addDynamicInputLinkOptions(input, linkerInputs, libOpts, solibDir, rpathRoot);
       } else {
-        addStaticInputLinkOptions(input, linkerInputs);
+        addStaticInputLinkOptions(input, linkerInputs, ltoMap);
       }
     }
 
@@ -813,7 +835,7 @@ public final class LinkCommandLine extends CommandLine {
         includeRuntimeSolibDir = true;
         addDynamicInputLinkOptions(input, optionsList, libOpts, solibDir, rpathRoot);
       } else {
-        addStaticInputLinkOptions(input, optionsList);
+        addStaticInputLinkOptions(input, optionsList, ltoMap);
       }
     }
 
@@ -857,6 +879,11 @@ public final class LinkCommandLine extends CommandLine {
        */
       argv.addAll(linkopts);
     }
+
+    if (ltoMap != null) {
+      Preconditions.checkState(
+          ltoMap.size() == 0, "Still have LTO objects left: " + ltoMap + ", command-line: " + argv);
+    }
   }
 
   /**
@@ -902,8 +929,12 @@ public final class LinkCommandLine extends CommandLine {
   /**
    * Adds command-line options for a static library or non-library input
    * into options.
+   *
+   * @param ltoMap is a mutable list of exec paths that should be on the command-line, which
+   *    must be supplied for LTO final links.
    */
-  private void addStaticInputLinkOptions(LinkerInput input, List<String> options) {
+  private void addStaticInputLinkOptions(
+      LinkerInput input, List<String> options, @Nullable Map<Artifact, Artifact> ltoMap) {
     Preconditions.checkState(!isDynamicLibrary(input));
 
     // start-lib/end-lib library: adds its input object files.
@@ -912,13 +943,32 @@ public final class LinkCommandLine extends CommandLine {
       if (!Iterables.isEmpty(archiveMembers)) {
         options.add("-Wl,--start-lib");
         for (Artifact member : archiveMembers) {
-          options.add(member.getExecPathString());
+          if (ltoMap != null) {
+            Artifact backend = ltoMap.remove(member);
+
+            if (backend == null) {
+              System.err.println(
+                  "LTO backend file missing for " + member + " already did: " + options);
+              backend = member;
+            }
+            options.add(backend.getExecPathString());
+          } else {
+            options.add(member.getExecPathString());
+          }
         }
         options.add("-Wl,--end-lib");
       }
-    // For anything else, add the input directly.
     } else {
+      // For anything else, add the input directly.
       Artifact inputArtifact = input.getArtifact();
+
+      if (ltoMap != null) {
+        Artifact ltoArtifact = ltoMap.remove(inputArtifact);
+        if (ltoArtifact != null) {
+          inputArtifact = ltoArtifact;
+        }
+      }
+
       if (input.isFake()) {
         options.add(Link.FAKE_OBJECT_PREFIX + inputArtifact.getExecPathString());
       } else {
@@ -968,6 +1018,7 @@ public final class LinkCommandLine extends CommandLine {
     private boolean nativeDeps;
     private boolean useTestOnlyFlags;
     private boolean needWholeArchive;
+    @Nullable private Iterable<LTOBackendArtifacts> allLTOBackendArtifacts;
     @Nullable private Artifact paramFile;
     @Nullable private Artifact interfaceSoBuilder;
 
@@ -1023,6 +1074,7 @@ public final class LinkCommandLine extends CommandLine {
           nativeDeps,
           useTestOnlyFlags,
           needWholeArchive,
+          allLTOBackendArtifacts,
           paramFile,
           interfaceSoBuilder,
           variables,
@@ -1191,5 +1243,10 @@ public final class LinkCommandLine extends CommandLine {
       this.paramFile = paramFile;
       return this;
     }
+
+    public Builder setAllLTOArtifacts(Iterable<LTOBackendArtifacts> allLTOArtifacts) {
+      this.allLTOBackendArtifacts = allLTOArtifacts;
+      return this;
+    }
   }
 }