Versions Compared

Old Version 24

changes.mady.by.user Changpeng Fang

Saved on

compared with

New Version 25

changes.mady.by.user Changpeng Fang

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

original loop

for (int i = init,  i < limit;  i += stride) {  // loop with array range check
    ...
    if (scale*i + offset < a.length) {  // array range check
<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="eb52b0dec24d2818-b92dab15-478a4e92-a6f9b33f-d14e5d24977e0ad0f1447e95"><ac:plain-text-body><![CDATA[        ... a[scale*i+offset] ...
]]></ac:plain-text-body></ac:structured-macro>
    } else raise_uncommon_trap();
    ...
}

after loop predication

if ( scale * imax + offset < a.length ) {  // loop predicate. imax is the maximum value of i where init <= i < limit
    for (int i = init,  i < limit;  i += stride) {  // loop without array range check
         ...
<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="91586fafd5f4a224-f4d33214-469a41ca-b9bca9ab-3dcb3727ee6c7a7104d960f9"><ac:plain-text-body><![CDATA[         ... a[scale*i+offset] ...
]]></ac:plain-text-body></ac:structured-macro>
         ...
    }
} else raise_uncommon_trap();

...

Compared with the iteration range splitting based check elimination, loop predication has the following advantages:

1.  Loop predication can be applied to outer loops without code size increment.

2.  With loop predication, the check can be eliminated in the entire iteration space.

3. Loop predication can be applied to loops with calls

4. (for future work) Loop predication provides a unified interface that can be implemented (extended) to replace the existing iteration range

    splitting based check eliminations (loop peeling, partial peeling, range check elimination)

Source Code

1. The parser inserts a dummy loop predicate on each path to the loop head block (Parse::add_predicate in parse1.cpp)

...