llvm/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp

//==- CanonicalizeFreezeInLoops - Canonicalize freezes in a loop-*- 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 canonicalizes freeze instructions in a loop by pushing them out to
// the preheader.
//
//   loop:
//     i = phi init, i.next
//     i.next = add nsw i, 1
//     i.next.fr = freeze i.next // push this out of this loop
//     use(i.next.fr)
//     br i1 (i.next <= N), loop, exit
//   =>
//     init.fr = freeze init
//   loop:
//     i = phi init.fr, i.next
//     i.next = add i, 1         // nsw is dropped here
//     use(i.next)
//     br i1 (i.next <= N), loop, exit
//
// Removing freezes from these chains help scalar evolution successfully analyze
// expressions.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils.h"

usingnamespacellvm;

#define DEBUG_TYPE …

namespace {

class CanonicalizeFreezeInLoops : public LoopPass { … };

class CanonicalizeFreezeInLoopsImpl { … };

} // anonymous namespace

namespace llvm {

struct FrozenIndPHIInfo { … };

template <> struct DenseMapInfo<FrozenIndPHIInfo> { … };

} // end namespace llvm

// Given U = (value, user), replace value with freeze(value), and let
// SCEV forget user. The inserted freeze is placed in the preheader.
void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) { … }

bool CanonicalizeFreezeInLoopsImpl::run() { … }

CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : … { … }

void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) { … }

PreservedAnalyses
CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,
                                   LoopStandardAnalysisResults &AR,
                                   LPMUpdater &U) { … }

INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
                      "Canonicalize Freeze Instructions in Loops", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
                    "Canonicalize Freeze Instructions in Loops", false, false)

Pass *llvm::createCanonicalizeFreezeInLoopsPass() { … }

char CanonicalizeFreezeInLoops::ID = …;