544 eff.c 1761 優化設計文檔

1:性能分析

1.1性能對比

oneapi 與hygonGcc性能對比發現，544課題中的eff.c 1761循環處，oneapi 進行了循環向量化, gcc使用標量，循環源碼前加 #pragma clang loop vectorize(disable) 找出oneapi在該循環處關閉和開啟loop vect 的性能差距，在15%左右。

? mme34.0.svg(圖中的svml_log4_mask)

1.2源代碼

1761           for (k = 0; k < lpears[i] + upears[i]; k++) {
1762
1763             if (pearlist[i] == NULL) {
1764                fprintf(nabout,
1765                        "NULL pair list entry in egb loop 1, taskid = %d\n",
1766                        mytaskid);
1767                fflush(nabout);
1768             }
1769             j = pearlist[i][k];
1770
1771             xij = xi - x[dim * j];
1772             yij = yi - x[dim * j + 1];
1773             zij = zi - x[dim * j + 2];
1774             r2 = xij * xij + yij * yij + zij * zij;
1775
1776             if (dim == 4) {                     // delete
1777                wij = wi - x[dim * j + 3];
1778                r2 += wij * wij;
1779             }
1780
1781             if (r2 > rgbmaxpsmax2)      //  %hir.cmp.4310 ule
1782                continue;
1783             dij1i = 1.0 / sqrt(r2);
1784             dij = r2 * dij1i;
1785             sj = fs[j] * (rborn[j] - BOFFSET);   //   select fast
1786             sj2 = sj * sj;
1787
1788             /*
1789              * ---following are from the Appendix of Schaefer and Froemmel,
1790              * JMB 216:1045-1066, 1990;  Taylor series expansion for d>>s
1791              * is by Andreas Svrcek-Seiler; smooth rgbmax idea is from
1792              * Andreas Svrcek-Seiler and Alexey Onufriev.
1793              */
1794
1795             if (dij > rgbmax + sj)      // rgbmax = 20;   %hir.cmp.4333 ule
1796                continue;
1797
1798             if ((dij > rgbmax - sj)) {      //    %hir.cmp.4349  ogt
1799                uij = 1. / (dij - sj);
1800                sumi -= 0.125 * dij1i * (1.0 + 2.0 * dij * uij +
1801                                         rgbmax2i * (r2 -
1802                                                     4.0 * rgbmax *
1803                                                     dij - sj2) +
1804                                         2.0 * log((dij - sj) * rgbmax1i));
1805
1806             } else if (dij > 4.0 * sj) {
1807                dij2i = dij1i * dij1i;
1808                tmpsd = sj2 * dij2i;
1809                dumbo =
1810                    TA + tmpsd * (TB +
1811                                  tmpsd * (TC +
1812                                           tmpsd * (TD + tmpsd * TDD)));
1813                sumi -= sj * tmpsd * dij2i * dumbo;
1814
1815             } else if (dij > ri + sj) {
1816                sumi -= 0.5 * (sj / (r2 - sj2) +
1817                               0.5 * dij1i * log((dij - sj) / (dij + sj)));
1818
1819             } else if (dij > fabs(ri - sj)) {
1820                theta = 0.5 * ri1i * dij1i * (r2 + ri * ri - sj2);
1821                uij = 1. / (dij + sj);
1822                sumi -= 0.25 * (ri1i * (2. - theta) - uij +
1823                                dij1i * log(ri * uij));
1824
1825             } else if (ri < sj) {
1826                sumi -= 0.5 * (sj / (r2 - sj2) + 2. * ri1i +
1827                               0.5 * dij1i * log((sj - dij) / (sj + dij)));
1828
1829             }
1830
1831          }

2 向量化遇到的問題

2.1 if printf

               if (pearlist[i] == NULL) {
1764                fprintf(nabout,
1765                        "NULL pair list entry in egb loop 1, taskid = %d\n",
1766                        mytaskid);
1767                fflush(nabout);
1768             }j = pearlist[i][k];

問題：分析不出內存關系，無法ifcvt。引入了控制流，否則control flow in loop。

eff.c:2072:16: missed: statement clobbers memory: fprintf (nabout.934_2047, "NULL pair list entry in egb loop 1, taskid = %d\n", 0);

解決辦法：循環無關的判斷，若 pearlist[i] == NULL 則求j = pearlist[i][k]為非法，按照邏輯在if判斷里面插入abort()（AOCC 插入了），符合邏輯同時 loop unswitch 可以將其提到循環外

2.2 ifcvt pass?

ifcvt pass 是loop vect pass 的必須經過的前置pass, 二者綁定，中間一般不能插入其他pass , 目的為了對if else 分支做conversion , 將分支跳轉轉化為條件選擇，以便于做 loop vect.

對于if else 的結構，ifcvt pass可以將其轉化為由原來多個控制流和bb塊的形式，消除控制流合并到到同一個bb塊，通過條件運算符？或者 mask_load的方式，使其滿足loop vect? pass 的 loop form analysis。最內層的loop只能由兩個bb塊組成的要求，進而進行下一步的loop vect。

ifcvt 消除if中的control flow。

/* Predicate each write to memory in LOOP.
2401
2402    This function transforms control flow constructs containing memory
2403    writes of the form:
2404
2405    | for (i = 0; i < N; i++)
2406    |   if (cond)
2407    |     A[i] = expr;
2408
2409    into the following form that does not contain control flow:
2410
2411    | for (i = 0; i < N; i++)
2412    |   A[i] = cond ? expr : A[i];

2.3 dim =3 常量傳播

1776             if (dim == 4) {
1777                wij = wi - x[dim * j + 3];
1778                r2 += wij * wij;
1779             }

問題：wij的計算會向量化遇到問題。

解決辦法：由于dim 是靜態全局變量，嘗試過inline 做常量傳播，發現并未能實現。調整loop unswitch 參數--param=max-unswitch-insns=150，將其提到循環外面。

2.4? ?phi 節點的參數超過限制

問題：sumi 的結果的phi節點參數過多，無法進行ifcvt

BB 90 has complicated PHI with more than 4 args.

解決：aggressive_if_conv = true; 讓ifcvt 做激進的優化，不受phi節點參數個數限制。

3300   /* Apply more aggressive if-conversion when loop or its outer loop were
3301      marked with simd pragma.  When that's the case, we try to if-convert
3302      loop containing PHIs with more than MAX_PHI_ARG_NUM arguments.  */
3303  // aggressive_if_conv = loop->force_vectorize;
3304   aggressive_if_conv = true;
3305   if (!aggressive_if_conv)
3306     {
3307       class loop *outer_loop = loop_outer (loop);
3308       if (outer_loop && outer_loop->force_vectorize)
3309   aggressive_if_conv = true;
3310     }

2.5? gcc在zen架構下，不支持mask gather

1769             j = pearlist[i][k];
1781             if (r2 > rgbmaxpsmax2)      
1782                continue;
1783             dij1i = 1.0 / sqrt(r2);
1784             dij = r2 * dij1i;
1785             sj = fs[j] * (rborn[j] - BOFFSET); 
1786             sj2 = sj * sj;

問題：對于每一輪的j 的值是不連續的，因此fs[j] 也不連續, 并且在if continue 之后需要進行mask, 不支持使用mask從不連續的內存向量化的取數據。

467 /* X86_TUNE_USE_GATHER_4PARTS: Use gather instructions for vectors with 4
468    elements.  */
469 /*DEF_TUNE (X86_TUNE_USE_GATHER_4PARTS, "use_gather_4parts",
470     ~(m_ZNVER1 | m_ZNVER2 | m_ZNVER3 | m_ZNVER4 | m_ALDERLAKE | m_GENERIC))*/

解決方法：可以使用-mtune-ctrl=use_gather_4parts 使其支持builtin 形式的mask gather操作。

2.6 多分支下的同一個reduction var 問題

問題：nphi_def_loop_uses >?1 一個reduction 變量在loop 中使用次數超過一個，被認為不是simple reduction 。loop vect pass 不會對其向量化。

69628 eff.c:1761:24: note:   Analyze phi: sumi_1654 = PHI <sumi_1557(320), 0.0(402)>69629 eff.c:1761:24: missed:   reduction used in loop.

解決辦法：在ifcvt pass 中加上一個函數，實現如下述源碼中的，將同一個reduction 變為多個不同的reduction ，實現向量化。

    
1763          double temp0 = 0;
1764          double temp1 = 0;
1765          double temp2 = 0;
1766          double temp3 = 0;
1767          double temp4 = 0;
1805 
1806             if ((dij > rgbmax - sj)) {
1807                uij = 1. / (dij - sj);
1808             
1813             /*   sumi -= 0.125 * dij1i * (1.0 + 2.0 * dij * uij +
1814                                         rgbmax2i * (r2 -
1815                                                     4.0 * rgbmax *
1816                                                     dij - sj2) +
1817                                         2.0 * log((dij - sj) * rgbmax1i));*/
1818            
1823                temp0 -= 0.125 * dij1i * (1.0 + 2.0 * dij * uij +
1824                                         rgbmax2i * (r2 -
1825                                                     4.0 * rgbmax *
1826                                                     dij - sj2) +
1827                                         2.0 * log((dij - sj) * rgbmax1i));
1828 
1829             } else if (dij > 4.0 * sj) {
1830                dij2i = dij1i * dij1i;
1831                tmpsd = sj2 * dij2i;
1832                dumbo =
1833                    TA + tmpsd * (TB +
1834                                  tmpsd * (TC +
1835                                           tmpsd * (TD + tmpsd * TDD)));
1836           
1837           //     sumi -= sj * tmpsd * dij2i * dumbo;
1839                temp1 -= sj * tmpsd * dij2i * dumbo;
1840 
1841             } 
1879          sumi = temp0 + temp1 + temp2+ temp3+temp4;
1880

能夠實現向量化，但是性能相對與標量下降了

544	base	向量化	加上分塊
32 copies	100	92	107

?向量化的代價太大，臨時變量，mask gather load帶來的性能下降太顯著。（性能下降的loop vect 為什么能通過，cost的計算，沒有把mask gather 算進去）。

3. 向量化后優化

3.1：循環分塊

問題：gcc 向量化后所有分支的代碼在一個bb塊里面，所以所有的分支都會走一遍，對最后運算的結果根據分支條件進行選擇，帶來冗余運算。

解決方法：發現gcc loop pass 上有對optimize_mask_stores，向量化后進行分塊的函數。在此基礎上拓展添加了對 VEC_COND_EXPR的分塊。

添加對于每個分支判斷變量全為0，也就是所有元素都不滿足該分支，則不需要進入該分支計算，省去了以部分冗余運算。

3.2：向量化因子

使用該選擇? -mtune-ctrl=^avx256_split_regs,^avx128_optimal,256_unaligned_store_optimal 打開256非對其存儲優化，可以使VF 由 4 變為8, 提高性能。

544	base	VF4	VF8
32 copies	100	101	107

4：優化詳細說明

4.1 添加的編譯選項

--param=max-unswitch-insns=150 -ftree-insert-abort
-mtune-ctrl=^avx256_split_regs,^avx128_optimal,256_unaligned_store_optimal,use_gather_4parts

1：loop unswitch? insns 參數調整，默認是50，調整到150

2：插入一個新的pass 來插入abort()

3: 使能256bit的非對齊存儲優化，VF為8.（^avx256_split_regs 不加這個也可）

4：使能256bit 的 mask gather 指令。

4.2：添加的優化代碼

4.2.1 激進的ifcvt優化（找到選項來控制）？

將?aggressive_if_conv 標志位修改為true。（能否通過某些選項來控制）

3303  // aggressive_if_conv = loop->force_vectorize;
3304   aggressive_if_conv = true;

4.2.2? 插入abort() 優化

新建一個gimple pass,? 放在adjust_alignment pass 后。（107 pass)

199   NEXT_PASS (pass_adjust_alignment);
200   NEXT_PASS (pass_insert_abort);
201   NEXT_PASS (pass_all_optimizations);

設計思路：識別對0進行判斷gimple_cond，并且判斷為true的bb 以及其single suc，有對該gimple cond lhs 定義的stmt進行解引用，則認為是對空指針解引用回出現問題，插入abort()

識別的pattern:

(1) ：識別一個gimple_cond 語句，并且是和0進行相等判斷

(2) ：找到判斷為true的bb塊以及其后繼bb塊中，是否有對該判斷條件lhs的def的stmt進行解引用使用。

transform:

（1）：找到后在gimple cond條件為true的bb 末尾插入abort()。

14044   <bb 148> [local count: 919275880]:
14045   _2044 = _127 + _2039;
14046   _2045 = *_2044;
14047   if (_2045 == 0B)
14048     goto <bb 149>; [17.43%]
14049   else
14050     goto <bb 150>; [82.57%]
14051
14052   <bb 149> [local count: 160229786]:
14053   _2046 = 0;
14054   _2047 = nabout;
14055   fprintf (_2047, "NULL pair list entry in egb loop 1, taskid = %d\n", _2046);
14056   _2048 = nabout;
14057   fflush (_2048);
14058
14059   <bb 150> [local count: 919275880]:
14060   _2049 = *_2044;
14061   _2051 = (long unsigned int) k_2050;
14062   _2052 = _2051 * 4;
14063   _2053 = _2049 + _2052;
14064   j_2054 = *_2053;

4.2.3 消除reduction use in loop （改變一種方式，消除reduction，重新修改代碼），如果是sumi的加減混合運算？

使用其他方法修改reduction 后性能沒有原方法好，因為原方法都是在循環外面，新方法需要在循環里面。

在ifcvt pass 中添加函數，（嘗試在loop vect pass 中當出現reduction use in loop? 后transform , 新建的reduction 會錯過 loop vect 中對reduction 的分析）

思路：識別reduction? 在 loop 中的使用次數超過1次的情況，找到該reduction 的phi 節點，在每次使用的地方進行替換成為不同的reduction，需要對是否進行ifcvt的兩個版本都進行轉化。標量和向量版本都會走到（如何識別是reduction?)? ? ? ?復用發現reduction 的接口，在一個新的pass 里面加上這部分代碼。

（該優化是根據先修改源碼后，產生的IR，進行對照修改，涉及到的修改較多，目前想僅僅針對該課題pattern，其他情況比較難以覆蓋）

1761           for (k = 0; k < lpears[i] + upears[i]; k++) {
1762
1763             if (pearlist[i] == NULL) {
1764                fprintf(nabout,
1765                        "NULL pair list entry in egb loop 1, taskid = %d\n",
1766                        mytaskid);
1767                fflush(nabout);
1768             }
1769             j = pearlist[i][k];
1770
1771             xij = xi - x[dim * j];
1772             yij = yi - x[dim * j + 1];
1773             zij = zi - x[dim * j + 2];
1774             r2 = xij * xij + yij * yij + zij * zij;
1775
1776             if (dim == 4) {                     // delete
1777                wij = wi - x[dim * j + 3];
1778                r2 += wij * wij;
1779             }
1780
1781             if (r2 > rgbmaxpsmax2)      //  %hir.cmp.4310 ule
1782                continue;
1783             dij1i = 1.0 / sqrt(r2);
1784             dij = r2 * dij1i;
1785             sj = fs[j] * (rborn[j] - BOFFSET);   //   select fast
1786             sj2 = sj * sj;
1787
1788             /*
1789              * ---following are from the Appendix of Schaefer and Froemmel,
1790              * JMB 216:1045-1066, 1990;  Taylor series expansion for d>>s
1791              * is by Andreas Svrcek-Seiler; smooth rgbmax idea is from
1792              * Andreas Svrcek-Seiler and Alexey Onufriev.
1793              */
1794
1795             if (dij > rgbmax + sj)      // rgbmax = 20;   %hir.cmp.4333 ule
1796                continue;
1797             double temp = 0;
1798             if ((dij > rgbmax - sj)) {      //    %hir.cmp.4349  ogt
1799                uij = 1. / (dij - sj);
1800                temp -= 0.125 * dij1i * (1.0 + 2.0 * dij * uij +
1801                                         rgbmax2i * (r2 -
1802                                                     4.0 * rgbmax *
1803                                                     dij - sj2) +
1804                                         2.0 * log((dij - sj) * rgbmax1i));
1805
1806             } else if (dij > 4.0 * sj) {
1807                dij2i = dij1i * dij1i;
1808                tmpsd = sj2 * dij2i;
1809                dumbo =
1810                    TA + tmpsd * (TB +
1811                                  tmpsd * (TC +
1812                                           tmpsd * (TD + tmpsd * TDD)));
1813                temp -= sj * tmpsd * dij2i * dumbo;
1814
1815             } else if (dij > ri + sj) {
1816                temp -= 0.5 * (sj / (r2 - sj2) +
1817                               0.5 * dij1i * log((dij - sj) / (dij + sj)));
1818
1819             } else if (dij > fabs(ri - sj)) {
1820                theta = 0.5 * ri1i * dij1i * (r2 + ri * ri - sj2);
1821                uij = 1. / (dij + sj);
1822                temp -= 0.25 * (ri1i * (2. - theta) - uij +
1823                                dij1i * log(ri * uij));
1824
1825             } else if (ri < sj) {
1826                temp -= 0.5 * (sj / (r2 - sj2) + 2. * ri1i +
1827                               0.5 * dij1i * log((sj - dij) / (sj + dij)));
1828
1829             }sumi+=temp;
1830
1831          }

進行ifcvt后的部分（向量）（初始化為0，不為0 的情況應該直接將其初始化結果加入到新建的reduction 變量中）

（1）：在loop header bb 中識別phi stmt，找到其lhs中使用次數等于該分支數量，并且初始化為0的phi stmt。

transfrom:?

（1）：新建與分支數量相等的phi stmt ，初始值為0和該循環計算后的結果，作為一個新的reduction.

? (2)? :? ?新建該reduction 和每個分支運算結果的gimple assign。

（3）：對最后結果累加運算。

48399   # k_1747 = PHI <k_2147(234), 0(279)>                                                      
48400   # sumi_1470 = PHI <sumi_2753(234), 0.0(279)>                                                
48401   # RANGE [0, 2147483647] NONZERO 2147483647  48488   sumi_2087 = sumi_1470 + _2085;
48489   _3187 = dij_2056 <= _2068;48507   sumi_2102 = sumi_1470 - _2101;
48508   _3169 = dij_2056 <= _2088;
48509   _3168 = _3169 & _3184;

轉化為：

 51162   # temp_value.1035_2087 = PHI <tmp_var.1036_2090(320), 0.0(402)>
51164   # temp_value.1043_2073 = PHI <tmp_var.1044_2063(320), 0.0(402)>51320   _ifc__2108 = _1303 ? _1605 : 0.0;51321   tmp_var.1036_2090 = _ifc__2108 + temp_value.1035_2087;
51324   _ifc__2064 = _1315 ? _1586 : 0.0;51325   tmp_var.1044_2063 = _ifc__2064 + temp_value.1043_2073;52177   # tmp_sumi.1045_2075 = PHI <tmp_var.1044_2063(304), tmp_sumi_2.1060_2061(399)>52175   # tmp_sumi.1037_2076 = PHI <tmp_var.1036_2090(304), tmp_sumi_2.1056_2057(399)>52190   # sumi_suc.1046_2042 = PHI <tmp_sumi.1045_2075(351), 0.0(74), tmp_sumi.1074_644(352)>52188   # sumi_suc.1038_2775 = PHI <tmp_sumi.1037_2076(351), 0.0(74), tmp_sumi.1068_704(352)>
52193   _2052 = sumi_suc.1038_2775 + sumi_suc.1046_2042;

不進行ifcvt的部分（標量）

transform:?

（1）：新建phi stmt 初始化為0，與分支數量相同。

（2）：修改每個分支的中間運算結果。

（3）：對每個分支的結果用phi節點來控制。

 # sumi_3078 = PHI <0.0(280), sumi_2855(277)>sumi_2872 = sumi_3078 + _2911;sumi_2973 = sumi_3078 - _2974;sumi_2855 = PHI <sumi_3078(261), sumi_3078(263), sumi_3078(269), sumi_3016(271), sumi_2999(272), sumi_2988(273), sumi_2973(274), sumi_2872(275)>

轉化為：

 51867   # temp_value_2.1081_596 = PHI <0.0(426), tmp_sumi_2.1082_597(423)>51868   # temp_value_2.1083_598 = PHI <0.0(426), tmp_sumi_2.1084_575(423)>sumi_1004 = temp_value_2.1081_596 + _1003;sumi_866 = temp_value_2.1083_598 - _865;# tmp_sumi_2.1082_597 = PHI <temp_value_2.1081_596(407),temp_value_2.1081_596(409),temp_value_2.1081_596(412),temp_value_2.1081_596(414), temp_value_2.1081_596(416),temp_value_2.1081_596(418),temp_value_2.1081_596(419), sumi_1004(421)># tmp_sumi_2.1084_575 = PHI <temp_value_2.1083_598(407), temp_value_2.1083_598(409), temp_value_2.1083_598(412), temp_value_2.1083_598(414), temp_value_2.1083_598(416), temp_value_2.1083_598(418), sumi_866(419), temp_value_2.1083_598(421)>

4.2.4 if else / if continue 向量化后分塊優化? ?（添加cost計算？）

targetm.vectorize.empty_mask_is_expensive

aarch64_empty_mask_is_expensive? 這里不做mask_store 的

default_empty_mask_is_expensive? 其他情況都會進行

26378 /* Implement TARGET_VECTORIZE_EMPTY_MASK_IS_EXPENSIVE.  Assume for now that
26379    it isn't worth branching around empty masked ops (including masked
26380    stores).  */
26381
26382 static bool
26383 aarch64_empty_mask_is_expensive (unsigned)
26384 {
26385   return false;
26386 }

仿照loop vect pass 中的optimize_mask_stores，在loop vect pass 中加上基于vec_cond_expr分塊的函數

思路：（1）識別loop 中在同一個bb 中的 VEC_COND_EXPR，

（2）根據第二個參數找到每個分支最后計算的結果，從此處開始拆分bb。

（3）根據第一個參數mask，找到每個分支條件，將這兩個mask相或，在此后新建一個該或結果與0進行比較的gimple_cond，插入到分支條件后，同時新建該結果判斷為ture 和 false的edge,分別指向新建的bb和其下一個bb。

（4）在拆分bb 塊后面新建一個空 bb ,并且gimple_cond 之后的stmt 移動到新建的bb 中，維護其edge,指向下一個bb.

 98615   vect__ifc__2106.1217_795 = VEC_COND_EXPR <mask__1612.1193_854, vect__1541.1206_870, { 0.0, 0.0, 0.0, 0.0 }>;98616   vect__ifc__2106.1217_796 = VEC_COND_EXPR <mask__1612.1193_821, vect__1541.1206_871, { 0.0, 0.0, 0.0, 0.0 }>; 98621   vect__ifc__2706.1220_803 = VEC_COND_EXPR <mask__1617.1210_879, vect__1555.1216_792, { 0.0, 0.0, 0.0, 0.0 }>;98622   vect__ifc__2706.1220_804 = VEC_COND_EXPR <mask__1617.1210_880, vect__1555.1216_793, { 0.0, 0.0, 0.0, 0.0 }>;

? ? ? ?

? ? ? ? ?

5.其他優化探索

5.1帶有mask的向量數學函數

在loop vect pass 后新建一個pass ,替換原有的數學函數調用帶有mask的svml函數。

 98615   vect__ifc__2106.1217_795 = VEC_COND_EXPR <mask__1612.1193_854, vect__1541.1206_870, { 0.0, 0.0, 0.0, 0.0 }>;

設計方案：找到一個VEC_COND_EXPR，在同一個基本塊中，根據參數中的分支運算的結果，順著運算的關系一步步往上找（SSA_NAME_DEF_STMT)，進行深度優先遍歷，直到找到了需要進行mask的數學函數。VEC_COND_EXPR中的參數mask就是數學函數需要進行mask的值。將數學函數和mask一起生成帶有mask的數學函數的IR，替換掉原來的不帶mask的。