<html dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style id="owaParaStyle" type="text/css">P {margin-top:0;margin-bottom:0;}</style>
</head>
<body ocsi="0" fpstyle="1">
<div style="direction: ltr;font-family: Tahoma;color: #000000;font-size: 10pt;"><br>
This is a first step towards to full iterative compilation framework for<br>
Clang/LLVM. The attached patch is work in progress and the idea of sending<br>
it to the list earlier rather than later is to open up a discussion on<br>
iterative compilation in Clang/LLVM. All comments are welcome, especially<br>
those related to integration of the framework into Clang/LLVM.<br>
<br>
Current compilers have pipeline structure in which data from one phase is<br>
passed to the following one. But these compilation phases can interfere in<br>
unpredictable way so compilers use conservative heuristics on which they<br>
make decisions during the compilation process. Because of unpredictability<br>
of these interferences, compilers sometimes make decisions which can degrade<br>
code quality. Iterative compilation could partially resolve these problems<br>
by allowing compiler to explore some alternative decisions, generate code<br>
for these new decision paths and take the generated code that is the best<br>
for a particular criteria eventually.<br>
<br>
This approach is not new in the literature, we can mention Milepost/CTuning<br>
[http://ctuning.org] among other projects. In this approach, in comparison<br>
to Milepost/CTuning, the emphasis is on much finer granularity by changing<br>
arbitrary compiler decisions, and not only those based on values of command<br>
line options, at any point in translation process.<br>
<br>
This framework implements iterative approach in which in every iteration<br>
slightly different code is generated. At the end of compilation process the<br>
best emitted code is chosen.<br>
<br>
All points at which relevant decisions are made should be identified. <br>
Access to framework data structure (DecisionTree) should be provided at<br>
these points. Based on the data from DecisionTree, obtained by calling<br>
getDecision member function, at these points decisions are made whether to<br>
execute default actions (as compiler would do without this framework) or to<br>
follow alternative paths.<br>
<br>
Let us consider Inliner example:<br>
<br>
Original code:<br>
<br>
if (!IC) {<br>
DEBUG(dbgs() << " NOT Inlining: cost=" << IC.getCost()<br>
<< ", thres=" << (IC.getCostDelta() + IC.getCost())<br>
<< ", Call: " << *CS.getInstruction() << "\n");<br>
return false;<br>
}<br>
<br>
Code after instrumentalization:<br>
<br>
bool doInlinging = (bool)IC;<br>
DecisionTreeProxy *decisionTreeProxy;<br>
decisionTreeProxy =<br>
moduleDecisionTreeProxies->getCurrFnDecisionTreeProxy();<br>
int t = MaxDtPriority - abs(IC.getCostDelta());<br>
bool decision = false;<br>
if (t >= 0)<br>
decision = decisionTreeProxy->getDecision(call);<br>
if (decision)<br>
doInlinging = !doInlinging;<br>
<br>
if (!doInlinging) {<br>
DEBUG(dbgs() << " NOT Inlining: cost=" << IC.getCost()<br>
<< ", thres=" << (IC.getCostDelta() + IC.getCost())<br>
<< ", Call: " << *CS.getInstruction() << "\n");<br>
return false;<br>
}<br>
<br>
Function getDecision returns true or false. If false is returned than this<br>
means to take default path and true means to take alternative one.<br>
<br>
Compilation process can be represented by sequence of binary values where<br>
every value determines decision made at some point. Value FALSE means to<br>
follow normal compilation process as original compiler would do without<br>
presence of iterative compilation framework. TRUE value means to take<br>
alternative path or to make opposite decision at that point. This naturally<br>
forms tree like structure which we named Decision Tree. <br>
Traversing the tree from the root to the leaf of the tree provides all the<br>
decisions made during one iteration in compilation process.<br>
<br>
At the end of each iteration, quality of generated code is estimated by<br>
executing newly introduced target dependent pass. Based on results path for<br>
the following iteration is calculated. At the moment, this has been proved<br>
for MIPS only and it is based on code size.<br>
<br>
Initially iterative compilation framework was implemented in CodeGen phase<br>
but large number of code transformations was already performed in earlier<br>
phases. This reduces possibilities to improve quality of generated code.<br>
Thus iterative compilation framework is applied to Clang driver where it can<br>
influence every single compiler phase. This relocation resulted in some<br>
implementation issues mostly related to the fact that driver and the<br>
compiler itself (-cc1) are located in different processes. This is resolved<br>
by introducing DecisionTreeProxy class that implements communication between<br>
these two processes through temporary files.<br>
<br>
At this point mechanism is applied to two optimizations: Inliner and Loop<br>
Invariant Code Motion. Supported platform is MIPS32r2.<br>
<br>
Despite small number of instrumented points we got improvements on some test<br>
files from CSiBE benchmark. Here are the promising results:<br>
<br>
jpeg-6b/jidctflt.c -10.2%<br>
OpenTCP-1.0.4/system.c -6.7%<br>
libmspack/test/chmd_md5.c -5.8%<br>
flex-2.5.31/regex.c -4.8%<br>
<br>
We plan to apply this framework to more compiler phases and to some other<br>
target architectures. It is expected to give better results on some non<br>
orthogonal architectures like microMIPS. Another direction is to apply<br>
machine learning based on some input program features (number of basic<br>
blocks, register pressure at some point etc.) and it can be used for<br>
selecting compilation path for the next iteration or estimating the best<br>
path for compiling program without using iterative approach (with only one<br>
iteration).<br>
<br>
<br>
o<br>
/ \<br>
/ \<br>
o \<br>
/ \<br>
/ \<br>
o o<br>
/ \ /<br>
/ \ /<br>
L1 o o<br>
/ /<br>
/ /<br>
L2 L3<br>
<br>
Figure 1: Decision Tree Example - Symbol 'o' represent decision points. If<br>
getDecision function returns FALSE the left branch is taken (default path),<br>
otherwise the right branch is taken.<br>
'L1' compilation iteration can be represented as a string<br>
(FALSE,FALSE,FALSE), 'L2' as (FALSE,FALSE,TRUE,FALSE) and 'L3'<br>
as (TRUE, FALSE, FALSE).<br>
<br>
<br>
Clearly, we see huge potential in this direction. At the same time, we are<br>
aware this would cause compiler to be slower which everyone is against, but<br>
this penalty can be taken when we are in need for most optimized code.<br>
<br>
What does everyone think?<br>
Could this approach be considered as a valid mode for Clang/LLVM?<br>
<br>
Please use this post and the attached patch (it can be applied to 3.3<br>
release - clang should be inside llvm/tools folder) as a reference and<br>
not the patch for submission.<br>
<br>
Example command line:<br>
> clang -target mipsel-unknown-linux -Oz -S -fiterative-comp=3 example.c<br>
<br>
Thank you. Looking forward to hearing your comments on this.<br>
<br>
<br>
</div>
</body>
</html>