path: root/lib/SPIRV/SPIRVRegularizeLLVM.cpp

//===- SPIRVRegularizeLLVM.cpp - Regularize LLVM for SPIR-V ------- C++ -*-===//
//
//                     The LLVM/SPIRV Translator
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
// Copyright (c) 2014 Advanced Micro Devices, Inc. All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal with 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:
//
// Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimers.
// Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimers in the documentation
// and/or other materials provided with the distribution.
// Neither the names of Advanced Micro Devices, Inc., nor the names of its
// contributors may be used to endorse or promote products derived from this
// Software without specific prior written permission.
// 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
// CONTRIBUTORS 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 WITH
// THE SOFTWARE.
//
//===----------------------------------------------------------------------===//
//
// This file implements regularization of LLVM moduel for SPIR-V.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "spvregular"

#include "SPIRVInternal.h"
#include "OCLUtil.h"
#include "SPIRVMDBuilder.h"
#include "SPIRVMDWalker.h"

#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/ADT/Triple.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/PassSupport.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

#include <set>

using namespace llvm;
using namespace SPIRV;
using namespace OCLUtil;

namespace SPIRV {

static bool SPIRVDbgSaveRegularizedModule = false;
static std::string RegularizedModuleTmpFile = "regularized.bc";

class SPIRVRegularizeLLVM: public ModulePass {
public:
  SPIRVRegularizeLLVM():ModulePass(ID), M(nullptr), Ctx(nullptr) {
    initializeSPIRVRegularizeLLVMPass(*PassRegistry::getPassRegistry());
  }

  virtual bool runOnModule(Module &M);

  // Lower functions
  bool regularize();

  /// Erase cast inst of function and replace with the function.
  /// Assuming F is a SPIR-V builtin function with op code \param OC.
  void lowerFuncPtr(Function *F, Op OC);
  void lowerFuncPtr(Module *M);

  bool getSwitchCaseOrdering(BasicBlock *BB);

  static char ID;
private:
  Module *M;
  LLVMContext *Ctx;
};

char SPIRVRegularizeLLVM::ID = 0;

bool
SPIRVRegularizeLLVM::runOnModule(Module& Module) {
  M = &Module;
  Ctx = &M->getContext();

  DEBUG(dbgs() << "Enter SPIRVRegularizeLLVM:\n");
  regularize();

  DEBUG(dbgs() << "After SPIRVRegularizeLLVM:\n" << *M);
  std::string Err;
  raw_string_ostream ErrorOS(Err);
  if (verifyModule(*M, &ErrorOS)){
    DEBUG(errs() << "Fails to verify module: " << ErrorOS.str());
  }
  return true;
}

/// Remove entities not representable by SPIR-V
bool
SPIRVRegularizeLLVM::regularize() {
  LLVMContext *Context = &M->getContext();

  eraseUselessFunctions(M);
  lowerFuncPtr(M);
  //lowerConstantExpressions();

  for (auto I = M->begin(), E = M->end(); I != E;) {
    Function *F = I++;
    if (F->isDeclaration() && F->use_empty()) {
      F->eraseFromParent();
      continue;
    }

    for (auto BI = F->begin(), BE = F->end(); BI != BE; ++BI) {
      for (auto II = BI->begin(), IE = BI->end(); II != IE; ++II) {
        if (auto Call = dyn_cast<CallInst>(II)) {
          Call->setTailCall(false);
          if (Call->getCalledFunction()->isIntrinsic())
            removeFnAttr(Context, Call, Attribute::NoUnwind);
        }

        // Remove optimization info not supported by SPIRV
        if (auto BO = dyn_cast<BinaryOperator>(II)) {
          if (isa<OverflowingBinaryOperator>(BO)) {
            if (BO->hasNoUnsignedWrap())
              BO->setHasNoUnsignedWrap(false);
            if (BO->hasNoSignedWrap())
              BO->setHasNoSignedWrap(false);
          }
          if (isa<PossiblyExactOperator>(BO) && BO->isExact())
            BO->setIsExact(false);
        }
        // Remove metadata not supported by SPIRV
        static const char *MDs[] = {
            "fpmath",
            "tbaa",
            "range",
        };
        for (auto &MDName:MDs) {
          if (II->getMetadata(MDName)) {
            II->setMetadata(MDName, nullptr);
          }
        }
      }
    }

    if (F->getBasicBlockList().size() < 2)
      continue;
    // The order of blocks in a function must satisfy the rule
    // that blocks appear before all blocks they dominate.
    // We iterate over the SCCs in a graph in post-order
    for (scc_iterator<Function*> SCCI = scc_begin(F); !SCCI.isAtEnd(); ++SCCI) {
      const std::vector<BasicBlock *> &NextSCC = *SCCI;
      assert(!NextSCC.empty());
      for (const auto &I : NextSCC) {
        BasicBlock *BB = I;
        // The order of blocks in switch instruction shouldn't be changed
        if (!getSwitchCaseOrdering(BB))
          BB->moveAfter(&F->getEntryBlock());
      }
    }
  }

  std::string Err;
  raw_string_ostream ErrorOS(Err);
  if (verifyModule(*M, &ErrorOS)){
    SPIRVDBG(errs() << "Fails to verify module: " << ErrorOS.str();)
    return false;
  }

  if (SPIRVDbgSaveRegularizedModule)
    saveLLVMModule(M, RegularizedModuleTmpFile);
  return true;
}

// Assume F is a SPIR-V builtin function with a function pointer argument which
// is a bitcast instruction casting a function to a void(void) function pointer.
void SPIRVRegularizeLLVM::lowerFuncPtr(Function* F, Op OC) {
  DEBUG(dbgs() << "[lowerFuncPtr] " << *F << '\n');
  auto Name = decorateSPIRVFunction(getName(OC));
  std::set<Value *> InvokeFuncPtrs;
  auto Attrs = F->getAttributes();
  mutateFunction(F, [=, &InvokeFuncPtrs](
      CallInst *CI, std::vector<Value *> &Args) {
    for (auto &I:Args) {
      if (isFunctionPointerType(I->getType())) {
        InvokeFuncPtrs.insert(I);
        I = removeCast(I);
      }
    }
    return Name;
  }, nullptr, &Attrs, false);
  for (auto &I:InvokeFuncPtrs)
    eraseIfNoUse(I);
}

void
SPIRVRegularizeLLVM::lowerFuncPtr(Module* M) {
  std::vector<std::pair<Function *, Op>> Work;
  for (auto I = M->begin(), E = M->end(); I != E;) {
    Function *F = I++;
    auto AI = F->arg_begin();
    if (hasFunctionPointerArg(F, AI)) {
      auto OC = getSPIRVFuncOC(F->getName());
      assert(OC != OpNop && "Invalid function pointer usage");
      Work.push_back(std::make_pair(F, OC));
    }
  }
  for (auto &I:Work)
    lowerFuncPtr(I.first, I.second);
}

bool
SPIRVRegularizeLLVM::getSwitchCaseOrdering(BasicBlock *BB) {
  // The order of the BBs was reversed
  // We want to restore the original order of switch statement
  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
    BasicBlock *Pred = *PI;
    // Check if we have a case value
    if (auto SI = dyn_cast<SwitchInst>(Pred->getTerminator())) {
      BasicBlock* Default = SI->getDefaultDest();
      if (BB == Default)
        BB->moveAfter(Pred);
      else
        BB->moveBefore(Default);
      return true;
    }
  }
  return false;
}

}

INITIALIZE_PASS(SPIRVRegularizeLLVM, "spvregular",
    "Regularize LLVM for SPIR-V", false, false)

ModulePass *llvm::createSPIRVRegularizeLLVM() {
  return new SPIRVRegularizeLLVM();
}