Attachment 221579 Details for Bug 127245 – llvm patch

[patch] llvm patch

revive-llvm-tail-dup.patch (text/plain), 32.05 KB, created by Filip Pizlo on 2014-01-18 20:21:15 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2014-01-18 20:21:15 PST

Size: 32.05 KB

patch

obsolete

>Index: include/llvm/InitializePasses.h
>===================================================================
>--- include/llvm/InitializePasses.h	(revision 199570)
>+++ include/llvm/InitializePasses.h	(working copy)
>@@ -245,6 +245,7 @@
> void initializeStripNonDebugSymbolsPass(PassRegistry&);
> void initializeStripSymbolsPass(PassRegistry&);
> void initializeTailCallElimPass(PassRegistry&);
>+void initializeTailDupPass(PassRegistry&);
> void initializeTailDuplicatePassPass(PassRegistry&);
> void initializeTargetPassConfigPass(PassRegistry&);
> void initializeDataLayoutPass(PassRegistry&);
>Index: include/llvm/LinkAllPasses.h
>===================================================================
>--- include/llvm/LinkAllPasses.h	(revision 199570)
>+++ include/llvm/LinkAllPasses.h	(working copy)
>@@ -126,6 +126,7 @@
>       (void) llvm::createStripDeadDebugInfoPass();
>       (void) llvm::createStripDeadPrototypesPass();
>       (void) llvm::createTailCallEliminationPass();
>+      (void) llvm::createTailDuplicationPass();
>       (void) llvm::createJumpThreadingPass();
>       (void) llvm::createUnifyFunctionExitNodesPass();
>       (void) llvm::createInstCountPass();
>Index: include/llvm/Transforms/Scalar.h
>===================================================================
>--- include/llvm/Transforms/Scalar.h	(revision 199570)
>+++ include/llvm/Transforms/Scalar.h	(working copy)
>@@ -195,6 +195,13 @@
> 
> //===----------------------------------------------------------------------===//
> //
>+// TailDuplication - Eliminate unconditional branches through controlled code
>+// duplication, creating simpler CFG structures.
>+//
>+FunctionPass *createTailDuplicationPass();
>+
>+//===----------------------------------------------------------------------===//
>+//
> // JumpThreading - Thread control through mult-pred/multi-succ blocks where some
> // preds always go to some succ.
> //
>Index: include/llvm-c/Transforms/Scalar.h
>===================================================================
>--- include/llvm-c/Transforms/Scalar.h	(revision 199570)
>+++ include/llvm-c/Transforms/Scalar.h	(working copy)
>@@ -108,6 +108,9 @@
> /** See llvm::createTailCallEliminationPass function. */
> void LLVMAddTailCallEliminationPass(LLVMPassManagerRef PM);
> 
>+/** See llvm::createTailDuplicationPass function. */
>+void LLVMAddTailDuplicationPass(LLVMPassManagerRef PM);
>+
> /** See llvm::createConstantPropagationPass function. */
> void LLVMAddConstantPropagationPass(LLVMPassManagerRef PM);
> 
>Index: lib/Transforms/Scalar/CMakeLists.txt
>===================================================================
>--- lib/Transforms/Scalar/CMakeLists.txt	(revision 199570)
>+++ lib/Transforms/Scalar/CMakeLists.txt	(working copy)
>@@ -34,6 +34,7 @@
>   FlattenCFGPass.cpp
>   Sink.cpp
>   StructurizeCFG.cpp
>+  TailDuplication.cpp
>   TailRecursionElimination.cpp
>   )
> 
>Index: lib/Transforms/Scalar/Scalar.cpp
>===================================================================
>--- lib/Transforms/Scalar/Scalar.cpp	(revision 199570)
>+++ lib/Transforms/Scalar/Scalar.cpp	(working copy)
>@@ -63,6 +63,7 @@
>   initializeCFGSimplifyPassPass(Registry);
>   initializeStructurizeCFGPass(Registry);
>   initializeSinkingPass(Registry);
>+  initializeTailDupPass(Registry);
>   initializeTailCallElimPass(Registry);
> }
> 
>@@ -171,6 +172,10 @@
>   unwrap(PM)->add(createTailCallEliminationPass());
> }
> 
>+void LLVMAddTailDuplicationPass(LLVMPassManagerRef PM) {
>+  unwrap(PM)->add(createTailDuplicationPass());
>+}
>+
> void LLVMAddConstantPropagationPass(LLVMPassManagerRef PM) {
>   unwrap(PM)->add(createConstantPropagationPass());
> }
>Index: lib/Transforms/Scalar/TailDuplication.cpp
>===================================================================
>--- lib/Transforms/Scalar/TailDuplication.cpp	(revision 0)
>+++ lib/Transforms/Scalar/TailDuplication.cpp	(working copy)
>@@ -0,0 +1,378 @@
>+//===- TailDuplication.cpp - Simplify CFG through tail duplication --------===//
>+//
>+//                     The LLVM Compiler Infrastructure
>+//
>+// This file is distributed under the University of Illinois Open Source
>+// License. See LICENSE.TXT for details.
>+//
>+//===----------------------------------------------------------------------===//
>+//
>+// 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.
>+//
>+// This pass could be enhanced in the future to use profile information to be
>+// more aggressive.
>+//
>+//===----------------------------------------------------------------------===//
>+
>+#define DEBUG_TYPE "tailduplicate"
>+#include "llvm/Transforms/Scalar.h"
>+#include "llvm/IR/Constant.h"
>+#include "llvm/IR/Function.h"
>+#include "llvm/IR/Instructions.h"
>+#include "llvm/IR/IntrinsicInst.h"
>+#include "llvm/IR/Type.h"
>+#include "llvm/Pass.h"
>+#include "llvm/ADT/Statistic.h"
>+#include "llvm/ADT/SmallPtrSet.h"
>+#include "llvm/Analysis/ValueTracking.h"
>+#include "llvm/Analysis/InstructionSimplify.h"
>+#include "llvm/Support/CFG.h"
>+#include "llvm/Support/CommandLine.h"
>+#include "llvm/Support/Debug.h"
>+#include "llvm/Support/raw_ostream.h"
>+#include "llvm/Transforms/Utils/Local.h"
>+#include <map>
>+using namespace llvm;
>+
>+STATISTIC(NumEliminated, "Number of unconditional branches eliminated");
>+
>+static cl::opt<unsigned>
>+TailDupThreshold("taildup-threshold",
>+                 cl::desc("Max block size to tail duplicate"),
>+                 cl::init(5), cl::Hidden);
>+
>+namespace {
>+  class TailDup : public FunctionPass {
>+    bool runOnFunction(Function &F);
>+  public:
>+    static char ID; // Pass identification, replacement for typeid
>+    TailDup() : FunctionPass(ID) {
>+      initializeTailDupPass(*PassRegistry::getPassRegistry());
>+    }
>+
>+  private:
>+    inline bool shouldEliminateUnconditionalBranch(TerminatorInst *, unsigned);
>+    inline void eliminateUnconditionalBranch(BranchInst *BI);
>+    SmallPtrSet<BasicBlock*, 4> CycleDetector;
>+  };
>+}
>+
>+char TailDup::ID = 0;
>+INITIALIZE_PASS(TailDup, "tailduplicate", "Tail Duplication", false, false)
>+
>+// Public interface to the Tail Duplication pass
>+FunctionPass *llvm::createTailDuplicationPass() { return new TailDup(); }
>+
>+/// runOnFunction - Top level algorithm - Loop over each unconditional branch in
>+/// the function, eliminating it if it looks attractive enough.  CycleDetector
>+/// prevents infinite loops by checking that we aren't redirecting a branch to
>+/// a place it already pointed to earlier; see PR 2323.
>+bool TailDup::runOnFunction(Function &F) {
>+  bool Changed = false;
>+  CycleDetector.clear();
>+  for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
>+    if (shouldEliminateUnconditionalBranch(I->getTerminator(),
>+                                           TailDupThreshold)) {
>+      eliminateUnconditionalBranch(cast<BranchInst>(I->getTerminator()));
>+      Changed = true;
>+    } else {
>+      ++I;
>+      CycleDetector.clear();
>+    }
>+  }
>+  return Changed;
>+}
>+
>+/// shouldEliminateUnconditionalBranch - Return true if this branch looks
>+/// attractive to eliminate.  We eliminate the branch if the destination basic
>+/// block has <= 5 instructions in it, not counting PHI nodes.  In practice,
>+/// since one of these is a terminator instruction, this means that we will add
>+/// up to 4 instructions to the new block.
>+///
>+/// We don't count PHI nodes in the count since they will be removed when the
>+/// contents of the block are copied over.
>+///
>+bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI,
>+                                                 unsigned Threshold) {
>+  BranchInst *BI = dyn_cast<BranchInst>(TI);
>+  if (!BI || !BI->isUnconditional()) return false;  // Not an uncond branch!
>+
>+  BasicBlock *Dest = BI->getSuccessor(0);
>+  if (Dest == BI->getParent()) return false;        // Do not loop infinitely!
>+
>+  // Do not inline a block if we will just get another branch to the same block!
>+  TerminatorInst *DTI = Dest->getTerminator();
>+  if (BranchInst *DBI = dyn_cast<BranchInst>(DTI))
>+    if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest)
>+      return false;                                 // Do not loop infinitely!
>+
>+  // FIXME: DemoteRegToStack cannot yet demote invoke instructions to the stack,
>+  // because doing so would require breaking critical edges.  This should be
>+  // fixed eventually.
>+  if (!DTI->use_empty())
>+    return false;
>+
>+  // Do not bother with blocks with only a single predecessor: simplify
>+  // CFG will fold these two blocks together!
>+  pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest);
>+  ++PI;
>+  if (PI == PE) return false;  // Exactly one predecessor!
>+
>+  BasicBlock::iterator I = Dest->getFirstNonPHI();
>+
>+  for (unsigned Size = 0; I != Dest->end(); ++I) {
>+    if (Size == Threshold)
>+      return false;  // The block is too large.
>+    
>+    // Don't tail duplicate call instructions.  They are very large compared to
>+    // other instructions.
>+    if (isa<CallInst>(I) || isa<InvokeInst>(I))
>+      return false;
>+
>+    // Also alloca and malloc.
>+    if (isa<AllocaInst>(I))
>+      return false;
>+
>+    // Some vector instructions can expand into a number of instructions.
>+    if (isa<ShuffleVectorInst>(I) || isa<ExtractElementInst>(I) ||
>+        isa<InsertElementInst>(I))
>+      return false;
>+    
>+    // Only count instructions that are not debugger intrinsics.
>+    if (!isa<DbgInfoIntrinsic>(I)) ++Size;
>+  }
>+  
>+  // Do not tail duplicate a block that has thousands of successors into a block
>+  // with a single successor if the block has many other predecessors.  This can
>+  // cause an N^2 explosion in CFG edges (and PHI node entries), as seen in
>+  // cases that have a large number of indirect gotos.
>+  unsigned NumSuccs = DTI->getNumSuccessors();
>+  if (NumSuccs > 8) {
>+    unsigned TooMany = 128;
>+    if (NumSuccs >= TooMany) return false;
>+    TooMany = TooMany/NumSuccs;
>+    for (; PI != PE; ++PI)
>+      if (TooMany-- == 0) return false;
>+  }
>+  
>+  // If this unconditional branch is a fall-through, be careful about
>+  // tail duplicating it.  In particular, we don't want to taildup it if the
>+  // original block will still be there after taildup is completed: doing so
>+  // would eliminate the fall-through, requiring unconditional branches.
>+  Function::iterator DestI = Dest;
>+  if (&*--DestI == BI->getParent()) {
>+    // The uncond branch is a fall-through.  Tail duplication of the block is
>+    // will eliminate the fall-through-ness and end up cloning the terminator
>+    // at the end of the Dest block.  Since the original Dest block will
>+    // continue to exist, this means that one or the other will not be able to
>+    // fall through.  One typical example that this helps with is code like:
>+    // if (a)
>+    //   foo();
>+    // if (b)
>+    //   foo();
>+    // Cloning the 'if b' block into the end of the first foo block is messy.
>+    
>+    // The messy case is when the fall-through block falls through to other
>+    // blocks.  This is what we would be preventing if we cloned the block.
>+    DestI = Dest;
>+    if (++DestI != Dest->getParent()->end()) {
>+      BasicBlock *DestSucc = DestI;
>+      // If any of Dest's successors are fall-throughs, don't do this xform.
>+      for (succ_iterator SI = succ_begin(Dest), SE = succ_end(Dest);
>+           SI != SE; ++SI)
>+        if (*SI == DestSucc)
>+          return false;
>+    }
>+  }
>+
>+  // Finally, check that we haven't redirected to this target block earlier;
>+  // there are cases where we loop forever if we don't check this (PR 2323).
>+  if (!CycleDetector.insert(Dest))
>+    return false;
>+
>+  return true;
>+}
>+
>+/// FindObviousSharedDomOf - We know there is a branch from SrcBlock to
>+/// DestBlock, and that SrcBlock is not the only predecessor of DstBlock.  If we
>+/// can find a predecessor of SrcBlock that is a dominator of both SrcBlock and
>+/// DstBlock, return it.
>+static BasicBlock *FindObviousSharedDomOf(BasicBlock *SrcBlock,
>+                                          BasicBlock *DstBlock) {
>+  // SrcBlock must have a single predecessor.
>+  pred_iterator PI = pred_begin(SrcBlock), PE = pred_end(SrcBlock);
>+  if (PI == PE || ++PI != PE) return 0;
>+
>+  BasicBlock *SrcPred = *pred_begin(SrcBlock);
>+
>+  // Look at the predecessors of DstBlock.  One of them will be SrcBlock.  If
>+  // there is only one other pred, get it, otherwise we can't handle it.
>+  PI = pred_begin(DstBlock); PE = pred_end(DstBlock);
>+  BasicBlock *DstOtherPred = 0;
>+  BasicBlock *P = *PI;
>+  if (P == SrcBlock) {
>+    if (++PI == PE) return 0;
>+    DstOtherPred = *PI;
>+    if (++PI != PE) return 0;
>+  } else {
>+    DstOtherPred = P;
>+    if (++PI == PE || *PI != SrcBlock || ++PI != PE) return 0;
>+  }
>+
>+  // We can handle two situations here: "if then" and "if then else" blocks.  An
>+  // 'if then' situation is just where DstOtherPred == SrcPred.
>+  if (DstOtherPred == SrcPred)
>+    return SrcPred;
>+
>+  // Check to see if we have an "if then else" situation, which means that
>+  // DstOtherPred will have a single predecessor and it will be SrcPred.
>+  PI = pred_begin(DstOtherPred); PE = pred_end(DstOtherPred);
>+  if (PI != PE && *PI == SrcPred) {
>+    if (++PI != PE) return 0;  // Not a single pred.
>+    return SrcPred;  // Otherwise, it's an "if then" situation.  Return the if.
>+  }
>+
>+  // Otherwise, this is something we can't handle.
>+  return 0;
>+}
>+
>+
>+/// eliminateUnconditionalBranch - Clone the instructions from the destination
>+/// block into the source block, eliminating the specified unconditional branch.
>+/// If the destination block defines values used by successors of the dest
>+/// block, we may need to insert PHI nodes.
>+///
>+void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) {
>+  BasicBlock *SourceBlock = Branch->getParent();
>+  BasicBlock *DestBlock = Branch->getSuccessor(0);
>+  assert(SourceBlock != DestBlock && "Our predicate is broken!");
>+
>+  DEBUG(dbgs() << "TailDuplication[" << SourceBlock->getParent()->getName()
>+        << "]: Eliminating branch: " << *Branch);
>+
>+  // See if we can avoid duplicating code by moving it up to a dominator of both
>+  // blocks.
>+  if (BasicBlock *DomBlock = FindObviousSharedDomOf(SourceBlock, DestBlock)) {
>+    DEBUG(dbgs() << "Found shared dominator: " << DomBlock->getName() << "\n");
>+
>+    // If there are non-phi instructions in DestBlock that have no operands
>+    // defined in DestBlock, and if the instruction has no side effects, we can
>+    // move the instruction to DomBlock instead of duplicating it.
>+    BasicBlock::iterator BBI = DestBlock->getFirstNonPHI();
>+    while (!isa<TerminatorInst>(BBI)) {
>+      Instruction *I = BBI++;
>+
>+      bool CanHoist = isSafeToSpeculativelyExecute(I) &&
>+                      !I->mayReadFromMemory();
>+      if (CanHoist) {
>+        for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
>+          if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(op)))
>+            if (OpI->getParent() == DestBlock ||
>+                (isa<InvokeInst>(OpI) && OpI->getParent() == DomBlock)) {
>+              CanHoist = false;
>+              break;
>+            }
>+        if (CanHoist) {
>+          // Remove from DestBlock, move right before the term in DomBlock.
>+          DestBlock->getInstList().remove(I);
>+          DomBlock->getInstList().insert(DomBlock->getTerminator(), I);
>+          DEBUG(dbgs() << "Hoisted: " << *I);
>+        }
>+      }
>+    }
>+  }
>+
>+  // Tail duplication can not update SSA properties correctly if the values
>+  // defined in the duplicated tail are used outside of the tail itself.  For
>+  // this reason, we spill all values that are used outside of the tail to the
>+  // stack.
>+  for (BasicBlock::iterator I = DestBlock->begin(); I != DestBlock->end(); ++I)
>+    if (I->isUsedOutsideOfBlock(DestBlock)) {
>+      // We found a use outside of the tail.  Create a new stack slot to
>+      // break this inter-block usage pattern.
>+      DemoteRegToStack(*I);
>+    }
>+
>+  // We are going to have to map operands from the original block B to the new
>+  // copy of the block B'.  If there are PHI nodes in the DestBlock, these PHI
>+  // nodes also define part of this mapping.  Loop over these PHI nodes, adding
>+  // them to our mapping.
>+  //
>+  std::map<Value*, Value*> ValueMapping;
>+
>+  BasicBlock::iterator BI = DestBlock->begin();
>+  bool HadPHINodes = isa<PHINode>(BI);
>+  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
>+    ValueMapping[PN] = PN->getIncomingValueForBlock(SourceBlock);
>+
>+  // Clone the non-phi instructions of the dest block into the source block,
>+  // keeping track of the mapping...
>+  //
>+  for (; BI != DestBlock->end(); ++BI) {
>+    Instruction *New = BI->clone();
>+    New->setName(BI->getName());
>+    SourceBlock->getInstList().push_back(New);
>+    ValueMapping[BI] = New;
>+  }
>+
>+  // Now that we have built the mapping information and cloned all of the
>+  // instructions (giving us a new terminator, among other things), walk the new
>+  // instructions, rewriting references of old instructions to use new
>+  // instructions.
>+  //
>+  BI = Branch; ++BI;  // Get an iterator to the first new instruction
>+  for (; BI != SourceBlock->end(); ++BI)
>+    for (unsigned i = 0, e = BI->getNumOperands(); i != e; ++i) {
>+      std::map<Value*, Value*>::const_iterator I =
>+        ValueMapping.find(BI->getOperand(i));
>+      if (I != ValueMapping.end())
>+        BI->setOperand(i, I->second);
>+    }
>+
>+  // Next we check to see if any of the successors of DestBlock had PHI nodes.
>+  // If so, we need to add entries to the PHI nodes for SourceBlock now.
>+  for (succ_iterator SI = succ_begin(DestBlock), SE = succ_end(DestBlock);
>+       SI != SE; ++SI) {
>+    BasicBlock *Succ = *SI;
>+    for (BasicBlock::iterator PNI = Succ->begin(); isa<PHINode>(PNI); ++PNI) {
>+      PHINode *PN = cast<PHINode>(PNI);
>+      // Ok, we have a PHI node.  Figure out what the incoming value was for the
>+      // DestBlock.
>+      Value *IV = PN->getIncomingValueForBlock(DestBlock);
>+
>+      // Remap the value if necessary...
>+      std::map<Value*, Value*>::const_iterator I = ValueMapping.find(IV);
>+      if (I != ValueMapping.end())
>+        IV = I->second;
>+      PN->addIncoming(IV, SourceBlock);
>+    }
>+  }
>+
>+  // Next, remove the old branch instruction, and any PHI node entries that we
>+  // had.
>+  BI = Branch; ++BI;  // Get an iterator to the first new instruction
>+  DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes...
>+  SourceBlock->getInstList().erase(Branch);  // Destroy the uncond branch...
>+
>+  // Final step: now that we have finished everything up, walk the cloned
>+  // instructions one last time, constant propagating and DCE'ing them, because
>+  // they may not be needed anymore.
>+  //
>+  if (HadPHINodes) {
>+    while (BI != SourceBlock->end()) {
>+      Instruction *Inst = BI++;
>+      if (isInstructionTriviallyDead(Inst))
>+        Inst->eraseFromParent();
>+      else if (Value *V = SimplifyInstruction(Inst)) {
>+        Inst->replaceAllUsesWith(V);
>+        Inst->eraseFromParent();
>+      }
>+    }
>+  }
>+
>+  ++NumEliminated;  // We just killed a branch!
>+}
>Index: test/Transforms/LoopDeletion/2008-05-06-Phi.ll
>===================================================================
>--- test/Transforms/LoopDeletion/2008-05-06-Phi.ll	(revision 199570)
>+++ test/Transforms/LoopDeletion/2008-05-06-Phi.ll	(working copy)
>@@ -1,4 +1,4 @@
>-; RUN: opt < %s -inline -instcombine -jump-threading -licm -loop-unswitch -instcombine -indvars -loop-deletion -gvn -simplifycfg -verify -disable-output
>+; RUN: opt < %s -inline -tailduplicate -instcombine -jump-threading -licm -loop-unswitch -instcombine -indvars -loop-deletion -gvn -simplifycfg -verify -disable-output
> 
> target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
> target triple = "i386-apple-darwin9"
>Index: test/Transforms/LoopSimplify/2003-08-15-PreheadersFail.ll
>===================================================================
>--- test/Transforms/LoopSimplify/2003-08-15-PreheadersFail.ll	(revision 199570)
>+++ test/Transforms/LoopSimplify/2003-08-15-PreheadersFail.ll	(working copy)
>@@ -1,4 +1,4 @@
>-; RUN: opt < %s -instcombine -simplifycfg -licm -disable-output
>+; RUN: opt < %s -tailduplicate -instcombine -simplifycfg -licm -disable-output
> target datalayout = "e-p:32:32"
> @yy_base = external global [787 x i16]		; <[787 x i16]*> [#uses=1]
> @yy_state_ptr = external global i32*		; <i32**> [#uses=3]
>Index: test/Transforms/TailDup/2003-06-24-Simpleloop.ll
>===================================================================
>--- test/Transforms/TailDup/2003-06-24-Simpleloop.ll	(revision 0)
>+++ test/Transforms/TailDup/2003-06-24-Simpleloop.ll	(working copy)
>@@ -0,0 +1,15 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+define void @motion_result7() {
>+entry:
>+       br label %endif
>+endif:         ; preds = %no_exit, %entry
>+       %i.1 = phi i32 [ %inc, %no_exit ], [ 0, %entry ]                ; <i32> [#uses=1]
>+       %inc = add i32 %i.1, 1          ; <i32> [#uses=1]
>+       br i1 false, label %no_exit, label %UnifiedExitNode
>+no_exit:               ; preds = %endif
>+       br i1 false, label %UnifiedExitNode, label %endif
>+UnifiedExitNode:               ; preds = %no_exit, %endif
>+       ret void
>+}
>+
>Index: test/Transforms/TailDup/2003-07-22-InfiniteLoop.ll
>===================================================================
>--- test/Transforms/TailDup/2003-07-22-InfiniteLoop.ll	(revision 0)
>+++ test/Transforms/TailDup/2003-07-22-InfiniteLoop.ll	(working copy)
>@@ -0,0 +1,11 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+define i32 @sum() {
>+entry:
>+       br label %loopentry
>+loopentry:             ; preds = %loopentry, %entry
>+       %i.0 = phi i32 [ 1, %entry ], [ %tmp.3, %loopentry ]            ; <i32> [#uses=1]
>+       %tmp.3 = add i32 %i.0, 1                ; <i32> [#uses=1]
>+       br label %loopentry
>+}
>+
>Index: test/Transforms/TailDup/2003-08-23-InvalidatedPointers.ll
>===================================================================
>--- test/Transforms/TailDup/2003-08-23-InvalidatedPointers.ll	(revision 0)
>+++ test/Transforms/TailDup/2003-08-23-InvalidatedPointers.ll	(working copy)
>@@ -0,0 +1,29 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+define i32 @sell_haggle() {
>+entry:
>+       br i1 false, label %then.5, label %UnifiedExitNode
>+then.5:                ; preds = %entry
>+       br i1 false, label %loopentry.1.preheader, label %else.1
>+else.1:                ; preds = %then.5
>+       br label %loopentry.1.preheader
>+loopentry.1.preheader:         ; preds = %else.1, %then.5
>+       %final_ask.0 = phi i32 [ 0, %else.1 ], [ 0, %then.5 ]           ; <i32> [#uses=2]
>+       br label %loopentry.1
>+loopentry.1:           ; preds = %endif.17, %loopentry.1.preheader
>+       switch i32 0, label %UnifiedExitNode [
>+                i32 2, label %UnifiedExitNode
>+                i32 1, label %endif.16
>+       ]
>+endif.16:              ; preds = %loopentry.1
>+       br i1 false, label %then.17, label %UnifiedExitNode
>+then.17:               ; preds = %endif.16
>+       br i1 false, label %then.18, label %endif.17
>+then.18:               ; preds = %then.17
>+       br i1 false, label %endif.17, label %UnifiedExitNode
>+endif.17:              ; preds = %then.18, %then.17
>+       %cur_ask.3 = phi i32 [ %final_ask.0, %then.17 ], [ %final_ask.0, %then.18 ]             ; <i32> [#uses=0]
>+       br i1 false, label %loopentry.1, label %UnifiedExitNode
>+UnifiedExitNode:               ; preds = %endif.17, %then.18, %endif.16, %loopentry.1, %loopentry.1, %entry
>+       ret i32 0
>+}
>Index: test/Transforms/TailDup/2003-08-31-UnreachableBlocks.ll
>===================================================================
>--- test/Transforms/TailDup/2003-08-31-UnreachableBlocks.ll	(revision 0)
>+++ test/Transforms/TailDup/2003-08-31-UnreachableBlocks.ll	(working copy)
>@@ -0,0 +1,17 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+define i32 @foo() {
>+entry:
>+       br label %return.i
>+after_ret.i:           ; No predecessors!
>+       br label %return.i
>+return.i:              ; preds = %after_ret.i, %entry
>+       %tmp.3 = ptrtoint i32* null to i32              ; <i32> [#uses=1]
>+       br label %return.i1
>+after_ret.i1:          ; No predecessors!
>+       br label %return.i1
>+return.i1:             ; preds = %after_ret.i1, %return.i
>+       %tmp.8 = sub i32 %tmp.3, 0              ; <i32> [#uses=0]
>+       ret i32 0
>+}
>+
>Index: test/Transforms/TailDup/2004-04-01-DemoteRegToStack.ll
>===================================================================
>--- test/Transforms/TailDup/2004-04-01-DemoteRegToStack.ll	(revision 0)
>+++ test/Transforms/TailDup/2004-04-01-DemoteRegToStack.ll	(working copy)
>@@ -0,0 +1,20 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+define void @interpret() {
>+entry:
>+       br label %retry
>+retry:         ; preds = %endif.4, %entry
>+       %tmp.8 = call i32 @interp( )            ; <i32> [#uses=3]
>+       switch i32 0, label %endif.4 [
>+                i32 -25, label %return
>+                i32 -16, label %return
>+       ]
>+endif.4:               ; preds = %retry
>+       br i1 false, label %return, label %retry
>+return:                ; preds = %endif.4, %retry, %retry
>+       %result.0 = phi i32 [ %tmp.8, %retry ], [ %tmp.8, %retry ], [ %tmp.8, %endif.4 ]                ; <i32> [#uses=0]
>+       ret void
>+}
>+
>+declare i32 @interp()
>+
>Index: test/Transforms/TailDup/2008-05-13-InfiniteLoop.ll
>===================================================================
>--- test/Transforms/TailDup/2008-05-13-InfiniteLoop.ll	(revision 0)
>+++ test/Transforms/TailDup/2008-05-13-InfiniteLoop.ll	(working copy)
>@@ -0,0 +1,26 @@
>+; RUN: opt < %s -tailduplicate | llc
>+; PR2323
>+
>+define i32 @func_27(i32 %p_28) nounwind  {
>+entry:
>+  %tmp125 = trunc i32 %p_28 to i8   ; <i8> [#uses=1]
>+  %tmp5.i = icmp eq i8 %tmp125, 0   ; <i1> [#uses=1]
>+  br i1 %tmp5.i, label %bb8.i, label %bb.i
>+
>+bb.i:   ; preds = %entry
>+  br label %bb39.i
>+
>+bb8.i:    ; preds = %entry
>+  br label %bb11.i
>+
>+bb11.i:   ; preds = %bb39.i, %bb8.i
>+  %tmp126 = trunc i32 %p_28 to i8   ; <i8> [#uses=1]
>+  br label %bb39.i
>+
>+bb39.i:   ; preds = %bb11.i, %bb.i
>+  %tmp127 = trunc i32 %p_28 to i8   ; <i8> [#uses=1]
>+  br label %bb11.i
>+
>+func_29.exit:   ; No predecessors!
>+  ret i32 undef
>+}
>Index: test/Transforms/TailDup/2009-07-31-phicrash.ll
>===================================================================
>--- test/Transforms/TailDup/2009-07-31-phicrash.ll	(revision 0)
>+++ test/Transforms/TailDup/2009-07-31-phicrash.ll	(working copy)
>@@ -0,0 +1,14 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+; PR4662
>+
>+define void @a() {
>+BB:
>+       br label %BB6
>+
>+BB6:
>+       %tmp9 = phi i64 [ 0, %BB ], [ 5, %BB34 ]
>+       br label %BB34
>+
>+BB34:
>+       br label %BB6
>+}
>Index: test/Transforms/TailDup/MergeTest.ll
>===================================================================
>--- test/Transforms/TailDup/MergeTest.ll	(revision 0)
>+++ test/Transforms/TailDup/MergeTest.ll	(working copy)
>@@ -0,0 +1,27 @@
>+; RUN: opt < %s -tailduplicate -taildup-threshold=2 -S | grep add | not grep uses=1
>+
>+define i32 @test1(i1 %C, i32 %A, i32* %P) {
>+entry:
>+       br i1 %C, label %L1, label %L2
>+L1:            ; preds = %entry
>+       store i32 1, i32* %P
>+       br label %L2
>+L2:            ; preds = %L1, %entry
>+       %X = add i32 %A, 17             ; <i32> [#uses=1]
>+       ret i32 %X
>+}
>+
>+define i32 @test2(i1 %C, i32 %A, i32* %P) {
>+entry:
>+       br i1 %C, label %L1, label %L2
>+L1:            ; preds = %entry
>+       store i32 1, i32* %P
>+       br label %L3
>+L2:            ; preds = %entry
>+       store i32 7, i32* %P
>+       br label %L3
>+L3:            ; preds = %L2, %L1
>+       %X = add i32 %A, 17             ; <i32> [#uses=1]
>+       ret i32 %X
>+}
>+
>Index: test/Transforms/TailDup/PHIUpdateTest.ll
>===================================================================
>--- test/Transforms/TailDup/PHIUpdateTest.ll	(revision 0)
>+++ test/Transforms/TailDup/PHIUpdateTest.ll	(working copy)
>@@ -0,0 +1,16 @@
>+; This test checks to make sure phi nodes are updated properly
>+;
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+define i32 @test(i1 %c, i32 %X, i32 %Y) {
>+       br label %L
>+L:             ; preds = %F, %0
>+       %A = add i32 %X, %Y             ; <i32> [#uses=1]
>+       br i1 %c, label %T, label %F
>+F:             ; preds = %L
>+       br i1 %c, label %L, label %T
>+T:             ; preds = %F, %L
>+       %V = phi i32 [ %A, %L ], [ 0, %F ]              ; <i32> [#uses=1]
>+       ret i32 %V
>+}
>+
>Index: test/Transforms/TailDup/X86/if-tail-dup.ll
>===================================================================
>--- test/Transforms/TailDup/X86/if-tail-dup.ll	(revision 0)
>+++ test/Transforms/TailDup/X86/if-tail-dup.ll	(working copy)
>@@ -0,0 +1,49 @@
>+; RUN: opt < %s -tailduplicate | \
>+; RUN:   llc -march=x86 -o %t
>+; RUN: grep je %t | count 4
>+; RUN: not grep jmp %t
>+; END.
>+; This should have no unconditional jumps in it.  The C source is:
>+
>+;void foo(int c, int* P) {
>+;  if (c & 1)  P[0] = 1;
>+;  if (c & 2)  P[1] = 1;
>+;  if (c & 4)  P[2] = 1;
>+;  if (c & 8)  P[3] = 1;
>+;}
>+
>+define void @foo(i32 %c, i32* %P) {
>+entry:
>+       %tmp1 = and i32 %c, 1           ; <i32> [#uses=1]
>+       %tmp1.upgrd.1 = icmp eq i32 %tmp1, 0            ; <i1> [#uses=1]
>+       br i1 %tmp1.upgrd.1, label %cond_next, label %cond_true
>+cond_true:             ; preds = %entry
>+       store i32 1, i32* %P
>+       br label %cond_next
>+cond_next:             ; preds = %cond_true, %entry
>+       %tmp5 = and i32 %c, 2           ; <i32> [#uses=1]
>+       %tmp5.upgrd.2 = icmp eq i32 %tmp5, 0            ; <i1> [#uses=1]
>+       br i1 %tmp5.upgrd.2, label %cond_next10, label %cond_true6
>+cond_true6:            ; preds = %cond_next
>+       %tmp8 = getelementptr i32* %P, i32 1            ; <i32*> [#uses=1]
>+       store i32 1, i32* %tmp8
>+       br label %cond_next10
>+cond_next10:           ; preds = %cond_true6, %cond_next
>+       %tmp13 = and i32 %c, 4          ; <i32> [#uses=1]
>+       %tmp13.upgrd.3 = icmp eq i32 %tmp13, 0          ; <i1> [#uses=1]
>+       br i1 %tmp13.upgrd.3, label %cond_next18, label %cond_true14
>+cond_true14:           ; preds = %cond_next10
>+       %tmp16 = getelementptr i32* %P, i32 2           ; <i32*> [#uses=1]
>+       store i32 1, i32* %tmp16
>+       br label %cond_next18
>+cond_next18:           ; preds = %cond_true14, %cond_next10
>+       %tmp21 = and i32 %c, 8          ; <i32> [#uses=1]
>+       %tmp21.upgrd.4 = icmp eq i32 %tmp21, 0          ; <i1> [#uses=1]
>+       br i1 %tmp21.upgrd.4, label %return, label %cond_true22
>+cond_true22:           ; preds = %cond_next18
>+       %tmp24 = getelementptr i32* %P, i32 3           ; <i32*> [#uses=1]
>+       store i32 1, i32* %tmp24
>+       ret void
>+return:                ; preds = %cond_next18
>+       ret void
>+}
>Index: test/Transforms/TailDup/basictest.ll
>===================================================================
>--- test/Transforms/TailDup/basictest.ll	(revision 0)
>+++ test/Transforms/TailDup/basictest.ll	(working copy)
>@@ -0,0 +1,20 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+declare void @__main()
>+
>+define i32 @main() {
>+entry:
>+       call void @__main( )
>+       br label %loopentry
>+loopentry:             ; preds = %no_exit, %entry
>+       %i.0 = phi i32 [ %inc, %no_exit ], [ 0, %entry ]                ; <i32> [#uses=3]
>+       %tmp.1 = icmp sle i32 %i.0, 99          ; <i1> [#uses=1]
>+       br i1 %tmp.1, label %no_exit, label %return
>+no_exit:               ; preds = %loopentry
>+       %tmp.51 = call i32 @main( )             ; <i32> [#uses=0]
>+       %inc = add i32 %i.0, 1          ; <i32> [#uses=1]
>+       br label %loopentry
>+return:                ; preds = %loopentry
>+       ret i32 %i.0
>+}
>+
>Index: test/Transforms/TailDup/basictest2.ll
>===================================================================
>--- test/Transforms/TailDup/basictest2.ll	(revision 0)
>+++ test/Transforms/TailDup/basictest2.ll	(working copy)
>@@ -0,0 +1,15 @@
>+; RUN: opt < %s -tailduplicate -disable-output
>+
>+define void @ab() {
>+entry:
>+       br label %loopentry.5
>+loopentry.5:           ; preds = %no_exit.5, %entry
>+       %poscnt.1 = phi i64 [ 0, %entry ], [ %tmp.289, %no_exit.5 ]             ; <i64> [#uses=1]
>+       %tmp.289 = ashr i64 %poscnt.1, 1                ; <i64> [#uses=1]
>+       br i1 false, label %no_exit.5, label %loopexit.5
>+no_exit.5:             ; preds = %loopentry.5
>+       br label %loopentry.5
>+loopexit.5:            ; preds = %loopentry.5
>+       ret void
>+}
>+

Actions: View | Formatted Diff | Diff

Attachments on bug 127245: 221578 | 221579