<|start_filename|>src/tools/inliner/src/Inliner_loopCarried.cpp<|end_filename|>
/*
 * Copyright 2016 - 2019  <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "Inliner.hpp"
#include "DOALL.hpp"

namespace llvm::noelle {

bool Inliner::inlineCallsInvolvedInLoopCarriedDataDependences (Noelle &noelle, noelle::CallGraph *pcg) {
  auto anyInlined = false;

  /*
   * Order these functions to prevent duplicating loops yet to be checked
   */
  std::vector<Function *> orderedFns;
  for (auto fnLoops : loopsToCheck) {
    orderedFns.push_back(fnLoops.first);
  }
  sortInDepthOrderFns(orderedFns);

  std::set<Function *> fnsToAvoid;
  for (auto F : orderedFns) {
    
    /*
     * If we avoid this function until next pass, we do the same with its parents
     */
    if (fnsToAvoid.find(F) != fnsToAvoid.end()) {
      for (auto parentF : parentFns[F]) {
        fnsToAvoid.insert(parentF);
      }
      continue;
    }

    /*
     * Fetch all loops of the current function.
     */
    auto allLoops = noelle.getLoops(F);

    /*
     * Sort the loops by size.
     * This makes the loops sorted by scope as well (from outer to inner loops).
     */
    noelle.sortByStaticNumberOfInstructions(*allLoops);

    /*
     * Fetch the set of loops that are enabled.
     */
    auto &toCheck = loopsToCheck[F];

    /*
     * Inline calls that are involved in loop-carried data dependences for the enabled loops.
     */
    auto inlined = false;
    std::set<LoopStructure *> removeSummaries;
    for (auto LDI : *allLoops){

      /*
       * Check if the current loop has been enabled.
       */
      LoopStructure *summary = nullptr;
      for (auto enabledLoop : toCheck){
        if (enabledLoop->getHeader() == LDI->getLoopStructure()->getHeader()){
          summary = enabledLoop;
          break ;
        }
      }
      if (summary == nullptr){
        continue ;
      }

      /*
       * Check if the current loop is a DOALL.
       * If it is, then we disable all sub-loops to be considered because DOALL always takes priority and we don't parallelize nested loops at the moment.
       */
      DOALL doall{
        *noelle.getProgram(),
        *noelle.getProfiles(),
        noelle.getVerbosity()
      };
      if (  true
            && (summary->getNumberOfSubLoops() >= 1)
            && doall.canBeAppliedToLoop(LDI, noelle, nullptr)
        ){

        /*
         * The loop is a doall.
         *
         * Disable all sub-loops
         */
        auto disableSubLoop = [&toCheck] (const LoopStructure &child) -> bool{

          /*
           * Check if the sub-loop is enabled.
           */
          if (std::find(toCheck.begin(), toCheck.end(), &child) == toCheck.end()){
            return false;
          }

          /*
           * The sub-loop is enabled.
           *
           * Disable it.
           */
          std::remove(toCheck.begin(), toCheck.end(), &child);

          return false;
        };
        LDI->iterateOverSubLoopsRecursively(disableSubLoop);

        continue ;
      }

      /*
       * Inline the call.
       */
      auto inlinedCall = this->inlineCallsInvolvedInLoopCarriedDataDependencesWithinLoop(F, LDI, pcg, noelle);
      inlined |= inlinedCall;
      if (inlined) {
        break;
      }
    }

    /*
     * Free the memory.
     */
    for (auto tempLDI : *allLoops){
      delete tempLDI;
    }
    delete allLoops ;

    /*
     * Keep track of the inlining.
     */
    anyInlined |= inlined;

    /*
     * Avoid parents of affected functions.
     * This is because we are not finished with the affected functions.
     */
    if (inlined) {
      for (auto parentF : parentFns[F]) {
        fnsToAvoid.insert(parentF);
      }
    }
  }
    
  return anyInlined;
}

/*
 * GOAL: Go through loops in function
 * If there is only one non-clonable/reducable SCC,
 * try inlining the function call in that SCC with the
 * most memory edges to other internal/external values
 */
bool Inliner::inlineCallsInvolvedInLoopCarriedDataDependencesWithinLoop (
    Function *F, 
    LoopDependenceInfo *LDI, 
    noelle::CallGraph *pcg,
    Noelle &noelle
    ) {
  assert(pcg != nullptr);
  assert(LDI != nullptr);

  /*
   * Fetch the SCC manager.
   */
  auto sccManager = LDI->getSCCManager();

  /*
   * Fetch the SCCDAG
   */
  auto SCCDAG = sccManager->getSCCDAG();

  /*
   *inlineFunctionCall Fetch the loop structure.
   */
  auto loopStructure = LDI->getLoopStructure();

  /*
   * Check every sequential SCC.
   */
  int64_t maxMemEdges = 0;
  CallInst *inlineCall = nullptr;
  auto nonDOALLSCCs = DOALL::getSCCsThatBlockDOALLToBeApplicable(LDI, noelle);
  for (auto scc : nonDOALLSCCs) {

    /*
     * Check every instruction within the sequential SCC.
     *
     * Do not inline a call that depends on itself because it is unlikely to make a difference.
     * Most of the time such situation shows up as an SCC with a single node.
     */
    if (scc->numberOfInstructions() == 1){
      continue ;
    }

    /*
     * The SCC includes more than one instruction.
     * Check its calls.
     */
    for (auto valNode : scc->getNodes()) {

      /*
       * Fetch the next call instruction of the current sequential SCC.
       */
      auto val = valNode->getT();
      if (!isa<CallInst>(val)) {
        continue ;
      }
      auto call = cast<CallInst>(val);

      /*
       * Fetch the callee.
       */
      auto callF = call->getCalledFunction();
      if (!callF){

        /*
         * The callee is unknown.
         * So we cannot inline this call.
         */
        continue ;
      }
      if (callF->empty()) {

        /*
         * The callee's body is unknown (it is a library function).
         * So we cannot inline this call.
         */
        continue;
      }

      /*
       * Check if the callee is an intrinsic.
       */
      if (callF->isIntrinsic()){
        continue ;
      }

      /*
       * Do not consider inlining a recursive function call
       */
      if (callF == F) {
        continue;
      }

      /*
       * Do not consider inlining calls to functions of lower depth
       */
      if (fnOrders[callF] < fnOrders[F]) {
        continue;
      }

      /*
       * If the call instruction belongs to a sub-loop, then its inlining is likely to be useless.
       */
      if (loopStructure->isIncludedInItsSubLoops(call)){
        continue ;
      }

      /*
       * Do not consider inlining calls that are in a cycle within the program call graph.
       */
      if (pcg->doesItBelongToASCC(callF)){
        continue ;
      }

      /*
       * Count how many memory edges this call is involved in.
       */
      auto memEdgeCount = 0;
      for (auto edge : valNode->getAllConnectedEdges()) {
        if (edge->isMemoryDependence()) {
          memEdgeCount++;
        }
      }

      /*
       * Consider only the call instruction with the maximum number of memory edges.
       */
      if (memEdgeCount > maxMemEdges) {
        maxMemEdges = memEdgeCount;
        inlineCall = call;
      }
    }
  }

  /*
   * Check if there is a function to inline.
   */
  if (inlineCall == nullptr){

    /*
     * No call needs to be inlined.
     */
    return false;
  }

  /*
   * Inline the call instruction.
   */
  auto hot = noelle.getProfiles();
  auto inlined = inlineFunctionCall(hot, F, inlineCall->getCalledFunction(), inlineCall);

  return inlined;
}

}


<|start_filename|>src/core/pdg/src/PDGAnalysis_memory.cpp<|end_filename|>
/*
 * Copyright 2016 - 2020  <NAME>, <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "SystemHeaders.hpp"
#include "TalkDown.hpp"
#include "PDGPrinter.hpp"
#include "PDGAnalysis.hpp"
#include "IntegrationWithSVF.hpp"
#include "Utils.hpp"

namespace llvm::noelle {

void PDGAnalysis::iterateInstForStore (PDG *pdg, Function &F, AAResults &AA, DataFlowResult *dfr, StoreInst *store) {

  for (auto I : dfr->OUT(store)) {

    /*
     * Check stores.
     */
    if (auto otherStore = dyn_cast<StoreInst>(I)) {
      if (store != otherStore) {
        this->addEdgeFromMemoryAlias<StoreInst, StoreInst>(pdg, F, AA, store, otherStore, DG_DATA_WAW);
      }
      continue ;
    }

    /* 
     * Check loads.
     */
    if (auto load = dyn_cast<LoadInst>(I)) {
      this->addEdgeFromMemoryAlias<StoreInst, LoadInst>(pdg, F, AA, store, load, DG_DATA_RAW);
      continue ;
    }

    /*
     * Check calls.
     */
    if (auto call = dyn_cast<CallInst>(I)) {
      if (!Utils::isActualCode(call)){
        continue ;
      }
      this->addEdgeFromFunctionModRef(pdg, F, AA, call, store, false);
      continue ;
    }
  }

  return ;
}

void PDGAnalysis::iterateInstForLoad (PDG *pdg, Function &F, AAResults &AA, DataFlowResult *dfr, LoadInst *load) {

  for (auto I : dfr->OUT(load)) {

    /*
     * Check stores.
     */
    if (auto store = dyn_cast<StoreInst>(I)) {
      addEdgeFromMemoryAlias<LoadInst, StoreInst>(pdg, F, AA, load, store, DG_DATA_WAR);
      continue ;
    }

    /*
     * Check calls.
     */
    if (auto call = dyn_cast<CallInst>(I)) {
      if (!Utils::isActualCode(call)){
        continue ;
      }
      addEdgeFromFunctionModRef(pdg, F, AA, call, load, false);
      continue ;
    }
  }

  return ;
}

bool PDGAnalysis::hasNoMemoryOperations (CallInst *call) {

  /*
   * Check if SVF is enabled.
   */
  if (this->disableSVF){
    return false;
  }

  /*
   * Check if the callee is a library function.
   */
  auto calleeFunction = call->getCalledFunction();
  if (calleeFunction != nullptr){
    if (  true
          && calleeFunction->empty()
          && this->isTheLibraryFunctionPure(calleeFunction)
       ){
      return true ;
    }
  }

  /*
   * SVF is enabled.
   * We can use it.
   */
  if (NoelleSVFIntegration::getModRefInfo(call) == ModRefInfo::NoModRef) {
    return true;
  }

  return false;
}

void PDGAnalysis::addEdgeFromFunctionModRef (PDG *pdg, Function &F, AAResults &AA, CallInst *call, StoreInst *store, bool addEdgeFromCall) {
  BitVector bv(3, false);
  auto makeRefEdge = false, makeModEdge = false;

  /*
   * We cannot have memory dependences from a call to a deallocator (e.g., free).
   */
  if (Utils::isDeallocator(call)){
    return ;
  }

  /*
   * Query the LLVM alias analyses.
   */
  switch (AA.getModRefInfo(call, MemoryLocation::get(store))) {
    case ModRefInfo::NoModRef:
      return;
    case ModRefInfo::Ref:
      bv[0] = true;
      break;
    case ModRefInfo::Mod:
      bv[1] = true;
      break;
    case ModRefInfo::ModRef:
      bv[2] = true;
      break;
  }

  /*
   * Check other alias analyses
   *
   * Check if SVF is enabled.
   */
  if (this->disableSVF){

    /*
     * SVF is disabled.
     */

  } else {

    /*
     * SVF is enabled; let's use it.
     */
    auto weCanRelyOnSVF = cannotReachUnhandledExternalFunction(call);
    if (  true
          && weCanRelyOnSVF 
          && hasNoMemoryOperations(call)
      ) {
      return;
    }

    /*
     * Check if it is safe to use SVF.
     * This is due to a bug in SVF that doesn't model I/O library calls correctly.
     */
    if (isSafeToQueryModRefOfSVF(call, bv)) {
      auto const &loc = MemoryLocation::get(store);
      switch (NoelleSVFIntegration::getModRefInfo(call, loc)) {
        case ModRefInfo::NoModRef:
          return;
        case ModRefInfo::Ref:
          bv[0] = true;
          break;
        case ModRefInfo::Mod:
          bv[1] = true;
          break;
        case ModRefInfo::ModRef:
          bv[2] = true;
          break;
      }
    }
  }

  /*
   * NoModRef when one says Mod and another says Ref
   */
  if (bv[0] && bv[1]) {
    return; 
  } 
  if (bv[0]) {
    makeRefEdge = true;
  } else if (bv[1]) {
    makeModEdge = true;
  } else {
    makeRefEdge = makeModEdge = true;
  }

  /*
   * There is a dependence.
   */
  if (makeRefEdge) {
    if (addEdgeFromCall) {
      pdg->addEdge(call, store)->setMemMustType(true, false, DG_DATA_WAR);

    } else {

      /*
       * We cannot have memory dependences from a memory instruction to allocators as they always return new memory.
       */
      if (!Utils::isAllocator(call)){
        pdg->addEdge(store, call)->setMemMustType(true, false, DG_DATA_RAW);
      }
    }
  }
  if (makeModEdge) {
    if (addEdgeFromCall) {
      pdg->addEdge(call, store)->setMemMustType(true, false, DG_DATA_WAW);

    } else {

      /*
       * We cannot have memory dependences from a memory instruction to allocators as they always return new memory.
       */
      if (!Utils::isAllocator(call)){
        pdg->addEdge(store, call)->setMemMustType(true, false, DG_DATA_WAW);
      }
    }
  }

  return ;
}

void PDGAnalysis::addEdgeFromFunctionModRef (PDG *pdg, Function &F, AAResults &AA, CallInst *call, LoadInst *load, bool addEdgeFromCall) {
  BitVector bv(3, false);

  /*
   * We cannot have memory dependences from a call to a deallocator (e.g., free).
   */
  if (Utils::isDeallocator(call)){
    return ;
  }

  /*
   * Query the LLVM alias analyses.
   */
  switch (AA.getModRefInfo(call, MemoryLocation::get(load))) {
    case ModRefInfo::NoModRef:
    case ModRefInfo::Ref:
      return;
    case ModRefInfo::Mod:
    case ModRefInfo::ModRef:
      break;
  }

  /*
   * Check other alias analyses
   *
   * Check if SVF is enabled.
   */
  if (this->disableSVF){

    /*
     * SVF is disabled.
     */

  } else {

    /*
     * SVF is enabled; let's use it.
     */
    auto weCanRelyOnSVF = cannotReachUnhandledExternalFunction(call);
    if (  true
          && weCanRelyOnSVF 
          && hasNoMemoryOperations(call)
      ) {
      return;
    }

    /*
     * Check if it is safe to use SVF.
     * This is due to a bug in SVF that doesn't model I/O library calls correctly.
     */
    if (isSafeToQueryModRefOfSVF(call, bv)) {
      switch (NoelleSVFIntegration::getModRefInfo(call, MemoryLocation::get(load))) {
        case ModRefInfo::NoModRef:
        case ModRefInfo::Ref:
          return;

        case ModRefInfo::Mod:
        case ModRefInfo::ModRef:
          break;
      }
    }
  }

  /*
   * There is a dependence.
   */
  if (addEdgeFromCall) {
    pdg->addEdge(call, load)->setMemMustType(true, false, DG_DATA_RAW);

  } else {

    /*
     * We cannot have memory dependences from a memory instruction to allocators as they always return new memory.
     */
    if (!Utils::isAllocator(call)){
      pdg->addEdge(load, call)->setMemMustType(true, false, DG_DATA_WAR);
    }
  }

  return ;
}

void PDGAnalysis::addEdgeFromFunctionModRef (PDG *pdg, Function &F, AAResults &AA, CallInst *call, CallInst *otherCall) {
  BitVector bv(3, false);
  BitVector rbv(3, false);
  auto makeRefEdge = false, makeModEdge = false, makeModRefEdge = false;
  auto reverseRefEdge = false, reverseModEdge = false, reverseModRefEdge = false;

  /*
   * There is no dependence between allocators
   */
  if (  true
        && Utils::isAllocator(call)
        && Utils::isAllocator(otherCall)
        && (!Utils::isReallocator(call))
        && (!Utils::isReallocator(otherCall))
     ){
    return ;
  }

  /*
   * Check if the call instructions are about an allocator and a deallocator.
   */
  CallInst *allocatorCall = nullptr;
  CallInst *deallocatorCall = nullptr;
  if (Utils::isAllocator(call)){
    allocatorCall = call;
  }
  if (Utils::isAllocator(otherCall)){
    allocatorCall = otherCall;
  }
  if (Utils::isDeallocator(call)){
    deallocatorCall = call;
  }
  if (Utils::isDeallocator(otherCall)){
    deallocatorCall = otherCall;
  }
  if (  true
        && (allocatorCall != nullptr)
        && (deallocatorCall != nullptr)
     ){

    /*
     * The call instructions are one allocator and one deallocator.
     * In this case, we only need to check if the pointer accessed by the deallocator can alias the pointer returned by the allocator.
     */
    auto objectAllocated = Utils::getAllocatedObject(allocatorCall);
    assert(objectAllocated != nullptr);
    auto objectFreed = Utils::getFreedObject(deallocatorCall);
    assert(objectFreed != nullptr);
    auto doesAlias = this->doTheyAlias(pdg, F, AA, objectAllocated, objectFreed);
    if (doesAlias == NoAlias){
      return ;
    }
  }

  /*
   * Query the LLVM alias analyses.
   */
  switch (AA.getModRefInfo(call, otherCall)) {
    case ModRefInfo::NoModRef:
      return;

    case ModRefInfo::Ref:

      /*
       * @call may read memory locations written by @otherCall
       */
      bv[0] = true;
      break;

    case ModRefInfo::Mod:

      /*
       * @call may write a memory location that can be read or written by @otherCall
       */
      bv[1] = true;

      switch (AA.getModRefInfo(otherCall, call)) {
        case ModRefInfo::NoModRef:
          return;
        case ModRefInfo::Ref:
          rbv[0] = true;
          break;
        case ModRefInfo::Mod:
          rbv[1] = true;
          break;
        case ModRefInfo::ModRef:
          rbv[2] = true;
          break;
      }
      break;

    case ModRefInfo::ModRef:

      /*
       * @call may read or write a memory location that can be written by @otherCall
       */
      bv[2] = true;
      break;
  }

  /*
   * Check other alias analyses
   *
   * Check if SVF is enabled.
   */
  if (this->disableSVF){

    /*
     * SVF is disabled.
     */

  } else {

    /*
     * SVF is enabled; let's use it.
     */
    auto weCanRelyOnSVF = cannotReachUnhandledExternalFunction(call);
    if (  true
          && weCanRelyOnSVF 
          && hasNoMemoryOperations(call)
      ) {
      return;
    }
    weCanRelyOnSVF = cannotReachUnhandledExternalFunction(otherCall);
    if (  true
          && weCanRelyOnSVF 
          && hasNoMemoryOperations(otherCall)
      ) {
      return;
    }

    /*
     * Check if it is safe to use SVF.
     * This is due to a bug in SVF that doesn't model I/O library calls correctly.
     */
    if (  true
          && isSafeToQueryModRefOfSVF(call, bv) 
          && isSafeToQueryModRefOfSVF(otherCall, bv)
      ) {
      switch (NoelleSVFIntegration::getModRefInfo(call, otherCall)) {
        case ModRefInfo::NoModRef:
          return;

        case ModRefInfo::Ref:
          bv[0] = true;
          break;

        case ModRefInfo::Mod:
          bv[1] = true;

          switch (NoelleSVFIntegration::getModRefInfo(otherCall, call)) {
            case ModRefInfo::NoModRef:
              return;
            case ModRefInfo::Ref:
              rbv[0] = true;
              break;
            case ModRefInfo::Mod:
              rbv[1] = true;
              break;
            case ModRefInfo::ModRef:
              rbv[2] = true;
              break;
          }
          break;

        case ModRefInfo::ModRef:
          bv[2] = true;
          break;
      }
    }
  }

  if (bv[0] && bv[1]) {
    return;
  }
  if (bv[0]) {
    makeRefEdge = true;

  } else if (bv[1]) {
    makeModEdge = true ;
    if (rbv[0] && rbv[1]) {
      return ;
    }

    if (rbv[0]) {
      reverseRefEdge = true;
    } else if (rbv[1]) {
      reverseModEdge = true;
    } else {
      reverseModRefEdge = true;
    }

  } else {
    makeModRefEdge = true;
  }

  /*
   * There is a dependence.
   */
  if (makeRefEdge) {

    /*
     * @call reads a memory location that @otherCall writes.
     * The sequence of execution is @call and then @otherCall.
     * Hence, there is a WAR memory dependence from @call to @otherCall
     */
    pdg->addEdge(call, otherCall)->setMemMustType(true, false, DG_DATA_WAR);

    /*
     * Check the unique case that @call and @otherCall are the same. 
     * In this case, there is also a RAW dependence between them.
     */
    if (call == otherCall){
      pdg->addEdge(otherCall, call)->setMemMustType(true, false, DG_DATA_RAW);
    }

  } else if (makeModEdge) {

    /*
     * Dependency of a Mod-result between call and otherCall depends on the reverse getModRefInfo result
     */
    if (reverseRefEdge) {
      pdg->addEdge(call, otherCall)->setMemMustType(true, false, DG_DATA_RAW);

      /*
       * Check the unique case that @call and @otherCall are the same. 
       * In this case, there is also a WAR dependence between them.
       */
      if (call == otherCall){
        pdg->addEdge(otherCall, call)->setMemMustType(true, false, DG_DATA_WAR);
      }

    } else if (reverseModEdge) {
      pdg->addEdge(call, otherCall)->setMemMustType(true, false, DG_DATA_WAW);

    } else if (reverseModRefEdge) {
      pdg->addEdge(call, otherCall)->setMemMustType(true, false, DG_DATA_RAW);
      pdg->addEdge(call, otherCall)->setMemMustType(true, false, DG_DATA_WAW);

      /*
       * Check the unique case that @call and @otherCall are the same. 
       * In this case, there is also a WAR dependence between them.
       */
      if (call == otherCall){
        pdg->addEdge(otherCall, call)->setMemMustType(true, false, DG_DATA_WAR);
      }
    }

  } else if (makeModRefEdge) {
    pdg->addEdge(call, otherCall)->setMemMustType(true, false, DG_DATA_WAR);
    pdg->addEdge(call, otherCall)->setMemMustType(true, false, DG_DATA_WAW);

    /*
     * Check the unique case that @call and @otherCall are the same. 
     * In this case, there is also a RAW dependence between them.
     */
    if (call == otherCall){
      pdg->addEdge(otherCall, call)->setMemMustType(true, false, DG_DATA_RAW);
    }
  }

  return ;
}

bool PDGAnalysis::isSafeToQueryModRefOfSVF(CallInst *call, BitVector &bv) {

  /*
   * Check if SVF is enabled.
   */
  if (this->disableSVF){

    /*
     * SVF is disabled.
     */
    return false;
  }

  if (NoelleSVFIntegration::hasIndCSCallees(call)) {
    auto callees = NoelleSVFIntegration::getIndCSCallees(call);
    for (auto &callee : callees) {
      if (this->isUnhandledExternalFunction(callee) || isInternalFunctionThatReachUnhandledExternalFunction(callee)) {
        return false;
      }
    }

  } else {
    auto callee = call->getCalledFunction();
    if (!callee) {
      bv[2] = true; // ModRef bit is set
      return false;
    }

    if (this->isUnhandledExternalFunction(callee) || isInternalFunctionThatReachUnhandledExternalFunction(callee)) {
      return false;
    }
  }

  return true;
}

template<class InstI, class InstJ>
void PDGAnalysis::addEdgeFromMemoryAlias (PDG *pdg, Function &F, AAResults &AA, InstI *instI, InstJ *instJ, DataDependenceType dataDependenceType) {
  auto must = false;

  /*
   * Query the LLVM alias analyses.
   */
  switch (AA.alias(MemoryLocation::get(instI), MemoryLocation::get(instJ))) {
    case NoAlias:
      return ;
    case PartialAlias:
    case MayAlias:
      break;
    case MustAlias:
      pdg->addEdge(instI, instJ)->setMemMustType(true, true, dataDependenceType);
      return ;
  }

  /*
   * Check other alias analyses
   *
   * Check if SVF is enabled.
   */
  if (this->disableSVF){

    /*
     * SVF is disabled.
     */

  } else {

    /*
     * SVF is enabled, so let's use it.
     */
    switch (NoelleSVFIntegration::alias(MemoryLocation::get(instI), MemoryLocation::get(instJ))) {
      case NoAlias:
        return;
      case PartialAlias:
      case MayAlias:
        break;
      case MustAlias:
        must = true;
        break;
    }
  }

  /*
   * There is a dependence.
   */
  pdg->addEdge(instI, instJ)->setMemMustType(true, must, dataDependenceType);

  return ;
}

AliasResult PDGAnalysis::doTheyAlias (PDG *pdg, Function &F, AAResults &AA, Value *instI, Value *instJ){
  auto must = false;

  /*
   * Query the LLVM alias analyses.
   */
  switch (AA.alias(instI, instJ)) {
    case NoAlias:
      return NoAlias;
    case PartialAlias:
    case MayAlias:
      break;
    case MustAlias:
      return MustAlias;
  }

  /*
   * Check other alias analyses
   *
   * Check if SVF is enabled.
   */
  if (this->disableSVF){

    /*
     * SVF is disabled.
     */

  } else {

    /*
     * SVF is enabled, so let's use it.
     */
    switch (NoelleSVFIntegration::alias(instI, instJ)) {
      case NoAlias:
        return NoAlias;
      case PartialAlias:
      case MayAlias:
        break;
      case MustAlias:
        return MustAlias;
    }
  }

  return MayAlias;
}

}


<|start_filename|>src/tools/doall/src/Builder.cpp<|end_filename|>
/*
 * Copyright 2016 - 2019  <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "DOALL.hpp"
#include "DOALLTask.hpp"

namespace llvm::noelle { 

void DOALL::rewireLoopToIterateChunks (
  LoopDependenceInfo *LDI
  ){

  /*
   * Fetch the task.
   */
  auto task = (DOALLTask *)tasks[0];

  /*
   * Fetch loop and IV information.
   */
  auto invariantManager = LDI->getInvariantManager();
  auto loopSummary = LDI->getLoopStructure();
  auto loopHeader = loopSummary->getHeader();
  auto loopPreHeader = loopSummary->getPreHeader();
  auto preheaderClone = task->getCloneOfOriginalBasicBlock(loopPreHeader);
  auto headerClone = task->getCloneOfOriginalBasicBlock(loopHeader);
  auto allIVInfo = LDI->getInductionVariableManager();

  /*
   * Hook up preheader to header to enable induction variable manipulation
   */
  IRBuilder<> entryBuilder(task->getEntry());
  auto temporaryBrToLoop = entryBuilder.CreateBr(headerClone);
  entryBuilder.SetInsertPoint(temporaryBrToLoop);

  /*
   * Generate PHI to track progress on the current chunk
   */
  auto chunkCounterType = task->chunkSizeArg->getType();
  auto chunkPHI = IVUtility::createChunkPHI(preheaderClone, headerClone, chunkCounterType, task->chunkSizeArg);

  /*
   * Collect clones of step size deriving values for all induction variables
   * of the top level loop
   */
  auto clonedStepSizeMap = this->cloneIVStepValueComputation(LDI, 0, entryBuilder);

  /*
   * Determine start value of the IV for the task
   * core_start: original_start + original_step_size * core_id * chunk_size
   */
  for (auto ivInfo : allIVInfo->getInductionVariables(*loopSummary)) {
    auto startOfIV = fetchClone(ivInfo->getStartValue());
    auto stepOfIV = clonedStepSizeMap.at(ivInfo);
    auto ivPHI = cast<PHINode>(fetchClone(ivInfo->getLoopEntryPHI()));

    auto nthCoreOffset = entryBuilder.CreateMul(
      stepOfIV,
      entryBuilder.CreateZExtOrTrunc(
        entryBuilder.CreateMul(task->coreArg, task->chunkSizeArg, "coreIdx_X_chunkSize"),
        stepOfIV->getType()
      ),
      "stepSize_X_coreIdx_X_chunkSize"
    );

    auto offsetStartValue = IVUtility::offsetIVPHI(preheaderClone, ivPHI, startOfIV, nthCoreOffset);
    ivPHI->setIncomingValueForBlock(preheaderClone, offsetStartValue);
  }

  /*
   * Determine additional step size from the beginning of the next core's chunk
   * to the start of this core's next chunk
   * chunk_step_size: original_step_size * (num_cores - 1) * chunk_size
   */
  for (auto ivInfo : allIVInfo->getInductionVariables(*loopSummary)) {
    auto stepOfIV = clonedStepSizeMap.at(ivInfo);
    auto ivPHI = cast<PHINode>(fetchClone(ivInfo->getLoopEntryPHI()));
    auto onesValueForChunking = ConstantInt::get(chunkCounterType, 1);
    auto chunkStepSize = entryBuilder.CreateMul(
      stepOfIV,
      entryBuilder.CreateZExtOrTrunc(
        entryBuilder.CreateMul(
          entryBuilder.CreateSub(task->numCoresArg, onesValueForChunking, "numCoresMinus1"),
          task->chunkSizeArg,
          "numCoresMinus1_X_chunkSize"
        ),
        stepOfIV->getType()
      ),
      "stepSizeToNextChunk"
    );

    IVUtility::chunkInductionVariablePHI(preheaderClone, ivPHI, chunkPHI, chunkStepSize);
  }

  /*
   * The exit condition needs to be made non-strict to catch iterating past it
   */
  auto loopGoverningIVAttr = LDI->getLoopGoverningIVAttribution();
  LoopGoverningIVUtility ivUtility(loopSummary, *allIVInfo, *loopGoverningIVAttr);
  auto cmpInst = cast<CmpInst>(task->getCloneOfOriginalInstruction(loopGoverningIVAttr->getHeaderCmpInst()));
  auto brInst = cast<BranchInst>(task->getCloneOfOriginalInstruction(loopGoverningIVAttr->getHeaderBrInst()));
  auto basicBlockToJumpToWhenTheLoopEnds = task->getLastBlock(0);
  ivUtility.updateConditionAndBranchToCatchIteratingPastExitValue(cmpInst, brInst, basicBlockToJumpToWhenTheLoopEnds);
  auto updatedCmpInst = cmpInst;

  /*
   * The exit condition value does not need to be computed each iteration and so the value's derivation can be hoisted into the preheader.
   * 
   * Instructions that the PDG states are independent can include PHI nodes.
   * Assert that any PHIs are invariant. Hoist one of those values (if instructions) to the preheader.
   */
  auto exitConditionValue = fetchClone(loopGoverningIVAttr->getExitConditionValue());
  if (auto exitConditionInst = dyn_cast<Instruction>(exitConditionValue)) {
    auto &derivation = ivUtility.getConditionValueDerivation();
    for (auto I : derivation) {
      assert(invariantManager->isLoopInvariant(I)
        && "DOALL exit condition value is not derived from loop invariant values!");

      /*
       * Fetch the clone of @I
       */
      auto cloneI = task->getCloneOfOriginalInstruction(I);

      if (auto clonePHI = dyn_cast<PHINode>(cloneI)) {
        auto usedValue = clonePHI->getIncomingValue(0);
        clonePHI->replaceAllUsesWith(usedValue);
        clonePHI->eraseFromParent();
        cloneI = dyn_cast<Instruction>(usedValue);
        if (!cloneI) {
          continue;
        }
      }

      cloneI->removeFromParent();
      entryBuilder.Insert(cloneI);
    }

    exitConditionInst->removeFromParent();
    entryBuilder.Insert(exitConditionInst);
  }

  /*
   * NOTE: When loop governing IV attribution allows for any other instructions in the header
   * other than those of the IV and its comparison, those unrelated instructions should be
   * copied into the body and the exit block (to preserve the number of times they execute)
   * 
   * The logic in the exit block must be guarded so only the "last" iteration executes it,
   * not any cores that pass the last iteration. This is further complicated because the mapping
   * of live-out environment producing instructions might need to be updated with the peeled
   * instructions in the exit block
   * 
   * A temporary mitigation is to transform loop latches with conditional branches that
   * verify if the next iteration would ever occur. This still requires live outs to be propagated
   * from both the header and the latches
   */

  /*
	 * Identify any instructions in the header that are NOT sensitive to the number of times they execute:
	 * 1) IV instructions, including the comparison and branch of the loop governing IV
	 * 2) The PHI used to chunk iterations 
	 * 3) Any PHIs of reducible variables
	 * 4) Any loop invariant instructions that belong to independent-execution SCCs
   */
  std::set<Instruction *> repeatableInstructions;

	/*
	 * Collect (1) by iterating the InductionVariableManager
	 */
  auto sccManager = LDI->getSCCManager();
  auto sccdag = sccManager->getSCCDAG();
  for (auto ivInfo : allIVInfo->getInductionVariables(*loopSummary)) {
    for (auto I : ivInfo->getAllInstructions()) {
      repeatableInstructions.insert(task->getCloneOfOriginalInstruction(I));
    }
  }
  repeatableInstructions.insert(cmpInst);
  repeatableInstructions.insert(brInst);

	/*
	 * Collect (2)
	 */
  repeatableInstructions.insert(chunkPHI);

	/*
	 * Collect (3) by identifying all reducible SCCs
	 */
  auto nonDOALLSCCs = sccManager->getSCCsWithLoopCarriedDataDependencies();
  for (auto scc : nonDOALLSCCs) {
    auto sccInfo = sccManager->getSCCAttrs(scc);
    if (!sccInfo->canExecuteReducibly()) continue;

    // HACK:
    for (auto nodePair : scc->internalNodePairs()) {
      auto value = nodePair.first;
      auto inst = cast<Instruction>(value);
      if (inst->getParent() != loopHeader) continue;

      auto instClone = task->getCloneOfOriginalInstruction(inst);
      repeatableInstructions.insert(instClone);
    }

    // assert(sccInfo->getSingleHeaderPHI());
    // repeatableInstructions.insert(task->getCloneOfOriginalInstruction(sccInfo->getSingleHeaderPHI()));
  }

	/*
	 * Collect (4) by identifying header instructions belonging to independent SCCs that are loop invariant
	 */
  for (auto &I : *loopHeader) {
		auto scc = sccdag->sccOfValue(&I);
    auto sccInfo = sccManager->getSCCAttrs(scc);
		if (!sccInfo->canExecuteIndependently()) continue;

    auto isInvariant = invariantManager->isLoopInvariant(&I);
    if (!isInvariant) continue;

		repeatableInstructions.insert(task->getCloneOfOriginalInstruction(&I));
	}

  /*
   * Check if we need to check whether we need to add a condition to execute instructions in the new header for tasks that are executing the header in iterations after the last one.
   */
  auto requiresConditionBeforeEnteringHeader = false;
  for (auto &I : *headerClone) {
    if (repeatableInstructions.find(&I) == repeatableInstructions.end()) {
      requiresConditionBeforeEnteringHeader = true;
      break;
    }
  }
  if (!requiresConditionBeforeEnteringHeader) {
    return ;
  }

  /*
   * The new header includes instructions that should be executed only if we know that we didn't pass the last iteration.
   * Hence, we need to add code to check this condition before entering the header.
   * Such code needs to be added for all predecessors of the header: pre-header and latches.
   *
   * Fetch the required information to generate the code.
   */
  auto &loopGoverningIV = loopGoverningIVAttr->getInductionVariable();
  auto loopGoverningPHI = task->getCloneOfOriginalInstruction(loopGoverningIV.getLoopEntryPHI());
  auto origValueUsedToCompareAgainstExitConditionValue = loopGoverningIVAttr->getValueToCompareAgainstExitConditionValue();
  auto valueUsedToCompareAgainstExitConditionValue = task->getCloneOfOriginalInstruction(origValueUsedToCompareAgainstExitConditionValue);
  assert(valueUsedToCompareAgainstExitConditionValue != nullptr);
  auto stepSize = clonedStepSizeMap.at(&loopGoverningIV);

  /*
   * In each latch, check whether we passed the last iteration.
   */
  for (auto latch : loopSummary->getLatches()) {

    /*
     * Fetch the latch in the loop within the task.
     */
    auto cloneLatch = task->getCloneOfOriginalBasicBlock(latch);

    /*
     * Remove the old terminator because it will replace with the check.
     */
    auto latchTerminator = cloneLatch->getTerminator();
    latchTerminator->eraseFromParent();
    IRBuilder<> latchBuilder(cloneLatch);

    /*
     * Fetch the value of the loop governing IV that would have been used to check whether the previous iteration was the last one.
     * To do so, we need to fetch the value of the loop-governing IV updated by the current iteration, which could be the IV value after updating it by adding the chunking size.
     * So for example, if 
     * - the current core excuted the iterations 0, 1, and 2 and 
     * - the chunking size is 3 and 
     * - there are 2 cores, then 
     * at the end of the iteration 2 (i.e., at the latch) of core 0 the updated loop-governing IV is 
     *   2 (the current value used in the compare instruction) 
     * + 1 (the normal IV increment) 
     * + 3 (the chunking size) * (2 - 1) (the other cores) 
     * ----
     *   6
     * 
     * The problem is that we don't know if the header of the iteration 6 should be executed at all as the loop might have ended at an earlier iteration (e.g., 4).
     * So we need to check whether the previous iteration (5 in the example) was actually executed.
     * To this end, we need to compare the previous iteration IV value (e.g., 5) against the exit condition.
     *
     * Fetch the updated loop-governing IV (6 in the example above).
     */
    auto currentIVValue = cast<PHINode>(loopGoverningPHI)->getIncomingValueForBlock(cloneLatch);

    /*
     * Compute the value that this IV had at the iteration before (5 in the example above).
     */
    auto prevIterationValue = ivUtility.generateCodeToComputePreviousValueUsedToCompareAgainstExitConditionValue(latchBuilder, currentIVValue, cloneLatch, stepSize);

    /*
     * Compare the previous-iteration IV value against the exit condition
     */
    auto clonedCmpInst = updatedCmpInst->clone();
    clonedCmpInst->replaceUsesOfWith(valueUsedToCompareAgainstExitConditionValue, prevIterationValue);
    latchBuilder.Insert(clonedCmpInst);
    latchBuilder.CreateCondBr(clonedCmpInst, task->getLastBlock(0), headerClone);
  }

  /*
   * In the preheader, assert that either the first iteration is being executed OR
   * that the previous iteration would have executed. The reason we must also check
   * if this is the first iteration is if the IV condition is such that <= 1
   * iteration would ever occur
   */
  auto preheaderTerminator = preheaderClone->getTerminator();
  preheaderTerminator->eraseFromParent();
  IRBuilder<> preheaderBuilder(preheaderClone);
  auto offsetStartValue = cast<PHINode>(loopGoverningPHI)->getIncomingValueForBlock(preheaderClone);
  auto prevIterationValue = ivUtility.generateCodeToComputeValueToUseForAnIterationAgo(preheaderBuilder, offsetStartValue, stepSize);

  auto clonedExitCmpInst = updatedCmpInst->clone();
  clonedExitCmpInst->replaceUsesOfWith(valueUsedToCompareAgainstExitConditionValue, prevIterationValue);
  preheaderBuilder.Insert(clonedExitCmpInst);

  auto startValue = fetchClone(loopGoverningIV.getStartValue());
  auto isNotFirstIteration = preheaderBuilder.CreateICmpNE(offsetStartValue, startValue);
  preheaderBuilder.CreateCondBr(
    preheaderBuilder.CreateAnd(isNotFirstIteration, clonedExitCmpInst),
    task->getExit(),
    headerClone
  );

  return ;
}

}


<|start_filename|>src/core/induction_variables/include/InductionVariables.hpp<|end_filename|>
/*
 * Copyright 2016 - 2021  <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#pragma once

#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "ScalarEvolutionReferencer.hpp"
#include "SystemHeaders.hpp"
#include "SCCDAG.hpp"
#include "SCC.hpp"
#include "LoopsSummary.hpp"
#include "LoopEnvironment.hpp"
#include "DominatorSummary.hpp"
#include "Invariants.hpp"

namespace llvm::noelle {

  class LoopGoverningIVAttribution;

  class InductionVariable {
    public:

      InductionVariable  (
          LoopStructure *LS,
          InvariantManager &IVM,
          ScalarEvolution &SE,
          PHINode *loopEntryPHI,
          SCC &scc,
          LoopEnvironment &loopEnvironment,
          ScalarEvolutionReferentialExpander &referentialExpander
          ) ;

      SCC * getSCC (void) const ;

      PHINode * getLoopEntryPHI (void) const ;

      std::unordered_set<PHINode *> getPHIs (void) const ;

      std::unordered_set<Instruction *> getNonPHIIntermediateValues (void) const ;

      std::unordered_set<Instruction *> getAllInstructions (void) const ;

      std::unordered_set<Instruction *> getDerivedSCEVInstructions (void) const ;

      Value * getStartValue (void) const;

      Value * getSingleComputedStepValue (void) const;

      std::vector<Instruction *> getComputationOfStepValue (void) const;

      bool isStepValueLoopInvariant (void) const;

      bool isStepValuePositive (void) const ;

      const SCEV * getStepSCEV (void) const;

      bool isIVInstruction (Instruction *I) const;

      bool isDerivedFromIVInstructions (Instruction *I) const;

      ~InductionVariable ();

    private:

      /*
       * The SCC that contains the induction variable
       */
      SCC &scc;

      /*
       * The loop entry PHI node. For normalized loops with a single header,
       * this PHI is the destination of all loop carried dependencies for the IV
       */
      PHINode *loopEntryPHI;

      /*
       * All PHIs, whether intermediate or the loop entry PHI
       */
      std::unordered_set<PHINode *> PHIs;

      /*
       * All non-PHI intermediate values of the IV
       */
      std::unordered_set<Instruction *> nonPHIIntermediateValues;

      /*
       * All PHI/non-PHI intermediate values AND all casts of the IV
       */
      std::unordered_set<Instruction *> allInstructions;

      /*
       * Derived SCEV instructions relying solely on loop invariants, constants, and this IV
       */
      std::unordered_set<Instruction *> derivedSCEVInstructions;

      /*
       * Start value (the incoming value to the loop entry PHI from the preheader)
       */
      Value *startValue;

      /*
       * The SCEV representing the step recurrence
       */
      const SCEV *stepSCEV;

      /*
       * A single constant or loop external value representing the step recurrence
       */
      Value *singleStepValue;

      /*
       * The values, in order of execution, used to compute the step recurrence
       * The last value is the step value between iterations
       * NOTE: these values expand the step SCEV so that all uses in the values are
       * 1) loop invariant and loop external
       * OR
       * 2) derived from another induction variable in the loop
       * 
       * TODO: Imply in name that this computation is a list of instructions, and
       * that if the value need not be computed and can instead be referenced, this
       * list will be empty
       */
      std::vector<Instruction *> computationOfStepValue;

      /*
       * Whether the computed step value's uses are all loop invariant/external
       */
      bool isComputedStepValueLoopInvariant;

      /*
       * Helper functions and structures
       */ 
      std::set<Value *> valuesToReferenceInComputingStepValue;
      std::set<Value *> valuesInScopeOfInductionVariable;
      void collectValuesInternalAndExternalToLoopAndSCC (
          LoopStructure *LS,
          LoopEnvironment &loopEnvironment
          ) ;

      void deriveStepValue (
          LoopStructure *LS,
          ScalarEvolution &SE,
          ScalarEvolutionReferentialExpander &referentialExpander,
          LoopEnvironment &loopEnv
          ) ;

      void deriveStepValueFromSCEVConstant (const SCEVConstant *scev) ;
      void deriveStepValueFromSCEVUnknown (const SCEVUnknown *scev, LoopStructure *LS) ;
      bool deriveStepValueFromCompositeSCEV (
          const SCEV *scev,
          ScalarEvolutionReferentialExpander &referentialExpander,
          LoopStructure *LS
          ) ;

      void traverseCycleThroughLoopEntryPHIToGetAllIVInstructions () ;

      void traverseConsumersOfIVInstructionsToGetAllDerivedSCEVInstructions (
          LoopStructure *LS,
          InvariantManager &IVM,
          ScalarEvolution &SE
          ) ;

  };

  class InductionVariableManager {
    public:

      InductionVariableManager (
          LoopsSummary &LIS,
          InvariantManager &IVM,
          ScalarEvolution &SE,
          SCCDAG &sccdag,
          LoopEnvironment &loopEnv
          );

      InductionVariableManager () = delete;

      /*
       * Return all induction variables including the loop-governing one of the outermost loop of the loop sub-tree related to @this.
       */
      std::unordered_set<InductionVariable *> getInductionVariables (void) const ;

      /*
       * Return all induction variables including the loop-governing one.
       */
      std::unordered_set<InductionVariable *> getInductionVariables (LoopStructure &LS) const ;

      /*
       * Return all induction variables that @i is involved in for any loop/sub-loop related to this manager.
       */
      std::unordered_set<InductionVariable *> getInductionVariables (Instruction *i) const ;

      InductionVariable * getInductionVariable (LoopStructure &LS, Instruction *i) const ;

      InductionVariable * getLoopGoverningInductionVariable (LoopStructure &LS) const ;

      bool doesContributeToComputeAnInductionVariable (Instruction *i) const ;

      LoopGoverningIVAttribution * getLoopGoverningIVAttribution (LoopStructure &LS) const ;

      InductionVariable * getDerivingInductionVariable (LoopStructure &LS, Instruction *derivedInstruction) const ;

      ~InductionVariableManager ();

    private:
      LoopsSummary &LIS;
      std::unordered_map<LoopStructure *, std::unordered_set<InductionVariable *>> loopToIVsMap;
      std::unordered_map<LoopStructure *, LoopGoverningIVAttribution *> loopToGoverningIVAttrMap;
  };

}


<|start_filename|>src/tools/enablers/src/Enablers.cpp<|end_filename|>
/*
 * Copyright 2019 - 2021 <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "EnablersManager.hpp"

namespace llvm::noelle {

  bool EnablersManager::applyEnablers (
      LoopDependenceInfo *LDI,
      Noelle &par,
      LoopDistribution &loopDist,
      LoopUnroll &loopUnroll,
      LoopWhilifier &loopWhilifier,
      LoopInvariantCodeMotion &loopInvariantCodeMotion,
      SCEVSimplification &scevSimplification
      ){

    /*
     * Apply loop distribution.
     */
    if (par.isTransformationEnabled(Transformation::LOOP_DISTRIBUTION_ID)){
      errs() << "EnablersManager:     Try to apply loop distribution\n";
      if (this->applyLoopDistribution(LDI, par, loopDist)){
        errs() << "EnablersManager:       Distributed loop\n";
        return true;
      }
    }

    /*
     * Try to devirtualize functions.
     */
    if (par.isTransformationEnabled(Transformation::DEVIRTUALIZER_ID)){
      errs() << "EnablersManager:     Try to devirtualize indirect calls\n";
      if (this->applyDevirtualizer(LDI, par, loopUnroll)){
        errs() << "EnablersManager:       Some calls have been devirtualized\n";
        return true;
      }
    }

    /*
     * Run the whilifier.
     */
    if (par.isTransformationEnabled(Transformation::LOOP_WHILIFIER_ID)){
      errs() << "EnablersManager:     Try to whilify loops\n";
      if (this->applyLoopWhilifier(LDI, par, loopWhilifier)){
        errs() << "EnablersManager:       The loop has been whilified\n";
        return true;
      }
    }

    /*
     * Run the extraction.
     */
    if (par.isTransformationEnabled(Transformation::LOOP_INVARIANT_CODE_MOTION_ID)){
      errs() << "EnablersManager:     Try to extract invariants out of loops\n";
      if (loopInvariantCodeMotion.extractInvariantsFromLoop(*LDI)){
        errs() << "EnablersManager:       Loop invariants have been extracted\n";
        return true;
      }
    }

    /*
     * Run the SCEV simplification pass
     */
    if (par.isTransformationEnabled(Transformation::SCEV_SIMPLIFICATION_ID)){
      errs() << "EnablersManager:     Try to simplify IV related SCEVs and their corresponding instructions in loops\n";
      if (scevSimplification.simplifyIVRelatedSCEVs(*LDI)){
        /*auto function = LDI->getLoopStructure()->getFunction();
          auto& SE = getAnalysis<ScalarEvolutionWrapperPass>(*function).getSE();
          if (scevSimplification.simplifyLoopGoverningIVGuards(*LDI, SE)){*/
        errs() << "EnablersManager:       Loop IV related SCEVs have been simplified\n";
        return true;
      }
      errs() << "EnablersManager:     Try to simplify constant SCEVs and their corresponding instructions in loops\n";
      if (scevSimplification.simplifyConstantPHIs(*LDI)){
        errs() << "EnablersManager:       Loop constant PHIs have been simplified\n";
        return true;
      }
      }

      return false;
    }

    bool EnablersManager::applyLoopWhilifier (
        LoopDependenceInfo *LDI,
        Noelle &par,
        LoopWhilifier &loopWhilifier
        ){
      assert(LDI != nullptr);

      /*
       * Check if we need to whilify the loop.
       */
      auto loopStructure = LDI->getLoopStructure();
      auto loopGoverningIVAttr = LDI->getLoopGoverningIVAttribution();
      if (  true
          && (loopGoverningIVAttr != nullptr)
          && (loopStructure->numberOfExitBasicBlocks() == 1)
         ){

        /*
         * The prologue is empty and the loop is in while form already.
         */
        return false;
      }

      /*
       * Whilify the loop
       */
      auto modified = loopWhilifier.whilifyLoop(*LDI);

      return modified;
    }

    bool EnablersManager::applyLoopDistribution (
        LoopDependenceInfo *LDI,
        Noelle &par,
        LoopDistribution &loopDist
        ){

      /*
       * Fetch the SCC manager.
       */
      auto sccManager = LDI->getSCCManager();

      /*
       * Fetch the SCCDAG of the loop.
       */
      auto SCCDAG = sccManager->getSCCDAG();

      /*
       * Define the set of SCCs to bring outside the loop.
       */
      std::set<SCC *> SCCsToBringOutsideParallelizedLoop{};

      /*
       * Collect all sequential SCCs.
       */
      std::set<SCC *> sequentialSCCs{};
      auto collectSequentialSCCsFunction = [sccManager,&sequentialSCCs](SCC *currentSCC) -> bool {

        /*
         * Fetch the SCC metadata.
         */
        auto sccInfo = sccManager->getSCCAttrs(currentSCC);

        /*
         * Check if the current SCC can be removed (e.g., because it is due to induction variables).
         * If it is, then we do not need to remove it from the loop to be parallelized.
         */
        if (  false
            || (!sccInfo->mustExecuteSequentially())
            || (sccInfo->canBeCloned())
            || (sccInfo->canBeClonedUsingLocalMemoryLocations())
           ){
          return false;
        }

        /*
         * The current SCC must run sequentially.
         */
        sequentialSCCs.insert(currentSCC);
        return false;
      } ;
      SCCDAG->iterateOverSCCs(collectSequentialSCCsFunction);

      /*
       * Check every sequential SCC of the loop and decide which ones to bring outside the loop to parallelize.
       */
      for (auto SCC : sequentialSCCs){

        /*
         * Try to bring the sequential SCC outside the loop.
         */
        std::set<Instruction *> instsRemoved;
        std::set<Instruction *> instsAdded;
        auto splitted = loopDist.splitLoop(*LDI, SCC, instsRemoved, instsAdded);
        if (!splitted){
          continue ;
        }

        /*
         * The SCC has been pulled out the loop.
         * We need to update all metadata about loops.
         * To do so, we currently quit and rerun noelle-enable
         */
        return true;
      }

      return false;
    }

    bool EnablersManager::applyDevirtualizer (
        LoopDependenceInfo *LDI,
        Noelle &par,
        LoopUnroll &loopUnroll
        ){

      /*
       * We want to fully unroll a loop if this can help the parallelization of an outer loop that includes it.
       *
       * One condition that allow this improvement is when the inner loop iterates over function pointers.
       * For example:
       * while (...){
       *    for (auto i=0; i < 10; i++){
       *      auto functionPtr = array[i];
       *      (*functionPtr)(...)
       *    }
       * }
       */

      /*
       * Fetch the loop information.
       */
      auto ls = LDI->getLoopStructure();
      auto IVM = LDI->getInductionVariableManager();

      /*
       * Check if the loop includes at least one call to unknown callee.
       */
      auto fullyUnroll = false;
      for (auto bb : ls->getBasicBlocks()){
        for (auto& inst : *bb){

          /*
           * Check if the instruction is a call one.
           */
          if (!isa<CallInst>(&inst)){
            continue ;
          }
          auto callInst = cast<CallInst>(&inst);

          /*
           * Check if the callee is known.
           */
          auto callee = callInst->getCalledFunction();
          if (callee != nullptr){
            continue ;
          }

          /*
           * The callee is unknown.
           *
           * Check if the callee is determined by the result of a load instruction.
           */
          auto calleePtr = callInst->getCalledOperand();
          if (!isa<LoadInst>(calleePtr)){
            continue ;
          }
          auto loadInst = cast<LoadInst>(calleePtr);

          /*
           * Check if the address of the load instruction is the result of a GEP.
           */
          auto addr = loadInst->getPointerOperand();
          if (!isa<GetElementPtrInst>(addr)){
            continue ;
          }
          auto addrComputation = cast<GetElementPtrInst>(addr);

          /*
           * Check if the GEP relies on an induction variable.
           */
          for (auto& idx : addrComputation->indices()){
            if (!isa<Instruction>(idx)){
              continue ;
            }
            auto instIdx = cast<Instruction>(idx);
            if (IVM->doesContributeToComputeAnInductionVariable(instIdx)){
              fullyUnroll = true;
              break ;
            }
          }
          if (fullyUnroll){
            break ;
          }
        }
      }
      if (!fullyUnroll){
        return false;
      }

      /*
       * Fully unroll the loop.
       */
      auto &loopFunction = *ls->getFunction();
      auto& LS = getAnalysis<LoopInfoWrapperPass>(loopFunction).getLoopInfo();
      auto& DT = getAnalysis<DominatorTreeWrapperPass>(loopFunction).getDomTree();
      auto& SE = getAnalysis<ScalarEvolutionWrapperPass>(loopFunction).getSE();
      auto& AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(loopFunction);
      auto modified = loopUnroll.fullyUnrollLoop(*LDI, LS, DT, SE, AC);

      return modified;
    }

  }


<|start_filename|>src/core/induction_variables/src/IVStepperUtility.cpp<|end_filename|>
/*
 * Copyright 2016 - 2021  <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "IVStepperUtility.hpp"

namespace llvm::noelle{

PHINode *IVUtility::createChunkPHI (BasicBlock *preheaderB, BasicBlock *headerB, Type *chunkPHIType, Value *chunkSize) {

  // TODO: Add asserts to ensure the basic blocks/terminators are well formed

  std::vector<BasicBlock *> headerPreds(pred_begin(headerB), pred_end(headerB));
  IRBuilder<> headerBuilder(headerB->getFirstNonPHIOrDbgOrLifetime());
  auto chunkPHI = headerBuilder.CreatePHI(chunkPHIType, headerPreds.size());
  auto zeroValueForChunking = ConstantInt::get(chunkPHIType, 0);
  auto onesValueForChunking = ConstantInt::get(chunkPHIType, 1);

  for (auto B : headerPreds) {
    IRBuilder<> latchBuilder(B->getTerminator());

    if (preheaderB == B) {
      chunkPHI->addIncoming(zeroValueForChunking, B);
    } else {
      auto chunkIncrement = latchBuilder.CreateAdd(chunkPHI, onesValueForChunking);
      auto isChunkCompleted = latchBuilder.CreateICmp(CmpInst::Predicate::ICMP_EQ, chunkIncrement, chunkSize);
      auto chunkWrap = latchBuilder.CreateSelect(isChunkCompleted, zeroValueForChunking, chunkIncrement, "chunkWrap");
      chunkPHI->addIncoming(chunkWrap, B);
    }
  }

  return chunkPHI;
}

void IVUtility::chunkInductionVariablePHI(
  BasicBlock *preheaderBlock,
  PHINode *ivPHI,
  PHINode *chunkPHI,
  Value *chunkStepSize
) {

  for (auto i = 0; i < ivPHI->getNumIncomingValues(); ++i) {
    auto B = ivPHI->getIncomingBlock(i);
    IRBuilder<> latchBuilder(B->getTerminator());
    if (preheaderBlock == B) continue;

    auto chunkIncomingIdx = chunkPHI->getBasicBlockIndex(B);
    Value *isChunkCompleted = cast<SelectInst>(chunkPHI->getIncomingValue(chunkIncomingIdx))->getCondition();

    auto initialLatchValue = ivPHI->getIncomingValue(i);
    auto ivOffsetByChunk = offsetIVPHI(B, ivPHI, initialLatchValue, chunkStepSize);

    /*
     * Iterate to next chunk if necessary
     */
    ivPHI->setIncomingValue(i, latchBuilder.CreateSelect(
      isChunkCompleted,
      ivOffsetByChunk,
      initialLatchValue, 
      "nextStepOrNextChunk"
    ));

  }
}

void IVUtility::stepInductionVariablePHI (
  BasicBlock *preheaderBlock,
  PHINode *ivPHI,
  Value *additionalStepSize
) {

  for (auto i = 0; i < ivPHI->getNumIncomingValues(); ++i) {
    auto B = ivPHI->getIncomingBlock(i);
    if (preheaderBlock == B) {
      continue;
    }

    auto prevStepRecurrence = ivPHI->getIncomingValue(i);
    auto batchStepRecurrence = offsetIVPHI(B, ivPHI, prevStepRecurrence, additionalStepSize);
    ivPHI->setIncomingValue(i, batchStepRecurrence);
  }

  return ;
}

Value *IVUtility::offsetIVPHI (
  BasicBlock *insertBlock,
  PHINode *ivPHI,
  Value *startValue,
  Value *offsetValue
) {

  IRBuilder<> insertBuilder(insertBlock->getTerminator());
  Value *offsetStartValue = nullptr;

  /*
   * For pointer arithmetic, use ptrtoint - inttoptr paradigm
   */
  auto ivType = ivPHI->getType();
  if (ivType->isPointerTy()) {
    offsetStartValue = insertBuilder.CreateIntToPtr(
      insertBuilder.CreateAdd(
        insertBuilder.CreatePtrToInt(
          startValue,
          offsetValue->getType()
        ),
        offsetValue
      ),
      ivType
    );

  } else {
    offsetStartValue = insertBuilder.CreateAdd(startValue, offsetValue);
  }

  return offsetStartValue;
}

}


<|start_filename|>src/tools/helix/src/HELIX.cpp<|end_filename|>
/*
 * Copyright 2016 - 2019  <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "HELIX.hpp"
#include "HELIXTask.hpp"

namespace llvm::noelle{

HELIX::HELIX (
  Module &module, 
  Hot &p,
  bool forceParallelization,
  Verbosity v
  )
  : ParallelizationTechniqueForLoopsWithLoopCarriedDataDependences{module, p, forceParallelization, v},
    loopCarriedEnvBuilder{nullptr}, 
    taskFunctionDG{nullptr},
    lastIterationExecutionBlock{nullptr},
    enableInliner{true}
  {

  /*
   * Fetch the LLVM context.
   */
  auto &cxt = module.getContext();

  /*
   * Fetch the dispatcher to use to jump to a parallelized HELIX loop.
   */
  this->taskDispatcherSS = this->module.getFunction("NOELLE_HELIX_dispatcher_sequentialSegments");
  assert(this->taskDispatcherSS != nullptr);
  this->taskDispatcherCS = this->module.getFunction("NOELLE_HELIX_dispatcher_criticalSections");
  assert(this->taskDispatcherCS != nullptr);
  this->waitSSCall = this->module.getFunction("HELIX_wait");
  this->signalSSCall =  this->module.getFunction("HELIX_signal");
  if (!this->waitSSCall  || !this->signalSSCall) {
    errs() << "HELIX: ERROR = sync functions HELIX_wait, HELIX_signal were not both found.\n";
    abort();
  }

  /*
   * Fetch the LLVM types of the HELIX_dispatcher arguments.
   */
  auto int8 = IntegerType::get(cxt, 8);
  auto int64 = IntegerType::get(cxt, 64);

  /*
   * Create the LLVM signature of HELIX_dispatcher.
   */
  auto funcArgTypes = ArrayRef<Type*>({
    PointerType::getUnqual(int8),
    PointerType::getUnqual(int8),
    PointerType::getUnqual(int8),
    PointerType::getUnqual(int8),
    int64,
    int64,
    PointerType::getUnqual(int64)
  });
  this->taskSignature = FunctionType::get(Type::getVoidTy(cxt), funcArgTypes, false);

  return ;
}

void HELIX::reset () {
  ParallelizationTechnique::reset();
  if (loopCarriedEnvBuilder) {
    delete loopCarriedEnvBuilder;
  }

  if (taskFunctionDG) {
    delete taskFunctionDG;
  }

  for (auto spill : spills) {
    delete spill;
  }
  spills.clear();

  if (this->lastIterationExecutionBlock) {
    this->lastIterationExecutionBlock = nullptr;
  }
  lastIterationExecutionDuplicateMap.clear();

}

bool HELIX::canBeAppliedToLoop (LoopDependenceInfo *LDI, Noelle &par, Heuristics *h) const {

  /*
   * Check the parent class.
   */
  if (!ParallelizationTechniqueForLoopsWithLoopCarriedDataDependences::canBeAppliedToLoop(LDI, par, h)){
    return false;
  }

  /*
   * Check if we are forced to parallelize
   */
  if (this->forceParallelization){

    /*
     * HELIX is applicable.
     */
    return true;
  }

  /*
   * Ensure there is not too little execution that is too proportionally sequential for HELIX 
   */
  auto profiles = par.getProfiles();
  auto loopID = LDI->getID();
  auto loopStructure = LDI->getLoopStructure();
  auto averageInstructions = profiles->getAverageTotalInstructionsPerIteration(loopStructure);
  auto averageInstructionThreshold = 20;
  bool hasLittleExecution = averageInstructions < averageInstructionThreshold;
  auto maximumSequentialFraction = .2;
  auto sequentialFraction = this->computeSequentialFractionOfExecution(LDI, par);
  bool hasProportionallySignificantSequentialExecution = sequentialFraction >= maximumSequentialFraction;
  if (hasLittleExecution && hasProportionallySignificantSequentialExecution) {
    errs() << "Parallelizer:    Loop " << loopID << " has "
      << averageInstructions << " number of sequential instructions on average per loop iteration\n";
    errs() << "Parallelizer:    Loop " << loopID << " has "
      << sequentialFraction << " % sequential execution per loop iteration\n";
    errs() << "Parallelizer:      It will be too heavily synchronized for HELIX. The thresholds are at least "
      << averageInstructionThreshold << " instructions per iteration or less than "
      << maximumSequentialFraction << " % sequential execution." << "\n";

    return false;
  }

  return true ;
}

bool HELIX::apply (
  LoopDependenceInfo *LDI,
  Noelle &par,
  Heuristics *h
) {

  /*
   * If a task has not been defined, create such a task from the
   * loop dependence info of the original function's loop
   * Otherwise, add synchronization to the already defined task
   * using the loop dependence info for that task
   */
  if (this->tasks.size() == 0) {
    this->createParallelizableTask(LDI, par, h);
    return true;
  }

  auto modified = this->synchronizeTask(LDI, par, h);

  return modified;
}

void HELIX::createParallelizableTask (
  LoopDependenceInfo *LDI,
  Noelle &par, 
  Heuristics *h
){

  /*
   * Fetch the header.
   */
  auto loopStructure = LDI->getLoopStructure();
  auto loopHeader = loopStructure->getHeader();

  /*
   * Fetch the SCC manager.
   */
  auto sccManager = LDI->getSCCManager();

  /*
   * NOTE: Keep around the original loops' LoopDependenceInfo for later phases
   * //TODO: we need to specify why this is necessary
   */
  this->originalLDI = LDI;

  /*
   * Print the parallelization request.
   */
  if (this->verbose != Verbosity::Disabled) {
    errs() << "HELIX: Start the parallelization\n";
    auto nonDOALLSCCs = sccManager->getSCCsWithLoopCarriedDependencies();
    for (auto scc : nonDOALLSCCs) {

      /*
       * Fetch the SCC metadata.
       */
      auto sccInfo = sccManager->getSCCAttrs(scc);

      /*
       * Check the SCC.
       */
      if (sccInfo->canExecuteReducibly()){
        continue ;
      }
      if (sccInfo->canBeCloned()){
        continue ;
      }
      if (LDI->isSCCContainedInSubloop(scc)) {
        continue ;
      }

      /*
       * The current SCC needs to create a sequential segment.
       */
      errs() << "HELIX:   We found an SCC of type " << sccInfo->getType() << " of the loop that is non clonable and non commutative\n" ;
      if (this->verbose >= Verbosity::Maximal) {
        // errs() << "HELIX:     SCC:\n";
        // scc->printMinimal(errs(), "HELIX:       ") ;
        errs() << "HELIX:       Loop-carried dependences\n";
        sccManager->iterateOverLoopCarriedDependences(scc, [](DGEdge<Value> *dep) -> bool {
          auto fromInst = dep->getOutgoingT();
          auto toInst = dep->getIncomingT();
          errs() << "HELIX:       " << *fromInst << " ---> " << *toInst ;

          /*
           * Control dependences.
           */
          if (dep->isControlDependence()){
            errs() << " control\n";
            return false;
          }

          /*
           * Data dependences.
           */
          if (dep->isMemoryDependence()){
            errs() << " via memory\n";
          } else {
            errs() << " via variable\n";
          }
          return false;
            });
      }
    }
  }

  /*
   * Compute reachability so that determining whether spill loads placed in loop
   * exit blocks could be invalidated by spill stores in the loop. If so,
   * they will have to be placed within the loop (which is less optimal)
   * NOTE: This is computed BEFORE addPredecessorAndSuccessorsBasicBlocksToTasks creates an empty basic block
   * in the original function which will be used to link this task
   */
  auto reachabilityDFR = this->computeReachabilityFromInstructions(LDI);

  /*
   * Generate empty tasks for the HELIX execution.
   */
  auto helixTask = new HELIXTask(this->taskSignature, this->module);
  this->addPredecessorAndSuccessorsBasicBlocksToTasks(LDI, { helixTask });
  this->numTaskInstances = LDI->getMaximumNumberOfCores();
  assert(helixTask == this->tasks[0]);

  /*
   * Fetch the indices of live-in and live-out variables of the loop being parallelized.
   */
  auto liveInVars = LDI->environment->getEnvIndicesOfLiveInVars();
  auto liveOutVars = LDI->environment->getEnvIndicesOfLiveOutVars();

  /*
   * Add all live-in and live-out variables as variables to be included in the environment.
   */
  std::set<int> nonReducableVars(liveInVars.begin(), liveInVars.end());
  std::set<int> reducableVars{};
  for (auto liveOutIndex : liveOutVars) {

    /*
     * We have a live-out variable.
     *
     * Check if it can be reduced so we can generate more efficient code that does not require a sequential segment.
     */
    auto producer = LDI->environment->producerAt(liveOutIndex);
    auto scc = sccManager->getSCCDAG()->sccOfValue(producer);
    auto sccInfo = sccManager->getSCCAttrs(scc);
    if (sccInfo->canExecuteReducibly()){

      /*
       * The live-out variable can be reduced so we can generate more efficient code that does not require a sequential segment.
       */
      reducableVars.insert(liveOutIndex);

    } else {
      nonReducableVars.insert(liveOutIndex);
    }
  }

  /*
   * Add the memory location of the environment used to store the exit block taken to leave the parallelized loop.
   * This location exists only if there is more than one loop exit.
   */
  if (loopStructure->numberOfExitBasicBlocks() > 1){ 
    nonReducableVars.insert(LDI->environment->indexOfExitBlockTaken());
  }

  /*
   * Build the single environment that is shared between all instances of the HELIX task.
   */
  this->initializeEnvironmentBuilder(LDI, nonReducableVars, reducableVars);

  /*
   * Clone the sequential loop and store the cloned instructions/basic blocks within the single task of HELIX.
   */
  if (this->verbose >= Verbosity::Maximal) {
    errs() << "HELIX:  Cloning loop in task\n";
  }
  this->cloneSequentialLoop(LDI, 0);

  /*
   * Load all loop live-in values at the entry point of the task.
   * Store final results to loop live-out variables.
   */
  auto envUser = this->envBuilder->getUser(0);
  for (auto envIndex : LDI->environment->getEnvIndicesOfLiveInVars()) {
    envUser->addLiveInIndex(envIndex);
  }
  for (auto envIndex : LDI->environment->getEnvIndicesOfLiveOutVars()) {
    envUser->addLiveOutIndex(envIndex);
  }
  this->generateCodeToLoadLiveInVariables(LDI, 0);

  /*
   * HACK: For now, this must follow loading live-ins as this re-wiring overrides
   * the live-in mapping to use locally cloned memory instructions that are live-in to the loop
   */
  if (LDI->isOptimizationEnabled(LoopDependenceInfoOptimization::MEMORY_CLONING_ID)) {
    this->cloneMemoryLocationsLocallyAndRewireLoop(LDI, 0);
  }

  /*
   * The operands of the cloned instructions still refer to the original ones.
   *
   * Fix the data flow within the parallelized loop by redirecting operands of cloned instructions to refer to the other cloned instructions. 
   */
  this->adjustDataFlowToUseClones(LDI, 0);
  this->setReducableVariablesToBeginAtIdentityValue(LDI, 0);

  /*
   * Add the unconditional branch from the entry basic block to the header of the loop.
   */
  IRBuilder<> entryBuilder(helixTask->getEntry());
  entryBuilder.CreateBr(helixTask->getCloneOfOriginalBasicBlock(loopHeader));

  /*
   * Spill loop carried dependencies into a separate environment array
   */
  if (this->verbose >= Verbosity::Maximal) {
    errs() << "HELIX:  Check if we need to spill variables because they are part of loop carried data dependencies\n";
  }
  this->spillLoopCarriedDataDependencies(LDI, reachabilityDFR);

  /*
   * For IVs that were not spilled, adjust their step size appropriately
   */
  if (this->verbose >= Verbosity::Maximal) {
    errs() << "HELIX:  Adjusting loop IVs\n";
  }
  this->rewireLoopForIVsToIterateNthIterations(LDI);

  /*
   * Add the final return instruction to the single task's exit block.
   */
  IRBuilder<> exitB(helixTask->getExit());
  exitB.CreateRetVoid();

  if (this->verbose >= Verbosity::Maximal) {
    SubCFGs execGraph(*helixTask->getTaskBody());
    // DGPrinter::writeGraph<SubCFGs, BasicBlock>("unsync-helixtask-loop" + std::to_string(LDI->getID()) + ".dot", &execGraph);
  }

  /*
   * Delete reachability results
   */
  delete reachabilityDFR;

  return ;
}

bool HELIX::synchronizeTask (
  LoopDependenceInfo *LDI,
  Noelle &par, 
  Heuristics *h
){

  /*
   * Fetch the HELIX task.
   */
  auto helixTask = static_cast<HELIXTask *>(this->tasks[0]);

  /*
   * Compute reachability analysis for computing SS frontiers and scheduling SS instructions
   */
  auto reachabilityDFR = this->computeReachabilityFromInstructions(LDI);

  /*
   * Schedule the code to minimize the instructions within each sequential segment.
   * HACK: Entries and exits are determined when identifying a sequential segment. They
   * aren't adjusted after squeezing. Delay computing entry and exit frontiers for identified
   * sequential segments until AFTER squeezing.
   */
  auto sequentialSegments = this->identifySequentialSegments(originalLDI, LDI, reachabilityDFR);
  this->squeezeSequentialSegments(LDI, &sequentialSegments, reachabilityDFR);

  /*
   * Free the memory.
   */
  delete reachabilityDFR;
  for (auto ss : sequentialSegments) {
    delete ss;
  }

  /*
   * Re-compute reachability analysis after squeezing sequential segments
   * Identify the sequential segments.
   */
  if (this->verbose >= Verbosity::Maximal) {
    errs() << "HELIX:  Identifying sequential segments\n";
  }
  reachabilityDFR = this->computeReachabilityFromInstructions(LDI);
  sequentialSegments = this->identifySequentialSegments(originalLDI, LDI, reachabilityDFR);

  /*
   * Schedule the sequential segments to overlap parallel and sequential segments.
   */
  this->scheduleSequentialSegments(LDI, &sequentialSegments, reachabilityDFR);

  /*
   * Delete reachability results here before we decide whether to continue with the HELIX parallelization
   */
  delete reachabilityDFR;

  /*
   * Check if any sequential segment's entry and exit frontier spans the entire loop execution
   * If so, do not parallelize
   */
  if (!this->forceParallelization) {
    auto loopStructure = LDI->getLoopStructure();
    auto loopHeader = loopStructure->getHeader();
    auto loopLatches = loopStructure->getLatches();
    for (auto sequentialSegment : sequentialSegments) {
      bool entryAtHeader = false, exitAtLatch = false;
      sequentialSegment->forEachEntry([&](Instruction *entry) -> void {
        auto entryBlock = entry->getParent();
        entryAtHeader |= loopHeader == entryBlock;
        exitAtLatch |= loopLatches.find(entryBlock) != loopLatches.end();
      });
      if (!entryAtHeader || !exitAtLatch) continue;

      /*
       * The HELIX parallelization isn't worth it.
       */
      if (this->verbose != Verbosity::Disabled) {
        errs() << "HELIX: There is a sequential segment spanning the entire loop; therefore, the parallelization isn't worth it.\n";
      }

      /*
       * Free the memory.
       */
      for (auto ss : sequentialSegments) {
        delete ss;
      }

      return false;
    }
  }

  /*
   * Add synchronization instructions.
   */
  if (this->verbose >= Verbosity::Maximal) {
    errs() << "HELIX:  Synchronizing sequential segments\n";
  }
  this->addSynchronizations(LDI, &sequentialSegments);

  /*
   * Store final results of loop live-out variables. 
   *
   * Note this occurs after synchronization has been put in place. This is to ensure
   * that reducible variables not tracked in the loop carried environment are properly
   * propagated as live outs even when check-exit fails and branches directly to the task function's
   * exit block (it can't branch to the task loop's exit blocks because logic in those exit blocks
   * should only be executed by the last iteration, not by all cores)
   */
  if (this->verbose >= Verbosity::Maximal) {
    errs() << "HELIX:  Storing live out variables and exit block index\n";
  }

  /*
   * HACK: swap the mapping so that original loop instructions map to possible duplicates
   * that were created should the original header have had sequential instructions that
   * were moved to the loop body and duplicated after exiting the loop
   *
   * Once live out storing is finished, restore the mapping
   */
  std::unordered_map<Instruction *, Instruction *> loopBodyExecutionMap;
  for (auto lastExecutionInstPair : this->lastIterationExecutionDuplicateMap) {
    auto originalI = lastExecutionInstPair.first;
    auto exitCloneI = lastExecutionInstPair.second;
    auto loopBodyCloneI = helixTask->getCloneOfOriginalInstruction(originalI);
    helixTask->addInstruction(originalI, exitCloneI);
    loopBodyExecutionMap.insert(std::make_pair(originalI, loopBodyCloneI));
  }

  /*
   * NOTE: The assumption being made here is that if we have a last iteration execution block,
   * it is because we have attributed a loop governing IV. Our attribution relies on there
   * being only one loop exit that is controlled by an IV. Hence, we fetch the lone exit block
   */
  auto originalExitBlocks = this->originalLDI->getLoopStructure()->getLoopExitBasicBlocks();
  auto originalSingleExitBlock = *originalExitBlocks.begin();
  BasicBlock * cloneLoopExitBlock = nullptr;
  if (this->lastIterationExecutionBlock) {
    assert(originalExitBlocks.size() == 1 && "loop governing IV attribution relies on only one exit block!");
    cloneLoopExitBlock = helixTask->getCloneOfOriginalBasicBlock(originalSingleExitBlock);
    helixTask->addBasicBlock(originalSingleExitBlock, lastIterationExecutionBlock);
  }

  /*
   * Generate stores for live out variables
   * Generate a store to propagate information about which exit block the parallelized loop took.
   */
  this->generateCodeToStoreLiveOutVariables(this->originalLDI, 0);
  this->generateCodeToStoreExitBlockIndex(this->originalLDI, 0);

  /*
   * HACK: reset the last clone map to reflect the loop exit block which is the successor
   * to the if else branch determining whether to execute the last iteration block before the loop exit block  
   */
  for (auto loopBodyExecutionInstPair : loopBodyExecutionMap) {
    auto originalI = loopBodyExecutionInstPair.first;
    auto loopBodyCloneI = loopBodyExecutionInstPair.second;
    auto exitCloneI = helixTask->getCloneOfOriginalInstruction(originalI);
    helixTask->addInstruction(originalI, loopBodyCloneI);
  }
  if (this->lastIterationExecutionBlock) {
    helixTask->addBasicBlock(originalSingleExitBlock, cloneLoopExitBlock);
  }

  /*
   * Link the parallelize code to the original one.
   */
  if (this->verbose >= Verbosity::Maximal) {
    errs() << "HELIX:  Linking task function\n";
  }
  this->addChunkFunctionExecutionAsideOriginalLoop(this->originalLDI, par, sequentialSegments.size());

  /*
   * Inline calls to HELIX functions.
   */
  this->inlineCalls(helixTask);

  /*
   * Print the HELIX task.
   */
  if (this->verbose >= Verbosity::Maximal) {
    helixTask->getTaskBody()->print(errs() << "HELIX:  Task code:\n"); errs() << "\n";
    // errs() << "HELIX: Exit\n";
    // SubCFGs execGraph(*helixTask->getTaskBody());
    // DGPrinter::writeGraph<SubCFGs, BasicBlock>("helixtask-loop" + std::to_string(LDI->getID()) + ".dot", &execGraph);
  }

  /*
   * Free the memory.
   */
  for (auto ss : sequentialSegments) {
    delete ss;
  }

  return true;
}

Function * HELIX::getTaskFunction (void) const {
  return tasks[0]->getTaskBody();
}

}


<|start_filename|>src/core/loop_structure/include/StayConnectedNestedLoopForest.hpp<|end_filename|>
/*
 * Copyright 2019 - 2020  <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#pragma once

#include "SystemHeaders.hpp"
#include "LoopStructure.hpp"
#include "DominatorSummary.hpp"
#include <unordered_map>

namespace llvm::noelle {
  class StayConnectedNestedLoopForest ;

  class StayConnectedNestedLoopForestNode {
    public:
      StayConnectedNestedLoopForestNode (StayConnectedNestedLoopForest *f, LoopStructure *l);

      StayConnectedNestedLoopForestNode (StayConnectedNestedLoopForest *f, LoopStructure *l, StayConnectedNestedLoopForestNode *parent);

      LoopStructure * getLoop (void) const ;

      StayConnectedNestedLoopForestNode * getParent (void) const ;

      std::unordered_set<StayConnectedNestedLoopForestNode *> getDescendants (void) const ;

      bool visitPreOrder (
        std::function<bool (StayConnectedNestedLoopForestNode *n, uint32_t treeLevel)> funcToInvoke
        ) ;

      bool visitPostOrder (
        std::function<bool (StayConnectedNestedLoopForestNode *n, uint32_t treeLevel)> funcToInvoke
        ) ;

      ~StayConnectedNestedLoopForestNode();

    private:
      friend class StayConnectedNestedLoopForest ;
      StayConnectedNestedLoopForest *forest;
      LoopStructure *loop;
      StayConnectedNestedLoopForestNode *parent;
      std::unordered_set<StayConnectedNestedLoopForestNode *> descendants;

      bool visitPreOrder (std::function<bool (StayConnectedNestedLoopForestNode *n, uint32_t treeLevel)> funcToInvoke, uint32_t treeLevel) ;
      bool visitPostOrder (std::function<bool (StayConnectedNestedLoopForestNode *n, uint32_t treeLevel)> funcToInvoke, uint32_t treeLevel) ;
  };

  class StayConnectedNestedLoopForest {
    public:
      StayConnectedNestedLoopForest (
        std::vector<LoopStructure *> const & loops, 
        std::unordered_map<Function *, DominatorSummary *> const &doms
        );

      std::unordered_set<StayConnectedNestedLoopForestNode *> getTrees (void) const ;

      void removeTree (StayConnectedNestedLoopForestNode *tree) ;
      
      void addTree (StayConnectedNestedLoopForestNode *tree) ;

      StayConnectedNestedLoopForestNode * getNode (LoopStructure *loop) const ;

      ~StayConnectedNestedLoopForest();

    private:
      std::unordered_map<LoopStructure *, StayConnectedNestedLoopForestNode *> nodes;
      std::unordered_set<StayConnectedNestedLoopForestNode *> trees;
      std::unordered_map<Function *, std::unordered_set<LoopStructure *>> functionLoops;
      std::unordered_map<BasicBlock *, StayConnectedNestedLoopForestNode *> headerLoops;

      void addChildrenToTree (
        StayConnectedNestedLoopForestNode *root, 
        std::unordered_map<Function *, DominatorSummary *> const &doms, 
        std::unordered_set<StayConnectedNestedLoopForestNode *> &potentialTrees
        );
  };

}


<|start_filename|>src/core/induction_variables/src/LoopGoverningIVUtility.cpp<|end_filename|>
/*
 * Copyright 2016 - 2021  <NAME>, <NAME>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "IVStepperUtility.hpp"

namespace llvm::noelle{

LoopGoverningIVUtility::LoopGoverningIVUtility (
    LoopStructure *loopOfGIV,
    InductionVariableManager &IVM,
    LoopGoverningIVAttribution &attribution
    )
  : loop{loopOfGIV}
  , attribution{attribution}
  , conditionValueOrderedDerivation{}
  , flipOperandsToUseNonStrictPredicate{false}
  , flipBrSuccessorsToUseNonStrictPredicate{false} 
  , isWhile{false}
{

  /*
   * Fetch the IV
   */
  auto IV = attribution.getInductionVariable();

  /*
   * Fetch information about the condition to exit the loop.
   *
   * Check where the IV is in the comparison (left or right).
   */
  this->condition = attribution.getHeaderCmpInst();
  // TODO: Refer to whichever intermediate value is used in the comparison (known on attribution)
  this->doesOriginalCmpInstHaveIVAsLeftOperand = condition->getOperand(0) == attribution.getValueToCompareAgainstExitConditionValue();

  /*
   * Collect the set of instructions that need to be executed to evaluate the loop exit condition for the subsequent iteration.
   */
  auto conditionValueDerivationSet = attribution.getConditionValueDerivation();
  for (auto &I : *condition->getParent()) {
    if (conditionValueDerivationSet.find(&I) == conditionValueDerivationSet.end()) continue;
    conditionValueOrderedDerivation.push_back(&I);
  }
  assert(IV.getSingleComputedStepValue() && isa<ConstantInt>(IV.getSingleComputedStepValue()));

  /*
   * Fetch information about the step value for the IV.
   */
  auto isStepValuePositive = IV.isStepValuePositive();

  /*
   * Fetch information about the predicate that when true the execution needs to leave the loop.
   */
  auto conditionExitsOnTrue = attribution.getHeaderBrInst()->getSuccessor(0) == attribution.getExitBlockFromHeader();
  auto exitPredicate = conditionExitsOnTrue ? condition->getPredicate() : condition->getInversePredicate();
  exitPredicate = doesOriginalCmpInstHaveIVAsLeftOperand ? exitPredicate : CmpInst::getSwappedPredicate(exitPredicate);
  this->flipOperandsToUseNonStrictPredicate = !doesOriginalCmpInstHaveIVAsLeftOperand;
  this->flipBrSuccessorsToUseNonStrictPredicate = !conditionExitsOnTrue;
  this->nonStrictPredicate = exitPredicate;
  this->strictPredicate = exitPredicate;
  switch (exitPredicate) {
    case CmpInst::Predicate::ICMP_NE:

      /*
       * This predicate is non-strict and will result in either 0 or 1 iteration(s)
       */
      break;
    case CmpInst::Predicate::ICMP_EQ:
      // This predicate is strict and needs to be extended to LTE/GTE to catch jumping past the exiting value
      if (isStepValuePositive){
        this->nonStrictPredicate = CmpInst::Predicate::ICMP_SGE;
        this->strictPredicate = CmpInst::Predicate::ICMP_SGT;
      } else {
        this->nonStrictPredicate = CmpInst::Predicate::ICMP_SLE;
        this->strictPredicate = CmpInst::Predicate::ICMP_SLT;
      }
      break;
    case CmpInst::Predicate::ICMP_SLE:
    case CmpInst::Predicate::ICMP_SLT:
    case CmpInst::Predicate::ICMP_ULT:
    case CmpInst::Predicate::ICMP_ULE:
      // This predicate is non-strict. We simply assert that the step value has the expected sign

      // HACK: while it is technically correct to increment with a less than exit condition, yielding 0 or 1 iteration,
      // it would break under assumptions that further recurrences of the IV can be checked on this condition
      // Our parallelization schemes make that assumption, hence the assert here
      assert(!isStepValuePositive && "IV step value is not compatible with exit condition!");
      break;
    case CmpInst::Predicate::ICMP_UGT:
    case CmpInst::Predicate::ICMP_UGE:
    case CmpInst::Predicate::ICMP_SGT:
    case CmpInst::Predicate::ICMP_SGE:
      // This predicate is non-strict. We simply assert that the step value has the expected sign

      // HACK: while it is technically correct to decrement with a greater than exit condition, yielding 0 or 1 iteration,
      // it would break under assumptions that further recurrences of the IV can be checked on this condition
      // Our parallelization schemes make that assumption, hence the assert here
      assert(isStepValuePositive && "IV step value is not compatible with exit condition!");
      break;
  }

  /*
   * Check if the loop has a while form.
   */
  for (auto predecessorOfHeader : predecessors(this->loop->getHeader())){

    /*
     * Fetch the next predecessor of the header that is included in the loop.
     */
    if (!this->loop->isIncluded(predecessorOfHeader)){
      continue ;
    }

    /*
     * Check if the terminator of the current predecessor is an unconditional branch (necessary condition for a while loop)
     */
    auto terminatorOfPred = predecessorOfHeader->getTerminator();
    if (!isa<BranchInst>(terminatorOfPred)){
      continue ;
    }
    auto branch = cast<BranchInst>(terminatorOfPred);
    if (branch->isConditional()){
      continue ;
    }

    /*
     * We found a predecessor of the loop's header that ends with an unconditional branch.
     * Check if this basic block contains computation that isn't bitcasts or IV related (necessary condition for a while loop).
     */
    auto doesItContainComputation = false;
    for (auto& inst : *predecessorOfHeader){
      if (predecessorOfHeader->getTerminator() == &inst){
        continue ;
      }
      if (isa<BitCastInst>(&inst)){
        continue ;
      }
      if (IVM.doesContributeToComputeAnInductionVariable(&inst)){
        continue ;
      }
      doesItContainComputation = true;
      break ;
    }
    if (doesItContainComputation){

      /*
       * We found a non empty basic block.
       * Hence, the loop is a while loop.
       */
      this->isWhile = true;
      break ;
    }
  }

  return ;
}

void LoopGoverningIVUtility::updateConditionAndBranchToCatchIteratingPastExitValue(
  CmpInst *cmpToUpdate,
  BranchInst *branchInst,
  BasicBlock *exitBlock
  ) {

  if (this->flipOperandsToUseNonStrictPredicate) {
    auto opL = cmpToUpdate->getOperand(0);
    auto opR = cmpToUpdate->getOperand(1);
    cmpToUpdate->setOperand(0, opR);
    cmpToUpdate->setOperand(1, opL);
  }
  cmpToUpdate->setPredicate(this->nonStrictPredicate);

  if (this->flipBrSuccessorsToUseNonStrictPredicate) {
    branchInst->swapSuccessors();
  }

  return ;
}

void LoopGoverningIVUtility::cloneConditionalCheckFor(
  Value *recurrenceOfIV,
  Value *clonedCompareValue,
  BasicBlock *continueBlock,
  BasicBlock *exitBlock,
  IRBuilder<> &cloneBuilder
  ) {

  /*
   * Create the comparison instruction.
   */
  auto cmpInst = cloneBuilder.CreateICmp(this->nonStrictPredicate, recurrenceOfIV, clonedCompareValue);

  /*
   * Add the conditional branch
   */
  cloneBuilder.CreateCondBr(cmpInst, exitBlock, continueBlock);

  return ;
}

void LoopGoverningIVUtility::updateConditionToCheckIfWeHavePastExitValue(
  CmpInst *cmpToUpdate
  ){

  /*
   * Check if the loop is a while one.
   */
  if (this->isWhile){
    cmpToUpdate->setPredicate(this->strictPredicate);
  }

  return ;
}

std::vector<Instruction *> & LoopGoverningIVUtility::getConditionValueDerivation (void) {
  return conditionValueOrderedDerivation;
}

Value * LoopGoverningIVUtility::generateCodeToComputeTheTripCount (
  IRBuilder<> &builder
  ){

  /*
   * Fetch the start and last value.
   */
  auto IV = this->attribution.getInductionVariable();
  auto startValue = IV.getStartValue();
  auto lastValue = this->attribution.getExitConditionValue();

  /*
   * Compute the delta.
   */
  Value *delta = nullptr;
  if (IV.isStepValuePositive()){
    delta = builder.CreateSub(lastValue, startValue);
  } else {
    delta = builder.CreateSub(startValue, lastValue);
  }

  /*
   * Compute the number of steps to reach the delta.
   */
  auto tripCount = builder.CreateUDiv(delta, IV.getSingleComputedStepValue());

  return tripCount;
}

Value * LoopGoverningIVUtility::generateCodeToComputePreviousValueUsedToCompareAgainstExitConditionValue (
  IRBuilder<> &builder,
  Value *currentIterationValue,
  BasicBlock *latch,
  Value *stepValue
  ){

  /*
   * Assert that the builder is pointing to an instruction within the loop.
   */
  //TODO

  /*
   * Generate the value that was used to compare against the exit condition value in the last iteration.
   */ 
  auto prevIterationValue = this->generateCodeToComputeValueToUseForAnIterationAgo(builder, currentIterationValue, stepValue);

  return prevIterationValue;
}

Value * LoopGoverningIVUtility::generateCodeToComputeValueToUseForAnIterationAgo (
  IRBuilder<> &builder,
  Value *currentIterationValue,
  Value *stepValue
  ){

  /*
   * Check if the value used to compare against the exit condition value is the PHI of the loop governing IV.
   */
  auto &IV = this->attribution.getInductionVariable();
  if (this->attribution.getValueToCompareAgainstExitConditionValue() == IV.getLoopEntryPHI()){

    /*
     * The value used is the PHI.
     * Hence, we must generate code to compute the value of the previous iteration.
     */
    auto prevIterationValue = builder.CreateSub(currentIterationValue, stepValue);

    return prevIterationValue;
  }

  /*
   * The value used to check whether we should exit the loop is the updated value.
   * Hence, the previous value is simply the current updated one.
   */
  return currentIterationValue;
}

}
