Glasgow Haskell 编译器和 LLVM

什么是 GHC 和 Haskell

现有管道

为什么使用 LLVM 后端？

• 卸载工作：构建一个高性能编译器后端是一项巨大的工作，例如 LLVM 大约在 10 年前开始。展望未来，LLVM 后端应该比 C 后端或 NCG 更容易维护和扩展。它还将受益于 LLVM 的任何未来改进。
• 优化过程：GHC 在生成快速 Haskell 程序方面做得很好。但是，它当前没有实现许多低级优化（尤其是需要机器特定知识的优化）。使用 LLVM 应该可以免费获得其中大部分优化。
• LLVM 框架：LLVM 最吸引人的特性可能是它从一开始就被设计为一个编译器框架。对于像 GHC 开发人员这样的研究人员来说，这是一个巨大的优势，使 LLVM 成为一个非常有趣的游乐场。例如，在 LLVM 后端公开发布后的几天内，一位开发人员 Don Stewart 写了一个遗传算法，用于找到用于各种 Haskell 程序的最佳 LLVM 优化管道（您可以在他的博客文章中找到关于此的更多信息 这里）。

展示速度

• 如果 n 是偶数，下一个数字是 n/2
• 如果 n 是奇数，下一个数字是 3n + 1
• 如果 n 是 1，停止。

#include <stdio.h>

int main(int argc, char **argv) {
   int longest = 0, terms = 0, this_terms = 1, i;
   unsigned long j;

   for (i = 1; i < 1000000; i++) {
      j = i;
      this_terms = 1;

      while (j != 1) {
         this_terms++;
         j = j % 2 == 0 ? j / 2 : 3 * j + 1;
      }

      if (this_terms > terms) {
         terms = this_terms;
         longest = i;
      }
   }
   printf("longest: %d (%d)\n", longest, terms);
   return 0;
}

--------

import Data.Word

collatzLen :: Int -> Word32 -> Int
collatzLen c 1 = c
collatzLen c n | n `mod` 2 == 0 = collatzLen (c+1) $ n `div` 2
               | otherwise      = collatzLen (c+1) $ 3*n+1

pmax x n = x `max` (collatzLen 1 n, n)

main = print . solve $ 1000000
    where solve xs = foldl pmax (1,1) [2..xs-1]

• GHC-6.13 (NCG)：2.876 秒
• GHC-6.13 (C)：0.576 秒
• GHC-6.13 (LLVM)：0.516 秒
• Clang-1.1：0.526 秒
• GCC-4.4.3：0.335 秒

import Control.Parallel
import Data.Word

collatzLen :: Int -> Word32 -> Int
collatzLen c 1 = c
collatzLen c n | n `mod` 2 == 0 = collatzLen (c+1) $ n `div` 2
               | otherwise      = collatzLen (c+1) $ 3*n+1

pmax x n = x `max` (collatzLen 1 n, n)
main = print soln
   where
      solve xs = foldl pmax (1,1) xs
      s1 = solve [2..500000]
      s2 = solve [500001..999999]
      soln = s2 `par` (s1 `pseq` max s1 s2)

• GHC-6.13（并行，LLVM）: 0.312

• GHC (NCG) 29.499
• GHC (C) 29.043
• GHC (LLVM) 20.774

后端概述

新的调用约定

后端评估

后端问题

LLVM 的成功？

> [Chris Lattner]: Talking about what you think is good and what you think should be improved in LLVM would also be great. :)

未来