llvm/llvm/lib/Transforms/Utils/LCSSA.cpp

//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
//
// 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 pass transforms loops by placing phi nodes at the end of the loops for
// all values that are live across the loop boundary.  For example, it turns
// the left into the right code:
//
// for (...)                for (...)
//   if (c)                   if (c)
//     X1 = ...                 X1 = ...
//   else                     else
//     X2 = ...                 X2 = ...
//   X3 = phi(X1, X2)         X3 = phi(X1, X2)
// ... = X3 + 4             X4 = phi(X3)
//                          ... = X4 + 4
//
// This is still valid LLVM; the extra phi nodes are purely redundant, and will
// be trivially eliminated by InstCombine.  The major benefit of this
// transformation is that it makes many other loop optimizations, such as
// LoopUnswitching, simpler.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/LCSSA.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumLCSSA, "Number of live out of a loop variables");

#ifdef EXPENSIVE_CHECKS
static bool VerifyLoopLCSSA = true;
#else
static bool VerifyLoopLCSSA = …;
#endif
static cl::opt<bool, true>
    VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA),
                        cl::Hidden,
                        cl::desc("Verify loop lcssa form (time consuming)"));

/// Return true if the specified block is in the list.
static bool isExitBlock(BasicBlock *BB,
                        const SmallVectorImpl<BasicBlock *> &ExitBlocks) { … }

// Cache the Loop ExitBlocks computed during the analysis.  We expect to get a
// lot of instructions within the same loops, computing the exit blocks is
// expensive, and we're not mutating the loop structure.
LoopExitBlocksTy;

/// For every instruction from the worklist, check to see if it has any uses
/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
/// rewrite the uses.
static bool
formLCSSAForInstructionsImpl(SmallVectorImpl<Instruction *> &Worklist,
                             const DominatorTree &DT, const LoopInfo &LI,
                             ScalarEvolution *SE,
                             SmallVectorImpl<PHINode *> *PHIsToRemove,
                             SmallVectorImpl<PHINode *> *InsertedPHIs,
                             LoopExitBlocksTy &LoopExitBlocks) { … }

/// For every instruction from the worklist, check to see if it has any uses
/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
/// rewrite the uses.
bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
                                    const DominatorTree &DT, const LoopInfo &LI,
                                    ScalarEvolution *SE,
                                    SmallVectorImpl<PHINode *> *PHIsToRemove,
                                    SmallVectorImpl<PHINode *> *InsertedPHIs) { … }

// Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
static void computeBlocksDominatingExits(
    Loop &L, const DominatorTree &DT, ArrayRef<BasicBlock *> ExitBlocks,
    SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) { … }

static bool formLCSSAImpl(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
                          ScalarEvolution *SE,
                          LoopExitBlocksTy &LoopExitBlocks) { … }

bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
                     ScalarEvolution *SE) { … }

/// Process a loop nest depth first.
static bool formLCSSARecursivelyImpl(Loop &L, const DominatorTree &DT,
                                     const LoopInfo *LI, ScalarEvolution *SE,
                                     LoopExitBlocksTy &LoopExitBlocks) { … }

/// Process a loop nest depth first.
bool llvm::formLCSSARecursively(Loop &L, const DominatorTree &DT,
                                const LoopInfo *LI, ScalarEvolution *SE) { … }

/// Process all loops in the function, inner-most out.
static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT,
                                ScalarEvolution *SE) { … }

namespace {
struct LCSSAWrapperPass : public FunctionPass { … };
}

char LCSSAWrapperPass::ID = …;
INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
                      false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LCSSAVerificationPass)
INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
                    false, false)

Pass *llvm::createLCSSAPass() { … }
char &llvm::LCSSAID = …;

/// Transform \p F into loop-closed SSA form.
bool LCSSAWrapperPass::runOnFunction(Function &F) { … }

PreservedAnalyses LCSSAPass::run(Function &F, FunctionAnalysisManager &AM) { … }