La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | Thesee |
Nombre de lectures | 78 |
Langue | Français |
Poids de l'ouvrage | 1 Mo |
Extrait
CONSERVACNAMPProfesseurTOIREhe,NAPr?sidenTIONALUnDESDARPTSXaETdeM?TIERSProfesseur,?coleENSIDoCNAMctoraleDirecteurEDITEDominiqueLABORAChristineTOIRE:CEDRIC,rec?TquCNRSipAesaris-SudCPR1etMa?treOCdeTH?SETEURSpr?senTEt?erecparDE:honoraire,Beno?tURUnivOBILLARDJURsoutenOueDirecteurlehe,:D30AlainNohercvWERRAemEPFLbreLIN-MOHRING2010ersit?pSandrineourersit?obtenirCatherineleSOUTIFgradeedeMa?tre:conf?rences,DoRAPPORcteur:duARConservAlainatoiredeNationalhercdesCNRSArtsWERRAetProfesseurM?tiersEPFLSpA?cialit?LIN-MOHRING:Professeur,Informatiqueersit?VERIFICAaris-SudTIONYFLERORMELLEYETvierOPTIMISAdeTIONhercDEINRIA,L'ALLOCAtTIONARDEEREGISTREDirecteurSrecTH?SEhe,dirig?eDEpDominiquearhonoraire,:PBLAZYUSandrineChristineProfesseur,UnivUnivPersit?BLAZYRennesProfesseur,1ivDUBOISRennesCatherineDUBOISProfesseur,Professeur,ENIESI?ricIEdSOUTIFconf?rences,?ric
tel-00562318, version 1 - 3 Feb 2011tel-00562318, version 1 - 3 Feb 2011RemerciementsIlestmontd?lisationtanCosta,tpasdedepprisersonnesnaturellemenqueilsjejugertiensuer?monremercier,ntanptn?deBlazypaccord?ersonnesansquierram'onsitm?meacfaitcompagn?tdedevmeslpremiersationpastrois?traiter.aujourd'hetui,tanquelquessjoursSoutifarvleuranvtplaisir.lacsoutenance.m'aJ'aineicidelaacsongehancehercdepasphe.ouvquioirdelesaremercierspet,pm?medoutesiqjeaillersaisdequequemesSandrinemotsXasonvtth?seinaptesheminemen?plustranscriredemesubsenletim'ametenid?ests,genj'espp?refanquec?t?cesouvquelquesencadranlignesDarte,exprimeronaultl'honneurauaux.mieuxqceaisque3jeetdoisan?jecconhacunlad'eux.e,Ilmesestletoutrecd'abtiensordremercierlestpdeersonnesdsansuquilacettedeth?sein'auraitenjamaismoi.vualemajour,lemeseenseignantrats,tdevr?sulteneninuslesensuiteeumesdonccoll?gues,deDubrecLerohercSoutifhe.imagIsujetlsj'apponCetmesu?metfairecadrand?couvrirSandrinetCatherineaimeretdesourdomainesqu'ilsdonptojetn'imaginaisvl'existenceconanceetj'aisusciteroser.endonmoitleego?tmoideCesla?recfuthercnehe.simplemenIlerm'estJeimptossibleDedeChristineneMohringpasoirremercierlireCatherinetraDubmanois,pasqui'illan'apremi?rebm'apr?cieusesfaitmod?couvrirg?om?triquelaqui,spv?cicationtformellequeetnela?preutinvdanserecdehprogramme,m'aainfairesipremiersquedansSandrinemondeBlazyla,hercJulienJeF?galemenorest,?XaceuxvieronUrbainfa?onn?etsujetPierrestageCourtieunqui'?tudes,m'onentptransmisrunesuitepartsujetdeth?se,leur?csaavemoirtdansourceIldomaine.'yJeaucundoisquetoutmotivautanettplaisirremercieruMarie-Christinej'aiCosta,?AlainvFduranacesyansetetmonErict?r?tSoutif,ourpprobl?mesourj'aim'a?vMercioir?initi?Blazy?Marie-ChristinecetteCatherinemervois,eillevierqu'estylaEricth?oried'adesoirgraphes,iAlainceBillionnet,deSourourqueEr?cielloumi,t.ChristophecPicouleautetconduitFtr?d?ricremercierRoupin,particuli?remenpmeouren-m'atsvth?se,oirefait,d?couvrirDlesoispassionnanErictespettoutmtempsultiplesm'onfacettesaccord?,deourlavreicadmirablemenhercguid?heaopoir?leurrationauxnelle.queJepumepropdoisLa?galementillessettdeonremercierfaitceuxreuvquiam'onectestconduittastique.?troisapass?svleursoirsl'enunvieJedepdevaisenirtcr?vhercmeilleursheur.ts.LeremerciepremierhaleureusemenfutAlainJean-MarcDominiqueMotaWqui,etaPvin-ecdeCatherinevDubfaitois,dem'aetenmescavdCer?uscritlorsseraitd'uncestageupestortanjetvsurpasla?n?ci?formalisationleursderemarques.la
tel-00562318, version 1 - 3 Feb 2011REMERCIEvournousMENTSousMercimerci?parfaitemenXaGueuvierdeLeroenypas,bquihmequfaitTitangelet.plaisirferaisdevupr?siderpass?letjuryterminerdedecettec?t?s.th?se,conetestaetvccupec,quimoj'aippuassezpartagerdoisdestoutdiscuctoranssionsmtoujoursvtr?stsinMatthieut?ressann'oubtes,estainsisaqueecdemomensucculenuts?mezze.sous-enJelesremercstupioneptousilmesvcoll?gues:desMimi,?quipOrz,esQueConcaeptionjeetousPr'aioremerciergrm?re,ammationpRpaisonn?particuli?reescoll?guesetqueOptimisationpCombinatoirsemaisdequilabtsoratoiretCEAm?lie,DRICramppNicolas.our?videmmentousynah,lesenbr?dactiononscmomenatsj'aipass?sbensemJ'aibleuet?toutesalesetdiscussionslesenricd'uhissanersationtesortemenquesonnousts.aceuxvbionsmeeuesleslorseek-ends,dear?unionsled'?quipquiecesouDraZel,sMad,implemenatOlz,auStarmanjourYlebjour.tsVecousourcotoheureuxyoirermainauraje?t?deupndeuxplaisirvie,dquieetcquihaque4jour.ens?eJeaussiremercieptoutmesautandottstousj'aimesunenseignaneutsoinetsouvcoll?guest,deal'ENSIecIE,j'aitropd'excellennmomeno?galemenm:breux?pH?l?ne,ourT?treoncit?s.etIlJeenliesesttcertainsZaquiquionvtuedulamedesuppth?seorterhezpetlusvsouvquienpass?ttr?squeonslests.autresappris:eajecoremerciepMatthieusesCarlier,SPicnicfacult?(aussicomprendreconnanalyserutsousmoindresletenduspseudonneymevdeetPierre-Nicolas),compStarmants(aussiumainsconntu?ansousIlleennpseudonquiymetWilliam)enetouluVincensuptorterdesoirslawbcaronnn'yepasheutramaileuorequotidiennecr?neauxquiAnne-So,r?gnaitElsa,dans,notreMatthieu,buNabrealuNemi,.Osi,J'aiPicnic,pass?TiTi,deettr?sass.bdeonsonsmomenmentspass?savvvecpvlesquelsous,suissidenomouvbreuxvqu'ilremercieresttenaninconcevEnn,ablendepaslesmots?nfortsum?rer.ourNullesdoutefemmesquemaceman'est?qjeutout,eC?line,leourd?bujet.tout.Une
tel-00562318, version 1 - 3 Feb 2011REMERCIEMENTS5
tel-00562318, version 1 - 3 Feb 2011REMERCIEMENTS6
tel-00562318, version 1 - 3 Feb 2011R?sum?LaprisedeCoelleslaconsciencealgorithmique,gde?nd'allo?raformalisationslCompCert.eladetronsl'impc?donsortanceisationdeprixvterf?rence-anit?s,?riervplusdonscrupuleusemen?r?estdelescetteprogrammeslaaparengendr?Counl'Iteratedeutilisateurcroissancevconsi'e-d?rableformdesfonctionneleortsvdet?gr?evdeux?ricationleursformelledededonprogrammecdurandutoptimisancettecompilationderni?requed?cennie.qN?anmoins,d'alloleraphcovdealgorithmesqu'ex?cuteparl'ordinateur,C),ouermettancoedefacilemenex?cutable,cetn'esttuellepasgler?exionscotiondesous?crit?ratifsparlaleimpland?vCeloppypeur,onsouterm?diairescoSdepropsource.deLal'unevl'allo?ricationleformellededetcompilateurscompteest7donceauxunpcompl?menetNousindispd'abensablet?elaad?quatvtion?ricationdededecoNousde?source.formelleL'uned'undesplust?cdehesdelesCoalescingplusd'unecomplexescelui-cide?compilationeuestdul'allod'implancationsadeteregistres.auC'est?vlorsertedeacelle-cimique.quetledecompilateursad?cidegraphesdelalapuremenfa?od'algorithmesndedonterminaisontdelesfonctionnelle.vformellemenaderi?t?aunbdulesaduiteprogrammetationssonprogratlastoetcpkde?escentionm?moirefduranoptimisationstdsondeex?cution.l'impactLafortmdu?moireCescompmonortedesdeuxtenantparam?tresypd'inesd?nirdnouvealgorithmescontsteneursour:?taplesderegistres,.zonesmond'acc?stoutrapide,ordpr?senl'assistants?enpreuvnomCobreestlimit?,?etformalisa-lad'algorithmespile,cationderegistrescapacit?colorationsuppgos?ees.susamenprotainsiimplaortan?ricationteenpqourdesh?blesergerclassiquestoutescationlesregistresvcolorationariablesgraphes,d'unRegisterprogramme,(IRmaetig?n?ral-sde?plaquelletl'acc?sunestpbienfamiliplusrlensyst?met.qLeterbuttdeproprel'alloariancationdedealgorithmeregistresseulestd'unedeentirerpaudmieuxcacit?plartiorithdeCeslan?cessitenrapidit?desdesautourregistres,lacaraliune-allodescationd'indederegistrestraductiondeformebtonnelequalit?imppeteutl'ecacit?conduirela?etunecorrectionam?liorationcettesignicativersioneNotredutationtempstd'ex?cution?ri?edul'IRprogramme.aLeinmo?d?leprototleepluscompilateurconnNousuvdeensul'allo?tudi?cationrepr?sendeinregistresderepmmes,osetsuformerSA,laexploit?colorationpropri?t?sdeourgrapheoserd'innouvterf?rence-anit?.approDanshescetter?soluth?se,optimalel'oblajectifusion,estdesdoubleop:lorsd'uneepartcationvregistres?riertformelle-estmenplustsurcertainsqualit?algorithmescoconncompil?.usapprod'allohescationtrendequeregistrescrit?resparfusioncolorationtdedegraphe,globauxetgraphed'autreterf?rence-anit?,part
tel-00562318, version 1 - 3 Feb 2011R?SUM?telsquetallo?ricationsates.largeurcolorationd'arbre,oten-ouvrenptcl?sladevgraphes,oie8vtiellemenersplusderformaneMotsnouv:ellescationm?thoregistres,desdedevr?solutionformellep
tel-00562318, version 1 - 3 Feb 2011Tabledes.Structure.mati?res.1deIn.t31r37oinduction.15.1.1.L'allo.cation1.3de.registres........Program.scan.........cation.graphes.....F.cation............................17.1.1.1proL'allo.cation.de.registresV?ricationen.quelqud'algorithmese.s.mots........l'allo.train.......TL.....Dur?e......17ec1.1.2.Quatre.comp.osandetes.de.l'allo.cation.d.e4registres........tra...........1.2.5.CompCert..19.1.1.3.Allo.cation.de.registres29pard'algorithmescoregistresl.oV?ricationrationth?oriede.graphe..tributions.................34.ts.de21Les1.1.4deLaregistrescinqui?me.comp.osan.te.:37leprogrammesd?coupage.des.d.ur?es.de.vie37.vie..........23.1.1.52.2Allod'allocation.de.registres.et.form.e.SSA2.2.1.d'in.......42.lin?aire.............2.2.3..........23.1.1.6.Allo.cation2.2.4deauxregistres.et.d?co.u.page.extr?me....9.....29.Le.jet............25.1.1.7.T.rois.probl?mes,.trois.solutions....1.2.6.formelle.d'allo.de.......1.2.7.formelle.de.des.......33.Con........2.5.1.2.V?rication.formelle.et.allo.ca.ti.o.n.de.registres....2.ondemen.de.cation.registres.2.1.con.tes.l'allo.de............26.1.2.1.Quelques.m?tho.des2.1.1formellesdes.R.......................2.1.2.de.et.terf?rences............26.1.2.2.Le.syst?me.Co.q39.T.hniques.cation.registres.......................41.Coloration.graphe.terf?rence-anit?...............2.2.2.mation....2.7.1.2.3.V.alidation.a.p.osteriori........3.Linear.................................45.Autres.v....28.1.2.4.Compara.i.son.v.?rication/v.alidation.par.l'exemple........45.
tel-00562318, version 1 - 3 Feb 2011TABLEDESMA..3.2TI?RES.2.3.Allo.cation.d.e.registres.par.coloration.dedesgraphe..................Suppression.es.........F.d46anit?s2.3.1.Le.vidagede...3.1.1.........terf?rence-anit?.v...dication.........sommets.....d'implan...structure...tre...graphes.........li?s.......V?rication46.2.3.2.Algorithme.de.vidage.de.Chaitin....Les.........base...68.d.....Les.............7047?2.3.3.LeFd?coupagenedes.dur?es71deterf?rence-anit?vie..................73.implan.....s.............3.6.2.un48.2.3.4usionLaanit?fusion..3.7........