Re: McCabe package for Ada?

[sparky!sparky!dwb@uunet.uu.net (David Boyd)]

In article <1993Jun3.194721.23315@vertex.com>, jaime@vertex.com (Jaime Cordera)
writes:

|> >something might be wrong.  In any case, this type of situation is again
|> >very tough to detect automatically.  About the only thing that can be done
|>  ^^^^ ^^^^^ ^^ ^^^^^^ ^^^^^^^^^^^^^
|> 
|> I'm not sure I understand the situation completely, (or the metrics)
|> but in the example above one of the problems was a lack of locality of 
|> reference. This is rather routinely calculated in optimizing compilers 
|> (called the use-definition tree). They want to know when they do and don't 
|> need to have space for a variable (especially when the variable lives in 
|> a register).
|> 
	What I was refering to that was hard to detect was what variables
where of significance in caclulating the cyclomatic complexity with reguard
to data.  Simple variables such a loop counters, and indexes would contribute
significantly to the number of paths but in the example provided would not
be significant.

	The "Locality of Reference" measure that Jamie mentions was the concept
 I was
referring to in a subsequent post.  Basically the metric
would look a the distance between references by counting the number of
nodes in the flow graph between references.  One could use this number to
look at an average locality,  the number of references which exceed a 
threshold.  Since straight line code on a flow graph is a would map to a single
node a variable referenced on opposite ends of the block would have a locality
metric of one.  This would be reasonable since the real problem is
following references to variables through complex loops and branches.  A 
standard for measuring the distance between references when there is complex
logic involved  since there would be multiple paths with different links
possible.  I would reccomend that the locality metric use the longest path
since in practice that is the path which is hardest to trace through.

	Jaime is very correct about compilers doing this type of calculation
all the time.  By looking at a locality measure like is being discussed one
could determine not only when situations such a what Wes described occure, 
but also would get a general idea (it would only be general since many other
factors are involved including hardware) of how well a given piece of
software could be optimized.  It would be interesting to do a study where
pieces of poorly written unstructure code and well written structured code whic
h
do the same things where run through optimizers.  Then look to see
if there is statistical coorrelations between certain metrics (like McCabe's
and the locality of reference we are discussing) and how well the resulting
object code is optimized (i.e. size and speed).  Since most good compilers
eliminate things like dead code and extranous assignments some degree
of the unstructuredness would be optimized out.  
the same
not be a problem 
-- 
David W. Boyd	             UUCP:     uunet!sparky!dwb
Sterling Software IMD        INTERNET: dwb@IMD.Sterling.COM
1404 Ft. Crook Rd. South     Phone:    (402) 291-8300 
Bellevue, NE. 68005-2969     FAX:      (402) 291-4362