[analyzer] Upstream BitwiseShiftChecker

[donat.nagy]

Summary

This commit releases a checker that was developed to a stable level in the Ericsson-internal fork of Clang Static Analyzer.

Note that the functionality of this checker overlaps with core.UndefinedBinaryOperatorResult ("UBOR"), but there are several differences between them:
(1) UBOR is only triggered when the constant folding performed by the Clang Static Analyzer engine determines that the value of a binary
operator expression is undefined; this checker can report issues where the operands are not constants.
(2) UBOR has unrelated checks for handling other binary operators, this checker only examines bitwise shifts.
(3) This checker has a Pedantic flag and by default does not report expressions (e.g. -2 << 2) that're undefined by the standard but consistently supported in practice.
(4) UBOR exhibits buggy behavior in code that involves cast expressions, e.g.

void foo(unsigned short s) {
  if (s == 2) {
    (void) ((unsigned int) s) << 16;
  }
}

Later it would be good to eliminate this overlap (perhaps by deprecating and then eliminating the bitwise shift handling in UBOR), but in my opinion that belongs to separate commits.

Co-authored-by: Endre Fulop <[e-mail]>

[donat.nagy]

I tested this commit on several open source projects (in the default mode Pedantic=false), the following table summarizes the results:

vim_v8.2.1920_baseline_vs_vim_v8.2.1920_with_bitwise_shift	New reports	Lost reports	no differences
openssl_openssl-3.0.0-alpha7_baseline_vs_openssl_openssl-3.0.0-alpha7_with_bitwise_shift	New reports	Lost reports	+2 FPs from same invalid loop assumption [1]
sqlite_version-3.33.0_baseline_vs_sqlite_version-3.33.0_with_bitwise_shift	New reports	Lost reports	one FP lost for unclear reasons
ffmpeg_n4.3.1_baseline_vs_ffmpeg_n4.3.1_with_bitwise_shift	New reports	Lost reports	21 new reports, 14 lost reports, mostly FPs [2]
postgres_REL_13_0_baseline_vs_postgres_REL_13_0_with_bitwise_shift	New reports	Lost reports	two FPs are "converted" to new checker, one unreadable report lost
libwebm_libwebm-1.0.0.27_baseline_vs_libwebm_libwebm-1.0.0.27_with_bitwise_shift	New reports	Lost reports	no differences
xerces_v3.2.3_baseline_vs_xerces_v3.2.3_with_bitwise_shift	New reports	Lost reports	no differences
bitcoin_v0.20.1_baseline_vs_bitcoin_v0.20.1_with_bitwise_shift	New reports	Lost reports	6 new FPs caused by incorrect config of our CI [3], one FP lost
protobuf_v3.13.0_baseline_vs_protobuf_v3.13.0_with_bitwise_shift	New reports	Lost reports	three reports "converted" to new checker
qtbase_v6.2.0_baseline_vs_qtbase_v6.2.0_with_bitwise_shift	New reports	Lost reports	3 new reports, 3 lost reports [4]
contour_v0.2.0.173_baseline_vs_contour_v0.2.0.173_with_bitwise_shift	New reports	Lost reports	no differences
acid_2022-08-02-codechecker-test_baseline_vs_acid_2022-08-02-codechecker-test_with_bitwise_shift	New reports	Lost reports	no differences

More detailed summary:
[1] When the engine encounters a loop, it arbitrarily assumes that (there is a valid path where) the loop body will be executed 0 times. These unfounded assumptions produce false positives in many stable checkers.
[2] It seems that most of these warnings report the same underlying issues in different ways, but I didn't do a through analysis yet.
[3] The build/analysis procedure of bitcoin was misconfigured in our CI and the VERIFY_CHECK() assertions were preprocessed incorrectly.
[4] Logical relationships between these reports:

• two new false positives (1 and 2) are caused by the same underlying engine misunderstanding which had caused a different false positve in the baseline;
• one old report is eliminated because core.BitwiseShift is non-pedantic by default;
• one old false positive is lost for unclear reasons;
• one new false positive appeared, it's caused by an incorrect assumption that an 'if' and a 'while' are logically independent (in fact, the loop body will never run in cases where the 'if' condition is false).

clang/test/Analysis/symbol-simplification-nonloc-loc.cpp

46–47

In this test file these warnings were irrelevant, so I picked a different arbitrary constant to eliminate them.

[donat.nagy]

(Fix incorrect filename mark in the license header.)

[NoQ]

(1) UBOR is only triggered when the constant folding performed by the Clang Static Analyzer engine determines that the value of a binary operator expression is undefined

Yes I wholeheartedly agree, these checks are pre-condition checks, they should have never been implemented in checkPostStmt. Instead they should stop the engine from evaluating the statement entirely if they think undefined behavior would occur, just like the division by zero checker. Just for that reason I'm happy to remove the existing bitshift check in favor of this check, as well as remove the ExprEngine/SValBuilder code that produces UndefinedVals in these cases. So, architecturally, this is the step in the right direction and I love it!

(4) UBOR exhibits buggy behavior in code that involves cast expressions

Hmm, what makes your check more resilient to our overall type-incorrectness?

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

95–99

Because addTransition() is a very confusing API that's very easy to misuse in subtle ways (causing unexpected state splits), I feel anxious when I see functions like

bool isValidShift();
bool isOvershift();
bool isOperandNegative(OperandSide Side);
bool isLeftShiftOverflow();

that look like boolean getters but in fact call addTransition() under the hood. If we could at least call them checkOvershift() etc., that'd be much better. Ideally I wish there was some safeguard against producing redundant transitions, like make them return an ExplodedNode and chain them, or something like that.

302–303

Can we just append this to the warning? The addNote() is useful for notes that need to be placed in code outside of the execution path, but if it's always next to the warning, it probably doesn't make sense to display it separately.

353–354

Props!! Even if they don't do anything, ultimately it's their responsibility.

[donat.nagy]

In D156312#4537200, @NoQ wrote:

(4) UBOR exhibits buggy behavior in code that involves cast expressions

Hmm, what makes your check more resilient to our overall type-incorrectness?

The code of UBOR (UndefResultChecker.cpp) uses the method LHS->countl_zero() (count zeros on the left side of the binary representation) which is very convenient but uses the "cached" bit width that is stored in the APSInt and apparently not updated by the casts. The checker proposed in this commit avoids this pitfall because it calls getActiveBits() on the APSInt and subtracts the result from the bit width of the type of the LHS (which is queried from the AST node).

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

95–99

These functions were originally called checkXXX() but I felt that the meaning of their boolean return value was too confusing with that naming scheme.

I'll try to ensure that emitReport or addTransition are only called on the topmost layer (the run() method) and change the return types of internal subroutines to make them return nullable pointers (e.g. std::unique_ptr<PathSensitiveBugReport>) instead of bools. This would (1) eliminate the "what does true mean at this point?" issues (2) clarify that this checker never performs more than one transition. (If the shift is invaild, we transition to a sink node by emitting a bug; if the shift is vaild, we perform a transition to record the state update.)

302–303

I didn't append this to the warning because I felt that the warning text is already too long. (By the way, an earlier internal variant of this checker produced two separate notes next to the warning message.)

I tweaked the messages of this checker before initiating this review, but I feel that there's still some room for improvements. (E.g. in this particular case perhaps we could omit some of the details that are not immediately useful and could be manually calculated from other parts of the message...)

[gamesh411]

I like this, especially, that the functionality of UBOR can be merged and extended in a much cleaner way (architecturally).

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

302–303

Just a thought on simplifying the diagnostics a bit:

Warning: "Right operand is negative in left shift"
Note: "The result of left shift is undefined because the right operand is negative"
Shortened: "Undefined left shift due to negative right operand"

Warning: "Left shift by '34' overflows the capacity of 'int'"
Note: "The result of left shift is undefined because the right operand '34' is not smaller than 32, the capacity of 'int'"
Shortened: "Undefined left shift: '34' exceeds 'int' capacity (32 bits)"

The more complex notes are a bit sketchy, as relevant information can be lost, and the following solution is probably a bit too much, but could prove to be an inspiration:

Warning: "Left shift of '1024' overflows the capacity of 'int'"
CXX Note: "Left shift of '1024' is undefined because 'int' can hold only 32 bits (including the sign bit), so some bits overflow"
CXX Note: "The value '1024' is represented by 11 bits, allowing at most 21 bits for bitshift"
C Note: "Left shift of '1024' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so some bits overflow"
C Note: "The value '1024' is represented by 11 bits, allowing at most 20 bits for bitshift"

Shortened:
CXX Warning: "Undefined left shift: '1024' (11 bits) exceeds 'int' capacity (32 bits, including sign)"
C Warning: "Undefined left shift: '1024' (11 bits) exceeds 'int' capacity (31 bits, excluding sign)"

[donat.nagy]

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

302–303

Clarification about the Msg/ShortMsg distinction:
I'm intentionally separating the short warning messages and the longer note messages because createBugReport() enforces the convention that it will always emit a warning and a note at the bug location.

According to the comments in the source code, the intention is that the note contains all the relevant information, while the warning is a brief summary that can be displayed in situations where the notes wouldn't fit the UI.

IIUC many checkers ignore this distinction and emit the same (often long and cumbersome) message both as a note and as a warning (createBugReport() has a variant which takes only one message parameter and passes it to both locations), but I tried to follow it because I think it's ugly when the same message is repeated twice and there is some sense in providing both a brief summary and a full description that doesn't use potentially-ambiguous abbreviations to save space.

Of course I could also accept a community decision that this "brief warning / full note" distinction is deprecated and will be eliminated (because e.g. front-end utilities are not prepared to handle it), but in that case I'd strongly suggest a redesign where we eliminate the redundantly printed 'note' message. (There is no reason to say the same thing twice! There is no reason to say the same thing twice!)

On the other hand, in addition to this Msg/ShortMsg distinction, this part of the code also adds the extra LeftNote (as a remnant from an earlier internal version of this checker), and that's that's what I'd like to merge into Msg (following NoQ's suggestion and keeping it distinct from the ShortMsg).

[steakhal]

clang/docs/analyzer/checkers.rst

35

44–50

I believe shifting out the "sign bit" is UB because the representation of the signed integer type was not defined.
Prior C++20 (?), it was allowed to represent signed integer types as two's-complement (virtually every platform uses this), one's complement, sign-magnitude. Wiki.
And it turns out, all these three representations behave differently with negative values.
Check out JF's talk from 2018 about this.

I'd need to think about the relevance of C++20 in this context, but here is what I think of now:
My idea is that the observed behavior is not influenced by the "standard", rather by the time we released C++20, they realized that no actual platform uses weird signed integer representations.
Given this observation, I'd argue that we shouldn't have this flag at all.

81

We should exactly elaborate on what "proper" means here.

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

143

One does not frequently see the long long type.
Do you have a specific reason why int or unsigned wouldn't be good?

151

How about swapping these branches on the ResultVal.isUndef() predicate?

153–157

Generally, I don't favor mutating member functions.
It makes it harder to track how we ended up with a given State.

158–159

I wonder if we should add a message here that we introduced a new constraint: "X assumed to be non-negative".
To add such a message, you should do something similar to what is done in the StdLibraryFunctionsChecker.
Take the C.getPredecessor() and chain all your NoteTags by calling the Pred = C.addTransition(NewState, Pred, Tag) like this. This way. This is how one "sequence of ExplodedNodes" can be made.

clang/test/Analysis/analyzer-config.c

36

I'm pretty sure I got rid of this one :D
Consider rebasing on top of llvm/main.

[donat.nagy]

@steakhal Thanks for the review!

I answered some of your questions; and I'll handle the rest soon.

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

151

The argument of ProgramState::assume() must be a DefinedOrUnknownSVal, so I need to cast the return value of evalBinOp (which may be Undefined) to this type.

158–159

This is already done by BitwiseShiftValidator::createNoteTag(). It's a bit complex because the checker merges all its assumptions into a single note tag (because I didn't want to emit two or three notes directly after each other.

clang/test/Analysis/analyzer-config.c

36

Oops, this might be an error introduced during a rebase... Thanks for catching it!

[donat.nagy]

I'll soon upload a refactored version.

clang/docs/analyzer/checkers.rst

44–50

Thanks for the background information! I knew the rough outlines of the situation, but your links provided interesting details.

I agree that the non-pedantic mode is the "sane mode" that reflects the real behavior of the hardware; but the standards (with the exception of C++20) explicitly declare that signed shift overflow and shifting negative values is UB and there may be secondary requirements like SEI-CERT rule INT32-C that demand compliance to the standards.

I don't think that I'd spend time on implementing pedantic mode because there are more important things to do, but as we already have this feature, I think we should release it as an off-by-default option.

81

What would you suggest? I could try to write a slightly longer suggestion, but I don't want to repeat the same conditions that I listed above the code example.

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

143

I inherited this type choice from old code and didn't think much about it. My guess is that LimitVal needs to be a signed integer (because e.g. -1 < 0u would be evaluated to false) and it's a long long because that's guaranteed to represent all unsigned values. (However, the actual values of Limit are very small.)

I'll probably use int for Limit and LimitVal with some comments to clarify the reason for this type choice.

153–157

I also agree that mutating member functions are often problematic and may make the code more difficult to understand.

However, in this particular case I think it's important to ensure that we're always using the most recent state, and that's difficult to guarantee in the "pass everything as arguments and return values" style. Moreover, I do some parallel bookkeeping because I want to summarize the state changes in a single note tag, and that would make the "naive functional" solution even more convoluted.

In a functional language like Haskell I'd use computations in a State monad to implement this logic; my C++ code is a direct translation of that solution. (As a secondary utility, my class also provides read-only access to some context like a Reader monad, because functions that take 5-8 arguments are also very difficult to understand. This way, the relevant arguments are highlighted as actual arguments, while the shared context is described by the const data members.)

302–303

Among notes, my only planned change is that instead of

Warning: "Left shift of '1024' overflows the capacity of 'int'"
CXX Note: "Left shift of '1024' is undefined because 'int' can hold only 32 bits (including the sign bit), so some bits overflow"
CXX Note: "The value '1024' is represented by 11 bits, allowing at most 21 bits for bitshift"
C Note: "Left shift of '1024' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so some bits overflow"
C Note: "The value '1024' is represented by 11 bits, allowing at most 20 bits for bitshift"

I'll implement something like

Warning: "Left shift of '1024' overflows the capacity of 'int'"
CXX Note: "Left shift of '1024' (represented by 11 bits) is undefined because 'int' can hold only 32 bits (including the sign bit), so some bits overflow"
C Note: "Left shift of '1024' (represented by 11 bits) is undefined because 'int' can hold only 31 bits (excluding the sign bit), so some bits overflow"

[donat.nagy]

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

302–303

Correction: now I'm leaning towards just discarding the secondary note, because the message examples listed in the previous comment are just the variants where the right operand is unknown. In the more detailed message template "The shift '{0} << {1}' is undefined {2}, so {3} bit{4} overflow{5}" there is no place to insert the "represented by {} bits" message.

[donat.nagy]

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

95–99

I eliminated isValidShift() by merging it with run() (which was very short) and renamed the rest of the functions to checkXXX.

Now the exploded graph is only modified in the top-level method run().

143

I changed the type of the Limit argument to unsigned (because that's what this function is called with) and changed the type of LimitVal to IntTy with a comment that describes that it must be signed.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

302–303

There's nothing wrong with long, multi-sentence diagnostic messages!

Unlike the compiler proper, we aren't typically used from the command line, so we aren't trying to fit into 80 columns. So we start our warnings with a capital letter and expect them to be, at the very least, complete sentences.

[steakhal]

I haven't gone deep into the implementation, but by only looking at the quality of the code and the structure I assume it implements the right behavior.
I've checked the tests though, and they look good.
I only found irrelevant nits. Awesome work.

---

Have you considered checking the shift operands for taint?
I wonder if we could warn if we cannot prove the correct use of the shift operator when either of the operands is tainted.

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

135

Check for subsequent duplicated words. They are usually typos.

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

10–12

Please elaborate what counts as "incorrect use".

30–31

This is used quite often and hinders the readability by indenting the args a lot. Making the spelling shorter, would somewhat mitigate this.

36

43

54

Where does this comment corresponds to?

58–60

How about using the same enum type for these two? It would signify that these are used together.
Also, by only looking at the possible values, it's not apparent that these are bitflag values. A suffix might help the reader.

61–64

Have you considered using std::optional?
Given that the dimension of this variable is "bits", I think it would be great to have that in its name.

82

Check if your member functions can be declared as const.

107–110

I'd prefer BR or Report. Since we know already that we are in the path-sensitive domain, P has less value there.
I'd apply this concept everywhere in the patch.

125–128

To me it feels as if this comment should be at the definition of checkLeftShiftOverflow, and only keep here a short reminder. Similarly to how you did with the previous cases.

149

191–192

219

The isLeftShift() ? "left" : "right" expression appears 4 times in total.
I'd also recommend to not distinguish the capitalized "left" and "right" strings, and just post-process the messages to ensure that the first character is capitalized inside the createBugReport().

Also note that you can reuse the same placeholder, so you would only need to pass the side() only once.

static void capitalizeBeginning(std::string &Str) {
  if (Str.empty())
    return;
  Str[0] = llvm::toUpper(Str[0]);
}

StringRef side() const {
  return isLeftShift() ? "left" : "right";
}

241

This will ensure that the definition of LeftAvailableBitWidth does not wrap.
And, more importantly, assert(LeftBitWidth >= UsedBitsInLeftOperand) also holds, asserted later.

253–255

Okay, so this is an invariant.
How about rephrasing this to better express that:

We should have already reported if the left operand of the shift was negative, thus this cannot be negative here.

264

I'd move this closer to the first "use" place.

316

clang/test/Analysis/bitwise-shift-common.c

109

Hmm, does this "but" actually mean "and" here?
Anyway, both using "but" and "and" there looks awkward.
It might be only me though.

130

It's an unrelated comment, but always bothers me to see 'right' mentioned here, where there is nothing called like that...

149

clang/test/Analysis/bitwise-shift-sanity-checks.c

21–23

How about simplifying these lines to -Wno-shift? Have you considered it?

58–59

Let's test if the shift RHS operand is bigger than 64.

clang/test/Analysis/bitwise-shift-state-update.c

31–36

Have you considered using clang_analyzer_value(left) for inspecting the assumed range of the operands?
IMO that leads to more readable tests.

[donat.nagy]

Thanks for the suggestions, I answered those where I had something to say and I'll implement the rest of them.

In D156312#4576120, @steakhal wrote:

Have you considered checking the shift operands for taint?
I wonder if we could warn if we cannot prove the correct use of the shift operator when either of the operands is tainted.

It would be straightforward to add taint handling; but I'd prefer to leave it for a follow-up commit. Some experimentation would be needed to see whether it produces useful results (do real-world projects use shifts on tainted numbers? do we encounter false positives?).

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

54

The two data members (Ctx and State) that are directly below the comment.

I tried to split the list of data members into three groups (primary mutable state, secondary mutable state, const members), but now I reconsider this I feel that these header comments are actually superfluous.

I'll return to a variant of the earlier layout where I put NonNegFlags/UpperBound to the end and comment that they are only used for note tag creation; but don't emphasize the (immediately visible) constness / non-const-ness of other members with comments.

58–60

Using the enum type is a good idea, however I'd probably put the Flag suffix into the name of the type:

enum SignednessFlags : unsigned { NonNegLeft = 1, NonNegRight = 2 };
SignednessFlags NonNegOperands = 0;

61–64

I considered using std::optional, but using this "old-school" solution ensures that NoUpperBound is comparable to and larger than the "real" upper bound values, which lets me avoid some ugly boolean logic. I'll update the comment and probably also the variable name.

107–110

The P stands for the "Ptr" in the name of the type alias BugReportPtr; but your comment clearly highlights that this variable name is confusing ;).

I'll probably avoid the auto and use BugReportPtr Bug = ... to remind the reader that this is a pointer (that can be null) and if it's non-null, then we found a bug.

191–192

This is an important distinction, I use "not smaller than {2}" as a shorter synonym of "larger than or equal to {2}". I can choose some other wording if you feel that this is not clear enough.

264

Good point, previously it was used by the calculation that is now performed by assumeRequirement.

302–303

Even if the message length is not limited, I think it's better to delete the additional note line (instead of merging it with the "regular" note line) because it's just too much information and the gist of the issue is lost behind the flood of redundant numbers.

However, this is just a subjective decision and I'm open to extending the message if you feel that something important is missing from it.

316

I'd say that the current wording is correct because the the checker "use"s the comparison operators (in its implementation) instead of "accept"ing them from outside; but I can replace the message with e.g. "this function does not accept other comparison operators" if you'd prefer that.

clang/test/Analysis/bitwise-shift-common.c

109

Yes, this sentence fragment is like "not too small but not too large", where "but" is equivalent to "and" and both are a bit awkward.

clang/test/Analysis/bitwise-shift-sanity-checks.c

21–23

Unfortunately there is no such shortcut: when I tried to execute trunk clang with it, I got "warning: unknown warning option '-Wno-shift'".

[donat.nagy]

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

30–31

Good idea!

58–60

I rename the member NonNegFlags to NonNegOperands but its type remains a plain unsigned because otherwise using the or-assign operator like NonNegOperands |= NonNegLeft produces the error

Assigning to 'enum SignednessFlags' from incompatible type 'unsigned int' (clang typecheck_convert_incompatible)

(note that both operands were from the same enum type).

219

I introduced a method for isLeftShift() ? "left" : "right" (which is indeed repeated several times), but I didn't define capitalizeBeginning because that would've been used only once.

Your remark that [with the capitalization function] "you can reuse the same placeholder, so you would only need to pass the side() only once" seems to be incorrect, because Side == OperandSide::Left ? "Left" : "Right" (which operand are we talking about?) and isLeftShift() ? "left" : "right" (what kind of shift operator are we talking about?) are two independent values.

[donat.nagy]

Uploading a new version based on the reviews.

[steakhal]

Great progress.
Now, moving to the docs.
Have you checked that the docs compile without errors and look as you would expect? Please post how it looks.

Please make a note about this new checker in the clang's release docs, as we usually announce new checkers and major changes there.

clang/docs/analyzer/checkers.rst

58–64

else after return

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

54

One way to emphasize this is by choosing names like FoldedState, or anything else that has something to do with "motion" or "change".
Given that if we have ProgramStateRefs in helper classes they usually remain still. Think of BugReportVisitors for example. Consequently,it's important to raise awareness when it's not like that. A different name would achieve this.

58–60

Okay, indeed one would need to define the operator|(SignednessStatus, SignednessStatus) and operato&|(SignednessStatus, SignednessStatus) as well.
It probably doesn't worth it. Such a pity that we can't have nice things in C++.

61–64

What "ugly boolean logic" are you referring to?
I thought one can always use value_or(999) anyway. To me, that means that the option approach is a refinement of yours. But depending on the situation, it might be possible to avoid the extrema value 999 altogether.

107–110

Oh I see. To me, it's fairly obvious now that bugreports are just smart-pointers.
So I implicitly looked for some other reason. But just look at other checker, and call it the same way how they do, for consistency. That's all I wanted.
There are two/three common options I believe: B or BR, and maybe Report.

191–192

No, I have not strong feelings. Feel free to use the one you like more.

219

Makes sense. It was so tempting though.

273

getExtValue(), I believe, asserts that it "fits", thus the concrete int is at most 64 bits wide. Does it work for _BigInts? (or whatever we have like that :D)

300–304

When I see something like this I always think of using a ternary.
Have you also considered?

316

No strong feelings :)

336–340

AHA! Now I got you. You also call this R.
Just use R at the callsite as well. Job done.

356–358

How about eagerly inline initializing this field? And avoiding mutable as well.

368–370

[donat.nagy]

I handled the inline comments, I'll check the example code and edit the release notes tomorrow.

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

54

My intuition is that the variable name "State" already implies that it will be regularly changed and updated as we are going forward; but you're right that in this project we've a tradition of storing snapshots of "old" states in various helper classes.

(By the way, I'm a bit worried when I read code that stores and passes around random stale snapshots of the state. Of course we cannot avoid the branching nature of the exploded graph, but other than that it'd be good to store the State in language constructs where you cannot accidentally lose information by building onto an older state variable.)

61–64

I'm prejudiced against optional in C++ because I feel that it's clunky and doesn't fit the rest of the language. (Note that I like Maybe in Haskell and don't have strong feelings about "using a variable that may be None" in Python; so this is specific to C++.)

However, in this particular case I decided to switch to std::optional<unsigned>, because it lets me write !UpperBoundBitCount instead of the longer (but perhaps more readable) UpperBoundBitCount != NoUpperBound.

The "ugly boolean logic" that I spoke about is (!UpperBoundBitCount || Limit < UpperBoundBitCount.value()); however I think this is still better than Limit < UpperBoundBitCount.value_or(999) which falls to the ground between two chairs as it introduces both the type optional and the arbitrary placeholder number.

107–110

Ok, I switched to the variable name "BR". I didn't have a strong preference for using "Bug", I just thought that your request is "the current name is bad, use anything else" and not "please use one of the traditional names".

219

Yes, trivial string formatting can introduce a surprising amount of complications...

273

This final check is executed when we already know that 0 <= ConcreteRight < 128 (or the bit width of the largest integer type). I added a comment that mentions this and replaced the type std::int64_t with a plain unsigned.

I also updated the testcase large_right to ensure that later changes don't introduce crashes related to absurdly oversized right arguments.

336–340

This is a code fragment that survived my refactoring efforts without significant changes... until now :)

Now that you highlighted it, I'm renaming R to BR just to be a contrarian :)

356–358

This pattern systematically appears in all checkers that I've seen because the constructor of BugType queries and stores the name of the checker, which is only initialized when the checker (*this) is registered. This dependency means that the BugType cannot be initialized in the constructor of the Checker.

[steakhal]

The test coverage is also impressive. Thanks!

[donat.nagy]

I verified that the checker handles the examples in the documentation correctly (and added them to the test suite). However, as I was tweaking the examples in the documentation, I accidentally found a situation where the checker produces a very surprising and arguably incorrect error message.

After investigating this issue, I added the testcases signed_aritmetic_{good,bad} which document the current sub-optimal state. The root cause of this problem is a high-level property of the engine (that it assumes that signed overflows are always possible and acceptable) and I don't see a local workaround that would silence or fix these incorrect error messages.

@steakhal @NoQ What do you know about these signed overflow issues (I presume that analogous issues also appear in other checkers)? How should we handle this limitation of this checker?

[donat.nagy]

(The release notes entry is still missing, I'll try to add it tomorrow.)

[steakhal]

In D156312#4588406, @donat.nagy wrote:

After investigating this issue, I added the testcases signed_aritmetic_{good,bad} which document the current sub-optimal state. The root cause of this problem is a high-level property of the engine (that it assumes that signed overflows are always possible and acceptable) and I don't see a local workaround that would silence or fix these incorrect error messages.

@steakhal @NoQ What do you know about these signed overflow issues (I presume that analogous issues also appear in other checkers)? How should we handle this limitation of this checker?

I don't think most checkers depend on value ranges explicitly, except for a handful of checkers maybe. So, I don't think it's such a huge deal, but I agree that it's a problem.
I would bet that the StdLibraryFunctionsChecker would suffer from the same issue, and the OOB checker(s) along with it.
I don't know of heuristics mitigating the damage.

I don't think we should do anything about it unless it's frequent enough.
Try to come up with a heuristic to be able to measure how often this happens, if you really care.
Once you have a semi-working heuristic for determining if that bugpath suffers from this, you can as well use it for marking the bugreport invalid if that's the case to lean towards suppressing those FPs.

I don't think it's completely necessary to fix those FPs to land this. I think of that as an improvement, on top of this one.
I hope I clarified my standpoint.

clang/test/Analysis/bitwise-shift-sanity-checks.c

71–75

Let's be explicit about the actual assumed value range, and use clang_analyzer_value().
I also recommend using an explicit FIXME for calling out what should be there, instead of abusing a non-matching expected pattern. I know I used that in the past, and probably seen it from me. I feel ashamed that I did that. I know I did that to have cleaner diffs, once fixed, but I honestly think it does more harm than good.

[donat.nagy]

In D156312#4589251, @steakhal wrote:

I don't think we should do anything about it unless it's frequent enough.
Try to come up with a heuristic to be able to measure how often this happens, if you really care.
Once you have a semi-working heuristic for determining if that bugpath suffers from this, you can as well use it for marking the bugreport invalid if that's the case to lean towards suppressing those FPs.

Minor clarification: these are not FPs, these are true positives with a bad error message. I was annoyed when I found this surprising bug on the almost-ready checker that I was working on; but I wouldn't say that this is an especially severe issue.

In D156312#4589251, @steakhal wrote:

I don't think it's completely necessary to fix those FPs to land this. I think of that as an improvement, on top of this one.
I hope I clarified my standpoint.

I agree, I'll create a new revision which mentions this checker in the release notes, and I hope that I'll be able to merge that. Later I'll try to return to this question with either an engine improvement or a heuristic mitigation.

clang/test/Analysis/bitwise-shift-sanity-checks.c

71–75

I already tried calling clang_analyzer_value() at that point when I was investigating, but unfortunately it won't say anything useful because the actual range corresponding to the symbolic expression is only calculated when the evalBinOp() calls examine it.

I'll change the "expected - warning" to a FIXME.

[donat.nagy]

Updated the release notes. This could be the final version of this commit if you agree that it's good enough.

[donat.nagy]

clang/docs/analyzer/checkers.rst

81

(I'm marking this request as "Done" because I couldn't find a better wording. Feel free to reopen the discussion if you wish.)

[donat.nagy]

A few minutes ago I accidentally re-uploaded the previous version of the patch (diffs #550318 and #550703 are identical); now I'm fixing this by uploading the actually updated variant.

[steakhal]

🎉 🚀

clang/docs/ReleaseNotes.rst

 libclang
 --------
 
 - Exposed arguments of ``clang::annotate``.
 
 Static Analyzer
 ---------------
 
+- Added a new checker ``core.BitwiseShift`` which reports situations where
+  bitwise shift operators produce undefined behavior (because some operand is
+  negative or too large).
+
 .. _release-notes-sanitizers:
 
 Sanitizers
 ----------
 - ``-fsanitize=signed-integer-overflow`` now instruments ``__builtin_abs`` and
   ``abs`` builtins.
 
 

clang/docs/analyzer/checkers.rst

 .. _core-checkers:
 
 core
 ^^^^
 Models core language features and contains general-purpose checkers such as division by zero,
 null pointer dereference, usage of uninitialized values, etc.
 *These checkers must be always switched on as other checker rely on them.*
 
+.. _core-BitwiseShift:
+
+core.BitwiseShift (C, C++)
+""""""""""""""""""""""""""
+
+Finds undefined behavior caused by the bitwise left- and right-shift operator
+operating on integer types.
+
+By default, this checker only reports situations when the right operand is
+either negative or larger than the bit width of the type of the left operand;
+these are logically unsound.
+
+Moreover, if the pedantic mode is activated by
+``-analyzer-config core.BitwiseShift:Pedantic=true``, then this checker also
+reports situations where the _left_ operand of a shift operator is negative or
+overflow occurs during the right shift of a signed value. (Most compilers
+handle these predictably, but the C standard and the C++ standards before C++20
+say that they're undefined behavior. In the C++20 standard these constructs are
+well-defined, so activating pedantic mode in C++20 has no effect.)
+
+**Examples**
+
+.. code-block:: cpp
+
+ static_assert(sizeof(int) == 4, "assuming 32-bit int")
+
+ void basic_examples(int a, int b) {
+   if (b < 0) {
+     b = a << b; // warn: right operand is negative in left shift
+   } else if (b >= 32) {
+     b = a >> b; // warn: right shift overflows the capacity of 'int'
+   }
+ }
+
+ int pedantic_examples(int a, int b) {
+   if (a < 0) {
+     return a >> b; // warn: left operand is negative in right shift
+   }
+   a = 1000u << 31; // OK, overflow of unsigned value is well-defined, a == 0
+   if (b > 10) {
+     a = b << 31; // this is undefined before C++20, but the checker doesn't
+                  // warn because it doesn't know the exact value of b
+   }
+   return 1000 << 31; // warn: this overflows the capacity of 'int'
+ }
+
+**Solution**
+
+Ensure the shift operands are in proper range before shifting.
+
 .. _core-CallAndMessage:
 
 core.CallAndMessage (C, C++, ObjC)
 """"""""""""""""""""""""""""""""""
  Check for logical errors for function calls and Objective-C message expressions (e.g., uninitialized arguments, null function pointers).
 
 .. literalinclude:: checkers/callandmessage_example.c
     :language: objc

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

 def WebKitAlpha : Package<"webkit">, ParentPackage<Alpha>;
 
 //===----------------------------------------------------------------------===//
 // Core Checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Core in {
 
+def BitwiseShiftChecker : Checker<"BitwiseShift">,
+  HelpText<"Finds cases where bitwise shift operation causes undefined behaviour.">,
+  CheckerOptions<[
+    CmdLineOption<Boolean,
+                  "Pedantic",
+                  "If set to true, the checker reports undefined behavior even "
+                  "if it is supported by most compilers. (This flag has no "
+                  "effect in C++20 where these constructs are legal.)",
+                  "false",
+                  Released>,
+  ]>,
+  Documentation<HasDocumentation>;
+
 def CallAndMessageModeling : Checker<"CallAndMessageModeling">,
   HelpText<"Responsible for essential modeling and assumptions after a "
            "function/method call. For instance, if we can't reason about the "
            "nullability of the implicit this parameter after a method call, "
            "this checker conservatively assumes it to be non-null">,
   Documentation<HasDocumentation>,
   Hidden;
 

clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp

+//== BitwiseShiftChecker.cpp ------------------------------------*- C++ -*--==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines BitwiseShiftChecker, which is a path-sensitive checker
+// that looks for undefined behavior when the operands of the bitwise shift
+// operators '<<' and '>>' are invalid (negative or too large).
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/CharUnits.h"
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
+#include "llvm/Support/FormatVariadic.h"
+#include <memory>
+
+using namespace clang;
+using namespace ento;
+using llvm::formatv;
+
+namespace {
+enum class OperandSide { Left, Right };
+
+using BugReportPtr = std::unique_ptr<PathSensitiveBugReport>;
+
+struct NoteTagTemplate {
+  llvm::StringLiteral SignInfo;
+  llvm::StringLiteral UpperBoundIntro;
+};
+
+constexpr NoteTagTemplate NoteTagTemplates[] = {
+  {"", "right operand of bit shift is less than "},
+  {"left operand of bit shift is non-negative", " and right operand is less than "},
+  {"right operand of bit shift is non-negative", " but less than "},
+  {"both operands of bit shift are non-negative", " and right operand is less than "}
+};
+
+/// An implementation detail class which is introduced to split the checker
+/// logic into several methods while maintaining a consistently updated state
+/// and access to other contextual data.
+class BitwiseShiftValidator {
+  CheckerContext &Ctx;
+  ProgramStateRef FoldedState;
+  const BinaryOperator *const Op;
+  const BugType &BT;
+  const bool PedanticFlag;
+
+  // The following data members are only used for note tag creation:
+  enum { NonNegLeft = 1, NonNegRight = 2 };
+  unsigned NonNegOperands = 0;
+
+  std::optional<unsigned> UpperBoundBitCount = std::nullopt;
+
+public:
+  BitwiseShiftValidator(const BinaryOperator *O, CheckerContext &C,
+                        const BugType &B, bool P)
+      : Ctx(C), FoldedState(C.getState()), Op(O), BT(B), PedanticFlag(P) {}
+  void run();
+
+private:
+  const Expr *operandExpr(OperandSide Side) const {
+    return Side == OperandSide::Left ? Op->getLHS() : Op->getRHS();
+  }
+
+  bool shouldPerformPedanticChecks() const {
+    // The pedantic flag has no effect under C++20 because the affected issues
+    // are no longer undefined under that version of the standard.
+    return PedanticFlag && !Ctx.getASTContext().getLangOpts().CPlusPlus20;
+  }
+
+  bool assumeRequirement(OperandSide Side, BinaryOperator::Opcode Cmp, unsigned Limit);
+
+  void recordAssumption(OperandSide Side, BinaryOperator::Opcode Cmp, unsigned Limit);
+  const NoteTag *createNoteTag() const;
+
+  BugReportPtr createBugReport(StringRef ShortMsg, StringRef Msg) const;
+
+  BugReportPtr checkOvershift();
+  BugReportPtr checkOperandNegative(OperandSide Side);
+  BugReportPtr checkLeftShiftOverflow();
+
+  bool isLeftShift() const { return Op->getOpcode() == BO_Shl; }
+  StringRef shiftDir() const { return isLeftShift() ? "left" : "right"; }
+  static StringRef pluralSuffix(unsigned n) { return n <= 1 ? "" : "s"; }
+  static StringRef verbSuffix(unsigned n) { return n <= 1 ? "s" : ""; }
+};
+
+void BitwiseShiftValidator::run() {
+  // Report a bug if the right operand is >= the bit width of the type of the
+  // left operand:
+  if (BugReportPtr BR = checkOvershift()) {
+    Ctx.emitReport(std::move(BR));
+    return;
+  }
+
+  // Report a bug if the right operand is negative:
+  if (BugReportPtr BR = checkOperandNegative(OperandSide::Right)) {
+    Ctx.emitReport(std::move(BR));
+    return;
+  }
+
+  if (shouldPerformPedanticChecks()) {
+    // Report a bug if the left operand is negative:
+    if (BugReportPtr BR = checkOperandNegative(OperandSide::Left)) {
+      Ctx.emitReport(std::move(BR));
+      return;
+    }
+
+    // Report a bug when left shift of a concrete signed value overflows:
+    if (BugReportPtr BR = checkLeftShiftOverflow()) {
+      Ctx.emitReport(std::move(BR));
+      return;
+    }
+  }
+
+  // No bugs detected, update the state and add a single note tag which
+  // summarizes the new assumptions.
+  Ctx.addTransition(FoldedState, createNoteTag());
+}
+
+/// This method checks a requirement that must be satisfied by the value on the
+/// given Side of a bitwise shift operator in well-defined code. If the
+/// requirement is incompatible with prior knowledge, this method reports
+/// failure by returning false.
+bool BitwiseShiftValidator::assumeRequirement(OperandSide Side,
+                                              BinaryOperator::Opcode Comparison,
+                                              unsigned Limit) {
+  SValBuilder &SVB = Ctx.getSValBuilder();
+
+  const SVal OperandVal = Ctx.getSVal(operandExpr(Side));
+  const auto LimitVal = SVB.makeIntVal(Limit, Ctx.getASTContext().IntTy);
+  // Note that the type of `LimitVal` must be a signed, because otherwise a
+  // negative `Val` could be converted to a large positive value.
+
+  auto ResultVal = SVB.evalBinOp(FoldedState, Comparison, OperandVal, LimitVal,
+                                 SVB.getConditionType());
+  if (auto DURes = ResultVal.getAs<DefinedOrUnknownSVal>()) {
+    auto [StTrue, StFalse] = FoldedState->assume(DURes.value());
+    if (!StTrue) {
+      // We detected undefined behavior (the caller will report it).
+      FoldedState = StFalse;
+      return false;
+    }
+    // The code may be valid, so let's assume that it's valid:
+    FoldedState = StTrue;
+    if (StFalse) {
+      // Record note tag data for the assumption that we made
+      recordAssumption(Side, Comparison, Limit);
+    }
+  }
+  return true;
+}
+
+BugReportPtr BitwiseShiftValidator::checkOvershift() {
+  const QualType LHSTy = Op->getLHS()->getType();
+  const unsigned LHSBitWidth = Ctx.getASTContext().getIntWidth(LHSTy);
+
+  if (assumeRequirement(OperandSide::Right, BO_LT, LHSBitWidth))
+    return nullptr;
+
+  const SVal Right = Ctx.getSVal(operandExpr(OperandSide::Right));
+
+  std::string RightOpStr = "";
+  if (auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>())
+    RightOpStr = formatv(" '{0}'", ConcreteRight->getValue());
+
+  std::string ShortMsg = formatv(
+      "{0} shift{1}{2} overflows the capacity of '{3}'",
+      isLeftShift() ? "Left" : "Right", RightOpStr.empty() ? "" : " by",
+      RightOpStr, LHSTy.getAsString());
+  std::string Msg =
+      formatv("The result of {0} shift is undefined because the right "
+              "operand{1} is not smaller than {2}, the capacity of '{3}'",
+              shiftDir(), RightOpStr, LHSBitWidth, LHSTy.getAsString());
+  return createBugReport(ShortMsg, Msg);
+}
+
+// Before C++20, at 5.8 [expr.shift] (N4296, 2014-11-19) the standard says
+// 1. "... The behaviour is undefined if the right operand is negative..."
+// 2. "The value of E1 << E2 ...
+//     if E1 has a signed type and non-negative value ...
+//     otherwise, the behavior is undefined."
+// 3. "The value of E1 >> E2 ...
+//     If E1 has a signed type and a negative value,
+//     the resulting value is implementation-defined."
+// However, negative left arguments work in practice and the C++20 standard
+// eliminates conditions 2 and 3.
+BugReportPtr BitwiseShiftValidator::checkOperandNegative(OperandSide Side) {
+  // If the type is unsigned, it cannot be negative
+  if (!operandExpr(Side)->getType()->isSignedIntegerType())
+    return nullptr;
+
+  // Main check: determine whether the operand is constrained to be negative
+  if (assumeRequirement(Side, BO_GE, 0))
+    return nullptr;
+
+  std::string ShortMsg = formatv("{0} operand is negative in {1} shift",
+                                 Side == OperandSide::Left ? "Left" : "Right",
+                                 shiftDir())
+                             .str();
+  std::string Msg = formatv("The result of {0} shift is undefined "
+                            "because the {1} operand is negative",
+                            shiftDir(),
+                            Side == OperandSide::Left ? "left" : "right")
+                        .str();
+
+  return createBugReport(ShortMsg, Msg);
+}
+
+BugReportPtr BitwiseShiftValidator::checkLeftShiftOverflow() {
+  // A right shift cannot be an overflowing left shift...
+  if (!isLeftShift())
+    return nullptr;
+
+  // In C++ it's well-defined to shift to the sign bit. In C however, it's UB.
+  // 5.8.2 [expr.shift] (N4296, 2014-11-19)
+  const bool ShouldPreserveSignBit = !Ctx.getLangOpts().CPlusPlus;
+
+  const Expr *LHS = operandExpr(OperandSide::Left);
+  const QualType LHSTy = LHS->getType();
+  const unsigned LeftBitWidth = Ctx.getASTContext().getIntWidth(LHSTy);
+  assert(LeftBitWidth > 0);
+
+  // Quote "For unsigned lhs, the value of LHS << RHS is the value of LHS *
+  // 2^RHS, reduced modulo maximum value of the return type plus 1."
+  if (LHSTy->isUnsignedIntegerType())
+    return nullptr;
+
+  // We only support concrete integers as left operand.
+  const auto Left = Ctx.getSVal(LHS).getAs<nonloc::ConcreteInt>();
+  if (!Left.has_value())
+    return nullptr;
+
+  // We should have already reported a bug if the left operand of the shift was
+  // negative, so it cannot be negative here.
+  assert(Left->getValue().isNonNegative());
+
+  const unsigned LeftAvailableBitWidth =
+      LeftBitWidth - static_cast<unsigned>(ShouldPreserveSignBit);
+  const unsigned UsedBitsInLeftOperand = Left->getValue().getActiveBits();
+  assert(LeftBitWidth >= UsedBitsInLeftOperand);
+  const unsigned MaximalAllowedShift =
+      LeftAvailableBitWidth - UsedBitsInLeftOperand;
+
+  if (assumeRequirement(OperandSide::Right, BO_LT, MaximalAllowedShift + 1))
+    return nullptr;
+
+  const std::string CapacityMsg =
+      formatv("because '{0}' can hold only {1} bits ({2} the sign bit)",
+                    LHSTy.getAsString(), LeftAvailableBitWidth,
+                    ShouldPreserveSignBit ? "excluding" : "including");
+
+  const SVal Right = Ctx.getSVal(Op->getRHS());
+
+  std::string ShortMsg, Msg;
+  if (const auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>()) {
+    // Here ConcreteRight must contain a small non-negative integer, because
+    // otherwise one of the earlier checks should've reported a bug.
+    const unsigned RHS = ConcreteRight->getValue().getExtValue();
+    assert(RHS > MaximalAllowedShift);
+    const unsigned OverflownBits = RHS - MaximalAllowedShift;
+    ShortMsg = formatv(
+        "The shift '{0} << {1}' overflows the capacity of '{2}'",
+        Left->getValue(), ConcreteRight->getValue(), LHSTy.getAsString());
+    Msg = formatv(
+        "The shift '{0} << {1}' is undefined {2}, so {3} bit{4} overflow{5}",
+        Left->getValue(), ConcreteRight->getValue(), CapacityMsg, OverflownBits,
+        pluralSuffix(OverflownBits), verbSuffix(OverflownBits));
+  } else {
+    ShortMsg = formatv("Left shift of '{0}' overflows the capacity of '{1}'",
+                       Left->getValue(), LHSTy.getAsString());
+    Msg = formatv(
+        "Left shift of '{0}' is undefined {1}, so some bits overflow",
+        Left->getValue(), CapacityMsg);
+  }
+
+  return createBugReport(ShortMsg, Msg);
+}
+
+void BitwiseShiftValidator::recordAssumption(OperandSide Side,
+                                             BinaryOperator::Opcode Comparison,
+                                             unsigned Limit) {
+  switch (Comparison)  {
+    case BO_GE:
+      assert(Limit == 0);
+      NonNegOperands |= (Side == OperandSide::Left ? NonNegLeft : NonNegRight);
+      break;
+    case BO_LT:
+      assert(Side == OperandSide::Right);
+      if (!UpperBoundBitCount || Limit < UpperBoundBitCount.value())
+        UpperBoundBitCount = Limit;
+      break;
+    default:
+      llvm_unreachable("this checker does not use other comparison operators");
+  }
+}
+
+const NoteTag *BitwiseShiftValidator::createNoteTag() const {
+  if (!NonNegOperands && !UpperBoundBitCount)
+    return nullptr;
+
+  SmallString<128> Buf;
+  llvm::raw_svector_ostream Out(Buf);
+  Out << "Assuming ";
+  NoteTagTemplate Templ = NoteTagTemplates[NonNegOperands];
+  Out << Templ.SignInfo;
+  if (UpperBoundBitCount)
+    Out << Templ.UpperBoundIntro << UpperBoundBitCount.value();
+  const std::string Msg(Out.str());
+
+  return Ctx.getNoteTag(Msg, /*isPrunable=*/true);
+}
+
+std::unique_ptr<PathSensitiveBugReport>
+BitwiseShiftValidator::createBugReport(StringRef ShortMsg, StringRef Msg) const {
+  ProgramStateRef State = Ctx.getState();
+  if (ExplodedNode *ErrNode = Ctx.generateErrorNode(State)) {
+    auto BR =
+        std::make_unique<PathSensitiveBugReport>(BT, ShortMsg, Msg, ErrNode);
+    bugreporter::trackExpressionValue(ErrNode, Op->getLHS(), *BR);
+    bugreporter::trackExpressionValue(ErrNode, Op->getRHS(), *BR);
+    return BR;
+  }
+  return nullptr;
+}
+} // anonymous namespace
+
+class BitwiseShiftChecker : public Checker<check::PreStmt<BinaryOperator>> {
+  mutable std::unique_ptr<BugType> BTPtr;
+
+public:
+  void checkPreStmt(const BinaryOperator *B, CheckerContext &Ctx) const {
+    BinaryOperator::Opcode Op = B->getOpcode();
+
+    if (Op != BO_Shl && Op != BO_Shr)
+      return;
+
+    if (!BTPtr)
+      BTPtr = std::make_unique<BugType>(this, "Bitwise shift",
+                                        "Suspicious operation");
+
+    BitwiseShiftValidator(B, Ctx, *BTPtr, Pedantic).run();
+  }
+
+  bool Pedantic = false;
+};
+
+void ento::registerBitwiseShiftChecker(CheckerManager &Mgr) {
+  auto *Chk = Mgr.registerChecker<BitwiseShiftChecker>();
+  const AnalyzerOptions &Opts = Mgr.getAnalyzerOptions();
+  Chk->Pedantic = Opts.getCheckerBooleanOption(Chk, "Pedantic");
+}
+
+bool ento::shouldRegisterBitwiseShiftChecker(const CheckerManager &mgr) {
+  return true;
+}

clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   TargetParser
   )
 
 add_clang_library(clangStaticAnalyzerCheckers
   AnalysisOrderChecker.cpp
   AnalyzerStatsChecker.cpp
   ArrayBoundChecker.cpp
   ArrayBoundCheckerV2.cpp
   BasicObjCFoundationChecks.cpp
+  BitwiseShiftChecker.cpp
   BlockInCriticalSectionChecker.cpp
   BoolAssignmentChecker.cpp
   BuiltinFunctionChecker.cpp
   CStringChecker.cpp
   CStringSyntaxChecker.cpp
   CallAndMessageChecker.cpp
   CastSizeChecker.cpp
   CastToStructChecker.cpp

clang/test/Analysis/analyzer-config.c

 // CHECK-NEXT: cfg-conditional-static-initializers = true
 // CHECK-NEXT: cfg-expand-default-aggr-inits = false
 // CHECK-NEXT: cfg-implicit-dtors = true
 // CHECK-NEXT: cfg-lifetime = false
 // CHECK-NEXT: cfg-loopexit = false
 // CHECK-NEXT: cfg-rich-constructors = true
 // CHECK-NEXT: cfg-scopes = false
 // CHECK-NEXT: cfg-temporary-dtors = true
+// CHECK-NEXT: core.BitwiseShift:Pedantic = false
 // CHECK-NEXT: core.CallAndMessage:ArgInitializedness = true
 // CHECK-NEXT: core.CallAndMessage:ArgPointeeInitializedness = false
 // CHECK-NEXT: core.CallAndMessage:CXXDeallocationArg = true
 // CHECK-NEXT: core.CallAndMessage:CXXThisMethodCall = true
 // CHECK-NEXT: core.CallAndMessage:FunctionPointer = true
 // CHECK-NEXT: core.CallAndMessage:NilReceiver = true
 // CHECK-NEXT: core.CallAndMessage:ParameterCount = true
 // CHECK-NEXT: core.CallAndMessage:UndefReceiver = true

clang/test/Analysis/analyzer-enabled-checkers.c

 // RUN: %clang --analyze %s --target=x86_64-pc-linux-gnu \
 // RUN:   -Xclang -analyzer-list-enabled-checkers \
 // RUN:   -Xclang -analyzer-display-progress \
 // RUN:   2>&1 | FileCheck %s --implicit-check-not=ANALYZE \
 // RUN:                       --implicit-check-not=\.
 
 // CHECK:      OVERVIEW: Clang Static Analyzer Enabled Checkers List
 // CHECK-EMPTY:
 // CHECK-NEXT: apiModeling.Errno
 // CHECK-NEXT: apiModeling.TrustNonnull
 // CHECK-NEXT: apiModeling.TrustReturnsNonnull
 // CHECK-NEXT: apiModeling.llvm.CastValue
 // CHECK-NEXT: apiModeling.llvm.ReturnValue
+// CHECK-NEXT: core.BitwiseShift
 // CHECK-NEXT: core.CallAndMessageModeling
 // CHECK-NEXT: core.CallAndMessage
 // CHECK-NEXT: core.DivideZero
 // CHECK-NEXT: core.DynamicTypePropagation
 // CHECK-NEXT: core.NonNullParamChecker
 // CHECK-NEXT: core.NonnilStringConstants
 // CHECK-NEXT: core.NullDereference
 // CHECK-NEXT: core.StackAddrEscapeBase

clang/test/Analysis/bitwise-ops-nocrash.c

-// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-output=text -triple x86_64-linux-gnu -Wno-shift-count-overflow -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-disable-checker=core.BitwiseShift -analyzer-output=text -triple x86_64-linux-gnu -Wno-shift-count-overflow -verify %s
+
+// NOTE: This test file disables the checker core.BitwiseShift (which would
+// report all undefined behavior connected to bitwise shifts) to verify the
+// behavior of core.UndefinedBinaryOperatorResult (which resports cases when
+// the constant folding in BasicValueFactory produces an "undefined" result
+// from a shift or any other binary operator).
 
 #define offsetof(type,memb) ((unsigned long)&((type*)0)->memb)
 
 typedef struct {
   unsigned long guest_counter;
   unsigned int guest_fpc;
 } S;
 
 // no crash
 int left_shift_overflow_no_crash(unsigned int i) {
   unsigned shift = 323U; // expected-note{{'shift' initialized to 323}}
-  switch (i) { // expected-note{{Control jumps to 'case 8:'  at line 14}}
+  switch (i) { // expected-note{{Control jumps to 'case 8:'  at line 20}}
   case offsetof(S, guest_fpc):
     return 3 << shift; // expected-warning{{The result of the left shift is undefined due to shifting by '323', which is greater or equal to the width of type 'int'}}
     // expected-note@-1{{The result of the left shift is undefined due to shifting by '323', which is greater or equal to the width of type 'int'}}
   default:
     break;
   }
 
   return 0;
 }

clang/test/Analysis/bitwise-ops.c

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -triple x86_64-apple-darwin13 -Wno-shift-count-overflow -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-disable-checker=core.BitwiseShift -triple x86_64-apple-darwin13 -Wno-shift-count-overflow -verify %s
+
+// NOTE: This test file disables the checker core.BitwiseShift (which would
+// report all undefined behavior connected to bitwise shifts) to verify the
+// behavior of core.UndefinedBinaryOperatorResult (which resports cases when
+// the constant folding in BasicValueFactory produces an "undefined" result
+// from a shift or any other binary operator).
 
 void clang_analyzer_eval(int);
 #define CHECK(expr) if (!(expr)) return; clang_analyzer_eval(expr)
 
 void testPersistentConstraints(int x, int y) {
   // Basic check
   CHECK(x); // expected-warning{{TRUE}}
   CHECK(x & 1); // expected-warning{{TRUE}}
   
   CHECK(1 - x); // expected-warning{{TRUE}}
   CHECK(x & y); // expected-warning{{TRUE}}
 }
 
 int testConstantShifts_PR18073(int which) {
-  // FIXME: We should have a checker that actually specifically checks bitwise
-  // shifts against the width of the LHS's /static/ type, rather than just
-  // having BasicValueFactory return "undefined" when dealing with two constant
-  // operands.
   switch (which) {
   case 1:
     return 0ULL << 63; // no-warning
   case 2:
     return 0ULL << 64; // expected-warning{{The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'}}
   case 3:
     return 0ULL << 65; // expected-warning{{The result of the left shift is undefined due to shifting by '65', which is greater or equal to the width of type 'unsigned long long'}}
 

clang/test/Analysis/bitwise-shift-common.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-output=text -verify \
+// RUN:    -triple x86_64-pc-linux-gnu -x c %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+//
+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-config core.BitwiseShift:Pedantic=true \
+// RUN:    -analyzer-output=text -verify \
+// RUN:    -triple x86_64-pc-linux-gnu -x c++ -std=c++20 %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+//
+// This test file verifies the default behavior of the BitwiseShift checker,
+// which reports the serious logical defects, but doesn't warn on code that's
+// legal under C++20 (or later) and widely accepted (but theoretically
+// undefined) in other compilation modes.
+
+// TEST NEGATIVE RIGHT OPERAND
+//===----------------------------------------------------------------------===//
+
+int negative_right_operand_literal(void) {
+  return 2 << -2;
+  // expected-warning@-1 {{Right operand is negative in left shift}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand is negative}}
+}
+
+int negative_right_operand_symbolic(int left, int right) {
+  // expected-note@+2 {{Assuming 'right' is < 0}}
+  // expected-note@+1 {{Taking false branch}}
+  if (right >= 0)
+    return 0;
+  return left >> right;
+  // expected-warning@-1 {{Right operand is negative in right shift}}
+  // expected-note@-2 {{The result of right shift is undefined because the right operand is negative}}
+}
+
+int negative_right_operand_compound(short arg) {
+  // expected-note@+2 {{Assuming 'arg' is < 2}}
+  // expected-note@+1 {{Taking false branch}}
+  if (arg >= 2 )
+    return 0;
+  return 2 << (arg - 1 - 1 - 1);
+  // expected-warning@-1 {{Right operand is negative in left shift}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand is negative}}
+}
+
+// TEST TOO LARGE RIGHT OPERAND
+//===----------------------------------------------------------------------===//
+
+int too_large_right_operand_literal(void) {
+  return 2 << 32;
+  // expected-warning@-1 {{Left shift by '32' overflows the capacity of 'int'}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand '32' is not smaller than 32, the capacity of 'int'}}
+}
+
+int too_large_right_operand_exact_symbolic(int arg) {
+  // expected-note@+4 {{Assuming 'arg' is > 33}}
+  // expected-note@+3 {{Left side of '||' is false}}
+  // expected-note@+2 {{Assuming 'arg' is < 35}}
+  // expected-note@+1 {{Taking false branch}}
+  if (arg <= 33 || arg >= 35)
+    return 0;
+  return 3 << arg;
+  // expected-warning@-1 {{Left shift by '34' overflows the capacity of 'int'}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand '34' is not smaller than 32, the capacity of 'int'}}
+}
+
+int too_large_right_operand_exact_symbolic_2(char arg) {
+  // expected-note@+2 {{Assuming the condition is false}}
+  // expected-note@+1 {{Taking false branch}}
+  if (arg != ' ')
+    return 0;
+  return 3 << arg;
+  // expected-warning@-1 {{Left shift by '32' overflows the capacity of 'int'}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand '32' is not smaller than 32, the capacity of 'int'}}
+}
+
+int too_large_right_operand_symbolic(int left, int right) {
+  // expected-note@+2 {{Assuming 'right' is > 31}}
+  // expected-note@+1 {{Taking false branch}}
+  if (right <= 31)
+    return 0;
+  return left >> right;
+  // expected-warning@-1 {{Right shift overflows the capacity of 'int'}}
+  // expected-note@-2 {{The result of right shift is undefined because the right operand is not smaller than 32, the capacity of 'int'}}
+  // NOTE: the messages of the checker are a bit vague in this case, but the
+  // tracking of the variables reveals our knowledge about them.
+}
+
+int too_large_right_operand_compound(unsigned short arg) {
+  // Note: this would be valid code with an 'unsigned int' because
+  // unsigned addition is allowed to overflow.
+  return 1 << (32 + arg);
+  // expected-warning@-1 {{Left shift overflows the capacity of 'int'}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand is not smaller than 32, the capacity of 'int'}}
+}
+
+// TEST STATE UPDATES
+//===----------------------------------------------------------------------===//
+
+void state_update(char a, int *p) {
+  // NOTE: with 'int a' this would not produce a bug report because the engine
+  // would not rule out an overflow.
+  *p += 1 << a;
+  // expected-note@-1 {{Assuming right operand of bit shift is non-negative but less than 32}}
+  *p += 1 << (a + 32);
+  // expected-warning@-1 {{Left shift overflows the capacity of 'int'}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand is not smaller than 32, the capacity of 'int'}}
+}
+
+void state_update_2(char a, int *p) {
+  *p += 1234 >> (a + 32);
+  // expected-note@-1 {{Assuming right operand of bit shift is non-negative but less than 32}}
+  *p += 1234 >> a;
+  // expected-warning@-1 {{Right operand is negative in right shift}}
+  // expected-note@-2 {{The result of right shift is undefined because the right operand is negative}}
+}
+
+// TEST EXPRESSION TRACKING
+//===----------------------------------------------------------------------===//
+// Expression tracking a "generic" tool that's used by many other checkers,
+// so this is just a minimal test to see that it's activated.
+
+void setValue(unsigned *p, unsigned newval) {
+  *p = newval;
+  // expected-note@-1 {{The value 33 is assigned to 'right'}}
+}
+
+int expression_tracked_back(void) {
+  unsigned left = 115; // expected-note {{'left' initialized to 115}}
+  unsigned right;
+  setValue(&right, 33);
+  // expected-note@-1 {{Calling 'setValue'}}
+  // expected-note@-2 {{Passing the value 33 via 2nd parameter 'newval'}}
+  // expected-note@-3 {{Returning from 'setValue'}}
+
+  return left << right;
+  // expected-warning@-1 {{Left shift by '33' overflows the capacity of 'unsigned int'}}
+  // expected-note@-2 {{The result of left shift is undefined because the right operand '33' is not smaller than 32, the capacity of 'unsigned int'}}
+}
+
+// TEST PERMISSIVENESS
+//===----------------------------------------------------------------------===//
+
+int allow_overflows_and_negative_operands(void) {
+  // These are all legal under C++ 20 and many compilers accept them under
+  // earlier standards as well.
+  int int_min = 1 << 31; // no-warning
+  int this_overflows = 1027 << 30; // no-warning
+  return (-2 << 5) + (-3 >> 4); // no-warning
+}
+
+int double_negative(void) {
+  return -2 >> -2;
+  // expected-warning@-1 {{Right operand is negative in right shift}}
+  // expected-note@-2 {{The result of right shift is undefined because the right operand is negative}}
+}

clang/test/Analysis/bitwise-shift-pedantic.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-config core.BitwiseShift:Pedantic=true \
+// RUN:    -analyzer-output=text -verify=expected,c \
+// RUN:    -triple x86_64-pc-linux-gnu -x c %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+//
+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-config core.BitwiseShift:Pedantic=true \
+// RUN:    -analyzer-output=text -verify=expected,cxx \
+// RUN:    -triple x86_64-pc-linux-gnu -x c++ -std=c++14 %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+
+// This test file verifies the pedantic mode of the BitwiseShift checker, which
+// also reports issues that are undefined behavior (according to the standard,
+// under C and in C++ before C++20), but would be accepted by many compilers.
+
+// TEST NEGATIVE LEFT OPERAND
+//===----------------------------------------------------------------------===//
+
+int negative_left_operand_literal(void) {
+  return -2 << 2;
+  // expected-warning@-1 {{Left operand is negative in left shift}}
+  // expected-note@-2 {{The result of left shift is undefined because the left operand is negative}}
+}
+
+int negative_left_operand_symbolic(int left, int right) {
+  // expected-note@+2 {{Assuming 'left' is < 0}}
+  // expected-note@+1 {{Taking false branch}}
+  if (left >= 0)
+    return 0;
+  return left >> right;
+  // expected-warning@-1 {{Left operand is negative in right shift}}
+  // expected-note@-2 {{The result of right shift is undefined because the left operand is negative}}
+}
+
+int negative_left_operand_compound(short arg) {
+  // expected-note@+2 {{Assuming 'arg' is < 0}}
+  // expected-note@+1 {{Taking false branch}}
+  if (arg >= 0)
+    return 0;
+  return (arg - 3) << 2;
+  // expected-warning@-1 {{Left operand is negative in left shift}}
+  // expected-note@-2 {{The result of left shift is undefined because the left operand is negative}}
+}
+
+int double_negative(void) {
+  // In this case we still report that the right operand is negative, because
+  // that's the more "serious" issue:
+  return -2 >> -2;
+  // expected-warning@-1 {{Right operand is negative in right shift}}
+  // expected-note@-2 {{The result of right shift is undefined because the right operand is negative}}
+}
+
+int single_unknown_negative(int arg) {
+  // In this case just one of the operands will be negative, so we end up
+  // reporting the left operand after assuming that the right operand is
+  // positive.
+  // expected-note@+2 {{Assuming 'arg' is not equal to 0}}
+  // expected-note@+1 {{Taking false branch}}
+  if (!arg)
+    return 0;
+  // We're first checking the right operand, record that it must be positive,
+  // then report that then the left argument must be negative.
+  return -arg << arg;
+  // expected-warning@-1 {{Left operand is negative in left shift}}
+  // expected-note@-2 {{The result of left shift is undefined because the left operand is negative}}
+}
+
+void shift_negative_by_zero(int c) {
+  // This seems to be innocent, but the standard (before C++20) clearly implies
+  // that this is UB, so we should report it in pedantic mode.
+  c = (-1) << 0;
+  // expected-warning@-1 {{Left operand is negative in left shift}}
+  // expected-note@-2 {{The result of left shift is undefined because the left operand is negative}}
+}
+
+// TEST OVERFLOW OF CONCRETE SIGNED LEFT OPERAND
+//===----------------------------------------------------------------------===//
+// (the most complex and least important part of the checker)
+
+int concrete_overflow_literal(void) {
+  // 27 in binary is 11011 (5 bits), when shifted by 28 bits it becomes
+  // 1_10110000_00000000_00000000_00000000
+  return 27 << 28;
+  // expected-warning@-1 {{The shift '27 << 28' overflows the capacity of 'int'}}
+  // cxx-note@-2 {{The shift '27 << 28' is undefined because 'int' can hold only 32 bits (including the sign bit), so 1 bit overflows}}
+  // c-note@-3 {{The shift '27 << 28' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so 2 bits overflow}}
+}
+
+int concrete_overflow_symbolic(int arg) {
+  // 29 in binary is 11101 (5 bits), when shifted by 29 bits it becomes
+  // 11_10100000_00000000_00000000_00000000
+
+  // expected-note@+2 {{Assuming 'arg' is equal to 29}}
+  // expected-note@+1 {{Taking false branch}}
+  if (arg != 29)
+    return 0;
+  return arg << arg;
+  // expected-warning@-1 {{The shift '29 << 29' overflows the capacity of 'int'}}
+  // cxx-note@-2 {{The shift '29 << 29' is undefined because 'int' can hold only 32 bits (including the sign bit), so 2 bits overflow}}
+  // c-note@-3 {{The shift '29 << 29' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so 3 bits overflow}}
+}
+
+int concrete_overflow_language_difference(void) {
+  // 21 in binary is 10101 (5 bits), when shifted by 27 bits it becomes
+  // 10101000_00000000_00000000_00000000
+  // This does not overflow the 32-bit capacity of int, but reaches the sign
+  // bit, which is undefined under C (but accepted in C++ even before C++20).
+  return 21 << 27;
+  // c-warning@-1 {{The shift '21 << 27' overflows the capacity of 'int'}}
+  // c-note@-2 {{The shift '21 << 27' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so 1 bit overflows}}
+}
+
+int concrete_overflow_int_min(void) {
+  // Another case that's undefined in C but valid in all C++ versions.
+  // Note the "represented by 1 bit" special case
+  return 1 << 31;
+  // c-warning@-1 {{The shift '1 << 31' overflows the capacity of 'int'}}
+  // c-note@-2 {{The shift '1 << 31' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so 1 bit overflows}}
+}
+
+int concrete_overflow_vague(int arg) {
+  // expected-note@+2 {{Assuming 'arg' is > 25}}
+  // expected-note@+1 {{Taking false branch}}
+  if (arg <= 25)
+    return 0;
+  return 1024 << arg;
+    // expected-warning@-1 {{Left shift of '1024' overflows the capacity of 'int'}}
+  // cxx-note@-2 {{Left shift of '1024' is undefined because 'int' can hold only 32 bits (including the sign bit), so some bits overflow}}
+  // c-note@-3 {{Left shift of '1024' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so some bits overflow}}
+}
+
+int concrete_overflow_vague_only_c(int arg) {
+  // A third case that's undefined in C but valid in all C++ versions.
+
+  // c-note@+2 {{Assuming 'arg' is > 20}}
+  // c-note@+1 {{Taking false branch}}
+  if (arg <= 20)
+    return 0;
+  return 1024 << arg;
+  // c-warning@-1 {{Left shift of '1024' overflows the capacity of 'int'}}
+  // c-note@-2 {{Left shift of '1024' is undefined because 'int' can hold only 31 bits (excluding the sign bit), so some bits overflow}}
+}
+
+int concrete_overflow_vague_left(int arg) {
+  // This kind of overflow check only handles concrete values on the LHS. With
+  // some effort it would be possible to report errors in cases like this; but
+  // it's probably a waste of time especially considering that overflows of
+  // left shifts became well-defined in C++20.
+
+  if (arg <= 1024)
+    return 0;
+  return arg << 25; // no-warning
+}
+
+int concrete_overflow_shift_zero(void) {
+  // This is legal, even in C.
+  // The relevant rule (as paraphrased on cppreference.com) is:
+  // "For signed LHS with nonnegative values, the value of LHS << RHS is
+  // LHS * 2^RHS if it is representable in the promoted type of lhs, otherwise
+  // the behavior is undefined."
+  return 0 << 31; // no-warning
+}

clang/test/Analysis/bitwise-shift-sanity-checks.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-config core.BitwiseShift:Pedantic=true \
+// RUN:    -verify=expected,pedantic \
+// RUN:    -triple x86_64-pc-linux-gnu -x c %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+//
+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-config core.BitwiseShift:Pedantic=true \
+// RUN:    -verify=expected,pedantic \
+// RUN:    -triple x86_64-pc-linux-gnu -x c++ -std=c++14 %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+//
+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -verify=expected \
+// RUN:    -triple x86_64-pc-linux-gnu -x c++ -std=c++20 %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+
+// This test file verifies that the BitwiseShift checker does not crash or
+// report false positives (at least on the cases that are listed here...)
+// For the sake of brevity, 'note' output is not checked in this file.
+
+// TEST OBVIOUSLY CORRECT CODE
+//===----------------------------------------------------------------------===//
+
+unsigned shift_unsigned(void) {
+  // Shifts of unsigned LHS may overflow, even if the RHS is signed.
+  // In shifts the type of the right operand does not affect the type of the
+  // calculation and the result.
+  return 1024u << 25ll; // no-warning
+}
+
+int shift_zeroes(void) {
+  return 0 << 0; // no-warning
+}
+
+int no_info(int left, int right) {
+  return left << right; // no-warning
+}
+
+int all_okay(int left, int right) {
+  if (left < 0 || right < 0)
+    return 42;
+  return (left << right) + (left >> right); // no-warning
+}
+
+// DOCUMENT A LIMITATION OF THE ANALYZER ENGINE
+//===----------------------------------------------------------------------===//
+
+int signed_arithmetic_good(int left, int right) {
+  if (right >= 32)
+    return 0;
+  return left << (right - 32);
+  // expected-warning@-1 {{Right operand is negative in left shift}}
+}
+
+int signed_arithmetic_bad(int left, int right) {
+  // FIXME: The analyzer engine handles overflow of signed values as if it was
+  // a valid code path, so in this case it will think that that (right + 32) is
+  // either at least 32 *or* very negative after an overflow.
+  // As checkOvershift() is called before checkOperandNegative(), the checker
+  // will first rule out the case when (right + 32) is larger than 32 and then
+  // it reports that it's negative. Swapping the order of the two checks would
+  // trigger an analogous fault in signed_aritmetic_good().
+  if (right < 0)
+    return 0;
+  return left << (right + 32);
+  // expected-warning@-1 {{Right operand is negative in left shift}}
+  // FIXME: we should rather have {{Left shift overflows the capacity of 'int'}}
+}
+
+// TEST THE EXAMPLES FROM THE DOCUMENTATION
+//===----------------------------------------------------------------------===//
+
+void basic_examples(int a, int b) {
+  if (b < 0) {
+    b = a << b; // expected-warning {{Right operand is negative in left shift}}
+  } else if (b >= 32) {
+    b = a >> b; // expected-warning {{Right shift overflows the capacity of 'int'}}
+  }
+}
+
+int pedantic_examples(int a, int b) {
+  if (a < 0) {
+    return a >> b; // pedantic-warning {{Left operand is negative in right shift}}
+  }
+  a = 1000u << 31; // OK, overflow of unsigned shift is well-defined, a == 0
+  if (b > 10) {
+    a = b << 31; // this is UB before C++20, but the checker doesn't warn because
+                 // it doesn't know the exact value of b
+  }
+  return 1000 << 31; // pedantic-warning {{The shift '1000 << 31' overflows the capacity of 'int'}}
+}
+
+// TEST UNUSUAL CODE THAT SHOULD NOT CRASH
+//===----------------------------------------------------------------------===//
+
+__int128 large_left(void) {
+  // Ensure that we do not crash when the left operand doesn't fit in 64 bits.
+  return (__int128) 1 << 63 << 10 << 10; // no-crash
+}
+
+int large_right(void) {
+  // Ensure that we do not crash when the right operand doesn't fit in 64 bits.
+  return 1 << ((__int128) 1 << 118); // no-crash
+  // expected-warning@-1 {{Left shift by '332306998946228968225951765070086144' overflows the capacity of 'int'}}
+}
+
+void doubles_cast_to_integer(int *c) {
+  *c = 1 << (int)1.5;          // no-crash
+  *c = ((int)1.5) << 1;        // no-crash
+  *c = ((int)1.5) << (int)1.5; // no-crash
+}

clang/test/Analysis/bitwise-shift-state-update.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-config core.BitwiseShift:Pedantic=true \
+// RUN:    -analyzer-checker=debug.ExprInspection \
+// RUN:    -analyzer-config eagerly-assume=false \
+// RUN:    -verify=expected,c \
+// RUN:    -triple x86_64-pc-linux-gnu -x c %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+//
+// RUN: %clang_analyze_cc1 -analyzer-checker=core.BitwiseShift \
+// RUN:    -analyzer-config core.BitwiseShift:Pedantic=true \
+// RUN:    -analyzer-checker=debug.ExprInspection \
+// RUN:    -analyzer-config eagerly-assume=false \
+// RUN:    -verify=expected,cxx \
+// RUN:    -triple x86_64-pc-linux-gnu -x c++ -std=c++14 %s \
+// RUN:    -Wno-shift-count-negative -Wno-shift-negative-value \
+// RUN:    -Wno-shift-count-overflow -Wno-shift-overflow \
+// RUN:    -Wno-shift-sign-overflow
+
+// Tests for validating the state updates provided by the BitwiseShift checker.
+// These clang_analyzer_value() tests are in a separate file because
+// debug.ExprInspection repeats each 'warning' with an superfluous 'note', so
+// note level output (-analyzer-output=text) is not enabled in this file.
+
+void clang_analyzer_value(int);
+void clang_analyzer_eval(int);
+
+int state_update_generic(int left, int right) {
+  int x = left << right;
+  clang_analyzer_value(left); // expected-warning {{32s:{ [0, 2147483647] } }}
+  clang_analyzer_value(right); // expected-warning {{32s:{ [0, 31] } }}
+  return x;
+}
+
+int state_update_exact_shift(int arg) {
+  int x = 65535 << arg;
+  clang_analyzer_value(arg);
+  // c-warning@-1 {{32s:{ [0, 15] } }}
+  // cxx-warning@-2 {{32s:{ [0, 16] } }}
+  return x;
+}

clang/test/Analysis/casts.c

 extern int globalFunc(void);
 void no_crash_on_symsym_cast_to_long(void) {
   char c = globalFunc() - 5;
   c == 0;
   globalA -= c;
   globalA == 3;
   (long)globalA << 48;
   #ifdef BIT32
-  // expected-warning@-2{{The result of the left shift is undefined due to shifting by '48', which is greater or equal to the width of type 'long'}}
+  // expected-warning@-2{{Left shift by '48' overflows the capacity of 'long'}}
   #else
   // expected-no-diagnostics
   #endif
 }
 
 #endif
 
 char no_crash_SymbolCast_of_float_type_aux(int *p) {

clang/test/Analysis/diagnostics/track_subexpressions.cpp

 // RUN: %clang_analyze_cc1 -x c++ -analyzer-checker=core -analyzer-output=text -verify %s
 
 typedef unsigned char uint8_t;
 
 #define UINT8_MAX 255
 #define TCP_MAXWIN 65535
 
 uint8_t get_uint8_max() {
   uint8_t rcvscale = UINT8_MAX; // expected-note{{'rcvscale' initialized to 255}}
   return rcvscale; // expected-note{{Returning the value 255 (loaded from 'rcvscale')}}
 }
 
 void shift_by_undefined_value() {
   uint8_t shift_amount = get_uint8_max(); // expected-note{{'shift_amount' initialized to 255}}
-                                // expected-note@-1{{Calling 'get_uint8_max'}}
-                                // expected-note@-2{{Returning from 'get_uint8_max'}}
-  (void)(TCP_MAXWIN << shift_amount); // expected-warning{{The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'int'}}
-                                      // expected-note@-1{{The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'int'}}
+  (void)(TCP_MAXWIN << shift_amount); // expected-warning{{Left shift by '255' overflows the capacity of 'int'}}
+  // expected-note@-1{{The result of left shift is undefined because the right operand '255' is not smaller than 32, the capacity of 'int'}}
 }
 
 namespace array_index_tracking {
 void consume(int);
 
 int getIndex(int x) {
   int a;
   if (x > 0) // expected-note {{Assuming 'x' is > 0}}

clang/test/Analysis/left-shift-cxx2a.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -triple x86_64-apple-darwin13 -Wno-shift-count-overflow -verify=expected,cxx17 -std=c++17 %s
-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -triple x86_64-apple-darwin13 -Wno-shift-count-overflow -verify=expected,cxx2a -std=c++2a %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-disable-checker core.BitwiseShift -triple x86_64-apple-darwin13 -Wno-shift-count-overflow -verify=expected,cxx17 -std=c++17 %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-disable-checker core.BitwiseShift -triple x86_64-apple-darwin13 -Wno-shift-count-overflow -verify=expected,cxx2a -std=c++2a %s
 
 int testNegativeShift(int a) {
   if (a == -5) {
     return 1 << a; // expected-warning{{The result of the left shift is undefined because the right operand is negative}}
   }
   return 0;
 }
 

clang/test/Analysis/std-c-library-functions-arg-enabled-checkers.c

 // CHECK-NEXT: core.NonNullParamChecker
 // CHECK-NEXT: alpha.unix.Stream
 // CHECK-NEXT: alpha.unix.StdCLibraryFunctions
 // CHECK-NEXT: apiModeling.Errno
 // CHECK-NEXT: apiModeling.TrustNonnull
 // CHECK-NEXT: apiModeling.TrustReturnsNonnull
 // CHECK-NEXT: apiModeling.llvm.CastValue
 // CHECK-NEXT: apiModeling.llvm.ReturnValue
+// CHECK-NEXT: core.BitwiseShift
 // CHECK-NEXT: core.DivideZero
 // CHECK-NEXT: core.DynamicTypePropagation
 // CHECK-NEXT: core.NonnilStringConstants
 // CHECK-NEXT: core.NullDereference
 // CHECK-NEXT: core.StackAddrEscapeBase
 // CHECK-NEXT: core.StackAddressEscape
 // CHECK-NEXT: core.UndefinedBinaryOperatorResult
 // CHECK-NEXT: core.VLASize

clang/test/Analysis/symbol-simplification-nonloc-loc.cpp

 // RUN: %clang_analyze_cc1 -analyzer-checker=core %s \
 // RUN:    -triple x86_64-pc-linux-gnu -verify
 
 #define BINOP(OP) [](auto x, auto y) { return x OP y; }
 
 template <typename BinOp>
 void nonloc_OP_loc(int *p, BinOp op) {
   long p_as_integer = (long)p;
   if (op(12, p_as_integer) != 11)
     return;
 
   // Perfectly constrain 'p', thus 'p_as_integer', and trigger a simplification
   // of the previously recorded constraint.
   if (p) {
     // no-crash
   }
-  if (p == (int *)0x404) {
+  if (p == (int *)0x1b) {
     // no-crash
   }
 }
 
 // Same as before, but the operands are swapped.
 template <typename BinOp>
 void loc_OP_nonloc(int *p, BinOp op) {
   long p_as_integer = (long)p;
   if (op(p_as_integer, 12) != 11)
     return;
 
   if (p) {
     // no-crash
   }
-  if (p == (int *)0x404) {
+  if (p == (int *)0x1b) {
     // no-crash
   }
 }
 
 void instantiate_tests_for_nonloc_OP_loc(int *p) {
   // Multiplicative and additive operators:
   nonloc_OP_loc(p, BINOP(*));
   nonloc_OP_loc(p, BINOP(/)); // no-crash
   nonloc_OP_loc(p, BINOP(%)); // no-crash
   nonloc_OP_loc(p, BINOP(+));
   nonloc_OP_loc(p, BINOP(-)); // no-crash
 
   // Bitwise operators:
-  // expected-warning@+2 {{The result of the left shift is undefined due to shifting by '1028', which is greater or equal to the width of type 'int' [core.UndefinedBinaryOperatorResult]}}
-  // expected-warning@+2 {{The result of the right shift is undefined due to shifting by '1028', which is greater or equal to the width of type 'int' [core.UndefinedBinaryOperatorResult]}}
   nonloc_OP_loc(p, BINOP(<<)); // no-crash
   nonloc_OP_loc(p, BINOP(>>)); // no-crash
   nonloc_OP_loc(p, BINOP(&));
   nonloc_OP_loc(p, BINOP(^));
   nonloc_OP_loc(p, BINOP(|));
 }
 
 void instantiate_tests_for_loc_OP_nonloc(int *p) {