Optimizing redundant code into loops algorithmically

Question

I'm writing a converter for fairly basic scripting language, however it seems to lack the ability to use for loops. This makes code very messy and redundant, for instance, instead of:

for(int i = 0; i < 5; i++) {
    ECHO Hello World!
    SLEEP 500
}

The scripts written in this language end up looking like this:

ECHO Hello World!
SLEEP 500
ECHO Hello World!
SLEEP 500
ECHO Hello World!
SLEEP 500
ECHO Hello World!
SLEEP 500
ECHO Hello World!
SLEEP 500

and so on. So basically, I'm converting this script to c++, would it be possible to reduce all of these repeating calls? I had thought about looping through and looking for duplicate code, however the problem arises that I can't process code such as this:

ECHO 1
SLEEP 500
ECHO 2
SLEEP 500
ECHO 3
SLEEP 500
ECHO 4

Is there a simpler way to recognize these patterns or do I need to delve into something more complicated such as neural networks?

What should the converter do, just execute them? Or does it really need to output readable code? — Bergi
– Bergi, Commented May 28, 2014 at 18:52
Well, then I wouldn't care about optimising it. Let the c++ compiler care about that. Or do you have any problems with code size of the unrolled loops? — Bergi
– Bergi, Commented May 28, 2014 at 19:21
That would be the main issue, I have very limited code size in this situation. — Dylan Katz
– Dylan Katz, Commented May 28, 2014 at 19:25

Ira Baxter · Accepted Answer · 2015-01-24 10:36:59Z

I don't know about "simpler".

What you want is a clone detector that detects parametric clones. This finds repeated sequence of clones, such that the clone, having a parameter, can be instantiated to produce the exact code instances.

What your example loop contains is repeated instances of the parameterized clone:

   ECHO n
   SLEEP 500

so the first abstraction of your sequence is:

   for n in {1,2,3,4}
      ECHO n
      SLEEP 500

A for loop over a sequence is easily converted to:

  for n=1,4 step 1
      ECHO n
      SLEEP 500

which is the code I think you want to generate.

So you problem is to get a parametric clone detector.

See this technical paper on how to implement a parametric cloned detector over abstract syntax trees. These are not easy tools to build. However, if you build one, then if you can parse your scripting language to ASTs, then this will give you the core parametric clones. Then you can carry out the additional optimizations that you think helpful.

Collectives™ on Stack Overflow

Optimizing redundant code into loops algorithmically

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related