How to eliminate "if continue " or "if break" statements in loop ?

Armstrong

hi,ti optimization experts!

Now I always find many "if continue " and " if break " statements in my algorithms.These statements prevented to produce software pipeline in loops and has poor

performance.for example:

how to optimize code like this:

for(...)

{

if (A) continue;

if(B) break;

}

when I compilered these code,I would found feedback information like this "Disqualified loop: Loop contains control code "; So, I couldn't know how to eliminate

"if break" and "if continue" to produce software pipeline.

over 12 years ago

0 MaciejKucia over 12 years ago

Mastermind 7925 points

There is no simple answer. In general you can't just remove them. You need to re-design your algorithm. Software pipeline works best with data frames. Can you give us some more specific example?

Regards,
Maciej

0 Armstrong over 12 years ago in reply to MaciejKucia

Intellectual 820 points

MaciejKucia said:

There is no simple answer. In general you can't just remove them. You need to re-design your algorithm. Software pipeline works best with data frames. Can you give us some more specific example?

Regards,
Maciej

for example:

for(index_i = 0; index_i < NUM_COUNT; index_i ++)
{
for(index_j = 0; index_j < NUM_COUNT; index_j ++)
{
if(pStr[index_j].id == 0 || index_i == index_j)
continue;

if( pStr[index_j].wx0 == pStr[index_i].wx0 \
&& pStr[index_j].wx1 == pStr[index_i].wx1 \
&& pStr[index_j].wy0 == pStr[index_i].wy0 \
&& pStr[index_j].wy1 == pStr[index_i].wy1)
pStr[index_i].id = 0;
}

}

statements like below contains"if continue",

if(pStr[index_j].id == 0 || index_i == index_j)
continue;

so, That couldn't produce software pipeline. how to eliminate the "if continue"??

0 Archaeologist over 12 years ago in reply to Armstrong

TI__Guru* 84285 points

A continue can always be turned into an if statement, possibly with an added variable. In this case, it's particularly simple:

for(index_i = 0; index_i < NUM_COUNT; index_i ++)
{
    for(index_j = 0; index_j < NUM_COUNT; index_j ++)
    {
         if (!(pStr[index_j].id == 0 || index_i == index_j))
         {
             if(   pStr[index_j].wx0 == pStr[index_i].wx0 \
                && pStr[index_j].wx1 == pStr[index_i].wx1 \
                && pStr[index_j].wy0 == pStr[index_i].wy0 \
                && pStr[index_j].wy1 == pStr[index_i].wy1)
             {
                 pStr[index_i].id = 0;
             }
         }
   }

}

However, that's still a pretty complicated conditional test. I'd be surprised if the compiler could software pipeline that.

0 MaciejKucia over 12 years ago in reply to Archaeologist

Mastermind 7925 points

if removal of first IF will not affect numerical stability and correctness you can use just:

pStr[index_i].id = (pStr[index_j].wx0 ^ pStr[index_i].wx0 ) & ([index_j].wx1 ^ pStr[index_i].wx1 ) & ( pStr[index_j].wy0 ^ pStr[index_i].wy0 ) & ( pStr[index_j].wy1 ^ pStr[inde x_i].wy1)

Regards,
Maciej

0 Armstrong over 12 years ago in reply to Archaeologist

Intellectual 820 points

Archaeologist said:

However, that's still a pretty complicated conditional test. I'd be surprised if the compiler could software pipeline that.

thx,But in fact what I expected was how to modify if statements to produce software pipeline,

so what you modified still couldn't produce software pipeline.

0 Armstrong over 12 years ago in reply to MaciejKucia

Intellectual 820 points

MaciejKucia said:

if removal of first IF will not affect numerical stability and correctness you can use just:

pStr[index_i].id = (pStr[index_j].wx0 ^ pStr[index_i].wx0 ) & ([index_j].wx1 ^ pStr[index_i].wx1 ) & ( pStr[index_j].wy0 ^ pStr[index_i].wy0 ) & ( pStr[index_j].wy1 ^ pStr[inde x_i].wy1)

Regards,
Maciej

MaciejKucia,thx!

But were you sure you understand my if statements.I didn't think you were wright.I guessed you forgot the condition ---

if (!(pStr[index_j].id == 0 || index_i == index_j)).Please check it.

0 MaciejKucia over 12 years ago in reply to Armstrong

Mastermind 7925 points

I said:

MaciejKucia said:
if removal of first IF will not affect numerical stability and correctness you can use just:

If you want zeroes on diagonal you can further multiply (or logical AND) by anty-identity matrix (not sure English name).

0 Armstrong over 12 years ago in reply to MaciejKucia

Intellectual 820 points

MaciejKucia said:

I said:
if removal of first IF will not affect numerical stability and correctness you can use just:

If you want zeroes on diagonal you can further multiply (or logical AND) by anty-identity matrix (not sure English name).

[/quote]

if code like below:

for(index_i = 0; index_i < NUM_COUNT; index_i ++)
{
if(pStr[index_j].id == 0 || index_i == index_j)
continue;
for(index_j = 0; index_j < NUM_COUNT; index_j ++)
{
if( pStr[index_j].wx0 == pStr[index_i].wx0 \
&& pStr[index_j].wx1 == pStr[index_i].wx1 \
&& pStr[index_j].wy0 == pStr[index_i].wy0 \
&& pStr[index_j].wy1 == pStr[index_i].wy1)
pStr[index_i].id = 0;
}
}

How to eliminate "if(pStr[index_j].id == 0 || index_i == index_j) continue;" I felt it was very hard to eliminate to produce software pipeline.

0 Armstrong over 12 years ago in reply to Armstrong

Intellectual 820 points

hi,MaciejKucia:

Do you agree that however nested if statements such as if continue statement and if break statement are complex they definitely can be eliminate.

And when these nested if statements are be compiled by DSP compiler.the codes can produce software pipeline.

So,here involved another problem. When I optimized algorithms on TI DSP such as C6000 C64x+ cpu ,my only goal was that made all codes and loops or functions

produce software pipeline. If software pipeline couldn't be produced the performance of algorithms was rather poor.So my question was: Could any nested if statements contained in loops

and functions be eliminated.

0 MaciejKucia over 12 years ago in reply to Armstrong

Mastermind 7925 points

Typical DSP algorithm does not have any IF.

Maybe those two materials will be an use for you:

http://www.ti.com/lit/an/spra666/spra666.pdf

http://www.ti.com/lit/ug/spru352g/spru352g.pdf

Regards,
Maciej

0 Armstrong over 12 years ago in reply to MaciejKucia

Intellectual 820 points

MaciejKucia said:

Typical DSP algorithm does not have any IF.

But , in my application the condition that "Typical DSP algorithm does not have any IF." couldn't always be satisfied .

0 Archaeologist over 12 years ago in reply to Armstrong

TI__Guru* 84285 points

Not every loop can be software pipelined. As a guideline, loops that have a constant increment and contain minimal conditional code in the body have the best chance of being software pipelined, but this is not a guarantee. Some loops with conditional code can be software pipelined, but the more complicated a conditional is, the less likely the loop can be software pipelined.

0 Archaeologist over 12 years ago in reply to Archaeologist

TI__Guru* 84285 points

Try this:

    for(index_i = 0; index_i < NUM_COUNT; index_i ++)
    {
        for(index_j = 0; index_j < NUM_COUNT; index_j ++)
        {
            if ((~(index_i ^ index_j)
                 | (pStr[index_j].wx0 ^ pStr[index_i].wx0)
                 | (pStr[index_j].wx1 ^ pStr[index_i].wx1)
                 | (pStr[index_j].wy0 ^ pStr[index_i].wy0)
                 | (pStr[index_j].wy1 ^ pStr[index_i].wy1)) == 0)
                pStr[index_i].id = 0;
        }
    }

0 Armstrong over 12 years ago in reply to Archaeologist

Intellectual 820 points

Archaeologist said:

Not every loop can be software pipelined.

I'm very appreciated that you give me reply.First,I agreed with you very much that not every loop can be software pipelined.

In my daily work. it was always puzzled that how to judge whether loops and functions in my code could be software pipelined.

I got some information form C6x programmer's guide.All of them said loops couldn't contain functions or control code (for example if continue if break),If loops contained functions and control code,software pipeline couldn't be produced ,But was it possible? How hard we achieve that goal! I thought it was impossible to guarantee that every loop didn't have any function and control code .

So. some loops that can be software pipelined can be optimized and get high performance.but some other loops cannot be software pipelined however.

Code Composer Studio™︎

Code Composer Studio forum

How to eliminate "if continue " or "if break" statements in loop ?