`altera-id-dependent-backward-branch` mass false positive: all variables assigned/initialized with a variable are considered id-dependent

[yeputons]

Inspired by this StackOverflow question.

Steps to reproduce

1. Consider the following code and save it to a.cpp:

void foo(int x, int y) {
    x = y;
    while (x < y) {
    }
}

2. Run clang-tidy-13 --checks=altera-id-dependent-backward-branch a.cpp

I'm running on Ubuntu 20.04.3 LTS:

Ubuntu LLVM version 13.0.1

  Optimized build.
  Default target: x86_64-pc-linux-gnu
  Host CPU: haswell

Expected outcome

There are no warnings, except maybe "this loop is never executed".

Real outcome

Error while trying to load a compilation database:
Could not auto-detect compilation database for file "a.cpp"
No compilation database found in /home/yeputons or any parent directory
fixed-compilation-database: Error while opening fixed database: No such file or directory
json-compilation-database: Error while opening JSON database: No such file or directory
Running without flags.
1 warning generated.
/home/yeputons/a.cpp:3:12: warning: backward branch (while loop) is ID-dependent due to variable reference to 'x' and may cause performance degradation [altera-id-dependent-backward-branch]
    while (x < y) {

Comments

This look completely unrelated to the altera-id-dependent-backward-branch check's docs: there is no get_local_id or anything like this in sight.

If I remove the x = y assignment, the warning goes away.

There is also no note on why exactly x is considered id-dependent, while there should be one. Maybe I need some extra flags or it's a separate issue?

Probable cause

I'm not familiar with LLVM's source code, but it seems to me that the bug is in saveIdDepVarFromReference at the very least: it saves all potentially id-dependent variables in IdDepVarsMap regardless of whether the right-hand side of the assignment/initialization is id-dependent itself. Looks like some early returns are missing. Similar bug probably happens in saveIdDepFieldFromReference as well.

More high-level picture is as follows:

1. The warning is issued here iff IdDepVar is found in the IdDepVarsMap map.
2. Variable x is marked as id-dependent by one of IdDependentBackwardBranchCheck::saveIdDep* methods from here (they're the only place modifying IdDepVarsMap).
3. They are called from this bunch of ifs. In particular, if there is a PotentialVar (pot_tid_var match) and RefExpr (assign_ref_var match), saveIdDepVarFromReference is called.
4. pot_tid_var matches either a variable initialized from a variable or a field (because the latter may be id-dependent) or a similar assignment. In both cases, either assign_ref_var or assign_ref_field is matches as well via RefVarOrField depending on whether the initializer is a variable or a field.
5. Hence, saveIdDepVarFromReference is called on the x = y assignment as well with assign_ref_var = y and pot_tid_var = x.
6. While saveIdDepVarFromReference checks that the right hand side is in IdDepFieldsMap, it does not do anything to with knowledge and assumes that PotentialVar is always id-dependent.

Btw, here is a code review

Suggested fix

1. Early return from saveIdDepVarFromReference if RefVar/RefField (there should be only one, an assertion would be nice to have) is not found in IdDepVarsMap.
2. Rename both saveIdDepVarFromReference and saveIdDepFieldFromReference to something like potentiallySaveIdDepVarFromReference to highlight that it performs some checks itself. It's easy to assume that the variable is already established to be id-dependent while reviewing saveIdDepVarFromReference.
3. Rename PotentialVar and pot_tid_var to something like PossiblyIdDependentVar/possibly_iddep_var to highlight that it's not necessary id-dependent even more. PotentialVar is more open to interpretation and the erroneous saveIdDepVarFromReference(RefExpr, MemExpr, PotentialVar); line does not immediately stand out as "save only a possible id dependent variable as really id-dependent". However, I'm not sure if that would really help, as the line is already inside some if-statement which looks somewhat reasonable.

[yeputons]

@ffrankies I see that you're the original author, would you mind taking a look?

[G-Harmon]

(I got here from the same stack overflow question. Hoping for a fix.)

[cheyao]

Bump, also came here from the so question, hoping for a quick fix

[yeputons]

@njames93, as the owner of clang-tidy and the first choice of reviewer, would you prefer to see a single big patch which fixes this issue and some other stuff, or a sequence of small independent refactorings and fixes (~40 LOC each)?

I've resolved the issue and wrote some tests in a branch: https://github.com/yeputons/llvm-project/commits/fix-altera-id-dependent-backward-branch . I've also added some minor quality-of-life improvements. Although I personally don't use this check, they're hopefully useful and break no workflows. Anyway, most of them are separate commits and can be easily omitted.

[EugeneZelenko]

@yeputons: See https://llvm.org/docs/Phabricator.html for patch process.

[yeputons]

@EugeneZelenko Thank you. I will create a series of small patches then.

[yeputons]

For the record, here is the first batch of patches, ones related to fixing this specific issue:
https://reviews.llvm.org/D145303
https://reviews.llvm.org/D145304
https://reviews.llvm.org/D145305

I suppose all further communication is to happen in that Phabricator