Refactor all patterns that use container iterator in the wrong way

[vgene]

Problem

In Speculation/Classify.cpp, we are using iterator loop of stl containers and then remove elements based on some condition. This is wrong! Removing an element invalidate the iterator and reusing that iterator will lead to segfault.

Instead of pattern like:

for (auto i : cheapPrivAUs) {
   if (LoopAA::containsExpensiveRemeds(i.second))
     cheapPrivAUs.erase(i.first);
 }

We need to use iterator more explicitly to avoid the problem (source):

    auto it = v.begin();
    while (it != v.end())
    {
        // remove odd numbers
        if (*it & 1) {
            // erase() invalidates the iterator, use returned iterator
            it = v.erase(it);
        }
        // Notice that iterator is incremented only on the else part (why?)
        else {
            ++it;
        }
    }

TODOs

• [ ] Find all patterns like this
• [ ] Refactor the code with

[vgene]

@gchan510 Please close this today.

[gchan510]

All cases are fixed except for the ones in CodeGen/Postprocess.cpp:606,628,809

ETA: tomorrow

[vgene]

@gchan510

[VictorYing]

Hi, I found this repo and came to see what recent development looks like after reading the Perspective and SCAF papers. Seems like you're doing cool work. Upon reading this issue, I thought I'd point out that there is a standard C++ idiom to remove items from a container without resorting to directly manipulating iterators: the erase-remove idiom. The erase-remove idiom, when used with remove_if, is guaranteed to execute the predicate code (often a lambda) exactly once per element of the container, and this idiom is often more efficient in addition to less error-prone than direct use of iterators.

llvm has a generic utility llvm::erase_if in llvm/ADT/STLExtras.h that makes the erase-remove idiom even easier.

EDIT: Oops, you can't use remove_if or erase_if on an associative container (i.e., a set or map), so please ignore my comment as it does not apply to your case.

[vgene]

@VictorYing Thank you for the comment! Please also let us know if you are interested in a tutorial of the current system and the recent development effort.

[VictorYing]

For sure, maybe after I'm finished with a MICRO submission, we can chat?

[gchan510]

Cases mentioned in https://github.com/PrincetonUniversity/cpf/issues/26#issuecomment-789503397 are ok. Every time the iterator is invalidated the outer loop starts iterating again from the beginning. It's not the cleanest way but it works so I'm closing this issue. If it becomes a performance bottleneck in the future we can reopen it.