Tail Duplication Questions

I'm reading up on LLVM's implementation of tail duplication and the
description is confusing:

http://llvm.org/docs/Passes.html

  -tailduplicate: Tail Duplication

  This pass performs a limited form of tail duplication, intended to
  simplify CFGs by removing some unconditional branches. This pass is
  necessary to straighten out loops created by the C front-end, but also
  is capable of making other code nicer. After this pass is run, the CFG
  simplify pass should be run to clean up the mess.

First, lib/CodeGen/TailDuplication.cpp says the pass name is
-tailduplication, not -tailduplicate. Am I looking at the right pass?

  INITIALIZE_PASS(TailDuplicatePass, "tailduplication", "Tail Duplication",
                  false, false)

Second, SimplifyCFG is a FunctionPass, not a MachineFunctionPass. What
cleanup pass is this description really referring to?

Thanks!

                         -David

There is a tail duplication that runs on bitcode. I think this is the one that the document refers to.

-Krzysztof

We used to have an LLVM-IR pass did tail duplication
(http://llvm.org/viewvc/llvm-project/llvm/tags/RELEASE_29/final/lib/Transforms/Scalar/TailDuplication.cpp)
It was not used and went away with 3.0. The documentation is out of
date.

commit f940a1a869b4fe6f857e7fd8aeb97e7b7e9b390e
Author: Rafael Espindola <rafael.espindola@gmail.com>

    Remove the old tail duplication pass. It is not used and is unable to update
    ssa, so it has to be run really early in the pipeline. Any replacement
    should probably use the SSAUpdater.

    git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138841
91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/docs/ReleaseNotes.html b/docs/ReleaseNotes.html
index 6188ffd4..4feb907 100644
--- a/docs/ReleaseNotes.html
+++ b/docs/ReleaseNotes.html
@@ -583,6 +583,8 @@ it run faster:</p>
<ul>
   <li>The <code>LowerSetJmp</code> pass wasn't used effectively by any
       target and has been removed.</li>
+ <li>The old <code>TailDup</code> pass was not used in the standard pipeline
+ and was unable to update ssa form, so it has been removed.
   <li>The syntax of volatile loads and stores in IR has been changed to
       "<code>load volatile</code>"/"<code>store volatile</code>". The old
       syntax ("<code>volatile load</code>"/"<code>volatile store</code>")

Arnold Schwaighofer <arnold.schwaighofer@gmail.com> writes:

We used to have an LLVM-IR pass did tail duplication
(http://llvm.org/viewvc/llvm-project/llvm/tags/RELEASE_29/final/lib/Transforms/Scalar/TailDuplication.cpp)
It was not used and went away with 3.0. The documentation is out of
date.

Ah. So is the MachineFunction version expected to work correctly?

                               -David

It's part of the default set of CodeGen passes.

-Eli

Eli Friedman <eli.friedman@gmail.com> writes:

Ah. So is the MachineFunction version expected to work correctly?

It's part of the default set of CodeGen passes.

It is? Was that true in 3.1? I can't see where it is initialized in
llc. I probably missed something important. :slight_smile:

Thanks!

                             -David

http://llvm.org/viewvc/llvm-project/llvm/tags/RELEASE_31/final/lib/CodeGen/Passes.cpp?revision=156747&view=markup

void TargetPassConfig::addMachineSSAOptimization() {
  // Pre-ra tail duplication.
  if (addPass(EarlyTailDuplicateID) != &NoPassID)
    printAndVerify("After Pre-RegAlloc TailDuplicate");

/// Add passes that optimize machine instructions after register allocation.
void TargetPassConfig::addMachineLateOptimization() {
  // Branch folding must be run after regalloc and prolog/epilog insertion.
  if (addPass(BranchFolderPassID) != &NoPassID)
    printAndVerify("After BranchFolding");

  // Tail duplication.
  if (addPass(TailDuplicateID) != &NoPassID)
    printAndVerify("After TailDuplicate");

Arnold Schwaighofer <arnolds@codeaurora.org> writes:

http://llvm.org/viewvc/llvm-project/llvm/tags/RELEASE_31/final/lib/CodeGen/Passes.cpp?revision=156747&view=markup

void TargetPassConfig::addMachineSSAOptimization() {
  // Pre-ra tail duplication.
  if (addPass(EarlyTailDuplicateID) != &NoPassID)
    printAndVerify("After Pre-RegAlloc TailDuplicate");

/// Add passes that optimize machine instructions after register allocation.
void TargetPassConfig::addMachineLateOptimization() {
  // Branch folding must be run after regalloc and prolog/epilog insertion.
  if (addPass(BranchFolderPassID) != &NoPassID)
    printAndVerify("After BranchFolding");

  // Tail duplication.
  if (addPass(TailDuplicateID) != &NoPassID)
    printAndVerify("After TailDuplicate");

Hmm. Why doesn't -tailduplication show up in llc -help?