llvm/llvm/include/llvm/Analysis/SparsePropagation.h

//===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
//
// 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 file implements an abstract sparse conditional propagation algorithm,
// modeled after SCCP, but with a customizable lattice function.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
#define LLVM_ANALYSIS_SPARSEPROPAGATION_H

#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/Debug.h"
#include <set>

#define DEBUG_TYPE …

namespace llvm {

/// A template for translating between LLVM Values and LatticeKeys. Clients must
/// provide a specialization of LatticeKeyInfo for their LatticeKey type.
template <class LatticeKey> struct LatticeKeyInfo { … };

template <class LatticeKey, class LatticeVal,
          class KeyInfo = LatticeKeyInfo<LatticeKey>>
class SparseSolver;

/// AbstractLatticeFunction - This class is implemented by the dataflow instance
/// to specify what the lattice values are and how they handle merges etc.  This
/// gives the client the power to compute lattice values from instructions,
/// constants, etc.  The current requirement is that lattice values must be
/// copyable.  At the moment, nothing tries to avoid copying.  Additionally,
/// lattice keys must be able to be used as keys of a mapping data structure.
/// Internally, the generic solver currently uses a DenseMap to map lattice keys
/// to lattice values.  If the lattice key is a non-standard type, a
/// specialization of DenseMapInfo must be provided.
template <class LatticeKey, class LatticeVal> class AbstractLatticeFunction { … };

/// SparseSolver - This class is a general purpose solver for Sparse Conditional
/// Propagation with a programmable lattice function.
template <class LatticeKey, class LatticeVal, class KeyInfo>
class SparseSolver { … };

//===----------------------------------------------------------------------===//
//                  AbstractLatticeFunction Implementation
//===----------------------------------------------------------------------===//

template <class LatticeKey, class LatticeVal>
void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeVal(
    LatticeVal V, raw_ostream &OS) { … }

template <class LatticeKey, class LatticeVal>
void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeKey(
    LatticeKey Key, raw_ostream &OS) { … }

//===----------------------------------------------------------------------===//
//                          SparseSolver Implementation
//===----------------------------------------------------------------------===//

template <class LatticeKey, class LatticeVal, class KeyInfo>
LatticeVal
SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getValueState(LatticeKey Key) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::UpdateState(LatticeKey Key,
                                                                LatticeVal LV) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::MarkBlockExecutable(
    BasicBlock *BB) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::markEdgeExecutable(
    BasicBlock *Source, BasicBlock *Dest) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
    Instruction &TI, SmallVectorImpl<bool> &Succs, bool AggressiveUndef) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
bool SparseSolver<LatticeKey, LatticeVal, KeyInfo>::isEdgeFeasible(
    BasicBlock *From, BasicBlock *To, bool AggressiveUndef) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitTerminator(
    Instruction &TI) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitInst(Instruction &I) { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Solve() { … }

template <class LatticeKey, class LatticeVal, class KeyInfo>
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Print(
    raw_ostream &OS) const { … }
} // end namespace llvm

#undef DEBUG_TYPE

#endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H