Compilers: Register Allocation Against Complex Branching/Jumps -


i've taken side interest optimizers , how work, particularly respect register allocation. have of background in writing high-level interpreters didn't bother generate efficient machine code, parts revolving around compiler construction relate parsing, constructing asts, etc. straightforward me.

as learning project, i've been trying hand @ toy compiler higher level machine-level main difference being works variables rather registers.

where i'm confused low-level optimizer parts, respect register allocation ir , how affected branching/jumps, basic of heuristic algorithms excluding advanced topics ssa , phi nodes.

basic example:

a = ... b = ... c = ... d = ... e = ... f = ... g = ...  jump_if x == 1, section1 jump_if x == 2, section2 jump_if x == 3, section3 etc  = + b - c * 2 jump end  section1: ; kinds of stuff happens here of above variables jump end  section2: ; kinds of stuff happens here of above variables jump end  section3: ; kinds of stuff happens here of above variables jump section1 ; tricky branch!!!  end:

and perhaps can throw in loopy logic , kinds of other branching make example more convoluted.

what don't understand of these branching paths might potentially make of variables above 'live' if consider them instead of each path individually.

what seems lacking me kind of stack-based block structure can have nested blocks register allocation can taken account variables referenced innermost block , outer blocks , execute register allocation heuristic separately on each block/branching path.

in higher-level ir that's more block-based, seems easier deduce branching paths because branching constrained within block, low-level ir abstracted above machine level has unconstrained branching can jump/branch on place?

most ir examples i've seen rather low-level abstractions of machine code, seem allow chaotic how our branching (ex: jump tables) in way might make difficult deduce such blocks/sections/paths.

how people typically deal problem? there algorithm , clean organization/code design can break down possible branching paths given such low-level code allows such flexible branches/jumps?

register allocation long standing problem. there have been number of research papers in area. recent popular algorithms in area ssa , linear scan register allocation.

static single assignment form (ssa) has gained popularity register allocation. idea convert program logic variable assigned once , every variable needs assigned before used. assumed there unlimited number of registers can used.

once program converted ssa form, can converted register allocation easier. can done graph coloring in polynomial time (the popular compiler llvm). pretty complex topic discuss here. recommend read couple of papers in area.

  1. efficiently computing static single assignment form , control dependence graph ron cytron, et al. 1 of pioneer in ssa area.

  2. single-pass generation of static single assignment form structured languages marc m. brandis, et al.

  3. a simple, fast dominance algorithm keith d. cooper, et al.

if don't want deal ssa intermediate step, might want take @ linear scan register allocation massimiliano poletto. greedy algorithm used in many non-llvm based compilers including v8 , jvm.


-

Comments

Post a Comment

Popular posts from this blog

apache - PHP Soap issue while content length is larger -

we have developed soap based webservice post data third party webservice. accepts 4 params. in 1 of parameters accepts xml string no size limit restriction put in place. the webservice works fine in local environment running on php 5.2 , apache2. works content length long 10 mb. in staging server running nginx , php fpm.we have updated max post size , max upload filesize in php.ini , client_max_body param in nginx.conf allow upto 50 mb. but webservice client keeps on loading in staging environment. gives 502 timeout , gives soap error. can me understand issue here?
Read more

asynchronous - Python asyncio task got bad yield -

i confused how play around asyncio module in python 3.4. have searching api search engine, , want each search request run either parallel, or asynchronously, don't have wait 1 search finish start another. here high-level searching api build objects raw search results. search engine using kind of asyncio mechanism, won't bother that. # no asyncio module used here class search(object): ... self.s = some_search_engine() ... def searching(self, *args, **kwargs): ret = {} # raw searching according args , kwargs , build wrapped results ... return ret to try async requests, wrote following test case test how can interact stuff asyncio module. # here testing script @asyncio.coroutine def handle(f, *args, **kwargs): r = yield f(*args, **kwargs) return r s = search() loop = asyncio.get_event_loop() loop.run_until_complete(handle(s.searching, arg1, arg2, ...)) loop.close() by running pytest, return runtimeerror: task got bad yield : {results s...
Read more

javascript - Complete OpenIDConnect auth when requesting via Ajax -

the normal openidconnect server works like: you go a.com/secure-resource you 302 server your browser handles , sends identity server you login there it sends a.com via post you logged in on a.com , a.com/secure-resource on browser. however have scenario i'm trying solve need help. the user logged in on idserver the user logged in on a.com the user not logged in on b.com we need send ajax call web server b.com (from domain a.com ) b.com configured use openidconnect. but because request b.com via ajax, user cannot redirected idserver. (all in response 302 ) we can go ahead , handle 302 via ajax (i'm still not sure whether work, security-wise). but is there scenario in identityserver/openidconnect designed these situations? with identityserver in scenario setup server b.com use bearer token authentication, need use access token provided a.com in headers of ajax call $.ajax({ url: 'http://b.com', headers: { ...
Read more