WIXLIB

PROGRAMMING LANGUAGES LABORATORY!UniversidadeFederaldeMinasGerais- ‐DepartmentofComputerScienceINTRODUCTION TO CODE ANALYSISAND OPTIMIZATION!PROGRAM ANALYSISANDOPTIMIZATION – DCC888!Fernando Magno Quintão Pereira!fernando@dcc.ufmg.brRESEARCH SCHOOLSOF THEÉCOLE NORMALE SUPÉRIEUREDELYON!

onsHardwareengineerswantefficiency

minglanguages!

OGRAMISMOREEFFICIENTACCORDINGTOAWELL- ‐DEFINEDMETRIC. – Time– Space– EnergyconsumpCon1) Isasmallerprogramalwaysfaster?2) Isafasterprogramalwaysmoreenergyefficient?

POFAMACHINE. WeunderstandprogramsviastaCcanalysistechniques. TheseanalysesarekeytoenablecodeopCmizaCons. Buttheyalsohaveotheruses:– TheyhelpustoprovecorrectnessproperCes.– Theyhelpustofindbugsinprograms.

Goal1:ProgramOpCmizaCon eittoopCmizeprograms. StrengthReducConEtc,etc,etc.#include stdio.h !#define CUBE(x) (x)*(x)*(x)!int main() {!int i 0;!main:!int x 2;!pushlint sum 0;!movlwhile (i 100) {!pushlsum CUBE(x);!sublcall}!L3:!printf("%d\n", lladdlpoplleave!ret!%ebp!%esp, %ebp!%ebx! 20, %esp!L3!%ebx! 800, 4(%esp)!%eax, (%esp)!printf! 20, %esp!%ebx!

Goal2:BugFinding �x)bugsinprograms.12345678910void read matrix(int* data,char w, char h) {char buf size w * h;if (buf size BUF SIZE) {int c0, c1;int buf[BUF SIZE];for (c0 0; c0 h; c0 ) {for (c1 0; c1 w; c1 ) {int index c0 * w c1;buf[index] ��–NullpointerdereferenceArrayout- ‐of- ecuritybuginthisprogram.Beaware:thebugistricky.

TheContentsoftheCourse Allthematerialrelatedtothiscourseisavailableon- ‐line,athep://www.dcc.ufmg.br/ fernando/classes/dcc888. gnmentClassExercisesUsefullinks Thepagealsocontainsthecoursebibliography.

TheContentsoftheCourse lableon- ‐line:Lectures1. IntroducCon2. LoopOpCmizaCons3. StaCcSingleAssignment4. SparseAnalyses5. RangeAnalysis6. SSA- ‐BasedRegisterAllocaCon7. Just- ‐in- ‐CmecompilersLabs1. IntrotoLLVM2. Compilingalanguage3. WriCngapass4. TesCng5. UsingtheAPI6. InterproceduralAnalyses

Wherewewillbe Acompilerhasthreemainparts– Thefront- ‐endiswhereparsingtakesplace.– Themiddle- ‐endiswhereopCmizaConsandanalysestakeplace.– Theback- machinecodeisgenerated.theotherphases?We shall stay here!FortranPowerPCCOBOLx86Lisp FrontEndOpCmizerBackEndARM

ThereisnoSilverBullet1. ItisimpossibletobuildtheperfectopCmizingcompiler. eCanyouprovethefirststatement?

ThereisnoSilverBullet1. ganddoesnotterminateisPleast L: goto lemisNo,otherwiseitisYes.

TheFull- ‐EmploymentTheorem1. nC. dweprovethisnewtheorem?

TheFull- ‐EmploymentTheorem1. beaprogramPxthatdoesnotterminate,suchthatB(Px) owingway:B'(P) ifP Pxthen[L:gotoL]elseB(P)

LEARNCOMPILERS?DCC888

yinparCcular turesorimproveduClizaCon." lpmakebeeerengineeringdecisionseverywhere." nce.CompileropCmizaContrainsinbig- senCaltosuccessintoday'sworld."

But ds?

WhytoLearnCompilers1. ilaContechnology.2. ofcompilers.– d,weneedthembadly." 3. unitytolearncompilaContechnology.– ects.– heCme. ldlearnaboutcompilers?

y: gcc -fdefer-pop -o test : gcc -O1 -fno-defer-pop -o test test.c!fauto-inc-dec !fcompare-elim !fcprop-registers !fdce !fdefer-pop !fdelayed-branch !fdse !fguess-branch-probability !fif-conversion2 !fif-conversion !fipa-pure-const !fipa-profile !fipa-reference !fmerge-constants!fsplit-wide-types !ftree-bit-ccp !ftree-builtin-call-dce !ftree-ccp !ftree-ch !ftree-copyrename !ftree-dce !ftree-dominator-opts !ftree-dse !ftree-forwprop !ftree-fre !ftree-phiprop !ftree-slsr !ftree-sra !ftree-pta !funit-at-a-time!

mmer,becauseIamint i read();!reusingthename'i'.Inthiswaymyprogramif (i ! EOF)!i read();!willconsumelessmemory.”printf("%d", thesequotaCons?#define MAX(X, Y) (X) (Y) ? (X) : (Y)!int max(int i, int j) { return i j ? i : j; }!

LotsofJobOpportuniCes thWorks,IBM,AMD,Mozilla,etc. ThesejobsusuallyaskforC/C experCse.WhyC/C are ngcompiler Advancedprogrammingskills.writers? Knowledgeofcompilertheoryisabigplus! Paperspublishedinthefieldwillhelpalottoo!

eedcompilaContechnology.Intel iccMozilla JaegerMonkey,IonMonkey,TraceMonkeyApple LLVMNVIDIA nvccGoogle Delvik,V8MicrosoE visualstudio,.NETVMSTMicroelectronics open64Canyouthinkaboutotherexamples?

ays,e.g.,tocreateanewback- ls,forC,C rangingfrom8- ‐bitmicrocontrollerstoCISC,RISC,DSPand256- ompanythatdevelopsanopCmizingcompilerforthex86- ,CandC compilersforhigh- mpilersforC,C ,Fortran,andAda.Thecompilerstarget32- ‐and64- ‐bitpla kaboutotherexamples?

March'13)

pic?Regards,Stephan(May'13)

CompilerKnowledgeisFun(andAwesome) programmingskillstowritethem.– Large,robustsystem,usuallycodedinahigh- ‐performancelanguage,suchasCorC ardware. Itisnotonlyprogramming.– gyoulearnedbeforeyoutookthecourse."SteveYegge :SteveYeggehasworkedatAmazonandGoogle,amongothers.

Compilers–AMicrocosmofComputerScience Algorithms:graphseverywhere,union- ‐find,dynamicprogramming ntextfreegrammars. Algebra:la ces,fixedpointtheory,GaloisConnecCons,TypeSystems strucConsets g,schedulingCanyouthinkonanythingelse? .iitm.ac.in/ krishna/cs3300/lecture1.pdf)

LIESOFTHECOMPILERWRITERDCC888

StaCcAndDynamicAnalysis Compilershavetwowaystounderstandprograms:– StaCcAnalysis– DynamicAnalysis ithoutrunningit. h?

DynamicAnalyses DynamicanalysesinvolveexecuCngtheprogram.– happenedatrunCme.Example:gprof.– – ind.– InstrumentaLon:weaugmenttheprogramwithameta- Sanitizer.

StaCcAnalyses InthiscoursewewillfocusonstaCcanalyses. beusing:– esyntaxoftheprogram.– Constraint- plicitlybytheprogramsyntax.– ,suchasprogressandpreservaCon.

DataflowAnalyses m. Manyclassicanalysesfitintothiscategory:– gaCon,availableexpressions,verybusyy x/2{x,y}y 3{ x, y }expressions,etc.{x}{x}x x - y{x}x inputAnyideaonwhatisaControlFlowGraph?{x}z x - 4x 1{}{x}var x, y, zoutput x{}{}{ x, z }z 0{x}{ x, z }x x / 2{ x, z }{ x, z }z z - 1

Constraint- ‐BasedAnalyses Constraint- heprogram'ssyntax. �ow!"y# "'#analysis,andpointeranalysis.{idy} !* dx} "(# {idy} ")# "&#{idx} !* "&#{idx} !* "&#"{idy} !* "&#!"x# "%#{idy}{idy}

TypeSystems ogram.– ses.– Theysimplifyproofsofcorrectness.– MaybesolvedviaunificaLon,ordata- Con?

TheBroadTheory ––GraphsareeverywhereLa lstrengthcompilers!

Graphs ependenceGraphsStronglyConnectedComponents– Wherearetheyused?

FixedPointTheory raCve.Howcanweprovethattheyterminate? ralgorithm andthetotalamountofinformaConisfinite Then,eventuallyouralgorithmmuststabilize.

InducConalltheway MostofourproofsarebasedoninducCon. WeusethreemaintypesofinducCon:– StructuralinducCon– InducCononderivaConrules– InducCononsizeofsyntacCcterms1) HasanyoneheardofstructuralinducCon?2) heseproofsarecorrectmechanically.

TheProgramRepresentaConZoo ifferentstaCcanalyses. ta@cSingleAssignment(SSA)formprograms.– lmosteverycompilerthatismildlyimportant.– cubic gorithmwasproposed,basedonarepresentaConcallede- ‐SSAform . omialCmesoluCon,whereasitisNP- ‐completeingeneralprograms! :TaintedFlowAnalysisone- ‐SSA- ‐FormPrograms :Trustinthelambda- ‐Calculus

OpenSourceCommunity Manyimportantcompilersarecurrentlyopensource. lerforC/C programs. industry. users. raphicsprocessingunits. ogrammingresearch.

ConferencesandJournals relatedpapers:– .75,18%)– POPL:PrinciplesofProgrammingLanguages(8.22,20%)– andOperaCngSystems(11.49,15%)– CGO:CodeGeneraConandOpCmizaCon(3.56,31%)– CC:CompilerConstrucCon(2.46,25%) –ACMTransacConsonProgrammingLanguagesandSystems.

FHISTORYOFOPTIMIZINGCOMPILERSDCC888

yvideogames,oranythingthatrequiressomesortofnon- oryofcompilers?

TheLongRoad1) Whatwerethefirstcompilers?2) Whatwerethe“firstcompilaConchallenges”?3) WhoweretheimportantpeopleincompilaCon?4) oryappearedinFrance?

TheDawnoftheFirstCompilers yfromprogrammersstartedinthe50's. nusetoday,tobecompiledbyanopCmizingcompiler. inproblems:– Parsing– CodeopCmizaCon led.Howso?

EarlyCodeOpCmizaCons introducedmanyoftheconceptsforopCmizaCon:– Controlflowgraphs– Manydataflowanalyses– AdescripConofmanydifferentprogramopCmizaCons– Interproceduraldataflowanalyses– Worklistalgorithms eIBMlabs.

TheDataflowMonotoneFramework sedonthenoConofthedataflowmonotoneframework.The inventor of the––––PropagaConofinformaConBIOS lems eismostlyknownforthedealwiththeMs- ‐DOSsystemthatinvolvedIBMandBillGates.

AbstractInterpretaCon apersincompilerresearch preta@on. cbehaviorofaprogram. itistrue.– pproachcouldtaketoolong.– terminates.– ThisapproachmaybeconservaCve,butitdoesterminate! :AbstractInterpretaCon:aUnifiedLa proximaConofFixpoints

RegisterAllocaCon ers,oneofth

Goals*of*this*Course* There*are*many*ways*to*compare*the*performance*of* programs:* – Time* – Space* – Energyconsumpon THEP RIMARYG OAL*OF*THISC OURSE*IS*TOE XPLAIN*THES TUDENT* HOW*TOT RANSFORM*AP ROGRAMA UTOMATICALLY, WHILE* PRESERVING*ITSS EMANTICS, IN*SUCH*A*WAY*THAT*THE*NEWP ROGRAM* IS*MOREE FFICIENTA CCORDING*TO*AW ELLD EFINEDM ETRIC. 1) Is*asmaller*program*