<commit_before>//===- PromoteMemoryToRegister.cpp - Convert memory refs to regs ----------===//
//
// This file is used to promote memory references to be register references.  A
// simple example of the transformation performed by this function is:
//
//        FROM CODE                           TO CODE
//   %X = alloca int, uint 1                 ret int 42
//   store int 42, int *%X
//   %Y = load int* %X
//   ret int %Y
//
// The code is transformed by looping over all of the alloca instruction,
// calculating dominator frontiers, then inserting phi-nodes following the usual
// SSA construction algorithm.  This code does not modify the CFG of the
// function.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/iMemory.h"
#include "llvm/iPHINode.h"
#include "llvm/iTerminators.h"
#include "llvm/Function.h"
#include "llvm/Constant.h"
#include "llvm/Type.h"
#include "llvm/Support/CFG.h"
#include "Support/StringExtras.h"

/// isAllocaPromotable - Return true if this alloca is legal for promotion.
/// This is true if there are only loads and stores to the alloca...
///
bool isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) {
  // FIXME: If the memory unit is of pointer or integer type, we can permit
  // assignments to subsections of the memory unit.

  // Only allow direct loads and stores...
  for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end();
       UI != UE; ++UI)     // Loop over all of the uses of the alloca
    if (!isa<LoadInst>(*UI))
      if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
        if (SI->getOperand(0) == AI)
          return false;   // Don't allow a store of the AI, only INTO the AI.
      } else {
        return false;   // Not a load or store?
      }
  
  return true;
}


namespace {
  struct PromoteMem2Reg {
    // Allocas - The alloca instructions being promoted
    const std::vector<AllocaInst*> &Allocas;
    DominanceFrontier &DF;
    const TargetData &TD;

    // AllocaLookup - Reverse mapping of Allocas
    std::map<AllocaInst*, unsigned>  AllocaLookup;

    // VersionNumbers - Current version counters for each alloca
    std::vector<unsigned> VersionNumbers;
    
    // NewPhiNodes - The PhiNodes we're adding.
    std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes;

    // Visited - The set of basic blocks the renamer has already visited.
    std::set<BasicBlock*> Visited;

  public:
    PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominanceFrontier &df,
                   const TargetData &td) : Allocas(A), DF(df), TD(td) {}

    void run();

  private:
    void RenamePass(BasicBlock *BB, BasicBlock *Pred,
                    std::vector<Value*> &IncVals);
    bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx);
  };
}  // end of anonymous namespace


void PromoteMem2Reg::run() {
  Function &F = *DF.getRoot()->getParent();

  VersionNumbers.resize(Allocas.size());

  for (unsigned i = 0; i != Allocas.size(); ++i) {
    AllocaInst *AI = Allocas[i];

    assert(isAllocaPromotable(AI, TD) &&
           "Cannot promote non-promotable alloca!");
    assert(Allocas[i]->getParent()->getParent() == &F &&
           "All allocas should be in the same function, which is same as DF!");

    // Calculate the set of write-locations for each alloca.  This is analogous
    // to counting the number of 'redefinitions' of each variable.
    std::vector<BasicBlock*> WriteSets;
    for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E; ++U)
      if (StoreInst *SI = dyn_cast<StoreInst>(cast<Instruction>(*U)))
        // jot down the basic-block it came from
        WriteSets.push_back(SI->getParent());

    AllocaLookup[Allocas[i]] = i;
    
    // PhiNodeBlocks - A list of blocks that phi nodes have been inserted for
    // this alloca.
    std::vector<BasicBlock*> PhiNodeBlocks;

    // Compute the locations where PhiNodes need to be inserted.  Look at the
    // dominance frontier of EACH basic-block we have a write in.
    //
    for (unsigned j = 0; j != WriteSets.size(); j++) {
      // Look up the DF for this write, add it to PhiNodes
      DominanceFrontier::const_iterator it = DF.find(WriteSets[j]);
      if (it != DF.end()) {
        const DominanceFrontier::DomSetType &S = it->second;
        for (DominanceFrontier::DomSetType::iterator P = S.begin(),PE = S.end();
             P != PE; ++P)
          if (QueuePhiNode(*P, i))
            PhiNodeBlocks.push_back(*P);
      }
    }
    
    // Perform iterative step
    for (unsigned k = 0; k != PhiNodeBlocks.size(); k++) {
      DominanceFrontier::const_iterator it = DF.find(PhiNodeBlocks[k]);
      if (it != DF.end()) {
        const DominanceFrontier::DomSetType &S = it->second;
        for (DominanceFrontier::DomSetType::iterator
               P = S.begin(), PE = S.end(); P != PE; ++P)
          if (QueuePhiNode(*P, i))
            PhiNodeBlocks.push_back(*P);
      }
    }
  }

  // Set the incoming values for the basic block to be null values for all of
  // the alloca's.  We do this in case there is a load of a value that has not
  // been stored yet.  In this case, it will get this null value.
  //<commit_msg>There is no need for separate WriteSets and PhiNodeBlocks lists.  It is just a work-list of value definitions.  This allows elimination of the explicit 'iterative' step of the algorithm, and also reuses temporary memory better.<commit_after>//===- PromoteMemoryToRegister.cpp - Convert memory refs to regs ----------===//
//
// This file is used to promote memory references to be register references.  A
// simple example of the transformation performed by this function is:
//
//        FROM CODE                           TO CODE
//   %X = alloca int, uint 1                 ret int 42
//   store int 42, int *%X
//   %Y = load int* %X
//   ret int %Y
//
// The code is transformed by looping over all of the alloca instruction,
// calculating dominator frontiers, then inserting phi-nodes following the usual
// SSA construction algorithm.  This code does not modify the CFG of the
// function.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/iMemory.h"
#include "llvm/iPHINode.h"
#include "llvm/iTerminators.h"
#include "llvm/Function.h"
#include "llvm/Constant.h"
#include "llvm/Type.h"
#include "llvm/Support/CFG.h"
#include "Support/StringExtras.h"

/// isAllocaPromotable - Return true if this alloca is legal for promotion.
/// This is true if there are only loads and stores to the alloca...
///
bool isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) {
  // FIXME: If the memory unit is of pointer or integer type, we can permit
  // assignments to subsections of the memory unit.

  // Only allow direct loads and stores...
  for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end();
       UI != UE; ++UI)     // Loop over all of the uses of the alloca
    if (!isa<LoadInst>(*UI))
      if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
        if (SI->getOperand(0) == AI)
          return false;   // Don't allow a store of the AI, only INTO the AI.
      } else {
        return false;   // Not a load or store?
      }
  
  return true;
}


namespace {
  struct PromoteMem2Reg {
    // Allocas - The alloca instructions being promoted
    const std::vector<AllocaInst*> &Allocas;
    DominanceFrontier &DF;
    const TargetData &TD;

    // AllocaLookup - Reverse mapping of Allocas
    std::map<AllocaInst*, unsigned>  AllocaLookup;

    // VersionNumbers - Current version counters for each alloca
    std::vector<unsigned> VersionNumbers;
    
    // NewPhiNodes - The PhiNodes we're adding.
    std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes;

    // Visited - The set of basic blocks the renamer has already visited.
    std::set<BasicBlock*> Visited;

  public:
    PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominanceFrontier &df,
                   const TargetData &td) : Allocas(A), DF(df), TD(td) {}

    void run();

  private:
    void RenamePass(BasicBlock *BB, BasicBlock *Pred,
                    std::vector<Value*> &IncVals);
    bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx);
  };
}  // end of anonymous namespace

void PromoteMem2Reg::run() {
  Function &F = *DF.getRoot()->getParent();

  VersionNumbers.resize(Allocas.size());

  for (unsigned i = 0; i != Allocas.size(); ++i) {
    AllocaInst *AI = Allocas[i];

    assert(isAllocaPromotable(AI, TD) &&
           "Cannot promote non-promotable alloca!");
    assert(Allocas[i]->getParent()->getParent() == &F &&
           "All allocas should be in the same function, which is same as DF!");

    // Calculate the set of write-locations for each alloca.  This is analogous
    // to counting the number of 'redefinitions' of each variable.
    std::vector<BasicBlock*> DefiningBlocks;
    for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E; ++U)
      if (StoreInst *SI = dyn_cast<StoreInst>(cast<Instruction>(*U)))
        // jot down the basic-block it came from
        DefiningBlocks.push_back(SI->getParent());

    AllocaLookup[Allocas[i]] = i;
    
    // PhiNodeBlocks - A list of blocks that phi nodes have been inserted for
    // this alloca.
    std::vector<BasicBlock*> PhiNodeBlocks;

    // Compute the locations where PhiNodes need to be inserted.  Look at the
    // dominance frontier of EACH basic-block we have a write in.
    //
    while (!DefiningBlocks.empty()) {
      BasicBlock *BB = DefiningBlocks.back();
      DefiningBlocks.pop_back();

      // Look up the DF for this write, add it to PhiNodes
      DominanceFrontier::const_iterator it = DF.find(BB);
      if (it != DF.end()) {
        const DominanceFrontier::DomSetType &S = it->second;
        for (DominanceFrontier::DomSetType::iterator P = S.begin(),PE = S.end();
             P != PE; ++P)
          if (QueuePhiNode(*P, i))
            DefiningBlocks.push_back(*P);
      }
    }
  }

  // Set the incoming values for the basic block to be null values for all of
  // the alloca's.  We do this in case there is a load of a value that has not
  // been stored yet.  In this case, it will get this null value.
  //
{'fraction_non_alphanumeric': 0.13579179871314703, 'fraction_numerical': 0.0021127436857773935, 'mean_word_length': 2.6109570041608876, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 52, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4662374', 'n_tokens_mistral': 3213, 'n_tokens_neox': 3115, 'n_words': 1080}