{"id":3019,"date":"2013-09-08T04:16:46","date_gmt":"2013-09-07T19:16:46","guid":{"rendered":"http:\/\/peta.okechan.net\/blog\/?p=3019"},"modified":"2013-09-08T04:16:46","modified_gmt":"2013-09-07T19:16:46","slug":"7-3-llvm%e3%81%ab%e3%81%8a%e3%81%91%e3%82%8b%e3%83%a1%e3%83%a2%e3%83%aa","status":"publish","type":"post","link":"https:\/\/peta.okechan.net\/blog\/archives\/3019","title":{"rendered":"7.3. LLVM\u306b\u304a\u3051\u308b\u30e1\u30e2\u30ea"},"content":{"rendered":"

LLVM\u306b\u3088\u308b\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u8a00\u8a9e\u306e\u5b9f\u88c5\u30c1\u30e5\u30fc\u30c8\u30ea\u30a2\u30eb\u65e5\u672c\u8a9e\u8a33<\/a>
\n\u7b2c7\u7ae0 \u4e07\u83ef\u93e1: \u8a00\u8a9e\u306e\u62e1\u5f35: \u5909\u66f4\u53ef\u80fd\u306a\u5909\u6570\uff08Mutable Variables\uff09
\n\u7b2c3\u7bc0 LLVM\u306b\u304a\u3051\u308b\u30e1\u30e2\u30ea<\/a><\/p>\n

LLVM\u306f\u5168\u3066\u306e\u30ec\u30b8\u30b9\u30bf\u3092SSA\u5f62\u5f0f\u306b\u3059\u308b\u3053\u3068\u3092\u8981\u6c42\u3059\u308b\u304c\u3001\u30e1\u30e2\u30ea\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306b\u95a2\u3057\u3066\u306fSSA\u5f62\u5f0f\u3067\u3042\u308b\u3053\u3068\u3092\u8981\u6c42\u3057\u306a\u3044\uff08\u3082\u3057\u304f\u306f\u8a31\u53ef\u3057\u3057\u306a\u3044\uff09\u3068\u3044\u3046\u70b9\u304c\u30df\u30bd\u3067\u3042\u308b\u3002
\n\u524d\u7bc0\u306e\u4f8b\u306b\u304a\u3044\u3066\u306f\u3001G\u3084H\u304b\u3089\u306e\u8aad\u307f\u8fbc\u307f\u306f\u3001G\u3084H\u306b\u5bfe\u3059\u308b\u76f4\u63a5\u7684\u306a\u30a2\u30af\u30bb\u30b9\u3067\u3042\u308b\u3002\uff08G\u3084H\u306f\u3001\u30ea\u30cd\u30fc\u30e0\u3055\u308c\u305f\u308a\u30d0\u30fc\u30b8\u30e7\u30f3\u4ed8\u3051\u3055\u308c\u3066\u3044\u306a\u3044\u3002\uff09
\n\u3053\u308c\u306f\u3001\u30e1\u30e2\u30ea\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u3092\u30d0\u30fc\u30b8\u30e7\u30f3\u4ed8\u3051\u3057\u3088\u3046\u3068\u3059\u308b\u4ed6\u306e\u30b3\u30f3\u30d1\u30a4\u30e9\u30b7\u30b9\u30c6\u30e0\u3068\u306f\u9055\u3063\u3066\u3044\u308b\u3002
\nLLVM\u3067\u306f\u3001\u30e1\u30e2\u30ea\u306e\u30c7\u30fc\u30bf\u30d5\u30ed\u30fc\u89e3\u6790\u3092LLVM IR\u306b\u30a8\u30f3\u30b3\u30fc\u30c9\u305b\u305a\u306b\u3001\u5fc5\u8981\u306b\u5fdc\u3058\u3066\u8a08\u7b97\u3055\u308c\u308b\u89e3\u6790\u30d1\u30b9\uff08Analysis Passes\uff09\u306b\u3088\u3063\u3066\u51e6\u7406\u3059\u308b\u3002<\/p>\n

\u3053\u308c\u3092\u8e0f\u307e\u3048\u3066\u3001\u95a2\u6570\u306e\u4e2d\u306b\u304a\u3051\u308b\u5909\u66f4\u53ef\u80fd\u306a\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306e\u305f\u3081\u306e\u30b9\u30bf\u30c3\u30af\u5909\u6570\uff08\u30b9\u30bf\u30c3\u30af\u4e0a\u306b\u3042\u308b\u306e\u3067\u3001\u3064\u307e\u308a\u30e1\u30e2\u30ea\u4e0a\u306b\u3042\u308b\uff09\u3092\u4f5c\u6210\u3057\u305f\u3044\u3001\u3068\u3044\u3046\u306e\u304c\u3088\u308a\u9ad8\u3044\u30ec\u30d9\u30eb\u306e\u30a2\u30a4\u30c7\u30a2\u3067\u3042\u308b\u3002
\n\u3053\u306e\u65b9\u6cd5\u306e\u5229\u70b9\u3092\u6d3b\u304b\u3059\u305f\u3081\u306b\u3001LLVM\u306f\u3069\u3046\u3084\u3063\u3066\u30b9\u30bf\u30c3\u30af\u5909\u6570\u3092\u8868\u73fe\u3059\u308b\u306e\u304b\u3068\u3044\u3046\u3053\u3068\u306b\u3064\u3044\u3066\u8003\u3048\u308b\u5fc5\u8981\u304c\u3042\u308b\u3002<\/p>\n

LLVM\u3067\u306f\u3001\u5168\u3066\u306e\u30e1\u30e2\u30ea\u30a2\u30af\u30bb\u30b9\u306fload\/store\u547d\u4ee4\u306b\u3088\u3063\u3066\u660e\u78ba\u306b\u884c\u308f\u308c\u3001\u30a2\u30c9\u30ec\u30b9\u3092\u5f97\u308b\u547d\u4ee4\uff08”address-of” operator\uff09\u3092\u6301\u305f\u306a\u3044\uff08\u307e\u305f\u306f\u5fc5\u8981\u3068\u3057\u306a\u3044\uff09\u3088\u3046\u6ce8\u610f\u6df1\u304f\u30c7\u30b6\u30a4\u30f3\u3055\u308c\u3066\u3044\u308b\u3002
\n\u30b0\u30ed\u30fc\u30d0\u30eb\u5909\u6570@G\/@H\u306f\u3001”i32″\u3068\u3057\u3066\u5b9a\u7fa9\u3055\u308c\u3066\u3044\u308b\u304c\u3001\u5b9f\u969b\u306f”i32*”\u3067\u3042\u308b\u4e8b\u306b\u6ce8\u610f\u3002
\n\u3064\u307e\u308a\u3001\uff20G\u306f\u30b0\u30ed\u30fc\u30d0\u30eb\u306e\u30c7\u30fc\u30bf\u9818\u57df\u306bi32\u7528\u306e\u9818\u57df\u3092\u5b9a\u7fa9\u3059\u308b\u304c\u3001\u305d\u306e\u540d\u524d\u306f\u5b9f\u969b\u306b\u306f\u305d\u306e\u9818\u57df\u306e\u30a2\u30c9\u30ec\u30b9\u3092\u53c2\u7167\u3059\u308b\u3068\u3044\u3046\u4e8b\u3067\u3042\u308b\u3002
\n\u30b9\u30bf\u30c3\u30af\u5909\u6570\u3082\u3001\u30b0\u30ed\u30fc\u30d0\u30eb\u5909\u6570\u5b9a\u7fa9\u3068\u3057\u3066\u5ba3\u8a00\u3055\u308c\u308b\u306e\u3067\u306f\u306a\u304f\u3001LLVM\u306ealloca\u547d\u4ee4\u3067\u5ba3\u8a00\u3055\u308c\u308b\u70b9\u3092\u9664\u3044\u3066\uff08@G\/@H\u3068\uff09\u540c\u3058\u3088\u3046\u306b\u52d5\u4f5c\u3059\u308b\u3002<\/p>\n

define i32 @example() {\r\nentry:\r\n  %X = alloca i32           ; %X \u306f i32* \u578b\u3002\r\n  ...\r\n  %tmp = load i32* %X       ; \u30b9\u30bf\u30c3\u30af\u304b\u3089\u30b9\u30bf\u30c3\u30af\u5024 %X \u3092\u8aad\u307f\u8fbc\u3080\u3002\r\n  %tmp2 = add i32 %tmp, 1   ; \u30a4\u30f3\u30af\u30ea\u30e1\u30f3\u30c8\u3002\r\n  store i32 %tmp2, i32* %X  ; %tmp2 \u304b\u3089 %X \u3078\u66f8\u304d\u623b\u3059\u3002\r\n  ...<\/pre>\n
\u3053\u306e\u30b3\u30fc\u30c9\u306f\u3001LLVM\u306b\u304a\u3051\u308b\u30b9\u30bf\u30c3\u30af\u5909\u6570\u306e\u5ba3\u8a00\u3068\u64cd\u4f5c\u306e\u65b9\u6cd5\u3092\u4f8b\u793a\u3057\u3066\u3044\u308b\u3002
\nalloca\u547d\u4ee4\u306b\u3088\u3063\u3066\u30b9\u30bf\u30c3\u30af\u30e1\u30e2\u30ea\u3092\u5272\u308a\u5f53\u3066\u308b\u306e\u306f\u3001LLVM\u306b\u304a\u3044\u3066\u306f\u6975\u3081\u3066\u666e\u901a\u306e\u4e8b\u3067\u3042\u308b\u3002\uff08\u30b9\u30bf\u30c3\u30af\u30b9\u30ed\u30c3\u30c8\u306e\u30a2\u30c9\u30ec\u30b9\u3092\u95a2\u6570\u306b\u6e21\u3057\u305f\u308a\u3001\u305d\u308c\u3092\u4ed6\u306e\u5909\u6570\u306b\u683c\u7d0d\u3057\u305f\u308a\u306a\u3069\u3082\u53ef\u80fd\u3067\u3042\u308b\u3002\uff09
\n\u524d\u7bc0\u306e\u4f8b\u3060\u3068\u3001phi\u30ce\u30fc\u30c9\u306e\u4f7f\u7528\u3092\u907f\u3051\u308b\u305f\u3081\u306balloca\u3092\u4f7f\u7528\u3059\u308b\u3088\u3046\u66f8\u304d\u63db\u3048\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002<\/p>\n
@G = weak global i32 0   ; type of @G is i32*\r\n@H = weak global i32 0   ; type of @H is i32*\r\n\r\ndefine i32 @test(i1 %Condition) {\r\nentry:\r\n  %X = alloca i32           ; type of %X is i32*.\r\n  br i1 %Condition, label %cond_true, label %cond_false\r\n\r\ncond_true:\r\n  %X.0 = load i32* @G\r\n  store i32 %X.0, i32* %X   ; Update X\r\n  br label %cond_next\r\n\r\ncond_false:\r\n  %X.1 = load i32* @H\r\n  store i32 %X.1, i32* %X   ; Update X\r\n  br label %cond_next\r\n\r\ncond_next:\r\n  %X.2 = load i32* %X       ; Read X\r\n  ret i32 %X.2\r\n}<\/pre>\n
\u3053\u308c\u306b\u3088\u3063\u3066\u3001\u6211\u3005\u306f\u4efb\u610f\u306e\u5909\u66f4\u53ef\u80fd\u306a\u5909\u6570\u3092\u3001phi\u30ce\u30fc\u30c9\u306e\u751f\u6210\u3092\u307e\u3063\u305f\u304f\u5fc5\u8981\u3068\u305b\u305a\u306b\u3001\u51e6\u7406\u3059\u308b\u65b9\u6cd5\u3092\u767a\u898b\u3057\u305f\u4e8b\u306b\u306a\u308b\u3002<\/p>\n
    \n
  1. \u5909\u66f4\u53ef\u80fd\u306a\u5909\u6570\u306f\u3001\u30b9\u30bf\u30c3\u30af\u3078\u306e\u5272\u308a\u5f53\u3066\uff08allocation\uff09\u3068\u306a\u308b\u3002<\/li>\n
  2. \u5909\u6570\u304b\u3089\u306e\u8aad\u307f\u8fbc\u307f\u306f\u3001\u30b9\u30bf\u30c3\u30af\u304b\u3089\u306e\u30ed\u30fc\u30c9\uff08load\uff09\u3068\u306a\u308b\u3002<\/li>\n
  3. \u5909\u6570\u306e\u66f8\u304d\u63db\u3048\u306f\u3001\u30b9\u30bf\u30c3\u30af\u3078\u306e\u30b9\u30c8\u30a2\uff08store\uff09\u3068\u306a\u308b\u3002<\/li>\n
  4. \u5909\u6570\u306e\u30a2\u30c9\u30ec\u30b9\u3092\u5f97\u308b\u306b\u306f\u3001\u30b9\u30bf\u30c3\u30af\u306e\u30a2\u30c9\u30ec\u30b9\u3092\u76f4\u63a5\u7528\u3044\u308b\u3002<\/li>\n<\/ol>\n
    \u3053\u306e\u3084\u308a\u65b9\u306f\u3001\u6211\u3005\u306e\u76ee\u4e0b\u306e\u554f\u984c\u3092\u89e3\u6c7a\u3059\u308b\u4e00\u65b9\u3001\u3042\u3089\u305f\u306a\u554f\u984c\u3092\u8d77\u3053\u3059\u3002
    \n\u304b\u306a\u308a\u30b7\u30f3\u30d7\u30eb\u3067\u57fa\u672c\u7684\u306a\u51e6\u7406\u3092\u884c\u3046\u306b\u3082\u3001\u30b9\u30bf\u30c3\u30af\u3078\u306e\u30a2\u30af\u30bb\u30b9\u91cf\u306e\u5897\u5927\u3092\u62db\u304d\u305d\u3046\u3060\u3068\u3044\u3046\u3001\u6027\u80fd\u4e0a\u91cd\u5927\u306a\u554f\u984c\u3067\u3042\u308b\u3002
    \n\u5e78\u3044\u3001LLVM\u306e\u30aa\u30d7\u30c6\u30a3\u30de\u30a4\u30b6\u306f\u9ad8\u5ea6\u306b\u30c1\u30e5\u30fc\u30f3\u3055\u308c\u305f\u6700\u9069\u5316\u30d1\u30b9\u3092\u6301\u3064\u3002
    \n\u305d\u306e\u540d\u3082”mem2reg”\u3067\u3001\u305d\u308c\u306f\u3053\u306e\u5834\u5408\u306e\u3088\u3046\u306aalloca\u3092SSA\u30ec\u30b8\u30b9\u30bf\u306b\u5909\u63db\u3057\u3001\u9069\u5207\u306bphi\u30ce\u30fc\u30c9\u3092\u633f\u5165\u3059\u308b\u3002
    \n\u4ee5\u4e0a\u306e\u4f8b\u3092\u3001\u3053\u306e\u30d1\u30b9\u306b\u901a\u3059\u3068\u3001\u4ee5\u4e0b\u306e\u3088\u3046\u306a\u7d50\u679c\u304c\u5f97\u3089\u308c\u308b\u3002<\/p>\n
    $ llvm-as < example.ll | opt -mem2reg | llvm-dis\u3053\u308c\r\n@G = weak global i32 0\r\n@H = weak global i32 0\r\n\r\ndefine i32 @test(i1 %Condition) {\r\nentry:\r\n  br i1 %Condition, label %cond_true, label %cond_false\r\n\r\ncond_true:\r\n  %X.0 = load i32* @G\r\n  br label %cond_next\r\n\r\ncond_false:\r\n  %X.1 = load i32* @H\r\n  br label %cond_next\r\n\r\ncond_next:\r\n  %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]\r\n  ret i32 %X.01\r\n}<\/pre>\n
    mem2reg\u30d1\u30b9\u306b\u306f\u3001SSA\u5f62\u5f0f\u306e\u69cb\u7bc9\u3068\u3001\u6a19\u6e96\u7684\u306a”\u7e70\u308a\u8fd4\u3057\u652f\u914d\u8fba\u5883\uff08iterated dominance frontier\uff09”\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u5b9f\u88c5\u3055\u308c\u3066\u3001\u307e\u305f\uff08\u3088\u304f\u3042\u308b\uff09\u60aa\u3044\u30b1\u30fc\u30b9\u3092\u30b9\u30d4\u30fc\u30c9\u30a2\u30c3\u30d7\u3059\u308b\u305f\u3081\u306e\u591a\u304f\u306e\u6700\u9069\u5316\u51e6\u7406\u3082\u6301\u3064\u3002
    \nmem2reg\u6700\u9069\u5316\u30d1\u30b9\u306f\u3001\u5909\u66f4\u53ef\u80fd\u306a\u5909\u6570\u3092\u6271\u3046\u305f\u3081\u306e\u7b54\u3048\u3067\u3042\u308a\u3001\u305d\u308c\u3092\u4f7f\u3046\u4e8b\u3092\u6211\u3005\u306f\u5f37\u304f\u63a8\u5968\u3059\u308b\u3002
    \nmem2reg\u306f\u3001\u3042\u308b\u7a2e\u306e\u72b6\u6cc1\u306b\u304a\u3044\u3066\u306e\u307f\u52d5\u4f5c\u3059\u308b\u70b9\u306b\u6ce8\u610f\u3002<\/p>\n
      \n
    1. mem2reg\u306f\u3001alloca\u99c6\u52d5\u3067\u3042\u308b\u3002
      \nalloca\u3092\u63a2\u3057\u3001\u305d\u308c\u304c\u51e6\u7406\u53ef\u80fd\u306a\u3089\u51e6\u7406\u3059\u308b\u3002
      \n\u30b0\u30ed\u30fc\u30d0\u30eb\u5909\u6570\u3084\u3001\u30d2\u30fc\u30d7\u306e\u5272\u308a\u5f53\u3066\uff08heap allocation\uff09\u306b\u5bfe\u3057\u3066\u306f\u52d5\u4f5c\u3057\u306a\u3044\u3002<\/li>\n
    2. mem2reg\u306f\u3001\u95a2\u6570\u306eentry\u30d6\u30ed\u30c3\u30af\u306e\u4e2d\u3067\u306e\u307falloca\u547d\u4ee4\u3092\u63a2\u3059\u3002
      \nentry\u30d6\u30ed\u30c3\u30af\u3067\u306falloca\u304c\u4e00\u5ea6\u3060\u3051\u5b9f\u884c\u3055\u308c\u308b\u3053\u3068\u304c\u4fdd\u8a3c\u3055\u308c\u308b\u306e\u3067\u3001\u89e3\u6790\u51e6\u7406\u3092\u30b7\u30f3\u30d7\u30eb\u306b\u51fa\u6765\u308b\u3002<\/li>\n
    3. mem2reg\u306f\u3001\u76f4\u63a5\u30ed\u30fc\u30c9\u3082\u3057\u304f\u306f\u30b9\u30c8\u30a2\u3055\u308c\u308balloca\u306e\u307f\u3092\u51e6\u7406\u3059\u308b\u3002
      \n\u3082\u3057\u95a2\u6570\u306b\u3001\u30b9\u30bf\u30c3\u30af\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306e\u30a2\u30c9\u30ec\u30b9\u304c\u6e21\u3055\u308c\u305f\u5834\u5408\u3001\u3082\u3057\u304f\u306f\u3001\u4f55\u304b\u7279\u6b8a\u306a\u30dd\u30a4\u30f3\u30bf\u6f14\u7b97\u306b\u95a2\u4fc2\u3059\u308b\u5834\u5408\u3001\u305d\u306ealloca\u3092\u51e6\u7406\u3057\u306a\u3044\u3002<\/li>\n
    4. mem2reg\u306f\u3001\uff08\u30dd\u30a4\u30f3\u30bf\u3084\u30b9\u30ab\u30e9\u3084\u30d9\u30af\u30bf\u306e\u3088\u3046\u306a\uff09\u7b2c\u4e00\u7d1a\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\uff08first class value\uff09\u3067\u3001\u914d\u5217\u306e\u5272\u308a\u5f53\u3066\u30b5\u30a4\u30ba\u304c1\uff08\u3082\u3057\u304f\u306f.ll\u30d5\u30a1\u30a4\u30eb\u4e0a\u3067\u30b5\u30a4\u30ba\u304c\u7701\u7565\u3055\u308c\u3066\u3044\u308b\u5834\u5408\uff09\u306ealloca\u306e\u307f\u3092\u5bfe\u8c61\u3068\u3059\u308b\u3002
      \nmem2reg\u306b\u306f\u3001\u69cb\u9020\u4f53\u3084\u914d\u5217\u3092\u30ec\u30b8\u30b9\u30bf\u306b\u5909\u63db\u3059\u308b\u80fd\u529b\u306f\u306a\u3044\u3002
      \n\u3061\u306a\u307f\u306b\u3001”scalarrepl”\u30d1\u30b9\u306f\u3088\u308a\u5f37\u529b\u3067\u3001\u69cb\u9020\u4f53\u3084\u5171\u7528\u4f53\u3084\u914d\u5217\u3092\u591a\u304f\u306e\u5834\u5408\u3067\u51e6\u7406\u53ef\u80fd\u3067\u3042\u308b\u3002<\/li>\n<\/ol>\n
      \u591a\u304f\u306e\u547d\u4ee4\u578b\u8a00\u8a9e\u306b\u304a\u3044\u3066\u3001\u4ee5\u4e0a\u306e\u9805\u76ee\u3092\u5168\u3066\u6e80\u305f\u3059\u306e\u306f\u7c21\u5358\u3067\u3042\u308b\u3002
      \n\u3053\u308c\u306b\u3064\u3044\u3066\u3001\u3053\u306e\u5f8c\u4e07\u83ef\u93e1\u3092\u4f7f\u3063\u3066\u89e3\u8aac\u3059\u308b\u3002
      \n\u3042\u306a\u305f\u304c\u3059\u308b\u3067\u3042\u308d\u3046\u6700\u5f8c\u306e\u8cea\u554f\u306f\u3001\u6b21\u306e\u3088\u3046\u306a\u3082\u306e\u3060\u308d\u3046\u3002
      \n“\u30d5\u30ed\u30f3\u30c8\u30a8\u30f3\u30c9\u306e\u5b9f\u88c5\u306b\u304a\u3044\u3066\u3001\u3053\u306e\u3088\u304f\u89e3\u3089\u306a\u3044\u3084\u308a\u65b9\u306b\u3064\u3044\u3066\u5fc3\u914d\u3059\u3079\u304d\u3067\u3057\u3087\u3046\u304b\u3002mem2reg\u6700\u9069\u5316\u30d1\u30b9\u3092\u4f7f\u7528\u305b\u305a\u306b\u3001\u5358\u306bSSA\u3092\u76f4\u63a5\u69cb\u7bc9\u3059\u308c\u3070\u3044\u3044\u3093\u3058\u3083\u306a\u3044\u3067\u3057\u3087\u3046\u304b\uff1f”
      \n\u4e00\u53e3\u306b\u8a00\u3048\u3070\u3001\u975e\u5e38\u306b\u5341\u5206\u306a\u7406\u7531\u304c\u7121\u3044\u9650\u308a\u3001SSA\u5f62\u5f0f\u306e\u69cb\u7bc9\u306e\u305f\u3081\u306b\u3053\u306e\u6280\u6cd5\u3092\u4f7f\u7528\u3059\u308b\u3088\u3046\u5f37\u304f\u63a8\u5968\u3059\u308b\u3002
      \n\u8a33\u6ce8: \u3053\u306e\u6280\u6cd5 = \u3068\u308a\u3042\u3048\u305a\u5909\u6570\u3092alloca\u3067\u5ba3\u8a00\u3059\u308b\u3088\u3046\u306b\u3057\u3001phi\u30ce\u30fc\u30c9\u3092\u751f\u6210\u3057\u306a\u3044\u3067\u304a\u3044\u3066\u3001\u5f8c\u306fmem2reg\u306b\u4efb\u305b\u308b\u65b9\u6cd5<\/em><\/p>\n
      \u3053\u306e\u6280\u6cd5\u3092\u4f7f\u3046\u4e8b\u306f\u3001<\/p>\n