[ICI] new static program features

[JeremySinger]

Hi Grigori, Mircea,

I have been investigating the use of classical software metrics as
static program features. In case these additional features are useful
to other members of the ICI community, I attach my code (cut-n-paste
into featlstn.P) below.

Best regards,
Jeremy

----

%% Software metrics features for GCC-ICI static features
%% add this code to the featlstn.P file.
%% Jeremy Singer
%% Nov 2009
%% jsi...@cs.man.ac.uk

%% CYCLOMATIC COMPLEXITY
%% N == number of return instrs in fn
%% N1 == number of cond instrs in fn
%% N2 == N1-N
%% N3 == N2+2. definition of cyclomatic complexity from:
%% http://en.wikipedia.org/wiki/Cyclomatic_complexity
ft(ft56,N3):-findall(E,stmt_code(E,gimple_return),L),
count_lst(L,N),
findall(E1, stmt_code(E1,gimple_cond),L1),
count_lst(L1,N1),
N2 is N1-N,
N3 is N2+2.

%% @jsinger addition
%% HALSTEAD's METRICS
%% described at
%% http://en.wikipedia.org/wiki/Halstead_complexity_measures

%% HN2 is total number of operands (Halstead N2)
ft(ft57,HN2):-findall(E,expr_var(E,_),L),
count_lst(L,HN2).

%% Hn2 is number of distinct operands (Halstead n2)
ft(ft58,Hn2):-findall(V,var_p(V),L),
count_lst(L,Hn2).

%% N is num var defs (should be == Halstead n2 or Halstead N2?)
ft(ft59,N):-findall(E,expr_code(E,var_decl),L),
count_lst(L,N).

%% HN1 is total number of operators (Halstead N1) (approx due to
abstraction)
ft(ft60,HN1):-findall(E,expr_code(E,_),L),
count_lst(L,HN1).

%% Hn1 is number of distinct operators (Halstead n1) (approx due to
abstractn)
ft(ft61,Hn1):-findall(C,expr_code(_,C),L),
sort(L,S),
count_lst(S,Hn1).


%% approx of Halstead difficulty D == Hn1/2 * (HN2 / Hn2)
%% (NB uses the aver routine to avoid problems with 0 divisor in
%% computation of HN2/Hn2)
ft(ft62, D):-findall(C,expr_code(_,C),L1),
sort(L1,S),
count_lst(S,Hn1),
findall(V,var_p(V),L),
count_lst(L,Hn2),
findall(E,expr_var(E,_),L2),
count_lst(L2,HN2),
aver(Hn2,HN2,Y),
X is Hn1/2,
D is X*Y.

%% approx of Halstead volume
%% volume == HN *log_2(Hn)
%% where HN == HN1+HN2
%% and Hn == Hn1+Hn2
ft(ft63,Volume):-findall(E,expr_code(E,_),L),
count_lst(L,HN1),
findall(C,expr_code(_,C),L1),
sort(L1,S),
count_lst(S,Hn1),
findall(E1,expr_var(E1,_),L2),
count_lst(L2,HN2),
findall(V,var_p(V),L3),
count_lst(L3,Hn2),
HN is HN1+HN2,
Hn is Hn1+Hn2,
Logterm is log10(Hn),
Logterm2 is Logterm*3.32,
Volume is HN*Logterm2.

%% approx of Halstead effort, which
%% == Difficulty * Volume
ft(ft64,Effort):-findall(E,expr_code(E,_),L),
count_lst(L,HN1),
findall(C,expr_code(_,C),L1),
sort(L1,S),
count_lst(S,Hn1),
findall(E1,expr_var(E1,_),L2),
count_lst(L2,HN2),
findall(V,var_p(V),L3),
count_lst(L3,Hn2),
HN is HN1+HN2,
Hn is Hn1+Hn2,
Logterm is log10(Hn),
Logterm2 is Logterm*3.32,
V is HN*Logterm2,
aver(Hn2,HN2,Y),
X is Hn1/2,
D is X*Y,
Effort is D*V.

---

[Grigori Fursin]

Thanks, Jeremy.

I just created a page on cTuning where everyone can add their own extensions to the feature
extractor:
http://ctuning.org/wiki/index.php/CTools:MilepostGCC:StaticFeatures:Extensions
http://ctuning.org/wiki/index.php/CTools:MilepostGCC:StaticFeatures

You can update it, upload your featlstn.P there and describe it more ...

Your additions look interesting (and that is one of the nice things about
the feature extractor that Mircea wrote is the ability to extend it easily)
but it would be interesting to see the evaluation of those features, i.e.
if they help classify programs and improve the predictions in comparison
with the released MILEPOST GCC. But maybe I will see that in one of your
new submissions ;) ?..

Thanks again for sharing this code with us.

By the way, Mircea continues working on a considerable extension
to this feature extractor but it will still take some time and as soon
as we have some new results, we will share the new code with the community ...

Take care,
Grigori