static analysis - How do you include subroutine calls in a control flow graph? -

-

i idea of control flow graph; involves nodes basic blocks (sequences of operations occur), connected edges represent jumps.

but how represent subroutine call?

if have 2 functions this:

int tweedledee(void) {     int x = 16;     return x + do_something(); }  int tweedledum(int n) {     if (n < 0)        return n;     else        return n + do_something(); }

with both functions calling do_something(), need way allow jump block in tweedledee do_something , jump tweedledee, , jump block in tweedledum do_something , tweedledum, there's never jump tweedledee do_something , tweedledum. (or tweedledum → do_something → tweedledee) seems plain directed graph wouldn't suffice define these relationships... maybe i'm missing something.

procedures make cfgs , static analysis in general quite complicated. there different approaches representing routine calls in control flow graphs.

one first , common solution create cfg each routine, , split "call nodes" (the basic block corresponding "call do_something()" in tweedledee example) 2 nodes, actual call block c , block r writing return value.

an edge (normally of special type) inserted between c , initial block of routine being called, , 1 between end block of routine being called , r. simple example:

void foo() { int x = bar(); } int bar() { return 1; }

might transformed to:

[init::foo] ==> [call bar()]  [x = retval(bar())] ==> [end::foo]                      ||            /\                      \/            ||                 [init::bar] ==> [ret = 1 (end::bar)]

if there call bar(), e.g. routine 

void foo2() { int y = bar(); }

then following graph might result:

 [init::foo] ==> [call bar()]  [x = retval(bar())] ==> [end::foo]                      ||            /\                      \/            ||                 [init::bar] ==> [ret = 1 (end::bar)]                      /\            ||                      ||            \/  [init::foo2]==> [call bar()]  [x = retval(bar())] ==> [end::foo2]

the problem here: there paths in graph (e.g. init::foo ==> call bar() ==> init::bar ==> ret = 1 ==> x = retval(bar()) ==> end::foo2) make no sense in program. might mean wondering whether "plain directed graph" suffices. there different approaches problem, e.g.: make copies of routine (here bar) each invocation of it. helps if there no real recursion, , expensive in general. static analysis useful "overapproximate" number of paths using fixed number of such copies.

the slides interprocedural analysis lecture notes (stephen chong) seem introduction. there quite books constructing such graphs, e.g. principles of program analysis nielson et al.


Comments

Post a Comment

Popular posts from this blog

python - No exponential form of the z-axis in matplotlib-3D-plots -

-
Image
i have similar problem described in how prevent numbers being changed exponential form in python matplotlib figure : i don't want (in special case) weird scientific formatting of axis. problem different have problem @ z -axis. 2-d plots can use ax.get_yaxis().get_major_formatter().set_useoffset(false) . , there no function ax.get_zaxis() what use format z -axis same way? edit: example: from mpl_toolkits.mplot3d import axes3d import numpy np import sys import matplotlib import matplotlib.pyplot pyplot def func(xi, ti): res = 10e3 + np.cos(ti) * np.sin(xi) return res if __name__ == '__main__': timespacing = 20 timestart = 0 timeend = 1 time = np.linspace(timestart, timeend, timespacing) widthspacing = 50 widthstart = 0 widthend = 3 width = np.linspace(widthstart, widthend, widthspacing) reslist = [] matplotlib.rcparams['legend.fontsize'] = 10 fig = pyplot.figure() ax = fig.gca(projection = '3d...
Read more

php - Best Light server (Linux + Web server + Database) for Raspberry Pi -

-
i install web server database on raspberry pi (little computer). computer has 1gb ram. i want know best combination: linux distribution , web server , dbms run local server multiple users minimal latency, use php on server. , best settings performance , not have bugs (memory usage, disable plugin, disable service, etc)? i thought light debian , lighttpd server , sqlite database. solution? i think lighttpd + sqlite great choice. linux distro, debian @ centos or tiny core linux , although i'm not sure of compatibility pi. obviously, can't go wrong raspbian if want use in production , more stable performance, few more pi's , set them in cluster .
Read more

c# - "Newtonsoft.Json.JsonSerializationException unable to find constructor to use for types" error when deserializing class -

-
i developing app in xamarin android. have splash screen serialize class , pass mainactivity using intent . when try deserialize in mainactivity error message : "serializationexception unable find constructor use types" serialization : void loaddata() { currency currency = new currency(this); intent = new intent(this, typeof(mainactivity)); intent.putextra("currency", newtonsoft.json.jsonconvert.serializeobject(currency)); startactivity(intent); } deserialization : cur = newtonsoft.json.jsonconvert.deserializeobject<currency> (intent.getstringextra("currency")); // error here class constructor : public currency(context context) { thiscontext = context; } i began experiencing problem after added parameter context context constructor. has caused this? how can solve it? possible serialize/deserialize class has parameters? you need have empty constructor in currency class in order deserialize it. ...
Read more