llvm/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

//===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
//
// 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 family of functions perform movements on basic blocks, and instructions
// contained within a function.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/CodeMoverUtils.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(HasDependences,
          "Cannot move across instructions that has memory dependences");
STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
STATISTIC(NotControlFlowEquivalent,
          "Instructions are not control flow equivalent");
STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");

namespace {
/// Represent a control condition. A control condition is a condition of a
/// terminator to decide which successors to execute. The pointer field
/// represents the address of the condition of the terminator. The integer field
/// is a bool, it is true when the basic block is executed when V is true. For
/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
/// integer field equals to true, while %cond is a control condition of bb1 with
/// the integer field equals to false.
ControlCondition;
#ifndef NDEBUG
raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
  OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
     << "]";
  return OS;
}
#endif

/// Represent a set of control conditions required to execute ToBB from FromBB.
class ControlConditions { … };
} // namespace

static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,
                               const Instruction *InstB) { … }

const std::optional<ControlConditions>
ControlConditions::collectControlConditions(const BasicBlock &BB,
                                            const BasicBlock &Dominator,
                                            const DominatorTree &DT,
                                            const PostDominatorTree &PDT,
                                            unsigned MaxLookup) { … }

bool ControlConditions::addControlCondition(ControlCondition C) { … }

bool ControlConditions::isEquivalent(const ControlConditions &Other) const { … }

bool ControlConditions::isEquivalent(const ControlCondition &C1,
                                     const ControlCondition &C2) { … }

// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
// Values.
// Currently, isEquivalent rely on other passes to ensure equivalent conditions
// have the same value, e.g. GVN.
bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) { … }

bool ControlConditions::isInverse(const Value &V1, const Value &V2) { … }

bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                                   const DominatorTree &DT,
                                   const PostDominatorTree &PDT) { … }

bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                                   const DominatorTree &DT,
                                   const PostDominatorTree &PDT) { … }

static bool reportInvalidCandidate(const Instruction &I,
                                   llvm::Statistic &Stat) { … }

/// Collect all instructions in between \p StartInst and \p EndInst, and store
/// them in \p InBetweenInsts.
static void
collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
                             SmallPtrSetImpl<Instruction *> &InBetweenInsts) { … }

bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                              DominatorTree &DT, const PostDominatorTree *PDT,
                              DependenceInfo *DI, bool CheckForEntireBlock) { … }

bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
                              DominatorTree &DT, const PostDominatorTree *PDT,
                              DependenceInfo *DI) { … }

void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
                                          DominatorTree &DT,
                                          const PostDominatorTree &PDT,
                                          DependenceInfo &DI) { … }

void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
                                    DominatorTree &DT,
                                    const PostDominatorTree &PDT,
                                    DependenceInfo &DI) { … }

bool llvm::nonStrictlyPostDominate(const BasicBlock *ThisBlock,
                                   const BasicBlock *OtherBlock,
                                   const DominatorTree *DT,
                                   const PostDominatorTree *PDT) { … }

bool llvm::isReachedBefore(const Instruction *I0, const Instruction *I1,
                           const DominatorTree *DT,
                           const PostDominatorTree *PDT) { … }