<commit_before>//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass performs several transformations to transform natural loops into a
// simpler form, which makes subsequent analyses and transformations simpler and
// more effective.
//
// Loop pre-header insertion guarantees that there is a single, non-critical
// entry edge from outside of the loop to the loop header.  This simplifies a
// number of analyses and transformations, such as LICM.
//
// Loop exit-block insertion guarantees that all exit blocks from the loop
// (blocks which are outside of the loop that have predecessors inside of the
// loop) only have predecessors from inside of the loop (and are thus dominated
// by the loop header).  This simplifies transformations such as store-sinking
// that are built into LICM.
//
// This pass also guarantees that loops will have exactly one backedge.
//
// Note that the simplifycfg pass will clean up blocks which are split out but
// end up being unnecessary, so usage of this pass should not pessimize
// generated code.
//
// This pass obviously modifies the CFG, but updates loop information and
// dominator information.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constant.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Type.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Support/CFG.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/DepthFirstIterator.h"
using namespace llvm;

namespace {
  Statistic<>
  NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted");
  Statistic<>
  NumNested("loopsimplify", "Number of nested loops split out");

  struct LoopSimplify : public FunctionPass {
    // AA - If we have an alias analysis object to update, this is it, otherwise
    // this is null.
    AliasAnalysis *AA;

    virtual bool runOnFunction(Function &F);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      // We need loop information to identify the loops...
      AU.addRequired<LoopInfo>();
      AU.addRequired<DominatorSet>();
      AU.addRequired<DominatorTree>();

      AU.addPreserved<LoopInfo>();
      AU.addPreserved<DominatorSet>();
      AU.addPreserved<ImmediateDominators>();
      AU.addPreserved<DominatorTree>();
      AU.addPreserved<DominanceFrontier>();
      AU.addPreservedID(BreakCriticalEdgesID);  // No crit edges added....
    }
  private:
    bool ProcessLoop(Loop *L);
    BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix,
                                       const std::vector<BasicBlock*> &Preds);
    BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
    void InsertPreheaderForLoop(Loop *L);
    Loop *SeparateNestedLoop(Loop *L);
    void InsertUniqueBackedgeBlock(Loop *L);

    void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
                                         std::vector<BasicBlock*> &PredBlocks);
  };

  RegisterOpt<LoopSimplify>
  X("loopsimplify", "Canonicalize natural loops", true);
}

// Publically exposed interface to pass...
const PassInfo *llvm::LoopSimplifyID = X.getPassInfo();
FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }

/// runOnFunction - Run down all loops in the CFG (recursively, but we could do
/// it in any convenient order) inserting preheaders...
///
bool LoopSimplify::runOnFunction(Function &F) {
  bool Changed = false;
  LoopInfo &LI = getAnalysis<LoopInfo>();
  AA = getAnalysisToUpdate<AliasAnalysis>();

  for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
    Changed |= ProcessLoop(*I);

  return Changed;
}


/// ProcessLoop - Walk the loop structure in depth first order, ensuring that
/// all loops have preheaders.
///
bool LoopSimplify::ProcessLoop(Loop *L) {
  bool Changed = false;

  // Check to see that no blocks (other than the header) in the loop have
  // predecessors that are not in the loop.  This is not valid for natural
  // loops, but can occur if the blocks are unreachable.  Since they are
  // unreachable we can just shamelessly destroy their terminators to make them
  // not branch into the loop!
  assert(L->getBlocks()[0] == L->getHeader() &&
         "Header isn't first block in loop?");
  for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) {
    BasicBlock *LoopBB = L->getBlocks()[i];
  Retry:
    for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB);
         PI != E; ++PI)
      if (!L->contains(*PI)) {
        // This predecessor is not in the loop.  Kill its terminator!
        BasicBlock *DeadBlock = *PI;
        for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock);
             SI != E; ++SI)
          (*SI)->removePredecessor(DeadBlock);  // Remove PHI node entries

        // Delete the dead terminator.
        if (AA) AA->deleteValue(&DeadBlock->back());
        DeadBlock->getInstList().pop_back();

        Value *RetVal = 0;
        if (LoopBB->getParent()->getReturnType() != Type::VoidTy)
          RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType());
        new ReturnInst(RetVal, DeadBlock);
        goto Retry;  // We just invalidated the pred_iterator.  Retry.
      }
  }

  // Does the loop already have a preheader?  If so, don't modify the loop...
  if (L->getLoopPreheader() == 0) {
    InsertPreheaderForLoop(L);
    NumInserted++;
    Changed = true;
  }

  // Next, check to make sure that all exit nodes of the loop only have
  // predecessors that are inside of the loop.  This check guarantees that the
  // loop preheader/header will dominate the exit blocks.  If the exit block has
  // predecessors from outside of the loop, split the edge now.
  std::vector<BasicBlock*> ExitBlocks;
  L->getExitBlocks(ExitBlocks);

  SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
  for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(),
         E = ExitBlockSet.end(); I != E; ++I) {
    BasicBlock *ExitBlock = *I;
    for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
         PI != PE; ++PI)
      if (!L->contains(*PI)) {
        RewriteLoopExitBlock(L, ExitBlock);
        NumInserted++;
        Changed = true;
        break;
      }
  }

  // If the header has more than two predecessors at this point (from the
  // preheader and from multiple backedges), we must adjust the loop.
  if (L->getNumBackEdges() != 1) {
    // If this is really a nested loop, rip it out into a child loop.
    if (Loop *NL = SeparateNestedLoop(L)) {
      ++NumNested;
      // This is a big restructuring change, reprocess the whole loop.
      ProcessLoop(NL);
      return true;
    }

    InsertUniqueBackedgeBlock(L);
    NumInserted++;
    Changed = true;
  }

  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
    Changed |= ProcessLoop(*I);
  return Changed;
}

/// SplitBlockPredecessors - Split the specified block into two blocks.  We want
/// to move the predecessors specified in the Preds list to point to the new
/// block, leaving the remaining predecessors pointing to BB.  This method
/// updates the SSA PHINode's, but no other analyses.
///
BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB,
                                                 const char *Suffix,
                                       const std::vector<BasicBlock*> &Preds) {

  // Create new basic block, insert right before the original block...
  BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB);

  // The preheader first gets an unconditional branch to the loop header...
  BranchInst *BI = new BranchInst(BB, NewBB);

  // For every PHI node in the block, insert a PHI node into NewBB where the
  // incoming values from the out of loop edges are moved to NewBB.  We have two
  // possible cases here.  If the loop is dead, we just insert dummy entries
  // into the PHI nodes for the new edge.  If the loop is not dead, we move the
  // incoming edges in BB into new PHI nodes in NewBB.
  //
  if (!Preds.empty()) {  // Is the loop not obviously dead?
    // Check to see if the values being merged into the new block need PHI
    // nodes.  If so, insert them.
    for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) {
      PHINode *PN = cast<PHINode>(I);<commit_msg>Make loop-simplify produce better loops by turning PHI nodes like X = phi [X, Y] into just Y.  This often occurs when it seperates loops that have collapsed loop headers.  This implements LoopSimplify/phi-node-simplify.ll<commit_after>//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass performs several transformations to transform natural loops into a
// simpler form, which makes subsequent analyses and transformations simpler and
// more effective.
//
// Loop pre-header insertion guarantees that there is a single, non-critical
// entry edge from outside of the loop to the loop header.  This simplifies a
// number of analyses and transformations, such as LICM.
//
// Loop exit-block insertion guarantees that all exit blocks from the loop
// (blocks which are outside of the loop that have predecessors inside of the
// loop) only have predecessors from inside of the loop (and are thus dominated
// by the loop header).  This simplifies transformations such as store-sinking
// that are built into LICM.
//
// This pass also guarantees that loops will have exactly one backedge.
//
// Note that the simplifycfg pass will clean up blocks which are split out but
// end up being unnecessary, so usage of this pass should not pessimize
// generated code.
//
// This pass obviously modifies the CFG, but updates loop information and
// dominator information.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constant.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Type.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Support/CFG.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/DepthFirstIterator.h"
using namespace llvm;

namespace {
  Statistic<>
  NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted");
  Statistic<>
  NumNested("loopsimplify", "Number of nested loops split out");

  struct LoopSimplify : public FunctionPass {
    // AA - If we have an alias analysis object to update, this is it, otherwise
    // this is null.
    AliasAnalysis *AA;

    virtual bool runOnFunction(Function &F);

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      // We need loop information to identify the loops...
      AU.addRequired<LoopInfo>();
      AU.addRequired<DominatorSet>();
      AU.addRequired<DominatorTree>();

      AU.addPreserved<LoopInfo>();
      AU.addPreserved<DominatorSet>();
      AU.addPreserved<ImmediateDominators>();
      AU.addPreserved<DominatorTree>();
      AU.addPreserved<DominanceFrontier>();
      AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
    }
  private:
    bool ProcessLoop(Loop *L);
    BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix,
                                       const std::vector<BasicBlock*> &Preds);
    BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
    void InsertPreheaderForLoop(Loop *L);
    Loop *SeparateNestedLoop(Loop *L);
    void InsertUniqueBackedgeBlock(Loop *L);

    void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
                                         std::vector<BasicBlock*> &PredBlocks);
  };

  RegisterOpt<LoopSimplify>
  X("loopsimplify", "Canonicalize natural loops", true);
}

// Publically exposed interface to pass...
const PassInfo *llvm::LoopSimplifyID = X.getPassInfo();
FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }

/// runOnFunction - Run down all loops in the CFG (recursively, but we could do
/// it in any convenient order) inserting preheaders...
///
bool LoopSimplify::runOnFunction(Function &F) {
  bool Changed = false;
  LoopInfo &LI = getAnalysis<LoopInfo>();
  AA = getAnalysisToUpdate<AliasAnalysis>();

  for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
    Changed |= ProcessLoop(*I);

  return Changed;
}


/// ProcessLoop - Walk the loop structure in depth first order, ensuring that
/// all loops have preheaders.
///
bool LoopSimplify::ProcessLoop(Loop *L) {
  bool Changed = false;

  // Check to see that no blocks (other than the header) in the loop have
  // predecessors that are not in the loop.  This is not valid for natural
  // loops, but can occur if the blocks are unreachable.  Since they are
  // unreachable we can just shamelessly destroy their terminators to make them
  // not branch into the loop!
  assert(L->getBlocks()[0] == L->getHeader() &&
         "Header isn't first block in loop?");
  for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) {
    BasicBlock *LoopBB = L->getBlocks()[i];
  Retry:
    for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB);
         PI != E; ++PI)
      if (!L->contains(*PI)) {
        // This predecessor is not in the loop.  Kill its terminator!
        BasicBlock *DeadBlock = *PI;
        for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock);
             SI != E; ++SI)
          (*SI)->removePredecessor(DeadBlock);  // Remove PHI node entries

        // Delete the dead terminator.
        if (AA) AA->deleteValue(&DeadBlock->back());
        DeadBlock->getInstList().pop_back();

        Value *RetVal = 0;
        if (LoopBB->getParent()->getReturnType() != Type::VoidTy)
          RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType());
        new ReturnInst(RetVal, DeadBlock);
        goto Retry;  // We just invalidated the pred_iterator.  Retry.
      }
  }

  // Does the loop already have a preheader?  If so, don't modify the loop...
  if (L->getLoopPreheader() == 0) {
    InsertPreheaderForLoop(L);
    NumInserted++;
    Changed = true;
  }

  // Next, check to make sure that all exit nodes of the loop only have
  // predecessors that are inside of the loop.  This check guarantees that the
  // loop preheader/header will dominate the exit blocks.  If the exit block has
  // predecessors from outside of the loop, split the edge now.
  std::vector<BasicBlock*> ExitBlocks;
  L->getExitBlocks(ExitBlocks);

  SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
  for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(),
         E = ExitBlockSet.end(); I != E; ++I) {
    BasicBlock *ExitBlock = *I;
    for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
         PI != PE; ++PI)
      if (!L->contains(*PI)) {
        RewriteLoopExitBlock(L, ExitBlock);
        NumInserted++;
        Changed = true;
        break;
      }
  }

  // If the header has more than two predecessors at this point (from the
  // preheader and from multiple backedges), we must adjust the loop.
  if (L->getNumBackEdges() != 1) {
    // If this is really a nested loop, rip it out into a child loop.
    if (Loop *NL = SeparateNestedLoop(L)) {
      ++NumNested;
      // This is a big restructuring change, reprocess the whole loop.
      ProcessLoop(NL);
      return true;
    }

    InsertUniqueBackedgeBlock(L);
    NumInserted++;
    Changed = true;
  }

  // Scan over the PHI nodes in the loop header.  Since they now have only two
  // incoming values (the loop is canonicalized), we may have simplified the PHI
  // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
  PHINode *PN;
  DominatorSet &DS = getAnalysis<DominatorSet>();
  for (BasicBlock::iterator I = L->getHeader()->begin();
       (PN = dyn_cast<PHINode>(I++)); )
    if (Value *V = PN->hasConstantValue(true))
      if (!isa<Instruction>(V) ||
          DS.dominates(cast<Instruction>(V)->getParent(), L->getHeader())) {
        PN->replaceAllUsesWith(V);
        PN->eraseFromParent();
      }

  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
    Changed |= ProcessLoop(*I);

  return Changed;
}

/// SplitBlockPredecessors - Split the specified block into two blocks.  We want
/// to move the predecessors specified in the Preds list to point to the new
/// block, leaving the remaining predecessors pointing to BB.  This method
/// updates the SSA PHINode's, but no other analyses.
///
BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB,
                                                 const char *Suffix,
                                       const std::vector<BasicBlock*> &Preds) {

  // Create new basic block, insert right before the original block...
  BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB);

  // The preheader first gets an unconditional branch to the loop header...
  BranchInst *BI = new BranchInst(BB, NewBB);

  // For every PHI node in the block, insert a PHI node into NewBB where the
  // incoming values from the out of loop edges are moved to NewBB.  We have two
  // possible cases here.  If the loop is dead, we just insert dummy entries
  // into the PHI nodes for the new edge.  If the loop is not dead, we move the
  // incoming edges in BB into new PHI nodes in NewBB.
  //
  if (!Preds.empty()) {  // Is the loop not obviously dead?
    // Check to see if the values being merged into the new block need PHI
    // nodes.  If so, insert them.
    for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) {
      PHINode *PN = cast<PHINode>(I);
{'fraction_non_alphanumeric': 0.13046525419160063, 'fraction_numerical': 0.0005391126206264489, 'mean_word_length': 2.8493463374144015, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 100, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4316485', 'n_tokens_mistral': 5384, 'n_tokens_neox': 5158, 'n_words': 1922}