<commit_before>//===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass transforms loops that contain branches on loop-invariant conditions
// to have multiple loops.  For example, it turns the left into the right code:
//
//  for (...)                  if (lic)
//    A                          for (...)
//    if (lic)                     A; B; C
//      B                      else
//    C                          for (...)
//                                 A; C
//
// This can increase the size of the code exponentially (doubling it every time
// a loop is unswitched) so we only unswitch if the resultant code will be
// smaller than a threshold.
//
// This pass expects LICM to be run before it to hoist invariant conditions out
// of the loop, to make the unswitching opportunity obvious.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <map>
#include <set>
using namespace llvm;

#define DEBUG_TYPE "loop-unswitch"

STATISTIC(NumBranches, "Number of branches unswitched");
STATISTIC(NumSwitches, "Number of switches unswitched");
STATISTIC(NumSelects , "Number of selects unswitched");
STATISTIC(NumTrivial , "Number of unswitches that are trivial");
STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
STATISTIC(TotalInsts,  "Total number of instructions analyzed");

// The specific value of 100 here was chosen based only on intuition and a
// few specific examples.
static cl::opt<unsigned>
Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
          cl::init(100), cl::Hidden);

namespace {

  class LUAnalysisCache {

    typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> >
      UnswitchedValsMap;

    typedef UnswitchedValsMap::iterator UnswitchedValsIt;

    struct LoopProperties {
      unsigned CanBeUnswitchedCount;
      unsigned WasUnswitchedCount;
      unsigned SizeEstimation;
      UnswitchedValsMap UnswitchedVals;
    };

    // Here we use std::map instead of DenseMap, since we need to keep valid
    // LoopProperties pointer for current loop for better performance.
    typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
    typedef LoopPropsMap::iterator LoopPropsMapIt;

    LoopPropsMap LoopsProperties;
    UnswitchedValsMap *CurLoopInstructions;
    LoopProperties *CurrentLoopProperties;

    // A loop unswitching with an estimated cost above this threshold
    // is not performed. MaxSize is turned into unswitching quota for
    // the current loop, and reduced correspondingly, though note that
    // the quota is returned by releaseMemory() when the loop has been
    // processed, so that MaxSize will return to its previous
    // value. So in most cases MaxSize will equal the Threshold flag
    // when a new loop is processed. An exception to that is that
    // MaxSize will have a smaller value while processing nested loops
    // that were introduced due to loop unswitching of an outer loop.
    //
    // FIXME: The way that MaxSize works is subtle and depends on the
    // pass manager processing loops and calling releaseMemory() in a
    // specific order. It would be good to find a more straightforward
    // way of doing what MaxSize does.
    unsigned MaxSize;

  public:
    LUAnalysisCache()
        : CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr),
          MaxSize(Threshold) {}

    // Analyze loop. Check its size, calculate is it possible to unswitch
    // it. Returns true if we can unswitch this loop.
    bool countLoop(const Loop *L, const TargetTransformInfo &TTI,
                   AssumptionCache *AC);

    // Clean all data related to given loop.
    void forgetLoop(const Loop *L);

    // Mark case value as unswitched.
    // Since SI instruction can be partly unswitched, in order to avoid
    // extra unswitching in cloned loops keep track all unswitched values.
    void setUnswitched(const SwitchInst *SI, const Value *V);

    // Check was this case value unswitched before or not.
    bool isUnswitched(const SwitchInst *SI, const Value *V);

    // Returns true if another unswitching could be done within the cost
    // threshold.
    bool CostAllowsUnswitching();

    // Clone all loop-unswitch related loop properties.
    // Redistribute unswitching quotas.
    // Note, that new loop data is stored inside the VMap.
    void cloneData(const Loop *NewLoop, const Loop *OldLoop,
                   const ValueToValueMapTy &VMap);
  };

  class LoopUnswitch : public LoopPass {
    LoopInfo *LI;  // Loop information
    LPPassManager *LPM;
    AssumptionCache *AC;

    // Used to check if second loop needs processing after
    // RewriteLoopBodyWithConditionConstant rewrites first loop.
    std::vector<Loop*> LoopProcessWorklist;

    LUAnalysisCache BranchesInfo;

    bool OptimizeForSize;
    bool redoLoop;

    Loop *currentLoop;
    DominatorTree *DT;
    BasicBlock *loopHeader;
    BasicBlock *loopPreheader;

    // LoopBlocks contains all of the basic blocks of the loop, including the
    // preheader of the loop, the body of the loop, and the exit blocks of the
    // loop, in that order.
    std::vector<BasicBlock*> LoopBlocks;
    // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
    std::vector<BasicBlock*> NewBlocks;

  public:
    static char ID; // Pass ID, replacement for typeid
    explicit LoopUnswitch(bool Os = false) :
      LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
      currentLoop(nullptr), DT(nullptr), loopHeader(nullptr),
      loopPreheader(nullptr) {
        initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
      }

    bool runOnLoop(Loop *L, LPPassManager &LPM) override;
    bool processCurrentLoop();

    /// This transformation requires natural loop information & requires that
    /// loop preheaders be inserted into the CFG.
    ///
    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.addRequired<AssumptionCacheTracker>();
      AU.addRequiredID(LoopSimplifyID);
      AU.addPreservedID(LoopSimplifyID);
      AU.addRequired<LoopInfoWrapperPass>();
      AU.addPreserved<LoopInfoWrapperPass>();
      AU.addRequiredID(LCSSAID);
      AU.addPreservedID(LCSSAID);
      AU.addPreserved<DominatorTreeWrapperPass>();
      AU.addPreserved<ScalarEvolutionWrapperPass>();
      AU.addRequired<TargetTransformInfoWrapperPass>();
      AU.addPreserved<GlobalsAAWrapperPass>();
    }

  private:

    void releaseMemory() override {
      BranchesInfo.forgetLoop(currentLoop);
    }

    void initLoopData() {
      loopHeader = currentLoop->getHeader();
      loopPreheader = currentLoop->getLoopPreheader();
    }

    /// Split all of the edges from inside the loop to their exit blocks.
    /// Update the appropriate Phi nodes as we do so.
    void SplitExitEdges(Loop *L,
                        const SmallVectorImpl<BasicBlock *> &ExitBlocks);

    bool TryTrivialLoopUnswitch(bool &Changed);

    bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,
                              TerminatorInst *TI = nullptr);
    void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
                                  BasicBlock *ExitBlock, TerminatorInst *TI);
    void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,
                                     TerminatorInst *TI);

    void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
                                              Constant *Val, bool isEqual);

    void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
                                        BasicBlock *TrueDest,
                                        BasicBlock *FalseDest,
                                        Instruction *InsertPt,
                                        TerminatorInst *TI);

    void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
  };
}

// Analyze loop. Check its size, calculate is it possible to unswitch
// it. Returns true if we can unswitch this loop.
bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
                                AssumptionCache *AC) {

  LoopPropsMapIt PropsIt;
  bool Inserted;
  std::tie(PropsIt, Inserted) =
      LoopsProperties.insert(std::make_pair(L, LoopProperties()));

  LoopProperties &Props = PropsIt->second;

  if (Inserted) {
    // New loop.

    // Limit the number of instructions to avoid causing significant code
    // expansion, and the number of basic blocks, to avoid loops with
    // large numbers of branches which cause loop unswitching to go crazy.
    // This is a very ad-hoc heuristic.

    SmallPtrSet<const Value *, 32> EphValues;
    CodeMetrics::collectEphemeralValues(L, AC, EphValues);

    // FIXME: This is overly conservative because it does not take into
    // consideration code simplification opportunities and code that can
    // be shared by the resultant unswitched loops.
    CodeMetrics Metrics;
    for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
         ++I)
      Metrics.analyzeBasicBlock(*I, TTI, EphValues);

    Props.SizeEstimation = Metrics.NumInsts;
    Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
    Props.WasUnswitchedCount = 0;
    MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;

    if (Metrics.notDuplicatable) {
      DEBUG(dbgs() << "NOT unswitching loop %"
                   << L->getHeader()->getName() << ", contents cannot be "
                   << "duplicated!\n");
      return false;
    }
  }

  // Be careful. This links are good only before new loop addition.
  CurrentLoopProperties = &Props;
  CurLoopInstructions = &Props.UnswitchedVals;

  return true;
}

// Clean all data related to given loop.
void LUAnalysisCache::forgetLoop(const Loop *L) {

  LoopPropsMapIt LIt = LoopsProperties.find(L);

  if (LIt != LoopsProperties.end()) {
    LoopProperties &Props = LIt->second;
    MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) *
               Props.SizeEstimation;
    LoopsProperties.erase(LIt);
  }

  CurrentLoopProperties = nullptr;
  CurLoopInstructions = nullptr;
}

// Mark case value as unswitched.
// Since SI instruction can be partly unswitched, in order to avoid
// extra unswitching in cloned loops keep track all unswitched values.
void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
  (*CurLoopInstructions)[SI].insert(V);
}

// Check was this case value unswitched before or not.
bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
  return (*CurLoopInstructions)[SI].count(V);
}

bool LUAnalysisCache::CostAllowsUnswitching() {
  return CurrentLoopProperties->CanBeUnswitchedCount > 0;
}

// Clone all loop-unswitch related loop properties.
// Redistribute unswitching quotas.
// Note, that new loop data is stored inside the VMap.
void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
                                const ValueToValueMapTy &VMap) {

  LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
  LoopProperties &OldLoopProps = *CurrentLoopProperties;
  UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;

  // Reallocate "can-be-unswitched quota"

  --OldLoopProps.CanBeUnswitchedCount;
  ++OldLoopProps.WasUnswitchedCount;
  NewLoopProps.WasUnswitchedCount = 0;
  unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
  NewLoopProps.CanBeUnswitchedCount = Quota / 2;
  OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;

  NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;

  // Clone unswitched values info:
  // for new loop switches we clone info about values that was
  // already unswitched and has redundant successors.
  for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
    const SwitchInst *OldInst = I->first;
    Value *NewI = VMap.lookup(OldInst);
    const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
    assert(NewInst && "All instructions that are in SrcBB must be in VMap.");

    NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
  }
}

char LoopUnswitch::ID = 0;
INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                      false, false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                      false, false)

Pass *llvm::createLoopUnswitchPass(bool Os) {
  return new LoopUnswitch(Os);
}

/// Cond is a condition that occurs in L. If it is invariant in the loop, or has
/// an invariant piece, return the invariant. Otherwise, return null.
static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {

  // We started analyze new instruction, increment scanned instructions counter.
  ++TotalInsts;

  // We can never unswitch on vector conditions.
  if (Cond->getType()->isVectorTy())
    return nullptr;

  // Constants should be folded, not unswitched on!
  if (isa<Constant>(Cond)) return nullptr;

  // TODO: Handle: br (VARIANT|INVARIANT).

  // Hoist simple values out.
  if (L->makeLoopInvariant(Cond, Changed))
    return Cond;

  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
    if (BO->getOpcode() == Instruction::And ||
        BO->getOpcode() == Instruction::Or) {
      // If either the left or right side is invariant, we can unswitch on this,
      // which will cause the branch to go away in one loop and the condition to
      // simplify in the other one.
      if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed))
        return LHS;
      if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed))
        return RHS;
    }

  return nullptr;
}

bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
  if (skipOptnoneFunction(L))
    return false;

  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
      *L->getHeader()->getParent());
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  LPM = &LPM_Ref;
  DominatorTreeWrapperPass *DTWP =
      getAnalysisIfAvailable<DominatorTreeWrapperPass>();
  DT = DTWP ? &DTWP->getDomTree() : nullptr;
  currentLoop = L;
  Function *F = currentLoop->getHeader()->getParent();
  bool Changed = false;
  do {
    assert(currentLoop->isLCSSAForm(*DT));
    redoLoop = false;
    Changed |= processCurrentLoop();
  } while(redoLoop);

  if (Changed) {
    // FIXME: Reconstruct dom info, because it is not preserved properly.
    if (DT)
      DT->recalculate(*F);
  }
  return Changed;
}

/// Do actual work and unswitch loop if possible and profitable.
bool LoopUnswitch::processCurrentLoop() {
  bool Changed = false;

  initLoopData();

  // If LoopSimplify was unable to form a preheader, don't do any unswitching.
  if (!loopPreheader)
    return false;

  // Loops with indirectbr cannot be cloned.
  if (!currentLoop->isSafeToClone())
    return false;

  // Without dedicated exits, splitting the exit edge may fail.
  if (!currentLoop->hasDedicatedExits())
    return false;

  LLVMContext &Context = loopHeader->getContext();<commit_msg>Fix UB: can't bind a reference to nullptr (NFC)<commit_after>//===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass transforms loops that contain branches on loop-invariant conditions
// to have multiple loops.  For example, it turns the left into the right code:
//
//  for (...)                  if (lic)
//    A                          for (...)
//    if (lic)                     A; B; C
//      B                      else
//    C                          for (...)
//                                 A; C
//
// This can increase the size of the code exponentially (doubling it every time
// a loop is unswitched) so we only unswitch if the resultant code will be
// smaller than a threshold.
//
// This pass expects LICM to be run before it to hoist invariant conditions out
// of the loop, to make the unswitching opportunity obvious.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <map>
#include <set>
using namespace llvm;

#define DEBUG_TYPE "loop-unswitch"

STATISTIC(NumBranches, "Number of branches unswitched");
STATISTIC(NumSwitches, "Number of switches unswitched");
STATISTIC(NumSelects , "Number of selects unswitched");
STATISTIC(NumTrivial , "Number of unswitches that are trivial");
STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
STATISTIC(TotalInsts,  "Total number of instructions analyzed");

// The specific value of 100 here was chosen based only on intuition and a
// few specific examples.
static cl::opt<unsigned>
Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
          cl::init(100), cl::Hidden);

namespace {

  class LUAnalysisCache {

    typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> >
      UnswitchedValsMap;

    typedef UnswitchedValsMap::iterator UnswitchedValsIt;

    struct LoopProperties {
      unsigned CanBeUnswitchedCount;
      unsigned WasUnswitchedCount;
      unsigned SizeEstimation;
      UnswitchedValsMap UnswitchedVals;
    };

    // Here we use std::map instead of DenseMap, since we need to keep valid
    // LoopProperties pointer for current loop for better performance.
    typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
    typedef LoopPropsMap::iterator LoopPropsMapIt;

    LoopPropsMap LoopsProperties;
    UnswitchedValsMap *CurLoopInstructions;
    LoopProperties *CurrentLoopProperties;

    // A loop unswitching with an estimated cost above this threshold
    // is not performed. MaxSize is turned into unswitching quota for
    // the current loop, and reduced correspondingly, though note that
    // the quota is returned by releaseMemory() when the loop has been
    // processed, so that MaxSize will return to its previous
    // value. So in most cases MaxSize will equal the Threshold flag
    // when a new loop is processed. An exception to that is that
    // MaxSize will have a smaller value while processing nested loops
    // that were introduced due to loop unswitching of an outer loop.
    //
    // FIXME: The way that MaxSize works is subtle and depends on the
    // pass manager processing loops and calling releaseMemory() in a
    // specific order. It would be good to find a more straightforward
    // way of doing what MaxSize does.
    unsigned MaxSize;

  public:
    LUAnalysisCache()
        : CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr),
          MaxSize(Threshold) {}

    // Analyze loop. Check its size, calculate is it possible to unswitch
    // it. Returns true if we can unswitch this loop.
    bool countLoop(const Loop *L, const TargetTransformInfo &TTI,
                   AssumptionCache *AC);

    // Clean all data related to given loop.
    void forgetLoop(const Loop *L);

    // Mark case value as unswitched.
    // Since SI instruction can be partly unswitched, in order to avoid
    // extra unswitching in cloned loops keep track all unswitched values.
    void setUnswitched(const SwitchInst *SI, const Value *V);

    // Check was this case value unswitched before or not.
    bool isUnswitched(const SwitchInst *SI, const Value *V);

    // Returns true if another unswitching could be done within the cost
    // threshold.
    bool CostAllowsUnswitching();

    // Clone all loop-unswitch related loop properties.
    // Redistribute unswitching quotas.
    // Note, that new loop data is stored inside the VMap.
    void cloneData(const Loop *NewLoop, const Loop *OldLoop,
                   const ValueToValueMapTy &VMap);
  };

  class LoopUnswitch : public LoopPass {
    LoopInfo *LI;  // Loop information
    LPPassManager *LPM;
    AssumptionCache *AC;

    // Used to check if second loop needs processing after
    // RewriteLoopBodyWithConditionConstant rewrites first loop.
    std::vector<Loop*> LoopProcessWorklist;

    LUAnalysisCache BranchesInfo;

    bool OptimizeForSize;
    bool redoLoop;

    Loop *currentLoop;
    DominatorTree *DT;
    BasicBlock *loopHeader;
    BasicBlock *loopPreheader;

    // LoopBlocks contains all of the basic blocks of the loop, including the
    // preheader of the loop, the body of the loop, and the exit blocks of the
    // loop, in that order.
    std::vector<BasicBlock*> LoopBlocks;
    // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
    std::vector<BasicBlock*> NewBlocks;

  public:
    static char ID; // Pass ID, replacement for typeid
    explicit LoopUnswitch(bool Os = false) :
      LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
      currentLoop(nullptr), DT(nullptr), loopHeader(nullptr),
      loopPreheader(nullptr) {
        initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
      }

    bool runOnLoop(Loop *L, LPPassManager &LPM) override;
    bool processCurrentLoop();

    /// This transformation requires natural loop information & requires that
    /// loop preheaders be inserted into the CFG.
    ///
    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.addRequired<AssumptionCacheTracker>();
      AU.addRequiredID(LoopSimplifyID);
      AU.addPreservedID(LoopSimplifyID);
      AU.addRequired<LoopInfoWrapperPass>();
      AU.addPreserved<LoopInfoWrapperPass>();
      AU.addRequiredID(LCSSAID);
      AU.addPreservedID(LCSSAID);
      AU.addPreserved<DominatorTreeWrapperPass>();
      AU.addPreserved<ScalarEvolutionWrapperPass>();
      AU.addRequired<TargetTransformInfoWrapperPass>();
      AU.addPreserved<GlobalsAAWrapperPass>();
    }

  private:

    void releaseMemory() override {
      BranchesInfo.forgetLoop(currentLoop);
    }

    void initLoopData() {
      loopHeader = currentLoop->getHeader();
      loopPreheader = currentLoop->getLoopPreheader();
    }

    /// Split all of the edges from inside the loop to their exit blocks.
    /// Update the appropriate Phi nodes as we do so.
    void SplitExitEdges(Loop *L,
                        const SmallVectorImpl<BasicBlock *> &ExitBlocks);

    bool TryTrivialLoopUnswitch(bool &Changed);

    bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,
                              TerminatorInst *TI = nullptr);
    void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
                                  BasicBlock *ExitBlock, TerminatorInst *TI);
    void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,
                                     TerminatorInst *TI);

    void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
                                              Constant *Val, bool isEqual);

    void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
                                        BasicBlock *TrueDest,
                                        BasicBlock *FalseDest,
                                        Instruction *InsertPt,
                                        TerminatorInst *TI);

    void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
  };
}

// Analyze loop. Check its size, calculate is it possible to unswitch
// it. Returns true if we can unswitch this loop.
bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
                                AssumptionCache *AC) {

  LoopPropsMapIt PropsIt;
  bool Inserted;
  std::tie(PropsIt, Inserted) =
      LoopsProperties.insert(std::make_pair(L, LoopProperties()));

  LoopProperties &Props = PropsIt->second;

  if (Inserted) {
    // New loop.

    // Limit the number of instructions to avoid causing significant code
    // expansion, and the number of basic blocks, to avoid loops with
    // large numbers of branches which cause loop unswitching to go crazy.
    // This is a very ad-hoc heuristic.

    SmallPtrSet<const Value *, 32> EphValues;
    CodeMetrics::collectEphemeralValues(L, AC, EphValues);

    // FIXME: This is overly conservative because it does not take into
    // consideration code simplification opportunities and code that can
    // be shared by the resultant unswitched loops.
    CodeMetrics Metrics;
    for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
         ++I)
      Metrics.analyzeBasicBlock(*I, TTI, EphValues);

    Props.SizeEstimation = Metrics.NumInsts;
    Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
    Props.WasUnswitchedCount = 0;
    MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;

    if (Metrics.notDuplicatable) {
      DEBUG(dbgs() << "NOT unswitching loop %"
                   << L->getHeader()->getName() << ", contents cannot be "
                   << "duplicated!\n");
      return false;
    }
  }

  // Be careful. This links are good only before new loop addition.
  CurrentLoopProperties = &Props;
  CurLoopInstructions = &Props.UnswitchedVals;

  return true;
}

// Clean all data related to given loop.
void LUAnalysisCache::forgetLoop(const Loop *L) {

  LoopPropsMapIt LIt = LoopsProperties.find(L);

  if (LIt != LoopsProperties.end()) {
    LoopProperties &Props = LIt->second;
    MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) *
               Props.SizeEstimation;
    LoopsProperties.erase(LIt);
  }

  CurrentLoopProperties = nullptr;
  CurLoopInstructions = nullptr;
}

// Mark case value as unswitched.
// Since SI instruction can be partly unswitched, in order to avoid
// extra unswitching in cloned loops keep track all unswitched values.
void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
  (*CurLoopInstructions)[SI].insert(V);
}

// Check was this case value unswitched before or not.
bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
  return (*CurLoopInstructions)[SI].count(V);
}

bool LUAnalysisCache::CostAllowsUnswitching() {
  return CurrentLoopProperties->CanBeUnswitchedCount > 0;
}

// Clone all loop-unswitch related loop properties.
// Redistribute unswitching quotas.
// Note, that new loop data is stored inside the VMap.
void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
                                const ValueToValueMapTy &VMap) {

  LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
  LoopProperties &OldLoopProps = *CurrentLoopProperties;
  UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;

  // Reallocate "can-be-unswitched quota"

  --OldLoopProps.CanBeUnswitchedCount;
  ++OldLoopProps.WasUnswitchedCount;
  NewLoopProps.WasUnswitchedCount = 0;
  unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
  NewLoopProps.CanBeUnswitchedCount = Quota / 2;
  OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;

  NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;

  // Clone unswitched values info:
  // for new loop switches we clone info about values that was
  // already unswitched and has redundant successors.
  for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
    const SwitchInst *OldInst = I->first;
    Value *NewI = VMap.lookup(OldInst);
    const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
    assert(NewInst && "All instructions that are in SrcBB must be in VMap.");

    NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
  }
}

char LoopUnswitch::ID = 0;
INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                      false, false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                      false, false)

Pass *llvm::createLoopUnswitchPass(bool Os) {
  return new LoopUnswitch(Os);
}

/// Cond is a condition that occurs in L. If it is invariant in the loop, or has
/// an invariant piece, return the invariant. Otherwise, return null.
static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {

  // We started analyze new instruction, increment scanned instructions counter.
  ++TotalInsts;

  // We can never unswitch on vector conditions.
  if (Cond->getType()->isVectorTy())
    return nullptr;

  // Constants should be folded, not unswitched on!
  if (isa<Constant>(Cond)) return nullptr;

  // TODO: Handle: br (VARIANT|INVARIANT).

  // Hoist simple values out.
  if (L->makeLoopInvariant(Cond, Changed))
    return Cond;

  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond))
    if (BO->getOpcode() == Instruction::And ||
        BO->getOpcode() == Instruction::Or) {
      // If either the left or right side is invariant, we can unswitch on this,
      // which will cause the branch to go away in one loop and the condition to
      // simplify in the other one.
      if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed))
        return LHS;
      if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed))
        return RHS;
    }

  return nullptr;
}

bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
  if (skipOptnoneFunction(L))
    return false;

  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
      *L->getHeader()->getParent());
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  LPM = &LPM_Ref;
  DominatorTreeWrapperPass *DTWP =
      getAnalysisIfAvailable<DominatorTreeWrapperPass>();
  DT = DTWP ? &DTWP->getDomTree() : nullptr;
  currentLoop = L;
  Function *F = currentLoop->getHeader()->getParent();
  bool Changed = false;
  do {
    assert(!DT || currentLoop->isLCSSAForm(*DT));
    redoLoop = false;
    Changed |= processCurrentLoop();
  } while(redoLoop);

  if (Changed) {
    // FIXME: Reconstruct dom info, because it is not preserved properly.
    if (DT)
      DT->recalculate(*F);
  }
  return Changed;
}

/// Do actual work and unswitch loop if possible and profitable.
bool LoopUnswitch::processCurrentLoop() {
  bool Changed = false;

  initLoopData();

  // If LoopSimplify was unable to form a preheader, don't do any unswitching.
  if (!loopPreheader)
    return false;

  // Loops with indirectbr cannot be cloned.
  if (!currentLoop->isSafeToClone())
    return false;

  // Without dedicated exits, splitting the exit edge may fail.
  if (!currentLoop->hasDedicatedExits())
    return false;

  LLVMContext &Context = loopHeader->getContext();
{'fraction_non_alphanumeric': 0.10530933292996521, 'fraction_numerical': 0.0010285887157767358, 'mean_word_length': 3.0774639200690763, 'pattern_counts': {'":': 0, '<': 71, '<?xml version=': 0, '>': 111, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5380630', 'n_tokens_mistral': 9684, 'n_tokens_neox': 9287, 'n_words': 2928}