<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
p.gmail-m-1391975889066283759msolistparagraph, li.gmail-m-1391975889066283759msolistparagraph, div.gmail-m-1391975889066283759msolistparagraph
{mso-style-name:gmail-m_-1391975889066283759msolistparagraph;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
.MsoPapDefault
{mso-style-type:export-only;
margin-top:6.0pt;
margin-right:0cm;
margin-bottom:6.0pt;
margin-left:0cm;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:383914736;
mso-list-template-ids:-2061080194;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1
{mso-list-id:435638757;
mso-list-template-ids:762882368;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2
{mso-list-id:479158295;
mso-list-template-ids:718561846;}
@list l2:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3
{mso-list-id:683019598;
mso-list-template-ids:474885760;}
@list l3:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4
{mso-list-id:771903755;
mso-list-template-ids:-719031486;}
@list l4:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l5
{mso-list-id:841818632;
mso-list-template-ids:2050031380;}
@list l5:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l5:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l5:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l5:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l5:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l5:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l5:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l5:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l5:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l6
{mso-list-id:841820987;
mso-list-template-ids:1457684456;}
@list l6:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l6:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7
{mso-list-id:941645292;
mso-list-template-ids:-1105324582;}
@list l7:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l7:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l8
{mso-list-id:961887266;
mso-list-template-ids:1389387548;}
@list l9
{mso-list-id:1323656337;
mso-list-template-ids:-788340632;}
@list l9:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l9:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l9:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l9:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l9:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l9:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l9:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l9:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l9:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l10
{mso-list-id:1350445876;
mso-list-template-ids:1542333794;}
@list l10:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l10:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l11
{mso-list-id:1610771627;
mso-list-template-ids:2082251812;}
@list l11:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l11:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l11:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l11:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l11:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l11:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l11:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l11:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l11:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l12
{mso-list-id:1610893493;
mso-list-template-ids:-172167248;}
@list l12:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l12:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13
{mso-list-id:1653874152;
mso-list-template-ids:30559892;}
@list l13:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l13:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14
{mso-list-id:1783958808;
mso-list-template-ids:126379260;}
@list l14:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l14:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l15
{mso-list-id:1830169644;
mso-list-template-ids:-2032399338;}
@list l15:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l15:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l15:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l15:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l15:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l15:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l15:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l15:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l15:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l16
{mso-list-id:1877505464;
mso-list-template-ids:-263975546;}
@list l16:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l16:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17
{mso-list-id:1940524676;
mso-list-template-ids:197145964;}
@list l17:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l17:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal" style="margin-left:36.0pt">I often hear from researchers and Haskell experts that whole program compilation does not work.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Do you? Not from me I hope.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">My position is rather: I think there <b>should</b> be things we can get from WPC, but dead-code elim is the only quick win that is obvious to me. I fully expect there are less obvious wins, but I would love to see demonstrated examples.
So I don’t think you are on the wrong track! <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Simon<o:p></o:p></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US">From:</span></b><span lang="EN-US"> Csaba Hruska <csaba.hruska@gmail.com>
<br>
<b>Sent:</b> 21 June 2020 14:41<br>
<b>To:</b> Simon Peyton Jones <simonpj@microsoft.com><br>
<b>Cc:</b> Alexis King <lexi.lambda@gmail.com>; GHC developers <ghc-devs@haskell.org><br>
<b>Subject:</b> Re: Introducing GHC whole program compiler (GHC-WPC)<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Hello,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
All the questions you have asked are important, but before I answer them I'd like to emphasize that as a research platform it is worth supporting WPC/WPA even with the worst case memory and runtime properties. It would allow researchers to observe Haskell programs
with arbitrary precision. Not giving access to the whole program IR simply rules out certain types of research directions. IMO this is an important issue, because some experiment might reveal something that is applicable in practice or might be implemented
in the incremental compilation pipeline as well. I find it cool to allow developers to use GHC in an unexpected or unintended way that may lead to something new and valuable.<o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
It is common sense that whole (or large chunks) program analysis and compilation is infeasible. I believe that common sense needs to be reevaluated time to time, because the conditions may change. E.g.. Would the existence of huge amounts of RAM with multicore
CPUs or GPU or quantum computers change the situation? Not to mention the new research results of the static analysis field.<o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Questions that come to mind (to be understood in the context of the above enthusiasm):<o:p></o:p></p>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l10 level1 lfo1">
If you compile a program that depends on (say) lens, you get a lot of code. Dead-code elim will drop lots, perhaps, but you start with everything. So what do memory footprints and compile times look like when you do WPC? Remembering that people often complain
about GHC’s footprint when compiling a <i>single</i> module. <br>
Also, WPC means that instead of just linking to precompiled libraries, you have to recompile (parts of) them. What does that do to compile times?<o:p></o:p></li></ul>
</div>
</blockquote>
<div>
<div>
<p class="MsoNormal">I deliberately split the WPC pipeline into IR export and import/codegen pieces. GHC-WPC does only the STG IR export, and the External STG compiler could be seen as a separate project that uses GHC-WPC as frontend and GHC as backend. It
is important to note that compilation pipeline design is not fixed in this setting. It could implement the regular per module incremental compilation, or could batch compile multiple modules or even the whole program. The IR export part is the same for each
case, only the backend driver differs.<br>
While it is true that the GHC-WPC project implements the whole program compiler scenario currently, I also plan to extend it to allow incremental compilation with arbitrary sized program clusters. So it would not use the source code structure based module or
package boundaries, instead the compilation unit size granularity could be changed at will. Possibly driven by some static or runtime analysis. It would be a free parameter that can be adjusted to get an acceptable compilation time, and as the software and
hardware advances the practical compilation unit size would increase.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">It is also possible to implement incremental whole program compilation. This technique is already used in the Visual C++ compiler:
<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdl.acm.org%2Fdoi%2Fpdf%2F10.5555%2F3049832.3049857&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426315953&sdata=rh9F4tjw6%2Fq4C2%2BNfud5OBG%2Fu6vgFa3dn8ZnNjYlP%2Fc%3D&reserved=0" target="_blank">
Incremental Whole Program Optimization and Compilation</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal">The current whole program compilation pipeline first compiles the project with GHC-WPC. GHC-WPC compiles the target project through the standard GHC backend and generates executable, in addition it exports the Ext-STG IR. Then gen-exe is
executed and the whole stg program compilation is done using the following steps:<o:p></o:p></p>
<ol start="1" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l8 level1 lfo2">
extracting liveness datalog facts from each project module<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l8 level1 lfo2">
running the whole program liveness analysis<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l8 level1 lfo2">
per module link time codegen for the whole project cutting out the dead top level functions using the liveness analysis result<o:p></o:p></li></ol>
</div>
<p class="MsoNormal">I designed the pipeline to have a light memory footprint. I intentionally implemented the static analyses in Datalog using the Souffle Datalog compiler. Souffle generates small and efficient parallel (OpenMP) C++ code that stores the in-memory
database in specialised data types (Trie/B-tree).<br>
Another important design choice was to collect the datalog facts incrementally for static analysis, instead of loading the whole program IR to the memory. The insight is that it is not the complete IR that is needed for whole program analysis, but just a projection
of the IR. It is perfectly OK to calculate that projection on a per module basis, then run the static analysis on the collected data. Furthermore it is even possible to store the collected facts in files separately for each module for later reuse.<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">I measured the compilation of pandoc and a simple (hello world like) project. I put the collected data grouped by compilation stages into bullet points with notes:<o:p></o:p></p>
</div>
<div>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
ext-stg export<br>
Currently the serializer uses binary via the generic instance, which is not the fastest method. The store package via TH would be the fastest way of exporting the IR, but it is not in the foundation libraries. Also at the current stage of the project this is
not an issue (binary is good enough).<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
liveness datalog fact generator<br>
simple: 2.107545216s<br>
pandoc: 18.431660236s<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
liveness datalog facts size:<br>
simple: 11 MB<br>
pandoc: 186 MB<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
liveness analysis (CSV) result size:<br>
simple: 92 KB<br>
pandoc: 14 MB<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
liveness analysis memory usage:<br>
simple: Maximum resident set size: 15 MB<br>
pandoc: Maximum resident set size: 109 MB<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
liveness analysis run time:<br>
simple: 0.118736736s<br>
pandoc: 2.322970868s<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
link time codegen via GHC:<br>
simple: 15.683492995s<br>
pandoc: 790.070061268s<br>
memory usage: around 100 MB (typical GHC module compilation footprint)<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l11 level1 lfo3">
gen-exe is the whole stg program compiler driver:<br>
simple:<br>
Maximum resident set size: 186 MB<br>
Elapsed (wall clock) time: 18.63 sec<br>
pandoc:<br>
Maximum resident set size: 401 MB<br>
Elapsed (wall clock) time: 13 min 35 sec<o:p></o:p></li></ul>
<p class="MsoNormal">GHC-WPC Ext-STG IR serializer<o:p></o:p></p>
</div>
<div>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l9 level1 lfo4">
without ext-stg export -O0 from scratch with deps (full world)<br>
simple: 5.455 sec<br>
pandoc: 8 min 54.363 sec<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l9 level1 lfo4">
with ext-stg export -O0 from scratch with deps (full world)<br>
simple: 5.576 sec<br>
pandoc: 12 min 50.101 sec<o:p></o:p></li></ul>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l14 level1 lfo5">
I love the 25% reduction in binary size. In fact I’m surprised it isn’t bigger. <o:p>
</o:p></li></ul>
</div>
</blockquote>
<div>
<p class="MsoNormal"> I used a simple and fast method for the link time dead code elimination. It calculates the references of the module top level functions transitively, then only the reachable ones are passed to the codegen. So it does not eliminate the
local closures, nor the dead case alternatives. Check the analysis source code how simple the implementation is:
<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fgrin-compiler%2Fghc-whole-program-compiler-project%2Fblob%2Fmaster%2Fexternal-stg-compiler%2Fdatalog%2Fext-stg-liveness.dl&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426315953&sdata=fr0fbO21e2c048s%2BJSMVfRbhX9Y%2Fl%2BcmXfzS%2BEVBONQ%3D&reserved=0">
ext-stg-liveness.dl</a><o:p></o:p></p>
</div>
<div>
<p style="margin:0cm;margin-bottom:.0001pt" id="gmail-docs-internal-guid-316b64e8-7fff-2580-8d38-c57e52809896">
<o:p> </o:p></p>
<p class="MsoNormal">I also implemented a much more sophisticated control flow analysis, which could eliminate much more code. i.e.<o:p></o:p></p>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l5 level1 lfo6">
constructor data fields<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l5 level1 lfo6">
case alternatives<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l5 level1 lfo6">
function parameters<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l5 level1 lfo6">
local closures<o:p></o:p></li></ul>
<p class="MsoNormal">It is future work to integrate this precise CFA into the external STG compiler pipeline. My initial goal was to create the simplest and fastest working whole compiler pipeline for GHC. So I prioritised my plans and tasks accordingly.<br>
I'd like to mention that the current pipeline design is a result of iterative development. The first version was written entirely in Haskell. It comprised a points-to analysis and the simple liveness analysis. The Haskell version of these analyses worked fine
for small programs, but the memory and runtime properties were bad. Of course I tried to add some strictness annotations, that helped a bit, but it was not good enough. Then I rewrote the points-to analysis in C++, which resulted in a much better memory footprint,
but my fixed point evaluator was still naive so it was not fast enough. Also the C++ implementation increased the development and maintenance complexity that I did not like. Luckily I found the Souffle Datalog compiler that just fits my needs. It is super
easy to write static analyses in Datalog and it does not compromise in the performance either. I'd like to write all these parts in Haskell but IMO it is not possible yet. Hopefully this will change in the future, maybe LoCal can make a big difference. (<a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Frecurial.com%2Fpldi19main.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426325913&sdata=DojMrnzpvK9BAmk4X7Afy0DWJZcrecvchsXOCNr%2F%2FuE%3D&reserved=0">http://recurial.com/pldi19main.pdf</a>)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l12 level1 lfo7">
Why are you using STG? It’s mostly untyped – or at least much less strongly typed than Core. It has lots of restrictions (like ANF) that Core does not. Indeed I think of STG as a little lily-pad to alight on in the hop from Core to Cmm. Maybe your entire
setup would work equally well with Core, provided you can serialise and deserialise it.<o:p></o:p></li></ul>
</div>
</blockquote>
<p class="MsoNormal">To me every IR layer is an API for the compiler. The long term existence of the different IRs must have a reason. As I understand, the GHC Core is about polymorphic reasoning and STG IR is about operational semantics with explicit notion
of evaluation, allocation of closures/data constructors and pattern matching. Thirdly, Cmm is the language of the runtime system that expresses the lowest level memory operations.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I chose STG because I am interested in the analysis of the operational semantics of Haskell programs. I see STG IR as an entry/exit point for the GHC pipeline. The actual IR data type does not matter because most researchers or developers
will have their own needs regarding the IR conventions. I.e. I'd like to write analyses in Souffle/Datalog but both GHC Core and GHC STG are insufficient for direct datalog translation, because not every expression has a name, neither a unique one. But this
is totally fine. It is impossible to design the perfect IR, instead everyone should do the customised conversion for their project.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">IMO STG is implicitly typed, its type system is the TYPE's RuntimeRep kind parameter that describes the value’s runtime representation. And this is exactly what I'm interested in, because the Core type system is not expressive enough for
the optimizations that I'd like to implement. In fact GHC has the unarise pass that flattens unboxed tuples, and it is implemented in STG because it would not type check in Core. Also there are Cmm and LLVM transformations that are semantically valid but not
typeable in GHC Core.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Ideally it would be great to have a single IR that could express both Core and Cmm properties in a typed way, but it would require a much stronger (probably dependent) type system. I find this idea a promising research direction.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Indeed the whole GHC-WPC could support Core also, it would just be an additional export operation at the same place in the GHC and Cabal source code where STG gets exported. The same would be true for the Cmm IR.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l6 level1 lfo8">
Moreover, we *<b>already</b>* have a fast serialiser and deserialiser for Core – the stuff we use for interface files. So maybe you could re-use that … no need for pretty-print and parse.<o:p></o:p></li></ul>
</div>
</blockquote>
<div>
<p class="MsoNormal">Ideally there would be a binary import/export facility and pretty printer for every IR layer. The speed might matter for the main use cases but for the experimental cases it is not an issue at all. Serializers would allow us to use GHC
internal components with finer granularity and from arbitrary programming languages. Having a binary IR (de)serializer without a specification or without stability guarantees is still much better than having nothing.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l13 level1 lfo9">
You say “That would mean a significant conceptual shift in the GHC compiler pipeline, because heavy optimizations would be introduced at the low level IRs beside GHC Core.” Fair enough, but what I’m missing is the
<b>rationale</b> for doing heavy opts on STG rather than Core.<o:p></o:p></li></ul>
</div>
</blockquote>
<div>
<p class="MsoNormal"> The Core type system is not expressive enough to reason about memory layout. Of course STG's RuntimeRep type system cannot describe the shape of the heap either, but at least it can be used as a starting point in an experiment.<br>
Haskell and pure functional programming formed my views on how to automate programming tasks, and how to utilise the type system for specific domains. Haskell as a pure FP also shaped how I see compilers. The traditional view is that at the top of the compilation
pipeline there is the high level language with a rich and rigorous type system, and during the compilation process (lowering) every lower level IR has a weaker type system that encodes slightly less semantic information. And at the level of assembly language
or machine code there is nothing left from the original types and semantic information. So instead of this traditional approach I can imagine a pipeline that preserves high level semantic information during the lowering process. But for this the low-level
IRs would require increasingly more expressive type systems. I'd like to explore this idea further and GHC would be a good platform for such an experiment. I also believe that this direction is the future of compilers and programming languages.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l1 level1 lfo10">
Apart from (a) dead code, and (b) GRIN, do you have ideas in mind for what we could do with WPC?<o:p></o:p></li></ul>
</div>
</blockquote>
<div>
<p class="MsoNormal">I have lots of ideas regarding the usage of the whole program IR.<o:p></o:p></p>
</div>
<div>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt;mso-list:l0 level1 lfo11">
GHC-WPC's exported STG IR could be useful for any backend or codegen project.<br>
The existing cross compilation projects like Asterius and GHCJS could use the External-STG as input IR. The benefit of this approach is that the alternative Haskell compiler backends do not need to be supported by Cabal directly instead they would entirely
rely on the External STG IR and the exported linker metadata file.<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt;mso-list:l0 level1 lfo11">
External STG could allow using GHC as frontend and backend, with additional support of custom IR transformations.<br>
E.g. maybe the <a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fiu-parfunc.github.io%2Fgibbon%2F&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426325913&sdata=6UeZA2%2F%2Bx0ibVbOXJkMTGF8VVwqFjS%2BBRiWBQy8QMjw%3D&reserved=0">
Gibbon</a> language project could compile real-world Haskell programs via Ext-STG. Or maybe Purescript or Idris would add GHC with RTS as a new target. STG's weaker type system is actually beneficial for programming languages that differ from Haskell in evaluation
model or type system.<br>
Maybe I'll add external Core or external Cmm support also.<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt;mso-list:l0 level1 lfo11">
The Intel Haskell Research Compiler optimizer part is called Functional Language Research Compiler (<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FIntelLabs%2Fflrc%23the-functional-language-research-compiler-&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426325913&sdata=iowWjGeFbMjBwqtMPLzYwlxUT9znNUBqNAploe4%2FmO8%3D&reserved=0">FLRC</a>)
and its IR is called MIL. Its source is on github and it still compiles. I'd like to plug the FLRC vectorising and memory layout optimizer into GHC. FLRC's RTS was not optimized for laziness, however it would be interesting to see how it would perform with
GHC's fine tuned GC and RTS.<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt;mso-list:l0 level1 lfo11">
I also plan to implement an STG interpreter with FFI support that could run any Haskell program.<br>
With such an interpreter I could implement runtime control flow tracing, or a stop the world debugger that could observe and visualize the runtime heap values. I'd like to track the source origin and lifetime of run-time values. I'd use that information to
build a better intuition of the Haskell program’s runtime behaviour. I hope that it will lead to important insights to improve the performance. I'm optimistic with this idea because AFAIK it has not been done yet. Haskell's GC removes the unreachable values
from the memory that might be dead for a long time. According to the As Static As Possible Memory Management thesis, reachability is too conservative approximation of the actual liveness.<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo11">
I’d like to do partial defunctionalization on the STG IR.<br>
Regarding the engineering complexity of an optimizing compiler I believe it is the easiest to start with a whole program analysis and compilation. It is easier to construct a static analysis as a data flow analysis, then later with the insights the same analysis
could be formulated as a type system. Which might enable compositional analysis, and therefore incremental compilation.<o:p></o:p></li></ul>
<p class="MsoNormal">I see GHC-WPC as a framework that would allow us to explore these ideas.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
I often hear from researchers and Haskell experts that whole program compilation does not work. They seem so confident with this claim, and I'd like to understand why. I read several papers on the topic and also checked quite a few compilers’ source code. LLVM,
GCC, Visual C++ is doing LTO. Intel Haskell Research Compiler research results, MLton, Boquist's GRIN supports the idea of whole program analysis and compilation. At least it seems reasonable to continue the research in this direction. I wonder if those who
concluded against WPA read the same papers and projects.<br>
<br>
Do you think that I am on the wrong track?<o:p></o:p></p>
<div>
<p class="MsoNormal">Am I chasing unimportant or impossible things?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><br>
Important papers:<o:p></o:p></p>
</div>
<div>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l15 level1 lfo12">
The Intel Labs Haskell Research Compiler<br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.leafpetersen.com%2Fleaf%2Fpublications%2Fhs2013%2Fhrc-paper.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426335866&sdata=xb1zM%2BBxJUYEJc3DgKA3SSVOVOP09vM6IloNra8XTkk%3D&reserved=0">http://www.leafpetersen.com/leaf/publications/hs2013/hrc-paper.pdf</a><o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l15 level1 lfo12">
Measuring the Haskell Gap<br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.leafpetersen.com%2Fleaf%2Fpublications%2Fifl2013%2Fhaskell-gap.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426335866&sdata=grXRj5LtGUiGKBkHManA8EdKq62zqJS9OnKJjkm11QI%3D&reserved=0">http://www.leafpetersen.com/leaf/publications/ifl2013/haskell-gap.pdf</a><o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l15 level1 lfo12">
LoCal: A Language for Programs Operating on Serialized Data<br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Frecurial.com%2Fpldi19main.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426335866&sdata=zhSFQsHitxKk65tipdsaaBuw5JEMtGUFU9uV45NiZwg%3D&reserved=0">http://recurial.com/pldi19main.pdf</a><o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l15 level1 lfo12">
On fast large-scale program analysis in Datalog<br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fsouffle-lang.github.io%2Fpdf%2Fcc.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426345823&sdata=oHHOZpD%2FufgPBVZLyqu2BTTLPfrQhVGqWi%2BuEgqixSw%3D&reserved=0">https://souffle-lang.github.io/pdf/cc.pdf</a><o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l15 level1 lfo12">
ASAP: As Static As Possible memory management<br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.cl.cam.ac.uk%2Ftechreports%2FUCAM-CL-TR-908.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426345823&sdata=jXdwSdr5hye%2Bz223akBUFd8JAT2LiadAi5ecQStY2gc%3D&reserved=0">https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf</a><o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l15 level1 lfo12">
Pushdown Control-Flow Analysis for Free<br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Farxiv.org%2Fabs%2F1507.03137&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426355784&sdata=HgUm5lcQ1ANZqYXnF6T83TSIk3Fca3hGeetr46MzMkw%3D&reserved=0">https://arxiv.org/abs/1507.03137</a><o:p></o:p></li></ul>
</div>
<div>
<p class="MsoNormal">Regards,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Csaba Hruska<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Mon, Jun 15, 2020 at 11:34 AM Simon Peyton Jones <<a href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">I’ve always thought that whole-program compilation has the possibility of doing optimisations that are simply inaccessible without the whole program, but been daunted by the engineering
challenges of making WPC actually work. So it’s fantastic that you’ve made progress on this. Well done!
<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Questions that come to mind (to be understood in the context of the above enthusiasm):<o:p></o:p></p>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l2 level1 lfo13">
If you compile a program that depends on (say) lens, you get a lot of code. Dead-code elim will drop lots, perhaps, but you start with everything. So what do memory footprints and compile times look like when you do WPC? Remembering that people often complain
about GHC’s footprint when compiling a <i>single</i> module.<o:p></o:p></li></ul>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:36.0pt">
Also, WPC means that instead of just linking to precompiled libraries, you have to recompile (parts of) them. What does that do to compile times?
<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l16 level1 lfo14">
I love the 25% reduction in binary size. In fact I’m surprised it isn’t bigger.<o:p></o:p></li></ul>
<p class="gmail-m-1391975889066283759msolistparagraph"> <o:p></o:p></p>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l17 level1 lfo15">
Why are you using STG? It’s mostly untyped – or at least much less strongly typed than Core. It has lots of restrictions (like ANF) that Core does not. Indeed I think of STG as a little lily-pad to alight on in the hop from Core to Cmm. Maybe your entire
setup would work equally well with Core, provided you can serialise and deserialise it.<o:p></o:p></li></ul>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l7 level1 lfo16">
Moreover, we *<b>already</b>* have a fast serialiser and deserialiser for Core – the stuff we use for interface files. So maybe you could re-use that … no need for pretty-print and parse.<o:p></o:p></li></ul>
<p class="gmail-m-1391975889066283759msolistparagraph"> <o:p></o:p></p>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l3 level1 lfo17">
You say “That would mean a significant conceptual shift in the GHC compiler pipeline, because heavy optimizations would be introduced at the low level IRs beside GHC Core.” Fair enough, but what I’m missing is the
<b>rationale</b> for doing heavy opts on STG rather than Core.<o:p></o:p></li></ul>
<p class="gmail-m-1391975889066283759msolistparagraph"> <o:p></o:p></p>
<ul type="disc">
<li class="gmail-m-1391975889066283759msolistparagraph" style="mso-list:l4 level1 lfo18">
Apart from (a) dead code, and (b) GRIN, do you have ideas in mind for what we could do with WPC?<o:p></o:p></li></ul>
<p class="gmail-m-1391975889066283759msolistparagraph"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Thanks<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Simon<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div style="border:none;border-left:solid windowtext 1.5pt;padding:0cm 0cm 0cm 4.0pt;border-color:currentcolor currentcolor currentcolor blue">
<div>
<div style="border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0cm 0cm 0cm;border-color:currentcolor currentcolor">
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><b><span lang="EN-US">From:</span></b><span lang="EN-US"> ghc-devs <<a href="mailto:ghc-devs-bounces@haskell.org" target="_blank">ghc-devs-bounces@haskell.org</a>>
<b>On Behalf Of </b>Csaba Hruska<br>
<b>Sent:</b> 14 June 2020 13:46<br>
<b>To:</b> Alexis King <<a href="mailto:lexi.lambda@gmail.com" target="_blank">lexi.lambda@gmail.com</a>><br>
<b>Cc:</b> GHC developers <<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a>><br>
<b>Subject:</b> Re: Introducing GHC whole program compiler (GHC-WPC)</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Hi,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">I thought about the GHC-LTO project name before, but it would not be an accurate description though. The GHC-WPC in its current state is about exporting STG + linker info for later processing,
either feed it back to GHC backend or to a third party pipeline. It depends what the user/researcher wants, the point is that GHC-WPC solves the IR export part of the issue. It is the external stg compiler that implements a (simple) whole program dead function
elimination pass that I implemented as a proof of concept to show the new possibilities GHC-WPC opens up. But I plan to do much more optimization with sophisticated dataflow analyses. I.e. I have a fast and working implementation of control flow analysis in
souffle/datalog that I plan to use to do more accurate dead code elimination and partial program defunctionalization on the whole program STG IR. In theory I could implement all GRIN optimizations on STG. That would mean a significant conceptual shift in the
GHC compiler pipeline, because heavy optimizations would be introduced at the low level IRs beside GHC Core. I'd like to go even further with experimentation. I can imagine a dependently typed Cmm with a similar type system that ATS (<a href="https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.ats-lang.org%2FMYDATA%2FVsTsVTs-2018-10-28.pdf&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426355784&sdata=y%2BaBJDnFNAG0bcedIlGDzeOVyh6I2RMwfZCUV7OooWs%3D&reserved=0" target="_blank">http://www.ats-lang.org/MYDATA/VsTsVTs-2018-10-28.pdf</a>)
has. I definitely would like to make an experiment in the future, to come up with an Idirs2 EDSL for GHC RTS heap operations where the type system would ensure the correctness of pointer arithmetic and heap object manipulation. The purpose of GHC-WPC in this
story is to deliver the IR for these stuff.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Beside exporting STG IR, the external STG compiler can compile STG via GHC's standard code generator. This makes GHC codegen/RTS available as a backend for programming language developers.
I.e. Idris, Agda, Purescript could use GHC/STG/RTS as a backend with all of its cool features.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">So these are the key parts of my vision about the purpose and development of GHC-WPC. It is meant to be more than a link time optimizer.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Cheers,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Csaba<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">On Sat, Jun 13, 2020 at 10:26 PM Alexis King <<a href="mailto:lexi.lambda@gmail.com" target="_blank">lexi.lambda@gmail.com</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid windowtext 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt;border-color:currentcolor currentcolor currentcolor rgb(204,204,204)">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Hi Csaba,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">I originally posted this comment <a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.reddit.com%2Fr%2Fhaskell%2Fcomments%2Fh7t8wr%2Fintroducing_ghc_whole_program_compiler_ghcwpc%2Ffuqdnye%2F&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426365739&sdata=s1VfLnKIybBpEjP0CsuvPsmJC5Mrk0d76SMFHG15FoU%3D&reserved=0" target="_blank">on
/r/haskell</a> before I saw you also sent this to ghc-devs. I’ve decided to reproduce my comment here as well, since this list probably has a more relevant audience:<o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">I want to start by saying that I think this sounds totally awesome, and I think it’s a fantastic idea. I’m really interested in seeing how this progresses!<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"><br>
I do wonder if people might find the name a little misleading. “Whole program compilation” usually implies “whole program optimization,” but most of GHC’s key optimizations happen at the Core level, before STG is even generated. (Of course, I’m sure you’re
well aware of that, I’m just stating it for the sake of others who might be reading who aren’t aware.)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"><br>
This seems much closer in spirit to “link-time optimization” (LTO) as performed by Clang and GCC than whole program compilation. For example, Clang’s LTO works by “linking” LLVM bitcode files instead of fully-compiled native objects. STG is not quite analogous
to LLVM IR—GHC’s analog would be Cmm, not STG—but I think that difference is not that significant here: the STG-to-Cmm pass is quite mechanical, and STG is mostly just easier to manipulate.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"><br>
tl;dr: Have you considered naming this project GHC-LTO instead of GHC-WPC?<o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Alexis<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt"><o:p> </o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">On Jun 12, 2020, at 16:16, Csaba Hruska <<a href="mailto:csaba.hruska@gmail.com" target="_blank">csaba.hruska@gmail.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
<div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Hello,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">I've created a whole program compilation pipeline for GHC via STG.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Please read my blog post for the details:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"><a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.patreon.com%2Fposts%2Fintroducing-ghc-38173710&data=02%7C01%7Csimonpj%40microsoft.com%7C26c8bdcfdce940474bfe08d815e8bc1c%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637283437426365739&sdata=TXa9%2BkFUdm5qkoh1y2hr4%2Fg%2FrFp3HmjKSDGlg7TRKa4%3D&reserved=0" target="_blank">Introducing
GHC whole program compiler (GHC-WPC)</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Regards,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Csaba Hruska<o:p></o:p></p>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</body>
</html>