//===- LCSSA.h - Loop-closed SSA transform Pass -----------------*- C++ -*-===//
//
// 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.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_UTILS_LCSSA_H
#define LLVM_TRANSFORMS_UTILS_LCSSA_H

#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/PassManager.h"

namespace llvm {

/// This function converts regions into region-closed SSA form. This tries to
/// achieve similar result to LCSSA but for a region of basic blocks. Please
/// note that the definition of region in this case is different than the usual
/// region (a collection of basic blocks which have a single entry and single
/// exit). In this case, a region of basic blocks satisfies the following
/// criteria:
///
/// 1. The region start basic block dominates all the basic blocks in the region
///    which also essentially means this block has the only entry to the region.
/// 2. The region end basic block either post-dominates all the basic blocks OR
///    the region end basic block is reachable from all other basic blocks (not
///    considering loop back-edges). This is to accomodate the cases in which
///    the other basic blocks can exit from the region.
/// 3. If there is a loop contained within this region, all the basic blocks
///    within the loop should be included in the region.
///
/// This function creates SSA form for such kinds of regions defined by a
/// collection of basic blocks by \param RegionBlocks and with region start
/// basic block \param RegionStartBB. The exit blocks for this region are
/// supposed to be provided at \param ExitBlocks by the users.
bool formRegionCSSA(SmallVector<BasicBlock *, 8> &RegionBlocks,
                    BasicBlock *RegionStartBB, const DominatorTree &DT,
                    const LoopInfo *LI, ScalarEvolution *SE,
                    SmallVector<BasicBlock *, 8> &ExitBlocks);

/// Converts loops into loop-closed SSA form.
class LCSSAPass : public PassInfoMixin<LCSSAPass> {
public:
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
};
} // end namespace llvm

#endif // LLVM_TRANSFORMS_UTILS_LCSSA_H
