<commit_before>//===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the Loop SimplifyCFG Pass. This pass is responsible for
// basic loop CFG cleanup, primarily to assist other loop passes. If you
// encounter a noncanonical CFG construct that causes another loop pass to
// perform suboptimally, this is the place to fix it up.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
using namespace llvm;

#define DEBUG_TYPE "loop-simplifycfg"

static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
                                       cl::init(true));

STATISTIC(NumTerminatorsFolded,
          "Number of terminators folded to unconditional branches");
STATISTIC(NumLoopBlocksDeleted,
          "Number of loop blocks deleted");
STATISTIC(NumLoopExitsDeleted,
          "Number of loop exiting edges deleted");

/// If \p BB is a switch or a conditional branch, but only one of its successors
/// can be reached from this block in runtime, return this successor. Otherwise,
/// return nullptr.
static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
  Instruction *TI = BB->getTerminator();
  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
    if (BI->isUnconditional())
      return nullptr;
    if (BI->getSuccessor(0) == BI->getSuccessor(1))
      return BI->getSuccessor(0);
    ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
    if (!Cond)
      return nullptr;
    return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
  }

  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
    auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
    if (!CI)
      return nullptr;
    for (auto Case : SI->cases())
      if (Case.getCaseValue() == CI)
        return Case.getCaseSuccessor();
    return SI->getDefaultDest();
  }

  return nullptr;
}

/// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
                                 Loop *LastLoop = nullptr) {
  assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
         "First loop is supposed to be inside of last loop!");
  assert(FirstLoop->contains(BB) && "Must be a loop block!");
  for (Loop *Current = FirstLoop; Current != LastLoop;
       Current = Current->getParentLoop())
    Current->removeBlockFromLoop(BB);
}

/// Find innermost loop that contains at least one block from \p BBs and
/// contains the header of loop \p L.
static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs,
                                 Loop &L, LoopInfo &LI) {
  Loop *StillReachable = nullptr;
  for (BasicBlock *BB : BBs) {
    Loop *BBL = LI.getLoopFor(BB);
    if (BBL && BBL->contains(L.getHeader()))
      if (!StillReachable ||
          BBL->getLoopDepth() > StillReachable->getLoopDepth())
        StillReachable = BBL;
  }
  return StillReachable;
}

namespace {
/// Helper class that can turn branches and switches with constant conditions
/// into unconditional branches.
class ConstantTerminatorFoldingImpl {
private:
  Loop &L;
  LoopInfo &LI;
  DominatorTree &DT;
  ScalarEvolution &SE;
  MemorySSAUpdater *MSSAU;
  LoopBlocksDFS DFS;
  DomTreeUpdater DTU;
  SmallVector<DominatorTree::UpdateType, 16> DTUpdates;

  // Whether or not the current loop has irreducible CFG.
  bool HasIrreducibleCFG = false;<commit_msg>[NFC] Teach getInnermostLoopFor walk up the loop trees<commit_after>//===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the Loop SimplifyCFG Pass. This pass is responsible for
// basic loop CFG cleanup, primarily to assist other loop passes. If you
// encounter a noncanonical CFG construct that causes another loop pass to
// perform suboptimally, this is the place to fix it up.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
using namespace llvm;

#define DEBUG_TYPE "loop-simplifycfg"

static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
                                       cl::init(true));

STATISTIC(NumTerminatorsFolded,
          "Number of terminators folded to unconditional branches");
STATISTIC(NumLoopBlocksDeleted,
          "Number of loop blocks deleted");
STATISTIC(NumLoopExitsDeleted,
          "Number of loop exiting edges deleted");

/// If \p BB is a switch or a conditional branch, but only one of its successors
/// can be reached from this block in runtime, return this successor. Otherwise,
/// return nullptr.
static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
  Instruction *TI = BB->getTerminator();
  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
    if (BI->isUnconditional())
      return nullptr;
    if (BI->getSuccessor(0) == BI->getSuccessor(1))
      return BI->getSuccessor(0);
    ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
    if (!Cond)
      return nullptr;
    return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
  }

  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
    auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
    if (!CI)
      return nullptr;
    for (auto Case : SI->cases())
      if (Case.getCaseValue() == CI)
        return Case.getCaseSuccessor();
    return SI->getDefaultDest();
  }

  return nullptr;
}

/// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
                                 Loop *LastLoop = nullptr) {
  assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
         "First loop is supposed to be inside of last loop!");
  assert(FirstLoop->contains(BB) && "Must be a loop block!");
  for (Loop *Current = FirstLoop; Current != LastLoop;
       Current = Current->getParentLoop())
    Current->removeBlockFromLoop(BB);
}

/// Find innermost loop that contains at least one block from \p BBs and
/// contains the header of loop \p L.
static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs,
                                 Loop &L, LoopInfo &LI) {
  Loop *Innermost = nullptr;
  for (BasicBlock *BB : BBs) {
    Loop *BBL = LI.getLoopFor(BB);
    while (BBL && !BBL->contains(L.getHeader()))
      BBL = BBL->getParentLoop();
    if (BBL == &L)
      BBL = BBL->getParentLoop();
    if (!BBL)
      continue;
    if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
      Innermost = BBL;
  }
  return Innermost;
}

namespace {
/// Helper class that can turn branches and switches with constant conditions
/// into unconditional branches.
class ConstantTerminatorFoldingImpl {
private:
  Loop &L;
  LoopInfo &LI;
  DominatorTree &DT;
  ScalarEvolution &SE;
  MemorySSAUpdater *MSSAU;
  LoopBlocksDFS DFS;
  DomTreeUpdater DTU;
  SmallVector<DominatorTree::UpdateType, 16> DTUpdates;

  // Whether or not the current loop has irreducible CFG.
  bool HasIrreducibleCFG = false;
{'fraction_non_alphanumeric': 0.15557657941763903, 'fraction_numerical': 0.0023126248291811206, 'mean_word_length': 3.222814025743453, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 61, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6707425', 'n_tokens_mistral': 2927, 'n_tokens_neox': 2839, 'n_words': 774}