text: //===- SROA.h - Scalar Replacement Of Aggregates ----------------*- 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
  //
  //===----------------------------------------------------------------------===//
  /// \file
  /// This file provides the interface for LLVM's Scalar Replacement of
  /// Aggregates pass. This pass provides both aggregate splitting and the
  /// primary SSA formation used in the compiler.
  ///
  //===----------------------------------------------------------------------===//
  
  #ifndef LLVM_TRANSFORMS_SCALAR_SROA_H
  #define LLVM_TRANSFORMS_SCALAR_SROA_H
  
  #include "llvm/ADT/SetVector.h"
  #include "llvm/ADT/SmallVector.h"
  #include "llvm/IR/PassManager.h"
  #include "llvm/IR/ValueHandle.h"
  #include <vector>
  
  namespace llvm {
  
  class AllocaInst;
  class AssumptionCache;
  class DominatorTree;
  class Function;
  class LLVMContext;
  class PHINode;
  class SelectInst;
  class Use;
  
  /// A private "module" namespace for types and utilities used by SROA. These
  /// are implementation details and should not be used by clients.
  namespace sroa LLVM_LIBRARY_VISIBILITY {
  
  class AllocaSliceRewriter;
  class AllocaSlices;
  class Partition;
  class SROALegacyPass;
  
  } // end namespace sroa
  
  /// An optimization pass providing Scalar Replacement of Aggregates.
  ///
  /// This pass takes allocations which can be completely analyzed (that is, they
  /// don't escape) and tries to turn them into scalar SSA values. There are
  /// a few steps to this process.
  ///
  /// 1) It takes allocations of aggregates and analyzes the ways in which they
  ///    are used to try to split them into smaller allocations, ideally of
  ///    a single scalar data type. It will split up memcpy and memset accesses
  ///    as necessary and try to isolate individual scalar accesses.
  /// 2) It will transform accesses into forms which are suitable for SSA value
  ///    promotion. This can be replacing a memset with a scalar store of an
  ///    integer value, or it can involve speculating operations on a PHI or
  ///    select to be a PHI or select of the results.
  /// 3) Finally, this will try to detect a pattern of accesses which map cleanly
  ///    onto insert and extract operations on a vector value, and convert them to
  ///    this form. By doing so, it will enable promotion of vector aggregates to
  ///    SSA vector values.
  class SROAPass : public PassInfoMixin<SROAPass> {
    LLVMContext *C = nullptr;
    DominatorTree *DT = nullptr;
    AssumptionCache *AC = nullptr;
  
    /// Worklist of alloca instructions to simplify.
    ///
    /// Each alloca in the function is added to this. Each new alloca formed gets
    /// added to it as well to recursively simplify unless that alloca can be
    /// directly promoted. Finally, each time we rewrite a use of an alloca other
    /// the one being actively rewritten, we add it back onto the list if not
    /// already present to ensure it is re-visited.
    SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist;
  
    /// A collection of instructions to delete.
    /// We try to batch deletions to simplify code and make things a bit more
    /// efficient. We also make sure there is no dangling pointers.
    SmallVector<WeakVH, 8> DeadInsts;
  
    /// Post-promotion worklist.
    ///
    /// Sometimes we discover an alloca which has a high probability of becoming
    /// viable for SROA after a round of promotion takes place. In those cases,
    /// the alloca is enqueued here for re-processing.
    ///
    /// Note that we have to be very careful to clear allocas out of this list in
    /// the event they are deleted.
    SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist;
  
    /// A collection of alloca instructions we can directly promote.
    std::vector<AllocaInst *> PromotableAllocas;
  
    /// A worklist of PHIs to speculate prior to promoting allocas.
    ///
    /// All of these PHIs have been checked for the safety of speculation and by
    /// being speculated will allow promoting allocas currently in the promotable
    /// queue.
    SetVector<PHINode *, SmallVector<PHINode *, 2>> SpeculatablePHIs;
  
    /// A worklist of select instructions to speculate prior to promoting
    /// allocas.
    ///
    /// All of these select instructions have been checked for the safety of
    /// speculation and by being speculated will allow promoting allocas
    /// currently in the promotable queue.
    SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects;
  
  public:
    SROAPass() = default;
  
    /// Run the pass over the function.
    PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
  
  private:
    friend class sroa::AllocaSliceRewriter;
    friend class sroa::SROALegacyPass;
  
    /// Helper used by both the public run method and by the legacy pass.
    PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT,
                              AssumptionCache &RunAC);
  
    bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS);
    AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS,
                                 sroa::Partition &P);
    bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
    bool runOnAlloca(AllocaInst &AI);
    void clobberUse(Use &U);
    bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
    bool promoteAllocas(Function &F);
  };
  
  } // end namespace llvm
  
  #endif // LLVM_TRANSFORMS_SCALAR_SROA_H
  