My Simpler Dead-code Remover

Question

I am doing a stimulation of dead-code remover in a very simpler manner.

For that my Idea is to,

Step 1: Read the input C-Program line by line and store it in a doubly linked-list or Array.(Since deletion and insertion will be easier than in file operations).

Doubt:Is my approach correct? If so, How to minimize traversing a Linked-List each time.

Step 2: Analyzing of the read strings will be done in parallel, and tables are created to maintain variables names and their details, functions and their calls,etc.,

Step 3: Searching will be done for each entries in the variable table, and the variables will be replaced by its that time's value(as it has). (E.g.)

i=0;
if(i==3) will be replaced by if(0==3).

But on situation like..

get(a);
i=a;
if(i){} 

here,'i' will not be replaced since it depends on another variable. 'a' will not be replaced since it depends on user input.

Doubt: if user input is, if(5*5+6){print hello;} , it surely will be unnecessary check. How can i solve this expression to simplify the code as { print hello; }

Step 4: Strings will be searched for if(0),while(0) etc., and using stack, the action block is removed. if(0){//this will be removed*/}

Step 5:(E.g) function foo(){/**/} ... if(0) foo(); ..., Once all the dead codes are removed, foo()'s entry in the function table is checked to get no.of.times it gets referred in the code. If it is 0, that function has to be removed using the same stack method.

Step 6: In the remaining functions, the lines below the return statements (if any) are removed except the '}'. This removal is done till the end of the function. The end of the function is identified using stack.

Step 7: And I will assume that my dead-free code is ready now. Store the linked-list or array in an output file.

My Questions are.. 1.Whether my idea will be meaningful? or will it be implementable? How can I improve this algorithm?

2.While i am trying to implement this idea, I have to deal more with string manipulations rather than removing dead-codes. Is any way to reduce string manipulations in this algorithm.

Answer 1

Do not do it this way. C is a free-form language, and trying to process it line-by-line will result in supporting a subset of C that is so ridiculously restricted that it doesn't deserve the name.

What you need to do is to write a proper parser. There is copious literature about that out there. Find out which textbook your school uses for its compiler-construction course, and work through that -- or just take the course! Only when you've got the parser down should you even begin to consider semantics. Then do your work on abstract syntax trees instead of strings. Alternatively, find an already written and tested parser for C that you can reuse (but you'll still need to learn quite a bit in order to integrate it with your own processing).

If you end up writing the parser yourself, and it's only for your own edification, consider using a simpler language than C as your subject. Even though C at is core is fairly compact as languages go, getting all details of the declaration syntax right is surprisingly tricky, and will probably detract you from what you're actually interested in. And the presence of the preprocessor is an issue in itself which can make it very difficult to design meaningful source-to-source transformations.

By the way, the transformations you sketch are known in the trade as "constant propagation", or (in a more ambitious variants that will clone functions and loop bodies when they have differing constant inputs) "partial evaluation". Googling those terms may be interesting.