Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- 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 file provides a template that implements the core algorithm for the

// SSAUpdater and MachineSSAUpdater.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H

#define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/Support/Allocator.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/raw_ostream.h"

#define DEBUG_TYPE "ssaupdater"

namespace llvm {

template<typename T> class SSAUpdaterTraits;

template<typename UpdaterT>

class SSAUpdaterImpl {

private:

  UpdaterT *Updater;

  using Traits = SSAUpdaterTraits<UpdaterT>;

  using BlkT = typename Traits::BlkT;

  using ValT = typename Traits::ValT;

  using PhiT = typename Traits::PhiT;

  /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.

  /// The predecessors of each block are cached here since pred_iterator is

  /// slow and we need to iterate over the blocks at least a few times.

  class BBInfo {

  public:

    // Back-pointer to the corresponding block.

    BlkT *BB;

    // Value to use in this block.

    ValT AvailableVal;

    // Block that defines the available value.

    BBInfo *DefBB;

    // Postorder number.

    int BlkNum = 0;

    // Immediate dominator.

    BBInfo *IDom = nullptr;

    // Number of predecessor blocks.

    unsigned NumPreds = 0;

    // Array[NumPreds] of predecessor blocks.

    BBInfo **Preds = nullptr;

    // Marker for existing PHIs that match.

    PhiT *PHITag = nullptr;

    BBInfo(BlkT *ThisBB, ValT V)

      : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}

  };

  using AvailableValsTy = DenseMap<BlkT *, ValT>;

  AvailableValsTy *AvailableVals;

  SmallVectorImpl<PhiT *> *InsertedPHIs;

  using BlockListTy = SmallVectorImpl<BBInfo *>;

  using BBMapTy = DenseMap<BlkT *, BBInfo *>;

  BBMapTy BBMap;

  BumpPtrAllocator Allocator;

public:

  explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,

                          SmallVectorImpl<PhiT *> *Ins) :

    Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}

  /// GetValue - Check to see if AvailableVals has an entry for the specified

  /// BB and if so, return it.  If not, construct SSA form by first

  /// calculating the required placement of PHIs and then inserting new PHIs

  /// where needed.

  ValT GetValue(BlkT *BB) {

    SmallVector<BBInfo *, 100> BlockList;

    BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);

    // Special case: bail out if BB is unreachable.

    if (BlockList.size() == 0) {

      ValT V = Traits::GetUndefVal(BB, Updater);

      (*AvailableVals)[BB] = V;

      return V;

    }

    FindDominators(&BlockList, PseudoEntry);

    FindPHIPlacement(&BlockList);

    FindAvailableVals(&BlockList);

    return BBMap[BB]->DefBB->AvailableVal;

  }

  /// BuildBlockList - Starting from the specified basic block, traverse back

  /// through its predecessors until reaching blocks with known values.

  /// Create BBInfo structures for the blocks and append them to the block

  /// list.

  BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {

    SmallVector<BBInfo *, 10> RootList;

    SmallVector<BBInfo *, 64> WorkList;

    BBInfo *Info = new (Allocator) BBInfo(BB, 0);

    BBMap[BB] = Info;

    WorkList.push_back(Info);

    // Search backward from BB, creating BBInfos along the way and stopping

    // when reaching blocks that define the value.  Record those defining

    // blocks on the RootList.

    SmallVector<BlkT *, 10> Preds;

    while (!WorkList.empty()) {

      Info = WorkList.pop_back_val();

      Preds.clear();

      Traits::FindPredecessorBlocks(Info->BB, &Preds);

      Info->NumPreds = Preds.size();

      if (Info->NumPreds == 0)

        Info->Preds = nullptr;

      else

        Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(

            Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));

      for (unsigned p = 0; p != Info->NumPreds; ++p) {

        BlkT *Pred = Preds[p];

        // Check if BBMap already has a BBInfo for the predecessor block.

        typename BBMapTy::value_type &BBMapBucket =

          BBMap.FindAndConstruct(Pred);

        if (BBMapBucket.second) {

          Info->Preds[p] = BBMapBucket.second;

          continue;

        }

        // Create a new BBInfo for the predecessor.

        ValT PredVal = AvailableVals->lookup(Pred);

        BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);

        BBMapBucket.second = PredInfo;

        Info->Preds[p] = PredInfo;

        if (PredInfo->AvailableVal) {

          RootList.push_back(PredInfo);

          continue;

        }

        WorkList.push_back(PredInfo);

      }

    }

    // Now that we know what blocks are backwards-reachable from the starting

    // block, do a forward depth-first traversal to assign postorder numbers

    // to those blocks.

    BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);

    unsigned BlkNum = 1;

    // Initialize the worklist with the roots from the backward traversal.

    while (!RootList.empty()) {

      Info = RootList.pop_back_val();

      Info->IDom = PseudoEntry;

      Info->BlkNum = -1;

      WorkList.push_back(Info);

    }

    while (!WorkList.empty()) {

      Info = WorkList.back();

      if (Info->BlkNum == -2) {

        // All the successors have been handled; assign the postorder number.

        Info->BlkNum = BlkNum++;

        // If not a root, put it on the BlockList.

        if (!Info->AvailableVal)

          BlockList->push_back(Info);

        WorkList.pop_back();

        continue;

      }

      // Leave this entry on the worklist, but set its BlkNum to mark that its

      // successors have been put on the worklist.  When it returns to the top

      // the list, after handling its successors, it will be assigned a

      // number.

      Info->BlkNum = -2;

      // Add unvisited successors to the work list.

      for (typename Traits::BlkSucc_iterator SI =

             Traits::BlkSucc_begin(Info->BB),

             E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {

        BBInfo *SuccInfo = BBMap[*SI];

        if (!SuccInfo || SuccInfo->BlkNum)

          continue;

        SuccInfo->BlkNum = -1;

        WorkList.push_back(SuccInfo);

      }

    }

    PseudoEntry->BlkNum = BlkNum;

    return PseudoEntry;

  }

  /// IntersectDominators - This is the dataflow lattice "meet" operation for

  /// finding dominators.  Given two basic blocks, it walks up the dominator

  /// tree until it finds a common dominator of both.  It uses the postorder

  /// number of the blocks to determine how to do that.

  BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {

    while (Blk1 != Blk2) {

      while (Blk1->BlkNum < Blk2->BlkNum) {

        Blk1 = Blk1->IDom;

        if (!Blk1)

          return Blk2;

      }

      while (Blk2->BlkNum < Blk1->BlkNum) {

        Blk2 = Blk2->IDom;

        if (!Blk2)

          return Blk1;

      }

    }

    return Blk1;

  }

  /// FindDominators - Calculate the dominator tree for the subset of the CFG

  /// corresponding to the basic blocks on the BlockList.  This uses the

  /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey

  /// and Kennedy, published in Software--Practice and Experience, 2001,

  /// 4:1-10.  Because the CFG subset does not include any edges leading into

  /// blocks that define the value, the results are not the usual dominator

  /// tree.  The CFG subset has a single pseudo-entry node with edges to a set

  /// of root nodes for blocks that define the value.  The dominators for this

  /// subset CFG are not the standard dominators but they are adequate for

  /// placing PHIs within the subset CFG.

  void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {

    bool Changed;

    do {

      Changed = false;

      // Iterate over the list in reverse order, i.e., forward on CFG edges.

      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),

             E = BlockList->rend(); I != E; ++I) {

        BBInfo *Info = *I;

        BBInfo *NewIDom = nullptr;

        // Iterate through the block's predecessors.

        for (unsigned p = 0; p != Info->NumPreds; ++p) {

          BBInfo *Pred = Info->Preds[p];

          // Treat an unreachable predecessor as a definition with 'undef'.

          if (Pred->BlkNum == 0) {

            Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);

            (*AvailableVals)[Pred->BB] = Pred->AvailableVal;

            Pred->DefBB = Pred;

            Pred->BlkNum = PseudoEntry->BlkNum;

            PseudoEntry->BlkNum++;

          }

          if (!NewIDom)

            NewIDom = Pred;

          else

            NewIDom = IntersectDominators(NewIDom, Pred);

        }

        // Check if the IDom value has changed.

        if (NewIDom && NewIDom != Info->IDom) {

          Info->IDom = NewIDom;

          Changed = true;

        }

      }

    } while (Changed);

  }

  /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for

  /// any blocks containing definitions of the value.  If one is found, then

  /// the successor of Pred is in the dominance frontier for the definition,

  /// and this function returns true.

  bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {

    for (; Pred != IDom; Pred = Pred->IDom) {

      if (Pred->DefBB == Pred)

        return true;

    }

    return false;

  }

  /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers

  /// of the known definitions.  Iteratively add PHIs in the dom frontiers

  /// until nothing changes.  Along the way, keep track of the nearest

  /// dominating definitions for non-PHI blocks.

  void FindPHIPlacement(BlockListTy *BlockList) {

    bool Changed;

    do {

      Changed = false;

      // Iterate over the list in reverse order, i.e., forward on CFG edges.

      for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),

             E = BlockList->rend(); I != E; ++I) {

        BBInfo *Info = *I;

        // If this block already needs a PHI, there is nothing to do here.

        if (Info->DefBB == Info)

          continue;

        // Default to use the same def as the immediate dominator.

        BBInfo *NewDefBB = Info->IDom->DefBB;

        for (unsigned p = 0; p != Info->NumPreds; ++p) {

          if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {

            // Need a PHI here.

            NewDefBB = Info;

            break;

          }

        }

        // Check if anything changed.

        if (NewDefBB != Info->DefBB) {

          Info->DefBB = NewDefBB;

          Changed = true;

        }

      }

    } while (Changed);

  }

  /// Check all predecessors and if all of them have the same AvailableVal use

  /// it as value for block represented by Info. Return true if singluar value

  /// is found.

  bool FindSingularVal(BBInfo *Info) {

    if (!Info->NumPreds)

      return false;

    ValT Singular = Info->Preds[0]->DefBB->AvailableVal;

    if (!Singular)

      return false;

    for (unsigned Idx = 1; Idx < Info->NumPreds; ++Idx) {

      ValT PredVal = Info->Preds[Idx]->DefBB->AvailableVal;

      if (!PredVal || Singular != PredVal)

        return false;

    }

    // Record Singular value.

    (*AvailableVals)[Info->BB] = Singular;

    assert(BBMap[Info->BB] == Info && "Info missed in BBMap?");

    Info->AvailableVal = Singular;

    Info->DefBB = Info->Preds[0]->DefBB;

    return true;

  }

  /// FindAvailableVal - If this block requires a PHI, first check if an

  /// existing PHI matches the PHI placement and reaching definitions computed

  /// earlier, and if not, create a new PHI.  Visit all the block's

  /// predecessors to calculate the available value for each one and fill in

  /// the incoming values for a new PHI.

  void FindAvailableVals(BlockListTy *BlockList) {

    // Go through the worklist in forward order (i.e., backward through the CFG)

    // and check if existing PHIs can be used.  If not, create empty PHIs where

    // they are needed.

    for (typename BlockListTy::iterator I = BlockList->begin(),

           E = BlockList->end(); I != E; ++I) {

      BBInfo *Info = *I;

      // Check if there needs to be a PHI in BB.

      if (Info->DefBB != Info)

        continue;

      // Look for singular value.

      if (FindSingularVal(Info))

        continue;

      // Look for an existing PHI.

      FindExistingPHI(Info->BB, BlockList);

      if (Info->AvailableVal)

        continue;

      ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);

      Info->AvailableVal = PHI;

      (*AvailableVals)[Info->BB] = PHI;

    }

    // Now go back through the worklist in reverse order to fill in the

    // arguments for any new PHIs added in the forward traversal.

    for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),

           E = BlockList->rend(); I != E; ++I) {

      BBInfo *Info = *I;

      if (Info->DefBB != Info) {

        // Record the available value to speed up subsequent uses of this

        // SSAUpdater for the same value.

        (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;

        continue;

      }

      // Check if this block contains a newly added PHI.

      PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);

      if (!PHI)

        continue;

      // Iterate through the block's predecessors.

      for (unsigned p = 0; p != Info->NumPreds; ++p) {

        BBInfo *PredInfo = Info->Preds[p];

        BlkT *Pred = PredInfo->BB;

        // Skip to the nearest preceding definition.

        if (PredInfo->DefBB != PredInfo)

          PredInfo = PredInfo->DefBB;

        Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);

      }

      LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");

      // If the client wants to know about all new instructions, tell it.

      if (InsertedPHIs) InsertedPHIs->push_back(PHI);

    }

  }

  /// FindExistingPHI - Look through the PHI nodes in a block to see if any of

  /// them match what is needed.

  void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {

    for (auto &SomePHI : BB->phis()) {

      if (CheckIfPHIMatches(&SomePHI)) {

        RecordMatchingPHIs(BlockList);

        break;

      }

      // Match failed: clear all the PHITag values.

      for (typename BlockListTy::iterator I = BlockList->begin(),

             E = BlockList->end(); I != E; ++I)

        (*I)->PHITag = nullptr;

    }

  }

  /// CheckIfPHIMatches - Check if a PHI node matches the placement and values

  /// in the BBMap.

  bool CheckIfPHIMatches(PhiT *PHI) {

    SmallVector<PhiT *, 20> WorkList;

    WorkList.push_back(PHI);

    // Mark that the block containing this PHI has been visited.

    BBMap[PHI->getParent()]->PHITag = PHI;

    while (!WorkList.empty()) {

      PHI = WorkList.pop_back_val();

      // Iterate through the PHI's incoming values.

      for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),

             E = Traits::PHI_end(PHI); I != E; ++I) {

        ValT IncomingVal = I.getIncomingValue();

        BBInfo *PredInfo = BBMap[I.getIncomingBlock()];

        // Skip to the nearest preceding definition.

        if (PredInfo->DefBB != PredInfo)

          PredInfo = PredInfo->DefBB;

        // Check if it matches the expected value.

        if (PredInfo->AvailableVal) {

          if (IncomingVal == PredInfo->AvailableVal)

            continue;

          return false;

        }

        // Check if the value is a PHI in the correct block.

        PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);

        if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)

          return false;

        // If this block has already been visited, check if this PHI matches.

        if (PredInfo->PHITag) {

          if (IncomingPHIVal == PredInfo->PHITag)

            continue;

          return false;

        }

        PredInfo->PHITag = IncomingPHIVal;

        WorkList.push_back(IncomingPHIVal);

      }

    }

    return true;

  }

  /// RecordMatchingPHIs - For each PHI node that matches, record it in both

  /// the BBMap and the AvailableVals mapping.

  void RecordMatchingPHIs(BlockListTy *BlockList) {

    for (typename BlockListTy::iterator I = BlockList->begin(),

           E = BlockList->end(); I != E; ++I)

      if (PhiT *PHI = (*I)->PHITag) {

        BlkT *BB = PHI->getParent();

        ValT PHIVal = Traits::GetPHIValue(PHI);

        (*AvailableVals)[BB] = PHIVal;

        BBMap[BB]->AvailableVal = PHIVal;

      }

  }

};

} // end namespace llvm

#undef DEBUG_TYPE // "ssaupdater"

#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H