<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Other people have already addressed the specific case of this example, but, in general, the passes use by the opt tool in -std-compile-opts are considered to be a good set for unit-at-a-time optimization, and similarly the ones used in llvm-ld are considered good (in addition to the single-unit ones) for whole-program optimization.<div><br></div><div>Also note that predsimplify is incomplete and has some known bugs. I would recommend against using it.</div><div><br></div><div>--Owen</div><div><br><div><html>On Mar 31, 2008, at 6:46 PM, Bobby Powers wrote:</html><br class="Apple-interchange-newline"><blockquote type="cite">Hello, I'm working on using the LLVM JIT for a little project of mine, amazing work first off! I have a question about optimization passes. I initially have this function I've created, in python it looks like this:<div> <br></div><div><span class="Apple-style-span" style="font-family: Verdana; "><pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><span class="n"><span class="Apple-style-span" style="font-size: small;">OS_end</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="o" style="font-weight: bold; "><span class="Apple-style-span" style="font-size: small;">=</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="mf" style="color: rgb(0, 153, 153); "><span class="Apple-style-span" style="font-size: small;">50</span></span><span class=""><span class="Apple-style-span" style="font-size: small;">
</span></span><span class="n"><span class="Apple-style-span" style="font-size: small;">OS_start</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="o" style="font-weight: bold; "><span class="Apple-style-span" style="font-size: small;">=</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="mf" style="color: rgb(0, 153, 153); "><span class="Apple-style-span" style="font-size: small;">0</span></span><span class=""><span class="Apple-style-span" style="font-size: small;">
</span></span><span class="n"><span class="Apple-style-span" style="font-size: small;">OS_timestep</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="o" style="font-weight: bold; "><span class="Apple-style-span" style="font-size: small;">=</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="mf" style="color: rgb(0, 153, 153); "><span class="Apple-style-span" style="font-size: small;">1</span></span><span class=""><span class="Apple-style-span" style="font-size: small;">
</span></span><span class="n"><span class="Apple-style-span" style="font-size: small;">birth_rate</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="o" style="font-weight: bold; "><span class="Apple-style-span" style="font-size: small;">=</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="o" style="font-weight: bold; "><span class="Apple-style-span" style="font-size: small;">.</span></span><span class="mf" style="color: rgb(0, 153, 153); "><span class="Apple-style-span" style="font-size: small;">3</span></span><span class=""><span class="Apple-style-span" style="font-size: small;">
</span></span><span class="n"><span class="Apple-style-span" style="font-size: small;">population</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="o" style="font-weight: bold; "><span class="Apple-style-span" style="font-size: small;">=</span></span><span class=""><span class="Apple-style-span" style="font-size: small;"> </span></span><span class="mf" style="color: rgb(0, 153, 153); "><span class="Apple-style-span" style="font-size: small;">30.0</span></span><span class=""><span class="Apple-style-span" style="font-size: small;">
</span></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">
</span></font></span><span class="k" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">for</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">time</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="ow" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">in</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="nb" style="color: rgb(153, 153, 153); "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">range</span></font></span><span class="p"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">(</span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">OS_start</span></font></span><span class="p"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">,</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">OS_end</span></font></span><span class="p"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">,</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">OS_timestep</span></font></span><span class="p"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">):</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">
</span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">births</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">=</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">birth_rate</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">*</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">population</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">
</span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">deaths</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">=</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="mf" style="color: rgb(0, 153, 153); "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">0.1</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">*</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">population</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">
</span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">population_NEXT</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">=</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">population</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">+</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">births</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">-</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">deaths</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">
</span></font></span><span class="c" style="color: rgb(153, 153, 136); font-style: italic; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">#generally put print statements here</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">
</span></font></span><span class="c" style="color: rgb(153, 153, 136); font-style: italic; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">#updating stocks</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">
</span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">population</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="o" style="font-weight: bold; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">=</span></font></span><span class=""><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;"> </span></font></span><span class="n"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">population_NEXT</span></font></span></pre> <pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><br></pre><pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><font class="Apple-style-span" face="arial, sans-serif">Then I can turn it into LLVM IR:</font></pre><pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><font class="Apple-style-span" face="arial" size="3"><span class="Apple-style-span" style="font-size: 13px;"><br></span></font></pre><pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">define void @simulate() {
entry:
%time = alloca double ; <double*> [#uses=4]
%population_next = alloca double ; <double*> [#uses=2]
%population = alloca double ; <double*> [#uses=5]
%net_change = alloca double ; <double*> [#uses=2]
%deaths = alloca double ; <double*> [#uses=2]
%births = alloca double ; <double*> [#uses=2]
%birth_rate = alloca double ; <double*> [#uses=2]
%OS_timestep = alloca double ; <double*> [#uses=2]
%OS_start = alloca double ; <double*> [#uses=2]
%OS_end = alloca double ; <double*> [#uses=2]
store double 5.000000e+01, double* %OS_end
store double 0.000000e+00, double* %OS_start
store double 1.000000e+00, double* %OS_timestep
store double 3.000000e-01, double* %birth_rate
store double 3.000000e+01, double* %population
%OS_start1 = load double* %OS_start ; <double> [#uses=1]
store double %OS_start1, double* %time
br label %forcond
forcond: ; preds = %forinc, %entry
%time2 = load double* %time ; <double> [#uses=1]
%OS_end3 = load double* %OS_end ; <double> [#uses=1]
%forcond4 = fcmp olt double %time2, %OS_end3 ; <i1> [#uses=1]
br i1 %forcond4, label %forbody, label %forafter
forbody: ; preds = %forcond
%birth_rate5 = load double* %birth_rate ; <double> [#uses=1]
%population6 = load double* %population ; <double> [#uses=1]
%multmp = mul double %birth_rate5, %population6 ; <double> [#uses=1]
store double %multmp, double* %births
%population7 = load double* %population ; <double> [#uses=1]
%multmp8 = mul double 1.000000e-01, %population7 ; <double> [#uses=1]
store double %multmp8, double* %deaths
%births9 = load double* %births ; <double> [#uses=1]
%deaths10 = load double* %deaths ; <double> [#uses=1]
%subtmp = sub double %births9, %deaths10 ; <double> [#uses=1]
store double %subtmp, double* %net_change
%population11 = load double* %population ; <double> [#uses=1]
%net_change12 = load double* %net_change ; <double> [#uses=1]
%addtmp = add double %population11, %net_change12 ; <double> [#uses=1]
store double %addtmp, double* %population_next
br label %updatestocks
updatestocks: ; preds = %forbody
%population_next13 = load double* %population_next ; <double> [#uses=1]
store double %population_next13, double* %population
br label %forinc
forinc: ; preds = %updatestocks
%time14 = load double* %time ; <double> [#uses=1]
%OS_timestep15 = load double* %OS_timestep ; <double> [#uses=1]
%new_time = add double %time14, %OS_timestep15 ; <double> [#uses=1]
store double %new_time, double* %time
br label %forcond
forafter: ; preds = %forcond
ret void
}
</span></font></pre><div><font class="Apple-style-span" face="'courier new'"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><font class="Apple-style-span" face="'courier new'"><br></font></pre><pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><font class="Apple-style-span" face="arial" size="3"><span class="Apple-style-span" style="font-size: 13px; ">And then I run the optimizations from the Kaleidoscope tutorial (mem2reg, predsimplify, instcombine, reassociate, gvn, simplifycfg) and get the following:</span></font></pre> <pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><font class="Apple-style-span" face="arial" size="3"><span class="Apple-style-span" style="font-size: 13px;"><br></span></font></pre><pre style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; background-image: initial; background-repeat: initial; background-attachment: initial; -webkit-background-clip: initial; -webkit-background-origin: initial; background-color: rgb(255, 255, 255); background-position: initial initial; "><font class="Apple-style-span" face="arial" size="3"><span class="Apple-style-span" style="font-size: 13px;"><font class="Apple-style-span" face="'courier new', monospace"><span class="Apple-style-span" style="font-size: small;">define void @simulate() {
entry:
br label %forcond
forcond: ; preds = %forbody, %entry
%population.0 = phi double [ 3.000000e+01, %entry ], [ %addtmp, %forbody ] ; <double> [#uses=3]
%time.0 = phi double [ 0.000000e+00, %entry ], [ %new_time, %forbody ] ; <double> [#uses=2]
%forcond4 = fcmp olt double %time.0, 5.000000e+01 ; <i1> [#uses=1]
br i1 %forcond4, label %forbody, label %forafter
forbody: ; preds = %forcond
%multmp = mul double %population.0, 3.000000e-01 ; <double> [#uses=1]
%multmp8 = mul double %population.0, 1.000000e-01 ; <double> [#uses=1]
%subtmp = sub double %multmp, %multmp8 ; <double> [#uses=1]
%addtmp = add double %population.0, %subtmp ; <double> [#uses=1]
%new_time = add double %time.0, 1.000000e+00 ; <double> [#uses=1]
br label %forcond
forafter: ; preds = %forcond
ret void
}</span></font>
</span></font></pre><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre; "><br></span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">The thing is, in forbody it is still doing:</span></font></div> <div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">subtmp = population + (population * .3) - (population * .1)</span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;"><br> </span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">ideally I would love to see it reduced to:</span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">subtmp = 1.2 * population</span></font></div> <div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;"><br> </span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">I've played around with adding a bunch of optimizations that sound<font class="Apple-style-span" face="arial, sans-serif"> good from [</font><span class="Apple-style-span" style="white-space: normal; font-family: Verdana; "><font class="Apple-style-span" face="arial, sans-serif"><a href="http://www.llvm.org/docs/Passes.html">http://www.llvm.org/docs/Passes.html</a></font><span class="Apple-style-span" style="white-space: pre; "><font class="Apple-style-span" face="arial, sans-serif">], but I must admit I'm a bit over my head here. Doe</font></span><span class="Apple-style-span" style="font-family: arial; white-space: pre; ">s anyone have any suggestions? Am I missing passes, do I need to restructure the IR, or am I missing some concept?</span></span></span></font></div> <div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;"><br></span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">thanks! (keep up the amazing work)</span></font></div> <div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">yours,</span></font></div><div><font class="Apple-style-span" face="arial"><span class="Apple-style-span" style="white-space: pre;">Bobby Powers</span></font></div> </span></div> _______________________________________________<br>LLVM Developers mailing list<br>LLVMdev@cs.uiuc.edu <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></div></body></html>