<filename>GenXIntrinsics/lib/GenXIntrinsics/GenXSimdCFLowering.cpp
/*===================== begin_copyright_notice ==================================

 Copyright (c) 2020, Intel Corporation


 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.
======================= end_copyright_notice ==================================*/

//===----------------------------------------------------------------------===//
//
/// CMSimdCFLowering
/// ----------------
///
/// This pass lowers CM SIMD control flow into a form where the IR reflects
/// the semantics.
///
/// On entry, SIMD control flow is as it was generated by Clang codegen:
///
/// * Any SIMD control flow conditional branch is a ``br`` instruction with a
///   scalar condition that is the result of an ``llvm.genx.simdcf.any``
///   intrinsic, which has a predicate (vector bool) operand.
///
/// * Any reducing intrinsic (cm_sum, cm_prod) has its input gated by a
///   ``llvm.genx.simdcf.predicate`` intrinsic. The semantics of the CM language
///   are that, in a reducing function such as cm_sum, elements corresponding
///   to a disabled channel take a default value (0 for cm_sum and 1 for cm_prod)
///   such that the disabled elements do not affect the result.
///
/// * There is no other masking of instructions by SIMD control flow condition(s).
///
/// In this state, the IR does not reflect the semantics of SIMD control flow.
/// No existing LLVM analysis or transformation understands what we really mean
/// by these intrinsics, so we are in danger of incorrect changes being made to
/// the IR by LLVM optimizations.
///
/// This CMSimdCFLowering pass runs very early, pretty much straight after Clang
/// codegen, so no other LLVM pass has had a chance to make an incorrect change.
/// This pass fixes the IR to reflect the semantics, so that subsequent passes
/// do not make an incorrect change. After this lowering, the IR uses:
///
/// * ``llvm.genx.simdcf.goto`` and ``llvm.genx.simdcf.join`` intrinsics for the
///   control flow, using and generating explicit EM (execution mask) values;
///
/// * predication of certain SIMD-CF-controlled instructions by the current EM
///   value, using select or the predicate operand of wrregion.
///
/// See the GenX language reference for details of these intrinsics and the model
/// for representing SIMD control flow semantics in LLVM IR.
///
/// Language semantics
/// ^^^^^^^^^^^^^^^^^^
///
/// The algorithm that this pass uses allows more general semantics than is
/// currently defined to work in the CM language. The SIMD control flow can be
/// arbitrarily unstructured, and it can be mixed with scalar control flow in
/// an arbitrarily unstructured way. It also allows up to 32 channels.
///
/// Algorithm
/// ^^^^^^^^^
///
/// 1. Find the SIMD branches, ones where Clang codegen has used
///    ``llvm.genx.simdcf.any``.
///
/// 2. Determine which basic blocks need to be predicated. Any block that is
///    *control dependent* on a SIMD branch needs to be predicated. See Muchnick
///    section 9.5 *Program-Dependence Graphs*. For each edge m->n in the
///    control flow graph where n does not post-dominate m, find l, the closest
///    common ancestor in the post-dominance tree of m and n. All nodes in the
///    post-dominance tree from l to n except l itself are control dependent on
///    m.
///
///    This step also issues an error if any block is found to be control
///    dependent on multiple SIMD branches that have different SIMD widths.
///
/// 3. Mark the branch at the end of any to-be-predicated block as a SIMD
///    branch. This is what allows the arbitrarily unstructured mixing of SIMD
///    and scalar control flow; any scalar control flow that is control dependent
///    on SIMD control flow is itself converted to SIMD control flow with a
///    splatted predicate. (It will get converted back into scalar control flow
///    if it turns out to be strictly nested inside SIMD control flow.)
///
/// 4. Fix SIMD branches:
///
///    a. Convert a backward SIMD branch into a forward one over a backward
///       unconditional branch, as required by the GenX backend's IR model of
///       SIMD CF.
///
///    b. For a SIMD branch, ensure that the false leg is fallthrough, also as
///       required by the GenX backend's IR model.
///
///    Both these changes are likely to be broken by subsequent LLVM passes, but
///    leaving the IR in a state that can be recovered to re-impose these
///    restrictions.
///
/// 5. Find the join points, any point that is the non-fallthrough target of a
///    SIMD branch. Split out any join point into its own basic block (so we
///    have somewhere to put the join intrinsic and its conditional branch).
///
/// 6. Determine the JIP for each conditional branch that will be a goto (a SIMD
///    branch) or join (a join point). Starting at the goto or join, the JIP is
///    the closest point lower down where a channel could become re-enabled.
///
/// 7. Predicate the code. Code within blocks identified in step 2 are
///    predicated. Code in other blocks is also predicated, but without
///    predicating stores, in a subroutine that is called with a predicated call
///    and thus takes a call mask.
///
///    a. A store to a vector local variable (an alloca) is predicated.
///
///       i. If it is the same vector width as the controlling SIMD branch width,
///          then the store is predicated by turning it into a load, select,
///          store sequence.
///
///       ii. If it is a wider vector than the controlling SIMD branch width,
///           then we look back through the chain of wrregions whose result is
///           stored to find one of the right width, and predicate that.
///
///       iii. If no wrregion of the correct width is found, then an error is
///            issued, as the original CM code must be incorrect.
///
///    b. Shared function intrinsics with a predicate operand are predicated
///       (for example gather).
///
///    c. Any ``llvm.genx.simdcf.predicate`` intrinsic is changed to a select.
///
///    d. A subroutine call is predicated by adding an extra argument for the
///       predicate, which acts as the *call mask*.
///
///    e. There is a single 32 bit EM (execution mask) global variable created
///       for the whole function, statically initialized to all ones. In
///       implementing predication in the items above, the EM value is loaded from
///       the variable. If a narrower-than-32-bit EM value is required, it is
///       sliced using a ``shufflevector``.
/// 
///       Like any other global variable, the EM global variable is transformed by
///       the CMABI pass into a local variable that is passed in and out of
///       subroutines as required. Where it is passed into a subroutine, this is
///       the *call mask* of the subroutine call.
///
/// 8. Lower the control flow. This is where the ``llvm.genx.simdcf.goto`` and
///    ``llvm.genx.simdcf.join`` intrinsic calls are inserted. Also each join
///    has a RM (resume mask) local variable created for the whole function,
///    initialized to all zeros. The width of the RM for a particular join is
///    the same as the width of the SIMD branches that modify that join's RM.
///    For multiple SIMD branches modifying the same join's RM, the widths are
///    guaranteed to be the same because of the check carried out in 2.
/// 
///    The inserted goto and join intrinsics manipulate the EM and RM values.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "cmsimdcflowering"

#include "llvm/ADT/MapVector.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/GenXIntrinsics/GenXIntrinsics.h"
#include "llvm/GenXIntrinsics/GenXMetadata.h"
#include "llvm/GenXIntrinsics/GenXIntrOpts.h"
#include "llvm/GenXIntrinsics/GenXSimdCFLowering.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/DiagnosticPrinter.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <set>

#if VC_INTR_LLVM_VERSION_MAJOR >= 8
#include <llvm/IR/PatternMatch.h>
#endif

#include "llvmVCWrapper/IR/GlobalValue.h"
#include "llvmVCWrapper/IR/DerivedTypes.h"
#include "llvmVCWrapper/IR/InstrTypes.h"

using namespace llvm;

namespace {

// Grouping : utility class to maintain a grouping, a partition of a set of
// items into disjoint groups. The initial state is that each item is in its
// own group, then you call joinGroups to join two groups together.
template<typename T> class Grouping {
  std::map<T, T> Group;
public:
  // joinGroups : join the groups that Block1 and Block2 are in
  void joinGroups(T Block1, T Block2) {
    auto G1 = getGroup(Block1);
    auto G2 = getGroup(Block2);
    if (G1 != G2)
      Group[G2] = G1;
  }
  // getGroup : get the group for Block
  // The chain of blocks between Block and its group are modified to point
  // directly to the group at the end of the chain.
  T getGroup(T Block) {
    SmallVector<T, 4> Chain;
    T G;
    for (;;) {
      G = Group[Block];
      if (!G)
        Group[Block] = G = Block; // never seen before, initialize
      if (G == Block)
        break;
      Chain.push_back(Block);
      Block = G;
    }
    for (auto i = Chain.begin(), e = Chain.end(); i != e; ++i)
      *i = G;
    return G;
  }
};

// Diagnostic information for error/warning relating to SIMD control flow.
class DiagnosticInfoSimdCF : public DiagnosticInfoOptimizationBase {
private:
  static int KindID;
  static int getKindID() {
    if (KindID == 0)
      KindID = llvm::getNextAvailablePluginDiagnosticKind();
    return KindID;
  }
public:
  static void emit(Instruction *Inst, StringRef Msg, DiagnosticSeverity Severity = DS_Error);
  DiagnosticInfoSimdCF(DiagnosticSeverity Severity, const Function &Fn,
      const DebugLoc &DLoc, StringRef Msg)
      : DiagnosticInfoOptimizationBase((DiagnosticKind)getKindID(), Severity,
          /*PassName=*/nullptr, Msg, Fn, DLoc) {}
  // This kind of message is always enabled, and not affected by -rpass.
  virtual bool isEnabled() const override { return true; }
  static bool classof(const DiagnosticInfo *DI) {
    return DI->getKind() == getKindID();
  }
  void print(DiagnosticPrinter &DP) const override { DP << "CMSimdCFLowering: " << RemarkName; }
};
int DiagnosticInfoSimdCF::KindID = 0;

// Call graph node
struct CGNode {
  Function *F;
  std::set<CGNode *> UnvisitedCallers;
  std::set<CGNode *> Callees;
};

// The ISPC SIMD CF lowering pass (a module pass)
class ISPCSimdCFLowering : public ModulePass {
public:
  static char ID;

  ISPCSimdCFLowering() : ModulePass(ID) {}
  void getAnalysisUsage(AnalysisUsage &AU) const {
    ModulePass::getAnalysisUsage(AU);
  }

  bool runOnModule(Module &M);
};

// The CM SIMD CF lowering pass (a function pass)
class CMSimdCFLowering : public FunctionPass {
public:
  static char ID;

  CMSimdCFLowering() : FunctionPass(ID) {
    initializeCMSimdCFLoweringPass(*PassRegistry::getPassRegistry());
  }
  void getAnalysisUsage(AnalysisUsage &AU) const {
    FunctionPass::getAnalysisUsage(AU);
  }

  virtual bool doInitialization(Module &M);
  virtual bool runOnFunction(Function &F) { return false; }
private:
  void calculateVisitOrder(Module *M, std::vector<Function *> *VisitOrder);
};

} // namespace

char CMSimdCFLowering::ID = 0;
INITIALIZE_PASS_BEGIN(CMSimdCFLowering, "cmsimdcflowering", "Lower CM SIMD control flow", false, false)
INITIALIZE_PASS_END(CMSimdCFLowering, "cmsimdcflowering", "Lower CM SIMD control flow", false, false)

Pass *llvm::createCMSimdCFLoweringPass() { return new CMSimdCFLowering(); }

char ISPCSimdCFLowering::ID = 0;
namespace llvm {
void initializeISPCSimdCFLoweringPass(PassRegistry&);
}
INITIALIZE_PASS_BEGIN(ISPCSimdCFLowering, "ispcsimdcflowering", "Lower ISPC SIMD control flow", false, false)
INITIALIZE_PASS_END(ISPCSimdCFLowering, "ispcsimdcflowering", "Lower ISPC SIMD control flow", false, false)

Pass *llvm::createISPCSimdCFLoweringPass() {
    initializeISPCSimdCFLoweringPass(*PassRegistry::getPassRegistry());
    return new ISPCSimdCFLowering();
}

bool ISPCSimdCFLowering::runOnModule(Module &M) {
    return CMSimdCFLowering().doInitialization(M);
}

/***********************************************************************
 * doInitialization : per-module initialization for CM simd CF lowering
 *
 * Really we want a module pass for CM simd CF lowering. But, without modifying
 * llvm's PassManagerBuilder, the earliest place to insert a pass is
 * EP_EarlyAsPossible, which must be a function pass. So, we do our
 * per-module processing here in doInitialization.
 */
bool CMSimdCFLowering::doInitialization(Module &M)
{
#if 0
  for (auto &F : M.getFunctionList()) {
    if (F.hasFnAttribute("CMGenxSIMT")) {
      if (F.hasFnAttribute(Attribute::AlwaysInline)) {
        F.removeFnAttr(Attribute::AlwaysInline);
        F.removeFnAttr(Attribute::InlineHint);
        F.addFnAttr("CMGenxInline");
        F.addFnAttr(Attribute::NoInline);
      }
    }
  }
#endif

  for (auto &G : M.getGlobalList()) {
    if (!G.hasAttribute(genx::FunctionMD::GenXVolatile))
      continue;
    // Transform all load store on volatile globals to vload/vstore to disable
    // optimizations on this global (no PHI will be produced.).
    auto AS0 = VCINTR::GlobalValue::getAddressSpace(G);
    std::vector<User*> WL;
    for (auto UI = G.user_begin(); UI != G.user_end();) {
      auto U = *UI++;
      WL.push_back(U);
    }

    while (!WL.empty()) {
      auto Inst = WL.back();
      WL.pop_back();
      if (auto CE = dyn_cast<ConstantExpr>(Inst)) {
        for (auto UI = CE->user_begin(); UI != CE->user_end();) {
          auto U = *UI++;
          WL.push_back(U);
        }
      }
      else if (auto CI = dyn_cast<CastInst>(Inst)) {
        for (auto UI = CI->user_begin(); UI != CI->user_end();) {
          auto U = *UI++;
          WL.push_back(U);
        }
      }
      else if (auto GEP = dyn_cast<GetElementPtrInst>(Inst)) {
        for (auto UI = GEP->user_begin(); UI != GEP->user_end();) {
          auto U = *UI++;
          WL.push_back(U);
        }
      }
      else if (auto LI = dyn_cast<LoadInst>(Inst)) {
        IRBuilder<> Builder(LI);
        auto Ptr = LI->getPointerOperand();
        auto AS1 = LI->getPointerAddressSpace();
        if (AS1 != AS0) {
          auto PtrTy = cast<PointerType>(Ptr->getType());
          PtrTy = PointerType::get(PtrTy->getElementType(), AS0);
          Ptr = Builder.CreateAddrSpaceCast(Ptr, PtrTy);
        }
        Type* Tys[] = { LI->getType(), Ptr->getType() };
        Function* Fn = GenXIntrinsic::getGenXDeclaration(&M, GenXIntrinsic::genx_vload, Tys);
        Value* VLoad = Builder.CreateCall(Fn, Ptr, "gload");
        LI->replaceAllUsesWith(VLoad);
        LI->eraseFromParent();
      }
      else if (auto SI = dyn_cast<StoreInst>(Inst)) {
        if (!SI->getValueOperand()->getType()->isVectorTy())
          continue;
        IRBuilder<> Builder(SI);
        auto Ptr = SI->getPointerOperand();
        auto AS1 = SI->getPointerAddressSpace();
        if (AS1 != AS0) {
          auto PtrTy = cast<PointerType>(Ptr->getType());
          PtrTy = PointerType::get(PtrTy->getElementType(), AS0);
          Ptr = Builder.CreateAddrSpaceCast(Ptr, PtrTy);
        }
        Type* Tys[] = { SI->getValueOperand()->getType(), Ptr->getType() };
        Value* Args[] = { SI->getValueOperand(), Ptr };
        Function* Fn = GenXIntrinsic::getGenXDeclaration(&M, GenXIntrinsic::genx_vstore, Tys);
        Builder.CreateCall(Fn, Args);
        SI->eraseFromParent();
      }
    }
  }

  // See if simd CF is used anywhere in this module.
  // We have to try each overload of llvm.genx.simdcf.any separately.
  bool HasSimdCF = false;
  for (unsigned Width = 2; Width <= CMSimdCFLower::MAX_SIMD_CF_WIDTH; Width <<= 1) {
    auto VT = VCINTR::getVectorType(Type::getInt1Ty(M.getContext()), Width);
    Function *SimdCFAny = GenXIntrinsic::getGenXDeclaration(
        &M, GenXIntrinsic::genx_simdcf_any, VT);
    if (!SimdCFAny->use_empty()) {
      HasSimdCF = true;
      break;
    }
  }

  if (HasSimdCF) {
    // Create the global variable for the execution mask.
    auto EMTy = VCINTR::getVectorType(Type::getInt1Ty(M.getContext()),
      CMSimdCFLower::MAX_SIMD_CF_WIDTH);
    auto EMVar = new GlobalVariable(M, EMTy, false/*isConstant*/,
        GlobalValue::InternalLinkage, Constant::getAllOnesValue(EMTy), "EM");
    // Derive an order to process functions such that a function is visited
    // after anything that calls it.
    std::vector<Function *> VisitOrder;
    calculateVisitOrder(&M, &VisitOrder);
    // Process functions in that order.
    CMSimdCFLower CFL(EMVar);
    for (auto i = VisitOrder.begin(), e = VisitOrder.end(); i != e; ++i) {
      Function *Fn = *i;
      if (Fn->hasFnAttribute("CMGenxNoSIMDPred"))
        continue;
      CFL.processFunction(Fn);
    }
  }

  // Any predication calls which remain are not in SIMD CF regions,
  // so can be deleted.
  for (auto mi = M.begin(), me = M.end(); mi != me; ++ mi) {
    Function *F = &*mi;
    if (GenXIntrinsic::getGenXIntrinsicID(F) !=
        GenXIntrinsic::genx_simdcf_predicate)
      continue;
    while (!F->use_empty()) {
      auto CI = cast<CallInst>(F->use_begin()->getUser());
      auto EnabledValues = CI->getArgOperand(0);
      CI->replaceAllUsesWith(EnabledValues);
      CI->eraseFromParent();
    }
  }
  return HasSimdCF;
}

/***********************************************************************
 * calculateVisitOrder : calculate the order we want to visit functions,
 *    such that a function is not visited until all its callers have been
 */
void CMSimdCFLowering::calculateVisitOrder(Module *M,
    std::vector<Function *> *VisitOrder)
{
  // First build the call graph.
  // We roll our own call graph here, because it is simpler than the general
  // case supported by LLVM's call graph analysis (CM does not support
  // recursion or function pointers), and we want to modify it (using the
  // UnvisitedCallers set) when we traverse it.
  std::map<Function *, CGNode> CallGraph;
  for (auto mi = M->begin(), me = M->end(); mi != me; ++mi) {
    Function *F = &*mi;
    if (F->empty())
      continue;
    // For each defined function: for each use (a call), add it to our
    // UnvisitedCallers set, and add us to its Callees set.
    // We are ignoring an illegal non-call use of a function; someone
    // else can spot and diagnose that later.
    // If the function has no callers, then add it straight in to VisitOrder.
    CGNode *CGN = &CallGraph[F];
    CGN->F = F;
    if (F->use_empty()) {
      VisitOrder->push_back(F);
      continue;
    }
    for (auto ui = F->use_begin(), ue = F->use_end(); ui != ue; ++ui) {
      if (auto I = dyn_cast<Instruction>(ui->getUser())) {
        Function *Caller = I->getFunction();
        // do not add a recursive call edge to the UnvisitedCallers
        if (Caller == F) {
          if (F->hasFnAttribute(genx::FunctionMD::CMStackCall))
            DiagnosticInfoSimdCF::emit(I, "SIMD recursive call", DS_Warning);
          else
            DiagnosticInfoSimdCF::emit(
                I, "Recursive function doesn't have CMStackCall attribute");
        } else {
          CGNode *CallerNode = &CallGraph[Caller];
          CallerNode->F = Caller;
          CGN->UnvisitedCallers.insert(CallerNode);
          CallerNode->Callees.insert(CGN);
        }
      }
    }
  }
  // Run through the visit order. For each function, remove it from each
  // callee's UnvisitedCallers set, and, if now empty, add the callee to
  // the end of the visit order.
  for (unsigned i = 0; i != VisitOrder->size(); ++i) {
    CGNode *CGN = &CallGraph[(*VisitOrder)[i]];
    for (auto ci = CGN->Callees.begin(), ce = CGN->Callees.end(); ci != ce;
         ++ci) {
      CGNode *Callee = *ci;
      Callee->UnvisitedCallers.erase(CGN);
      if (Callee->UnvisitedCallers.empty())
        VisitOrder->push_back(Callee->F);
    }
  }
}

/***********************************************************************
 * processFunction : process CM SIMD CF in a function
 */
void CMSimdCFLower::processFunction(Function *ArgF)
{
  F = ArgF;
  LLVM_DEBUG(dbgs() << "CMSimdCFLowering::processFunction:\n" << *F << "\n");
  LLVM_DEBUG(F->print(dbgs()));
  unsigned CMWidth = PredicatedSubroutines[F];
  // Find the simd branches.
  bool FoundSIMD = findSimdBranches(CMWidth);

  // Create shuffle mask for EM adjustment
  if (ShuffleMask.empty()) {
    auto I32Ty = Type::getInt32Ty(F->getContext());
    for (unsigned i = 0; i != 32; ++i)
      ShuffleMask.push_back(ConstantInt::get(I32Ty, i));
  }

  if (CMWidth > 0 || FoundSIMD) {
    // Determine which basic blocks need to be predicated.
    determinePredicatedBlocks();
    // Mark the branch at the end of any to-be-predicated block as a simd branch.
    markPredicatedBranches();
    // Fix simd branches:
    //  - remove backward simd branches
    //  - ensure that the false leg is fallthrough
    fixSimdBranches();
    // Find the join points, and split out any join point into its own basic
    // block.
    findAndSplitJoinPoints();
    // Determine the JIPs for the gotos and joins.
    determineJIPs();
    // Predicate the code.
    predicateCode(CMWidth);
    // Lower the control flow.
    lowerSimdCF();
    lowerUnmaskOps();
  }

  ShuffleMask.clear();
  SimdBranches.clear();
  PredicatedBlocks.clear();
  JoinPoints.clear();
  RMAddrs.clear();
  OriginalPred.clear();
  AlreadyPredicated.clear();
}

/***********************************************************************
 * findSimdBranches : find the simd branches in the function
 *
 * Enter:   CMWidth = 0 normally, or call mask width if in predicated subroutine
 *
 * This adds blocks to SimdBranches.
 */
bool CMSimdCFLower::findSimdBranches(unsigned CMWidth)
{
  bool found = false;
  for (auto fi = F->begin(), fe = F->end(); fi != fe; ++fi) {
    BasicBlock *BB = &*fi;
    auto Br = dyn_cast<BranchInst>(BB->getTerminator());
    if (!Br || !Br->isConditional())
      continue;
    if (auto SimdCondUse = getSimdConditionUse(Br->getCondition())) {
      unsigned SimdWidth = VCINTR::VectorType::getNumElements(
          cast<VectorType>((*SimdCondUse)->getType()));
      if (CMWidth && SimdWidth != CMWidth)
        DiagnosticInfoSimdCF::emit(Br, "mismatching SIMD CF width inside SIMD call");
      SimdBranches[BB] = SimdWidth;
      found = true;
    }
  }
  return found;
}

/***********************************************************************
 * determinePredicatedBlocks : determine which blocks need to be predicated
 *
 * We need to find blocks that are control dependent on a simd branch.
 *
 * This adds blocks to PredicatedBlocks. It also errors when a block is control
 * dependent on more than one simd branch with disagreeing simd width.
 *
 * See Muchnick section 9.5 Program-Dependence Graphs. For each edge m->n in
 * the control flow graph where n does not post-dominate m, find l, the
 * closest common ancestor in the post-dominance tree of m and n. All nodes
 * in the post-dominance tree from l to n except l itself are control dependent
 * on m.
 */
void CMSimdCFLower::determinePredicatedBlocks()
{
  PostDominatorTree PDT;
  PDT.recalculate(*F);

  for (auto sbi = SimdBranches.begin(), sbe = SimdBranches.end();
      sbi != sbe; ++sbi) {
    BasicBlock *BlockM = sbi->first;
    auto Br = cast<BranchInst>(BlockM->getTerminator());
    unsigned SimdWidth = sbi->second;
    LLVM_DEBUG(dbgs() << "simd branch (width " << SimdWidth << ") at " << BlockM->getName() << "\n");
    if (SimdWidth < 2 || SimdWidth > MAX_SIMD_CF_WIDTH || !isPowerOf2_32(SimdWidth))
      DiagnosticInfoSimdCF::emit(Br, "illegal SIMD CF width");
    // For each successor BlockN of BlockM...
    for (unsigned si = 0, se = Br->getNumSuccessors(); si != se; ++si) {
      auto BlockN = Br->getSuccessor(si);
      // Get BlockL, the closest common postdominator.
      auto BlockL = PDT.findNearestCommonDominator(BlockM, BlockN);
      if (BlockL == BlockM) {
        // need to include BlockM into the chain 
        // if the branch is the do-while back-edge
        if (auto ParentNode = PDT.getNode(BlockM))
          if (auto IDom = ParentNode->getIDom())
            BlockL = IDom->getBlock();
      }
      // Trace up the postdominator tree from BlockN (inclusive) to BlockL
      // (exclusive) to find blocks control dependent on BlockM. This also
      // handles the case that BlockN does postdominate BlockM; no blocks
      // are control dependent on BlockM.
      for (auto Node = PDT.getNode(BlockN); Node && Node->getBlock() != BlockL;
            Node = Node->getIDom()) {
        auto BB = Node->getBlock();
        LLVM_DEBUG(dbgs() << "  " << BB->getName() << " needs predicating\n");
        auto PBEntry = &PredicatedBlocks[BB];
        if (*PBEntry && *PBEntry != SimdWidth)
          DiagnosticInfoSimdCF::emit(Br, "mismatching SIMD CF width");
        *PBEntry = SimdWidth;
      }
    }
  }
}

/***********************************************************************
 * markPredicatedBranches : mark the branch in any to-be-predicated block
 *    as a simd branch, even if it is unconditional
 *
 * This errors if it finds anything other than a BranchInst. Using switch or
 * return inside simd control flow is not allowed.
 */
void CMSimdCFLower::markPredicatedBranches()
{
  for (auto pbi = PredicatedBlocks.begin(), pbe = PredicatedBlocks.end();
      pbi != pbe; ++pbi) {
    auto BB = pbi->first;
    unsigned SimdWidth = pbi->second;
    auto Term = BB->getTerminator();
    if (!isa<BranchInst>(Term))
      DiagnosticInfoSimdCF::emit(Term, "return or switch not allowed in SIMD control flow");
    if (!SimdBranches[BB])
      LLVM_DEBUG(dbgs() << "branch at " << BB->getName() << " becomes simd\n");
    SimdBranches[BB] = SimdWidth;
  }
}

static void fixPHIInput(BasicBlock *Succ, BasicBlock *OldPred, BasicBlock *NewPred)
{
  for (BasicBlock::iterator SBI = Succ->begin(), SBE = Succ->end();
    SBI != SBE; ++SBI) {
    PHINode *phi = dyn_cast<PHINode>(SBI);
    if (!phi)
      break;
    Value *SrcV = phi->getIncomingValueForBlock(OldPred);
    phi->removeIncomingValue(OldPred);
    phi->addIncoming(SrcV, NewPred);
  }
}
/***********************************************************************
 * fixSimdBranches : fix simd branches ready for JIP determination
 *
 * - remove backward simd branches
 * - ensure that the false leg is fallthrough
 */
void CMSimdCFLower::fixSimdBranches()
{
  // Scan through all basic blocks, remembering which ones we have seen.
  std::set<BasicBlock *> Seen;
  for (auto fi = F->begin(), fe = F->end(); fi != fe; ++fi) {
    BasicBlock *BB = &*fi;
    Seen.insert(BB);
    if (!SimdBranches.count(BB))
      continue;
    // This is a simd branch.
    auto Br = cast<BranchInst>(BB->getTerminator());
    bool IsBackward = false;
    // Check for backward branch in either leg.
    for (unsigned si = 0, se = Br->getNumSuccessors(); si != se; ++si) {
      BasicBlock *Succ = Br->getSuccessor(si);
      if (Seen.find(Succ) != Seen.end()) {
        LLVM_DEBUG(dbgs() << "simd branch at " << BB->getName() << " succ " << si << " is backward\n");
        if (!Br->isConditional()) {
          // Unconditional simd backward branch. We can just remove its simdness.
          LLVM_DEBUG(dbgs() << " unconditional, so unsimding\n");
          SimdBranches.erase(SimdBranches.find(BB));
        } else {
          // Conditional simd branch where a leg is backward. Insert an extra block.
          IsBackward = true;
          auto NextBB = BB->getNextNode();
          auto NewBB = BasicBlock::Create(BB->getContext(),
                BB->getName() + ".backward", BB->getParent(), NextBB);
          BranchInst::Create(Succ, NewBB)->setDebugLoc(Br->getDebugLoc());
          Br->setSuccessor(si, NewBB);
          fixPHIInput(Succ, BB, NewBB);
        }
      }
    }
    // fix loop-end critical edge
    if (IsBackward) {
      for (unsigned si = 0, se = Br->getNumSuccessors(); si != se; ++si) {
        BasicBlock *Succ = Br->getSuccessor(si);
        if (Seen.find(Succ) == Seen.end() &&
            Succ->getUniquePredecessor() == nullptr) {
          auto NewBB = BasicBlock::Create(BB->getContext(),
            BB->getName() + ".loopend", BB->getParent(), Succ);
          BranchInst::Create(Succ, NewBB)->setDebugLoc(Br->getDebugLoc());
          Br->setSuccessor(si, NewBB);
        }
      }
    }
    if (Br->isConditional()) {
      // Ensure that the false leg is fallthrough.
      auto NextBB = BB->getNextNode();
      if (Br->getSuccessor(1) != NextBB) {
        if (Br->getSuccessor(0) != NextBB) {
          // Neither leg is fallthrough. Add an extra basic block to make the
          // false one fallthrough.
          LLVM_DEBUG(dbgs() << "simd branch at " << BB->getName() << ": inserted fallthrough\n");
          auto Succ = Br->getSuccessor(1);
          auto NewBB = BasicBlock::Create(BB->getContext(),
                BB->getName() + ".fallthrough", BB->getParent(), NextBB);
          PredicatedBlocks[NewBB] = PredicatedBlocks[Br->getSuccessor(0)];
          BranchInst::Create(Succ, NewBB)->setDebugLoc(Br->getDebugLoc());
          Br->setSuccessor(1, NewBB);
          fixPHIInput(Succ, BB, NewBB);
        } else {
          // The true leg is fallthrough. Invert the branch.
          LLVM_DEBUG(dbgs() << "simd branch at " << BB->getName() << ": inverting\n");
          Use *U = getSimdConditionUse(Br->getCondition());
          if (!U)
            U = &Br->getOperandUse(0);
          Value *Cond = *U;
          auto Xor = BinaryOperator::Create(Instruction::Xor, *U,
              Constant::getAllOnesValue(Cond->getType()),
              "invert", cast<Instruction>(U->getUser()));
          Xor->setDebugLoc(Br->getDebugLoc());
          *U = Xor;
          Br->setSuccessor(0, Br->getSuccessor(1));
          Br->setSuccessor(1, NextBB);
        }
      }
    }
  }
}

/***********************************************************************
 * findAndSplitJoinPoints : find the join points, and split out any join point
 *      into its own basic block
 */
void CMSimdCFLower::findAndSplitJoinPoints()
{
  // cannot iterate the simd-branch blocks directly because some blocks may
  // be splitted in the loop, and the owner-block of a simd-branch may be
  // changed. So we collect the simd-branches first.
  SmallVector<Instruction*, 4> Jumps;
  for (auto sbi = SimdBranches.begin(), sbe = SimdBranches.end();
      sbi != sbe; ++sbi) {
    auto Br = sbi->first->getTerminator();
    Jumps.push_back(Br);
  }
  for (auto sji = Jumps.begin(), sje = Jumps.end(); sji != sje; ++sji) {
    assert((*sji)->isTerminator() && "Expected terminator inst");
    auto Br = cast<VCINTR::TerminatorInst>(*sji);
    unsigned SimdWidth = SimdBranches[Br->getParent()];
    LLVM_DEBUG(dbgs() << *Br << "\n");
    auto JP = Br->getSuccessor(0);
    if (JoinPoints.count(JP))
      continue;
    JoinToGoto[JP] = Br->getParent();
    // This is a new join point.
    LLVM_DEBUG(dbgs() << "new join point " << JP->getName() << "\n");
    auto SplitBB = JP->splitBasicBlock(JP->getFirstNonPHI(), ".afterjoin");
    // We need to split it into its own basic block, so later we can modify
    // the join to do a branch to its JIP.
    if (PredicatedBlocks.find(JP) != PredicatedBlocks.end())
      PredicatedBlocks.insert(std::make_pair(SplitBB, PredicatedBlocks[JP]));
    if (SimdBranches.find(JP) != SimdBranches.end()) {
      assert( SimdBranches[JP] == SimdWidth);
      SimdBranches[SplitBB] = SimdWidth;
      SimdBranches.erase(JP);
    }
    LLVM_DEBUG(dbgs() << "split join point " << JP->getName() << " out to " << SplitBB->getName() << "\n");
    JoinPoints[JP] = SimdWidth;
  }
}

/***********************************************************************
 * determineJIPs : determine the JIPs for the gotos and joins
 */
void CMSimdCFLower::determineJIPs()
{
  LLVM_DEBUG(dbgs() << "determineJIPs: " << F->getName() << "\n");
  // Number the basic blocks.
  std::map<BasicBlock *, unsigned> Numbers;
  unsigned Num = 0;
  for (auto fi = F->begin(), fe = F->end(); fi != fe; ++fi) {
    BasicBlock *BB = &*fi;
    Numbers[BB] = Num++;
  }
  // Work out which joins do not need a JIP at all. Doing that helps avoid
  // problems in the GenX backend where a join that turns out to be a branching
  // join label needs to be in a basic block by itself, so other code has to be
  // moved out, which is not always possible.
  //
  // A join does not need a JIP if we can guarantee that any path reaching the
  // join will result in at least one channel being enabled.
  //
  // As a proxy for that, which is sufficient but maybe not necessary, we
  // divide the control flow up into groups. Two groups are either disjoint, or
  // one is nested inside the other. Then the join at the end of a group does
  // not need a JIP.
  //
  // We find the groups as follows: any edge that is not a fallthrough edge
  // causes the target block and the block after the branch block to be in the
  // same group.
  Grouping<BasicBlock *> Groups;
  for (auto NextBB = &F->front(), EndBB = &F->back(); NextBB;) {
    auto BB = NextBB;
    NextBB = BB == EndBB ? nullptr : BB->getNextNode();
    auto Term = cast<VCINTR::TerminatorInst>(BB->getTerminator());
    for (unsigned si = 0, se = Term->getNumSuccessors(); si != se; ++si) {
      BasicBlock *Succ = Term->getSuccessor(si);
      if (Succ == NextBB)
        continue;
      // We have a non-fallthrough edge BB -> Succ. Thus NextBB and Succ need
      // to be in the same group.
      if (NextBB && Succ) {
        LLVM_DEBUG(dbgs() << "joinGroups " << NextBB->getName() << " " << Succ->getName() << "\n");
      } else {
        LLVM_DEBUG(dbgs() << "Warning: NextBB or Succ is nullptr\n");
      }
      Groups.joinGroups(NextBB, Succ);
    }
  }
  // Repeat until we stop un-simding branches...
  for (;;) {
    // Determine the JIPs for the SIMD branches.
    for (auto sbi = SimdBranches.begin(), sbe = SimdBranches.end();
        sbi != sbe; ++sbi)
      determineJIP(sbi->first, &Numbers, /*IsJoin=*/false);
    // Determine the JIPs for the joins. A join does not need a JIP if it is the
    // last block in its group.
    std::set<BasicBlock *> SeenGroup;
    for (auto BB = &F->back();;) {
      LLVM_DEBUG(dbgs() << "  " << BB->getName() << " is group " << Groups.getGroup(BB)->getName() << "\n");
      if (JoinPoints.count(BB)) {
        if (!SeenGroup.insert(Groups.getGroup(BB)).second)
          determineJIP(BB, &Numbers, /*IsJoin=*/true);
        else
          LLVM_DEBUG(dbgs() << BB->getName() << " does not need JIP\n");
      }
      if (BB == &F->front())
        break;
      BB = BB->getPrevNode();
    }

    // See if we have any unconditional branch with UIP == JIP or no JIP. If so,
    // it can stay as a scalar unconditional branch.
    SmallVector<BasicBlock *, 4> BranchesToUnsimd;
    std::set<BasicBlock *> UIPs;
    for (auto sbi = SimdBranches.begin(), sbe = SimdBranches.end();
        sbi != sbe; ++sbi) {
      BasicBlock *BB = sbi->first;
      auto Br = cast<BranchInst>(BB->getTerminator());
      BasicBlock *UIP = Br->getSuccessor(0);
      BasicBlock *JIP = JIPs[BB];
      if (!Br->isConditional() && (!JIP || UIP == JIP)) {
        LLVM_DEBUG(dbgs() << BB->getName() << ": converting back to unconditional branch to " << UIP->getName() << "\n");
        BranchesToUnsimd.push_back(BB);
      } else
        UIPs.insert(UIP);
    }
    // If we did not un-simd any branch, we are done.
    if (BranchesToUnsimd.empty())
      break;
    for (auto i = BranchesToUnsimd.begin(), e = BranchesToUnsimd.end(); i != e; ++i)
      SimdBranches.erase(SimdBranches.find(*i));

    // For each join, see if it is still the UIP of any goto. If not, remove it.
    SmallVector<BasicBlock *, 4> JoinsToRemove;
    for (auto i = JoinPoints.begin(), e = JoinPoints.end(); i != e; ++i)
      if (UIPs.find(i->first) == UIPs.end())
        JoinsToRemove.push_back(i->first);
    for (auto i = JoinsToRemove.begin(), e = JoinsToRemove.end(); i != e; ++i) {
      LLVM_DEBUG(dbgs() << (*i)->getName() << ": removing now unreferenced join\n");
      JoinPoints.erase(JoinPoints.find(*i));
    }
  }
}

/***********************************************************************
 * determineJIP : determine the JIP for a goto or join
 */
void CMSimdCFLower::determineJIP(BasicBlock *BB,
      std::map<BasicBlock *, unsigned> *Numbers, bool IsJoin)
{
  BasicBlock *UIP = nullptr;
  auto Br = cast<BranchInst>(BB->getTerminator());
  if (!IsJoin)
    UIP = Br->getSuccessor(0); // this is a goto with a UIP, not a join
  LLVM_DEBUG(dbgs() << BB->getName() << ": UIP is " << (UIP ? UIP->getName() : "(none)") << "\n");
  // Scan forwards to find the next join point that could be resumed by any
  // code before or at BB.
  unsigned BBNum = (*Numbers)[BB];
  bool NeedNextJoin = false;
  BasicBlock *JP = BB->getNextNode();
  unsigned JPNum = BBNum + 1;
  for (;; JP = JP->getNextNode(), ++JPNum) {
    assert(JP);
    if ((*Numbers)[JP] != JPNum)
      LLVM_DEBUG(dbgs() << JP->getName() << " number " << (*Numbers)[JP]
                   << " does not match " << JPNum << " for " << JP->getName()
                   << "\n");
    assert((*Numbers)[JP] == JPNum);
    // If we have reached UIP, then that is also JIP.
    if (JP == UIP)
      break;
    // See if JP is a basic block with a branch from before BB.
    for (auto ui = JP->use_begin(), ue = JP->use_end(); ui != ue; ++ui) {
      auto BranchBlock = cast<Instruction>(ui->getUser())->getParent();
      if ((*Numbers)[BranchBlock] < BBNum) {
        NeedNextJoin = true;
        break;
      }
    }
    if (NeedNextJoin && JoinPoints.count(JP))
      break; // found join point
    // See if JP finishes with a branch to BB or before.
    auto Term = cast<VCINTR::TerminatorInst>(JP->getTerminator());
    for (unsigned si = 0, se = Term->getNumSuccessors(); si != se; ++si) {
      auto Succ = Term->getSuccessor(si);
      if ((*Numbers)[Succ] <= BBNum) {
        NeedNextJoin = true;
        break;
      }
    }
    assert(JP != &BB->getParent()->back() && "reached end");
  }
  LLVM_DEBUG(dbgs() << BB->getName() << ": JIP is " << JP->getName() << "\n");
  JIPs[BB] = JP;
}

/***********************************************************************
 * predicateCode : predicate the instructions in the code
 */
void CMSimdCFLower::predicateCode(unsigned CMWidth)
{
  if (CMWidth) {
    // Inside a predicated call, also predicate all other blocks. We do this
    // first so the entry block gets done before any other block, avoiding a
    // problem that code we insert to set up the EMs and RMs accidentally gets
    // predicated.
    for (auto fi = F->begin(), fe = F->end(); fi != fe; ++fi) {
      BasicBlock *BB = &*fi;
      if (PredicatedBlocks.find(BB) == PredicatedBlocks.end())
        predicateBlock(BB, CMWidth);
    }
  }
  // Predicate all basic blocks that need it.
  for (auto pbi = PredicatedBlocks.begin(), pbe = PredicatedBlocks.end();
      pbi != pbe; ++pbi) {
    BasicBlock *BB = pbi->first;
    unsigned SimdWidth = pbi->second;
    predicateBlock(BB, SimdWidth);
  }
}

/***********************************************************************
 * predicateBlock : add predication to a basic block
 *
 * Enter:   BB = basic block
 *          SimdWidth = simd width of controlling simd branch or call mask
 */
void CMSimdCFLower::predicateBlock(BasicBlock *BB, unsigned SimdWidth)
{
  for (auto bi = BB->begin(), be = BB->end(); bi != be; ) {
    Instruction *Inst = &*bi;
    ++bi; // Increment here in case Inst is removed
    predicateInst(Inst, SimdWidth);
  }
}

/***********************************************************************
 * createWrRegion : create wrregion instruction
 *
 * Enter:   Args = the args for wrregion
 *          Name
 *          InsertBefore
 */
static CallInst *createWrRegion(ArrayRef<Value *> Args, const Twine &Name,
    Instruction *InsertBefore)
{
  Type *OverloadedTypes[] = { Args[0]->getType(), Args[1]->getType(),
      Args[5]->getType(), Args[7]->getType() };
  Module *M = InsertBefore->getParent()->getParent()->getParent();
  Function *Decl = GenXIntrinsic::getGenXDeclaration(M,
      OverloadedTypes[0]->isFPOrFPVectorTy()
        ? GenXIntrinsic::genx_wrregionf : GenXIntrinsic::genx_wrregioni,
      OverloadedTypes);
  auto WrRegion = CallInst::Create(Decl, Args, Name, InsertBefore);
  WrRegion->setDebugLoc(InsertBefore->getDebugLoc());
  return WrRegion;
}

/***********************************************************************
 * predicateInst : add predication to an Instruction if necessary
 *
 * Enter:   Inst = the instruction
 *          SimdWidth = simd cf width in force
 */
void CMSimdCFLower::predicateInst(Instruction *Inst, unsigned SimdWidth) {
  if (isa<StoreInst>(Inst) || GenXIntrinsic::isVStore(Inst)) {
    predicateStore(Inst, SimdWidth);
    return;
  }

  if (auto CI = dyn_cast<CallInst>(Inst)) {
    unsigned IntrinsicID = GenXIntrinsic::getAnyIntrinsicID(Inst);
    auto Callee = CI->getCalledFunction();
    switch (IntrinsicID) {
      case GenXIntrinsic::genx_rdregioni:
      case GenXIntrinsic::genx_rdregionf:
      case GenXIntrinsic::genx_wrregioni:
      case GenXIntrinsic::genx_wrregionf:
      case GenXIntrinsic::genx_simdcf_any:
      case GenXIntrinsic::genx_vload:
      case GenXIntrinsic::genx_vstore:
      case GenXIntrinsic::genx_simdcf_savemask:
      case GenXIntrinsic::genx_simdcf_unmask:
      case GenXIntrinsic::genx_simdcf_remask:
      case GenXIntrinsic::genx_unmask_begin:
      case GenXIntrinsic::genx_unmask_end:
      case Intrinsic::lifetime_start:
      case Intrinsic::lifetime_end:
        return; // ignore these intrinsics

      // These intrinsics can be predicated but they do not have
      // explicit predicate operand: they use predicate of wrregion.
      case GenXIntrinsic::genx_gather_scaled2:
      case GenXIntrinsic::genx_gather4_scaled2:
        return;

      case GenXIntrinsic::genx_simdcf_predicate:
        rewritePredication(CI, SimdWidth);
        return;
      case GenXIntrinsic::genx_raw_send:
      case GenXIntrinsic::genx_raw_send_noresult:
      case GenXIntrinsic::genx_raw_sends:
      case GenXIntrinsic::genx_raw_sends_noresult:
        predicateSend(CI, IntrinsicID, SimdWidth);
        return;
      case GenXIntrinsic::not_any_intrinsic:
        // Call to a real subroutine.
        // Ignore those SIMT entry function for direct calls, for indirect ones
        // conservatively allow everything for now.
        if (!Callee || (!Callee->hasFnAttribute("CMGenxSIMT") &&
                        !Callee->hasFnAttribute("CMGenxNoSIMDPred"))) {
          predicateCall(CI, SimdWidth);
        }
        return;
    }
    // An IntrNoMem intrinsic is an ALU intrinsic and can be ignored.
    if (Callee->doesNotAccessMemory() || CI->getNumArgOperands() == 0)
      return;
    // no predication for intrinsic marked as ISPC uniform, 
	// for example, atomic and oword_store used in printf
    if (CI->getMetadata("ISPC-Uniform") != nullptr)
      return;

    // Look for a predicate operand in operand 2, 1 or 0.
    unsigned PredNum = CI->getNumArgOperands() - 1;
    for (;;) {
      if (auto VT = dyn_cast<VectorType>(CI->getArgOperand(PredNum)->getType()))
      {
        if (VT->getElementType()->isIntegerTy(1)) {
          // We have a predicate operand.
          predicateScatterGather(CI, SimdWidth, PredNum);
          return;
        }
      }
      if (!PredNum)
        break;
      --PredNum;
    }
    DiagnosticInfoSimdCF::emit(CI, "illegal instruction inside SIMD control flow");
    return;
  }
}

/***********************************************************************
 * rewritePredication : convert a predication intrinsic call into a
 * selection based on the region's SIMD predicate mask.
 *
 * Enter:   Inst = the predication intrinsic call instruction
 *          SimdWidth = simd cf width in force
 */
void CMSimdCFLower::rewritePredication(CallInst *CI, unsigned SimdWidth)
{
  auto EnabledValues = CI->getArgOperand(0);
  auto DisabledDefaults = CI->getArgOperand(1);

  assert(isa<VectorType>(EnabledValues->getType()) &&
         EnabledValues->getType() == DisabledDefaults->getType() &&
         "malformed predication intrinsic");

  if (VCINTR::VectorType::getNumElements(
          cast<VectorType>(EnabledValues->getType())) != SimdWidth) {
    DiagnosticInfoSimdCF::emit(CI, "mismatching SIMD width inside SIMD control flow");
    return;
  }
  auto EM = loadExecutionMask(CI, SimdWidth);
  auto Select = SelectInst::Create(EM, EnabledValues, DisabledDefaults,
      EnabledValues->getName() + ".simdcfpred", CI);
  Select->setDebugLoc(CI->getDebugLoc());
  CI->replaceAllUsesWith(Select);
  eraseInstruction(CI);
}

static bool IsBitCastForLifetimeMark(const Value *V) {
  if (!V || !isa<BitCastInst>(V)) {
    return false;
  }
  for (auto U : V->users()) {
    unsigned IntrinsicID = GenXIntrinsic::getAnyIntrinsicID(U);
    if (IntrinsicID != Intrinsic::lifetime_start &&
        IntrinsicID != Intrinsic::lifetime_end) {
      return false;
    }
  }
  return true;
}

static bool isSingleBlockLocalStore(const Instruction *SI)
{
  const Value *P = SI->getOperand(1);
  // pointer has to be an alloca
  if (isa<AllocaInst>(P)) {
    // check every uses of P, it has to be either a lift-time intrinsic or a
    // load/store in the same basic block.
    auto BLK = SI->getParent();
    for (auto U : P->users()) {
      if (isa<LoadInst>(U) || isa<StoreInst>(U) ||
          GenXIntrinsic::isVLoadStore(U)) {
        if (cast<Instruction>(U)->getParent() != BLK)
          return false;
      } else if (!IsBitCastForLifetimeMark(U))
        return false;
    }
    return true;
  }
  return false;
}

static bool replicatesMask(Function *F) {
  return F->hasFnAttribute(genx::FunctionMD::CMGenxReplicateMask);
}

static unsigned getNumChannelsReplicated(Function *F) {
  assert(replicatesMask(F) &&
         "Expected function with 'genx_replicate_mask' attribute");
  uint32_t NumChannels = 0;
  F->getFnAttribute(genx::FunctionMD::CMGenxReplicateMask)
      .getValueAsString()
      .getAsInteger(0, NumChannels);
  return NumChannels;
}

// Instructions like gather4 or functions which use gather4
// (marked with genx_replicate_mask attribute) have more output than execution
// size. In this case, subsequent store will be wider. Handle this case here.
unsigned CMSimdCFLower::deduceNumChannels(Instruction *SI) {
  assert((isa<StoreInst>(SI) || GenXIntrinsic::isVStore(SI)) &&
         "Store inst expected");
  unsigned NumChannels = 1;
  Value *StoredValue = SI->getOperand(0);
  // TODO: handle cases when stored value is used in cast instructions

  // If it's not a call there can't be possible replication of the mask
  if (!isa<CallInst>(StoredValue))
    return NumChannels;

  auto *CI = cast<CallInst>(StoredValue);

  if (Function *F = CI->getCalledFunction()) {
    if (!GenXIntrinsic::isGenXIntrinsic(F)) {
       if (replicatesMask(F))
         return getNumChannelsReplicated(F);
      return NumChannels;
    }
  }
  // If it's not a function call then check for a specific instruction
  unsigned IID = GenXIntrinsic::getGenXIntrinsicID(CI);
  switch (IID) {
  case GenXIntrinsic::genx_gather4_masked_scaled2:
  case GenXIntrinsic::genx_gather4_scaled2: {
    unsigned AddrElems = VCINTR::VectorType::getNumElements(
        cast<VectorType>(CI->getOperand(4)->getType()));
    unsigned ResultElems =
        VCINTR::VectorType::getNumElements(cast<VectorType>(CI->getType()));
    NumChannels = ResultElems / AddrElems;
    break;
  }
  default:
    break;
  }

  return NumChannels;
}
/***********************************************************************
 * predicateStore : add predication to a StoreInst
 *
 * Enter:   Inst = the instruction
 *          SimdWidth = simd cf width in force
 *
 * This code avoids using the utility functions and classes for the wrregion
 * intrinsic that are in the GenX backend because this pass is not part of the
 * GenX backend.
 */
void CMSimdCFLower::predicateStore(Instruction *SI, unsigned SimdWidth)
{
  auto V = SI->getOperand(0);
  auto StoreVT = dyn_cast<VectorType>(V->getType());
  // Scalar store not predicated
  if (!StoreVT || VCINTR::VectorType::getNumElements(StoreVT) == 1)
    return; 
  // no predication for ISPC uniform store
  if (SI->getMetadata("ISPC-Uniform") != nullptr)
    return;
  // local-variable store that is only used within the same basic block 
  // do not need predicate
  if (isSingleBlockLocalStore(SI))
    return;
  // See if the value to store is a wrregion (possibly predicated) of the
  // right width. If so, we predicate that instead. This also handles
  // the case that the value to store is wider than the simd CF width,
  // but there is a wrregion with the right width.
  // Also allow for a chain of multiple wrregions, as clang can generate
  // two, one for the columns and one for the rows.
  // Also skip any bitcasts.
  CallInst *WrRegionToPredicate = nullptr;
  Use *U = &SI->getOperandUse(0);
  Use *UseNeedsUpdate = nullptr;
  Value *ExistingPred = nullptr;
  for (;;) {
    if (auto BC = dyn_cast<BitCastInst>(V)) {
      U = &BC->getOperandUse(0);
      V = *U;
      continue;
    }
    auto WrRegion = dyn_cast<CallInst>(V);
    if (!WrRegion)
      break;
    auto Callee = WrRegion->getCalledFunction();
    if (!Callee)
      break;
    unsigned IID = GenXIntrinsic::getGenXIntrinsicID(WrRegion);
    if (IID != GenXIntrinsic::genx_wrregioni
         && IID != GenXIntrinsic::genx_wrregionf) {
      // genx_gather4_masked_scaled2 and genx_gather_masked_scaled2 are slightly
      // different: they  have predicate operand and their users have to be
      // predicated as well.
      if (IID == GenXIntrinsic::genx_gather4_masked_scaled2 ||
          IID == GenXIntrinsic::genx_gather_masked_scaled2) {
        assert(AlreadyPredicated.find(WrRegion) != AlreadyPredicated.end());
        if (OriginalPred.count(WrRegion))
          ExistingPred = OriginalPred[WrRegion];
        break;
      }
      // Not wrregion. See if it is an intrinsic that has already been
      // predicated; if so do not attempt to predicate the store.
      if (AlreadyPredicated.find(WrRegion) != AlreadyPredicated.end())
        return;
      // Otherwise break out of the wrregion-and-bitcast-traversing loop.
      break;
    }
    // We have a wrregion. Check its input width.
    unsigned Width = 0;
    Value *Input = WrRegion->getArgOperand(
        GenXIntrinsic::GenXRegion::NewValueOperandNum);
    if (auto VT = dyn_cast<VectorType>(Input->getType()))
      Width = VCINTR::VectorType::getNumElements(VT);
    if (Width == SimdWidth) {
      // This wrregion has the right width input. We could predicate it.
      if (WrRegionToPredicate) {
        UseNeedsUpdate = &WrRegionToPredicate->getOperandUse(
            GenXIntrinsic::GenXRegion::NewValueOperandNum);
        // if there is a bitcast in between then replace bitcats's operand
        if (auto BC = dyn_cast<BitCastInst>(UseNeedsUpdate->get()))
          UseNeedsUpdate = &BC->getOperandUse(0);
      }
      else {
        UseNeedsUpdate = U;
      }
      WrRegionToPredicate = WrRegion;
      V = WrRegionToPredicate->getArgOperand(
          GenXIntrinsic::GenXRegion::NewValueOperandNum);
      // See if it is already predicated, other than by an all true constant.
      Value *Pred = WrRegion->getArgOperand(
          GenXIntrinsic::GenXRegion::PredicateOperandNum);
      if (auto C = dyn_cast<Constant>(Pred)) {
        if (C->isAllOnesValue())
          Pred = nullptr;
      }
      if (Pred) {
        // Yes it is predicated. Stop here and further predicate it.
        break;
      }
    } else if (Width == 1) {
      // Single element wrregion. This is a scalar operation, so we do not
      // want to predicate it at all.
      return;
    } else if (Width < SimdWidth) {
      // Too narrow. Predicate the last correctly sized wrregion or the store.
      break;
    } else {
      assert(false && "unexpected data size inside SIMD control flow");
    }
  }
  if (WrRegionToPredicate) {
    // We found a wrregion to predicate. Replace it with a predicated one.
    assert(UseNeedsUpdate);
    *UseNeedsUpdate = predicateWrRegion(WrRegionToPredicate, SimdWidth);
    if (WrRegionToPredicate->use_empty())
      eraseInstruction(WrRegionToPredicate);
    return;
  }
  // Try to deduce number of channels to fit into
  // current SIMD Width (check if certain instruction used or
  // 'genx_replicate_mask' attribute is provided)
  unsigned NumChannels = deduceNumChannels(SI);
  if (VCINTR::VectorType::getNumElements(StoreVT) != SimdWidth * NumChannels) {
    DiagnosticInfoSimdCF::emit(
        SI, "mismatching SIMD width inside SIMD control flow");
    return;
  }
  // Predicate the store by creating a select.
  Instruction *Load = nullptr;
  if (auto SInst = dyn_cast<StoreInst>(SI)) {
    auto *PtrOp = SInst->getPointerOperand();
    Load = new LoadInst(PtrOp->getType()->getPointerElementType(), PtrOp,
                        PtrOp->getName() + ".simdcfpred.load",
                        false /* isVolatile */, SI);
  }
  else {
    auto ID = GenXIntrinsic::genx_vload;
    Value *Addr = SI->getOperand(1);
    Type *Tys[] = {Addr->getType()->getPointerElementType(), Addr->getType()};
    auto Fn = GenXIntrinsic::getGenXDeclaration(
        SI->getParent()->getParent()->getParent(), ID, Tys);
    Load = CallInst::Create(Fn, Addr, ".simdcfpred.vload", SI);
  }
  Load->setDebugLoc(SI->getDebugLoc());
  Value *EM = loadExecutionMask(SI, SimdWidth);

  // If there was a predicate already then update it with current EM
  if (ExistingPred) {
    EM = BinaryOperator::Create(
        Instruction::And, ExistingPred, EM,
        ExistingPred->getName() + ".and." + EM->getName(), SI);
    cast<Instruction>(EM)->setDebugLoc(SI->getDebugLoc());
  }

  // Replicate mask for each channel if needed
  EM = replicateMask(EM, SI, SimdWidth, NumChannels);

  auto Select = SelectInst::Create(EM, SI->getOperand(0), Load,
      SI->getOperand(0)->getName() + ".simdcfpred", SI);
  SI->setOperand(0, Select);
}

/***********************************************************************
 * predicateSend : predicate a raw send
 *
 * This has to cope with the case that the predicate is a scalar i1 constant
 * 1. We first convert the predicate to whatever width matches current simd
 * control flow.
 */
void CMSimdCFLower::predicateSend(CallInst *CI, unsigned IntrinsicID,
      unsigned SimdWidth)
{
  unsigned PredOperandNum = 1;
  if (isa<VectorType>(CI->getOperand(PredOperandNum)->getType())) {
    // We already have a vector predicate.
    predicateScatterGather(CI, SimdWidth, PredOperandNum);
    return;
  }
  IRBuilder<> Builder(CI);
  Builder.SetCurrentDebugLocation(CI->getDebugLoc());
  // Need to convert scalar predicate to vector. We need to get a new intrinsic
  // declaration from an array of overloaded types, and that depends on exactly
  // which send intrinsic we have.
  auto Pred = Builder.CreateVectorSplat(
      SimdWidth, cast<Constant>(CI->getOperand(PredOperandNum)));
  Function *Decl = nullptr;
  switch (IntrinsicID) {
    case GenXIntrinsic::genx_raw_send: {
      Type *Tys[] = { CI->getType(), Pred->getType(),
          CI->getOperand(4)->getType() };
      Decl = GenXIntrinsic::getGenXDeclaration(CI->getParent()->getParent()->getParent(),
            (GenXIntrinsic::ID)IntrinsicID, Tys);
      break;
    }
    case GenXIntrinsic::genx_raw_send_noresult: {
      Type *Tys[] = { Pred->getType(), CI->getOperand(4)->getType() };
      Decl = GenXIntrinsic::getGenXDeclaration(
          CI->getParent()->getParent()->getParent(),
            (GenXIntrinsic::ID)IntrinsicID, Tys);
      break;
    }
    case GenXIntrinsic::genx_raw_sends: {
      Type *Tys[] = { CI->getType(), Pred->getType(),
          CI->getOperand(4)->getType(), CI->getOperand(5)->getType() };
      Decl = GenXIntrinsic::getGenXDeclaration(
          CI->getParent()->getParent()->getParent(),
            (GenXIntrinsic::ID)IntrinsicID, Tys);
      break;
    }
    case GenXIntrinsic::genx_raw_sends_noresult: {
      Type *Tys[] = { Pred->getType(), CI->getOperand(4)->getType(),
          CI->getOperand(5)->getType() };
      Decl = GenXIntrinsic::getGenXDeclaration(
          CI->getParent()->getParent()->getParent(),
            (GenXIntrinsic::ID)IntrinsicID, Tys);
      break;
    }
    default:
      llvm_unreachable("unexpected send intrinsic");
      break;
  }
  SmallVector<Value *, 8> Args;
  for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i)
    if (i == PredOperandNum)
      Args.push_back(Pred);
    else
      Args.push_back(CI->getOperand(i));

  auto NewCI = Builder.CreateCall(Decl, Args, CI->getName());
  CI->replaceAllUsesWith(NewCI);
  eraseInstruction(CI);
  // Now we can predicate the new send instruction.
  predicateScatterGather(NewCI, SimdWidth, PredOperandNum);
}

/***********************************************************************
 * predicateScatterGather : predicate a scatter/gather intrinsic call
 *
 * This works on the scatter/gather intrinsics with a predicate operand.
 */
void CMSimdCFLower::predicateScatterGather(CallInst *CI, unsigned SimdWidth,
      unsigned PredOperandNum)
{
  Value *OldPred = CI->getArgOperand(PredOperandNum);
  assert(OldPred->getType()->getScalarType()->isIntegerTy(1));
    if (SimdWidth != VCINTR::VectorType::getNumElements(
                         cast<VectorType>(OldPred->getType()))) {
      DiagnosticInfoSimdCF::emit(
          CI,
          "mismatching SIMD width of scatter/gather inside SIMD control flow");
      return;
  }
  Instruction *NewPred = loadExecutionMask(CI, SimdWidth);
  if (auto C = dyn_cast<Constant>(OldPred))
    if (C->isAllOnesValue())
      OldPred = nullptr;
  if (OldPred) {
    OriginalPred[CI] = OldPred;
    auto And = BinaryOperator::Create(Instruction::And, OldPred, NewPred,
        OldPred->getName() + ".and." + NewPred->getName(), CI);
    And->setDebugLoc(CI->getDebugLoc());
    NewPred = And;
  }
  CI->setArgOperand(PredOperandNum, NewPred);
  AlreadyPredicated.insert(CI);
}

/***********************************************************************
 * predicateWrRegion : create a predicated version of a wrregion
 *
 * Enter:   WrR = the wrregion, whose value width must be equal to the
 *                simd CF width
 *          SimdWidth = simd cf width in force
 *
 * Return:  the new predicated wrregion
 *
 * If the wrregion is already predicated, the new one has a predicated that
 * is an "and" of the original predicate and our EM.
 */
CallInst *CMSimdCFLower::predicateWrRegion(CallInst *WrR, unsigned SimdWidth)
{
  // First gather the args of the original wrregion.
  SmallVector<Value *, 8> Args;
  for (unsigned i = 0, e = WrR->getNumArgOperands(); i != e; ++i)
    Args.push_back(WrR->getArgOperand(i));
  // Modify the predicate in Args.
  Value *Pred = Args[GenXIntrinsic::GenXRegion::PredicateOperandNum];
  if (auto C = dyn_cast<Constant>(Pred))
    if (C->isAllOnesValue())
      Pred = nullptr;
  auto EM = loadExecutionMask(WrR, SimdWidth);
  if (!Pred)
    Pred = EM;
  else {
    OriginalPred[WrR] = Pred;
    auto And = BinaryOperator::Create(Instruction::And, EM, Pred,
        Pred->getName() + ".and." + EM->getName(), WrR);
    And->setDebugLoc(WrR->getDebugLoc());
    Pred = And;
  }
  Args[GenXIntrinsic::GenXRegion::PredicateOperandNum] = Pred;
  return createWrRegion(Args, WrR->getName(), WrR);
}

/***********************************************************************
 * predicateCall : predicate a real call to a subroutine
 */
void CMSimdCFLower::predicateCall(CallInst *CI, unsigned SimdWidth)
{
  Function *F = CI->getCalledFunction();
  // TODO: support width warnings for indirect calls,
  // now PSEntry for them is actually fake as F=nullptr for such cases
  auto PSEntry = &PredicatedSubroutines[F];

  // Skip predicating recursive function
  if (CI->getFunction() == F)
    return;

  if (!*PSEntry)
    *PSEntry = SimdWidth;
  else if (*PSEntry != SimdWidth)
    DiagnosticInfoSimdCF::emit(CI, "mismatching SIMD width of called subroutine");
}

/***********************************************************************
 * lowerSimdCF : lower the simd control flow
 */
void CMSimdCFLower::lowerSimdCF()
{
  IRBuilder<> Builder(F->getContext());
  // First lower the simd branches.
  for (auto sbi = SimdBranches.begin(), sbe = SimdBranches.end();
      sbi != sbe; ++sbi) {
    BasicBlock *BB = sbi->first;

    auto Br = cast<BranchInst>(BB->getTerminator());
    Builder.SetInsertPoint(Br);

    BasicBlock *UIP = Br->getSuccessor(0);
    BasicBlock *JIP = JIPs[BB];
    LLVM_DEBUG(dbgs() << "lower branch at " << BB->getName() << ", UIP=" << UIP->getName() << ", JIP=" << JIP->getName() << "\n");
    if (!Br->isConditional()) {
      // Unconditional branch.  Turn it into a conditional branch on true,
      // adding a fallthrough on false.
      auto NewBr = Builder.CreateCondBr(
          Constant::getAllOnesValue(Type::getInt1Ty(BB->getContext())), UIP,
          BB->getNextNode());
      eraseInstruction(Br);
      Br = NewBr;
    }
    Value *Cond = Br->getCondition();
    Use *CondUse = getSimdConditionUse(Cond);
    DebugLoc DL = Br->getDebugLoc();
    if (CondUse)
      Cond = *CondUse;
    else {
      // Branch is currently scalar. Splat to a vector condition.
      unsigned SimdWidth = PredicatedBlocks[BB];
      if (auto C = dyn_cast<Constant>(Cond))
        Cond = Builder.CreateVectorSplat(SimdWidth, C);
      else {
        Cond = Br->getCondition();
        Type *VecTy = VCINTR::getVectorType(Cond->getType(), 1);
        Value *Undef = UndefValue::get(VecTy);
        Type *I32Ty = Type::getInt32Ty(Cond->getContext());
        auto Insert = Builder.CreateInsertElement(Undef, Cond,
                                                  Constant::getNullValue(I32Ty),
                                                  Cond->getName() + ".splat");
        auto Splat = Builder.CreateShuffleVector(
            Insert, Undef,
            Constant::getNullValue(VCINTR::getVectorType(I32Ty, SimdWidth)),
            Insert->getName());
        Cond = Splat;
      }
    }
    // Insert {NewEM,NewRM,BranchCond} = llvm.genx.simdcf.goto(OldEM,OldRM,~Cond)
     // TODO: rewrite everything below using IRBuilder
    unsigned SimdWidth =
        VCINTR::VectorType::getNumElements(cast<VectorType>(Cond->getType()));
    auto NotCond = BinaryOperator::Create(Instruction::Xor, Cond,
        Constant::getAllOnesValue(Cond->getType()), Cond->getName() + ".not",
        Br);
    Value *RMAddr = getRMAddr(UIP, SimdWidth);
    Instruction *OldEM =
        new LoadInst(EMVar->getType()->getPointerElementType(), EMVar,
                     EMVar->getName(), false /* isVolatile */, Br);
    OldEM->setDebugLoc(DL);
    auto OldRM =
        new LoadInst(RMAddr->getType()->getPointerElementType(), RMAddr,
                     RMAddr->getName(), false /* isVolatile */, Br);
    OldRM->setDebugLoc(DL);
    Type *Tys[] = { OldEM->getType(), OldRM->getType() };
    auto GotoFunc = GenXIntrinsic::getGenXDeclaration(BB->getParent()->getParent(),
      GenXIntrinsic::genx_simdcf_goto, Tys);
    Value *Args[] = { OldEM, OldRM, NotCond };
    auto Goto = CallInst::Create(GotoFunc, Args, "goto", Br);
    Goto->setDebugLoc(DL);
    Goto->setConvergent();
    Instruction *NewEM = ExtractValueInst::Create(Goto, 0, "goto.extractem", Br);
    (new StoreInst(NewEM, EMVar, false /* isVolatile */, Br))->setDebugLoc(DL);
    auto NewRM = ExtractValueInst::Create(Goto, 1, "goto.extractrm", Br);
    (new StoreInst(NewRM, RMAddr, false /* isVolatile */, Br))->setDebugLoc(DL);
    auto BranchCond = ExtractValueInst::Create(Goto, 2, "goto.extractcond", Br);
    // Change the branch condition.
    auto OldCond = dyn_cast<Instruction>(Br->getCondition());
    Br->setCondition(BranchCond);
    // Change the branch target to JIP.
    Br->setSuccessor(0, JIP);
    // Erase the old llvm.genx.simdcf.any.
    if (OldCond && OldCond->use_empty())
      eraseInstruction(OldCond);
  }
  // Then lower the join points.
  for (auto jpi = JoinPoints.begin(), jpe = JoinPoints.end();
      jpi != jpe; ++jpi) {
    BasicBlock *JP = jpi->first;
    unsigned SimdWidth = jpi->second;
    LLVM_DEBUG(dbgs() << "lower join point " << JP->getName() << "\n");
    DebugLoc DL = JP->front().getDebugLoc();
    Instruction *InsertBefore = JP->getFirstNonPHI();
    // Insert {NewEM,BranchCond} = llvm.genx.simdcf.join(OldEM,RM)
    Value *RMAddr = getRMAddr(JP, SimdWidth);
    Instruction *OldEM =
        new LoadInst(EMVar->getType()->getPointerElementType(), EMVar,
                     EMVar->getName(), false /* isVolatile */, InsertBefore);
    OldEM->setDebugLoc(DL);
    auto RM =
        new LoadInst(RMAddr->getType()->getPointerElementType(), RMAddr,
                     RMAddr->getName(), false /* isVolatile */, InsertBefore);
    RM->setDebugLoc(DL);
    Type *Tys[] = { OldEM->getType(), RM->getType() };
    auto JoinFunc = GenXIntrinsic::getGenXDeclaration(
        JP->getParent()->getParent(),
      GenXIntrinsic::genx_simdcf_join, Tys);
    Value *Args[] = { OldEM, RM };
    auto Join = CallInst::Create(JoinFunc, Args, "join", InsertBefore);
    Join->setDebugLoc(DL);
    Join->setConvergent();
    auto NewEM = ExtractValueInst::Create(Join, 0, "join.extractem", InsertBefore);
    (new StoreInst(NewEM, EMVar, false /* isVolatile */, InsertBefore))
        ->setDebugLoc(DL);
    auto BranchCond = ExtractValueInst::Create(Join, 1, "join.extractcond", InsertBefore);
    // Zero RM.
    (new StoreInst(Constant::getNullValue(RM->getType()), RMAddr,
                   false /* isVolatile */, InsertBefore))
        ->setDebugLoc(DL);
    BasicBlock *JIP = JIPs[JP];
    if (JIP) {
      // This join point is in predicated code, so it was separated into its
      // own block. It needs to be turned into a conditional branch to JIP,
      // with the condition from llvm.genx.simdcf.join.
      auto Br = cast<BranchInst>(JP->getTerminator());
      assert(!Br->isConditional());
      auto NewBr = BranchInst::Create(JIP, JP->getNextNode(), BranchCond, Br);
      assert(JoinToGoto.count(JP));
      NewBr->setDebugLoc(DL);
      eraseInstruction(Br);
      auto *OrigBranch = cast<BranchInst>(JoinToGoto.at(JP)->getTerminator());
      if (OrigBranch->isConditional())
        fixPHIInput(JIP,
                    (OrigBranch->getSuccessor(0) == JP
                         ? OrigBranch->getSuccessor(1)
                         : OrigBranch->getSuccessor(0)),
                    NewBr->getParent());
      // Get the JIP's RM, just to ensure that it knows its SIMD width in case
      // nothing else references it.
      getRMAddr(JIP, VCINTR::VectorType::getNumElements(
                         cast<VectorType>(RM->getType())));
    }
  }
}

/***********************************************************************
 * lowerUnmaskOps : lower the simd unmask begins and ends
 */
void CMSimdCFLower::lowerUnmaskOps() {
  std::vector<Instruction *> MaskBegins;
  std::vector<Instruction *> MaskEnds;
  for (auto fi = F->begin(), fe = F->end(); fi != fe; ++fi) {
    BasicBlock *BB = &*fi;
    for (auto bi = BB->begin(), be = BB->end(); bi != be; ++bi) {
      Instruction *Inst = &*bi;
      // doing the work
      if (auto CIE = dyn_cast_or_null<CallInst>(Inst)) {
        if (GenXIntrinsic::getGenXIntrinsicID(CIE) ==
            GenXIntrinsic::genx_unmask_end) {
          auto LoadV = dyn_cast<LoadInst>(CIE->getArgOperand(0));
          assert(LoadV);
          auto PtrV = dyn_cast<AllocaInst>(LoadV->getPointerOperand());
          assert(PtrV);
          StoreInst *StoreV = nullptr;
          // search uses of PtrV
          for (auto ui = PtrV->use_begin(), ue = PtrV->use_end(); ui != ue;
                ++ui) {
            if (auto SI = dyn_cast<StoreInst>(ui->getUser())) {
              StoreV = SI;
              break;
            }
          }
          assert(StoreV);
          auto *CIB = cast<CallInst>(StoreV->getValueOperand());
          assert(GenXIntrinsic::getGenXIntrinsicID(CIB) ==
                  GenXIntrinsic::genx_unmask_begin);
          MaskBegins.push_back(CIB);
          MaskEnds.push_back(CIE);
          // put in genx_simdcf_savemask and genx_simdcf_remask
          auto DL = CIB->getDebugLoc();
          Instruction *OldEM =
              new LoadInst(EMVar->getType()->getPointerElementType(), EMVar,
                           EMVar->getName(), false /* isVolatile */, CIB);
          OldEM->setDebugLoc(DL);
          Type *Tys[] = {OldEM->getType()};
          auto SavemaskFunc =  GenXIntrinsic::getGenXDeclaration(
                               BB->getParent()->getParent(),
                               GenXIntrinsic::genx_simdcf_savemask, Tys);
          Value *Args[] = {OldEM};
          auto Savemask = CallInst::Create(SavemaskFunc, Args, "savemask", CIB);
          Savemask->setDebugLoc(DL);
          // the use should be the store for savemask
          CIB->replaceAllUsesWith(Savemask); 
          Type *Ty1s[] = {OldEM->getType()};
          auto UnmaskFunc = GenXIntrinsic::getGenXDeclaration(
              BB->getParent()->getParent(), GenXIntrinsic::genx_simdcf_unmask,
              Ty1s);
          Value *Arg1s[] = {Savemask, ConstantInt::get(Savemask->getType(), 0xFFFFFFFF) };
          auto Unmask = CallInst::Create(UnmaskFunc, Arg1s, "unmask", CIB);
          Unmask->setDebugLoc(DL);
          (new StoreInst(Unmask, EMVar, false /* isVolatile */, CIB))
              ->setDebugLoc(DL);
          // put in genx_simdcf_remask
          DL = CIE->getDebugLoc();
          OldEM = new LoadInst(EMVar->getType()->getPointerElementType(), EMVar,
                               EMVar->getName(), false /* isVolatile */, CIE);
          OldEM->setDebugLoc(DL);
          Type *Ty2s[] = {OldEM->getType()};
          auto RemaskFunc = GenXIntrinsic::getGenXDeclaration(
                              BB->getParent()->getParent(),
                              GenXIntrinsic::genx_simdcf_remask, Ty2s);
          Value *Arg2s[] = {OldEM, LoadV};
          auto Remask = CallInst::Create(RemaskFunc, Arg2s, "remask", CIE);
          Remask->setDebugLoc(DL);
          (new StoreInst(Remask, EMVar, false /* isVolatile */, CIE))
              ->setDebugLoc(DL);
        }
      }
    }
  }
  // erase Mask Ends
  for (auto CIE : MaskEnds) {
    eraseInstruction(CIE);
  }
  // erase Mask Begins
  for (auto CIB : MaskBegins) {
    eraseInstruction(CIB);
  }
}

/***********************************************************************
 * getSimdConditionUse : given a branch condition, if it is
 *    llvm.genx.simdcf.any, get the vector condition
 */
Use *CMSimdCFLower::getSimdConditionUse(Value *Cond)
{
  if (auto CI = isSimdCFAny(Cond))
    return &CI->getOperandUse(0);
  return nullptr;
}

/***********************************************************************
 * isSimdCFAny : given a value (or nullptr), see if it is a call to
 *    llvm.genx.simdcf.any
 *
 * Return:  the instruction (cast to CallInst) if it is such a call
 *          else nullptr
 */
CallInst *CMSimdCFLower::isSimdCFAny(Value *V)
{
  if (GenXIntrinsic::getGenXIntrinsicID(V) == GenXIntrinsic::genx_simdcf_any)
    return cast<CallInst>(V);
  return nullptr;
}

/***********************************************************************
 * replicateMask : copy mask for provided number of channels using shufflevector
 */
Value *CMSimdCFLower::replicateMask(Value *EM, Instruction *InsertBefore,
                                    unsigned SimdWidth, unsigned NumChannels) {
  // No need to replicate the mask for one channel
  if (NumChannels == 1)
    return EM;

  SmallVector<Constant *, 128> ChannelMask{SimdWidth * NumChannels};
  for (unsigned i = 0; i < NumChannels; ++i)
    std::copy(ShuffleMask.begin(), ShuffleMask.begin() + SimdWidth,
              ChannelMask.begin() + SimdWidth * i);
  EM = new ShuffleVectorInst(
      EM, UndefValue::get(EM->getType()), ConstantVector::get(ChannelMask),
      Twine("ChannelEM") + Twine(SimdWidth), InsertBefore);

  return EM;
}

/***********************************************************************
 * loadExecutionMask : create instruction to load EM
 */
Instruction *CMSimdCFLower::loadExecutionMask(Instruction *InsertBefore,
                                              unsigned SimdWidth) {
  Instruction *EM =
      new LoadInst(EMVar->getType()->getPointerElementType(), EMVar,
                   EMVar->getName(), false /* isVolatile */, InsertBefore);

  // If the simd width is not MAX_SIMD_CF_WIDTH, extract the part of EM we want.
  if (SimdWidth == MAX_SIMD_CF_WIDTH)
    return EM;

  ArrayRef<Constant *> Mask = ShuffleMask;
  EM = new ShuffleVectorInst(EM, UndefValue::get(EM->getType()),
                             ConstantVector::get(Mask.take_front(SimdWidth)),
                             Twine("EM") + Twine(SimdWidth), InsertBefore);

  EM->setDebugLoc(InsertBefore->getDebugLoc());

  return EM;
}

/***********************************************************************
 * getRMAddr : get address of resume mask variable for a particular join
 *        point, creating the variable if necessary
 *
 * Enter:   JP = the join point
 *          SimdWidth = the simd width for the join point, used for creating
 *              the RM variable. Can be 0 as long as the RM variable already
 *              exists.
 */
Value *CMSimdCFLower::getRMAddr(BasicBlock *JP, unsigned SimdWidth)
{
  LLVM_DEBUG(dbgs() << "getRMAddr(" << JP->getName() << ", " << SimdWidth << ")\n");
  auto RMAddr = &RMAddrs[JP];
  if (!*RMAddr) {
    assert(SimdWidth);
    // Create an RM variable for this join point. Insert an alloca at the start
    // of the function.
    Type *RMTy = VCINTR::getVectorType(Type::getInt1Ty(F->getContext()), SimdWidth);
    Instruction *InsertBefore = &F->front().front();
    *RMAddr = new AllocaInst(RMTy, /*AddrSpace*/ 0,
                             Twine("RM.") + JP->getName(), InsertBefore);
    // Initialize to all zeros.
    new StoreInst(Constant::getNullValue(RMTy), *RMAddr, false /* isVolatile */,
                  InsertBefore);
  }
  assert(!SimdWidth ||
         VCINTR::VectorType::getNumElements(cast<VectorType>(
             (*RMAddr)->getType()->getPointerElementType())) == SimdWidth);
  return *RMAddr;
}

/***********************************************************************
 * DiagnosticInfoSimdCF::emit : emit an error or warning
 */
void DiagnosticInfoSimdCF::emit(Instruction *Inst, StringRef Msg,
                                DiagnosticSeverity Severity) {
  DiagnosticInfoSimdCF Err(Severity, *Inst->getParent()->getParent(),
                           Inst->getDebugLoc(), Msg);
  Inst->getContext().diagnose(Err);
}
