2109-Source to Source LLVM 调研

翻译器调研

但是这里最重要的还是自己实现一个Demo并且测试

翻译器实验 clang-tool

这里众说纷纭，网上并没有一个”直接可用“的版本供我进行快速测试和检查，经历了一整天的失败之后，在LLVM12.0和LLVM12.1版本上，Google搜索的几乎所有方法全部失败，因为LLVM11的API大改动导致之后的GetLocStart等clang::Stmt类里的方法更名，需要重新设计测试例子。

这里测试方案重新在 LLVM clang-extra-tools 里，基于 LLVM clang tool template 进行更改和测试。

失败记录 #1

直接进行 cmake 失败，失败记录如下：

CMake Warning (dev) in CMakeLists.txt:
  No project() command is present.  The top-level CMakeLists.txt file must
  contain a literal, direct call to the project() command.  Add a line of
  code such as

    project(ProjectName)

  near the top of the file, but after cmake_minimum_required().

  CMake is pretending there is a "project(Project)" command on the first
  line.
This warning is for project developers.  Use -Wno-dev to suppress it.

CMake Error at CMakeLists.txt:6 (add_clang_executable):
  Unknown CMake command "add_clang_executable".

CMake Warning (dev) in CMakeLists.txt:
  No cmake_minimum_required command is present.  A line of code such as

    cmake_minimum_required(VERSION 3.16)

  should be added at the top of the file.  The version specified may be lower
  if you wish to support older CMake versions for this project.  For more
  information run "cmake --help-policy CMP0000".
This warning is for project developers.  Use -Wno-dev to suppress it.

-- Configuring incomplete, errors occurred!
See also "/home/chivier/opt/llvm/clang-tools/tool-template/build/CMakeFiles/CMakeOutput.log".

add_clang_executable 没有 include 合适的 .cmake 文件，所以无法使用

Unknown CMake command "add_clang_executable"

此处给出了一个不了了之的回答，并没有解决问题。之后对于LLVM的框架重新理解和思考，应该在find_package LLVM 和 libclang 入手，着手解决 LLVM 的 cmake 发现问题。

尝试用其他方法链接 LLVM 的 cmake 内容

Building LLVM example

这里只给出了解决 add_llvm_excutable 的方案，并没有解决我的问题

失败记录 #2

这里尝试直接去解决LLVM的问题，直接编译

g++ ToolTemplate.cpp -I/home/chivier/opt/llvm/llvm-download/include -std=c++14   -fno-exceptions -fno-rtti -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS `llvm-config --libs all`

这里直接采用

1 2	`llvm-config --cxxflags llvm-config --libs all`

得到llvm需要的c++编译选项和llvm需要链接选项，但是此时发现无法链接，找不到需要的链接库，报错如下：

/usr/bin/ld: cannot find -lLLVMMCParser
/usr/bin/ld: cannot find -lLLVMMC
/usr/bin/ld: cannot find -lLLVMDebugInfoCodeView
/usr/bin/ld: cannot find -lLLVMDebugInfoMSF
/usr/bin/ld: cannot find -lLLVMBitReader
/usr/bin/ld: cannot find -lLLVMCore
/usr/bin/ld: cannot find -lLLVMRemarks
/usr/bin/ld: cannot find -lLLVMBitstreamReader
/usr/bin/ld: cannot find -lLLVMBinaryFormat
/usr/bin/ld: cannot find -lLLVMTableGen
/usr/bin/ld: cannot find -lLLVMSupport
/usr/bin/ld: cannot find -lLLVMDemangle
...

失败记录 #3

根据之前的失败经验，分析之前的错误内容，主要错误集中在：add_clang_executable 的执行可行问题。在github里对该关键词进行搜索，找到和我需求最为相似的项目： https://github.com/firolino/clang-tool.git 但是编译报错还没有解决。

/home/chivier/Projects/clang-tool/src/utils/utils.cc: In function ‘bool utils::customRunToolOnCodeWithArgs(std::unique_ptr<clang::FrontendAction>, const llvm::Twine&, const std::vector<std::__cxx11::basic_string<char> >&, const llvm::Twine&, const FileContentMappings&)’:
/home/chivier/Projects/clang-tool/src/utils/utils.cc:32:16: error: ‘class clang::tooling::ToolInvocation’ has no member named ‘mapVirtualFile’
   32 |     invocation.mapVirtualFile(fileNameRef, code.toNullTerminatedStringRef(codeStorage));
      |                ^~~~~~~~~~~~~~
/home/chivier/Projects/clang-tool/src/utils/utils.cc:35:20: error: ‘class clang::tooling::ToolInvocation’ has no member named ‘mapVirtualFile’
   35 |         invocation.mapVirtualFile(filenameWithContent.first, filenameWithContent.second);
      |                    ^~~~~~~~~~~~~~
make[2]: *** [src/CMakeFiles/clang-tool.dir/build.make:102: src/CMakeFiles/clang-tool.dir/utils/utils.cc.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:94: src/CMakeFiles/clang-tool.dir/all] Error 2
make: *** [Makefile:84: all] Error 2

这里继续分析mapVirtualFile

调用 mapVirtualFile 的是一个 TollInnovation 类。这里存在一些借口不适配的问题。

成功记录

在网上搜索 ToolInnovation，在 github 上找到了一个性质类似的项目：

https://github.com/firolino/clang-tool.git

此项目可以很好的完善我目前的研究，基于 clang-tool 的 CMakeLists 我写出了如下的文件：

project(LLVM_test)
cmake_minimum_required(VERSION 2.8)
find_package(LLVM REQUIRED)
find_package(Clang REQUIRED)

set(CMAKE_CXX_FLAGS "-Wall -g3 -O0 -fno-rtti ${LLVM_COMPILE_FLAGS}")

include_directories(${LLVM_INCLUDE_DIRS})
include_directories(${CLANG_INCLUDE_DIRS})

set(LLVM_LINK_COMPONENTS
  FrontendOpenMP
  Support
  )

add_executable(tool-template
  ToolTemplate.cpp
  )

target_link_libraries(tool-template
  PRIVATE
  clangAST
  clangASTMatchers
  clangBasic
  clangFrontend
  clangTooling
  clangToolingRefactoring
  )

clang tooling

对于 clang tooling 的做法，需要有如下考量

调研期间发现了一个 LLVM 更好用一些的文档网站：

https://docs.hdoc.io/hdoc/llvm-project/

优势在于提供了 doxygen 中不便于搜索的麻烦，提供了搜索接口

https://docs.hdoc.io/hdoc/llvm-project/search.html

LLVM 框架的整体架构是

Frontend -> Optimizer -> Backend Frontend = Lexer + Parser Optimizer = Passed Backend = MD Optimizer + CodeGen

分析出的 AST 树使我们前端分析的目标，但是 AST 的遍历具有一定的麻烦，我们不太可能根据 LLVM 每一代 API 的接口去设计我们的程序，这个实话需要借助 LLVM 一个相对独立的子项目，就是 clang tooling，作为 LLVM18 大会上的报告，Clang tooling 以及其代表组件 LibClang 在 "few years" 将维持稳定版本。

LibClang 的作用更想一个“光标”，用于遍历和访问每一个 AST 的 Translate Unit。

作为一个方便的接口，测试的时候可以先使用 Python 去开发和测试，便于调试。

from clang.cindex import *

def is_function_call(funcdecl, c):
    """ Determine where a call-expression cursor refers to a particular function declaration
    """
    defn = c.get_definition()
    return (defn is not None) and (defn == funcdecl)

def fully_qualified(c):
    """ Retrieve a fully qualified function name (with namespaces)
    """
    res = c.spelling
    c = c.semantic_parent
    while c.kind != CursorKind.TRANSLATION_UNIT:
        res = c.spelling + '::' + res
        c = c.semantic_parent
    return res

def find_funcs_and_calls(tu):
    """ Retrieve lists of function declarations and call expressions in a translation unit
    """
    filename = tu.cursor.spelling
    calls = []
    funcs = []
    for c in tu.cursor.walk_preorder():
        if c.location.file is None:
            pass
        elif c.location.file.name != filename:
            pass
        elif c.kind == CursorKind.CALL_EXPR:
            calls.append(c)
        elif c.kind == CursorKind.FUNCTION_DECL:
            funcs.append(c)
    return funcs, calls

idx = Index.create()
args =  '-x c++ --std=c++11'.split()
tu = idx.parse('tmp.cpp', args=args)
funcs, calls = find_funcs_and_calls(tu)
for f in funcs:
    print(fully_qualified(f), f.location)
    for c in calls:
        if is_function_call(f, c):
            print('-', c.location)
    print()

OP2-Clang

OP2 clang 项目是基于 LLVM 项目开发的。基本思想是为了适应更多更新的硬件设备，我们不应该去专门花时间在底层设计上，这些部分理应由编译器后端进行处理。更好的构建起前端到这里的框架才是一个 DSL 应该做的事情。非结构化网格是一个代表性的问题。

OP2 Clang 的主要工作是借用 Clang 将中间层 API 转移，用户不必直接去写 OP2 Library 中的 API 代码，而是用简单的逻辑说明代码的逻辑。Clang 再利用前端去实现 OP2 中的并行化。

Youtube 的视频讲解了论文的思路 https://www.youtube.com/watch?v=Ie2WjoUEnKw

设计思想重要部分是： handle significant structural transformations

其实这个工作的价值并不在于 Clang，而在于 OP2 库的并行化的易用性，那么这项工作是否真的那么容易复现呢？

答案是肯定的，并且这里将给出一个更加简单的复现思路，如果读了之前的工作文档，那么会发现，如果使用 libclang Python API ，那么复现此工作将不再复杂，知识简单的：“模式匹配” + “代码替换”

其代码框架如下：

Op2ModeScan -> [generator]

generator 包含如下部分： common, cuda, openmp, sequntial, vectorization

以 openmp 举例，我在下面的代码标出注释


namespace {
using namespace clang::ast_matchers;
const auto parLoopSkeletonCompStmtMatcher =
    compoundStmt(hasParent(functionDecl(hasName("op_par_loop_skeleton"))));
} // namespace

namespace OP2 {
using namespace clang::ast_matchers;
using namespace clang;
//___________________________________MATCHERS__________________________________
// 下面用LLVM接口对AST的节点进行判定

const StatementMatcher OMPKernelHandler::locRedVarMatcher =
    declStmt(containsDeclaration(0, varDecl(hasName("arg0_l"))),
             hasParent(parLoopSkeletonCompStmtMatcher))
        .bind("local_reduction_variable");

const StatementMatcher OMPKernelHandler::locRedToArgMatcher =
    binaryOperator(
        hasOperatorName("="),
        hasRHS(ignoringImpCasts(declRefExpr(to(varDecl(hasName("arg0_l")))))),
        hasParent(parLoopSkeletonCompStmtMatcher))
        .bind("loc_red_to_arg_assignment");

const StatementMatcher OMPKernelHandler::ompParForMatcher =
    ompParallelForDirective().bind(
        "ompParForDir"); // FIXME check if it is in the main file.

//_________________________________CONSTRUCTORS________________________________
OMPKernelHandler::OMPKernelHandler(
    std::map<std::string, clang::tooling::Replacements> *Replace,
    const ParLoop &loop)
    : Replace(Replace), loop(loop) {}

//________________________________GLOBAL_HANDLER_______________________________
void OMPKernelHandler::run(const MatchFinder::MatchResult &Result) {
  if (!lineReplHandler<DeclStmt, 1>(
          Result, Replace, "local_reduction_variable",
          std::bind(&OMPKernelHandler::handleRedLocalVarDecl, this)))
    return;
  if (!HANDLER(CallExpr, 2, "func_call", OMPKernelHandler::handleFuncCall))
    return; // if successfully handled return
  if (!lineReplHandler<BinaryOperator, 7>(
          Result, Replace, "loc_red_to_arg_assignment",
          std::bind(&OMPKernelHandler::handlelocRedToArgAssignment, this)))
    return; // if successfully handled return
  if (!HANDLER(OMPParallelForDirective, 0, "ompParForDir",
               OMPKernelHandler::handleOMPParLoop)) {
    return;
  }
}
//___________________________________HANDLERS__________________________________

std::string OMPKernelHandler::handleFuncCall() {
  std::string funcCall = "";
  llvm::raw_string_ostream ss(funcCall);
  ss << loop.getUserFuncInfo().funcName << "(";
  for (size_t i = 0; i < loop.getNumArgs(); ++i) {
    if (!loop.getArg(i).isReduction()) {
      if (loop.getArg(i).isDirect()) {
        ss << loop.getArg(i).getArgCall(i, "n");
      } else {

        ss << loop.getArg(i).getArgCall(
            loop.dat2argIdxs[loop.dataIdxs[i]],
            ("map" + std::to_string(loop.mapIdxs[i]) + "idx"));
      }
      ss << ",";
    } else {
      ss << "&arg" << i << "_l,";
    }
  }
  ss.str();
  return funcCall.substr(0, funcCall.length() - 1) + ");";
}

std::string OMPKernelHandler::handleRedLocalVarDecl() {
  std::string s;
  llvm::raw_string_ostream os(s);
  for (size_t ind = 0; ind < loop.getNumArgs(); ++ind) {
    const OPArg &arg = loop.getArg(ind);
    if (arg.isReduction()) {
      os << arg.type << " arg" << ind << "_l = *(" + arg.type + " *)arg" << ind
         << ".data;\n";
    }
  }
  return os.str();
}

std::string OMPKernelHandler::handlelocRedToArgAssignment() {
  std::string s;
  llvm::raw_string_ostream os(s);
  for (size_t ind = 0; ind < loop.getNumArgs(); ++ind) {
    const OPArg &arg = loop.getArg(ind);
    if (arg.isReduction()) {
      os << "*((" + arg.type + " *)arg" << ind << ".data) = arg" << ind
         << "_l;\n";
    }
  }
  return os.str();
}

std::string OMPKernelHandler::handleOMPParLoop() {
  std::string plusReds, minReds, maxReds;
  llvm::raw_string_ostream os(plusReds);
  llvm::raw_string_ostream osMin(minReds);
  llvm::raw_string_ostream osMax(maxReds);
  // 计算可用资源
  for (size_t ind = 0; ind < loop.getNumArgs(); ++ind) {
    const OPArg &arg = loop.getArg(ind);
    if (arg.isReduction()) {
      switch (arg.accs) {
      case OP2::OP_INC:
        os << "arg" << ind << "_l, ";
        break;
      case OP2::OP_MAX:
        osMax << "arg" << ind << "_l, ";
        break;
      case OP2::OP_MIN:
        osMin << "arg" << ind << "_l, ";
        break;
      default:
        // error if this is a reduction it must be one of OP_MIN, OP_MAX or
        // OP_INC
        assert(!arg.isReduction() ||
               (arg.accs == OP2::OP_INC || arg.accs == OP2::OP_MAX ||
                arg.accs == OP2::OP_MIN));
      }
    }
  }
  // 生成 omp 宏语句
  if (os.str().length() > 0) {
    plusReds =
        " reduction(+:" + plusReds.substr(0, plusReds.length() - 2) + ")";
  }
  if (osMin.str().length() > 0) {
    minReds = " reduction(min:" + minReds.substr(0, minReds.length() - 2) + ")";
  }
  if (osMax.str().length() > 0) {
    maxReds = " reduction(max:" + maxReds.substr(0, maxReds.length() - 2) + ")";
  }
  return "omp parallel for " + plusReds + " " + minReds + " " + maxReds;
}

} // namespace OP2

这项工作本质上难度不大，对于之后工作的意义在于：

网格划分部分的代码其实可以根据群论提供的对称性思想进行划分和生成。我们只需要简单描述网格方法，之后就可以生成那一部分的代码，并且自动将 OpenMP 的部分自动植入。

正在测试的例子：

生成一个3维网格，每个格子里有10个点，之后会自由扩散。目前编码方法为自然编码，按长宽高依次顺次编号。

总结

本周工作： 1. 总结 OP2 Clang，学习项目框架，自己基本复现。 2. 总结 LLVM Clang Tooling 工作框架，于 github: Chivier/still 3. 总结 LLVM Python Clang API，分析 Translation Unit 的行为，编写函数调用 demo 见 github: Chivier/still 4. 学习文档工具 hdoc 5. 继续完善 3D 绘图库，目前可以完成自动生成任意亏格小于2的管状模型 6. 编译 LLVM 12，13，14 的文档，对比 LLVM Clang 接口 7. Sourcetrail 分析 Python Clang API

之后工作计划：

完善算例，将该算例发展成为网格Benchmark
基于改 Benchmark 测试自动 OpenMP 并行化方案的可行性
自动优化工具测试 SPH 原版代码

Research

#LLVM #DSL

2109-Source to Source LLVM 调研

http://blog.chivier.site/2021-10-26/2022/2109-Source-to-Source-LLVM-调研/

Author

Chivier Humber

Posted on

October 26, 2021

Licensed under

2201-布谷计划 Previous

New Laptop Next